# Matrices and discrete Fourier transform

Consider $\operatorname{GF}(16)$; denote by $\mathfrak A$ its primitive element.

Input stripe $$(Y_0,Y_1,\dots,Y_{14} ) , \quad Y_j\in \operatorname{GF}(16) \ .$$ $$G(\mathfrak x):=Y_0+Y_1 \mathfrak x + \dots + Y_{14} \mathfrak x^{14}$$ $$G(\mathfrak e)=\mathfrak o,\ G(\mathfrak A)= \mathfrak o,\ G(\mathfrak A^2)= \mathfrak o,\ G(\mathfrak A^3)= \mathfrak o \, .$$ (possibility to correct up to $2_{}$ SDCs).

Output stripe $$(\widetilde Y_0, \widetilde Y_1,\dots, \widetilde Y_{14}) \ .$$

Th

Theorem 1. There exists a unique polynomial $H(\mathfrak x)$ over $\operatorname{GF}(16)$ such that $$H(\mathfrak A^{-1})=Y_{14},\ H(\mathfrak A^{-2})=Y_{13},\dots, H(\mathfrak A^{-15})=H(\mathfrak e)=Y_{0} \, .$$

§

It is claimed the existence of the «interpolation» polynomial with the number of indeterminate coefficients equal to $11$, i.e. the $15$ equalities from the theorem are evidently redundant.

$$\left(\begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^{-14} & (\mathfrak A^{-14})^2 & \dots & (\mathfrak A^{-14})^{10} \\ \mathfrak e & \mathfrak A^{-13} & (\mathfrak A^{-13})^2 & \dots & (\mathfrak A^{-13})^{10} \\ \vdots & & & & \vdots \\ \mathfrak e & \mathfrak A^{-2} & (\mathfrak A^{-2})^2 & \dots & (\mathfrak A^{-2})^{10} \\ \mathfrak e & \mathfrak A^{-1} & \mathfrak A^{-2} & \dots & \mathfrak A^{-10} \end{array} \right)_{15\times 11} \left(\begin{array}{l} H_0 \\ H_1 \\ \vdots \\ H_{10} \end{array} \right)= \left(\begin{array}{l} Y_0 \\ Y_1 \\ \vdots \\ Y_{14} \end{array} \right) \ .$$

Th

Theorem 2. The following equalities are fulfilled $$H_{10}=G(\mathfrak A^5),\ H_9=G(\mathfrak A^6),\dots, H_0= G(\mathfrak A^{15})= G(\mathfrak e) \ ,$$ i.e. the coefficients of the «interpolation» polynomial $H(\mathfrak x)$ turn out to be the values of the code polynomial $G(\mathfrak x)$ on the set $\mathfrak A^5,\mathfrak A^6, \dots, \mathfrak A^{15}$.

Proof. Multiply the system of linear equations from the previous theorem from the left-hand side by the matrix $$\left(\begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^{14} & (\mathfrak A^{14})^2 & \dots & (\mathfrak A^{14})^{14} \\ \mathfrak e & \mathfrak A^{13} & (\mathfrak A^{13})^2 & \dots & (\mathfrak A^{13})^{14} \\ \vdots & & & & \vdots \\ \mathfrak e & \mathfrak A^{6} & (\mathfrak A^{6})^2 & \dots & (\mathfrak A^{6})^{14} \\ \mathfrak e & \mathfrak A^{5} & (\mathfrak A^{5})^2 & \dots & (\mathfrak A^{5})^{14} \end{array} \right)_{11\times 15} \ .$$ The obtained matrix equation has in its right-hand side the column $$\left(\begin{array}{c} Y_0+Y_1+\dots+Y_{14} \\ Y_0+Y_1\mathfrak A^{14}+ Y_2 (\mathfrak A^{14})^2 + \dots + Y_{14} (\mathfrak A^{14})^{14} \\ Y_0+Y_1\mathfrak A^{13}+ Y_2 (\mathfrak A^{13})^2 + \dots + Y_{14} (\mathfrak A^{13})^{14} \\ \vdots \\ Y_0+Y_1\mathfrak A^{5}+ Y_2 (\mathfrak A^{5})^2 + \dots + Y_{14} (\mathfrak A^{5})^{14} \end{array} \right)= \left(\begin{array}{c} G(\mathfrak e) \\ G(\mathfrak A^{14}) \\ G(\mathfrak A^{13}) \\ \vdots \\ G(\mathfrak A^{5}) \end{array} \right) \ ;$$ i.e. the column entries coincide with the right-hand sides of the equalities from the theorem statement.

