UKHAS Wiki

This is an old revision of the document!

---

#!/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 
global alpha_to [range(nn+1)]
global index_of [range(nn+1)]
global gg [range(nn-kk+1)] 
global recd [range(nn)]
global data [range(kk)]
global bb [range(nn-kk)] 
 
 
 
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 ;
 
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):
		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]] ;
 
 
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
 
# generate the Galois Field GF(2**mm) 
generate_gf()
print "Look-up tables for GF(2**%2d)\n",mm
print "  i   alpha_to[i]  index_of[i]\n"
for i in range(0,nn):
	print i,alpha_to[i],index_of[i]
print "\n\n"
 
#compute the generator polynomial for this RS code 
gen_poly()
 
#for known data, stick a few numbers into a zero codeword. Data is in
# polynomial form.
 
for  i in range(0,kk):
	data[i] = 0
 
# for example, say we transmit the following message (nothing special!) 
data[0] = 8 
data[1] = 6 
data[2] = 8 
data[3] = 1 
data[4] = 2 
data[5] = 4 
data[6] = 15 
data[7] = 9 
data[8] = 9 
 
# 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