Polynomial Codes

We can easily identify messages from $\mathbb{Z}_2^{k}$ with a polynomial in $\mathbb{Z}_2[x]$ with the following map \[ (a_0,a_1,\dots,a_{k-1})\rightarrow a_0+a_1x+\cdots +a_{k-1}x^{k-1} \] If we then fix some nonconstant polynomial $g(x)\in\mathbb{Z}_2[x]$ of degree $n-k$, we can create a $(n,k)$-code defined by multiplication the polynomial $g(x)$. We will make use of Polynomial Rings in SageMath to implement this here. Consider the following example, taken from Judson's Abstract Algebra: Theory and Applications.

Here is another example, complete with creating a message and encodeding it.

BCH Codes

Here we will expound on the polynomial codes that we explored in the previous document. BCH codes are very similar, although we are a little more careful with the choice of the generating polynomial. Let $d=2r+1$. Then if \[ g(x)=\text{lcm}\{m_1(x),m_2(x),\dots,m_{2r}(x)\} \] where $m_i(x)$ is the minimal polynomial of $\omega^i$ where $\omega $ is the primitive $n^{th}$ root of unity over $\mathbb{Z}_2$, then with this choice of $g$, we have that the cyclic code $\langle g(x)\rangle$ in \[ \frac{\mathbb{Z}_2[x]}{\langle x^n-1\rangle } \] is called the BHC code of length $n$ and distance $d$. If we recall the previous results from the Linear codes that were discussed earlier, we have that this code can detect $2r$ errors, and correct $r$ errors.

Here is an example of defining a BCH code, and encoding a message using the corresponding matrix.

Similarly to what we did with Linear Codes, we define a BurstChannel that we can transmit our messages through, which will randomly flip bits in the message. This class will also have a higher probability of burst errors, that is, if the previous bit has been flipped, then the probability that the next bit will be flipped is higher. In this cell we also define encode and decode functions, so that we may use lists for our messages, rather than matrices. Run the next cell to define this class, then proceed to the examples.

The Bernoulli class acts just like a Bernoulli trial, with the .randomTrial() method, we recieve a 0 or a 1, and the probablility that we recieve a 1 is the number $p$ that was passed to the constructor, which must be between zero and one. The BurstChannel class acts as a symmetric channel, that will ocasionally introduce errors into the message that is being passed through it. If the previous bit of the message has been flipped, then the probability that the next bit will be flipped is higher, therefore increasing the probability of burst errors that occur adjacent to one another. The constructor for the BurstChannel class takes in the probability of an error, as well as the probability of the next bit having an error, given that the previous bit contains an error, in that order.

Example

Here we have a full example of encoded a message using the encoding matrix defined above, sending the message through the burst channel, then decoding it, run this cell several times to see how the syndrome of the message changes as we see different errors in the message.