Reed–Muller code: Difference between revisions

Revision as of 16:47, 14 January 2021

Revision as of 22:43, 4 February 2021

Line 72:

=== Generalization to larger alphabets via low-degree polynomials ===

Using low-degree polynomials over a finite field <math>\mathbb F</math> of size <math>q</math>, it is possible to extend the definition of Reed&ndash;Muller codes to alphabets of size <math>q</math>. Let <math>m</math> and <math>d</math> be positive integers, where <math>m</math> should be thought of as larger than <math>d</math>. To encode a message <math display="inline">x\in\mathbb F^k</math> of withwidth <math>k=\textstyle\binom{m+d}{m}</math>, the message is again interpreted as an <math>m</math>-variate polynomial <math>p_x</math> of total degree at most <math>d</math> and with coefficient from <math>\mathbb F</math>. Such a polynomial indeed has <math>\textstyle\binom{m+d}{m}</math> coefficients. The Reed–Muller encoding of <math>x</math> is the list of all evaluations of <math>p_x(a)</math> over all <math>a\in\mathbb F^m</math>. Thus the block length is <math>n=q^m</math>.

== Description using a generator matrix ==