Berlekamp-Massey algorithm for binary fields in Python

For the course in Design of Digital Circuits.

# BM algorithm \ carl@grocid.net
max_poly_len 	= 64
polyCD  		= [0]*max_poly_len
polyCpD 		= [0]*max_poly_len
polyTD  		= [0]*max_poly_len
desired_seq		= '10011101'

# functions to help with doing various stuff
def trunc(monomial_deg): 		return '1' if monomial_deg == 0 else 'D^'+str(monomial_deg)
def print_poly(poly_var): 		return  ''.join([trunc(x)+'  ' for x, e in enumerate(poly_var) if e != 0])
def parse_seq(poly_var): 		return [int(x) for x in poly_var]
def discrepancy(seq,polyCD,i): 	return sum([seq[i-j]&polyCD[j] for j in range(0,L+1)])%2
def add_poly(poly_a,poly_b): 	return [poly_a[j]^poly_b[j] for j in range(0,max_poly_len)]
def print_line():				print  ''.join(['-']*40)

# init
polyCD[0] 		= 1
polyCpD[0] 		= 1
polySeq 		= parse_seq(desired_seq)
L				= 0
l				= 1

# main loop
for i in range(0, len(desired_seq)):
	d = discrepancy(polySeq,polyCD,i)
	if d != 0:
		polyTD = polyCD
		polyCD =  add_poly(polyCD,[0]*l+polyCpD)
		if 2*L <= i:
			L = i+1-L
			l = 1
			polyCpD = polyTD
		else:
			l += 1
	else:
		l += 1
	# printout
	print_line()
	print 'i='+str(i),'s_i='+desired_seq[i],'d='+str(d),\
		  'L='+str(L),'l='+str(l),'\tC(D)='+print_poly(polyCD)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s