193443. lajstromszámú szabadalom • Elrendezés nagysebességű aritmetikai műveletek elvégzésére,előnyösen különböző információs blokkhosszúságú gyors fourier transzformáció,valamint digitális szűrés esetén
1 193443 A találmány tárgya olyan elrendezés, melynek segítségével nagy sebességű aritmetikai műveleteket lehet elvégezni és úgy kialakítani, hogy különböző blokkhosszűságú adattömbök esetén a gyors Fourier transzformáció számítása különösen kedvezően alakul. Mint ismeretes a Fourier transzformáció igen elterjedt eljárás időben lejátszódó folyamatok frekvencia tartománybeli vizsgálatára. Ezeket a vizsgálatokat az esetek döntő többségében digitálisan, különböző számítási teljesítményű számítógépek segítségével végzik. A Fourier transzformációt általános esetben az alábbi kifejezés írja le: X(f) = <’J°x(t) e~Juíidt Ezesetben az x(t) folytonos függvény. Ez a kifejezés a gyakorlati felhasználásra alkalmatlan. A digitális technika alkalmazása esetén az időbeli folyamatokkal általában egyenlő időközönként mintát vesznek, azt digitalizálják, és ebből áll elő egy, számunkra használható különböző blokkhosszúságú adattömb. A mintavételezésnél a Nyquist szabályt be kell tartani a transzformálhatóság érdekében. A transzformálhatóság érdekében ezt a mintaregisztrátumot úgy tekintjük, mintha időben periodikus lenne, így matematikai értelembe véve is alkalmassá válik a Fourier transzformáció elvégzésére. A diszkrét Fourier transzformációt az X*=S xr(n), DxO TM alapján lehet elvégezni, ahol k a k-ik frekvencia komponens és Xk az r-ik minta a regisztrátumban. Ezeknek a műveleteknek az elvégzése N2 számú szorzást és N2 számú összeadást kell végezni. Két amerikai matematikus Cooley és Tukey 1965-ben olyan eljárást publikált, /„An Algorithm for the Machine Calculation of Complex Fourier Series". Math. Computation, Vol. 19. pp. 297-301 Apr. 1965/, amely lehetővé teszi, hogy a DFT-ben meglévő redundanciát redukálják, így lényegesen kevesebb művelet szükséges a transzformáció elvégzéséhez. Az eljárás azon alapszik, hogy a mintaregisztrátum páros és páratlan elemeit szétválasztják, és e_j2nK==u^ahol k=0, 1, 2, .... N-l és W"=-Wk + N2, ahol k=0, 1, ... (N/2)-1 így a fenti kifejezések felhasználásával vk k WAH “ x (2n ) WN/t +WN X _V--Zj fl-O H-o (2n + l)W^, k=0, 1....N-1 Az egyenletet átalakítva X*=Xe(k) + W* X„(k), K=0, 1,.... (N/2)-l X*+N/2=Xe(k) - W*X0(k), k=0, 1, (N/2) -1 2 ahol az Xe (k) a páros sorszámú az X0(k) a páratlan sorszámú eleme a tömbnek. így a transzformáció első N/2 DFT műveletből áll. Az eredmények további páros, páratlan szétvá- 5 logatásával kételemű DFT műveletekre lehet a gyors Fourier transzformációt szétbontani. Az elemi művelet folyamatát az 1. ábra mutatja. Nyolc elemre kidolgozott műveletsor elvi folyamat ábráját a 2. ábra mutatja. Az ábrá- 1 3 ból kitűnik, hogy a gyors Fourier transzformáció elemi műveletsora egy komplex szorzásból, valamint négy összeadás-kivonás műveletből áll. A fentebb említett műveletsor elvégzésére sok megoldás létezik, ennek egy példája a 15 1.330.700 számú US szabadalmi leírásban található, mely olyan számítóegységet ír le, amelyben a transzformálandó adattömböket szétválasztják valós és képzetes részre, majd az adatok a műveletvégző egységbe kerültek, 20 amely két külön számítógépegységből, egy közös komplex szorzóegységből, valamint a trigonometrikus függvényeket előállító generátorból áll. A számítás' közbeni részeredmények tárolására, valamint a megfelelő indexű 25 elemek előállítására soros hozzáférésű léptető regisztereket használnak. Az említett elrendezés szekvenciális tárolói miatt az adott kialakításban alkalmatlan változó blokkhosszúságú adattömbök transzformációjára. Az in- 30 verz Fourier transzformáció számítása ebben a változatban nem kivihető. A szekvenciális tárolókhoz történő soros hozzáférés nem biztosít megfelelően nagy aritmetikai sebességet. A találmánnyal célunk, hogy a fentiekben 35 vázolt valamennyi nehézség egyidejű kiküszöbölése és olyan elrendezés létrehozása, amellyel nagy sebességgel végezhető gyors Fourier transzformáció, tetszőleges ablakfüggvénnyel történő műveletvégzés különböző 40 hosszúságú adattömbök esetén. A találmánnyal megoldandó feladat ennek megfelelően olyan elrendezés kialakítása, amely a legmesszebbmenőkig kihasználja az elektronikus eszközök sebességét annak ér- 45 dekében, hogy minimális elemszámmal, nagysebességgel lehessen aritmetikai műveleteket végezni, különös tekintettel a gyors Fourier transzformációnál fellépő követelményekre. E0 A találmány alapija az a felismerés, hogy amennyiben egyidejűleg két memóriát használunk az egyiket olvasásra címezzük, míg a másikat pedig írásra, abban az esetben az íróolvasó ciklus műveletvégzés ideje felére csök- E5 ken. A találmány szerinti elrendezés egy olyan ismert elrendezés továbbfejlesztése, melynek első belső adat vezetékköteggel és második belső adat vezetékköteggel összekötött átmenő neti tároló egysége és címgeneráló egysége van. Továbbá az első belső adatt vezetékkötegre kapcsolódó koefficiens memóriája, a koefficiens memória bemeneteire első vezérlő vezetékkötegen, a tároló egység bemeneteire második vezérlő vezetékkötegen, a műveletvégző egység bemeneteire a harmadik vezérlő ve-2
