capitolul 6 - implementarea blocurilor de calcul numeric - after review jan 4, 2008

Arhitecturi si Structuri Paralele de Calcul

Tiberiu-Dinu TEODORESCU

Copyright 2006-20008, Toate drepturile rezervate

1

Capitolul 6: Implementarea blocurilor de calcul numeric Blocuri elementare (elemente de sistem)

Blocurile elementare din cadrul unui sistem de prelucrare de semnal sunt: a) Amplificatorul (scalorul) Reprezentarile schematice ale scalorului sunt date in Fig. 1 , precum si functia

indeplinita (operatorul matematic asociat):

Fig. 1: Scalorul b) Sumatorul Mai jos se prezinta sumatorul cu N intrari. Alternativ, cu ajutorul sumatorului cu 2

intrari se poate construi sumatorul cu N intrari.

Fig. 2: Sumatorul

y[k]=ae[k] e[k] a

a

e[k] y[k]=ae[k]

e3[n]

e1[n]

y[n]

e1[n]

e2[n]

eN[n]

=

=

N

n

neny1

][][

e1[n]

e2[n]

y[n]

e1[n]

e2[n]

y[n]

eN[n]

b)

c)

a)

=

=

N

n

neny1

][][




2

Ambele blocuri prezentate pana in acest moment sunt liniare, fara memorie. c) Celula de memorare (intarziere)

Fig. 3: Celula de intarziere d) Multiplicatorul

Fig. 4: Multiplicatorul Deosebirea fundamentala intre scalor si multiplicator este aceea ca multiplicatorul inmulteste 2 esantioane, realizand o functie neliniara.

e) Blocul ce implemeteaza o functie neliniara

Fig. 5: Implementarea unei functii neliniare

Pana in acest moment s-au prezentat elementele de sistem, fara a se pune accent pe modul de implementare ale acestora. In cele ce urmeaza se va detalia implementarea fiecaruia. Vom prezenta in continuare structuri de element cu memorie, sumatoare, elemente neliniare si multiplicatoare.

y[n]=f(e[n])

e[n]

f()

p[k]

e[k] y[k]=p[k]e[k]

e[n]

z-1

y[n]=e[n-1]




3

Structuri de element cu memorie Se prezinta elemente cu memorie pe 1 si B biti.

Fig. 6: a) Celula de intarziere pe B biti la nivel de system; b) Celula de intarziere pe 1 bit; c) Registru pe B biti

y[n]=e[n-1]

e[n]

B

B

e[n]

z-1

y[n]=e[n-1]

D Q

CLK

a)

b)

y1[n]

e1[n]

MSB

D Q

CLK

y2[n]

e2[n]

D Q

CLK

yB[n]

eB[n]

LSB

D Q

CLK




4

Complexitatea structurii din Fig. 6c) este data de formula: CBBz BCC =1 (1)

Timpii la sacadare si respectiv de latenta sunt:

SL

CLKS

TTTT

=

=

(2)

Sa consideram in cele ce urmeaza structura unui element de intarziere cu N tacte, detaliind structura acestuia pentru functionarea pe 1 bit, respectiv pentru functionarea pe B biti:

Fig. 7: a) Celula de intarziere cu N tacte pe 1 bit; b) Celula de intarziere cu N tacte pe B biti

CLK

yB[n]= eB[n-N]

y2[n]= e2[n-N]

y[n]=e[n-N]

e[n]

D Q

CLK

a)

y1[n]= e1[n-N]

e1[n]

MSB

D Q

CLK

e2[n]

D Q

CLK

eB[n]

LSB

D Q

CLK

b)

D Q

CLK

D Q

CLK

D Q

CLK

D Q

CLK

D Q

CLK

D Q

CLK

D Q

CLK

D Q

CLK




5

Complexitatea structurii din Fig. 7b) este data de formula: CBBz NBCC =1 (3)

Timpii la sacadare si respectiv de latenta sunt:

SL

CLKS

NTTTT

=

=

(4)

Structuri de sumatoare Vom incepe prin prezentarea sumatorului pe 1 bit cu transport pe intrare (FA Full Adder) si respectiv fara transport pe intrare (HA Half Adder).

Full Adder (FA) Schema sumatorului pe 1 bit cu transport pe intrare este data in Fig. 8:

Fig. 8: Sumator pe 1 bit cu transport pe intrare (doua reprezentari ale aceleiasi realitati)

Tabelul de adevar ce descrie logica de functionarea a sumatorului cu transport pe intrare este dat mai jos:

