NMM Метод NMM - (Nonadditive Multiply Module) (умножение без сложения) +-----+ A0..A3 -| NMM |- P0..P7 B0..B3 -| | +-----+ A3 A2 A1 A0 * B3 B2 B1 B0 ------------------------ A3B0 A2B0 A1B0 A0B0 + A3B1 A2B1 A1B1 A0B1 A3B2 A2B2 A1B2 A0B2 A3B3 A2B3 A1B3 A0B3 ----------------------------------- P7P6 P5 P4 P3 P2 P1 P0 NMM 4x2 умножитель:
A3B0 0 A2B0 0 A1B0 0 A0B0 | | | | | | | V V V V V V | +------+ +------+ +-----+ | | CSA |<-A2B1 | CSA |<-A1B1 | CSA |<-A0B1 | +------+ +------+ +-----+ | |C |S |C |S |C |S | A3B1 +--------+ | +---------+ | +---------+ | | | | | | | | | | V V V V V V | | +------+ +------+ +------+ | | | CSA |<-A2B2 | CSA |<-A1B2 | CSA |<-A0B2 | | +------+ +------+ +------+ | | |C |S |C |S |C |S | | A3B2 +-----+ | +---------+ | +---------+ | | | | | | | | | | | | V V V V V V | | | +-----+ +------+ +------+ | | | A2B3 ->| CSA | | CSA |<-A1B3 | CSA |<-A0B3 | | | +-----+ +------+ +------+ | V V |C |S |C |S |C | | P1 P0 A3B3 +---+ | +--+ +-+ +-----+ | | | | | | | | | | V V V V V V | | +-----+ +------+ +------+ | | | CSA |<-+ | CSA |<-+ | CSA |<- 0 | | +-----+ | +------+ | +------+ | | |C |S | |C |S | |C |S | | | | +--+ | +---+ | | | | | | | | | V V V V V V P7 P6 P5 P4 P3 P2 Время работы T = 19L
Пример реализации Двухбитного умножителя (на базе NMM) (правда особой разницы на 2х битах мы не увидем). a1 a0 * b1 b0 ---------------- + a1b0 a0b0 a1b1 a0b1 ----------------- ^ | +--- не тянет за собой перенос Результат: AND элементы и каскад полусумматоров.
Иерархия NMM умножителей:
Ячейка NMM умножителя: library ieee; use ieee.std_logic_1164.all; entity nmm_cell is port( a,b,cin,sin : in std_logic; sout, cout : out std_logic); end nmm_cell; architecture cell of nmm_cell is signal x : std_logic; component full_adder is port ( a,b,cin : in std_logic; s, cout : out std_logic); end component; begin fa1 : full_adder port map(sin,x,cin,sout,cout); x <= a and b; end cell; NMM умножитель (любого размера): library ieee; use ieee.std_logic_1164.all; entity nmm is generic(n : natural range 32 downto 2); port( a,b : in std_logic_vector(N-1 downto 0); p : out std_logic_vector(2*N-1 downto 0)); end nmm; architecture nmmi of nmm is type sum_array is array(N downto 0, N downto 0) of std_logic; type carry_array is array(N-1 downto 0, N downto 0) of std_logic; signal sum: sum_array; signal carry : carry_array; component nmm_cell is port( a,b,cin,sin : in std_logic; sout, cout : out std_logic); end component; begin row : for i in N-1 downto 0 generate col: for j in N-1 downto 0 generate ex_cell: nmm_cell port map(a(i),b(j),carry(i,j),sum(i,j+1), sum(i+1,j),carry(i,j+1)); top_row: if i = 0 generate sum(i,j+1) <= '0'; end generate; bottom_row: if i = N-1 generate p(N+j) <= sum(i+1,j+1); end generate; left_col: if j = N - 1 generate sum(i+1,j+1) <= carry(i,j+1); end generate; right_col: if j = 0 generate carry(i,j) <= '0'; p(i) <= sum(i+1,j); end generate; end generate; end generate; end nmmi; Результат моделирования NMM умножителя 3x3 (фрагмент):
Пример умножителя 8x8 на основе NMM 4x4 и дерева Уолиса: +------------+ +-----------+ +-----------+ +-----------+ | Ah * Bh | | Al * Bh | | Ah * Bl | | Al * Bl | +------------+ +-----------+ +-----------+ +-----------+ |H |L |H |L |H |L |H |L | | +----+ | | | | | | | | +--------=-----+ | +--------+ V | | | | | | | R3..0 | V V V V V V | +-----------+ +------------+ | | CSA 1 | | CSA 2 | | +-----------+ +------------+ | |C12.9 |S11.8 |S7..5 |C8..5 | | | | | +------=------O----------+ | H15..12 | | | +------=--------O---------+ | | V V +---------------+ | CPA | +---------------+ | V R15..4 В CPA складываются: 1) H15..12, S11..8, S7..5 2) C12..9 , C8..5 Время работы T = Tnmm + Tcsa + Tcpa(n=12) T = 19L + 3L + 12 * 3L = 58L