Gyors eljárások a diszkrét Fouriertranszformáció számítására. I. rész D R . KOCSIS F E R E N C Budapesti Műszaki Egyetem H í r a d á s t e c h n i k a i Elektronika Intézet
ÖSSZBFOGLAXAS
DR. KOCSIS
A digitális jelfeldolgozás egyik legfontosabb műveletének, a diszkrét Fourier-transzformációnak ( D F T ) az elvégzésére szolgáló gyors el járások keresését tűztük ki célul egy gyakorlatban is felmerülő fel adat kapcsán. A D F T számítási bonyolultságának a mérésére a szük séges valós szorzások számát választva, összefüggést származtattunk a kötött idejű (real-time) jelfeldolgozás maximális frekvenciájának a valós szorzások száma függvényében történő meghatározására. A közvetlen Mértékelés kötött idejű feladatok megoldására csak kor látozott mértékben alkalmas, műveletigénye 0 ( N ) . A jelfeldolgozási frekvencia növelése érdekében a szorzások számát algoritmikus esz közökkel próbáltuk csökkenteni. A fokozatos részekre osztással a műveletigény 0(N log iV)-re csökkent. A transzformáció pontszámá ra tett bizonyos feltevések esetén (egymáshoz relatív prím számok szorzatára bontható) az egydimenziós D F T többdimenziós transzfor mációvá alakítható. A fokozatos részekre osztás lehetőségeinek ki merítése után a D F T számítását ekvivalens módon más feladat megoldására próbáltuk visszavezetni. Ha a pontszám N=2, 4, p, p" vagy 2p" (p páratlan prím) alakú, akkor a D F T számítása ekvivalens a periodikus konvolúció meghatározásával. A lineáris és a periodikus konvolúció kiértékelésére a polinomokra vonatkozó kínai maradék tétel felhasználásával O(N) szorzásigényű algoritmus származtat ható. Röviden összefoglaljuk a periodikus konvolúcióra való vissza vezetéssel számítható kis pontszámú, optimális (N = 2, 3, 4, 5, 7, 8, 9 és 16) D F T modulokat. Nagyobb pontszámú transzformációk számí tásához a kis pontszámú modulok összekombinálhatók a Good-algoritmussal, 111. a Winograd-eljárással ( W F T A ) . Utóbbi szorzásigénye 0(N). Végül elemezzük az egyes algoritmusokat a gyakorlati meg valósítás szempontjából. 2
FERENC
1975-ben szerzett villa mosmérnöki diplomát a BME Villamosmérnöki Karán, majd a Távköz lési Kutató Intézetben kezdett dolgozni. Egye temi doktori értekezését 1978-ban védte meg. 1983 szeptembere óta a BME
HEI-ben dolgozik tudo mányos ösztöndíjasként, ahol a digitális jelfeldol gozás és jelszintézis algo ritmikus kérdéseivel fog lalkozik. Szakmai érdek lődési köre: rendszer technika, digitális jelfel dolgozás, számítástech nika, algoritmusok el mélete.
N
W
,20,-1)
a#f-iXw-i) transzformációs m á t r i x , X = [ X ( 0 ) , X ( l ) , X(TV—1)] a transzformált értékek vektora és x = [ a ; (0), x(l) . . . , x(n — 1)] a kiindulási ponthalmazt leíró vektor. X és x elemei általános esetben komplexek is lehetnek. Egy, a műszaki gyakorlatban felmerülő feladat k a p c s á n egységes keretbe foglaljuk a D F T gyors meghatározására kidolgozott eljárásokat ([5], [8], [11], [13], [23], [28]). A lényeges pontokat a mérnöki gyakorlat követelményeinek figyelembe vételével rövid levezetésekkel t á m a s z t j u k alá. Kifejezést szár maztatunk D F T felhasználásával történő, k ö t ö t t idejű jelfeldolgozási feladatok (pl. spektrumanalízis) maximális sávszélessége (a maximális jelfeldolgozási frekvencia) és a D F T kiszámításához szükséges valós szorzások száma k ö z t i összefüggés leírására, majd an nak felhasználásával elvégezzük az egyes D F T algo ritmusok összehasonlító értékelését. r
r
1. Bevezetés
T
A digitális jelfeldolgozásban k ö z p o n t i szerepet j á t szik az TV elemmel leírható (véges vagy periodikus) számsorozathoz rendelt Fourier-spektrumot N egy m á s t ó l egyenlő távolságú pontban vett m i n t á k k a l megadó diszkrét Fourier-transzformált ( D F T ) . De finíció szerint véges, vagy periodikus sorozat egy dimenziós diszkrét Fourier-transzformáltján (1—D D F T ) az (l-l)
X^^Wv*
0-sft=síV-- 1
<= - (5r) j
, , [
e
!=0
sorozatot értjük. {x(i)} a szóban forgó számsorozat, vagy annak egy periódusa, {X(k)} a transzformált értékek sorozata. Periodikus esetben TV a jel egy periódusra eső pontjainak a száma, míg véges soro z a t n á l TV a sorozat pontjainak a száma. A D F T lineáris transzformáció, a l a p v e t ő tulajdon ságainak elemzése m e g t a l á l h a t ó p l . a [9], [10], [21] m ű v e k b e n . A transzformáció pontsorozatot képez le azonos s z á m ú pontot t a r t a l m a z ó pontsorozatba: {x(i)}-+{X(k)}. Mátrixalakban: (1-2)
X=W x ,
ahol
Beérkezett: 1984. V I . 6. ( « )
W
A
T
A t o v á b b i a k b a n szükségünk lesz az egyes D F T számítási eljárások értékelésénél valamilyen mérték re, amely alapján az egyes algoritmusok egységes alapon összehasonlíthatók, értékelhetők. A gyakorlati alkalmazások szempontjából egyik döntő tényező a D F T kiszámításához szükséges i d ő : sok feladatban ez korlátozza az elérhető maximális jelfeldolgozási frekvenciát. A jelenlegi á r a m k ö r i technológiák és ismeretek mellett a D F T kiértékelése során a szorzás a legidőigényesebb művelet. Feltételezve, hogy a szükséges szorzások ideje mellett az egyéb műveletek (összeadások, kivonások, léptetések, a d a t m o z g a t á sok stb.) ideje elhanyagolható, a következőkben egy D F T eljárás számítási bonyolultságán a szükséges valós szorzások /(TV) s z á m á t értjük. Híradástechnika
544
XXXV.
évfolyam 1984. 12. szám
Tekintsük a k ö v e t k e z ő problémát (amely összetett digitális jelfeldolgozási feladatok része is lehet): valamely folytonos jelből egymást követően t idő intervallumonként N pontot t a r t a l m a z ó m i n t á k a t veszünk, és képezzük ezen sorozatok diszkrét Fouriertranszformáltjait. A kapott spektrumon esetleg t o v á b b i jelfeldolgozási műveleteket k í v á n u n k végez ni. A k ö t ö t t idejű (real-time) feldolgozás feltétele, hogy az N ponthoz rendelt spektrumot legfeljebb t idő alatt elő tudjuk állítani (különben az egyes soro zatok feldolgozásának m á r az első lépése is átlapolódna a következő részsorozat feldolgozási inter vallumára). Ha egyetlen valós szorzás elvégzéséhez 'szorzás időre van szükség, akkor az átlapolódás h a t á r helyzetében (a D F T számításához szükséges idő éppen a következő mintasorozat vételéhez szükséges t idő): s
konvolúciós eljárások felhasználásával t ö r t é n ő meg h a t á r o z á s á v a l . Az 1—D és n—D D F T e g y ü t t h a t ó m á t r i x a i k ö z t i összefüggés felhasználásával kétféle módszert (a Good-eljárás és a Wínograd-algoritmus) mutatunk be nagyobb p o n t s z á m ú D F T kisebb pont számú transzformáltakból t ö r t é n ő előállítására. Végül a szükséges műveletszám alapján röviden összehason lítjuk az ismertetett algoritmusokat, értékeljük az eredményeket.
s
s
(1-3)
's
mint
N /maxiéi iaxjel
r^.f
m a x j e l
növelésé
a Szorzás értékének csökkentése, ami új á r a m körök, technológiák kidolgozását jelenti;
— az NJf(N) h á n y a d o s értékének növelése. Az egyik lehetőség N (a p o n t s z á m ) csökkentése. Sok esetben azonban a p o n t s z á m értékét m á s követelmények (pl. felbontóképesség) h a t á r o z zák meg. E m i a t t j á r h a t ó ú t k é n t elsősorban f(N) értékének a csökkentése marad. A t o v á b b i a k b a n algoritmikus eszközökkel próbál j u k f(N) értékét csökkenteni. A vizsgálatok során azonban meghatározzuk a D F T számításához szük séges összeadások s z á m á t is. A dolgozat h á r o m részből áll, irodalomjegyzék azonban csak az elsőhöz kapcsolódik. A t ö b b i rész ben levő hivatkozások az első részbeli irodalomjegy zék sorszámai szerintiek. A jelen első részben először az ( l - l ) definíció sze r i n t i összeg közvetlen kiértékelésével próbálkozunk. Ezt követi az algoritmuselméletben gyakran használt fokozatos részekre osztás (divide and conquer) elvé nek alkalmazása. A részekre osztás k o r l á t a i n a k fel mérése u t á n a második részben m á s ú t o n kísérlete zünk : az eredetileg k i t ű z ö t t feladatot olyan m á s fel a d a t t á kíséreljük meg á t a l a k í t a n i ekvivalens módon, amelynek megoldására m á r ismert h a t é k o n y eljárás. K i m u t a t h a t ó , hogy bizonyos feltételek teljesülése esetén az egydimenziós (1 —D) D F T többdimenziós (n —D) DFT-be a l a k í t h a t ó á t . A számelmélet ered ményeinek felhasználásával egyes esetekben a D F T számítása periodikus konvolúció kiértékelésére vezet hető vissza, amely elvégzésére a polinomok elméleté nek eredményei alapján a d h a t ó igen h a t é k o n y algo ritmus. A harmadik rész foglalkozik a D F T gyors Híradástechnika
XXXV.
N-l
(2-1)
X(k)=x(0)+2
évfolyam 1984. 12. szám
x(i)e- [-N) ,
l
=
Í=I
=*(0)+2
szorzás •f(N)
Az összefüggésből l á t h a t ó , hogy az / nek k é t útja k í n á l k o z i k : —
A közvetlen kiértékelés műveletigényének becslé séhez alakítsuk á t az alapkifejezést (általános esetben x(i) = a(i) + ]b(i) alakú komplex szám (a és b valósak):
/C^O' 'szorzás •
Az egy pontra eső tJN átlagos feldolgozási idő érté kéből a mintavételi frekvenciára vonatkozó Nyquistk r i t é r i u m ( / a v é t e i = 2-/maxiéi) felhasználásával a maximális, még feldolgozható jelfrekvencia: (1-4)
2. A D F T számítása közvetlen kiértékeléssel
W O + M O ) (cos(~j
fti-j sin
(^J Aíj.
K é t komplex szám szorzása elvégezhető 4 valós szorzás és 2 valós összeadás felhasználásával. A (2-2) azonosságok alapján azonban elegendő 3 valós szorzás is, aminek á r a az összeadások s z á m á n a k 5-re t ö r t é n ő növekedése: w = a(c + d) (a + ]b)(c + )d) = p + ]q w^=d(a + b) p = w -w w = c(b — a) q = w + w L
(2-2)
x
2
1
A
2
Ekkor a közvetlen számítás műveletigénye f(N) = = 3.(N-íf valós szorzás és A(N)=(5N-3)-(N-í) valós összeadás. A bonyolultságvizsgálatok során szokásos jelölésmóddal: f(N) = 0 ( N ) és A(iV) = 0(AT ). Á l t a l á b a n azt mondjuk, hogy egy / ( N ) függvény 0(g(N)) rendű, ha létezik olyan c állandó, amelyre az f(N)^sc-g(N) összefüggés legfeljebb véges számú érték kivételével minden egész, nem negatív N érték re teljesül. 2
2
N nagyobb értékeire a D F T k o n k r é t meghatározása k ö t ö t t időben igen nagy problémát jelenthet. Az (1-4) kifejezés alapján, gyors szorzóáramkört hasz nálva ( í = 2 0 0 ns) egy tipikus alkalmazásban (Af = 10 ) az / maximális jelfeldolgozási frekven cia é r t é k e : / = 8 3 3 H z , ami a gyakorlati esetek többségébén t ú l kicsi. s z o r z á s
3
m a x i e l
m a x J e l
Az {x(i)} jelsorozat speciális tulajdonságaira vo natkozó előzetes információ ismeretében a közvetlen kiértékelés műveletszáma jelentősen csökkenthető. Ilyen információ lehet p l . az adatok valós volta, az {x(í)} sorozat szimmetrikus stb. K i m u t a t h a t ó azon ban, hogy a szükséges szorzások í(N) száma a lehet séges egyszerűsítések elvégzése u t á n is 0(N ) rendű, csupán a c állandó értéke csökken. Ez azt jelenti, hogy az / , frekvencia értéke csak azonos nagyság renden belül növelhető. 2
m a x j e
545
3. A D F T meghatározása fokozatos részekre osztással 3.1. Számítás a részekre, osztás elvének felhasználásával Az algoritmuselmélet gyakran alkalmazott fogása a kiindulási probléma kisebb méretű részekre t ö r t é n ő felbontása, az ezekhez t a r t o z ó megoldások megkere sése, majd a kapott eredmények összekombinálásával az eredeti feladat megoldásának összeállítása. A módszer gyakran vezet a közvetlen megoldásnál gyor sabb (kisebb műveletigényű) megoldásra különösen akkor, ha a részekre osztásnál az eredeti feladat k i sebb méretű változatai állnak elő. Ezen megoldás t í p u s o k a t „divide-and-conquer" (fokozatos részekre osztás) t í p u s ú algoritmusoknak szokás nevezni. Próbáljuk meg a módszert nagy méretű (nagy pont számú) D F T számítására alkalmazni, azaz t ö b b k i sebb méretű D F T meghatározására visszavezetni. Feltéve, hogy az eredeti D F T N p o n t s z á m a öszszetett szám, a tényezőkre b o n t á s t elvégezve: JV = =N N -.. .-N , ahol az egyes Nj (l==/=sn) t é n y e zőkre azon kívül, hogy egészek, semmilyen meg k ö t é s t nem teszünk. A P=N -N -.. .-N választás sal az ( l - l ) definíciós összefüggésben az indexeket N és P lineáris kombinációjaként kifejezve: V
2
n
2
3
n
1
k=k
i
(3-1)
Ors/í^A^-l Qsft^P-l
+ kP 1
Az indexek m á s felbontása (nemlineáris, nem algeb rai stb.) is elképzelhető, azonban a gyakorlatban leginkább hasznos a (3-1) típusú lineáris összefüggés. A felbontás l á t h a t ó a n kölcsönösen egyértelmű le képezést teremt k-*(k k ) és i—(i i ) között. A defi níciós összefüggésbe h e l y e t t e s í t v e : (3-2)
X(k
2
v
+ k P) = X(k ,
i
1
2
k) =
1
(3-5) ahol
f (N) = 3 N • (Ni + N + ... + N„), 2
N=jjN í=i r
Ha N—afii (a,-, Í>,->1), akkor C^ + ^TSÍV,-, így általában (de nem minden esetben, mint azt majd látni fogjuk) célszerű N értékét a lehető legtöbb tényezőre felbontani, azaz a törzstényezős felbontásn
ból kiindulni. N = JJp** esetén (3-5) alakja: i= l
(3-6)
/(N) = 3 N 2 « P . Í
2
H a AT>4, akkor
1
v
,V!1+
(h>
K
k = 2 ~ k ,+
.. .+k 2°
1
n
rendje
)
esetén
k, = 0, 1
0
z =2"- í„_i + ... + z 2° 1
0
0
i, = 0, 1
n = log N. 2
Az alapösszefüggésbe helyettesítve: X(k , i
l
(3-8)
k
v
i
=2-- - 2
hV
Í2 = 0
N
n
0
x
z
A pontos műveletszám meghatározásánál sok egy szerűsítő tényező is figyelembe vehető. N = 2 esetén a w'x exponenciális tényezővel t ö r t é n ő szorzás sok esetben ± 1 , ± j értékkel való szorzásra redukálódik (triviális szorzások), amit a tényleges számítás során természetesen nem szorzásként veszünk figyelembe. A szorzások nem triviális s z á m á n a k számításához írjuk fel az ( l - l ) definíciós összefüggésben szereplő i és k indexeket kettes számrendszerben (ez minden különösebb feltétel teljesülése nélkül megtehető).
. /2n \
•2
a
2
h=o
P-l
z
n
=l):
A-^J^V [(lr) (^r) H
X(k
a
U P?> i=i
valóban csökkent az f(N) = 0(iV )-hez képest. N — p" esetben (p prím) f ( N ) = 3-JV-logpN, vagyis f(N) = 0(N• log N). A gyakorlatban különösen fontos N=2 esetben f(N) = 0 ( A M o g N). A D F T i l y módon t ö r t é n ő számítását szokás gyors Fourier-transzformációnak ( F F T ) nevezni.
(3-7)
2
(3-3)
£ *ÍPÍ< i=i
2
n
il=0 i = 0
Azonos átalakítások u t á n .(e-i \
Í
í=i
3.2. A nem triviális szorzások számának meghatározása 2 és 4 szerinti faktorizáció
(W,sP-l.
v
gondolatmenetet k ö v e t v e az eredeti D F T végül k i sebb méretű D F T - k számítására vezethető vissza. Az eljárás (n — 1) lépésben ér véget (n a tényezők száma N felbontásában). Az összes valós szorzások s z á m a :
1=0
ft„_i)
=
w) " e
('o> h>
x
lVl=0
A belső összeg csupán p-i k és i függvénye: 2
1
= 0 (3-4) X,(k„ U)= i's?. x(z\, zV>e iw) X értékkészlete N -P = N db értékből áll (valójá ban N elemű kétdimenziós t ö m b az (i k ) indexek kel). Közvetlen kiértékelésnél a szükséges szorzások s z á m a (eltekintve a ^ = 0 esetben lehetséges egysze rűsítéstől) M =3-P -N = 3P-N valós szorzás. A külső összeg belső összegből való s z á m í t á s á n a k lépés száma M = 3N -P = 3N-N valós szorzás. A teljes m ű v e l e t i g é n y : f(N)=M +M =iN-(N +P). Lát h a t ó , hogy a belső összeg valójában egy P-pontos D F T . A tényezőkre bontást folytatva, és az előző -i
1
1
v
2
Behelyettesítve, átrendezve és a minden c egészre érvényes e~ = 1 azonosságot figyelembe v é v e : i2nc
(3-9)
X(V
K-ú=
2
1
1
2
2
1
1
2
1
-p = 0
/o = 0
. p"\ '(^•) "- '"" .
1
•2
!
(io> h> •••>
x
'„-i) ~ e
J
l2
1A0
|
1„-1 = 0
546
Híradástechnika
XXXV.
évfolyam 1984. 12. szám
A legbelső összeg láthatóan N/2 db 2-pontos D F T . Kiértékeléséhez nem szükséges szorzás. Á l t a l á b a n az (n—p)-ik összegben az előző fokozatban keletke zett N db értéket kell szorozni egy exponenciális taggal, amelynek k i t e v ő j e :
csak a forgatásokat leíró exponenciális tagokkal kap csolatosak), a szükséges komplex szorzások s z á m a :
4pJ i6; ^ -ir 3'
M =2
(3-i6)
=
n
l 0
i V
+
amiből:
(- > 3
^)^
10
~
2 n
i ' '-
p P
k
2
(3-17)
A legmagasabb indexű k taggal való szorzás ismét 2-pontos D F T - t jelent, amelynek számításához — mint m á r e m l í t e t t ü k — nincs szükség szorzásra. Az összeg t ö b b i tagjával t ö r t é n ő szorzás forgatást jelent. Az összeg második tagjával (k ) való szorzások k i 2
f(N) = 3M
p
p
™ l o
g
i
N - ^ + l .
Az összeadások s z á m a az előzőekhez adódik: (3-18)
A(N) = 2NXog N+~f(N)
%
67ÍV,
155N
A r
hasonlóan
=
i
esnek, mivel e \ N ) " értéke i _ és k _ lehet séges értékeire +1, i l l . — j . Azon kívül m é g nincs n
=
N
5
p-3
szükség valós szorzásokra, ha í
=0, ill. a
2^ 1=0
összegben az összes k e g y ü t t h a t ó értéke zérus. A z előző fokozatbeli számítások u t á n adódó n-változós eredmény: (3-11) n~p-l(kp-2>
^p-3>
x
• • •»
^0'
l
n-p'
Ín-p-V
• • •' *<))•
A t ö b b i i _ változó ( l < ? s p - 1 ) a k o r á b b i össze gezések során eltűnik, és helyükre a k értékek ( 0 < =s,s
q
s
n
p
p-3
még azok a szorzások, amelyeknél a 2 kft összeg zérus, azaz (p—2) db kj e g y ü t t h a t ó zérus. Ezen fel tételek mellett kifejezés lehetséges értékeinek száma 2 ~ (n — p db í, ( 0 < f < n — p — 1) változó és a k _ változó értékei). Azaz az n — p-ik összegzésben a szükséges komplex szorzások s z á m a : n
p
p+1
2
(3-12)
M,n-p
N 2
-_N
2"-P
+1
2 \
2P- ) 2
A (3-9) összefüggés nyilván csak psr3-ra érvényes, mivel az első k é t összefüggésben csak a D F T - k , i l l . a triviális forgatás szerepel. A z egyes fokozatokbeli szorzások s z á m á t összegezve: (3-13) M
N
=
Ni -. j 3 N =-log 2V~
»
f(N) = 3.M
N
3.3. A fokozatos részekre osztás értelmezése
eredményének
A fokozatos részekre osztás e g y ú t t a l azt is jelentette, hogy az (l-l) definíciós' összefüggésben az i és k indexeket t ö b b indexváltozó lineáris kombinációjára bontottuk. H a t á s a : a kiindulási egydimenziós pont sorozatot t ö b b indexszel elérhető többdimenziós p o n t s o r o z a t t á a l a k í t o t t u k á t , aminek következtében a számításokhoz szükséges adatsorrend eltérhet az eredeti a d a t s o r r e n d t ő l . Ugyanaz áll a transzformált értékeket t a r t a l m a z ó sorozatra is. Következésképp a D F T meghatározásához a hagyományos aritmetikai műveleteken kívül (szorzás, összeadás, kivonás, lép tetés) m á s műveletekre (adatmozgatás) is szükség lehet, amelyek a gyakorlati megvalósítás során eset leg nem elhanyagolhatóak. Léteznek olyan eljárások is, amelyek a fokozatos részekre osztást úgy szerve zik, hogy a számításokhoz az adatok eredeti sorrend jére van szükség, és az eredmény is az eredeti sor rendben képződik. A t o v á b b i a k b a n az átrendezés problémáját azonban részletesen nem vizsgáljuk. A (3—3) összefüggés m á s k é p p is értelmezhető. M i n t arról m á r k o r á b b a n szó volt, a belső összeg N db p-pontos D F T számítását jelenti. Azonos á t alakítás u t á n (3—3) új formája: 1
n
a
ill. komplex szorzásonként 3 valós szorzást és 5 valós összeadást s z á m o l v a : (3-14)
A (3-17) és (3-18) kifejezések csak JV>16 érté kekre érvényesek.
(3-19) ii=0
p-i
3iV 92V = — log N-— + 6.
• 2
2
*0i»
h) ' e
ff)
(2 = 0
A szükséges összeadások s z á m a : fokozatonként N, amihez j ö n a forgatások m i a t t i szorzásokból adódó összeadások s z á m a : (3-15)
A(N) = 2Nlog N 2
+
5/(N)
L á t h a t ó , hogy a külső összeg az e ' szorzötényezőtől eltekintve A -pontos D F T - t definiál, azaz a (3 — 19) kifejezés számításának algoritmusa: 1. N db P-pontos D F T számítása; 2. a kapott N *P=N érték szorzása a megfelelő w v
r
1
1
1
9N , =—log jV 2
15ÍV . 2 ~ + 10. n
Hasonló gondolatmenetet alkalmazva N=A" alakú p o n t s z á m o k r a 4 szerinti faktorizációval (a 4-pontos D F T számírásához sincs szükség szorzásokra, azok Híradástechnika
XXXV.
e értékekkel (0=s z ^ A ^ - l , 0
évfolyam 1984. 12. szám 547
A számítások 2. lépésében szükséges szorzások nél kül az eredetileg 1 - D D F T s z á m í t á s á t 2-D DFT s z á m í t á s á r a lehetne visszavezetni. A szükséges szor zások s z á m a : (3-20)
f(N) = N f(P)
+ P-fiNJ
y
+ N=^-f(P)
+
A kiinduló feltevések szerint P=N -N -...-N , vagyis a fokozatos részekre osztás t o v á b b folytat h a t ó a (3-19) kifejezésben szereplő belső összeg (P-pontos D F T ) felbontásával. A k o r á b b i a k b a n k ö vetett eljárás ismételt alkalmazásával adódik [24]: 2
(3-21)
m = É-S--f
3
n
(n-W.
A felbontási módszerből következik, hogy a foko z a t o n k é n t szükséges korrekciós tagtól eltekintve (2. lépés) lényegében az 1-D D F T n-D DFT-be való á t a l a k í t á s á t kaptuk, azaz az eredeti nagy méretű feladatot v a l ó b a n t ö b b , kisebb m é r e t ű , azonos típusú feladattá sikerült felbontani. A részekre osztást álta l á b a n célszerű prímtényezős alakig elvégezni, b á r egyes esetekben a gyakorlati követelmények más fel b o n t á s a l k a l m a z á s á t tehetik szükségessé. Elemezzük röviden a (3—21) összefüggés jelenté sét. Az első tag jelenti az N XN X • • • XN n — D D F T s z á m í t á s á n a k műveletigényét, ha f(Nj) az Njpontos 1 - D D F T számításigénye. H a f(Nj) = 0(Nj), akkor a (3—5) összefüggés s z á r m a z t a t á s á n á l alkal mazott gondolatmenet kisebb műveletszámra vezet (nem bontjuk fel a (3-3) összefüggés külső összegé ben az exponenciális tagot k é t exponenciális tag szorzatára): n TV X
(3-22)
2
n
f(Nj) = 3 N 5 - /(N) = 2 Á T y+(" - W j=l * y . = 3 ^ ( ^ + 7 ^ + . . . +N ) + (n~í)N. 3 i V
=
n
Ha azonban f(N )~=zO(Nj}, akkor remélhető, hogy a (3-21) a (3-5) egyenlőséggel m e g h a t á r o z o t t m ű v e l e t s z á m n á l kevesebbre vezet. Amennyiben N = 2 , akkor: í
n
(3-23)
f(N) = n2 - f(2) n
+
1
(n-l)2 . n
Mivel /(2) = 0 (X(0) = x(0) + x ( l ) , X ( l ) = x ( 0 ) - x ( l ) ) , (3-24)
f(N = 2") = (n - 1 ) 2 " = A (log N -1) r
2
=
= 0(7V.log A0, 2
mint azt az előzőekben m e g h a t á r o z t u k . n
K i i n d u l v a ismét az N = JJp?
törzstényezős alak
i é i
ból és N é r t é k é t a lehető legtöbb tényezőre bontva: (3-25)
f(N)=7VÍ
f( )+N Pj
{Í
« -1). y
H a N = p (j> prím), akkor f(N)=f(p), azaz a fenti m ó d o n t ö r t é n ő fokozatos részekre osztással nem ér h e t ü n k el e r e d m é n y t (egyébként is kiindulási feltétel volt, hogy N összetett szám). N—p e s e t é n ; (3-26)
548
/(/V=p*) = « p ° - 7 < p ) + ( a - l ) p .
Egyszerű átalakításokkal k i m u t a t h a t ó , hogy N>-4 esetben /(N)«=0(iV ) még akkor is, ha /(p) = 0(p ). (3-25)-ből az f(N) bonyolultsági mérték (valós szorzások száma) csökkentésének k é t kézenfekvő módja adódik. E g y r é s z t visszavezetni az l—D D F 1 számítását valóban n — D D F T m e g h a t á r o z á s á r a : ekkor ugyanis a (3-21) összegben az (n — 1)N alakú második tag elmarad. Ennek feltétele, hogy a szá mítási algoritmus 2. lépésében az exponenciális tag gal való szorzásra (forgatásra) ne legyen szükség. A másik lehetőség az f(pj) értékek csökkentése: p r í m számokra heurisztikus vagy szisztematikus úton olyan algoritmusokat s z á r m a z t a t n i , amelyekre /(p,) < <0(/r;). A t o v á b b i a k b a n megvizsgáljuk, m i a felté tele, hogy az 1 - D D F T n-D DFT-be legyen á t a l a kítható. 2
2
(A cikk ugyanezen folyóirat későbbi számaiban folytatódik.)
IRODALOM [1] Aho, A. V.-Hopcroft, J. E.-Ullmann, J. D.: "The Design and Analysis of Computer Algo ritmus", Addison-Wesley Publishing Company, (1975). [2] Ahmed, N. — Rao, K. R.: "Orthogonal Transforms for Digital Signal Processing", Springer-Verlag, Berlin and New York, (1975). [3] Agarwal, R. C—Burrus, C. S.: "Fast One-Dimensional Convolution by Multidimensional Techniques", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-22, pp. 1 — 10, (1974). [4] Agarwal, R. C — Burrus, C. S.: "Number Theoretic Transforms to Implement Fast Digital Con volution", Proceedings of the I E E E , vol. 63, pp. 550-560, (1975). [5] Agarwal, R. C. — Cooley, J. C.: "New Algorithms for Digital Convolutions", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-25, pp. 392-410, (1977). [6] Agarwal, R. C: " A n In-Place and In-Order W F T A " , ICASSP '83, Boston, pp. 190-193, (1983). [7] Bellman, R.: "Introduction to Mátrix Analysis", McGraw-Hill, New York, (1960). [8] Burrus, C. S.: "Index Mappings for Multidimen sional Formulation of the D F T and Convolu t i o n " , I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-25, pp. 239—242, (1977). [9] Bringham, E. O.: "The Fast Fourier Transform", Prentice-Hall, Englewood Cliffs, New Jersey, (1974). [10] Czebe, L . : „ A diszkrét és a gyors Fourier-transzformáció", Híradástechnika, vol. 32., no. 4., pp. 141-155, (1981). [11] Cooley, 1. W.-Tukey, I. W.: " A n Algorithm for the Machine Calculation of Complex Fourier Series", Mathematics of Computation, vol. 19., pp. 2 9 7 - 3 0 1 , (1965). [12] Good, I. J.: "The Relationship Between Two Fast Fourier Transforms", I E E E Transactions on Computers, C-20, pp. 310-317, (1917). [13] Kolba, D. P.-Parks, I. W.: " A Prime Factor F F T Algorithm Using High-Speed Convolution", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-25, pp. 281—294, (1977). [14] Knuth, D. E.: "The A r t of Computer Programming", vol. 1. "Fundamental Algorithms", és vol. 2. "Seminumerical Algorithms", AddisonWesly, Reading, Massachusetts, (1969). Híradástechnika
XXXV.
évfolyam 1984. 12. szám
[15] Nawab, H. — McClellan, J. H. : A Comparison of W F T A and F F T Programs", Proceedings of Asilomar Conference on Circuits, Systems and Computers, Pacific Grove, California, pp. 613 — 617, (1978). [16] Nawab, H.-McClellan, J. H.: "Bounds on the Minimum Number of Data Transfers in W F T A and F F T Programs", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP27, pp. 394-398, (1979). [17] Niven, I.—Zuckerman, H. S.: "Bevezetés a számelméletbe", Műszaki Könyvkiadó, Buda pest, (1978). [18] Nussbaumer, H. J.—Quandalle, P.: "Comparison of Convolutions and Discrete Fourier Transforms", I B M Journal of Research and Development, vol. 22, pp. 134-144, (1978). [19] Nussbaumer, H. J.—Quandalle, P.: "Fast Compatition of Discrete Fourier Transforms Using Polynominal Transforms", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-27, pp. 1 6 9 - 1 8 1 , (1979). [20] Nussbaumer, H. J.: "Fast Polynominal Trans form Algorithms for Digital Convolution", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-28, pp. 205-215, (1980). [21] Oppenheim, A. V.-Schafer, R. W.: "Digital Signal Processing", Prentice-Hall, Englewood Cliffs, New Jersey, (1975). [22] Rabiner, L . R. — Gold, B.: "Theory and Applica tion of Digital Signal Processing", PrenticeHall, Englewood Cliffs, New Jersey, (1975). [23] Rader, C. M.: "Discrete Fourier Transforms When
Híradástechnika
XXXV.
the Number of Data Samples is Prime", Proceedings of the I E E E , vol. 56., pp. 1107-1108, (1968). [24] Rader, C. M. - McClellan, J. H.: "Number Theory in Digital Signal Processing", Prentice-Hall, Englewood Cliffs, New Jersey, (1979). [25] Silverman, H. F.: " A n Introduction to Programming the Winograd Fourier Transform Algor i t h m ( W F T A ) " , I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-25, pp. 152-165, (1977). [26] Toom, A. L . : "The Complexity of a Scheme of Functional Elements Simulating the Multiplication of Integers", Dokladi Akademii Nauk SSSR, pp. 496-498, (1963). [27] Winograd, S.: "Somé Bilinear Forms Whose Multiplicative Complexity Depends on the Field of Gonstants", Mathematical Systems Theory, vol. 10., pp. 169-180, (1977). [28] Winograd, S.: "On Computing the Discrete Fourier Transform", Mathematics of Computation, vol. 32., pp. 175-199, (1978). [29] Winograd, S.: "Signal Processing and Comple x i t y of Computation", Proceedings of Interna tional Conference on Acoustics, Speech, and Signal Processing, pp. 94—101, (1980). [30] Zohar, S.: " A Prescription of Winograd's Dis crete Fourier Transform Algorithm", I E E E Transactions on Acoustics, Speech, and Signal Processing, ASSP-27, pp. 4 0 9 - 4 2 1 , (1979). [31] Gordos, G. — Takács, Gy.: „Digitális beszédfeldol gozás", Műszaki Könyvkiadó, Budapest, 1983, p. 345.
évfolyam 1984. 12. szám 549
