Cyklotomiczna szybka transformata Fouriera

Cyklotomiczna szybka transformata Fouriera jest rodzajem algorytmu szybkiej transformacji Fouriera na polach skończonych . Ten algorytm najpierw rozkłada DFT na kilka splotów kołowych, a następnie wyprowadza wyniki DFT z wyników splotów kołowych. Po zastosowaniu do DFT przez $ma$ złożoność W praktyce, ponieważ zwykle istnieją wydajne algorytmy dla splotów kołowych o określonej długości, algorytm ten jest bardzo wydajny.

Tło

Dyskretna transformata Fouriera na polach skończonych znajduje szerokie zastosowanie w dekodowaniu kodów korekcji błędów, takich jak kody BCH i kody Reeda-Solomona . Uogólniona z pola zespolonego dyskretna transformata Fouriera sekwencji ${\ Displaystyle \ {f_ {i} \} _ {0} ^ {N-1}}$ nad polem skończonym GF ( p ^m ) jest zdefiniowany jako

${\ Displaystyle F_ {j} = \ suma _ {i = 0} ^ {N-1} f_ {i} \ alfa ^{ij},0\równik j\równoważnik N-1,}$

gdzie jest $pierwiastkiem$ -tym pierwotnym z 1 w GF ( p ^m ). Jeśli zdefiniujemy reprezentację wielomianową jako ${\ Displaystyle \ {f_ {i} \} _ {0} ^ {N-1}}$

${\ Displaystyle f (x) = f_ {0} + f_ {1}x+f_{2}x^{2}+\cdots +f_{N-1}x^{N-1}=\suma _{0}^{N-1}f_{i}x^ {I},}$

łatwo zauważyć, że $\ displaystyle$ prostu ${j$ } Oznacza to, że dyskretna transformata Fouriera sekwencji przekształca ją w wielomianowy problem oceny.

Zapisane w formacie macierzowym,

${\ Displaystyle \ mathbf {F} = \ lewo [{\ rozpocząć {macierz} F_ {0} \\ F_ {1} \\\ vdots \\ F_ {N-1} \ koniec {macierz}} \ prawo] = \left[{\begin{matrix}\alpha ^{0}&\alpha ^{0}&\cdots &\alpha ^{0}\\\alpha ^{0}&\alpha ^{1}&\cdots &\alpha ^{N-1}\\\vdots &\vdots &\ddots &\vdots \\\alpha ^{0}&\alpha ^{N-1}&\cdots &\alpha ^{(N- 1)(N-1)}\end{macierz}}\right]\left[{\begin{matrix}f_{0}\\f_{1}\\\vdots \\f_{N-1}\end {macierz}}\right]={\mathcal {F}}\mathbf {f} .}$

$_$ DFT _ Szybkie transformaty Fouriera to po prostu wydajne algorytmy oceniające powyższy iloczyn macierzowo-wektorowy.

Algorytm

Najpierw definiujemy zlinearyzowany wielomian nad GF(pm ⁾ jako

${\ Displaystyle L (x) = \ suma _ {i} l_ {i} x ^ {p ^ {i}}, l_ {i} \ w \ operatorname {GF} (p ^ {m}).}$

${\ Displaystyle L (x)}$ nazywa się linearyzowanym, ponieważ ${\ Displaystyle L (x_ {1} + x_ {2} ) = L (x_ {1}) + L (x_ {2})}$ , co wynika z faktu, że dla elementów ${\ Displaystyle x_ {1}, x_ { 2}\in \mathrm {GF} (p^{m}),}$${\ Displaystyle (x_ {1} + x_ {2}) ^ {p} = x_ {1} ^ {p} + x_ {2} ^ {p}.}$

Zauważ, że jest odwracalny modulo , ponieważ $N$$Displaystyle$$}$ musi podzielić rząd multiplikatywnej grupy pola $\ Displaystyle p ^ {m} -1$${\ Displaystyle \ operatorname {GF} (p ^ {m})}$ . Tak więc elementy można podzielić na . $}$$Displaystyle \ {0,1,2, \ ldots, N-1 \$ cyklotomiczne cosets modulo ${\ Displaystyle N}$ :

${\ Displaystyle \ {0 \},}$

${\ Displaystyle \ {k_ {1}, pk_ {1 }, p ^ {2} k_ {1}, \ ldots, p ^ {m_ {1} -1} k_ {1} \},} … , {$

$\ ldots,}$

${\ Displaystyle \ {k_ {l}, pk_ {l}, p ^ {2} k_ {l}, \ ldots, p ^ {m_ {l} }-1}k_{l}\},}$