Tin x y S Tout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

x y Tin

Tout S

FA x

y

Tin

Tout

S

FA




6

Pe baza tabelului de adevar, folosind o tehnica de minimizare (Veitch-Karnaugh sau Queen-McKlusky) se obtine structura combinationala de mai jos:

Fig. 9: Sumator pe 1 bit cu transport pe intrare (rezultat minimizare - sinteza) Structura combinationala este corespunzatoare urmatoarelor functii logice sintetizate:

( )

+==

inout

in

TyxxyTTyxS

(5)

Half Adder (HA) Structura HA se obtine usor din structura FA, considerand Tin = 0:

Fig. 10: Sumator pe 1 bit fara transport pe intrare (rezultat minimizare - sinteza)

Functia logica este data mai jos:

=

=xyT

yxS

out

(6)

In cele ce urmeaza vom deduce cateva topologii de sumatoare pe B biti, punand in evidenta avantajele si dezavantajele lor.

Sumator pe B biti ripple carry (cu propagarea transportului) Daca transportul de la iesirea unui sumator a doi biti se propaga catre bitul urmator, se obtine urmatoarea topologie:




7

Fig. 11: Sumator pe B biti

Aceasta arhitectura nu este una paralela, deoarece, pentru a se realize sumarea la bitul urmator, sumatorul pe 1 bit trebuie sa astepte rezultatul de la precedenta sumare, pentru a lua in calcul transportul. Evaluarea complexitatii duce la formula:

)22(1_ ORANDXORbit CCCBBCC ++== (7)

Timpii caracteristici sunt: bitL BT 1_= (8)

Se observa ca timpul de latenta depinde de numarul de biti utilizati, ceea ce reprezinta un inconvenient major intr-un sistem sincron.

Tout

x1

y1

Tin

S1

FA

S2

FA

SB

FA xB

yB

x2

y2




8

Sumator pe B biti carry-look ahead (cu calcul anticipat al transportului) Sa consideram pentru ilustrarea functionarii acestui sumator cazul in care B=4. In cazul acestui sumator se va tine seama de structura sintetizata a sumatorului pe 1 bit. Astfel, se considera o unitate denumita sumator partial (Partial Full Adder PFA), caracterizat de urmatoarele ecuatii:

)( iiiiii yxPyxG == iiii TPGT +=+1

iiiiii TPTyxS ==

(9)

Vom denumi semnalele Pi si Gi propagator si generator, Ti este carry-in, iar Ti+1 este carry-out pentru etajul i. Si este rezultatul sumei pentru bitul etajului respectiv. La baza functionarii acestei arhitecturi pe 4 biti stau ecuatiile:

0001 CPGT +=

0010111112 TPPGPGTPGT ++=+=

00120121223 TPPPGPPGPGT +++=

0012301231232334 TPPPPGPPPGPPGPGT ++++=

(10)

Se vede ca termenii P si G se calculeaza dupa 2 unitati de intarziere, iar fiecare T se calculeaza dupa inca 2 unitati (vezi ultimele ecuatii). Schema finala a sumatorului cu calculul anticipat al transportului este:

Fig. 12: Sumator cu transport anticipat pe B=4 biti




9

Logica de calcul anticipat al transportului, ce se bazeaza pe ecuatiile

(10), determina ca timpul de latenta sa se scrie ca:

ORANDXORLT ++= 2 (11)

Timpii de propagare prin portile AND si OR vor diferi insa practic intre ei, deoarece se foloseste un numar de intrari diferite pentru calculul transportului pentru fiecare bit in parte. Totusi, in mod ideal, timpul de latenta in cazul acestei topologii nu depinde de numarul de biti al sumatorului. Exercitiu: Realizati schema sumatorului cu transport anticipat ce functioneaza pe B=5 biti.

Structuri de implementare a elementelor neliniare O functie neliniara se implementeaza discretizand abscisa si ordonata functiei respective, cu pasul de cuantizare. Schema de implementare a acesteia este data mai jos:

Fig. 13: Implementarea unei functii neliniare pe B biti

Structuri de implementare a multiplicatoarelor Ca si in cazul celorlalte elemente de sistem se porneste de la multiplicatorul pe 1 bit:

Fig. 14: Multiplicatorul pe 1 bit

y= b1 b2

b1 b2 b2

b1 y= b1 b2

X - Abus Y- Dbus

ROM

Y=f(X)




10

Pentru a deduce structuri de multiplicatoare binare, sa recapitulam modul in care se realizeaza acestea (principiul de inmultire): Fie doua numere binare, a si b, ce se doreste a fi inmultite. Sa presupunem ca aceste numere sunt pozitive. Fie a si b de forma:

LH

LH

bbbaaa

=

=

(12)

Pentru a deduce o regula, sa luam un caz particulat in care:

0123

0123

bbbbbaaaaa

=

=

(13)

Identificam termenii:

0123

0123

;

;

bbbbbbaaaaaa

LH

LH

==

==

(14)

Sa detaliem termenii urmatori:

a) aLbL a1 a0 b1 b0 a1 b0 a0 b0 a1 b1 a0 b1 a1 b1 a0 b1+ a1 b0 a0 b0

