Introduction
-2 finite field. In Binius, RS-encoding (Reed-Solomon encoding) is employed, but there is a challenge: the conventional Radix-2 FFT cannot be utilized in characteristic-2 finite fields. This paper addresses that challenge.
The title of the paper is "Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes." A characteristic-2 finite field is an extension field of the form F 2 r \mathbb{F}_{2^r} F 2 r 1 , X , X 2 , … 1, X, X^2, \dots 1 , X , X 2 , … new polynomial basis and proposes an encoding algorithm that achieves performance comparable to the Radix-2 FFT.
Background
Radix-2 FFT
The coefficient form of a univariate polynomial of degree n − 1 n−1 n − 1
P ( X ) = c 0 + c 1 X + c 2 X 2 + ⋯ + c n − 1 X n − 1 P(X) = c_0 + c_1X + c_2X^2 + \cdots + c_{n-1}X^{n-1} P ( X ) = c 0 + c 1 X + c 2 X 2 + ⋯ + c n − 1 X n − 1 where the basis is { 1 , X , X 2 , … , X n − 1 } \{1, X, X^2, \dots, X^{n-1}\} { 1 , X , X 2 , … , X n − 1 }
On the other hand, the evaluation form of a univariate polynomial is defined as:
P ( X ) = P ( x 0 ) ⋅ L 0 ( X ) + P ( x 1 ) ⋅ L 1 ( X ) + P ( x 2 ) ⋅ L 2 ( X ) + ⋯ + P ( x n − 1 ) ⋅ L n − 1 ( X ) P(X) = P(x_0)\cdot L_0(X) + P(x_1)\cdot L_1(X) + P(x_2)\cdot L_2(X) + \cdots + P(x_{n-1})\cdot L_{n-1}(X) P ( X ) = P ( x 0 ) ⋅ L 0 ( X ) + P ( x 1 ) ⋅ L 1 ( X ) + P ( x 2 ) ⋅ L 2 ( X ) + ⋯ + P ( x n − 1 ) ⋅ L n − 1 ( X ) where the basis is { L 0 ( X ) , L 1 ( X ) , L 2 ( X ) , … , L n − 1 ( X ) } \{L_0(X), L_1(X), L_2(X), \dots, L_{n-1}(X)\} { L 0 ( X ) , L 1 ( X ) , L 2 ( X ) , … , L n − 1 ( X )} Lagrange basis .
L i ( X ) = ∏ j ≠ i X − ω j ω i − ω j = { 1 if X = ω i 0 otherwise L_i(X) = \prod_{j \ne i}\frac{X - \omega^j}{\omega^i - \omega^j} = \begin{cases} 1 &\text{ if }X = \omega^i \\ 0 &\text{ otherwise} \end{cases} L i ( X ) = j = i ∏ ω i − ω j X − ω j = { 1 0 if X = ω i otherwise [ P ( 1 ) P ( ω ) P ( ω 2 ) ⋮ P ( ω n − 1 ) ] = [ 1 1 1 ⋯ 1 1 ω ω 2 ⋯ ω n − 1 1 ω 2 ω 4 ⋯ ω 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω n − 1 ω 2 ( n − 1 ) ⋯ ω ( n − 1 ) 2 ] ⋅ [ c 0 c 1 c 2 ⋮ c n − 1 ] \begin{bmatrix} P(1)\\ P(\omega)\\ P(\omega^2)\\ \vdots \\ P(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix} \cdot \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{bmatrix} P ( 1 ) P ( ω ) P ( ω 2 ) ⋮ P ( ω n − 1 ) = 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω n − 1 1 ω 2 ω 4 ⋮ ω 2 ( n − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω n − 1 ω 2 ( n − 1 ) ⋮ ω ( n − 1 ) 2 ⋅ c 0 c 1 c 2 ⋮ c n − 1 The n n n
ω n − 1 = ( ω n / 2 − 1 ) ( ω n / 2 + 1 ) = 0 \omega^n - 1 = (\omega^{n/2} - 1)(\omega^{n/2} + 1) = 0 ω n − 1 = ( ω n /2 − 1 ) ( ω n /2 + 1 ) = 0 Since ω n / 2 \omega^{n/2} ω n /2 1 1 1 − 1 -1 − 1
P E ( X 2 ) P_E(X^2) P E ( X 2 ) X X X
P O ( X 2 ) P_O(X^2) P O ( X 2 ) X X X
This gives:
P ( X ) = P E ( X 2 ) + X ⋅ P O ( X 2 ) P(X) = P_{E}(X^2) + X \cdot P_{O}(X^2) P ( X ) = P E ( X 2 ) + X ⋅ P O ( X 2 ) For X = − X X = -X X = − X X ⋅ ω n / 2 X \cdot \omega^{n/2} X ⋅ ω n /2
P ( − X ) = P ( X ⋅ ω n / 2 ) = P E ( X 2 ) − X ⋅ P O ( X 2 ) P(-X) = P(X \cdot \omega^{n/2}) = P_E(X^2) - X\cdot P_O(X^2) P ( − X ) = P ( X ⋅ ω n /2 ) = P E ( X 2 ) − X ⋅ P O ( X 2 ) This transforms an n n n n / 2 n / 2 n /2
Define Δ i m ( X ) \Delta^m_i(X) Δ i m ( X )
Δ i m ( X ) = { Δ i + 1 m ( X ) + X 2 i Δ i + 1 m + 2 i ( X ) if 0 ≤ i < log 2 n c m if i = log 2 n \Delta^m_i(X) = \begin{cases} \Delta^m_{i+1}(X) + X^{2^i}\Delta^{m + 2^i }_{i+1}(X) & \text{ if }0 \le i < \log_2 n \\ c_m & \text{ if }i = \log_2 n\\ \end{cases} Δ i m ( X ) = { Δ i + 1 m ( X ) + X 2 i Δ i + 1 m + 2 i ( X ) c m if 0 ≤ i < log 2 n if i = log 2 n For example, for n = 8 n=8 n = 8
P ( X ) = ∑ i = 0 7 c i X i = c 0 + c 4 X 4 + X 2 ( c 2 + c 6 X 4 ) + X ( c 1 + c 5 X 4 + X 2 ( c 3 + c 7 X 4 ) = Δ 2 0 ( X ) + X 2 Δ 2 2 ( X ) + X ( Δ 2 1 ( X ) + X 2 Δ 2 3 ( X ) ) = Δ 1 0 ( X ) + X Δ 1 1 ( X ) = Δ 0 0 ( X ) \begin{align*} P(X) &= \sum_{i = 0}^{7}c_iX_i \\ &= c_0 + c_4X^4 + X^2(c_2 + c_6X^4) + X(c_1 + c_5X^4 + X^2(c_3 + c_7X^4)\\ &= \Delta^0_2(X) + X^2\Delta^2_2(X) + X(\Delta^1_2(X) + X^2\Delta^3_2(X)) \\ &=\Delta^0_1(X) + X\Delta^1_1(X) \\ &=\Delta^0_0(X) \end{align*} P ( X ) = i = 0 ∑ 7 c i X i = c 0 + c 4 X 4 + X 2 ( c 2 + c 6 X 4 ) + X ( c 1 + c 5 X 4 + X 2 ( c 3 + c 7 X 4 ) = Δ 2 0 ( X ) + X 2 Δ 2 2 ( X ) + X ( Δ 2 1 ( X ) + X 2 Δ 2 3 ( X )) = Δ 1 0 ( X ) + X Δ 1 1 ( X ) = Δ 0 0 ( X ) By recursively applying this process, the computational complexity of FFT becomes O ( n ⋅ log n ) O(n \cdot \log n) O ( n ⋅ log n )
The Inverse FFT (IFFT) converts a polynomial from its evaluation form back to its coefficient form by using the inverse of the Vandermonde matrix :
[ c 0 c 1 c 2 ⋮ c n − 1 ] = [ 1 1 1 ⋯ 1 1 ω ω 2 ⋯ ω n − 1 1 ω 2 ω 4 ⋯ ω 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω n − 1 ω 2 ( n − 1 ) ⋯ ω ( n − 1 ) 2 ] − 1 ⋅ [ P ( 1 ) P ( ω ) P ( ω 2 ) ⋮ P ( ω n − 1 ) ] \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix}^{-1} \cdot \begin{bmatrix} P(1)\\ P(\omega)\\ P(\omega^2)\\ \vdots \\ P(\omega^{n-1}) \end{bmatrix} c 0 c 1 c 2 ⋮ c n − 1 = 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω n − 1 1 ω 2 ω 4 ⋮ ω 2 ( n − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω n − 1 ω 2 ( n − 1 ) ⋮ ω ( n − 1 ) 2 − 1 ⋅ P ( 1 ) P ( ω ) P ( ω 2 ) ⋮ P ( ω n − 1 ) The IFFT can also be computed in O ( n ⋅ log n ) O(n \cdot \log n) O ( n ⋅ log n )
2-adicity
When the modulus of a prime field is of the form 2 S ⋅ T + 1 2^S\cdot T + 1 2 S ⋅ T + 1 2 k 2^k 2 k ω \omega ω k < S k < S k < S
g p − 1 = g 2 S ⋅ T = ( g 2 S − k ⋅ T ) 2 k = ω 2 k ≡ 1 ( m o d p ) g^{p-1} = g^{2^S \cdot T} = (g^{2^{S-k} \cdot T})^{2^k} = \omega^{2^k} \equiv 1 \pmod p g p − 1 = g 2 S ⋅ T = ( g 2 S − k ⋅ T ) 2 k = ω 2 k ≡ 1 ( mod p ) In other words, if the order of the multiplicative subgroup F p × \mathbb{F}_p^\times F p × 2 S ⋅ T 2^S \cdot T 2 S ⋅ T S S S 2-adicity ) is large, FFT can be used effectively. Fields with this structure are referred to as FFT-friendly fields .
What about characteristic-2 finite fields, such as F 2 r \mathbb{F}_{2^r} F 2 r F 2 r × \mathbb{F}_{2^r}^{\times} F 2 r × 2 r − 1 2^r - 1 2 r − 1 2 r − 1 2^r - 1 2 r − 1
This naturally raises the question: when the characteristic is 2, what new polynomial basis would be suitable? Moreover, to achieve fast computation similar to Radix-2 FFT, the method must recursively reduce the problem into smaller subproblems.Protocol Explanation
NOTE: From this point onward, ω \omega ω Δ \Delta Δ
Polynomial Basis
The elements of F 2 r \mathbb{F}_{2^r} F 2 r { ω i } i = 0 2 r − 1 \{\omega_i\}_{i=0}^{2^r - 1} { ω i } i = 0 2 r − 1
i = ∑ k = 0 r − 1 i k ⋅ 2 k , ∀ i k ∈ 0 , 1 i = \sum_{k = 0}^{r-1}i_k \cdot 2^k, \forall i_k \in {0,1} i = k = 0 ∑ r − 1 i k ⋅ 2 k , ∀ i k ∈ 0 , 1 Given a basis vector v = { v 0 , … , v r − 1 } v = \{v_0, \dots, v_{r-1}\} v = { v 0 , … , v r − 1 } F 2 r \mathbb{F}_{2^r} F 2 r ω i \omega_i ω i
ω i = ∑ k = 0 r − 1 i k ⋅ v k \omega_i = \sum_{k = 0}^{r-1}i_k \cdot v_k ω i = k = 0 ∑ r − 1 i k ⋅ v k We define the subspace vanishing polynomial as:
W j ( X ) = ∏ i = 0 2 j − 1 ( X + ω i ) , where 0 ≤ j ≤ r − 1 W_j(X) = \prod_{i=0}^{2^j-1}(X + \omega_i)\text{, where } 0 \le j \le r - 1 W j ( X ) = i = 0 ∏ 2 j − 1 ( X + ω i ) , where 0 ≤ j ≤ r − 1 This mean the full form of the vanishing polynomials W j ( X ) W_j(X) W j ( X )
W 0 ( X ) = X + ω 0 , W 1 ( X ) = ( X + ω 0 ) ( X + ω 1 ) , W 2 ( X ) = ( X + ω 0 ) ( X + ω 1 ) ( X + ω 2 ) ( X + ω 3 ) , W_0(X) = X + \omega_0, \\ W_1(X) = (X + \omega_0)(X + \omega_1) ,\\ W_2(X) = (X + \omega_0)(X + \omega_1)(X + \omega_2)(X + \omega_3) ,\\ W 0 ( X ) = X + ω 0 , W 1 ( X ) = ( X + ω 0 ) ( X + ω 1 ) , W 2 ( X ) = ( X + ω 0 ) ( X + ω 1 ) ( X + ω 2 ) ( X + ω 3 ) , and so on.
Thus, deg ( W j ( X ) ) = 2 j \deg(W_j(X)) = 2^j deg ( W j ( X )) = 2 j W 2 ( X ) W_2(X) W 2 ( X ) ω 0 , ω 1 , ω 2 , ω 3 \omega_0, \omega_1, \omega_2, \omega_3 ω 0 , ω 1 , ω 2 , ω 3 F 2 r \mathbb{F}_{2^r} F 2 r ω i + ω i = 0 \omega_i + \omega_i = 0 ω i + ω i = 0
Lemma 1. W j ( X ) W_j(X) W j ( X ) F 2 \mathbb{F}_2 F 2
W j ( X ) = ∑ i = 0 j a j , i X 2 i , where a j , i ∈ F 2 r W_j(X) = \sum_{i = 0}^{j}a_{j,i}X^{2^i} \text{, where }a_{j,i} \in \mathbb{F}_{2^r} W j ( X ) = i = 0 ∑ j a j , i X 2 i , where a j , i ∈ F 2 r Furthermore, W j ( X ) W_j(X) W j ( X )
W j ( X + Y ) = W j ( X ) + W j ( Y ) , ∀ X , Y ∈ F 2 r W_j(X + Y) = W_j(X) + W_j(Y), \forall X,Y \in \mathbb{F}_{2^r} W j ( X + Y ) = W j ( X ) + W j ( Y ) , ∀ X , Y ∈ F 2 r We now define a new polynomial basis X i ( X ) X_i(X) X i ( X )
X i ( X ) = ∏ j = 0 r − 1 ( W j ( X ) W j ( ω 2 j ) ) i j X_i(X) = \prod_{j= 0}^{r-1}(\frac{W_j(X)}{W_j(\omega_{2^j})})^{i_j} X i ( X ) = j = 0 ∏ r − 1 ( W j ( ω 2 j ) W j ( X ) ) i j where:
i = ∑ j = 0 r − 1 i j ⋅ 2 j , ∀ i j ∈ 0 , 1 i = \sum_{j = 0}^{r-1}i_j \cdot 2^j, \forall i_j \in {0,1} i = j = 0 ∑ r − 1 i j ⋅ 2 j , ∀ i j ∈ 0 , 1 The new polynomial basis X i ( X ) X_i(X) X i ( X )
X 0 ( X ) = 1 , X 1 ( X ) = W 0 ( X ) W 0 ( ω 1 ) = X + ω 0 ω 1 + ω 0 , X 2 ( X ) = W 1 ( X ) W 1 ( ω 2 ) = ( X + ω 0 ) ( X + ω 1 ) ( ω 2 + ω 0 ) ( ω 2 + ω 1 ) , X 3 ( X ) = W 0 ( X ) W 1 ( X ) W 0 ( ω 1 ) W 1 ( ω 2 ) = ( X + ω 0 ) 2 ( X + ω 1 ) ( ω 1 + ω 0 ) ( ω 2 + ω 0 ) ( ω 2 + ω 1 ) , X 4 ( X ) = W 2 ( X ) W 2 ( ω 4 ) = ( X + ω 0 ) ( X + ω 1 ) ( X + ω 2 ) ( X + ω 3 ) ( ω 4 + ω 0 ) ( ω 4 + ω 1 ) ( ω 4 + ω 2 ) ( ω 4 + ω 3 ) , X_0(X) = 1 ,
\\ X_1(X) = \frac{W_0(X)}{W_0(\omega_1)} = \frac{X + \omega_0}{\omega_1 + \omega_0} ,
\\ X_2(X) = \frac{W_1(X)}{W_1(\omega_2)} = \frac{(X + \omega_0)(X + \omega_1)}{(\omega_2 + \omega_0)(\omega_2 + \omega_1)},
\\ X_3(X) = \frac{W_0(X)W_1(X)}{W_0(\omega_1)W_1(\omega_2)} = \frac{(X + \omega_0)^2(X + \omega_1)}{(\omega_1 + \omega_0)(\omega_2 + \omega_0)(\omega_2 + \omega_1)} ,
\\ X_4(X) = \frac{W_2(X)}{W_2(\omega_4)} = \frac{(X + \omega_0)(X + \omega_1)(X + \omega_2)(X + \omega_3)}{(\omega_4 + \omega_0)(\omega_4 + \omega_1)(\omega_4 + \omega_2)(\omega_4 + \omega_3)}, X 0 ( X ) = 1 , X 1 ( X ) = W 0 ( ω 1 ) W 0 ( X ) = ω 1 + ω 0 X + ω 0 , X 2 ( X ) = W 1 ( ω 2 ) W 1 ( X ) = ( ω 2 + ω 0 ) ( ω 2 + ω 1 ) ( X + ω 0 ) ( X + ω 1 ) , X 3 ( X ) = W 0 ( ω 1 ) W 1 ( ω 2 ) W 0 ( X ) W 1 ( X ) = ( ω 1 + ω 0 ) ( ω 2 + ω 0 ) ( ω 2 + ω 1 ) ( X + ω 0 ) 2 ( X + ω 1 ) , X 4 ( X ) = W 2 ( ω 4 ) W 2 ( X ) = ( ω 4 + ω 0 ) ( ω 4 + ω 1 ) ( ω 4 + ω 2 ) ( ω 4 + ω 3 ) ( X + ω 0 ) ( X + ω 1 ) ( X + ω 2 ) ( X + ω 3 ) , and so on.
Thus, deg ( X i ( X ) ) = i \deg(X_i(X)) = i deg ( X i ( X )) = i
The coefficient form of an n − 1 n-1 n − 1 [ D n ] ( X ) ∈ F 2 r [ X ] / ( X 2 r − 1 ) [D_n](X) \in \mathbb{F}_{2^r}[X] / (X^{2^r} - 1) [ D n ] ( X ) ∈ F 2 r [ X ] / ( X 2 r − 1 )
[ D n ] ( X ) = d 0 + d 1 X 1 ( X ) + d 2 X 2 ( X ) + ⋯ + d n − 1 X n − 1 ( X ) [D_n](X) = d_0 + d_1X_1(X) + d_2X_2(X) + \dots + d_{n-1}X_{n-1}(X) [ D n ] ( X ) = d 0 + d 1 X 1 ( X ) + d 2 X 2 ( X ) + ⋯ + d n − 1 X n − 1 ( X ) The evaluation form of this polynomial is:
[ D n ] ( X ) = [ D n ] ( ω 0 + ω l ) ⋅ L 0 l ( X ) + [ D n ] ( ω 1 + ω l ) ⋅ L 1 l ( X ) + [ D n ] ( ω 2 + ω l ) ⋅ L 2 l ( X ) + ⋯ + [ D n ] ( ω n − 1 + ω l ) ⋅ L n − 1 l ( X ) [D_n](X) = [D_n](\omega_0 + \omega_l) \cdot L^l_0(X) + [D_n](\omega_1 + \omega_l) \cdot L^l_1(X) + [D_n](\omega_2 + \omega_l) \cdot L^l_2(X) + \cdots + [D_n](\omega_{n-1} + \omega_l) \cdot L^l_{n-1}(X) [ D n ] ( X ) = [ D n ] ( ω 0 + ω l ) ⋅ L 0 l ( X ) + [ D n ] ( ω 1 + ω l ) ⋅ L 1 l ( X ) + [ D n ] ( ω 2 + ω l ) ⋅ L 2 l ( X ) + ⋯ + [ D n ] ( ω n − 1 + ω l ) ⋅ L n − 1 l ( X ) where L i l ( X ) L^l_i(X) L i l ( X )
L i l ( X ) = ∏ j ≠ i X − ω j ω i + ω l − ω j = { 1 if X = ω i + ω l 0 otherwise L^l_i(X) = \prod_{j \ne i}\frac{X - \omega_j}{\omega_i + \omega_l - \omega_j} = \begin{cases} 1 &\text{ if }X = \omega_i + \omega_l \\ 0 &\text{ otherwise} \end{cases} L i l ( X ) = j = i ∏ ω i + ω l − ω j X − ω j = { 1 0 if X = ω i + ω l otherwise We denote the set of evaluations as D ^ n l \hat{D}^l_n D ^ n l
D ^ n l = { [ D n ] ( ω 0 + ω l ) , [ D n ] ( ω 1 + ω l ) , [ D n ] ( ω 2 + ω l ) , … , [ D n ] ( ω n − 1 + ω l ) } \hat{D}^l_n = \{[D_n](\omega_0 + \omega_l), [D_n](\omega_1 + \omega_l),[D_n](\omega_2 + \omega_l),\dots, [D_n](\omega_{n-1} + \omega_l) \} D ^ n l = {[ D n ] ( ω 0 + ω l ) , [ D n ] ( ω 1 + ω l ) , [ D n ] ( ω 2 + ω l ) , … , [ D n ] ( ω n − 1 + ω l )} Delta Polynomial
The recursive calculation of [ D n ] ( X ) [D_n](X) [ D n ] ( X ) Δ i m ( X ) \Delta^m_i(X) Δ i m ( X )
Δ i m ( X ) = { Δ i + 1 m ( X ) + W i ( X ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( X ) if 0 ≤ i < log 2 n d m if i = log 2 n \Delta^m_i(X) = \begin{cases}
\Delta^m_{i+1}(X) + \frac{W_i(X)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i+1}(X) & \text{ if }0 \le i < \log_2 n \\
d_m & \text { if } i = \log_2n \end{cases} Δ i m ( X ) = { Δ i + 1 m ( X ) + W i ( ω 2 i ) W i ( X ) Δ i + 1 m + 2 i ( X ) d m if 0 ≤ i < log 2 n if i = log 2 n where 0 ≤ m < 2 i 0 \le m < 2^i 0 ≤ m < 2 i
For n = 8 n = 8 n = 8 Δ \Delta Δ
Δ 3 0 ( X ) = d 0 , Δ 3 1 ( X ) = d 1 , Δ 3 2 ( X ) = d 2 , … , Δ 3 7 ( X ) = d 7 , Δ 2 0 ( X ) = Δ 3 0 ( X ) + W 2 ( X ) W 2 ( ω 4 ) Δ 3 4 ( X ) = d 0 + W 2 ( X ) W 2 ( ω 4 ) d 4 , Δ 2 1 ( X ) = Δ 3 1 ( X ) + W 2 ( X ) W 2 ( ω 4 ) Δ 3 5 ( X ) = d 1 + W 2 ( X ) W 2 ( ω 4 ) d 5 , Δ 2 2 ( X ) = Δ 3 2 ( X ) + W 2 ( X ) W 2 ( ω 4 ) Δ 3 6 ( X ) = d 2 + W 2 ( X ) W 2 ( ω 4 ) d 6 , Δ 2 3 ( X ) = Δ 3 3 ( X ) + W 2 ( X ) W 2 ( ω 4 ) Δ 3 7 ( X ) = d 3 + W 2 ( X ) W 2 ( ω 4 ) d 7 , Δ 1 0 ( X ) = Δ 2 0 ( X ) + W 1 ( X ) W 1 ( ω 2 ) Δ 2 2 ( X ) , Δ 1 1 ( X ) = Δ 2 1 ( X ) + W 1 ( X ) W 1 ( ω 2 ) Δ 2 3 ( X ) , Δ 0 0 ( X ) = Δ 1 0 ( X ) + W 0 ( X ) W 0 ( ω 1 ) Δ 1 1 ( X ) \Delta^0_3(X) = d_0,\Delta^1_3(X) = d_1, \Delta^2_3(X) = d_2, \dots, \Delta^7_3(X) = d_7, \\
\Delta^0_2(X) = \Delta^0_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^4_3(X) = d_0 + \frac{W_2(X)}{W_2(\omega_4)}d_4, \\
\Delta^1_2(X) = \Delta^1_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^5_3(X) = d_1 + \frac{W_2(X)}{W_2(\omega_4)}d_5, \\
\Delta^2_2(X) = \Delta^2_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^6_3(X) = d_2 + \frac{W_2(X)}{W_2(\omega_4)}d_6, \\
\Delta^3_2(X) = \Delta^3_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^7_3(X) = d_3 + \frac{W_2(X)}{W_2(\omega_4)}d_7, \\
\Delta^0_1(X) = \Delta^0_2(X) + \frac{W_1(X)}{W_1(\omega_2)} \Delta^2_2(X), \\
\Delta^1_1(X) = \Delta^1_2(X) + \frac{W_1(X)}{W_1(\omega_2)} \Delta^3_2(X), \\
\Delta^0_0(X) = \Delta^0_1(X) + \frac{W_0(X)}{W_0(\omega_1)} \Delta^1_1(X) Δ 3 0 ( X ) = d 0 , Δ 3 1 ( X ) = d 1 , Δ 3 2 ( X ) = d 2 , … , Δ 3 7 ( X ) = d 7 , Δ 2 0 ( X ) = Δ 3 0 ( X ) + W 2 ( ω 4 ) W 2 ( X ) Δ 3 4 ( X ) = d 0 + W 2 ( ω 4 ) W 2 ( X ) d 4 , Δ 2 1 ( X ) = Δ 3 1 ( X ) + W 2 ( ω 4 ) W 2 ( X ) Δ 3 5 ( X ) = d 1 + W 2 ( ω 4 ) W 2 ( X ) d 5 , Δ 2 2 ( X ) = Δ 3 2 ( X ) + W 2 ( ω 4 ) W 2 ( X ) Δ 3 6 ( X ) = d 2 + W 2 ( ω 4 ) W 2 ( X ) d 6 , Δ 2 3 ( X ) = Δ 3 3 ( X ) + W 2 ( ω 4 ) W 2 ( X ) Δ 3 7 ( X ) = d 3 + W 2 ( ω 4 ) W 2 ( X ) d 7 , Δ 1 0 ( X ) = Δ 2 0 ( X ) + W 1 ( ω 2 ) W 1 ( X ) Δ 2 2 ( X ) , Δ 1 1 ( X ) = Δ 2 1 ( X ) + W 1 ( ω 2 ) W 1 ( X ) Δ 2 3 ( X ) , Δ 0 0 ( X ) = Δ 1 0 ( X ) + W 0 ( ω 1 ) W 0 ( X ) Δ 1 1 ( X ) [ D n ] ( X ) [D_n](X) [ D n ] ( X ) Δ 0 0 ( X ) \Delta^0_0(X) Δ 0 0 ( X ) [ D 8 ] ( X ) [D_8](X) [ D 8 ] ( X )
[ D 8 ] ( X ) = ∑ i = 0 7 d i X i ( X ) = d 0 + d 1 W 0 ( X ) W 0 ( ω 1 ) + d 2 W 1 ( X ) W 1 ( ω 2 ) + d 3 W 0 ( X ) W 1 ( X ) W 0 ( ω 1 ) W 1 ( ω 2 ) + d 4 W 2 ( X ) W 2 ( ω 4 ) d 5 W 0 ( X ) W 2 ( X ) W 0 ( ω 1 ) W 2 ( ω 4 ) + d 6 W 1 ( X ) W 2 ( X ) W 1 ( ω 2 ) W 2 ( ω 4 ) + d 7 W 0 ( X ) W 1 ( X ) W 2 ( X ) W 0 ( ω 1 ) W 1 ( ω 2 ) W 2 ( ω 4 ) = ( d 0 + d 4 W 2 ( X ) W 2 ( ω 4 ) + W 1 ( X ) W 1 ( ω 2 ) ( d 2 + d 6 W 2 ( X ) W 2 ( ω 4 ) ) ) + W 0 ( X ) W 0 ( ω 1 ) ( d 1 + d 5 W 2 ( X ) W 2 ( ω 4 ) + W 1 ( X ) W 1 ( ω 2 ) ( d 3 + d 7 W 2 ( X ) W 2 ( ω 4 ) ) ) = ( Δ 2 0 ( X ) + W 1 ( X ) W 1 ( ω 2 ) Δ 2 2 ( X ) ) + W 0 ( X ) W 0 ( ω 1 ) ( Δ 2 1 ( X ) + W 1 ( X ) W 1 ( ω 2 ) Δ 2 3 ( X ) ) = Δ 1 0 ( X ) + W 0 ( X ) W 0 ( ω 1 ) Δ 1 1 ( X ) = Δ 0 0 ( X ) \begin{align*} [D_8](X) &= \sum_{i = 0}^{7} d_iX_i(X) \\ &=d_0 + d_1\frac{W_0(X)}{W_0(\omega_1)} + d_2\frac{W_1(X)}{W_1(\omega_2)} + d_3\frac{W_0(X)W_1(X)}{W_0(\omega_1)W_1(\omega_2)} + d_4\frac{W_2(X)}{W_2(\omega_4)} \\ &\space\space\space\space\space d_5\frac{W_0(X)W_2(X)}{W_0(\omega_1)W_2(\omega_4)} + d_6\frac{W_1(X)W_2(X)}{W_1(\omega_2)W_2(\omega_4)} + d_7\frac{W_0(X)W_1(X)W_2(X)}{W_0(\omega_1)W_1(\omega_2)W_2(\omega_4)} \\ &=\bigg(d_0 + d_4\frac{W_2(X)}{W_2(\omega_4)} + \frac{W_1(X)}{W_1(\omega_2)}\bigg( d_2 + d_6\frac{W_2(X)}{W_2(\omega_4)}\bigg)\bigg) \\ &\space\space\space\space\space + \frac{W_0(X)}{W_0(\omega_1)}\bigg(d_1 + d_5\frac{W_2(X)}{W_2(\omega_4)} + \frac{W_1(X)}{W_1(\omega_2)}\bigg(d_3 + d_7\frac{W_2(X)}{W_2(\omega_4)} \bigg) \bigg) \\ &=\bigg(\Delta^0_2(X) + \frac{W_1(X)}{W_1(\omega_2)}\Delta^2_2(X) \bigg) + \frac{W_0(X)}{W_0(\omega_1)}\bigg( \Delta^1_2(X) + \frac{W_1(X)}{W_1(\omega_2)}\Delta^3_2(X) \bigg) \\ &= \Delta^0_1(X) + \frac{W_0(X)}{W_0(\omega_1)}\Delta^1_1(X) \\ &= \Delta^0_0(X) \end{align*} [ D 8 ] ( X ) = i = 0 ∑ 7 d i X i ( X ) = d 0 + d 1 W 0 ( ω 1 ) W 0 ( X ) + d 2 W 1 ( ω 2 ) W 1 ( X ) + d 3 W 0 ( ω 1 ) W 1 ( ω 2 ) W 0 ( X ) W 1 ( X ) + d 4 W 2 ( ω 4 ) W 2 ( X ) d 5 W 0 ( ω 1 ) W 2 ( ω 4 ) W 0 ( X ) W 2 ( X ) + d 6 W 1 ( ω 2 ) W 2 ( ω 4 ) W 1 ( X ) W 2 ( X ) + d 7 W 0 ( ω 1 ) W 1 ( ω 2 ) W 2 ( ω 4 ) W 0 ( X ) W 1 ( X ) W 2 ( X ) = ( d 0 + d 4 W 2 ( ω 4 ) W 2 ( X ) + W 1 ( ω 2 ) W 1 ( X ) ( d 2 + d 6 W 2 ( ω 4 ) W 2 ( X ) ) ) + W 0 ( ω 1 ) W 0 ( X ) ( d 1 + d 5 W 2 ( ω 4 ) W 2 ( X ) + W 1 ( ω 2 ) W 1 ( X ) ( d 3 + d 7 W 2 ( ω 4 ) W 2 ( X ) ) ) = ( Δ 2 0 ( X ) + W 1 ( ω 2 ) W 1 ( X ) Δ 2 2 ( X ) ) + W 0 ( ω 1 ) W 0 ( X ) ( Δ 2 1 ( X ) + W 1 ( ω 2 ) W 1 ( X ) Δ 2 3 ( X ) ) = Δ 1 0 ( X ) + W 0 ( ω 1 ) W 0 ( X ) Δ 1 1 ( X ) = Δ 0 0 ( X ) Lemma 2. Δ i m ( X + Y ) = Δ i m ( X ) , ∀ Y ∈ { ω b } b = 0 2 i − 1 \Delta^m_i(X + Y) = \Delta^m_i(X), \forall Y \in \{\omega_b\}_{b = 0}^{2^i - 1} Δ i m ( X + Y ) = Δ i m ( X ) , ∀ Y ∈ { ω b } b = 0 2 i − 1
Proof:
Case 1: i = log 2 n i = \log_2 n i = log 2 n Δ i m ( X + Y ) \Delta^m_i(X + Y) Δ i m ( X + Y ) Δ i m ( X ) \Delta^m_i(X) Δ i m ( X ) d m d_m d m
Case 2: i = log 2 n − 1 i = \log_2 n - 1 i = log 2 n − 1 Δ i m ( X ) \Delta^m_i(X) Δ i m ( X )
Δ log 2 n − 1 m ( X ) = Δ log 2 n m ( X ) + W log 2 n − 1 ( X ) W log 2 n − 1 ( ω 2 log 2 n − 1 ) Δ log 2 n m + 2 log 2 n − 1 ( X ) = d m + W log 2 n − 1 ( X ) W log 2 n − 1 ( ω 2 log 2 n − 1 ) d m + 2 log 2 n − 1 \begin{align*} \Delta^m_{\log_2 n - 1}(X) &= \Delta^m_{\log_2 n}(X) + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} \Delta^{m + 2^{\log_2 n - 1}}_{\log_2 n}(X) \\
&= d_m + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}} \end{align*} Δ l o g 2 n − 1 m ( X ) = Δ l o g 2 n m ( X ) + W l o g 2 n − 1 ( ω 2 l o g 2 n − 1 ) W l o g 2 n − 1 ( X ) Δ l o g 2 n m + 2 l o g 2 n − 1 ( X ) = d m + W l o g 2 n − 1 ( ω 2 l o g 2 n − 1 ) W l o g 2 n − 1 ( X ) d m + 2 l o g 2 n − 1 which simplifies as follows:
Δ log 2 n − 1 m ( X + Y ) = d m + W log 2 n − 1 ( X + Y ) W log 2 n − 1 ( ω 2 log 2 n − 1 ) d m + 2 log 2 n − 1 \Delta^m_{\log_2 n - 1}(X + Y)
= d_m + \frac{W_{\log_2 n - 1}(X + Y)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}} Δ l o g 2 n − 1 m ( X + Y ) = d m + W l o g 2 n − 1 ( ω 2 l o g 2 n − 1 ) W l o g 2 n − 1 ( X + Y ) d m + 2 l o g 2 n − 1 Using Lemma 1 :
W log 2 n − 1 ( X + Y ) = W log 2 n − 1 ( X ) + W log 2 n − 1 ( Y ) W_{\log_2 n - 1}(X + Y) = W_{\log_2 n - 1}(X) + W_{\log_2 n - 1}(Y) W l o g 2 n − 1 ( X + Y ) = W l o g 2 n − 1 ( X ) + W l o g 2 n − 1 ( Y ) Since Y ∈ { ω b } b = 0 2 i − 1 Y \in \{\omega_b\}_{b=0}^{2^i - 1} Y ∈ { ω b } b = 0 2 i − 1 W log 2 n − 1 ( Y ) = 0 W_{\log_2 n - 1}(Y) = 0 W l o g 2 n − 1 ( Y ) = 0
Δ log 2 n − 1 m ( X + Y ) = d m + W log 2 n − 1 ( X ) W log 2 n − 1 ( ω 2 log 2 n − 1 ) d m + 2 log 2 n − 1 = Δ log 2 n − 1 m ( X ) \begin{align*}
\Delta^m_{\log_2 n - 1}(X + Y)
&= d_m + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}} \\
&= \Delta^m_{\log_2 n -1}(X)
\end{align*} Δ l o g 2 n − 1 m ( X + Y ) = d m + W l o g 2 n − 1 ( ω 2 l o g 2 n − 1 ) W l o g 2 n − 1 ( X ) d m + 2 l o g 2 n − 1 = Δ l o g 2 n − 1 m ( X ) Case 3: Inductive Step
Assume the equality holds for i = c + 1 i = c+ 1 i = c + 1
Δ c m ( X + Y ) = Δ c + 1 m ( X + Y ) + W c ( X + Y ) W c ( ω 2 c ) Δ c + 1 m + 2 c ( X + Y ) \Delta^m_{c}(X + Y) = \Delta^m_{c + 1}(X + Y) + \frac{W_{c}(X + Y)}{W_{c}(\omega_{2^c})} \Delta^{m + 2^c}_{c + 1}(X + Y) Δ c m ( X + Y ) = Δ c + 1 m ( X + Y ) + W c ( ω 2 c ) W c ( X + Y ) Δ c + 1 m + 2 c ( X + Y ) By Lemma 1 :
W c ( X + Y ) = W c ( X ) + W c ( Y ) W_c(X + Y) = W_c(X) + W_c(Y) W c ( X + Y ) = W c ( X ) + W c ( Y ) Since Y ∈ { ω b } b = 0 2 c − 1 Y \in \{\omega_b\}_{b=0}^{2^c - 1} Y ∈ { ω b } b = 0 2 c − 1 W c ( Y ) = 0 W_{c}(Y) = 0 W c ( Y ) = 0
Δ c m ( X + Y ) = Δ c + 1 m ( X + Y ) + W c ( X ) W c ( ω 2 c ) Δ c + 1 m + 2 c ( X + Y ) = Δ c m ( X ) \begin{align*}
\Delta^m_{c}(X + Y) &= \Delta^m_{c + 1}(X + Y) + \frac{W_{c}(X)}{W_{c}(\omega_{2^c})} \Delta^{m + 2^c}_{c + 1}(X + Y) \\
&= \Delta^m_c(X)
\end{align*} Δ c m ( X + Y ) = Δ c + 1 m ( X + Y ) + W c ( ω 2 c ) W c ( X ) Δ c + 1 m + 2 c ( X + Y ) = Δ c m ( X ) Define the transform Ψ \Psi Ψ
Ψ ( i , m , l ) = { { Δ i m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i } b = 0 n / 2 i − 1 } if 0 ≤ i < log 2 n { d m } if i = log 2 n \Psi(i, m, l) = \begin{cases} \{ \Delta^m_i(\omega_c + \omega_l)| c \in \{b \cdot 2^i\}^{n/2^i - 1}_{b = 0} \} & \text{ if } 0 \le i < \log_2 n \\ \{d_m\} & \text{ if } i = \log_2n \end{cases} Ψ ( i , m , l ) = { { Δ i m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i } b = 0 n / 2 i − 1 } { d m } if 0 ≤ i < log 2 n if i = log 2 n where 0 ≤ m < 2 i 0 \le m < 2^i 0 ≤ m < 2 i
The transform computes { Ψ ( log 2 n , k , l ) ∣ k ∈ [ 0 , n − 1 ] } → Ψ ( 0 , 0 , l ) \{\Psi(\log_2 n, k, l)|k \in [0, n-1]\} \rightarrow \Psi(0, 0, l) { Ψ ( log 2 n , k , l ) ∣ k ∈ [ 0 , n − 1 ]} → Ψ ( 0 , 0 , l ) n = 8 n = 8 n = 8
{ d 0 , d 1 , d 2 … , d 7 } = Ψ ( 3 , 0 , l ) ∪ Ψ ( 3 , 1 , l ) ∪ Ψ ( 3 , 2 , l ) ∪ ⋯ ∪ Ψ ( 3 , 7 , l ) → { Δ 0 0 ( ω 0 + ω l ) , Δ 0 0 ( ω 1 + ω l ) , Δ 0 0 ( ω 2 + ω l ) , … , Δ 0 0 ( ω 7 + ω l ) } = Ψ ( 0 , 0 , l ) \{d_0, d_1, d_2 \dots, d_{7}\} = \Psi(3, 0, l) \cup \Psi(3, 1, l) \cup \Psi(3, 2, l) \cup \cdots \cup \Psi(3, 7, l) \\ \rightarrow \{\Delta^0_0(\omega_0 + \omega_l),\Delta^0_0(\omega_1 + \omega_l), \Delta^0_0(\omega_2 + \omega_l), \dots, \Delta^0_0(\omega_{7} + \omega_l)\} = \Psi(0, 0, l) { d 0 , d 1 , d 2 … , d 7 } = Ψ ( 3 , 0 , l ) ∪ Ψ ( 3 , 1 , l ) ∪ Ψ ( 3 , 2 , l ) ∪ ⋯ ∪ Ψ ( 3 , 7 , l ) → { Δ 0 0 ( ω 0 + ω l ) , Δ 0 0 ( ω 1 + ω l ) , Δ 0 0 ( ω 2 + ω l ) , … , Δ 0 0 ( ω 7 + ω l )} = Ψ ( 0 , 0 , l ) Remember that Δ 0 0 ( X ) \Delta^0_0(X) Δ 0 0 ( X ) [ D n ] ( X ) [D_n](X) [ D n ] ( X )
Ψ ( i , m , l ) \Psi(i, m, l) Ψ ( i , m , l )
{ Δ i m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } \{\Delta^m_i(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} { Δ i m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } Ψ ( i + 1 , m , l ) \Psi(i + 1, m, l) Ψ ( i + 1 , m , l )
{ Δ i m ( ω c + ω l + ω 2 i ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } \{\Delta^m_i(\omega_c + \omega_l + \omega_{2^i})| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} { Δ i m ( ω c + ω l + ω 2 i ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } Ψ ( i + 1 , m + 2 i , l ) \Psi(i + 1, m +2^i, l) Ψ ( i + 1 , m + 2 i , l )
Part 1. Ψ ( i + 1 , m , l ) \Psi(i + 1, m, l) Ψ ( i + 1 , m , l )
Δ i m ( ω c + ω l ) = Δ i + 1 m ( ω c + ω l ) + W i ( ω c + ω l ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) \Delta^m_i(\omega_c + \omega_l) = \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) Δ i m ( ω c + ω l ) = Δ i + 1 m ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω c + ω l ) Δ i + 1 m + 2 i ( ω c + ω l ) Since all the right-hand terms are known, the left-hand terms can be determined.
Part 2. Ψ ( i + 1 , m + 2 i , l ) \Psi(i + 1, m + 2^i, l) Ψ ( i + 1 , m + 2 i , l )
Δ i m ( ω c + ω l + ω 2 i ) = Δ i + 1 m ( ω c + ω l + ω 2 i ) + W i ( ω c + ω l + ω 2 i ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l + ω 2 i ) = Δ i + 1 m ( ω c + ω l ) + W i ( ω c + ω l + ω 2 i ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) ∵ Lemma 2. = Δ i + 1 m ( ω c + ω l ) + W i ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) ∵ Lemma 1. = Δ i + 1 m ( ω c + ω l ) + W i ( ω c + ω l ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) + Δ i + 1 m + 2 i ( ω c + ω l ) = Δ i m ( ω c + ω l ) + Δ i + 1 m + 2 i ( ω c + ω l ) \begin{align*}
\Delta^m_i(\omega_c + \omega_l + \omega_{2^i}) &= \Delta^m_{i+1}(\omega_c + \omega_l + \omega_{2^i}) + \frac{W_i(\omega_c + \omega_l + \omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l + \omega{2^i})
\\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l + \omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) \because \text{Lemma } 2.
\\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l) + W_i(\omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) \because \text{Lemma } 1.
\\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) + \Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l)
\\ &= \Delta^m_i(\omega_c + \omega_l) + \Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l) \end{align*} Δ i m ( ω c + ω l + ω 2 i ) = Δ i + 1 m ( ω c + ω l + ω 2 i ) + W i ( ω 2 i ) W i ( ω c + ω l + ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l + ω 2 i ) = Δ i + 1 m ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω c + ω l + ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) ∵ Lemma 2. = Δ i + 1 m ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω c + ω l ) + W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) ∵ Lemma 1. = Δ i + 1 m ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω c + ω l ) Δ i + 1 m + 2 i ( ω c + ω l ) + Δ i + 1 m + 2 i ( ω c + ω l ) = Δ i m ( ω c + ω l ) + Δ i + 1 m + 2 i ( ω c + ω l ) Since Δ i m ( ω c + ω l ) \Delta^m_i(\omega_c + \omega_l) Δ i m ( ω c + ω l )
When n = 8 , i = 2 n=8, i=2 n = 8 , i = 2 Ψ ( 2 , m , l ) \Psi(2, m, l) Ψ ( 2 , m , l ) Ψ ( 3 , m , l ) = { d m } \Psi(3,m , l) = \{d_m\} Ψ ( 3 , m , l ) = { d m } Ψ ( 3 , m + 4 , l ) = Δ 3 m + 4 ( X ) = { d m + 4 } \Psi(3, m + 4, l) = \Delta^{m+4}_3(X) =\{d_{m+4}\} Ψ ( 3 , m + 4 , l ) = Δ 3 m + 4 ( X ) = { d m + 4 }
Ψ ( 2 , m , l ) = { Δ 2 m ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l ) } = { Δ 3 m ( ω 0 + ω l ) + W 2 ( ω 0 + ω l ) W 2 ( ω 4 ) Δ 3 m + 4 ( ω 0 + ω l ) , Δ 3 m ( ω 4 + ω l ) + W 2 ( ω 4 + ω l ) W 2 ( ω 4 ) Δ 3 m + 4 ( ω 4 + ω l ) } = { d m + W 2 ( ω 0 + ω l ) W 2 ( ω 4 ) d m + 4 , d m + W 2 ( ω 4 + ω l ) W 2 ( ω 4 ) d m + 4 } \begin{align*}
\Psi(2, m, l) &= \{\Delta^m_2(\omega_0 + \omega_l),\Delta^m_2(\omega_4 + \omega_l)\}
\\ &= \{\Delta^m_3(\omega_0 + \omega_l) + \frac{W_2(\omega_0 + \omega_l)}{W_2(\omega_4)}\Delta^{m + 4}_3(\omega_0 + \omega_l), \Delta^m_3(\omega_4 + \omega_l) + \frac{W_2(\omega_4 + \omega_l)}{W_2(\omega_4)}\Delta^{m + 4}_3(\omega_4 + \omega_l) \}
\\ &= \{d_m + \frac{W_2(\omega_0 + \omega_l)}{W_2(\omega_4)}d_{m+4}, d_m + \frac{W_2(\omega_4 + \omega_l)}{W_2(\omega_4)}d_{m+4} \}
\end{align*} Ψ ( 2 , m , l ) = { Δ 2 m ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l )} = { Δ 3 m ( ω 0 + ω l ) + W 2 ( ω 4 ) W 2 ( ω 0 + ω l ) Δ 3 m + 4 ( ω 0 + ω l ) , Δ 3 m ( ω 4 + ω l ) + W 2 ( ω 4 ) W 2 ( ω 4 + ω l ) Δ 3 m + 4 ( ω 4 + ω l )} = { d m + W 2 ( ω 4 ) W 2 ( ω 0 + ω l ) d m + 4 , d m + W 2 ( ω 4 ) W 2 ( ω 4 + ω l ) d m + 4 } When n = 8 , i = 1 n=8, i=1 n = 8 , i = 1 Ψ ( 1 , m , l ) \Psi(1, m, l) Ψ ( 1 , m , l ) Ψ ( 2 , m , l ) = { Δ 2 m ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l ) } \Psi(2, m, l) = \{\Delta^m_2(\omega_0 + \omega_l), \Delta^m_2(\omega_4 + \omega_l)\} Ψ ( 2 , m , l ) = { Δ 2 m ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l )} Ψ ( 2 , m + 2 , l ) = { Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m + 2 ( ω 4 + ω l ) } \Psi(2, m + 2, l) = \{\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^{m + 2}_2(\omega_4 + \omega_l)\} Ψ ( 2 , m + 2 , l ) = { Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m + 2 ( ω 4 + ω l )}
Ψ ( 1 , m , l ) = { Δ 1 m ( ω 0 + ω l ) , Δ 1 m ( ω 2 + ω l ) , Δ 1 m ( ω 4 + ω l ) , Δ 1 m ( ω 6 + ω l ) } = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 0 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 2 + ω l ) + W 1 ( ω 2 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 2 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 4 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 6 + ω l ) + W 1 ( ω 6 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 6 + ω l ) } = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 0 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 0 + ω l + ω 2 ) + W 1 ( ω 0 + ω l + ω 2 ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 0 + ω l + ω 2 ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 4 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 4 + ω l + ω 2 ) + W 1 ( ω 4 + ω l + ω 2 ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 4 + ω l + ω 2 ) } = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 0 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 0 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 4 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 4 + ω l ) W 1 ( ω 2 ) Δ 2 m + 2 ( ω 4 + ω l ) } \begin{align*}\Psi(1, m, l) &= \{\Delta^m_1(\omega_0 + \omega_l),\Delta^m_1(\omega_2 + \omega_l),\Delta^m_1(\omega_4 + \omega_l),\Delta^m_1(\omega_6 + \omega_l)\} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_2 + \omega_l) + \frac{W_1(\omega_2 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_2 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_6 + \omega_l) + \frac{W_1(\omega_6 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_6 + \omega_l) \} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_0 + \omega_l + \omega_2) + \frac{W_1(\omega_0 + \omega_l + \omega_2)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l + \omega_2), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_4 + \omega_l + \omega_2) + \frac{W_1(\omega_4 + \omega_l + \omega_2)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l + \omega_2) \} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l) \} \\ \end{align*} Ψ ( 1 , m , l ) = { Δ 1 m ( ω 0 + ω l ) , Δ 1 m ( ω 2 + ω l ) , Δ 1 m ( ω 4 + ω l ) , Δ 1 m ( ω 6 + ω l )} = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 0 + ω l ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 2 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 2 + ω l ) Δ 2 m + 2 ( ω 2 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 4 + ω l ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 6 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 6 + ω l ) Δ 2 m + 2 ( ω 6 + ω l )} = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 0 + ω l ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 0 + ω l + ω 2 ) + W 1 ( ω 2 ) W 1 ( ω 0 + ω l + ω 2 ) Δ 2 m + 2 ( ω 0 + ω l + ω 2 ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 4 + ω l ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 4 + ω l + ω 2 ) + W 1 ( ω 2 ) W 1 ( ω 4 + ω l + ω 2 ) Δ 2 m + 2 ( ω 4 + ω l + ω 2 )} = { Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 0 + ω l ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 0 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 0 + ω l ) Δ 2 m + 2 ( ω 0 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 4 + ω l ) Δ 2 m + 2 ( ω 4 + ω l ) , Δ 2 m ( ω 4 + ω l ) + W 1 ( ω 2 ) W 1 ( ω 4 + ω l ) Δ 2 m + 2 ( ω 4 + ω l )} To compute Ψ ( i + 1 , m , l ) \Psi(i + 1, m, l) Ψ ( i + 1 , m , l ) Ψ ( i + 1 , m + 2 i , l ) \Psi(i + 1, m + 2^i, l) Ψ ( i + 1 , m + 2 i , l ) Ψ ( i , m , l ) \Psi(i, m, l) Ψ ( i , m , l )
Part 1. Ψ ( i + 1 , m + 2 i , l ) \Psi(i + 1, m + 2^i, l) Ψ ( i + 1 , m + 2 i , l )
Ψ ( i + 1 , m + 2 i , l ) = { Δ i + 1 m + 2 i ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } \Psi(i + 1, m + 2^i, l) = \{\Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} Ψ ( i + 1 , m + 2 i , l ) = { Δ i + 1 m + 2 i ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } where: (Refer to Part 2. in Transform section above.)
Δ i + 1 m + 2 i ( ω c + ω l ) = Δ i m ( ω c + ω l ) + Δ i m ( ω c + ω l + ω 2 i ) \Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l) = \Delta^m_i(\omega_c + \omega_l) + \Delta^m_i(\omega_c + \omega_l + \omega_{2^i}) Δ i + 1 m + 2 i ( ω c + ω l ) = Δ i m ( ω c + ω l ) + Δ i m ( ω c + ω l + ω 2 i ) Since all the right-hand terms are known, the left-hand terms can be determined.
Part 2. Ψ ( i + 1 , m , l ) \Psi(i + 1, m, l) Ψ ( i + 1 , m , l )
Ψ ( i + 1 , m , l ) = { Δ i + 1 m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } \Psi(i + 1, m, l) = \{\Delta^{m }_{i+1}(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} Ψ ( i + 1 , m , l ) = { Δ i + 1 m ( ω c + ω l ) ∣ c ∈ { b ⋅ 2 i + 1 } b = 0 n / 2 i + 1 − 1 } where (Refer to Part 1. in Transform section above):
Δ i + 1 m ( ω c + ω l ) = Δ i m ( ω c + ω l ) + W i ( ω c + ω l ) W i ( ω 2 i ) Δ i + 1 m + 2 i ( ω c + ω l ) \Delta^{m}_{i+1}(\omega_c + \omega_l) = \Delta^m_i(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l) Δ i + 1 m ( ω c + ω l ) = Δ i m ( ω c + ω l ) + W i ( ω 2 i ) W i ( ω c + ω l ) Δ i + 1 m + 2 i ( ω c + ω l ) Since Δ i m ( ω c + ω l ) \Delta^m_i(\omega_c + \omega_l) Δ i m ( ω c + ω l )
The diagram above illustrates the data dependencies for transforming and inversely transforming a polynomial of size 8. Each element is computed as the sum of a solid-line element and a dashed-line element, where the la tter represents scalar multiplication by W ^ i j \widehat{W}^j_i W i j
W ^ i j = W i ( ω j ) W i ( ω 2 i ) \widehat{W}^j_i = \frac{W_i(\omega_j)}{W_i(\omega_{2^i})} W i j = W i ( ω 2 i ) W i ( ω j ) Conclusion
The method for performing a formal derivative on the Novel Polynomial Basis and its use in the RS erasure decoding algorithm is omitted here due to space constraints. For those interested, please refer to the original paper.
Using the newly proposed Novel Polynomial Basis, the Additive NTT achieves O ( n log n ) O(n \log n) O ( n log n ) O ( n log n ) O(n \log n) O ( n log n ) O ( n log n ) O(n \log n) O ( n log n )
Additionally, it is well-known that polynomial multiplication can be optimized using FFT. Similarly, by leveraging the Novel Polynomial Basis, multiplication in characteristic-2 finite fields can also be optimized.
