The Reed-Solomon code allows the addition of codes in order to correct errors.
Reed Solomon |
Method
In 1960, Irving Reed and Gustave Solomon proposed the Reed-Solomon method [1]. With this we have k data bits and 2t parity bits to give us a total of n bits, and which is defined an an (n,k) code for m-bit symbols. The value of t is the number of bits that can be corrected, and the block length (n) is defined by (2m-1) symbols. To encode we create a generator function that is a polynomial:
\(g(x) = (x-a)(x-\alpha^2)(x-\alpha^3) … (x-\alpha^{2t})\)
All of the codewords created by this generator will then be exactly divisible by it. We then create a polynomial from the message (p(x)) so that:
\(p_x(a_i) = x_i\)
This can be generated using Lagrange interpolation (as we would with Shamir Shares). The sender then sends:
\(s(x) = p(x).g(x)\)
and thus the value of \(s(x)\) will be actually divisible by \(g(x)\). If it is not, the receiver can determine that there has been an error, and where the error is determined from receiving:
\(r(x) = p(x) g(x) + e(x)\)
and where \(e(x)\) will provide the locations of the errors.
Coding
The following is an outline:
import reedsolo import random import sys strin='Hello World' rs = reedsolo.RSCodec(10) str1=rs.encode(strin) print 'Input string:\t\t',strin print 'String after SR:\t',str1,'\nHex:',str(str1).encode("hex") print '\n=== 1 error===' i = random.randrange(0,len(str1)) str1=str1.replace(chr(str1[i]),'X',1) print 'String with error:\t',str1 print 'Corrected string:\t',rs.decode(str1) print '\n=== 2 errors===' i = random.randrange(0,len(str1)) str1=str1.replace(chr(str1[i]),'X',1) print 'String with error:\t',str1 print 'Corrected string:\t',rs.decode(str1) print '\n=== 3 errors===' i = random.randrange(0,len(str1)) str1=str1.replace(chr(str1[i]),'X',1) print 'String with error:\t',str1 print 'Corrected string:\t',rs.decode(str1) print '\n=== 4 errors===' i = random.randrange(0,len(str1)) str1=str1.replace(chr(str1[i]),'X',1) print 'String with error:\t',str1 print 'Corrected string:\t',rs.decode(str1) print '\n=== 5 errors===' i = random.randrange(0,len(str1)) str1=str1.replace(chr(str1[i]),'X',1) print 'String with error:\t',str1 print 'Corrected string:\t',rs.decode(str1)