gdzie ${\ Displaystyle k_ {i} = p ^ {m_ {i}} k_ {i} {\ pmod {N}}}$ . Dlatego dane wejściowe do transformaty Fouriera można przepisać jako

${\ Displaystyle f (x) = \ suma _ {i = 0} ^ {l} L_ {i} (x ^ {k_ {i}}), \ quad L_ {i} (y) = \ suma _ {t =0}^{m_{i}-1}y^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}.}$

W ten sposób reprezentacja wielomianowa jest rozkładana na sumę wielomianów liniowych, a zatem jest dana przez ${\ displaystyle F_ {j}}$

${\ Displaystyle F_ {j} = f (\ alfa ^ {j}) = \ suma _ {i = 0} ^ {l }L_{i}(\alfa ^{jk_{i}})}$ .

${\ Displaystyle \ alfa ^ {jk_ {i}} \ in \ operatorname {GF} (p ^ {m_ {i}})}$ jot odpowiednią podstawą ${\ Displaystyle \ {\ beta _ {i, 0}, \ beta _ {i, 1}, \ ldots, \ beta _ {i, m_ {i} -1} \}}$ , mamy $} a_ {ijs} \ beta _ {i, s}} gdzie za ja jot$$jk_ {i}} = \ suma _ {s = 0} ^ {m_ {i$$Displaystyle a_ {ijs} \ w \ operatorname {GF} (p)}$ s i przez właściwość zlinearyzowanego wielomianu mamy ${\ Displaystyle L_ {i} (x)}$

${j} = \ suma _{i=0}^{l}\suma _{s=0}^{m_{i}-1}a_{ijs}\left(\suma _{t=0}^{m_{i}-1 }\beta _{i,s}^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}\right)}$

${\ Displaystyle \ mathbf {F} = \ mathbf {AL \ Pi f$ zapisać w postaci macierzowej jako , gdzie jest $\$$}$$}$$}$ Displaystyle \ mathbf { blokową macierzą diagonalną $\ mathbf {\ Pi}}$${ \$$displaystyle$ jest macierzą permutacji przegrupowującą elementy z cyklotomicznym indeksem coset.

Zauważ, że jeśli normalna podstawa ${\ Displaystyle \ {\ gamma _ {i} ^ {p ^ {0}}, \ gamma _ { i}^{p^{1}},\cdots ,\gamma _{i}^{p^{m_{i}-1}}\}} służy do rozszerzania$ elementów pola ${\ Displaystyle \ operatorname {GF} (p ^ {m_ {i}})}$ i-ty blok ${\ Displaystyle \ mathbf {L}}$ jest określony przez: L { \ Displaystyle \ mathbf {L}}

${\ Displaystyle \ mathbf {L} _ {i} = {\ zacząć {bmatrix} \ gamma _ {i} ^ {p ^ {0}} i \ gamma _ {i} ^ {p ^ {1 }}&\cdots &\gamma _{i}^{p^{m_{i}-1}}\\\gamma _{i}^{p^{1}}&\gamma _{i}^{ p^{2}}&\cdots &\gamma _{i}^{p^{0}}\\\vdots &\vdots &\ddots &\vdots \\\gamma _{i}^{p^{ m_{i}-1}}&\gamma _{i}^{p^{0}}&\cdots &\gamma _{i}^{p^{m_{i}-2}}\\\koniec {bmacierz}}}$

która jest macierzą cyrkulacyjną . Powszechnie wiadomo, że krążący iloczyn macierz-wektor można skutecznie obliczyć za pomocą splotów . Dlatego z powodzeniem redukujemy dyskretną transformatę Fouriera do krótkich splotów.

Złożoność

$zastosowaniu$ do charakterystycznego pola -2 GF (2 ^m macierz jest po prostu macierzą binarną. Przy obliczaniu iloczynu macierzowo-wektorowego używane jest tylko dodawanie $A}}$$}$ \ . Wykazano, że multiplikatywna złożoność algorytmu cyklotomicznego jest dana przez ${\ Displaystyle O (n (\ log _ {2} n) ^ {\ log _ {2} {\ Frac {3} {2}}})}$ , a addytywna złożoność jest dana przez ${\ Displaystyle O (n ^ {2) }/(\log _{2}n)^{\log _{2}{\frac {8}{3}}})}$ .