b) aLbH a1 a0 b3 b2 a1 b2 a0 b2 a1 b3 a0 b3 a1 b3 a1 b2+ a0 b3 a0 b2

c) aHbL a3 a2 b1 b0 a3 b0 a2 b0 a3 b1 a2 b1 a3 b1 a3 b0+ a2 b1 a2 b0

d) aHbH a3 a2 b3 b2 a3 b2 a2 b2 a3 b3 a2 b3 a3 b3 a3 b2+ a2 b3 a2 b2




11

Inmultirea celor doua numere pe 4 biti este figurata mai jos: a3 a2 a1 a0 b3 b2 b1 b0 a3 b0 a2 b0 a1 b0 a0 b0 a3 b1 a2 b1 a1 b1 a0 b1 a3 b2 a2 b2 a1 b2 a0 b2 a3 b3 a2 b3 a1 b3 a0 b3 a3 b3 a3 b2+ a2 b3 a3 b1+ a2 b2

+ a1 b3 a3 b0+ a2 b1+ a1 b2+ a0 b3

a2 b0+ a1 b1 + a0 b2

a0 b1+ a1 b0 a0 b0

Cu notatiile de la inmultirea perechilor de numere pe 2 biti, inmultirea lor pe 4 biti se poate scrie:

aH aL bH bL (aLbL)H (aLbL)L (aHbL)H (aHbL)L (aLbH)H (aLbH)L (aHbH)H (aHbH)L

Termenii de tipul (aXbY)L si (aXbY)H sunt pe cate 2 biti, partea high expandandu-se la 2 biti prin adaugarea unui bit 0 la MSB. Comparand, se poate observa ca (aLbL)L= a1b0 a0b0 , s.a.m.d.

Expandare Se dispune de obiectul multiplicator pe B/2 biti. Cu acest obiect se poate obtine prin tehnica descrisa mai sus un multiplicator pe B biti. Acest lucru se poate petrece ierarhic, pornind de la multiplicarea pe B biti se foloseste cea pe B/2 biti, s.a.m.d. Schema ce descrie procedeul de expandare se prezinta in Fig. 15: Expandare. Termenii partial se obtin folosind multiplicatorul pe B/2 biti.




12

Fig. 15: Expandare

Rezultatul inmultirii a doua numere pe B biti este prin urmare reprezentabil pe 2B biti. In cazul inmultirii nu exista notiunea de depasire de format in felul acesta. O alternativa de implementare a inmultirii pe B/2 biti este prezentata mai jos (solutie valabila daca B este suficient de mic):

Fig. 16: Implementare multiplicator pe B/2 biti

B/2 biti B/2 biti B/2 biti B/2 biti

0

0

aLbL aHbL aLbH aHbH H L

H L

H L

H L

FA FA

FA FA FA

B

B/2

B/2

ROM (LUT)

P

Q

M=PQ




13

Si in acest caz se poate folosi expandarea, folosind ca primitiva de multiplicare aceasta solutie.

Cateva structuri de multiplicatoare paralele Se da un prim exemplu, ce implementeaza modul de gandire natural utilizat atunci se inmultesc doua numere fara semn:

Fig. 17: Multiplicator natural

Multiplicatorul natural prezinta 13 timpi de propagare prin FA la operanzi pe B=5 biti. Al doilea exemplu minimizeaza timpul de propagare pe calea critica. Poarta numele de multiplicator Braun:




14

Fig. 18: Multiplicator Braun

Castigul multiplicatorului Braun este acela ca timpul necesar pentru a inmulti B=5 biti este 9 timpi de propagare prin FA.

Multiplicarea numerelor cu semn Pentru fixarea cadrului de rationament, sa presupunem doi operanzi:

01234

01234

bbbbbBaaaaaA

=

=

(15)

