Reed–Muller code: Difference between revisions

Revision as of 22:34, 7 June 2020

Revision as of 15:03, 16 August 2020

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&ndash;Muller code is a [[linear code]].

===== Example =====

For the code {{nowrap|RM(''2'', ''4'')}}, the parameters are as follows:

Line 107:

:<math>H_i = \{ y \in ( \mathbb{F}_2 ) ^m \mid y_i = 0 \} .</math>

==== The generator matrix= ===

The Reed&ndash;Muller {{nowrap|RM(''r'', ''m'')}} code of order ''r'' and length ''N''&nbsp;=&nbsp;2^''m'' is the code generated by ''v''₀ and the wedge products of up to ''r'' of the ''v''_''i'', {{nowrap|1 ≤ ''i'' ≤ ''m''}} (where by convention a wedge product of fewer than one vector is the identity for the operation). In other words, we can build a generator matrix for the {{nowrap|RM(''r'', ''m'')}} code, using vectors and their wedge product permutations up to ''r'' at a time <math>{v_0, v_1, \ldots, v_n, \ldots, (v_{i_1} \wedge v_{i_2}), \ldots (v_{i_1} \wedge v_{i_2} \ldots \wedge v_{i_r})}</math>, as the rows of the generator matrix, where {{nowrap|1 ≤ ''i''_''k'' ≤ ''m''}}.

==== Example 1= ===

Let ''m'' = 3. Then ''N'' = 8, and

Line 142:

</math>

==== Example 2= ===

The RM(2,3) code is generated by the set: