사이클로토믹 고속 푸리에 변환

사이클로토믹 고속 푸리에 변환은 유한한 분야에 걸친 고속 푸리에 변환 알고리즘의 일종이다.^[1]이 알고리즘은 먼저 DFT를 몇 개의 순환 경련으로 분해한 다음 순환 경련 결과에서 DFT 결과를 도출한다.$G{\displaystyle }$ ${\displaystyle F}$( ${\displaystyle 2^{}}$ m${\displaystyle {}^{}}$) ${\displaystyle GF(2^{m})}$를 통한 DFT에 적용할 때 이 알고리즘은 승법 복잡성이 매우 낮다$.$실제로 특정 길이의 순환 경련을 위한 효율적인 알고리즘이 일반적으로 존재하기 때문에 이 알고리즘은 매우 효율적이다.^[2]

배경

유한 분야에 걸친 이산 푸리에 변환은 BCH 코드와 Reed-Solomon 코드와 같은 오류 수정 코드의 디코딩에 광범위하게 적용된다는 것을 발견한다.복합 필드에서 일반화된 경우 유한 필드 GF(p^m)에$$ 걸쳐 시퀀스${\displaystyle }${${\displaystyle {}_{}}$ ${\displaystyle i_{}{}_{}^{}}$ 0 ${\displaystyle {}_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\$}의$$이산 푸리에 변환은 다음과 같이 정의된다.

${\displaystyle F_{j}=\sum _{i=0}^{N-1}f_{i}\알파 ^{ij},0\leq j\leq N-1,}$

여기서 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$은(는) GF(p^m) 1의 N번째 원시 루트다.$\{{\displaystyle {}_{}}$ ${\displaystyle i_{}{}_{}^{}}$} 0 ${\displaystyle {}_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\$의 다항식 표현을 다음과$$ 같이 정의하면

${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{{{N-1}x^{N-1}=\sum _{0}^{N-1}f_{i}x^{i}}}}}}}}}}}}}}}$

$F{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$가 단순히$$ ${\displaystyle {}^{}}$ ($\alpha j{\displaystyle {}^{}}$)${\displaystyle }${\$displaystyle f(\alpha ^{j})$인 것을 쉽게 알 수 있다$.$즉, 시퀀스의 이산 푸리에 변환은 그것을 다항식 평가 문제로 변환시킨다.

매트릭스 형식으로 작성,

${\displaystyle \mathbf {F} =\왼쪽[{\begin{matrix}F_{0}\\F_{1}\\\vdots}\right]=\left[{\begin{매트릭스}\alpha ^{0}일 경우&\alpha ^{0}일 경우&\cdots &,\alpha ^{0}일 경우\\\alpha ^{0}일 경우&\alpha ^{1}&\cdots &,\alpha ^{N-1}\\\vdots &, \vdots &, \ddots &, \vdots ^{0}일 경우 및 \\\alpha,\alpha ^{N-1}&\cdots &,\alpha ^{(N-1)(N-1)}\end{매트릭스}}\right]\left-LSB-{\begin{행렬}f_{0}\\f_{\\F_{N-1}\end{매트릭스}.1}\\\vdots \\f_{N-1}\end{매트릭스}}\right-RSB-={\mathcal{F}\mathbf {f} .}$

DFT의 직접 $평가$에는 O${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\디스플레이 스타일$ O$(N^{2})$ 복잡성이$$ 있다.빠른 푸리에 변환은 위의 매트릭스 벡터 제품을 평가하는 효율적인 알고리즘일 뿐이다.

알고리즘.

먼저 GF(p^m)에 대한 선형화된 다항식을 다음과 같이 정의한다.

${\displaystyle L(x)=\sum _{i}l_{i}x^{p^{i},l_{i}\in \mathrm {GF}(p^{m})}$

${\displaystyle L(x)}$ is called linearized because ${\displaystyle L(x_{1}+x_{2})=L(x_{1})+L(x_{2})}$, which comes from the fact that for elements ${\displaystyle x_{1},x_{2}\in \mathrm {GF} (p^{m}),}$${\displaystyle (x_1+x_2{)}^{}}$$displaystyle (x_{1$$$$}}^{p}}}$

Notice that ${\displaystyle p}$ is invertible modulo ${\displaystyle N}$ because ${\displaystyle N}$ must divide the order ${\displaystyle p^{m}-1}$ of the multiplicative group of the field ${\displaystyle \mathrm {GF} (p^{m})}$. So, the elements ${\dis$$Playstyle \{0,1,2,\ldots ,N-1\}$은(는) ${\displaystyle \mathrm{l}}$+ 1 ${\displaystyle l+1}$사이클로토믹$$ 코스메틱 코스메틱 $모듈$로 N ${\displaystyle$ N$}$로 분할할 수 있다$$$.$

${\displaystyle \{0\}}$

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

$\displaystyle \ldots ,}$

${\displaystyle \{k_{l},p^{2}k_{l},\dots,p^{m_{l}-1}k_{l}\}}$

여기서 $k{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {m{}_{}}^{}}$ ${\displaystyle {i_{}}^{}}$ ${\displaystyle i_{}}$ i${\displaystyle {}_{}}$(${\displaystyle \mathrm{mod}}$ ${\displaystyle N}$) ${\$따라서 푸리에 변환에 대한 입력은 다음과 같이 다시 쓸 수 있다.

${\displaystyle f(x)=\sum _{i=0}^{l_{i})(x^{k_{i}}),\quad L_{i}(y)=\sum _{t=0}^{m_{i}-1}y^{p^{p^{t}k_{n}{bmod}}}}}}}}}}}}}}}}}}}}}}}}}}}}}.}$

