ADAPTIVNA STRUKTURA S POLJI PROGRAMIRNIH VEZIJ ZA IZVEDBO NEREKURZIVNIH DIGITALNIH SIT
Davorin Osebik, Rudolf Babič, Mitja Solar
Fakulteta za elektrotehniko računalništvo in informatiko, Univerza v Mariboru,
Maribor, Slovenija
Ključne besede: asinhrono vezje, fundamentalni način, procesna algebra, preverjanje modelov, ACTL
Izvleček: V članku so opisane izvedbe digitalnih FIR sit s polji programirnih FPGA vezjih, l<i so primerna za uporabo v adaptivnih aplikacijah digitalnih sistemov Prikazana je analiza kompleksnosti aparaturne izvedbe adaptivnih struktur digitalnih FIR sit. Podali smo primerjavo vzporedne oblike digitalnega FIR sita v strukturi porazdeljene aritmetike z digitalnim FIR sitom v strukturi koncentrirane aritmetike izvedenim z uporabo zaporedne logike za izvajanje aritmetično logičnih operacij. Za obe strukturi smo opravili analizo naraščanja aparaturne kompleksnosti v odvisnosti od stopnje sita. Z dobljenimi rezultati smo pokazali primernost izvedbe digitalnih FIR sit v strukturi koncentrirane aritmetike z uporabo zaporedne logike za izvajanje aritmetično logičnih operacij.
The Adaptive Structure with FPGA Circuits for Adaptive FIR
Digital Filter Realization
Key words: digital signal processing, FIR digital filter, distributed arithmetic, direct calculation of partial products, bit serial multiplier MAC - Multiply and Accumulate, digit serial FIR filter, FPGA implementation
Abstract: In this article the two mode of hardware implementation of digital FIR filter in adaptive structure implemented with field programmable gate arrays XG4000 is presented. Implementations of digital FIR filter with programmable logic cell array circuits can be realized using different structures. Adaptive application of digital FIR filters reguires low complexity and guick enough entry of coefficients and calculation of output word y{k).
These conditions are satisfied by implementation of digital FIR filter in the structure of concentrated arithmetic with distributed adders and implementation in the structure of distributed arithmetic in fully parallel form. The structure of distributed arithmetic in fully parallel form is shown in block diagram in figure 3 and digital FIR filter in the structure of concentrated arithmetic with distributed adders is shown in figure 1.
Fully parallel form of digital FIR filter In the structure of distributed arithmetic
The vector of directly calculated partial sums of coefficients v(k-f) is calculated in circuit's unit for up-to-date calculation of partial sum of coefficients. Equation (10) describes calculation of the vector of partial sums of coefficients v(k-1). Equations 5, 7 and 9 describe the relationship between input signal u(k), vector of history of input signal u(/<) and vector bu(/(-1), where the öu(k-i).i are the bits with values 0 or 1, bu(k-i).Buis the sign bit and öu(k-)).o is the last significant bit (LSB). The vector bu(/<-1) has dimension ßuxW, where Bu is the number of bits of input signal u(k} and W is the number of coefficients of FIR filter The output word is calculated by equation (13). Tables 1 and 2 show the increase of the number of configuration logic blocks. The increase of configuration logic block depends on number of taps digital FIR filter and number of bits Bh. Sh describes quantization of the taps of digital FIR filter The hardware complexity of the structure of fully parallel form of digital FIR filter increases with (const. x/VxBh)^.
Digital FIR filter In the concentrated arithmetic
In this chapter the two mode hardware implementation of digital FIR filter in concentrated arithmetic is presented. This implementation of FIR filter uses parallel multipliers or serial multipliers. We constructed serial multiplier based on parallel multiplier Figure 4 shows a diagram of parallel multiplier Implementation of the parallel multiplier with two 16 bits long words needs 528 configuration logic blocks. Preliminary estimation of device utilization for part XC4013 is shown on table 3. The parallel multipliers take up the disproportionally large amount of the configuration logic blocks.
The serial multiplier is composed of one ßut2 -input adder one ßu -bit multiplexer, and two ßu -bit register Bu is the number of bits of input word u(k). One input /7i of this multiplier is in parallel form while other u(k) Is bit serial with the least significant bit öu(k-n,o presented first, h, are the coefficients of digital FIR filter The output is bit serial, with the least significant bit first. Figure 5 shows the structure of serial multiplier ßu -bit multiplexer can be replaced by ßu -bit register Figure 6 shows the structure of serial multiplier without multiplexers. Preliminary estimation of device utilization for part XC4013 of one is shown on table 4 and Preliminary estimation of device utilization for part XC4013 of sixteenth is shown on table 5.
All these hardware structures of digital FIR filter were constructed with OrCAD Express and Xilinx XAGT 5.2. Fully parallel form of digital FIR filter with 16-tabs in the structure of distributed arithmetic obtained equally hardware complexity than digital FIR filter with 16-tabs in concentrated arithmetic.
1. Uvod	rnnožilniki. Žal SO množilniki za aparaturno izvedbo najkompleksnejši elementi. Pri digitalnil^ sitili z nespremenljivimi
Digitalna FIR sita, ki jih uporabljamo v adaptivnih sistemili,	koeficienti učinkovito in enostavno rešujejo problem
morajo imeti takšno strukturo, da je možno spremeniti vse	aparaturne digitalnega FIR sita strukture porazdeljene arit-
njihove koeficiente v času enega otipka vhodnega signala.	metike(DA, Distributed Arithmetic)/1, 2/. Pri izračun izhod-
Pri večini aplikacij digitalnega procesiranja signalov, kakor	nega signala po postopku porazdeljene aritmetike upora-
tudi pri digitalnih FIR sitih, so njihovi osnovni gradniki	bljamo tabele, v katerih so zapisane predhodno izračunane
delne vsote koeficientov (LUT, look up table). Algoritem, kjer poteka množenje po postopku porazdeljene aritmetike (DA) s pomočjo tabel (LUT) s predhodno izračunanimi delnimi vsotami koeficientov, se imenuje DALUT. Izhodna vrednost digitalnega FIR sita se izračunava s pomočjo algoritma množenja in akumuliranja (MAC, Multiply and Accumulate) /3/ izhodne vrednosti. Običajno delne vsote koeficientov zapišemo v zunanji pomnilnik
Opisan postopek je uporaben le za sita s približno A/=20 koeficienti, saj potrebujemo za sito z N koeficienti pom-nilniških lokacij.
Za izvedbo sit v porazdeljeni aritmetiki višjih stopenj obstaja več načinov za zmanjševanje aparaturne kompleksnosti vezja. Dosedanje raziskave so potekale v smeri zmanjšanja potrebnega pomnilnika za zapis predhodno izračunanih delnih vsot koeficientov. Pomnilnik za zapis delnih vsot koeficientov je možno zmanjšati z 2"^ na pomnilniških lokacij z upoštevanjem simetričnosti koeficientov /4/. Na osnovi simetričnosti koeficientov smo razvili FIR sito z 32 koeficienti s 16 bitno vhodno besedo, dolžina aritmetične enote je bila med 16 in 24 bit. Izvedba in rezultati tako napravljenega sita so prikazani v /5/.
Z razdelitvijo FIR sita na kaskade dosežemo zmanjšanje potrebnih pomnilniških lokacij za zapis delnih vsot koeficientov z 2^ na 2^1+2^2+... + 2^"^, pri tem je A/i /V2...A/m zapisano število koeficientov posamezni kaskadi. Pri tem mora biti vsota posameznih koeficientov kaskad enaka vsoti vseh koeficientov. Izdelano kaskadno obliko sita z 58 koeficienti, kjer smo še dodatno zmanjšala aparaturno kompleksnost sita z upoštevanjem simetričnosti koeficientov, smo skupaj z dobljenimi rezultati meritev predstavili v /6/.
Z razvojem zmogljivejših programirnih FPGA vezij se je pokazalo, da se je zunanjemu pomnilniku za zapis delnih vsot koeficientov možno izogniti /12/. Za ta namen lahko uporabimo strukture digitalnih FIR sit v porazdeljeni aritmetiki, kjer v več pomnilniške lokacije, ki se nahajajo v FPGA vezju, vpišemo le karakteristične delne vsote. Ostale delne vsote aritmetika digitalnega FIR sita izračunava sproti /8/. Izdelano digitalno FIR sito, ki je temeljilo na karakterističnih delnih vsota koeficientov in dobljene rezultate smo prikazali v /9/. Takšna oblika digitalnega FIR sita je uporabna tudi v aplikacijah adaptivnih digitalnih FIR sit.
Za digitalna FIR sita v adaptivnih aplikacijah digitalnih sistemov, ki temeljijo na porazdeljeni aritmetiki, je uporaben postopek sprotnega izračuna delnih vsot koeficientov /10,11/. Ta oblika digitalnega FIR sita se imenuje tudi paralelna oblika digitalnega FIR sita v porazdeljeni aritmetiki (ang. fully parallel DA mode).
Ph adaptivnih digitalnih FIR sitih, kjer se koeficienti sita spremenijo v vsakem otipku, so zanimive strukture digitalnih FIR sit v koncentrirani aritmetiki, ki vsebujejo množilnike. V članku bosta predstavljena dva pristopa izvedbe digitalnega FIR sita s programirnimi FPGA vezji: digitalna FIR sita v strukturi porazdeljene aritmetike s sprotnim izračunom
delnih vsot koeficientov in digitalna FIR sita v strukturi koncentrirane aritmetike. Pri predstavitvi FIR sit v koncentrirani aritmetiki bomo posebej nakazali možnosti izvedene z zaporedno logiko za izvajanje aritmetično logičnih operacij.
2. Digitalna FIR sita
Osnovno strukturo digitalnega nerekurzivnega digitalnega sita opisuje konvolucijska enačba.
N~l

(1)
1=0
Za izvedbo digitalnih FIR sit s programirnimi FPGA vezji imamo na razpolago več različnih struktur. Digitalna FIR sita, ki jih želimo uporabljati v adaptivnih aplikacijah, morajo ustrezati naslednjim zahtevam: imeti morajo dovolj majhno aparaturno kompleksnost, dovolj hiter vpis koeficientov v strukturo FIR sita, dovolj hiter izračun izhodne besede.
Poznani sta dve osnovni obliki nerekurzivnih digitalnih FIR sit, kjer izračun izhodne vrednosti y{k) poteka po konvolu-cijski enačbi (1). Prva je struktura s porazdeljenim sešte-valnikom, ki jo prikazuje slika 1.

Slika 1: Digitalno FIR sito v strukturi koncentrirane aritmetike s porazdeljenimi seštevalniki
Fig. 1: The digital FIR filter in the structure
concentrated arithmetic structure with distributed adders
Pri tej strukturi digitalnega FIR sita s porazdeljenim sešte-valnikom običajno uporabljamo takšne algoritme za izvedbo aritmetično logičnih operacij, ki temeljijo na množenju in akumuliranju izračunane vrednosti (MAC, Multiply and Accumulate). Dobljene vrednosti posameznih produktovpm (m=0, 1 ... A/-1) zakasnimo z uporabo zakasnilnih členov z \ Zaradi tega je za izračun vsake vsote posameznega produkta na razpolago celotna perioda vzorčenja vhodne besede. Skupaj z zakasnilnimi členi, je pri izračunu izhodne besede možno enostavno uporabiti postopek cevljenja.
Druga struktura je digitalno FIR sito s skupnim globalnim seštevalnikom na izhodu, ki jo prikazuje slika 2.
Pri tej strukturi digitalnega FIR sita s skupnim globalnim seštevalnikom je potrebno vse dobljene produkte pi iz množilnikov v enem taktu sešteti, kar pri sitih višjih stopenj za aparaturno izvedbo ni enostavno.
Obe predstavljeni strukturi digitalnega FIR sita s slik 1 in 2 vsebujeta množilnike. Digitalna FIR sita potrebujejo za veliko slabljenje v zapornem pasu veliko število koeficientov.
Slika 2: Digitalno sito realizirano struicturi
koncentrirane aritmetike s skupnim globalnim seštevainikom
Fig. 2: The digital FIR filter in the structure
concentrated arithmetic with global adder
s tem pa posledično tudi veliko število množilnikov. Aparatur-na kompleksnost digitalnega FIR sita v koncentrirani aritmetiki se zaradi množilnikov zelo poveča. Za digitalna FIR sita uporabljena v adaptivnih aplikacija je možno zmanjšanje aparaturne kompleksnosti doseči z:
izvedbo digitalnega FIR sita v strukturi porazdeljene aritmetike s sprotnim izračunom delnih vsot koeficientov in,
z izvedbo digitalnega FIR sita v strukturi koncentrirane aritmetike z uporabo zaporedne logike za izvajanje aritmetično logičnih operacij /3/.
3. Digitalno FIR sito v strukturi
porazdeljene aritmetike s sprotnim izračunom delnih vsot koeficientov
Digitalno FIR sito, ki se uporablja v adaptivnih aplikacijah digitalnih sistemov je možno izvesti v strukturi porazdeljene aritmetike s sprotnim izračunom delnih vsot koeficientov. Takšna oblika digitalnega FIR sita je poznana tudi kot paralelna oblika digitalnega FIR sita v strukturi porazdeljene aritmetike. To obliko FIR digitalnega sita smo že uspešno uporabili v adaptivnem digitalnem FIR situ s 16 koeficienti, s 16 bitno kvantizacijo vhodne-izhodne besede in med 16 in 24 bitno širino notranje aritmetične enote.
3.1. Matematični opis izračuna izhodne besede pri FIR situ v porazdeljeni aritmetiki
Pri aparaturnih izvedbah digitalnih FIR je vrednost izhodne besede y{k) zakasnjena zaradi časa, ki ga zahteva digitalno procesiranje signala zakasnjena za en otipek. To zakasnitev opišemo z enačbo (2),
N-\
y(k) = ^hru(k-l-i)
1=0
(2)
V enačbi (1) so hj koeficienti digitalnega FIR sita, N je število vseh koeficientov in u{k) je vhodna vrednost FIR sita. Konvolucijsko enačbo (2) , ki podaja zvezo med izhodno vrednostjo y{k), koeficienti FIR sita /?, in vhodno vrednostjo u(k), lahko predstavimo tudi v vektorski obliki z enačbo (3),
y(k)=h^'u(k-\)
(3)
V enačbi (3) je h vektor koeficientov digitalnega FIR sita in u{k-1) je vektor predhodnih vrednosti otipkov vhodnega signala u{k). Pri digitalnem FIR situ z N koeficienti enačba (4) 30 komponente obeh vektorjev podane z:
(4)
Pri izračunu izhodne vrednosti y(k) digitalnega FIR sita v porazdeljeni aritmetiki s sprotnim izračunom delnih vsot koeficientov izhajamo iz enačbe (3). Po postopku porazdeljene aritmetike je potrebno opraviti množenje vektorja koeficientov digitalnega FIR sita h in vektorja koeficientov vhoda u(/(-1). Pri tem postopku vrednosti vhodnega signala u{k) zapišemo v bitni obliki z dvojiškim komplemen-tom. Zapis za ßu bitno kvantizacijo vhodnega signala u{k) podaja enačba (5),
" h '				
K	\l(k-	-0=	ii{k-	-2)
	in			
			u{k-	




(5)
V enačbi (5) najbolj utežni bit öu(k-i),o predstavlja predznak k-tega otipka vhodne besede. Zaradi časa, ki je potreben za postopek digitalnega procesiranje izhodne besede digitalnega FIR sita y{k), je potrebno pri opisu z enačbama upoštevati zakasnitev za vrednost enega otipka. Zakasnitev je predstavljena v enačbi (2). Z upoštevanjem te zakasnitve obravnavamo vrednost vhodnega signala digitalnega FIR sita u{k) zakasnjenega za en otipek. Zato enačba (5) za zapis vhodnega signala v bitni obliki preide v enačbo (6),
«„-1


(6)
1=1
Trenutni otipek vhodnega signala u{k) in njegove predhodne vrednosti uik-l), u(k-2)... lahko predstavimo z vektorjem vhodnega signala u{k) Vektor vhodnega signala u{k) v bitni obliki z dvojiškim komplementom predstavimo z naslednjimi komponentami, ki jih podaja enačba (7),

Bu-l
Mk}0
'Mk^ilO
/=1 Bi,-I
Bu-\
/=1
(7)
V enačbi (7) predstavlja zapis öu(k),i /-ti bit vhodne besede u(k) digitalnega FIR sita. Pri tem je število bitov bu.\ enako širini vhodne besede u(k). V našem primeru jo označuje spremenljivka ßu. Z upoštevanjem zakasnitve vhodnega signala zaradi zaporedno vzporedne pretvorbe dobimo vektor vhodnega signala zakasnjen za en otipek u{k-^). Ta

Bu-\
(=1 Bu~l
!=1 Bu-l
(=1
(8)
vektor vhodnega signala zapišemo prav tako v bitni obliki z dvojiškim komplementom z enačbo (8),
Iz enačbe (8) izpišimo vrednosti bitov buik) za vsak otipek vhodne besede u(k) in njihove predhodne vrednosti. Dobljene vrednosti bitov predstavimo z vektorjem bitnega zapisa bu(/(-1) vhodnega signala u(k) in predhodnih vrednosti vhodnega signala u{k-^).




(9)
Pri tem dimenzija vektorja bitnega zapisa bu(/<-1) predhodnih vrednosti vhodnega signala znaša Bu^A/. Bu je število bitov za zapis vhodne besede u{k), N je število koeficientov digitalnega FIR sita. S produktom vektorja bitnega zapisa zgodovine vhodnega signala huik-l) in vektorja koeficientov h dobimo vektor delnih vsot koeficientov vik-l), ki ga podaja enačba (10),

(10)
Dobljeni vektor delnih vsot koeficientov v(k-1) ima N komponent, ki so predstavljene z enačbo (11),
4-1)=

(11)
Vektor dobljenih delnih vsot v(k-^) je potrebno izračunati v vsaki k-tl taktu periodi vzorčenja vhodnega signala. Izhodno vrednost digitalnega FIR sita dobimo s pomočjo bitnega zapisa bu{k-1) trenutnih in predhodnih vrednosti vhodnega signala u{k). Pri tem lahko vektor bu(/f-1), ki ga opisuje enačba (9) razdelimo na posamezne vrstice /. Vsaka /-ta vrstica vsebuje vektor bitov bu{k-\), ki je potreben za zapis otipka vhodne besede u(k). Zapis tako razdeljenega vektorja bu(/<-1) na vektorje v posameznih /-tih vrsticah bu(k-i),bu podaja enačba (12),
»(A-/) -	"u(k~ili

J (12)
V enačbi (12)/ teče od /= 1... A/ in označuje /-te otipke vhodnega signala u(k). Dobljeni vektor bu(/(,-rt je osnova za izračun izhodne vrednosti digitalnega FIR sita y(/(). Izračun izhodne vrednosti digitalnega FIR sita poteka po enačbi (13).
Sk-1

(13)
1=1
Enačba (13) opisuje izračun vseh delnih vsot koeficientov. Za izračun izhodne besede po enačbi (13) je potrebno Su ite racij.
3.2. Izvedba in delovanje paralelne oblike digitalnega FIR sita v strukturi porazdeljene aritmetike
s programirnim FRGA vezjem smo realizirali paralelno obliko digitalnega FIR sita v strukturi porazdeljene aritmetike. Blokovno shemo prikazuje slika 3.
izhod
Slika 3: Vzporedna oblika digitalnega FIR sita v strukturi porazdeljene aritmetike Fig. 3: Fully parallel form of digital FIR filter In the structure of distributed aritlimetic
Digitalno FIR sito, ki ga prikazuje slika 3, smo izdelali s programirnim FPGA vezjem družine XC4000E. Predstavljeno vezje digitalnega FIR sita ima N= 16 koeficientov, vhodna beseda u{k) je dolžine ßu=16 bitov izhodne beseda y(k) je dolžine ßY=16 bitov, koeficienti digitalnega FIR sita so dolžine Bh=16 bitov in dolžina notranje aritmetične enote se zaradi robustnosti giblje med 16 in 22 biti.
Vzporedno obliko digitalnega FIR sita s slike 3 sestavljajo štiri različna vezja: vezje vhodnega polja, vezje pomnilnih celic za koeficiente FIR sita, vezje aritmetične enote za sprotni izračun delnih vsot koeficientov in vezje aritmetične enote za izračun izhodne besede. Tabela 1 prikazuje naraščanje kompleksnosti posameznih vezij glede na število koeficientov digitalnega FIR sita N, kvantizacijo vhodne besede ßu oziroma kvantizacijo zapisa koeficientov digitalnega FIR sita Bh.
Tabela 1: Kompleksnost posameznih vezij v vzporedni obliki FIR sita i/ strukturi porazdeljene aritmetike
Table 1: The complexity of particular circuits in the fully parallel form of digital FIR filter realization In distributed arithmetic
Iiiic vezja	Kompleksnost vezja
vezje vhodnega polja	konst. xA'xBu
vezje pomnilnih celic koeficientov .sita	konst. xA^xBii
vezje aritmetične enote za spfoten izračun delnih vsot koeficientov	(konst. xA'xBh)^
vezje aritmetične lo	konst. xBn
Iz tabele 1 je razvidno, da kompleksnost vezja aritmetične enote za sprotni izračun koeficientov narašča eksponen-cialno, zaradi tega je takšna oblika digitalnega FIR sita primerna le za aparaturne izvedbe sit z manj kot /V=20 koeficientov.
Pri predstavljeni vzporedni obliki digitalnega FIR sita v strukturi porazdeljene aritmetike je dosežen čas izračuna izhodne besede y(k) pri frekvenci osnovne ure 32 MHz znašal 1 |is. V tabeli 2 podajamo kompleksnost predstavljene vzporednega digitalnega FIR sita v porazdeljeni aritmetiki izvedenega s programirnim FPGA vezjem družine XC4000E.
Tabela 2: Zasedenost programirnega FPGA vezja pri Izvedbi vzporedne oblike digitalnega FIR sita v strukturi porazdeljene aritmetike
Table 2: The programmable FPGA device utilization for fully parallel form of digital FIR filter in the structure of distributed arithmetic
Preliminary estimate of device utilization for part 4013EPG223: 55% utilization of I/O pins.	(105 of 192)
82% utilization of CLB FG function generators. (946 of 1152) 3% utilization of CLB H function generators. ( 20 of 576) 92% utilization of CLB flip-flops.	(1058 of 1152)
17%, utilization of bus resources.	( 16 of 96)
4. Digitalna FIR sita v strukturi
koncentrirane aritmetike z uporabo zaporedne logike za izvajanje aritmetično logičnih operacij
Množilniki so eden najpomembnejših elementov v algoritmih za digitalno procesiranje signalov. Pri digitalnih FIR sitih s konstantnimi koeficienti, postopek porazdeljene aritmetike elegantno reši izvedbo produkta dveh matrik. Za digitalna FIR sita višjih stopenj v adaptivnih sistemih je uporaba porazdeljene aritmetike zaradi naraščajoče aparaturne kompleksnosti zahtevna. Zato so zanimiva v adaptivnih aplikacijah za digitalno procesiranje signalov digitalna FIR sita izvedena v strukturi koncentrirane aritmetike z uporabo množilnikov.
Pri digitalnih FIR sitih izvedenih v strukturi koncentrirane aritmetike je potrebno pri vsakem otipku opraviti produkt vektorjev koeficientov digitalnega FIR sita h""" in vektorja koeficientov vhodnega signala u(k), po enačbi (3). Za izvedbo tega produkta potrebujemo pri FIR digitalnem situ z N koeficienti N množilnikov. Za izvedbo teh množilnikov je možno uporabiti zaporedno logiko za izvajanje aritmetično logičnih operacij /1/. S tem močno zmanjšamo aparaturne kompleksnost izvedbe takšnega sita, pri tem se čas izračuna izhodne besede bistveno ne spremeni. Pri uporabi zaporedne logike za izvajanje aritmetično logičnih operacij, ločimo različne izvedbe množilnikov glede na obliko zapisa množenca in množitelja: oba množenec in množitelj sta zapisana vzporedni obliki in množenec je zapisan v zaporedni obliki, množitelj je zapisan v vzporedni obliki.
Uporaba zaporedne logike za izvajanje aritmetično logičnih operacij v digitalnem FIR situ ima naslednje prednosti pred paralelno obliko digitalnega FIR sita v strukturi porazdeljene aritmetike:
kompleksnost aparaturne opreme narašča linearno s številom koeficientov sita,
zaradi narave seštevalnikov v programirnih FPGA vezjih je čas izračuna izhodne besede y{k) digitalnega FIR sita primerljiv s časom izračuna v vzporedni obliki digitalnega FIR sita v strukturi porazdeljene aritmetike in
v primeru uporabe digitalnih FIR sit v adaptivnih aplikacijah je ugoden zaporedni prenos koeficientov v strukturo digitalnega FIR sita. Zato z uporabo zaporedne logike za izvajanje aritmetično logičnih operacij ne potrebujemo pretvornikov za pretvorbo zaporedne oblike koeficientov FIR sita v vzporedno obliko koeficientov FIR sita, kar še dodatno zmanjšuje aparaturna kompleksnost vezja.
Predstavili bomo dve obliki množilnikov, ki jih je možno izvesti s programirnimi FPGA vezji: vzporedni množilnik, pri katerem sta množenec in .množitelj zapisana v vzporedni obliki in zaporedni množilnik, kjer je množenec zapisan v vzporedni obliki množitelj pa je podan v zaporedni obliki.
4.1. Vzporedni množilnik pri digitalnem FIR situ v koncentrirani aritmetiki
Naša izvedba zaporednega množilnika.je temeljila na vzporednem množilniku. Pri tej obliki množilnika sta množenec, v našem primeru h\ in množitelj u(k) zapisana v vzporedni obliki. Dobljena izhodna vrednost pi je prav tako v vzporedni obliki dolžine Sh+Su bitov. Pri tem je množenec dolžine 6h bitov, množitelj pa dolžine Su bitov. Blokovno shemo takšnega množilnika prikazuje slika 4.

B[(B»11..01	A|(B.1)..01 1. krmiljeni
seštevalnik	m
S|(B»1)..11	S10|
16 U»
■Sh-1
81(B,.1),.01	A|(B»1)..0]
2. krmiljeni	
sešlevainik	m
St(B»1)..1l	S|01
1
B|(8«1}.,01	A|(Bk1),.0]
N-ti krmiljen	
sešlevainik	
S|(B»1)..l)	S[0|
J'8H.1 ▼ P(u^h-l} Jpu
pCO
Slika 4: Blokovna shema vzporednega množilnika Fig. 4: The schematic of parallel multiplier
Za aparaturno izvedbo predstavljenega množilnika je potrebno pri digitalnem FIR situ z N koeficienti, zagotoviti vhodnih vodil dolžine ßu-bitov oz Sh bitov in N izhodnih vodil dolžine (BH+ßu)-bitov. Za sito z A/= 16 koeficienti in dolžinami množitelja ßu= 16 bitov in množenca 6h= 16 bitov to znaša okoli 768 povezav, kar je za aparaturno izvedbo s FPGA vezjih precej. Čas izračuna zmnožka Pi je odvisen od hitrosti seštevalnikovv FPGA strukturi. V programirnih FPGA vezjih družine XC4000E so večbitni seštevalniki izvedeni v zaporedni obliki, zato je potrebni čas izračuna vsote dveh besed dolžine 16-bitov 12,5ns. Pri množilniku, kjer opravimo produkt dveh 16-bitnih števil, je uporabljenih 16 sešte-valnikov. Čas izračuna produkta znaša 16x12,Sns.Aparatur-na izvedba vzporednega množilnika v programirnem FPGA vezju je zahtevna, saj zahteva ßu multipleksorjev z dolžino Bh bitov. Multipleksorji so krmiljen z enim izmed bitov množitelja u{k). Delovanje vzporednega množilnika za m-ti koeficient opisuje enačba (14),
P,
Xk)= h„,u(k - m) OT = 0,l,2...yV-l
(14)
V enačbi (14), je vrednost množitelja u{k) zapisana v dvo-jiški obliki z enačbo (5). Posamezne dobljene produkte Pm zapišimo vvektorski obliki z enačbo (15),
p(k) =
Poik)
Py{k)
Pn-i

(15)
Z upoštevanjem enačbe (14), zapišemo enačbo (16) v vektorski obliki. Zapis podaja enačba (16),
p(^)=hu(t)
(16)
V enačbi (16) imata vektorja koeficientov FIR sita h in vektor predhodnih vrednosti vhodnega signala u{k) komponente, ki so podane z izrazom (4). Vrednost produkta nastaja v krmiljenih seštevalnikih. Delovanje m-tega sešteval-nika s slike 4 izmed N seštevalnikov opisuje enačba (17),
_ . A.. "' A..
1-0
bu(k),m = O
(17)
V enačbi (17) predstavlja spremenljivka Sn.m dobljeno vsoto za posamezni bit öuiw.m vhodne besede u(k). Pri tem posamezni bit bu{k).m krmili posamezne seštevalnike. Za vsak krmiljen seštevalnik potrebujemo krmilno vezje sestavljeno iz polja ßu IN vrat.
Dobljene vrednosti produktov p,,, iz vzporednih množilnikov je potrebno sešteti v A/-tih vzporednih seštevalnikih. Pri tem imamo dvoje možnosti: uporabiti strukturo s porazdeljenimi seštevalniki (slika , ki je primernejša za aparaturno izvedbo ali uporabiti strukturo z enim globalnim seštevaln-ikom (slika 2). V tabeli podajamo zasedenost pro-gramirnega FPGA vezja XG4013 pri izvedbi množilnika s 16. bitnima vhodnimi besedama.
Tabela 3: Zasedenost programirnega vezja pri izvedbi vzporednega množilnika s 16 bitnima vhodnima besedama Table 3: The programmable FPGA device utilization for 16-bit parallel multiplier
Preliminary estimate of device utilization for part 4013PG223:
42% utilization of I/O pins.	( 80 of 192)
46% utilization of CLB FG function generators.	(528 of 1152)
0% utilization of CLB H function generators.	( 0 of 576)
0% utilization of CLB flip-flops.	( 0 of 1152)
Zaradi zaporedne narave seštevalnikov v programirnih FPGA vezjih traja izračun produkta dveh 16 bitnih števil 170ns. Izvedba enega množilnika v programirnem FPGA vezju zaseda približno polovico logičnih blokov, ki jih zaseda vzporedna oblika digitalnega FIR sito v strukturi porazdeljene aritmetike, ki je predstavljena na sliki 3. Zaradi takšne aparaturne kompleksnosti je smiselno uporabiti zaporedne množilnike, ki temeljijo na MAC strukturah.
4.2. Zaporedni množilnik pri digitalnem
FIR situ v koncentrirani aritmetiki
Izvedba množilnikov v zaporedni obliki močno zmanjša aparaturno kompleksnost vezja. Čas izračuna izhodnega produkta Pm je odvisen od frekvence osnovne ure s katero deluje zaporedne množilnik in od kvantizacije ßu množitelja u{k). S primerno izbiro ure in kvantizacije vhodne besede, se čas izračuna izhodnega produkta pm v zaporednem množilniku bistveno ne razlikuje od časa izračuna produkta Pm V vzporednem množilniku. Pri vzporednem množilniku poteka izračun produkta pm po enačbi (14). Če v enačbi (14) zamenjamo zapis vhodnega signala u(k) z bitno obliko zapisa vhodnega signala u(k), ki ga podaja enačba (5) potem lahko zapišemo s končno enačbo (18) izračuna produkta Pm z zaporednim seštevalnikom.




(k\
2"

(18)
V enačbi (18) je množenec h\ zapisan v vzporedni obliki z Bh biti, množitelj u{k) je zapisan v zaporedni obliki z ßu biti. Dobljena izhodna vrednost produkta pm je v zaporedni obliki predstavljena z B» +ßu biti. Blokovno shemo množilnika v zaporedni obliki prikazuje slika 5.

10

	D|(B.*1).,0] Q[01 Q((8*!), 1)	
		
	{Bi-ŽVfcmi rog^slor	
		
	(Bt.2H>i;ni sežlu-.afrtk S((0-.2),.01	B,<>-2
		
	8[(B'.1)„0]	
	scšl./odit.	
	! pok{)
aie|. Q(Bh	
	
(Bh2>Mni fcffsler	
Slika 5: Blokovna shema zaporednega množilnika Fig. 5: A plan of serial multiplier
Pri deljenju z 2 ostane na izhodu Q[0] 18-bitnega registra vrednost ostanka pOmik), ki je dolžine ßu bitov. Ta ostanek je v zaporedni obliki, zato ima prikazani zaporedni množilnik na sliki 5 ima za izhodno vrednost produkta pm dva izhoda: izhod zgornjega dela besede pomik) dolžine Bh bitov in izhod spodnjega dela besede pOmik) dolžine ßu bitov. Takšna oblika zaporednega množilnika potrebuje le en sešte-valnik, multiplekser dolžine ßH bito, ki ga sestavlja 8» dvovhodnih IN vrat in zadrževalnik vmesnih vsot i/j. Slika 5 prikazuje m-ti množilnik za n-ti koeficient digitalnega FIR sita. Izhodni produkt Pm(/c) je vsota obeh produktov pom(k) in pcm(k) iz predstavljenega zaporednega množilnika v zaporedni obliki dolžine ßu+ßn bitov.
Pri izvedbi zaporednega množilnika je smiselno nadomestiti multiplekser dolžine Bh bitov s krmiljenimi pomnilniški-mi celicami. Izvedba takšnega zaporednega množilnika je prikazana na sliki 6.
Slika 6: Blokovna shema zaporednega množilnika brez uporabe muitipleksorjev
Fig. 6: A plan of serial multiplier without multiplexers
Na osnovi blokovne sheme prikazane na sliki 6 smo v pro-gramirnem FPGA vezju realizirali zaporedni množilnik. Zasedenost programirnega FPGA vezja za aparaturno izvedbo enega zaporednega množilnika prikazuje tabela 4.
Tabela 4:
Table 4:
Zasedenost programirnega FPGA vezja pri implementaciji zaporednega množilnika s 16 bitnima vhodnima besedama.
The programmable FPGA device utilization for 16-blt serial multiplier
Preliminary estimate of device utilization for part 4013EPG223: 11% utilization of I/O pins.	(21 of 192)
8% utilization of CLB FG function generators. (94 of 1152) 1% utilization of CLB H function generators, ( 5 of 576) 87o utilization of CLB flip-flops.	(88 of 1152)
Realiziran množilnik ima dva 16 bitna vhoda, kjer je množitelj u{k) dolžine ßu=16 bitov in množenec h, je dolžine ßH=16 bitov, ter dvoje izhodov za zmnožka pCmik) dolžine ßu=16 bitov in pOmik) dolžine Bh= 16 bitov. Del logičnih konfigurac-ijskih blokov v FPGA vezju zahteva krmilno logiko zaporednega množilnika. Pri implementaciji več zaporednih množilnikov v isto FPGA vezje lahko uporabimo skupno krmilno vezje. Na osnovi razlike, ki nastane med implementacijo enega množilnika in šestnajstih množilnikov v istem pro-gramirnem FPGA vezju, lahko ugotovimo kolikšen del kon-figuracijskih logičnih blokov je namenjen krmilni logiki in kolikšen del jih je namenjen množilnikom, V tabeli 5 je podana zasedenost enakega programirnega FPGA vezja v katerem je implementiranih 16 zaporednih množilnikov s 16-bitnima vhodnima besedama in 16 bitno izhodno besede.
Tabela 5:
Table 5:
Zasedenost programirnega FPGA pri implementaciji šestnajstih zaporednih množilnikov s 16 bitnimi vhodnima besedama
The programmable FPGA device utilization for sixteen 16-bit serial multiplier
Preliminary estimate of device utilization for part 4013PG223: 19% utilization of I/O pins,	( 36 of 192)
97% utilization of CLB FG function generators, (1122 of 1152) 1 % utilization of CLB H function generators, ( 5 of 576) 73% utilization of CLB flip-flops,	(838 of 1152)
Iz tabel 4 in 5 je razvidno, da potrebujemo za implementacija samo enega zaporednega množilnika v programirnem vezju 67 konfiguracijskih logičnih blokov. Krmilna logika potrebuje 30 konfiguracijskih logičnih blokov, Implementaciji šestnajstih množilnikovveno programirno FPGA vezje doseže enako aparaturno kompleksnost, kot implementacija vzporedne oblike digitalnega FIR sita v strukturi porazdeljene aritmetike. Za digitalna FIR sitaz adaptivno strukturo, ki imajo več kot 16 koeficientov, je za aparaturno izvedbo primernejša izvedba digitalnega FIR sita v strukturi koncentrirane aritmetike z uporabo zaporednih množilnikov,
5. Zaključek
v prispevku smo podali pregled načinov izvedbe digitalnih FIR sit s polji programirnih logičnih FPGA vezij. Pri tem smo podrobno opisali strukturi, ki sta primerni za uporabo digitalnih FIR sit v aplikacijah adaptivnih digitalnih sistemov, Aparaturna izvedba digitalnih FIR v teh aplikacijah s pro-gramirnimi logičnimi FPGA vezji je zaradi vsebovanih množilnikov precej zahtevna, zato je potrebno uporabiti takšne strukture digitalnih FIR sit, ki omogočajo v času enega otipka vhodnega signala zamenjavo vseh njegovih koeficientov. Takšne strukture digitalnih FIR sit imenujemo tudi adaptivne strukture digitalnih FIR sit. Izvedbe adaptivnih struktur digitalnih FIR sit v programirnih logičnih vezjih so zanimive zaradi možnosti enostavnega povečanja stopnje sita z uporabo večjih programirnih logičnih vezij ali z dodajanjem novih programirnih logičnih vezij,
V prispevku je opisana vzporedna oblika digitalnega FIR sita v strukturi porazdeljene aritmetike. Podane so njene prednosti in slabosti glede na strukture digitalnih FIR sit v koncentrirani aritmetiki.
Pri digitalnih FIR sitih v strukturi koncentrirane aritmetike smo nakazali možnosti njihove izvedbe z uporabo množilnikov. Predstavili smo dve vrsti izvedb množilnikov s programirnimi logičnimi vezji, ki jih je možno uporabiti v digitalnem FIR situ z adaptivno strukturo: vzporedni množilnik, ker sta množenec in množitelj zapisana v vzporedni obliki in zaporedni množilnik, kjer je množitelj podan v zaporedni obliki, množenec pa v vzporedni obliki,
S pomočjo dobljenih rezultatov smo podali analizo aparaturne kompleksnosti izvedbe digitalnih sit z adaptivno strukturo. Analizo smo opravili za primer, kjer je bila vhodna beseda dolžine ßu=16, koeficienti sita so bili dolžine eH=16 bitov in izhod digitalnega FIR sita je bil dolžine ßY=16, Pri tem smo notranje aritmetične enote v FIR sitih zaradi zahtev izvedli s 16 do 24 bitno dolžino. Vsa sita smo načrtali s programskim paketom OrCAD 9,0 implementacijo v programirna FPGA vezja družine XG4000E smo izvedli s programskim paketom XACT 5,0 firme Xilinx.
Z rezultati smo pokazali, da izvedba digitalnih FIR sit v koncentrirani aritmetiki narašča linearno s številom koeficientov pri tem je aparaturna kompleksnost za sita z A/= 16 koeficienti po aparaturni kompleksnosti enaka vzporedni obliki digitalnega FIR sita v strukturi porazdeljene aritmetike.
6. Literatura
/1 / R, S, Grover, W. Shang, Q. Li, A Faster Distributed Arithmetic Architecture for FPGAs, Tenth ACM International Symposium on Field Programmable Gate Arrays Monterey California, USA February 24-26, 2002 /2/ Martinez-Peiro, M.; Vails, J,; Sansaloni, T; Pascual, A.R; Boemo, E,I., A comparison between lattice, cascade and direct form FIR filter structures by using a FPGA bit-serial distributed arithmetic implementation, Electronics, Circuits and Systems, 1999, Proceedings of ICECS '99, The 6th IEEE International Conference on , Volume: 1 , 5-8 Sept. 1999 Page(s): 241 -244 vol,1 /3/ Ohsang Kwon, Kevin Nowka, Earl E., A 16-Bit by 16-Bit MAC Design Using Fast 5:3 Compressor Cells, The Journal of VLSI Signal Processing-Systems for Signal, Image, and Video Technology, June 2002 /4/ Les Mintzer, "FIR Filters with Field-Programmable Gate Arrays", Journal of VLSI Signal Processing, vol. 6, pp. 119-127, 1993 /5/ OSEBIK, Davorin, JARC, Bojan, SOLAR, Mitja, BABIČ, Rudolf. A30 tap FIR filter realization with FPGA circuits. V: 5th International Workshop on Systems, Signals and Image Processing, June 3-5, 1998, Zagreb. Proceedings IWSSIP98. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 1998, str. 86-89. /6/ OSEBIK, Davorin, SOLAR, Mitja, BABIČ, Rudolf. Kaskadna izvedba nerekurzivnega digitalnega sita z 58 koeficienti s pro-gramirljivim poljem logičnih vezij. Zbornik šeste Elektrotehniške in računalniške konference ERK '97, 25. - 27 september 1997, Portorož, Slovenija. Ljubljana: IEEE Region 8, Slovenska sekcija IEEE, 1997, str. A/69-72 /7/ Kaluri, K.: Wen Fung Leong; Kah-HoweTan; Johnson, L.; Sod-erstrand. M.; Signals, Systemsand Computers, 2001. Conference Record of the Thirty-Fifth Asilomar Conference on , Volume: 2 , 4-7 Nov, 2001 Page(s): 1340-1344 vol.2 /8/ Bill Allaire, Bud Fischer, Block Adaptivr Filter, XAPP 055, January 9, 1997(Vrsion 1.1) /9/ OSEBIK, Davorin, BABIČ, Rudolf. Izvedba FIR digitalnega sita v porazdeljeni aritmetiki z adaptivno strukturo. Zbornik osme Elektrotehniške in računalniške konference ERK'99, 23.-25, september 1999, Portorož, Slovenija. Ljubljana: IEEE Region 8, Slovenska sekcija IEEE, 1999, zv. A, sir. 59-62. /10/ Steve Knapp, FPGAs furnish fast, furious FIR filters, Personal
engineering, December 1998 /11/ Rolf Enzler, Tobias Jeger, Didier Cottet and Gerhard Troster, High-Level Area and Performance Estimation of Hardware Building Blocks on FPGAs, R, W. Hartenstein and H. Grunbacher (Eds.) FPL 2000, pp. 512-534 2000, Springer-Verlag Berlin Heidelberg 2000 /12/ Kaluri, K.; Wen Fung Leong: Kah-HoweTan: Johnson, L.; Sod-erstrand, M,: Signals, Systems and Computers, 2001. Conference Record of the Thirty-Fifth Asilomar Conference on , Volume: 2 , 4-7 Nov 2001 Page(s): 1340-1344 vol.2
mag. Davorin Osebik, tei.: (02) 220-7238, e-maii: davorin.osebil<@uni-mb. si izr. prof. dr. Rudoif Babič, tei.: (02) 220-7230, e-mail:
rudoif.babic@uni-mb.si doc. dr. Mitja Soiar, tei.: (02) 220-7232, e-maii: mitja.soiar@uni-mb. si
Univerza v Mariboru Fal<uiteta za eiei<troteiinil<o, računainištvo in informatil<o Smetanova 17, 2000 Maribor tei.: (02) 220-7000, Fax: (02) 251-1178
Prispelo (Arrived): 25.06.2003 Sprejeto (Accepted): 26.08.2003