UKHAS Wiki

The decoder can be found at hathawaymix.org

#!/usr/bin/python
 
mm=7           # RS code over GF(2**4) - change to suit 
tt=16          # number of errors that can be corrected 
nn=2**mm -1    #length of codeword 
kk = nn-2*tt  
 
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]]
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) 
 
 
 
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;
#                 polynomial form -> index form  index_of[j=alpha**i] = i
#   alpha=2 is the primitive element of GF(2**mm)
	mask = 1
	alpha_to[mm] = 0 
	for i in range(mm):
		alpha_to[i] = mask 
		index_of[alpha_to[i]] = i 
		if pp[i]!=0:
			alpha_to[mm] ^= mask 
		mask <<= 1 
	index_of[alpha_to[mm]] = mm
	mask >>= 1
	for i in range(mm+1,nn):
		if (alpha_to[i-1] >= mask):
			alpha_to[i] = alpha_to[mm] ^ ((alpha_to[i-1]^mask)<<1)
		else:
			alpha_to[i] = alpha_to[i-1]<<1
		index_of[alpha_to[i]] = i
	index_of[0] = -1 ;
 
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+1):
		gg[i] = 1
      		for j in range(i-1,0,-1):
			if (gg[j] != 0):
				gg[j] = gg[j-1]^ alpha_to[(index_of[gg[j]]+i)%nn]
			else:
				gg[j] = gg[j-1]
		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):
		gg[i] = index_of[gg[i]] ;
 
 
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]
#  data[] is input and bb[] is output in polynomial form.
#  Encoding is done by using a feedback shift register with appropriate
#  connections specified by the elements of gg[], which was generated above.
#  Codeword is   c(X) = data(X)*X**(nn-kk)+ b(X)          
	for i in range(0,nn-kk):   
		bb[i] = 0
	for i in range(kk-1,-1,-1):
		feedback = index_of[data[i]^bb[nn-kk-1]]
		if feedback != -1:
			for j in range(nn-kk-1,0,-1):
				if gg[j] !=-1:
					bb[j] = bb[j-1]^alpha_to[(gg[j]+feedback)%nn]
				else:
					bb[j] = bb[j-1]
			bb[0] = alpha_to[(gg[0]+feedback)%nn] 
		else:
			for j in range(nn-kk-1,0,-1):
				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]

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]

$ 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]