ARITMETIČNA-LOGIČNA ENOTA Z ZAPOREDNO LOGIKO ZA IZRAČUN UTEŽNE VSOTE S PROGRAMIRNIMI VEZJI Davorin Osebik^, Rudolf Babič^, Kosta Kovačič^ ^Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Maribor, Slovenija ^IDS d.o.o., Ljubljana, Slovenija Kjučne besede; digitalna obdelava signalov, nerekurzivna digitalna sita, aritmetično-logična enota, koncentrirana aritmetika, zaporedna aritmetika, implementacija, programirna vezja Izvleček: V članku je opisana izvedba aritmetično-iogične enote z zaporedno logiko za sprotno določitev utežne vsote implementirane v programirna vezja (FPGA). Aritmetično logično enoto lahko uporabimo pri načrtovanju in izvedbi digitalniti FIR sit. Celotna struktura sita ima modularno zasnovo, ki podpira enostavno razširitev digitalnega FIR sita glede na poljubno število koeficientov. Zgradba modulov temelji na uporabi zaporedne logike za izvajanje aritmetičnih operacij. Pri načrtovanju smo se omejili na 16-bitni zapis vhodno-izhodnega signala digitalnega FIR sita. Načrtovanje digitalnega FIR sita z opisano aritmetično logično enoto za izračun utežne vsote koeficientov zagotavlja majhno aparaturno kompleksnost in linearno naraščanje aparaturne kompleksnosti sita glede na število koeficientov. FIR sito je zasnovano tako, da se lahko uporabi kot samostojno vezje. Opisana aritmetično logična enota v sistemu digitalnega FIR sita omogoča sproten vnos koeficientov v času med dvema vzorcema vhodnega signala, zato jo lahko uporabimo tudi kot FIR enoto v sistemu adaptivnega sita. Za načrtovanje aritmetično-iogične enote in njene uporabe pri izvedbi digitalnih FIR sit smo uporabili programski paket Xilinx ISE 6.1 WebPack, ki podpira vnos, sintezo vezja in implementacijo v programirna vezja. Izbrali smo programirno vezje XC3S-400, družine Spartan, firme Xilinx. Vanj smo implementirali digitalna FIR sita z 8, 16, 32 in 64 koeficienti. Simulacijo digitalnega FIR sita smo opravili s programskim paketom tvlodelSim. Pri tem smo na osnovi rezultatov simulacije ugotovili, da lahko pri 16-bitnem zapisu vhodnega signala, dosežemo frekvenco vzorčenja 4.4M Hz. Arithmetic Logic Unit for Weighted Sum Calculation with Programmable Logic Cell Array Key words: digital signal processing, FIR filter, arithmetic logic unit, concentrated arithmetic, serial arithmetic, VHDL, implementation, FPGA. Abstract: In this article the design of the arithmetic logic unit with serial arithmetic procedure for weighted sum calculation and programmable logic cell array implementation is presented. This arithmetic logic unit is especially intended for adaptive FIR digital filter realization because all the coefficients of the digital filter can be changed simultaneously between two input samples. FIR digital filter with proposed arithmetic logic unit with serial arithmetic is shown in Fig. 3. It can be designed in the modular structure (Fig. 5) that allows the whole system tobe expanded to any numberof coefficients with minimal effort. The previous realizations of digital filters in programmable circuits were focused on reduction of the complexity of the hardware realization /5/. The idea that stands behind the serial arithmetic structure is the reduction of hardware implementation complexity. It is shown that the hardware complexity increases linearly with the number of coefficients used (Table 1 and Fig. 8). The FIR digital filter in the modular structure consists of N cells. One cell of the modular structure is elementary arithmetic block (Fig. 4) and consists of serial multiplier (Fig. 6), serial adder (Fig. 7) and FIFO register. The filter has been designed in the Xilinx ISE 6.1 environment. The basic units, serial multiplier, serial adder and FIFO register of digital filter structure is designed with VHDL. The Xilinx schematic editor was used for connections between basic units. The test application is made with FIR digital filter of 16 coefficients and a 16-bit quantization of input and output signal. The Xilinx FPGA circuit XC3S-400 is used for implementation of FIR digital filter structures with 8, 16, 32 and 64 taps. The 64 taps FiR digital filter occupy only 72 % of input output blocks (lOB) and 78 % of slices of the whole XG3S-400 circuit used for this application. At 71 fvlHz clock frequency a sample frequency of input-output signal of 4.4 MHz has been obtained. The processing of one output signal sample needs 16 clock pulses. 1. Uvod Programirna vezja so zanimiva za implementacijo digitalnih FIR sit, kjer izračun izhodnega otipka poteka brez. uporabe zunanjega pomnilnika, za zapis delnih vsot koeficientov /1/. Struktura digitalnega FIR sita, ki uporablja arit-metično-logično enoto z zaporedno logiko za izračun utežne vsote, omogoča vpis vektorja koeficientov v času med dvema otipkoma vhodnega signala. FIR sita s takšno arit-metično-logično enoto so zanimiva v sistemih adaptivnih digitalnih FIR sit, kjer se koeficienti dinamično spreminjajo. Pri načrtovanju struktur digitalnih FIR sit, ki omogočajo vnos koeficientov v času med dvema otipkoma, ločimo strukture s porazdeljeno aritmetiko /1, 2/ in strukture s koncentrirano aritmetiko /3/. Obe strukturi je možno implementirati v eno programirno vezje, če uporabimo načr-tovalske postopke, ki zmanjšajo aparaturno kompleksnost izvedbe. Aparaturna kompleksnost je odvisna od načina implementacije diskretnega sistema. Pri povsem strojni implementaciji je aparaturna kompleksnost diskretnega sistema v glavnem odvisna od števila množilnikov za izračun izhodnega signala /4/. Zaradi tega je uporabljeno število množilnikov za implementacijo nekega sistema najpomembnejši parameter aparaturne kompleksnosti. Drugi kriterij pri implementaciji diskretnih sistemov je zahteva po pomnilniku. Velikost potrebnega pomnilnika je odvisna od potrebnega števila lokacij za shranjevanje notranjih spremenljivk diskretnega sistema. Kot tretji kriterij računske kompleksnosti omenimo zbiranje in razmeščanje podatkov znotraj strukture. Zadnji, četrti kriterij pa je vpliv končne dolžine besede na čas izračuna izhodne vrednosti. Vse štiri opisane kriterije smo upoštevali pri izbiri strukture digitalnega FIR sita in pri njegovi implementacijo v programirno vezje. Pokazali bomo, daje možno z upoštevanjem vseh naštetih kriterijev v eno programirno vezje družine Spartan-3 ob uporabi 16-bitne aritmetike in 16-bitne kvantizacije vhodnih signalov, implementirati digitalno FIR sito s 100 koeficienti. Osnovno strukturo nerekurzivnega digitalnega FIR sita opišemo s konvolucijsko enačbo, ki jo opišemo tudi kot utežno vsoto. /V-l (1) n=0 V konvolucijski enačbi je vektor koeficientov h digitalnega FIR sita določen s komponentami, h=[/7o, /ii,.../7n-i], in vektor koeficientov vhoda s komponentami, u=[uo, tvi,...UN-i]. Izvedbe digitalnih FIR sit so bile vedno povezane z iskanjem postopkov za zmanjšanje kompleksnosti algoritma, saj pomeni direktna izvedba enačbe (1) N množenj in A/seštevanj za izračun otipkov izhodnega signal. Očitno je, da kompleksnost izračuna izhodnega otipka narašča z uporabljeno kvantizacijo vektorja koeficientov digitalnega FIR sita h in vektorja koeficientov vhoda u. Aparaturna kompleksnost digitalnega FIR sita narašča z večanjem števila koeficientov. Za implementacijo enačbe (1), bi bilo ugodno poiskati takšno strukturo digitalnega FIR sita, kjer bo aparaturna kompleksnost s kvantizacijo vhodno-izhodne besede in s številom koeficientov čim počasneje naraščala.. Znani pristop zmanjšanja potrebnih aritmetičnih operacij je uporaba aritmetično-logične enote na osnovi porazdeljene aritmetike, kjer se delne vsote koeficientov izračunajo vnaprej in se zapišejo v posebni pomnilnik /5/. Tako se potrebne operacije za izračun izhodnega signala y(k) omejijo na seštevanje in deljenje z dve. Žal pa takšne strukture ni možno uporabiti v sistemih adaptivnih digitalnih FIR sit, saj se v teh sistemih koeficienti dinamično spreminjajo. Rešitev je uporaba enote za sproten izračun koefi- cientov, ki je aparaturno najkompleksnejši del pri izvedbi digitalnega FIR sita v strukturi porazdeljene aritmetike /8/. Klasični način implementacije aritmetične-logične enote za izračun utežne vsote temelji na strukturi koncentrirane aritmetike. V strukturi koncentrirane aritmetike ločimo dve obliki nerekurzivnih digitalnih sit. Prva je struktura s porazdeljenimi seštevalniki, ki jo prikazuje slika 1. Druga struktura digitalnega FIR sita je izvedba z enim globalnim seštevalnikom. Blokovno shemo prikazuje slika 2. m -e ¥ Z K-: yik) Slika 2: Nerekurzivno digitalno sito v strukturi koncentrirane aritmetike s skupnim globalnim seštevalnikom Fig. 2: The FIR digital filter structure in concentrated arithmetic with a global adder Strukturo digitalnega FIR sita v koncentrirani aritmetiki s porazdeljenim seštevalnikom je enostavneje implementirati v programirno vezje. V programirnem vezju je enostavneje realizirati večje število zaporednih seštevalnikov, kot pa globalen seštevalnik. Poleg tega je struktura s porazdeljenimi seštevalniki tudi primernejša za modularno zgradbo nerekurzivnega digitalnega sita, kjer je možno enostavno povečati število uporabljenih koeficientov. Podana struktura nerekurzivnega digitalnega sita s slike 1 zadosti drugemu kriteriju o zahtevi po pomnilniku in tretjemu kriteriju o zbiranju in razmeščanju podatkov znotraj strukture. Pri uporabi strukture z globalnim seštevalnikom je potrebno za povečanje stopnje nerekurzivnega digitalnega sita spremeniti celotno strukturo globalnega seštevalnika. Postopek implementacije nerekurzivnega digitalnega sita v programirno vezje omogoča pomembno zmanjšanje aparaturne kompleksnosti izvedbe aritmetičnih operacij. Pri tem se število potrebnih aritmetičnih operacij ne spremeni. Za zmanjšanje aparaturne kompleksnosti aritmetičnih operacij uporabljenih v nerekurzivnem digitalnem situ smo uporabili zaporedno logiko /7/. Vse spremenljivke so zapisane na bitnem nivoju. Takšen zapis omogoča zmanjšanje aparaturne kompleksnosti implementacije enot za izvaja- m p z Z yik] Slika 1: Nerekurzivno digitalno sito \/ strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki Fig. 1: The FIR digital filter structure in concentrated arithmetic v^ith a distributed adder nje aritmetično-logičnih operacij. Princip je podoben cev-Ijenju, ki ga poznamo pri mikroprocesorjih. Ideja je v tem, da se zahtevna operacija razbije na več enostavnih, katere pa lahko tečejo hitreje. Z enostavno implementacijo več enakih struktur za izvajanje aritmetičnih operacij dosežemo njihovo sočasno izvajanje. Zaradi sočasnega izvajanja arit-metično-logičnih operacij je izračun otipka izhodnega signala odvisen samo od dolžine zapisa Bu vhodne besede u(k). 2. Izvedba aritmetično-logičnih operacij z zaporedno logiko Za ponazoritev izvedbe aritmetično-logičnih operacij z zaporedno logiko vzemimo izračun produkta po enačbi (1) med vektorjem koeficientov h nerekurzivnega digitalnega sita z N koeficienti in vektorjem vhodnega signala u. V enačbi sta vektorja h in u dimenzije N. Za izračun otipka izhodnega signala y{k) potrebujemo N množenj. Če so vrednosti komponent vektorja množitelja Un omejene na intervalu [-1 1 ], jih lahko zapišemo v binarni obliki z dvojiškim komplementom. = -^«.0 + Du (2) bit. Z uporabo binarnega zapisa spremenljivke Un v enačbo (1) zapišemo z, W-l f Bu~\ n=0 V 1=1 (3) Z zamenjavo vrstnega reda seštevanj dobimo izraz, ki omogoča izračun skalarnega produkta dveh vektorjev h in u na drugačni osnovi. Iz enačbe (3) zapišemo izraz za delne produkte pn med komponentami vektorja koeficientov vhoda Un in komponentami vektorja koeficientov sita ftn, Bu (4) in izraz za izračun delnih vsot produktov vpn vsot iz delnih produktov Pn, 1 Wn = Pn + ' « = 0,1,...,7V-1, (5) Izračun utežne vsote med vektorjema h in u je, y = =Y,vp„. (6) « = 0 v enačbi (2) je z ßu določena dolžina binarne besede za zapis vrednosti Un, z bn,\ so označene binarne spremenljivke, ki zavzemajo le vrednosti O ali 1. Predznak določa prvi najbolj utežen bit ön.o, ön,Bu-i pa je najmanjši utežni Izraz (6) predstavlja tudi izračun izhodne vrednosti nerekurzivnega digitalnega sita z N koeficienti na zasnovi MAC (Multply and Accumulate) strukture. Na osnovi podanih enačb (4), (5) in (6) smo načrtali nerekurzivno sito v strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki. /?:,iß,H S,. , polje zaporednih množilnikov N-ti množilnik (A/-1)-ti množilnik (A/-2)-ti množilnik polje A/-tih zaporednih množilnikov 3. množilnik 2. množilnik 1. množilnik uik) -pm...... -Mk)..... polje zaporednih seštevalnikov ..m-dk).......p. .....Vp!:::(/().> -mk)........ .mii} polje pomnilnih celic m'Akdlp. ypidkrü^ .....................................................................vpm.................. A/. > Slika 3: Povezava treh osnovnih enot nerekurzivnega digitalnega sita v strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki Fig. 3: Tree structure of FIR digital filter in concentrated arithmetic with distributed adder Strukturo nerekurzivnega digitalnega sita smo organizirali tako, da smo pri njeni implementacijo uporabili zaporedno logiko za izvajanje aritmetično-logičnih operacij. Shemat-sko povezavo treh glavnih enot nerekurzivnega digitalnega sita v strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki, prikazuje slika 3. Digitalno FIR sito v strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki sestavljajo tri glavne enote: polje zaporednih množilnikov, polje zaporednih seštevalnikov in polje pomnilnih celic. Tako organizirana struktura digitalnega FIR sita je osnova za implementacijo v programirno vezje. 3. Uporaba zaporedne logike za izvajanje aritmetično-logičnih operacij pri implementaciji digitalnega FIR sita Namesto povezave osnovnih enot, ki določajo strukturo digitalnega FIR sita s slike 3, lahko strukturo digitalnega FIR sita prikažemo in opišemo tudi kot povezavo posameznih celic, ki vsebujejo zaporedni množilnik, zaporedni seštevalnik in pomični register. Blokovno shemo celice prikazuje slika 4. u{k)zaf> —J.—-»1 zaporedni množilnik P Slika 7: Blokovna shema zaporednega seštevalnika Fig. 7: Serial adder block scheme Na sliki 7 je prikazan zaporedni seštevalnik ima dva vhoda. Na vhod An je pripeljemo n-to komponento delnega produkta pnik) in na vhod Bn pripeljemo n-to komponenta delnega produkta Pn+i (/<"), ki se iterativno deli z dve, kot to opisuje izraz (5). Izhod Sn predstavlja novo izračunano vrednost vsote delnega produkta vpn. Tretji sestavni del celice, prikazane na sliki 4, je pomični register (FIFO). Sestavljen je iz D pomnilnih celic velikosti ßu-bitov. Poleg treh opisanih enot celice, je za delovanje sita potrebno še uporabiti enoto za sinhronizacijo in enoto za vpis koeficientov. Za znižanje cene končnega izdelka pa je potrebno imeti v mislih čim manjše število uporabljenih priključkov, s tem bo tudi zunanji vmesnik programirnega vezja manjši. Ob inicializaciji programirnega vezja, je vanj potrebno vpisati vektor koeficientov digitalnega FIR sita h. Struktura nerekurzivnega digitalnega sita pa se lahko preuredi tudi tako, da so koeficienti zapisani že v samem čipu, če aplikacija ne zahteva spreminjanja koeficientov. Čas vnosa koeficientov namreč podaljša inicializacijo nerekurzivnega digitalnega sita za 16 period signala ure. Takšna struktura nerekurzivnega sita omogoča prilagajanje sita uporabljeni aplikaciji. Pri uporabi nerekurzivnega digitalnega v adap-tivnem sistemu je možen sproten vnos koeficientov. Načrtovanje sita je potekalo s programskim paketom ISE 6.0 podjetja Xilinx. Na najvišjem nivoju je potekalo načrtovanje na osnovi shematskega vnosa z načrtovalskim orodjem Xilinx ECS (Engineering Capture System). V jeziku VHDL je potekalo načrtovanje zaporednega množilnika, FIFO registrov in zaporednih seštevalnikov. 4. Rezultati Implementacijo digitalnega nerekurzivnega digitalnega sita v programirno vezje smo opravili s pomočjo programskega razvojnega orodja ISE 6.1 podjetja Xilinx. Za testno aplikacijo digitalnega FIR sita smo uporabili 16 koeficientov s 16-bitno kvantizacijo. Prav tako smo vliodno-izhodno besedo zapisali s 16-bitno kvantizacijo. Na osnovi simulacijskih rezultatov dobljenih s programom ModelSim smo ugotovili, da znaša največja frekvenca osnovnega signala ure 71 MHz. Za procesiranje enega otipka potrebujemo 16 period osnovnega urinega signala, kar omogoča frekvenco vzorčenja 4.4MHz. Odvisnost linearnega naraščanja strukture digitalnega FIR sita od stopnje sita, smo preverili z implementacijo štirih različnih stopenj digitalnih FIR sit v programirno vezje XC3S-400 firme Xilinx /9/. Vezje je družine Spartan-3 s sistemom 400k vrat kar ustreza 8,064 logičnim celicam. Velikost matrike konfiguracijskih logičnih celic (CLBs Configurable Logic Blocks) je dimenzije 32x28, kar znese 896 konfiguracijskih logičnih celic. Vsaka celica zaseda v strukturi programirnega vezja štiri rezine (Slices). Uporabljeno programirno vezje XC3S-400 s 3584 rezinami je eno manjših v družini Spartan-3. Ta družina vsebuje vezja od 50k vrat do 5M vrat, kar je od 200k do 20M rezin (Slices). Implementacijo smo izvedli za sita z 8, 16, 32 in 64. koeficienti. V tabeli 1 je podana zasedenost programirnega vezja glede na število vhodno izhodnih priključkov (lOB) in število uporabljenih rezin (Slices). Pri vseh digitalnih FIR sitih smo uporabili 16-bitno kvantizacijo vhodno-izhodne besede. Tabela 1: Zasedenost programirnega vezja XC3S-400 pri implementaciji digitalnega FIR sita z 8, 16, 32 in 64. i