# UKHAS Wiki

UK High Altitude Society

### Site Tools

code:python_reedsolomon

## 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 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=*(nn+1)
index_of=*(nn+1)
gg=*(nn-kk+1)
recd=*(nn)
data=*(kk)
bb=*(nn-kk)

def generate_gf():
# generate GF(2**mm) from the irreducible polynomial p(X) in pp..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)
alpha_to[mm] = 0
for i in range(mm):
index_of[alpha_to[i]] = i
if pp[i]!=0:
index_of[alpha_to[mm]] = mm
for i in range(mm+1,nn):
else:
alpha_to[i] = alpha_to[i-1]<<1
index_of[alpha_to[i]] = i
index_of = -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 = 2     # primitive element alpha = 2  for GF(2**mm)
gg = 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 = alpha_to[(index_of[gg]+i)%nn] ;     # gg 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..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 = alpha_to[(gg+feedback)%nn]
else:
for j in range(nn-kk-1,0,-1):
bb[j] = bb[j-1]
bb = 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:
b+=t[len(t)-len(b)-1]
for i in range(len(b)):
s+=b[i]
return s,t```

## Usage example

```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
print "Errors at: ",d```

## produces:

```\$ python testcode.py
hello world my name is Laurence and I am your supreme ruler !!!111!!111! dJ{,wOWOIUv?M
]'tkN{edkM98
hello world my name is Laurence and I am your supreme ruler !!!111!!111!
Errors at:  [84, 85]``` 