Sa calculam in cele ce urmeaza valorile zecimale ale celor doi operanzi, valorile fiind exprimate indiferent de faptul ca numarul este pozitiv sau negative (exprimat in complement fata de 2), ca mai jos:

( )

( )

=

=

+=

+=

3

04

410

3

04

410

22

22

i

ii

i

ii

bbB

aaA

(16)

Sa dam cate un exemplu in care sa verificam formula de mai sus:




15

Exemplu: Fie A=011 si B=101. Valoarea zecimala a lui A este +3, iar a lui B este -3. conform codului complementar fata de 2. Aplicand formulele de mai sus se obtine:

( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) 302121222

312120222

1021

02

210

1021

02

210

=++=+=

=++=+=

=

=

i

ii

i

ii

bbB

aaA

(17)

Produsul celor doua numere este: ( ) ( ) ( )( )

= =

+

==

==

+=

+

+=

=

3

0

3

0

3

0

44

3

0

44

844

3

04

43

04

410

101010

222222

2222

*

i j

jiji

i

ii

j

jj

j

jj

i

ii

baabbaba

bbaaC

BAC

(18)

Se tine cont de urmatoarea proprietate (calculul complementului fata de 2):

=

=

=

=

++=

++=

3

0

43

0

3

0

43

0

1222

1222

j

jj

j

jj

i

ii

i

ii

bb

aa

(19)

In acest context, relatia (18) devine:

( )

= =

+

=

=

+

+++

+++=

3

0

3

0

3

0

444

3

0

444

84410

21222

12222

i j

jiji

j

ii

j

jj

baab

babaC

(20)

Se tine cont de urmatoarele relatii la urmatoarele prelucrari ale ecuatiei (20):

=

=

=+

=+

1

1

1

1

44

44

44

44

bb

aa

bb

aa

(21)




16

( ) ( )

( )

( ) 4443

04

43

04

4

844

3

0

3

0

844

444

3

0

44

3

0

44

844

3

0

3

0

84410

22222

21122

22222

222

babaab

bababa

baabba

bababaC

i

ii

j

jj

i j

jiji

i

ii

j

jj

i j

jiji

+++

+

+++

=++++

++=

=

=

= =

+

=

=

= =

+

(22)

Dupa cateva manipulari algebrice, se obtine:

( )

( )

=

+

= =

+

++

++

++

++=

3

0

444

444

93

0

3

0

8444410

22

222

i

iii

i j

jiji

bababa

bababaC

(23)

Aranjand termenii dupa puterea lui 2, se obtine:

Fig. 19: Principiul multiplicatorului Baugh-Wooley

Termenul -29 (scazut de pe pozitia a 9-a), are un efect similar adunarii cu 1 pe pozitia a noua si neglijarii transaportului.




17

Fig. 20: Multiplicatorul Baugh-Wooley

Tema: Deduceti structura multiplicatorului Baugh-Wooley functionand cu operanzi de 4 biti.

Algoritm de multiplicare rapida Booth Algoritmul Booth este unul care ofera o solutie de multiplicare rapida atunci cand in inmultitor se afla mai multe pozitii consecutive de 1 sau 0. Un alt motiv pentru care acest algoritm este folosit este ca permite inmultirea a doua numere cu semn.

Exemplul 1: Inmultirea 22x17:

0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0

Se obtine 0101110110 = (374)10.

Daca exista o secventa de zerouri, toate acestea vor fi ignorate si scade astfel numarul de pasi necesari.




18

Exemplul 2: Inmultirea 22x14: 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0

Din exemplu 2 se deprinde concluzia ca tehnica folosita in cadrul exemplului 1 nu ajuta in acest caz (in care exista mai multi de 1 consecutivi). Cu observatia ca 001110=010000-000010

d d 1 0 0 . 0 0 0 d d - d d 0 1 1 . 1 1 0 d d 0 0 0 0 0 . 0 1 0 0 0

Observatia de principiu care se face este ca relatia:

