The image will be converted to black and white so images with large ranges from light to dark work best.
Hamming Codes
Extend binary messages by including information about the message in extra bits, a bit being a 1 or 0.
These extra bits are called parity bits. In the examples below, a specific type of hamming code, the hamming (7,4) will be used.
This means for every 4 message bits encoded there will be 7 bits returned, the extra being 3 parity bits.
Some random text
Matrix multiplication with a specific matrix called a generator matrix is required to encode the binary message. Try encoding some binary messages with it:
Some random text
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
×
=
→
→
Some random text
The outcome of the matrix multiplication is not always enough because sometimes the output has a 2 or 3 which is not binary. When this happens, finite field rules are applied, specifically GF(2). This basically means we take the remainder of each element after we
divide by two. This allows our result to stay binary. In coding, it is called mod 2 or % 2. Try different combinations to see how the finite field is applied.
Some random text
Now lets encode a binary image. Like the last step from above, the parity bits to be collected at the end of the message, or for an image to the very right. What do you think it will look like?
Some random text
Some random text
Matrix multiplication with a parity check matrix is required to calculate a binary number
that tells us the place where the error has occured. Both the parity check matrix and the generator matrix are tied together, you can see how they are calculated here. Try testing it out error correction by adding errors to the encoded 7 bit message from above:
Some random text
Some random text
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
0
1
×
=
→
Some random text
The finite field rules GF(2) still applies to the output. Knowing the place of the error, the incorrect bit can be swapped, therefore correcting the error. Then deconstruct back the orginal message. Its downside is how many errors it can correct, you can see with multiple errors, it loses its correction capabilities.
Some random text
→
Some random text
Now lets try it with an image. Interact with the noise to load the images:
Some random text
Some random text
Some random text
Some random text
Take note, the level of noise that can get through.
Some random text
Reed Solomon Codes
Hamming Codes are limited to binary messages and single bit error correction. If the aim is to correct more errors, Reed Solomon Codes offers a solution by allowing extension of the parity section length. In the Reed Solomon codes below, 8 bits are collected
together to make up a symbol that can be encoded in a similar process. Because the symbols are 8 bits (a byte) the finite field will be GF(28). Another process Reed Solomon does different is encoding and decoding.
Previously, linear algebra (matrices) was used for encoding and decoding, instead polynomial mathematics will be used.
Some random text
To start, a primitive polynomial is selected to work in conjunction with our GF(28). P(x) = x8 + x4 + x3 + x2 + 1 will be used for the examples below but any primitive polynomial of highest degree 8 should work.
A generator polynomial must be constructed with polynomial multiplication for encoding purposes. To correct
error bytes, _parity bytes will be required. If the message contains 5 bytes, this makes the code a reed solomon ___
.Some random text
For each parity byte included, the generator polynomial appended by the following:
Some random text
Some random text
This makes the generator polynomial, G(x) to be:
Some random text
Something interesting to note is the rules for generating the generator polynomial when trying to correct 5 or more error bytes changes. This
is because a number higher than 255 falls outside the GF(28). If you are curious about the rules of polynomial mathematics within finite fields,
you should check out this website by the University of New Brunswick.
Some random text
Construct a 5 byte message:
Some random text
Some random text
Then convert the message into a polynomial based of the highest degree of the G(x) polynomial.
Some random text
Some random text
The message polynomial, M(x) is divided by the generator polynomial,
G(x) to produce two outputs. A quotient and remainder polynomial. The remainder polynomial, R(x) is added to M(x) to finalise the encoded message. This produces the encoded reed solomon code.
Some random text
Some random text
Now with encoding understood, what would an image that has been reed solomon (9,5) encoded look like? The same as before, the parity bytes will be collected and displayed to right side of the image.
Image size has also been reduced to make image computations faster.
Some random text
Some random text
With encoding finished, noise can be applied to the encoded message to test its error correction.
Some random text
Some random text
Instead of going through
the details of the algorithms used, they will be listed as well as the output they produced.
If you are curious about how each algorithm step works, links to wikipedia pages and websites will be provided.
Some random text
The first step to correcting possible errors is to find the syndrome. To do this a Fourier Transform must be calculated. Horners scheme for polynomial mathematics will make this faster, see here.
Some random text
Some random text
Then calculate the error locator polynomial with Berlekamp-Massey alogorithm.
Some random text
Some random text
The error location positions can be calculted with a Chien search (inverse Fourier Transform). It contains a list of positions where the error has occurred with the first position being 0 unlike the hamming syndrome.
Some random text
Some random text
Finally, the message can be corrected by adding the encoded message to the errate message. The errate message is calculated from the Fourney algorithm that takes the incorrect msg, error location polynomial and error location postion list. Curious about how these steps work? Check out Introduction to finite fields by MIT
and Reed-Solomon Codes by CMU for further reading.
Some random text
Some random text
Let's experiment with your image, choose reed solomon:
Some random text
Some random text
Choose the noise level here:
Some random text
Some random text
Some random text
After error correction the image looks like this:
Some random text
Some random text
Thanks for interacting with this website. Want to implement your own reed solomon code, check out this resource with a python implementation: Reed-Solomon Codes for Coders.
You can view the code for this website on Github.
This website was made by Liam Patey-Dennis in conjunction with the University of Newcastle, Australia. Special thanks to Dr. Lawrence Ong for advice and guidance.