Perform now the matrix multiplication $$\left(\begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^{14} & (\mathfrak A^{14})^2 & \dots & (\mathfrak A^{14})^{14} \\ \mathfrak e & \mathfrak A^{13} & (\mathfrak A^{13})^2 & \dots & (\mathfrak A^{13})^{14} \\ \vdots & & & & \vdots \\ \mathfrak e & \mathfrak A^{6} & (\mathfrak A^{6})^2 & \dots & (\mathfrak A^{6})^{14} \\ \mathfrak e & \mathfrak A^{5} & (\mathfrak A^{5})^2 & \dots & (\mathfrak A^{5})^{14} \end{array} \right) \left(\begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^{-14} & (\mathfrak A^{-14})^2 & \dots & (\mathfrak A^{-14})^{10} \\ \mathfrak e & \mathfrak A^{-13} & (\mathfrak A^{-13})^2 & \dots & (\mathfrak A^{-13})^{10} \\ \vdots & & & & \vdots \\ \mathfrak e & \mathfrak A^{-2} & (\mathfrak A^{-2})^2 & \dots & (\mathfrak A^{-2})^{10} \\ \mathfrak e & \mathfrak A^{-1} & \mathfrak A^{-2} & \dots & \mathfrak A^{-10} \end{array} \right)$$ Compute the entries of the fisrt row: $$\underbrace{\mathfrak e+\mathfrak e+\dots+\mathfrak e}_{15}=\mathfrak e .$$ $$\mathfrak e + \mathfrak A^{-14} + \mathfrak A^{-13} + \dots + \mathfrak A^{-1} = \frac{(\mathfrak A^{-1})^{15}-\mathfrak e}{\mathfrak A^{-1}-\mathfrak e}=\mathfrak o$$ since, due to generalized Fermat theorem, $(\mathfrak A^{-1})^{15}=\mathfrak e$. The third entry equals $$\mathfrak e + (\mathfrak A^{-2})^{14} + (\mathfrak A^{-2})^{13} + \dots + \mathfrak A^{-2}= \mathfrak e + (\mathfrak A^{-14})^2 + (\mathfrak A^{-13})^2 + \dots + \mathfrak A^{-2} = \frac{(\mathfrak A^{-2})^{15}-\mathfrak e}{\mathfrak A^{-2}-\mathfrak e}=\mathfrak o$$ due to similar reason. And so forth. All the entries of the first row of the matrix, except for the first one, equal $\mathfrak o$, i.e. it is just $$[\mathfrak e,\mathfrak o,\mathfrak o,\dots,\mathfrak o] .$$ One can make a hypothesis that the second row of the matrix product equals $$[\mathfrak o,\mathfrak e,\mathfrak o,\dots,\mathfrak o] ,$$ and extend this hypothesis to the other rows. That means: the product of two non-square matrices is a square identity matrix. It can be verified by a direct computation, while for the general case it follows from the theory of discrete Fourier transform.

Wherefrom follows the statement of the theorem.

§

The results of Theorems 1 and 2 state that the polynomials $G(\mathfrak x)$ and $H(\mathfrak x)$ reciprocally define each other.

# The error correction scheme

If the output stripe $$(\widetilde Y_0, \widetilde Y_1,\dots, \widetilde Y_{14})$$ meats the conditions $$\widetilde G(\mathfrak e)=\mathfrak o,\ \widetilde G(\mathfrak A)= \mathfrak o,\ \widetilde G(\mathfrak A^2)= \mathfrak o,\ \widetilde G(\mathfrak A^3)= \mathfrak o \, .$$ for $$\widetilde G(\mathfrak x):= \widetilde Y_0+ \widetilde Y_1 \mathfrak x + \dots + \widetilde Y_{14} \mathfrak x^{14} ,$$ we do not trouble. If at least one of the equalities fails, we, under the assumption that the number of SDCs $\le 2_{}$, address Theorems 1 and 2 from the previous section. The blocks $$\widetilde Y_0, \widetilde Y_1,\dots, \widetilde Y_{14}$$ are considered as the values of some polynomial $H(\mathfrak x), \deg H \le 10$. Two errors from the interpolation table constructed for a polynomial can be corrected via the rational interpolation.

users/au/bw.txt · Последние изменения: 2020/03/11 14:00 (внешнее изменение)