+=== rightleftrightleftrightleft ABBABABAAABBA )(

(24)

Exemplul 3 (o alta perspectiva asupra exemplului 2 B=6 biti): 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 + -( 0 1 0 1 1 0 )

Aceasta este echivalent cu: 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 + 1 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0

Am extins numarul cu 1 MSB completand cu 1 pana la 12 biti (numarul de biti pe care incape rezultatul).




19

Regula lui Booth Fie numerele binare:

0121

0121

...

...

aaaaAbbbbB

BB

BB

=

=

(25)

Se doreste calculul produsului C=BA. Sa consideram urmatorul tabel: ai ai-1 ai-1-ai Operatie asociata 0 (i=0) 0 0 Nu face nimic 1 0 -1 Scade B din suma produselor partiale 1 1 0 (shift) Nu face nimic 0 1 1 Se aduna B la suma produselor partiale Sa reluam exemplu 3: A=001110. Aplicarea tabelului la acest exemplu se face considerand un 0 suplimentar (pozitia -1). Astfel, tabelul de mai sus devine pentru acest caz particular:

ai ai-1 ai-1-ai Operatie asociata 0 (i=0) 0 0 Nu face nimic (shift) 1 (i=1) 0 -1 Scade B din suma produselor partiale

(shift) 1 (i=2) 1 0 Nu face nimic (shift) 1 (i=3) 1 0 Nu face nimic (shift) 0 (i=4) 1 1 Se aduna B la suma produselor partiale

(shift) 0 (i=5) 0 0 Nu face nimic (shift) Produsul se calculeaza folosind urmatoarea relatie:

( ) ( )( ) ( )( ) ( )( )( )( ) ( )( ) 1101221023

21021

11010

0100110

22...222

++

+++=B

BBB

BB BaaBaa

BaaBaaBaaC

(26)

Sa demonstram ca ecuatia (26) reprezinta produsul celor doua numere. Se dezvolta relatia ca mai jos:

( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) 1101110221022103

2102

2101

1101

1100

0100

010110

2222...222222

++

+++=B

BB

BB

BB

B BaBaBaBa

BaBaBaBaBaBaC

(27)

Se tine cont de faptul ca a-1=0 si se grupeaza termenii dupa indicele lui a:

( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )1010

2

0

11

2

01010

1101

1101

2102

3103

2102

1101

010010

2222

222...222

ABaaBaBBa

BaBaBaBaBaBaCB

i

ii

BB

B

i

ii

BB

BB

BB

BB

=

+=+=

=+++++=

=

=

(28)

Relatia este valabila indiferent de semnul lui A si al lui B. Sa schitam algoritmul Booth pentru exemplul inmultirii numerelor B=22 si A=-34, pe un hardware la care cuvantul este reprezentat pe B=7 biti. Cuvintele binare se scriu ca mai jos:

B=0010110; -B=1101010; A=0100010; -A=1011110




20

Sunt la dispozitie 3 registrii pe B=7 biti. Se incarca B intr-un registru denumit M. Cuvantul [AQ], de 14 biti va memora rezultatele sumelor partiale. qi qi-1 Actiune M=0010110

A=0000000 Q=1011110 q

-1=0 qi-1=0

0 0 Shift right 0000000 0101111 0 1 0 Scad pe B

Shift right

1101010 1101010 1110101

0101111

0010111

1 1 Shift right 1111010 1001011 1 1 Shift right 1111101 0100101 1 1 Shift right 1111110 1010010 0 1 Aduna B

Shift right

1111110 0010110 10010100 (negl. 1) 0001010

1010010

0101001

1 0 Scad pe B

Shift right

0001010 1101010 1110100 1111010

0101001

0010100

Produsul (in setul de registrii AQ) este: 1111010_0010100. Va rezulta un numar negative, egal cu -748 in zecimal. Verificati!

Observatie: Datorita faptului ca operanzii sunt reprezentati in complement fata de 2, la shift-uri s-au introdus in cazul produselor partiale negative biti de 1, iar in cazul produselor partiale positive biti de 0.

Multiplicator-acumulator Structura de multiplicator-acumulator este utila deoarece, asa cum s-a aratat la capitolul ce trateaza structuri de DSP-uri, acest bloc mareste mult viteza de prelucrare a esantionelor prezentate la intrarea unui filtru numeric. Din punctul de vedere al reprezentarii operanzilor, se pot distinge doua arhitecturi:




21

Fig. 21: a) Multiplicator acumulator pe 2B biti. b) Multiplicator acumulator pe B biti.

Intre cele doua scheme, din punctual de vedere al controlabilitatii erorilor, prima este cea corecta. La nivel de bit multiplicatorul acumulator are urmatoarea arhitectura:

Fig. 22: Multiplicator-acumulator pe 1 bit

Multiplicator bit serial Structura corespunzatoare este una dintre cele mai complicate in cadrul arhitecturilor sistolice. Frecventa de lucru trebuie sa fie mare pentru a asigura o latenta acceptabila, insa nu creste cu numarul de biti/cuvant. Un alt avantaj al acestei structuri este acela ca ocupa mai putin spatiu pe siliciu in comparatie cu arhitecturile paralele de multiplicatoare. Sa prespunem ca avem de inmutit doi operanzi:

