1 Projektowanie cyfrowych systemów w oparciu o układy (VLSI i) PLDErnest Jamro Kat. Elektroniki AGH, Kraków Układy mnożące, konwolwery

2 Mnożenie 1 X + 9 x 11= 99

3 Mnożenie równoległe

4 Mnożenie sekwencyjne

5 Wallace Tree Multiplier (with Carry Save Adders)W układach FPGA nie zaleca się stosowania CSA

6 Szybkie mnożenie w układach FPGA26·(2·a7 ·b + a6 ·b)

7 Układy mnożące w FPGA (a7 and bi) xor (a6 and bi+1) Przykład: G4 - a7G3 - bi G2 - a6 G1 - bi+1 F4 – a7 F3 – bi-1 F2 – a6 F1 – bi Fragment of Virtex Configurable Logic Block (CLB)

8 Mnożenie liczb ze znakiemReprezentacja: Znak, Moduł: Mnożenie modułów jak liczb bez znaku Znak= Znak1 XOR Znak2 Reprezentacja w kodzie uzupełnień do dwóch: Zwykła operacja mnożenia liczb dodatnich C. R. Baugh and B. A.Wooley, “A two’s complement parallel array multiplication algorithm,” IEEE Trans. Comput., vol. C-22, pp. 1045–1047, Dec

9 Mnożenie w kodzie uzupełnień do 2

10 Układ mnożący o zredukowanej szerokości

11 Kompensacja błędu redukcji

12 Mnożenie przez stały współczynnik Zastosowanie pamięci Look Up Table (LUT)Przykład mnożenia przez stałą wartość C= 5 Adres Dana 0 0 1 5 2 10

13 Układy z wykorzystaniem pamięci LUT: mnożenie przez stały współczynnik C Y = CA = CA(0:3) + 24 CA(4:7)

14 Zastosowanie różnych pamięci ROM przykład: szerokość wejściowa= 6

15 Bardziej skomplikowany przykład Virtex: 161, 321, 4k1, 2k2, 1k4, 5128, 25616 szerokość wejścia i współczynnika mnożącego= 14

16 Migracja z CLB do BRAM CLB BRAM

17 Koszt [CLB] dla różnych szerokości K wejścia i współczynnika mnożeniaekwiwalentny koszt 1 BSR tylko CLB, skala 1:10 liczna użytych BSR

18 MM (Multiplierless Multiplication) Mnożenie przez stały współczynnikBinary Representation, example B= 14= 11102 M= AB= (A<<1)+(A<<2)+(A<<3) Sub-structure Sharing (SS) example B= 27= tmp= A + (A<<1) M= AB= tmp + (tmp<<3) Canonic Sign Digit (CSD) set {0, 1, -1} (0 – no operation, 1 – addition, -1 – subtraction) example: B= 7 = B= 100-1CSD M=B·A= (A<<2) + (A<<1) + A M= (A<<3)-A

19 BINARNIE  CSD insert symbol ‘-1’ only if the total number of operation is reducedStandard Modified

20 Stosowane techniki optymalizacji układów MM

21 The MM cost for different coefficients

22 Filtr FIR

23 Filtr FIR (sposób pośredni)

24 FIR 2D

25 Przykłady filtrów FIR 2D1 2 4 -1 -2 1 2 1 -8 Dolno-przepustowy Sobel Laplace’a

26 Filtr FIR N=2 z układami mnożącymi LUTIn 8 4 Adder1 Adder0 Adder2 12 13 4 18 Multiplier 1 Multiplier 2 Adder1 Adder0 Adder2 12 13 9 4 14 18 Adders Block

27 FIR, Arytmetyka w innej kolejności (Parallel) Distributed Arithmeticdifferent bits of the input input coefficient

28 Arytmetyka Rozproszona (Distributed Arithmetic)The same input bit weight (smaller LUT widths)

29 Filtry FIR z liniową fazą (symetryczne: h(0)=h(N-1), h(1)=h(N-2), ...)

30 Przykład dzielenia wspólnej podstrukturyH(z)= z-1 + 5z-2 = z z-2 Przykład 1: A= 5 = zmienna pomocnicza H(z)= A + ( A)z-1 + Az-2 Przykład 2: A= 1 + z-1 H(z)= 5A + 8z-1 + 5z-2