Cyklomtomická rychlá Fourierova transformace - Cyclotomic fast Fourier transform - Wikipedia

The cyklotomická rychlá Fourierova transformace je typ rychlá Fourierova transformace algoritmus skončil konečná pole.^[1] Tento algoritmus nejprve rozloží DFT na několik kruhových konvolucí a poté odvodí výsledky DFT z výsledků kruhové konvoluce. Při aplikaci na DFT přes ${ displaystyle GF (2 ^ {m})}$, tento algoritmus má velmi nízkou multiplikativní složitost. V praxi, protože obvykle existují efektivní algoritmy pro kruhové konvoluce se specifickými délkami, je tento algoritmus velmi efektivní.^[2]

Pozadí

The diskrétní Fourierova transformace přes konečná pole nachází široké uplatnění při dekódování kódy opravující chyby jako BCH kódy a Reed-Solomon kódy. Zobecněno z komplexní pole diskrétní Fourierova transformace sekvence ${ displaystyle {f_ {i} } _ {0} ^ {N-1}}$ přes konečné pole GF (str^m) je definován jako

${ displaystyle F_ {j} = součet _ {i = 0} ^ {N-1} f_ {i} alpha ^ {ij}, 0 leq j leq N-1,}$

kde ${ displaystyle alpha}$ je N-th primitivní kořen 1 v GF (str^m). Pokud definujeme polynomiální reprezentaci ${ displaystyle {f_ {i} } _ {0} ^ {N-1}}$ tak jako

${ displaystyle f (x) = f_ {0} + f_ {1} x + f_ {2} x ^ {2} + cdots + f_ {N-1} x ^ {N-1} = součet _ { 0} ^ {N-1} f_ {i} x ^ {i},}$

je to snadno vidět ${ displaystyle F_ {j}}$ je prostě ${ displaystyle f ( alpha ^ {j})}$. To znamená, že diskrétní Fourierova transformace sekvence ji převede na problém vyhodnocení polynomu.

Napsáno v maticovém formátu,

${ displaystyle mathbf {F} = left [{ begin {matrix} F_ {0} F_ {1} vdots F_ {N-1} end {matrix}} right] = 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 {matrix}} right] left [{ begin {matrix} f_ {0} f_ {1} vdots f_ {N-1} end {matrix}} right] = { mathcal {F}} mathbf {f}.}$

Přímé vyhodnocení DFT má ${ displaystyle O (N ^ {2})}$ složitost. Rychlé Fourierovy transformace jsou jen efektivní algoritmy vyhodnocující výše uvedený produkt matice-vektor.

Algoritmus

Nejprve definujeme a linearizovaný polynom přes GF (str^m) tak jako

${ displaystyle L (x) = součet _ {i} l_ {i} x ^ {p ^ {i}}, l_ {i} in mathrm {GF} (p ^ {m}).}$

${ displaystyle L (x)}$ se nazývá linearizovaný, protože ${ displaystyle L (x_ {1} + x_ {2}) = L (x_ {1}) + L (x_ {2})}$, který vychází ze skutečnosti, že pro prvky ${ displaystyle x_ {1}, x_ {2} in mathrm {GF} (p ^ {m}),}$${ displaystyle (x_ {1} + x_ {2}) ^ {p} = x_ {1} ^ {p} + x_ {2} ^ {p}.}$

Všimněte si toho ${ displaystyle p}$ je invertibilní modulo ${ displaystyle N}$ protože ${ displaystyle N}$ musí rozdělit pořadí ${ displaystyle p ^ {m} -1}$ multiplikativní skupiny pole ${ displaystyle mathrm {GF} (p ^ {m})}$. Takže prvky ${ displaystyle {0,1,2, ldots, N-1 }}$ lze rozdělit na ${ displaystyle l + 1}$ cyklotomické kosety modulo ${ displaystyle N}$:

${ displaystyle {0 },}$

${ displaystyle {k_ {1}, pk_ {1}, p ^ {2} k_ {1}, ldots, p ^ {m_ {1} -1} k_ {1} },}$

