Code encoding

Code encoding maps messages injectively to codewords. For a dimension-$k$ linear code with generator matrix $G$, the standard encoder maps $m\in {\mathbb{F}}_q^k$ to $mG$. The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.

A systematic encoder retains the message symbols unchanged in designated coordinates of its codeword and calculates the remaining check symbols. For a linear code, choosing an invertible set of $k$ columns of a generator matrix and changing its row basis gives this form.

For a length-$n$, dimension-$k$ cyclic code with generator polynomial $g$ of degree $n-k$, let the message polynomial satisfy $\mathrm{deg}M<k$. Subtracting the remainder upon polynomial division by $g$ makes the displayed word divisible by $g$. The remainder has degree less than $n-k$, so the highest $k$ coordinates retain the coefficients of $M$. This gives systematic encoding without losing any message information.