Goode-Thomasův algoritmus

Goode-Thomasův algoritmus je algoritmus pro výpočet rychlé Fourierovy transformace aplikovaný na sekvence, jejichž délka je rovna součinu dvou prvočísel .

Algoritmus Goode-Thomas by neměl být zaměňován s algoritmem Cooley-Tukey , kde dělitelé délky transformace nemusí být coprime. Goode-Thomasův algoritmus je touto podmínkou omezen a také používá složitější schéma reindexace než algoritmus Cooley-Tukey, ale nevyžaduje střední násobení komplexními faktory, a proto je z hlediska výpočtů poněkud jednodušší [1] .

Konstrukce algoritmu

Pro libovolné přirozené číslo, diskrétní Fourierova transformace komplexního vektoru , kde , je komplexní vektor , kde , jehož složky jsou dány vzorcem $n$ $x(j)$ $j=0,\ldots ,n-1$ $X(k)$ $k=0,\ldots ,n-1$

X(k)=\sum \limits _{j=0}^{n-1}x(j)\omega ^{kj},\;k=0,\ldots ,n-1,

kde . ${\displaystyle \omega =e^{-{\frac {2\pi i}{n))))$

Nechat , kde a být coprime. Nechť také a být nové vstupní indexy dané vztahy [2] $n=n_{1}n_{2}$ $n_{1}$ $n_{2}$ $j_{1}$ $j_{2}$

j_{1}=j\ ({\mbox{mod}}\ n_{1}),\ j_{2}=j\ ({\mbox{mod}}\ n_{2}).

Odtud podle čínské věty o zbytku a Bezoutova vztahu vyplývá, že existují celá čísla a taková, $N_1$ $N_2$

j=j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}\ ({\mbox{mod}}\ n)

a Podobně nechť a být nové výstupní indexy dané vztahy $N_{1}n_{1}+N_{2}n_{2}=1.$ $k_{1}$ $k_{2}$

k_{1}=N_{2}k\ ({\mbox{mod}}\ n_{1}),\ k_{2}=N_{1}k\ ({\mbox{mod}}\ n_{2}).

Pak

k=n_{2}k_{1}+n_{1}k_{2}\ ({\mbox{mod}}\ n).

Použití notace

x'(j_{1},j_{2})=x(j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}),

X'(k_{1},k_{2})=X(n_{2}k_{1}+n_{1}k_{2}),

\beta =\omega ^{N_{2}\left(n_{2}\right)^{2)),

\gamma =\omega ^{N_{1}\left(n_{1}\right)^{2)),

původní vzorec má formu

X'(k_{1},k_{2})=\sum \limits _{j_{1}=0}^{n_{1}-1}\sum \limits _{j_{2}= 0}^{n_{2}-1}\beta ^{j_{1}k_{1}}\gamma ^{j_{2}k_{2}}x'(j_{1},j_{2}) ,

to znamená, že došlo k přechodu z jednorozměrné transformace délky na dvourozměrnou transformaci velikosti . Počet násobení a počet sčítání se přitom stal přibližně [3] . $n$ $(n_{1}\times n_{2})$ $n(n_{1}+n_{2})$

Poznámky

↑ Blahut, 1989 , s. 141.
↑ Blahut, 1989 , s. 142.
↑ Blahut, 1989 , s. 143.

Literatura

Blahuth, R. Algoritmy rychlého digitálního zpracování signálu. —M.:Mir, 1989. — 448 s. (Ruština)