數論轉換 是一種計算摺積 的快速演算法。計算摺積的快速演算法中最常用的一種是使用快速傅里葉變換 ，然而快速傅利葉變換具有一些實現上的缺點，舉例來說，資料向量必須乘上複數 系數的矩陣加以處理，而且每個複數系數的實部和虛部是一個正弦 及餘弦 函數，因此大部分的系數都是浮點數 ，也就是說，必須做複數而且是浮點數的運算，因此計算量會比較大，而且浮點數運算產生的誤差會比較大。
而在數論轉換中，資料向量需要乘上的矩陣是一個整數 的矩陣，因此不需要作浮點數的乘法運算，更進一步，在模數為
M
{\displaystyle M}
M
2
{\displaystyle M^{2}}
M
2
{\displaystyle M^{2}}
雖然使用數論轉換可以降低計算摺積的複雜度，不過由於只進行整數的運算，所以只能用於對整數的訊號計算摺積，而利用快速傅利葉變換可以對任何複數的訊號計算摺積，這是降低運算複雜度所要付出的代價。
數論轉換的轉換式為
F
[
k
]
=
∑
n
=
0
N
−
1
f
[
n
]
α
n
k
(
mod
M
)
k
=
0
,
1
,
2
,
…
,
N
−
1
{\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}
而數論轉換的反轉換式為
f
[
n
]
=
N
−
1
∑
k
=
0
N
−
1
F
[
k
]
α
−
n
k
(
mod
M
)
n
=
0
,
1
,
2
,
…
,
N
−
1
{\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}{\pmod {M}}\quad n=0,1,2,\ldots ,N-1}
註解：
(1)
M
{\displaystyle M}
質數 。
(2)
(
mod
M
)
{\displaystyle {\pmod {M}}}
餘數
(3)
N
{\displaystyle N}
M
−
1
{\displaystyle M-1}
因數 。(當
N
≠
1
{\displaystyle N\neq 1}
N
{\displaystyle N}
M
{\displaystyle M}
互質 )
(4)
N
−
1
{\displaystyle N^{-1}}
N
{\displaystyle N}
M
{\displaystyle M}
模反元素
(5)
α
{\displaystyle \alpha }
α
N
=
1
(
mod
M
)
{\displaystyle \alpha ^{N}=1{\pmod {M}}}
α
k
≠
1
(
mod
M
)
k
=
1
,
2
,
…
,
N
−
1
{\displaystyle \alpha ^{k}\neq 1{\pmod {M}}\ k=1,2,\ldots ,N-1}
N
=
M
−
1
{\displaystyle N=M-1}
α
{\displaystyle \alpha }
原根
舉一個例子：
一個
M
=
5
{\displaystyle M=5}
N
=
4
{\displaystyle N=4}
α
=
2
{\displaystyle \alpha =2}
N
−
1
=
4
{\displaystyle N^{-1}=4}
正轉換
(
F
[
0
]
F
[
1
]
F
[
2
]
F
[
3
]
)
=
(
1
1
1
1
1
2
4
3
1
4
1
4
1
3
4
2
)
(
f
[
0
]
f
[
1
]
f
[
2
]
f
[
3
]
)
(
mod
M
)
{\displaystyle {\begin{pmatrix}F[0]\\F[1]\\F[2]\\F[3]\end{pmatrix}}={\begin{pmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{pmatrix}}{\begin{pmatrix}f[0]\\f[1]\\f[2]\\f[3]\end{pmatrix}}{\pmod {M}}}
反轉換
(
f
[
0
]
f
[
1
]
f
[
2
]
f
[
3
]
)
=
(
4
4
4
4
4
2
1
3
4
1
4
1
4
3
1
2
)
(
F
[
0
]
F
[
1
]
F
[
2
]
F
[
3
]
)
(
mod
M
)
{\displaystyle {\begin{pmatrix}f[0]\\f[1]\\f[2]\\f[3]\end{pmatrix}}={\begin{pmatrix}4&4&4&4\\4&2&1&3\\4&1&4&1\\4&3&1&2\end{pmatrix}}{\begin{pmatrix}F[0]\\F[1]\\F[2]\\F[3]\end{pmatrix}}{\pmod {M}}}
(1) 正交性質
數論轉換矩陣的每個列是互相正交的，即
∑
n
=
0
N
−
1
α
n
l
α
−
n
k
=
{
N
i
f
k
=
l
0
i
f
k
≠
l
(
mod
M
)
{\displaystyle \sum _{n=0}^{N-1}\alpha ^{nl}\alpha ^{-nk}={\begin{cases}N\quad if\ k=l\\0\quad if\ k\neq l\end{cases}}{\pmod {M}}}
(2) 對稱性
若
f
[
n
]
=
f
[
N
−
n
]
{\displaystyle f[n]=f[N-n]}
f
[
n
]
{\displaystyle f[n]}
F
[
k
]
{\displaystyle F[k]}
F
[
k
]
=
F
[
N
−
k
]
{\displaystyle F[k]=F[N-k]}
若
f
[
n
]
=
−
f
[
N
−
n
]
{\displaystyle f[n]=-f[N-n]}
f
[
n
]
{\displaystyle f[n]}
F
[
k
]
{\displaystyle F[k]}
F
[
k
]
=
−
F
[
N
−
k
]
{\displaystyle F[k]=-F[N-k]}
(3) 反數論轉換可由正數論轉換實現
f
[
n
]
=
N
−
1
∑
k
=
0
N
−
1
F
[
k
]
α
−
n
k
=
N
−
1
∑
−
k
=
0
N
−
1
F
[
−
k
]
α
n
k
{\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}=N^{-1}\sum _{-k=0}^{N-1}F[-k]\alpha ^{nk}}
N
−
1
F
[
−
k
]
{\displaystyle N^{-1}F[-k]}
步驟一：把
F
[
k
]
{\displaystyle F[k]}
F
[
−
k
]
{\displaystyle F[-k]}
F
[
k
]
=
F
0
,
F
1
,
,
F
2
…
,
F
N
−
1
{\displaystyle F[k]=F_{0},F_{1},,F_{2}\ldots ,F_{N-1}}
F
[
−
k
]
=
F
0
,
F
N
−
1
,
…
,
F
2
,
F
1
{\displaystyle F[-k]=F_{0},F_{N-1},\ldots ,F_{2},F_{1}}
步驟二：求
F
[
−
k
]
{\displaystyle F[-k]}
步驟三：乘上
N
−
1
{\displaystyle N^{-1}}
(4) 線性性質
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
g
[
n
]
↔
G
[
k
]
{\displaystyle g[n]\leftrightarrow G[k]}
↔
{\displaystyle \leftrightarrow }
a
f
[
n
]
+
b
g
[
n
]
↔
a
F
[
k
]
+
b
g
[
k
]
(
mod
M
)
{\displaystyle af[n]+bg[n]\leftrightarrow aF[k]+bg[k]{\pmod {M}}}
(5) 平移性質
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
f
[
n
+
l
]
↔
α
−
l
k
F
[
k
]
(
mod
M
)
{\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]{\pmod {M}}}
f
[
n
]
α
n
l
↔
F
[
k
+
l
]
{\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}
(6) 圓周摺積 性質
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
g
[
n
]
↔
G
[
k
]
{\displaystyle g[n]\leftrightarrow G[k]}
f
[
n
]
⊗
g
[
n
]
↔
F
[
k
]
G
[
k
]
(
mod
M
)
{\displaystyle f[n]\otimes g[n]\leftrightarrow F[k]G[k]{\pmod {M}}}
f
[
n
]
g
[
n
]
↔
1
N
F
[
k
]
⊗
G
[
k
]
(
mod
M
)
{\displaystyle f[n]g[n]\leftrightarrow {\frac {1}{N}}F[k]\otimes G[k]{\pmod {M}}}
⊗
{\displaystyle \otimes }
這個性質是數論轉換可以用來作為摺積的快速演算法的主要原因。
(7) 帕塞瓦爾定理 (Parseval's Theorem)
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
N
∑
n
=
0
N
−
1
f
[
n
]
f
[
−
n
]
=
∑
k
=
0
N
−
1
F
2
[
k
]
(
mod
M
)
{\displaystyle N\sum _{n=0}^{N-1}f[n]f[-n]=\sum _{k=0}^{N-1}F^{2}[k]{\pmod {M}}}
N
∑
n
=
0
N
−
1
f
2
[
n
]
=
∑
k
=
0
N
−
1
F
[
k
]
F
[
−
k
]
(
mod
M
)
{\displaystyle N\sum _{n=0}^{N-1}f^{2}[n]=\sum _{k=0}^{N-1}F[k]F[-k]{\pmod {M}}}
梅森質數是指形如
2
p
−
1
{\displaystyle 2^{p}-1}
M
p
{\displaystyle M_{p}}
p
{\displaystyle p}
在梅森質數數論轉換中，取
M
=
M
p
{\displaystyle M=M_{p}}
α
,
N
{\displaystyle \alpha ,N}
(1)
α
=
2
,
N
=
p
,
N
−
1
=
M
p
−
M
p
−
1
p
{\displaystyle \alpha =2,N=p,N^{-1}=M_{p}-{\frac {M_{p}-1}{p}}}
(2)
α
=
−
2
,
N
=
2
p
,
N
−
1
=
M
p
−
M
p
−
1
2
p
{\displaystyle \alpha =-2,N=2p,N^{-1}=M_{p}-{\frac {M_{p}-1}{2p}}}
在這兩種選取方式下，由於
α
{\displaystyle \alpha }
N
{\displaystyle N}
N
{\displaystyle N}
費馬數是指形如
2
2
t
+
1
{\displaystyle 2^{2^{t}}+1}
F
t
{\displaystyle F_{t}}
在費馬數數論轉換中，取
M
=
F
t
{\displaystyle M=F_{t}}
0
<
t
≤
4
{\displaystyle 0<t\leq 4}
α
,
N
{\displaystyle \alpha ,N}
(1)
α
=
2
,
N
=
2
t
+
1
{\displaystyle \alpha =2,N=2^{t+1}}
(2)
α
=
3
,
N
=
F
t
−
1
{\displaystyle \alpha =3,N=F_{t}-1}
在這兩種選取方式下，
N
{\displaystyle N}
α
{\displaystyle \alpha }
由於數論轉換需運用到餘數下的反元素，這邊提供一些不同的演算法。
(一) Euclidean algorithm - iterative version
假設M為質數的mod，N為我們當前的元素且符合M-1的因數，藉由Euclidean Algorithm知道必然存在x, y的整數使得
xM + yN = 1 - (1)
由上式左右mod M 可以得到 yN mod M= 1，顯然y就是我們這邊想求的反元素。
我們已知最大公因數(gcd)有如下性質。
gcd(M, N) = gcd(N, M mod N) = gcd(M mod N, N mod (M mod N)) = ... = 1
這邊設定q為商數，r為餘數，接上面的等式方程式化如下。
M
=
q
0
N
+
r
1
,
{\displaystyle M=q_{0}N+r_{1},}
N
=
q
1
r
1
+
r
2
,
{\displaystyle N=q_{1}r_{1}+r_{2},}
r
1
=
q
2
r
2
+
r
3
,
{\displaystyle r_{1}=q_{2}r_{2}+r_{3},}
r
2
=
q
3
r
3
+
r
4
,
.
.
.
{\displaystyle r_{2}=q_{3}r_{3}+r_{4},...}
整理一下
M
−
q
0
N
=
r
1
,
{\displaystyle M-q_{0}N=r_{1},}
N
−
q
1
r
1
=
r
2
,
{\displaystyle N-q_{1}r_{1}=r_{2},}
r
1
−
q
2
r
2
=
r
3
,
{\displaystyle r_{1}-q_{2}r_{2}=r_{3},}
r
2
−
q
3
r
3
=
r
4
,
.
.
.
{\displaystyle r_{2}-q_{3}r_{3}=r_{4},...}
最後的r 一定會變成1，所以我們只要不斷的將r乘上-q帶往下一個式子(像是r1*(-q1))，跟代往下下個式子(像是r3的左邊式子要帶入r1)即可求得最後我們想得到的 (1)，最後的N旁的系數就是反元素。
def modInv ( x , M ): #by Euclidean algorithm - iterative version
t , new_t , r , new_r = 0 , 1 , M , x
while new_r != 0 :
quotient = int ( r / new_r )
tmp_new_t = new_t
tmp_t = t
tmp_new_r = new_r
tmp_r = r
t , new_t = new_t , ( t - quotient * new_t )
r , new_r = new_r , ( r % new_r )
if r > 1 :
print ( "Inverse doesn't exist" )
if t < 0 :
t = t + M
return t
(二) Euclidean algorithm - recursion version
根據gcd的性質gcd(M, N) = gcd(N, M mod N) = gcd(M mod N, N mod (M mod N)) = ... = 1
可以看出遞迴的關係，藉此我們可以從這邊得到N的系數，也就是反元素。
gcd(M, N) = 1來看，我們知道存在
x
M
+
y
N
=
1
{\displaystyle xM+yN=1}
gcd(N, M mod N)=1，則存在
x
1
N
+
y
1
(
M
m
o
d
N
)
=
1
{\displaystyle x_{1}N+y_{1}(M\,mod\,N)=1}
x
1
N
+
y
1
(
M
m
o
d
N
)
=
x
1
N
+
y
1
(
M
−
q
1
N
)
=
y
1
M
+
(
x
1
−
q
1
y
1
)
N
=
1
{\displaystyle x_{1}N+y_{1}(M\,mod\,N)=x_{1}N+y_{1}(M-q_{1}N)=y_{1}M+(x_{1}-q_{1}y_{1})N=1}
這邊q就是相除的商數，比較M跟N的系數，這邊可以得到一個遞迴關係，
(
x
1
−
q
1
y
1
)
=
y
{\displaystyle (x_{1}-q_{1}y_{1})=y}
y
1
=
x
{\displaystyle y_{1}=x}
可以藉由下一層的系數來推出上一層的系數。
def egcd ( a , b ): # y = x1 - quotient * y1 , x = y1
if a == 0 :
return ( b , 0 , 1 )
else :
g , y , x = egcd ( b % a , a )
return ( g , x - ( b // a ) * y , y )
def modInv ( n , m ): #by Euclidean algorithm - recursion version
g , y , x = egcd ( n , m )
if g != 1 :
print ( "Inverse doesn't exist" )
else :
return y % m
(三) Fermat little theorem
當M是質數時，我們知道任何一個數字N，
N
M
−
1
m
o
d
M
=
1
{\displaystyle N^{M-1}\,mod\,M=1}
N
(
N
M
−
2
m
o
d
M
)
m
o
d
M
=
1
{\displaystyle N(N^{M-2}\,mod\,M)\,mod\,M=1}
顯然
N
M
−
2
m
o
d
M
{\displaystyle N^{M-2}\,mod\,M}
搭配快速mod可以容易的算出反元素，power是偶數時則可以用
(
a
2
m
o
d
M
)
p
o
w
e
r
/
2
{\displaystyle (a^{2}\,mod\,M)^{power/2}}
(
a
N
m
o
d
M
)
p
o
w
e
r
−
1
{\displaystyle (aN\,mod\,M)^{power-1}}
def modInv ( a , m ): #fermat little thm
return modExponent ( a , m - 2 , m )
def modExponent ( base , power , M ): #quick mod O(log(power))
result = 1
power = int ( power )
base = base % M
while power > 0 :
if power & 1 :
result = ( result * base ) % M
base = ( base * base ) % M
power = power >> 1
return result
以下程式預設。
這邊只要再從1到M-1中選出一個適當的alpha (Root Of Unity)，其滿足"轉換公式"段落的(5)即可。
def NTT ( x , N , M ):
#TODO: RootOfUnity
alpha = RootOfUnity ( N , M )
NInv = modInv ( N , M )
A = np . ones (( N , N ))
for i in range ( 1 , N ):
for j in range ( 1 , i + 1 ):
A [ i ][ j ] = A [ i ][ j - 1 ] * modExponent ( alpha , i , M ) % M
A [ j ][ i ] = A [ i ][ j ]
return np . matmul ( A , x ) % M , alpha
def invNTT ( x , alpha , N , M ):
alphaInv = modInv ( alpha , M )
NInv = modInv ( N , M )
B = np . ones (( N , N ))
for i in range ( 1 , N ):
for j in range ( 1 , i + 1 ):
B [ i ][ j ] = B [ i ][ j - 1 ] * modExponent ( alphaInv , i , M ) % M
B [ j ][ i ] = B [ i ][ j ]
B = B * NInv
return np . matmul ( B , x ) % M
[1] R.C. Agarval and C.S. Burrus,"Number Theoretic Transforms to Implement Fast Digital Convolution," Proc. IEEE , vol.63, no.4, pp. 550-560, Apr. 1975.
[2] I. Reed and T.K. Truong,"The use of finite fileds to compute convolution," IEEE Trans. Info. Theory , vol.21 ,pp.208-213, Mar. 1975.
![{\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b5ae80e3c29d7fc911df70abbcd11a02b956e9d)
![{\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}{\pmod {M}}\quad n=0,1,2,\ldots ,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc04903b711ec40cd564e396963030274d7f3253)
![{\displaystyle {\begin{pmatrix}F[0]\\F[1]\\F[2]\\F[3]\end{pmatrix}}={\begin{pmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{pmatrix}}{\begin{pmatrix}f[0]\\f[1]\\f[2]\\f[3]\end{pmatrix}}{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4913aac635b4044dbdb5942a9732e05d8666474d)
![{\displaystyle {\begin{pmatrix}f[0]\\f[1]\\f[2]\\f[3]\end{pmatrix}}={\begin{pmatrix}4&4&4&4\\4&2&1&3\\4&1&4&1\\4&3&1&2\end{pmatrix}}{\begin{pmatrix}F[0]\\F[1]\\F[2]\\F[3]\end{pmatrix}}{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71c1db5a02f7b0f215fbbb77095c4733303b0cf5)
![{\displaystyle f[n]=f[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1be38aeb60f3dc3b84bddbdb1860fe384c49237c)
![{\displaystyle f[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b176b3dbcced447341ad5ab70001ef0e3231062e)
![{\displaystyle F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b1a4da8ed199ca114765442e28d409694b6485f)
![{\displaystyle F[k]=F[N-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/012a5775e172f5beee85cdc07097534631c3976f)
![{\displaystyle f[n]=-f[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22bfea3756093c07cb80fa7f8eb015beff5ae936)
![{\displaystyle F[k]=-F[N-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6808e18eebce96aa50d295e7e399439c3567ed7)
![{\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}=N^{-1}\sum _{-k=0}^{N-1}F[-k]\alpha ^{nk}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3db9ac97e5206e8fef07bc7206e51e61c82168e7)
![{\displaystyle N^{-1}F[-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01a0859ee54d3f3a83e8caee0dbf6b364e58d1c1)
![{\displaystyle F[-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21c8c1694efabbd515f286b9237542c01ec0344a)
![{\displaystyle F[k]=F_{0},F_{1},,F_{2}\ldots ,F_{N-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5df045525f9d1939c56901c88c528215e95e89b1)
![{\displaystyle F[-k]=F_{0},F_{N-1},\ldots ,F_{2},F_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aa2e9608e94b4943fa0851c0efecc1787a2e4dc)
![{\displaystyle f[n]\leftrightarrow F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c270965e7225021b5807cb2a0bc0082c717d1c0)
![{\displaystyle g[n]\leftrightarrow G[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71cf7661bb0f576066b477f68cb37ff98ae4fffd)
![{\displaystyle af[n]+bg[n]\leftrightarrow aF[k]+bg[k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9d59f86aad988ca01ff3106456e0a3148f16f83)
![{\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17890df9ef584d6dc81c8d1010c1ce2c8da6a962)
![{\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/740c0342528c72337ccff5ead61d2768509a2d4b)
![{\displaystyle f[n]\otimes g[n]\leftrightarrow F[k]G[k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdd396805bd7f7b1f9eaa05e9d54e0c7c726b111)
![{\displaystyle f[n]g[n]\leftrightarrow {\frac {1}{N}}F[k]\otimes G[k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8287b8267d71e572a814252782edaae1d583770d)
![{\displaystyle N\sum _{n=0}^{N-1}f[n]f[-n]=\sum _{k=0}^{N-1}F^{2}[k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a72f74e4310684b38c42369b6ed2865ee692d50)
![{\displaystyle N\sum _{n=0}^{N-1}f^{2}[n]=\sum _{k=0}^{N-1}F[k]F[-k]{\pmod {M}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4dccbb87dfb48cded88581b6a11c5d61845a92f)
![{\displaystyle {\begin{matrix}F[k]&=&\sum _{n=0}^{N-1}f[n]\alpha ^{nk}\\\ &=&\sum _{r=0}^{N/2-1}f[2r]\alpha ^{2rk}+\sum _{r=0}^{N/2-1}f[2r+1]\alpha ^{(2r+1)k}\\\ &=&\sum _{r=0}^{N/2-1}f[2r](\alpha ^{2})^{rk}+\alpha ^{k}\sum _{r=0}^{N/2-1}f[2r+1](\alpha ^{2})^{rk}\\\ &=&{\begin{cases}G[k]+\alpha ^{k}H[k]\quad 0\leq k\leq {\frac {N}{2}}-1\\G[k-{\frac {N}{2}}]-\alpha ^{k}H[k-{\frac {N}{2}}]\quad {\frac {N}{2}}\leq k\leq N-1\end{cases}}\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31d0f486b888bbd17ae4bd1786762ffa22769aaf)
![{\displaystyle G[k]=\sum _{r=0}^{N/2-1}f[2r](\alpha ^{2})^{rk}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d432c5fa5164a8588105ed4daca8f7ff864813a3)
![{\displaystyle H[k]=\sum _{r=0}^{N/2-1}f[2r+1](\alpha ^{2})^{rk}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f7227b0da2519cad84e1732f928eafa3fd7312e)