overflow

2B biti

c

22B biti

B biti

B biti

a

b X

2B biti B biti

overflow

B biti

c

2B biti

B biti

B biti

a

b X

B biti

a) b)

Out

to ti

c b a

FA




22

=

=

=

=

1

0

1

0

2

2

B

jj

j

B

k

kk

bB

aA

(29)

Se impun doua observatii: rezultatul acestei operatii va fi reprezentat pe 2B biti iar ordinea in care va iesi rezultatul din structura va fi incepand cu LSB, deoarece transportul in calcul rezultatul se propaga de la dreapta la stanga intr-o operatie de inmultire. Rezultatul inmultirii celor doua numere este dat mai jos:

( )

=

=

+

=

=

=

=

==

1

0

1

0

1

0

1

0

2

22

B

k

B

jjk

jk

B

jj

jB

k

kk

ba

baABP

(30)

Pe de alta parte, iesirea din structura de inmultire ar trebui sa aiba forma:

=

=

12

02

B

n

nnpP

(31)

Prin realizarea schimbarii de variabila jkn +=

(32) Ecuatia ce da rezultatul devine:

=

+=

=

=

+

=

+++=

===

22

111

111

1

000

1

0

1

2...22

2

B

Bn

nBnB

B

n

nn

B

n

nn

B

k

Bk

kn

nknk

bababa

baABP

(33)

Daca sumele componente se extind si pt n de la B2B-2, se obtine:

=

+

=

=

+++=22

011

22

011

22

000 2...22

B

n

nBnB

B

n

nn

B

n

nn bababaP

(34)

Acest lucru a fost posibil intrucat B este reprezentat numai pe B biti, toate valorile bn pentru n>B-1 si n




23

Comparand ecuatiile ce il dau pe P se pot face urmatoarele observatii: a) termenul in plus (cu indicele 2B-1) este transportul propagat, ce a ajuns la ultimul

bit; b) ecuatia ce da rezultatul (bitii produsului) seamana cu convolutia a doua secvente

numerice :

=

=

1

0

B

kknkn hey

(37)

Tinand cont de acest lucru, structura cu ajutorul careia se implementeaza multiplicatorul va fi una a unui filtru FIR in care sumarile se fac cu ajutorul sumatorului pe un bit la care se tine cont si de transport, iar multiplicarile se fac cu ajutorul multiplicatorului pe 1 bit. Se realizeaza schema nesistolizata inca ce realizeaza calculul produsului a doua numere binare:

Fig. 23: Multiplicator bit serial

Sa analizam aceasta schema. Timpii importanti sunt: - timpul de latenta

SL BTT 2= (38)

- timpul de sacadare este:

pB-1p2p1p0

cB-1c2c1c0

aB-1a2a1a0 D Q

CLK

FA

Q D

CLK

D Q

CLK

FA

Q D

CLK

D Q

CLK

FA

Q D

CLK

B (registru)




24

ANDFAST += (39)

Perioada de clock cu care se aplica esantioanele la intrare trebuie sa fie mai mare decat timpul de calcul. Din punctul de vedere al complexitatii se disting:

- complexitatea elementului de procesare este data de relatia: FACBBANDPE CCCC ++= 2 (40)

- complexitatea circuitului este data de numarul de biti ai operanzilor: PEBCC = (41)

Se observa ca in orice caz, in aceasta arhitectura operandul B se incarca paralel. Din acest motiv multiplicatorul se mai numeste si serial-paralel.

Multiplicator serial paralel (variante sistolizate) Celula elementara ce intra in componenta schemei in cazul sistolizarii este:

Fig. 24: Structura celula sistolica pentru multiplicatorul bit serial

Din cascadarea a B astfel de celule elementare se obtine multiplicatorul sistolic pe B biti. Aceasta schema are timpul de latenta

D Q

CLK

FA

Q D

CLK

D Q

CLK

D Q

CLK




25

SL BTT 2= (42) Un avantaj este acela ca timpul de sacadare:

FAANDST += (43) este independent de numarul de biti pe care sunt reprezentati operanzii. Complexitatea elementului de procesare este data de relatia:

CBBANDFAPE CCCC 4++= (44) Prin urmare complexitatea schemei sistolizate este:

