Reed–Solomon error correction (BCH): encoder, decoder

Mariusz Najwer 29.09.2021

https://najwer23.github.io/

Intro

Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, the most prominent of which include consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, storage systems such as RAID 6, coding schemes used by NASA missions.

Credits: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Encoding

• 1. First of all, we must select the message. I chose a message: $$M(x)=\text{ Aperion w kodzie }$$
• Let's change coding of message on binary notation!
• 
  10000011110000110010111100101101001110111111011101000001110111100000110101111011111100100111101011010011100101

• 2. Next we have to choose parametrs of our code. So, I want my program to able to find and correct less or the same 33 errors, because i made reasearch and find out that in my transsmision channel I got ~20 errors
• Selected the code of length 511.
• $$GF = (2^9)$$
• Now we must find a primitive polynomial to generate elements of field.
• $$p(x) = 1+x^4+x^9$$
• Credits: https://youtu.be/PLi5xXP_gSY

• 3. Create minimal polynomials, then make LCM (lowest common multiple)

• 4. Create minimal polynomials in polynomial notations

• 5. After multiple 33 mini polynomials We get our code generator $G(x)$
• Next You have to multiple $$F(x) = x^{511-k} * M(x), \text{ k is degree of G(x) }$$
• Then make: $$Z(x) = \frac{F(x) * M(x)}{G(x)}$$
• Get Remainder from $Z(x)$ and add to $F(x)$
• Now we have enocded message $V(x)$!
• 1101101001010010001110001111000000100011011000011000010111111111000001011111000000000101010001101101110100110110001000010001110011001100011000001111010011101111111101100011101110011010111101010001101010010010111111010011111010111000100011001111101111010010001100001100111011100010110000010110001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000011110000110010111100101101001110111111011101000001110111100000110101111011111100100111101011010011100101

Decoding

• To decoding our message you must divide our message by code generator $$S(x) = \frac{V(x)}{G(x)}$$
• If syndrom is 0 just cut message from $V(x)$ The green part!
• 
  10000011110000110010111100101101001110111111011101000001110111100000110101111011111100100111101011010011100101
• 
  What if... our message has been destroyed?!
• We have errors on positions $$500,499,498,497,496,495,494,1,2,3,4,5,6,7,8,9,10,11,12,13,14,300$$
• 1010010110101100001110001111000000100011011000011000010111111111000001011111000000000101010001101101110100110110001000010001110011001100011000001111010011101111111101100011101110011010111101010001101010010010111111010011111010111000100011001111101111010010001100001100111011100010110000010110001110001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000011110000110010111100101101001110111111011101000001110111100000110101111011111100100111110100100011100101
• The game is starting! Our syndorm: $$ \text{S(x) != 0}$$
• 011101010000001001101010001101011100100100001101001110111110001001101101110101001101111100111010001110001000011111001001001001100010111110010000011110110110011001101011000011001010110010101100101110101011111100100001011111111110110101000111110100011001110011000100110010111010011001101101100100001
• Now we have to create matrix of syndroms
• $$ \text{S = } \left[\begin{array}{ccccc|c} S_1&S_2&S_3&\cdots &S_{n} &S_{n+1}\\ S_2&S_3&S_4&\cdots &S_{n+1} &S_{n+2}\\ S_3&S_4&S_5&\cdots &S_{n+2} &S_{n+3} \\ \vdots&&&\ddots&\\ S_{n}&S_{n+1}&S_{n+2}&\cdots &S_{2n-1} &S_{2n}\\ \end{array}\right] $$
• Now we must calculate $$det(S_{n*n}),\text{ where n = 33}$$ if it is equals 0, then we must calculate another determinat of matrix $$det(S_{n-1*n-1})$$ We calculate detarminat as long as we get somthing other than 0
• If determinat is not equal 0, then we have system of linear equations. We are at home!
• Now our matrix of Syndroms has $$ rank(S) = 22 $$
• We solve the case with Gauss-Jordan method. Our solution is coefficients of localization errors function.
• Next we are searching for roots of polynomian function - localization function
• Done! We have localization of our errors and corrected vector $V(x)$
$$M(x)=\text{ Aperion w kodzie }$$
• No algorithm can correct human errors. The message should be "Apeiron w kodzie"
• Happy coding! :)

Used algorithms

• - Binary Gauss-Jordan Elimination
• - Gauss-Jordan Elimination Polynomials in Galois field
• - Detrminant of Matrix n x n
• - Zech's logarithm
• - Adding polynomials
• - Multiplication polynomials
• - Dividing polynomials
• - Peterson–Gorenstein–Zierler decoder
• - Chien search
• - Cryptographic PRNGs (finding primitive polynomials)

It's possible to changing Galois Field $$\text{from GF(2^4) to GF(2^14)}$$

Time Encoding 0.005s

Time Decoding 0.007s

Time for finding primitive polynomial for $GF(2^9)$: 0.040s