이렇게 해서 다항식 표현은 선형 다항식의 합으로 분해되어 $F{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$가 주어진다$$.

${\displaystyle {}_{}\underset{}{\overset{}{F}}}$ ${\displaystyle j_{}}$= ${\displaystyle f}$(${\displaystyle {\alpha j}^{}}$)${\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= 0 ${\displaystyle \underset{}{\overset{}{\mathrm{L}}}}$ ${\displaystyle i_{}}$(${\displaystyle {\alpha j}^{}}$ ${\displaystyle {k_{}}^{}}$ i${\displaystyle {{}_{}}^{}}$) ${\displaystyle F_{j}=f(\alpha ^{j}}=\sum _{i=0}^{l}L_{i}(\alpha ^{jk_{i$

Expanding ${\displaystyle \alpha ^{jk_{i}}\in \mathrm {GF} (p^{m_{i}})}$ with the proper basis ${\displaystyle \{\beta _{i,0},\beta _{i,1},\ldots ,\beta _{i,m_{i}-1}\}}$, we have ${\displaystyle {\alpha }^{j{k}_i}=\sum _{s=0}^{m_i-1}{a}_{ijs}}$${\displaystyle \alpha ^{jk_{i}}=\sum _{s=0}^{m_{i}-1}a_{ijs}\beta _{i,s}}$ where ${\displaystyle a_{ijs}\in \mathrm {GF} (p)}$, and by the property of the linearized polynomial ${\displaystyle L_{i}(x)}$, we have

${\displaystyle F_{j}=\sum _{i=0}^{l}\sum _{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}}}\right)}$

This equation can be rewritten in matrix form as ${\displaystyle \mathbf {F} =\mathbf {AL\Pi f} }$, where ${\displaystyle \mathbf {A} }$ is an ${\displaystyle N\times N}$ matrix over GF(p) that contains the elements ${\displaystyle a_{ijs}}$, ${\displaystyle \mathbf {L} }$ is a$블록{\displaystyle \mathbf{}}$ 대각 행렬과 block ${\$은(는) 사이클로토믹 코제트 색인에 $따라$ f ${\$의 요소를 다시 구성하는 순열 행렬이다$$.

Note that if the normal basis ${\displaystyle \{\gamma _{i}^{p^{0}},\gamma _{i}^{p^{1}},\cdots ,\gamma _{i}^{p^{m_{i}-1}}\}}$ is used to expand the field elements of ${\displaystyle \mathrm {GF} (p^{m_{i}})}$, the i-th block of ${\displaystyle \mathbf{L}}$${\displaystyle \mathbf {L}은($는) 다음을 통해 제공됨$$:

${L\displaystyle \mathbf{}_{나는}={\begin{bmatrix}\gamma _{나는}^{p^{0}}&\gamma _{나는}^{p^{1}}&\cdots &, \gamma _{나는}^{p^{m_{나는}-1}}\\\gamma _{나는}^{p^{1}}&\gamma _{나는}^{p^{2}}&\cdots &, \gamma _{나는}^{p^{0}}\\\vdots &, \vdots &, \ddots &, \vdots(_{나는}^{p^{m_{나는}-1}}&\gamma _{나는}^{p^{0}}&\cdots &, \gamma _{나는}^{p^{m_{나는}-2.}}\\\end{bmatrix}}}$

순환 기질이야순환 매트릭스 벡터 제품은 경련을 통해 효율적으로 계산할 수 있다는 것은 잘 알려져 있다.그래서 우리는 분리된 푸리에 변환을 짧은 경련으로 성공적으로 줄였다.

복잡성

특성-2 필드 GF(2$)$에^m 적용할 때 $행렬{\displaystyle \mathbf{}}$ A {\$displaystyle$\mathbf {$A}$}은$($는) $이항$ 행렬에 불과하다.Only addition is used when calculating the matrix-vector product of ${\displaystyle \mathrm {A} }$ and ${\displaystyle \mathrm {L\Pi f} }$. It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by ${\displaystyle O(n(\log _{2}n)^{\log$$_{2}{\frac{3}{2$ 추가 복잡성은 $o{\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$2 /${\displaystyle }$( ${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle {}^{}\mathrm{nn}}$ ) ${\displaystyle {{로그\mathrm{}}_{}}^{}}$ 2${\displaystyle {{}_{}8\frac{\mathrm{}}{}}^{}}$ 8${\displaystyle {}^{}{\frac{3}{}}^{}}$ $){\displaystyle$O($n^{2}/(\log _{2$}n$)^{2}{{2}{frac {8}}}}}}}}}}}}}}}}$에 의해 주어진다$.$^[2]

참조