PEBCC = (45) O alta varianta de multiplicator sistolic se obtine in cazul in care, in cadrul celulei sistolice se adauga cei doi bistabili in fata celulei de baza, si nu la iesirea ei. Ca si in cazul filtrului FIR, si in cazul multiplicatorului bit serial se poate imagina o schema semi-sistolica. Celula elementara se obtine inversand sensul pe calea de jos si adaugand un bistabil necauzal pe calea de sus si unul cauzal pe calea de jos. Astfel, celula sistolica elementara devine:

Fig. 25: Celula sistolica elementara multiplicator semisistolic

In cazul acestei scheme, timpii relevanti sunt: SL BTT 2= (46)

FAANDST += (47) Complexitatea elementului de procesare este data de relatia:

FA

D Q

CLK

Q D

CLK




26

CBBANDFAPE CCCC 2++= (48) Prin urmare complexitatea schemei sistolizate este:

PEBCC = (49) Pentru a intelege mai bine functionarea, se dau in continuare rezultatele unei simulari in care operanzii sunt numere binare, considerate fara semn, pe 4 biti fiecare:

Fig. 26: Schema de simulare a multiplicatorului sistolic pe 4 biti

Sistemul incapsulat este detaliat in continuare:

Fig. 27: Schema de simulare a multiplicatorului sistoic pe 4 biti (detaliu)




27

