14.3. ДРЕВОВИДНЫЕ УМНОЖИТЕЛИ

Древовидные методы


Для сложения используют два вида базовых сумматоров CPA и CSA:



         A B D
         | | |
	 V V V
	+------+
	| CSA  |	Carry-Save Adder   (A+B+D = C + S)
	+------+	Быстрый  T = ~ 3L	
	  |  |  	(он считает быстро сумму и перенос для 
	  V  V		 каждого разряда, но не переносит в следующий)
	  C  S
  



  


  


Для сложения CPA сумматор нужен только в конце.
Предположим что нам надо сложить 6 частных произведений:





  
  Метод Уолеса 
 




Метод Уолеса:

Умножитель Уолеса:
  



	 A B C      D E F
         | | |      | | |
	 V V V      V V V
	+------+  +------+
	| CSA  |  | CSA  |
	+------+  +------+
	  |  |	     | |
	  |  +-----+ | |
	  |	   | | |
	  |	   V V V
          |	  +------+	
	  |	  | CSA  |
	  |	  +------+
	  | 	     | |
	  +--------+ | |
		   | | |
		   V V V
	          +------+
		  | CSA  |
		  +------+
		    | |
		    V V
		  +------+
		  | CPA  |
		  +------+		
		     |
		     V

Время работы T = 9L + 3nL

Деревья Уолисса:
Дерево Уолесса для 3:
  

Дерево Уолесса для 7:
  

Дерево Уолесса для 15: