Content deleted Content added
m →Encoder using multivariate polynomials: multivariate -> multilinear |
→Encoder using multilinear polynomials: added an example encoding of a specific bitstring (maybe the example is too large?) |
||
Line 31:
The fact that the codeword <math>C(x)</math> suffices to uniquely reconstruct <math>x</math> follows from [[Lagrange polynomial|Lagrange interpolation]], which states that the coefficients of a polynomial are uniquely determined when sufficiently many evaluation points are given. Since <math>C(0)=0</math> and <math>C(x+y)=C(x)+C(y) \bmod 2</math> holds for all messages <math>x,y\in\{0,1\}^k</math>, the function <math>C</math> is a [[linear map]]. Thus the Reed–Muller code is a [[linear code]].
===== Example =====
For the code {{nowrap|RM(''2'', ''4'')}}, the parameters are as follows:
<math display="inline"> \begin{align}
r&=2\\
m&=4\\
k&=\textstyle\binom{4}{2}+\binom{4}{1}+\binom{4}{0}= 6+4+1=11\\
n&=2^m=16\\
\end{align} </math>
Let <math display="inline"> C:\{0,1\}^{11}\to\{0,1\}^{16} </math> be the encoding function just defined. To encode the string x = 1 1010 010101 of length 11, the encoder first constructs the polynomial <math display="inline"> p_x </math> in 4 variables:<math display="block">\begin{align}
p_x(Z_1,Z_2,Z_3,Z_4)
&= 1
+ (1\cdot Z_1 + 0\cdot Z_2 + 1\cdot Z_3 + 0\cdot Z_4)
+ (0\cdot Z_1 Z_2 + 1\cdot Z_1Z_3 + 0\cdot Z_1Z_4 + 1\cdot Z_2Z_3 + 0\cdot Z_2Z_4+ 1\cdot Z_3Z_4)\\
&=1+Z_1+Z_3+Z_1Z_3+Z_2Z_3+Z_3Z_4
\end{align}</math>Then it evaluates this polynomial at all 16 evaluation points:<math display="block">p_x(0000)= 1,\;
p_x(0001)= 1,\;
p_x(0010)= 1,\;
p_x(0011)= 1,\;
p_x(0100)= 1,\;
p_x(0101)= 0,\;
p_x(0110)= 1,\;
p_x(0111)= 0,\;
p_x(1000)= 0,\;
p_x(1001)= 1,\;
p_x(1010)= 0,\;
p_x(1011)= 1,\;
p_x(1100)= 0,\;
p_x(1101)= 0,\;
p_x(1110)= 0,\;
p_x(1111)= 0\,.</math>As a result, C(1 1010 010101) = 1111 1010 0101 0000 holds.
=== Construction using a generator matrix ===
| |||