Radix-4 Fast kosinusne transformacije

EDAboard.com Forum Index -> Digital Signal Processing -> Radix-4 Fast kosinusne transformacije

Avtor

Message

mendozaulises

Joined: 08 Mar 2006
Posts: 58
S pomočjo: 7

17. marec 2006 19:55 radix-4

Jaz sem poskušal izvesti 1024-DCT točko na FPGA. Doslej sem le ugotovila Radix-2 v decimiranega Frequency algoritmov, vendar me zanima Radix-4 algoritmi. Ne želim uporabiti FFT pristop. Iščem algoritme razvite neposredno za DCT-II.
Can someone help me?

S spoštovanjem,

Nazaj na vrh

Google
AdSense
Google Adsense

17. marec 2006 19:55 Oglasi

Nazaj na vrh

mimomod

Joined: 25. januar 2006
Posts: 109
S pomočjo: 15

17. marec 2006 21:45 radix4 DCT

Hi mendozaulises,

kolikor jaz vem, FFT je algoritem za izračun transformacije (DFT, Discrete sine preoblikovati, Diskretna kosinusna transformacija, transformacija Hartley, etc) hitreje, kot če uporabimo formulo original omenjenega preoblikovanje.

Pravzaprav v mnogih učbenikov, na primer "Znotraj črne skrinjice FFT - serijska in vzporedna hitra Fourierjeva transformacija algoritmi 2000 - Chu, Eleanor Chin-Hwa - CRC Press", ki sem prenesete EDA (?) Za druge povezave v internet, glejte fast Diskretna kosinusna transformacija z uporabo FFT.

Če povzamemo, naloga računalništvo DCT N-1 realnih podatkih postavke lahko
dosežete tako, računalništvo pravi DFT dolžine 2N, ki jih je mogoče izvajati
FFT algoritem, posebej prilagojeno realnih podatkov.

V primeru radix-2 in radix-4 (ali drugih radix, na primer radix-3), to je samo atomska enota v določenem algoritmu FFT. To pomeni, da je za radix-2 FFT algoritem, problem (v vašem primeru 1024 vzorcev) na dosegu roke, dokler se razgradi na določeni stopnji algoritma samo v kakršnih 2 posameznih točkah (vzorcev), o njihovi obdelavi skupaj. To je srce algoritma FFT, kar si razdeliti napad problem na manjše enote za zmanjšanje izračun obremenitve.

V radix je 4-FFT algoritem, smo problem razgradi v atomski enoti 4 vzorci, itd kolikor jaz vem, najbolj učinkovita FFT algoritem, je eden z radix-2. Toda v nekaterih primerih ljudje ne potrebujejo drugih radix za napad problem. Na primer, če je število vzorcev, ki se obdelujejo, je moč 3, nato pa ljudje potrebujejo radix-3 FFT algoritem. Vendar pa lahko do zdaj nisem povsem prepričan, zakaj ljudje še vedno uporabljajo radix-4 FFT, ker dejansko je manj učinkovit od radix-2 FFT, poleg tega pa radix-4 FFT je treba poenostaviti v 2 radix-2 FFT.

Nisem povsem prepričan, kaj je vaš cilj v vaš design. Ampak če je za hitrost, potem radix-2 FFT algoritem, je eden ki jih potrebujete za početje DCT.

najboljši

Nazaj na vrh

mendozaulises

Joined: 08 Mar 2006
Posts: 58
S pomočjo: 7

20. marec 2006 18:34 radix 4 DCT

Hvala mimomod,
Iščem Radix-4 algoritmi, ker pri čemer je N močjo štirih, Radix-4 algoritmi so hitrejši od radix-2 algoritmi. To je samo, da so bolj resourceses potrebni za njihovo izvajanje. Iščem algoritma razvite neposredno, saj z uporabo FFT za izračun DCT uporablja več sredstev kot z neposredno hiter algoritem.
Trenutno delam na Radix-2 algoritem, ki jih uporablja le 2 in 3 krovne seštevalnikov za izračun 1024-point transformacija. Vendar pa ta algoritem zahteva 10 metulj postopka in 9. rekombinacija fazah.
Če se uporablja Radix-4 FFT, da je bil že razvit, bi jaz šele potreba 5 metulj stopnjah 1 in luščenje stopnji, bi to povečalo hitrost za najmanj dvakrat, vendar se uporablja tudi 3-krat toliko sredstev, kot sem trenutno algoritem uporabljate. To zaradi namišljenih pogoji, ki jih je treba upravljati.

Iščem non-FFT Fast algoritem, ki porabi manj sredstev kot FFT pristop, da pa je hitrejši od trenutnega algoritma rabim.

Hvala za vašo pomoč.

Dodano po 7 minutah:

Pozabil sem, Radix-2 Algoritem sem trenutno pripravlja, je opisana v priloženem dokumentu.
Hočem vedeti, da je nekdo pozna razvita radix-4 algoritem za računalništvo DCT. To primerjati prednosti in slabosti vsakega algoritma, kot so sredstva, ki jih uporabljajo, čas za izračun enotnega 1024-point transformacija, itd

Oprostite, toda morate prijavo na ogled te priloge

Nazaj na vrh

mimomod

Joined: 25. januar 2006
Posts: 109
S pomočjo: 15

21. marec 2006 14:33 radix-4 FFT algoritem

Hi mendozaulises,

ja, si prav in sem bil krivičen. Po moje kopanje učbenika, dejansko radix-4 algoritem je bolj učinkovito kot radix-2 algoritem, saj FFT je moč 4.

Tukaj je odstavek iz enega od mojih texbook:

Število množenja v IFFT se lahko zmanjša še z uporabo radix-4 algoritem. Ta tehnika izkoristi dejstvo, da je v štirih točk IFFT, obstajajo samo množenja, ki ga (1, j -1,-j), ki dejansko ni treba izvajati s polno multiplikacijski, ampak ga enostavno dodajanje ali odštevanje in stikalo za resnične in namišljene dele v primeru množenja, ki ga j ali-j. V radix-4 algoritem, preoblikovati je razdeljeno na več nepomembnih teh štirih točk transformacije, in non-trivial množenja je le, da je treba opraviti med fazah teh fourpoint transformacije. Na ta način, N-točke FFT z radix-4 algoritem zahteva le, (3 / Hladen

N (log_2 (N-2)) kompleks razmnožitvah ali fazo vrtenja in Nlog_2 (N) kompleks dodatki. Za 64-point FFT, na primer, to pomeni 96 rotacije in 384 dodatke, ali 1,5 in 6 rotacije in dopolnitve na vzorec, respectively.

najboljši

Nazaj na vrh