14.4. УМНОЖЕНИЕ БЕЗ СЛОЖЕНИЯ (NMM)

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