Reed–Muller code: Difference between revisions

Revision as of 14:25, 8 September 2023

Latest revision as of 03:04, 11 August 2025

(3 intermediate revisions by 3 users not shown)

Line 26:

=== Encoder ===

A [[block code]] can have one or more encoding functions <math display="inline"> C:\{0,1\}^k\to\{0,1\}^{n} </math> that map messages <math display="inline"> x\in\{0,1\}^k </math> to codewords <math display="inline"> C(x)\in\{0,1\}^{n} </math>. The Reed&ndash;Muller code {{nowrap|RM(''r'', ''m'')}} has [[Block code#The message length k|message length]] <math>\textstyle k=\sum_{i=0}^r \binom{m}{i}</math> and [[Block code#The block length n|block length]] <math>\textstyle n=2^m</math>. One way to define an encoding for this code is based on the evaluation of [[multilinear polynomial]]s with ''m'' variables and [[total degree]] at most ''r''. Every multilinear polynomial over the [[finite field]] with two elements can be written as follows:

<math display="block">p_c(Z_1,\dots,Z_m) = \sum_{\underset{|S|\le r}{S\subseteq\{1,\dots,m\}}} c_S\cdot \prod_{i\in S} Z_i\,.</math>

The <math display="inline"> Z_1,\dots,Z_m </math> are the variables of the polynomial, and the values <math display="inline"> c_S\in\{0,1\} </math> are the coefficients of the polynomial. SinceNote that there are exactly <math display="inline"> k=\sum_{i=0}^r \binom{m}{i}</math> coefficients. With this in mind, thean input message consists of <math display="inline"> x\in\{0,1\}^k </math> consists ofvalues <math display="inline"> x\in\{0,1\}^k </math> valueswhich that can beare used as these coefficients. In this way, each message <math display="inline"> x </math> gives rise to a unique polynomial <math display="inline"> p_x </math> in ''m'' variables. To construct the codeword <math display="inline"> C(x) </math>, the encoder evaluates the polynomial <math display="inline"> p_x </math> at all evaluation points <math display="inline"> aZ=(Z_1,\ldots,Z_m)\in\{0,1\}^m </math>, where it interprets the sumpolynomial asis additiontaken modulowith twomultiplication inand orderaddition tomod obtain a bit2 <math display="inline">(p_x(aZ)\bmod 2) \in \{0,1\}</math>. That is, the encoding function is defined via<math display="block">C(x) = \left(p_x(aZ)\bmod 2\right)_{aZ\in\{0,1\}^m}\,.</math>

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]].

Line 116:

* <math display="inline"> \mu=X_2X_3 </math>

** <u>1</u>1<u>0</u>0 <u>1</u>1<u>1</u>1 0000 0111. Sum is 1

** 1<u>1</u>0<u>0</u> 1<u>1</u>1<u>1</u> 0000 0111. Sum is 1

** 1100 1111 <u>0</u>0<u>0</u>0 <u>0</u>1<u>1</u>1. Sum is 1

** 1100 1111 0<u>0</u>0<u>0</u> 0<u>1</u>1<u>1</u>. Sum is 0

Line 342:

|

|

|Z

|{{math|1=RM(''m,m'')}}<br />({{math|1=2^''m''}}, {{math|1=2^''m''}}, 1)

|universe codes

Line 474:

==External links==

* [http://ocw.mit.edu MIT OpenCourseWare], 6.451 Principles of Digital Communication II, Lecture Notes section 6.4

* [httphttps://octave.sourceforge.net/communications/function/reedmullergen.html GPL Matlab-implementation of RM-codes ]

* [httphttps://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/comm/inst/reedmullergen.m?revision=9852&view=markup Source GPL Matlab-implementation of RM-codes]

*{{cite journal |last1=Weiss |first1=E. |title=Generalized Reed-Muller codes |journal=Information and Control |date=September 1962 |volume=5 |issue=3 |pages=213–222 |doi=10.1016/s0019-9958(62)90555-7 |issn=0019-9958|doi-access= }}