Celula elementara este in cazul figurii de mai sus multiplicator-acumulatorul pe 1 bit. S-a folosit (pentru studiul gradelor de libertate disponibile sistolizarea prin adaugarea in fata procesorului elementar a doua bistabile, pe fiecare cale. Schema multiplicator-acumulatorului rezultat este data mai jos:

Fig. 28: Multiplicator-acumulator pe 1 bit (varianta de sistolizare cu celule de intarziere in fata procesorului elem)

Semnalele relevante in cursul functionarii acestei scheme sunt date mai jos. Operanzii introdusi sunt urmatorii: h = 1011 (operandul B in partea teoretica) este incarcat paralel, iar a are valoarea 1111 si este incarcat serial, pornind de la LSB spre MSB. Rezultatul (P) este Sout.




28

Fig. 29: Exemplu de multiplicare a doua numere pe 4 biti, folosind schema sistolica

Un alt exemplu (pentru unul din numere negativ in complement fata de 2) este dat mai jos. Numerele sunt a=1001 (-7) adaugandu-se in fatza 4 de 1 (11111001) si b=0101 (5):




29

Fig. 30: Exemplu de multiplicare a doua numere pe 4 biti (unul pozitiv si unul negativ), folosind schema sistolica

Se iau numai primii biti din rezultat (incepand cu LSB).




30

Expandarea multiplicitatoarelor sistolice Pentru a expanda multiplicatoarele sistolice, Sin-ul celui de-al doilea multiplicator se leaga la Sout-ul primului iar SerialIn-ul celui de-al doilea se leaga la SerialOut-ul primului, ca in figura de mai jos:

Fig. 31: Expandarea multiplicatoarelor sistolice de la 4 la 8 biti

S-au folosit 2 multiplicatoare sistolice pe cate 4 biti, cascadate. Pentru exemplificare, se considera numerele a=00000011 si b=10111011 (numerele se considera a fi ambele pozitive, chiar daca b are primul bit 1, semnul fiind o chestiune de interpretare a codului!). Rezultatele simularii sunt date mai jos. Se observa ca iesirea (etichetata result) este c=0000001000110001. Sa se verifice ca rezultatul este corect.

Exercitiu Folosindu-se structura de mai sus sa se inmulteasca doua numere binare, din care unul (a introdus serial) sa fie negativ, scris in complement fata de 2. Sa se foloseasca exemplul dat pentru inmultirea a doua numere (unul pozitiv si unul negativ) pe 4 biti, prezentat mai sus.




31

Fig. 32: Exemplu de inmultire a doua numere pe 8 biti

Filtru FIR sistolic In cele ce urmeaza se va prezenta structura unui filtru FIR sistolic, ce lucreaza pe 4 biti. Pentru simplitate, se va considera un filtru de ordinul 1, acest exemplu putand fii extins cu usurinta la o valoare mai mare a bitilor pe cuvant si la un ordin mai mare al filtrului. Sa consideram urmatoarea structura de filtru FIR sistolic:




32

Fig. 33: Filtru FIR sistolic de ordinul 1

Structura de MAC pe 4 biti a fost deja exemplificata. Coeficientii b0 si b1 se incarca paralel in fiecare din cele 2 MAC-uri, iar intrarile in cele doua MAC-uri se incarca serial. Se refoloseste astfel structura de MAC si se regaseste intarzierea de 8 tacte pe calea superioara (fiecare celula de intarziere z-1 figurata face de fapt, in raport cu 1/Ts -Ts fiind perioada clock-ului - o intarziere de 4 tacte). Sumatoarele sunt sumatoare bitseriale, cu intrare de transport si iesire de transport, ce intra ca intrare de tranport la frontul pozitiv urmator al clock-ului. Realizarea practica se prezinta ca mai jos:

Fig. 34: Filtru FIR sistolic de ordinul 1 (realizare practica)

MAC 4 biti MAC 4 biti

Y(z)

z-4E(z)

0

E(z) z

-1

b0

z-1

z-1

z-1

b1

z-1

z-1




33

Fig. 35: Filtru FIR sistolic de ordinul 1 (rezultate simulare)

S-au considerat mai intai situatia cand la intrarea filtrului se aplica un impuls. La iesirea filtrului se obtine raspunsul la impuls. In cazul de fata s-a considerat functia de transfer:

]1[][][)(

10

110

+=

+=

nbnbnhzbbzH

(50)

Cand la intrarea filtrului se aplica un singur impuls, iesirea se calculeaza folosind relatia : ( )

][][]1[][]1[][*][][*][][ 1010

nhnynbnbnbnbnnhneny

=

+=+==

(51)

Coeficientii b0 si b1 sunt pe cate 4 biti fiecare, ca si esantioanele prezentate la intrarea filtrului (in acest caz un singur puls pe 4 biti).




34

Se prezinta in continuare un tabel cu bitii ce ies la iesirea filtrului: Index bit iesire Esantion Bit esantion

0 b0=1001

(LSB primul)

1 1 0 2 0 3 1 4

b1=1011 (LSB primul)

1 5 1 6 0 7 1

Restul de biti pana la 15 sunt 0. Verificati faptul ca valorile zecimale ale esantioanelor sunt corecte. Folositi modelul Matlab al sistemului postat pe site (Fir_4_biti_sistolic.mdl). Imaginati functionarea acestui filtru si pentru coeficienti si esantioane negative (in complement fata de 2).

Exercitiu Sa se calculeze si sa se simuleze acelasi filtru, in cazul in care la intrare se aplica

]1[][][ 10 += nanane (52) In care (exemplul Fir_4_biti_sistolic_2_pulsuri.mdl)

0011001000010001

1

0

1

0

=

=

=

=

bba

a

(53)

Calculati apoi si simulati cazul in care

0011001001010001

1

0

1

0

=

=

=

=

bba

a

(54)

Acest model este prezentat pe site sub denumirea Fir_4_biti_sistolic_2_pulsuri_val_dif.mdl .

Rezolvare Pentru primul caz rezultatele sumularii sunt prezentate mai jos:




35

Fig. 36: Filtru FIR sistolic de ordinul 1 (raspuns la aplicarea lui e[n] la intrare cu a0=1 si a1=1)

Rezultatul se verifica tinand cont de faptul ca ]1[3][2][],1[][][ +=+= nnnhnnne (55)

Se aplica transformata Z asupra celor doua expresii si se obtine:

( )( ) 21111

1

352321)()()(32)(

1)(

++=++==

+=

+=

zzzzzHzEzY

zzH

zzE

(56)

Aplicand transformata Z inversa: ]2[3]1[5][2][ ++= nnnny (57)

Prin urmare, la iesire ar trebui sa avem bitstream-ul : 1100_1010_0100=y (58)

ceea ce se verifica examinand semnalul result din figura de mai sus.

Se prezinta in continuare al doilea caz (a0=1 si a1=5): ]1[3][2][],1[5][][ +=+= nnnhnnne (59)

Se reia calculul raspunsului in domeniu transformat si se obtine :




36

( )( ) 21111

1

151323251)()()(32)(

51)(

++=++==

+=

+=

zzzzzHzEzY

zzH

zzE

(60)

De unde, raspunsul y[n] rezulta: ]2[15]1[13][2][ ++= nnnny (61)

Fig. 37: Filtru FIR sistolic de ordinul 1 (raspuns la aplicarea lui e[n] la intrare cu a0=1 si a1=5)

Conform lui y[n] bistreamul ar trebui sa fie: 1111_1011_0100=y (62)

ceea ce se verifica in simularea de mai sus (result).

capitolul 6 - implementarea blocurilor de calcul numeric - after review jan 4, 2008

Documents