DR. KOCSIS FERENC:
Gyors eljárások a diszkrét Fouriertranszformáció számítására. I. rész
A digitális jelfeldolgozás egyik legfontosabb műveletének, a diszkrét Fourier-transzformációnak (DFT) az elvégzésére szolgáló gyors eljárások keresését tűztük ki célul egy gyakorlatban is felmerülő feladat kapcsán. A D F T számítási bonyolultságának a mérésére a szüksé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 korlátozott mértékben alkalmas, műveletigénye 0(N2). A jelfeldolgozási frekvencia növelése érdekében a szorzások számát algoritmikus eszkö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 DFT többdimenziós transzformációvá alakítható. A fokozatos részekre osztás lehetőségeinek kimerítése után a DFT 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éktétel felhasználásával O(N) szorzásigényű algoritmus származtatható. Röviden összefoglaljuk a periodikus konvolúcióra való visszavezetéssel számítható kis pontszámú, optimális (N = 2, 3, 4, 5, 7, 8, 9 és 16) DFT 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 (WFTA). Utóbbi szorzásigénye 0(N). Végül elemezzük az egyes algoritmusokat a gyakorlati megvalósítás szempontjából.