Differences

This shows you the differences between two versions of the page.

--- code:python_reedsolomon [2008/02/03 18:37] – created laurenceb
+++ code:python_reedsolomon [2008/07/19 23:33] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
+===== Main code (uses a c library for decoding, as the tx only has to encode, and we're assuming running binaries on the ground is easy) =====
+The decoder can be found at [[http://hathawaymix.org/Software/ReedSolomon|hathawaymix.org]]
 <code python>
 #!/usr/bin/python
-global mm=4           # RS code over GF(2**4) - change to suit
-global nn=15          # nn=2**mm -1   length of codeword
-global tt=3           # number of errors that can be corrected
-global kk=9           # kk = nn-2*tt
-global pp [1, 1, 0, 0, 1]   # specify irreducible polynomial coeffts
+mm=7           # RS code over GF(2**4) - change to suit
-global alpha_to [range(nn+1)]
+tt=16          # number of errors that can be corrected
-global index_of [range(nn+1)]
+nn=2**mm -1    #length of codeword
-global gg [range(nn-kk+1)]
+kk = nn-2*tt
-global recd [range(nn)]
-global data [range(kk)]
+primative_polynomials=[[1,1,0,1],[1,1,0,0,1],[1,0,1,0,0,1],[1,1,0,0,0,0,1],[1,0,0,1,0,0,0,1],[1,0,1,1,1,0,0,0,1],[1,0,0,0,1,0,0,0,0,1]]
-global bb [range(nn-kk)]
+pp=primative_polynomials[mm-3]   # specify irreducible polynomial coeffts m=5
+alpha_to=[0]*(nn+1)
+index_of=[0]*(nn+1)
+gg=[0]*(nn-kk+1)
+recd=[0]*(nn)
+data=[0]*(kk)
+bb=[0]*(nn-kk)
-generate_gf():
+def generate_gf():
 # generate GF(2**mm) from the irreducible polynomial p(X) in pp[0]..pp[mm]
 # lookup tables:  index->polynomial form   alpha_to[] contains j=alpha**i;
@@ Line 39: / Line 45: @@
 	index_of[0] = -1 ;
-gen_poly():
+def gen_poly():
 # Obtain the generator polynomial of the tt-error correcting, length
 # nn=(2**mm -1) Reed Solomon code  from the product of (X+alpha**i), i=1..2*tt
 	gg[0] = 2     # primitive element alpha = 2  for GF(2**mm)
 	gg[1] = 1     # g(x) = (X+alpha) initially
-	for i in range(2,nn-kk):
+	for i in range(2,nn-kk+1):
 		gg[i] = 1
       		for j in range(i-1,0,-1):
@@ Line 51: / Line 57: @@
 			else:
 				gg[j] = gg[j-1]
-			gg[0] = alpha_to[(index_of[gg[0]]+i)%nn] ;     # gg[0] can never be zero
+		gg[0] = alpha_to[(index_of[gg[0]]+i)%nn] ;     # gg[0] can never be zero
 # convert gg[] to index form for quicker encoding */
 	for i in range(0,nn-kk):
@@ Line 57: / Line 63: @@
-encode_rs():
+def encode_rs():
 # take the string of symbols in data[i], i=0..(k-1) and encode systematically
 #  to produce 2*tt parity symbols in bb[0]..bb[2*tt-1]
@@ Line 79: / Line 85: @@
 				bb[j] = bb[j-1]
 			bb[0] = 0
+def setup_rs():
+# generate the Galois Field GF(2**mm)
+	generate_gf()
+#compute the generator polynomial for this RS code
+	gen_poly()
+def encode_string(s):
+	d=0
+	for i in s:
+		data[d]=ord(i)
+		d=d+1
+	for i in range(len(s),kk):
+		data[i]=0
+# encode data[] to produce parity in bb[].  Data input and parity output
+#  is in polynomial form
+	encode_rs()
+# put the transmitted codeword, made up of data plus parity, in recd[] */
+	for i in range(0,nn-kk):
+		recd[i] = bb[i]
+	for i in range(0,kk):
+		recd[i+nn-kk] = data[i]
+#	print recd
+#	print len(recd)
+	s=''
+	for i in range(2*tt,len(recd)):   #pick all the human readable data
+		s+=chr(recd[i])
+	for i in range(2*tt):
+		s+=chr(recd[i])
+#	print s
+	return s
+def decode_string(s,corruption):    #corruption is a list of know corrupted chr positions
+	from reedsolomon import Codec
+	c=Codec(nn,kk,mm)
+	f=''
+	for i in range(2*tt):   #pick all the parity and put @ front
+		f+=s[len(s)+i-2*tt]
+	for i in range(2*tt,len(s)):  #copy over the data
+		f+=s[i-2*tt]
+	t=''
+	for i in range(len(f)):   #reverses the whole string
+		t+=f[len(f)-len(t)-1]
+	#print len(t)
+	#print t
+	t=c.decode(t,corruption)
+	del s
+	s=''
+	b=''
+        for i in t[0]:
+		b+=t[0][len(t[0])-len(b)-1]
+	for i in range(len(b)):
+		s+=b[i]
+	return s,t[1]
 </code>
+===== Usage example =====
+<code python>
+import reed_solomon
+reed_solomon.setup_rs()
+s=reed_solomon.encode_string("hello world my name is Laurence and I am your supreme ruler !!!111!!111!")
+print s
+t=s[0:9]+"df"+s[11:len(s)]
+d = reed_solomon.decode_string(t,[])
+print d[0]
+print "Errors at: ",d[1]
+</code>
+===== produces: =====
+<code>
+$ python testcode.py
+hello world my name is Laurence and I am your supreme ruler !!!111!!111! dJ{,wOWOIUv?M
+         ]'tkN{edkM98
+hello world my name is Laurence and I am your supreme ruler !!!111!!111!
+Errors at:  [84, 85]
+</code>