Editing BCH code (section)

== Encoding ==
Because any polynomial that is a multiple of the generator polynomial is a valid BCH codeword, BCH encoding is merely the process of finding some polynomial that has the generator as a factor.

The BCH code itself is not prescriptive about the meaning of the coefficients of the polynomial; conceptually, a BCH decoding algorithm's sole concern is to find the valid codeword with the minimal Hamming distance to the received codeword. Therefore, the BCH code may be implemented either as a [[systematic code]] or not, depending on how the implementor chooses to embed the message in the encoded polynomial.

=== Non-systematic encoding: The message as a factor ===
The most straightforward way to find a polynomial that is a multiple of the generator is to compute the product of some arbitrary polynomial and the generator. In this case, the arbitrary polynomial can be chosen using the symbols of the message as coefficients.

:<math>s(x) = p(x)g(x)</math>

As an example, consider the generator polynomial <math>g(x)=x^{10}+x^9+x^8+x^6+x^5+x^3+1</math>, chosen for use in the (31, 21) binary BCH code used by [[POCSAG]] and others. To encode the 21-bit message {101101110111101111101}, we first represent it as a polynomial over <math>GF(2)</math>:
:<math>p(x) = x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^3+x^2+1</math>
Then, compute (also over <math>GF(2)</math>):
:<math>\begin{align}
  s(x) &= p(x)g(x)\\
       &= \left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^3+x^2+1\right)\left(x^{10}+x^9+x^8+x^6+x^5+x^3+1\right)\\
       &= x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^2+1
\end{align}</math>
Thus, the transmitted codeword is {1100111010010111101011101110101}.

The receiver can use these bits as coefficients in <math>s(x)</math> and, after error-correction to ensure a valid codeword, can recompute <math>p(x) = s(x)/g(x)</math>

=== Systematic encoding: The message as a prefix ===
A systematic code is one in which the message appears verbatim somewhere within the codeword. Therefore, systematic BCH encoding involves first embedding the message polynomial within the codeword polynomial, and then adjusting the coefficients of the remaining (non-message) terms to ensure that <math>s(x)</math> is divisible by <math>g(x)</math>.

This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial <math>p(x)</math> as before and multiply it by <math>x^{n-k}</math> (to "shift" the message out of the way of the remainder), we can then use [[Euclidean division]] of polynomials to yield:
:<math>p(x)x^{n-k} = q(x)g(x) + r(x)</math>

Here, we see that <math>q(x)g(x)</math> is a valid codeword. As <math>r(x)</math> is always of degree less than <math>n-k</math> (which is the degree of <math>g(x)</math>), we can safely subtract it from <math>p(x)x^{n-k}</math> without altering any of the message coefficients, hence we have our <math>s(x)</math> as
:<math>s(x) = q(x)g(x) = p(x)x^{n-k} - r(x)</math>

Over <math>GF(2)</math> (i.e. with binary BCH codes), this process is indistinguishable from appending a [[cyclic redundancy check]], and if a systematic binary BCH code is used only for error-detection purposes, we see that BCH codes are just a generalization of the [[mathematics of cyclic redundancy checks]].

The advantage to the systematic coding is that the receiver can recover the original message by discarding everything after the first <math>k</math> coefficients, after performing error correction.