${ displaystyle ldots,}$

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

kde ${ displaystyle k_ {i} = p ^ {m_ {i}} k_ {i} { pmod {N}}}$. Proto lze vstup do Fourierovy transformace přepsat jako

${ displaystyle f (x) = součet _ {i = 0} ^ {l} L_ {i} (x ^ {k_ {i}}), quad L_ {i} (y) = součet _ {t = 0} ^ {m_ {i} -1} y ^ {p ^ {t}} f_ {p ^ {t} k_ {i} { bmod {N}}}.}$

Tímto způsobem je polynomiální reprezentace rozložena na součet lineárních polynomů, a tedy ${ displaystyle F_ {j}}$ je dána

${ displaystyle F_ {j} = f ( alpha ^ {j}) = součet _ {i = 0} ^ {l} L_ {i} ( alpha ^ {jk_ {i}})}$.

Rozšiřuje se ${ displaystyle alpha ^ {jk_ {i}} in mathrm {GF} (p ^ {m_ {i}})}$ na správném základě ${ displaystyle { beta _ {i, 0}, beta _ {i, 1}, ldots, beta _ {i, m_ {i} -1} }}$, my máme ${ displaystyle alpha ^ {jk_ {i}} = součet _ {s = 0} ^ {m_ {i} -1} a_ {ijs} beta _ {i, s}}$ kde ${ displaystyle a_ {ijs} in mathrm {GF} (p)}$a vlastností linearizovaného polynomu ${ displaystyle L_ {i} (x)}$, my máme

${ displaystyle F_ {j} = součet _ {i = 0} ^ {l} součet _ {s = 0} ^ {m_ {i} -1} a_ {ijs} left ( sum _ {t = 0} ^ {m_ {i} -1} beta _ {i, s} ^ {p ^ {t}} f_ {p ^ {t} k_ {i} { bmod {N}}} vpravo)}$

Tuto rovnici lze přepsat do maticové podoby jako ${ displaystyle mathbf {F} = mathbf {AL Pi f}}$, kde ${ displaystyle mathbf {A}}$ je ${ displaystyle N krát N}$ matice nad GF (str), který obsahuje prvky ${ displaystyle a_ {ijs}}$, ${ displaystyle mathbf {L}}$ je bloková diagonální matice a ${ displaystyle mathbf { Pi}}$ je permutační matice přeskupující prvky ${ displaystyle mathbf {f}}$ podle indexu cotomtomomic coset.

Všimněte si, že pokud normální základ ${ displaystyle { gamma _ {i} ^ {p ^ {0}}, gamma _ {i} ^ {p ^ {1}}, cdots, gamma _ {i} ^ {p ^ {m_ {i} -1}} }}$ se používá k rozšíření polních prvků ${ displaystyle mathrm {GF} (p ^ {m_ {i}})}$, i-tý blok ${ displaystyle mathbf {L}}$ darováno:

${ displaystyle mathbf {L} _ {i} = { begin {bmatrix} gamma _ {i} ^ {p ^ {0}} & 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}} end {bmatrix}} }$

což je cirkulační matice. Je dobře známo, že produkt cirkulační matice-vektor lze efektivně vypočítat pomocí závity. Proto jsme úspěšně snížili diskrétní Fourierovu transformaci na krátké konvoluce.

Složitost

Při aplikaci na a charakteristický -2 pole GF (2^m), matice ${ displaystyle mathbf {A}}$ je jen binární matice. Při výpočtu součinu vektoru matice vektoru se používá pouze přidání ${ displaystyle mathrm {A}}$ a ${ displaystyle mathrm {L Pi f}}$. Ukázalo se, že multiplikativní složitost cyklotomického algoritmu je dána vztahem ${ displaystyle O (n ( log _ {2} n) ^ { log _ {2} { frac {3} {2}}})}$a složitost aditiv je dána vztahem ${ displaystyle O (n ^ {2} / ( log _ {2} n) ^ { log _ {2} { frac {8} {3}}})}$.^[2]

Reference