How to implement a Berlekamp–Massey algorithm? Explained with easy example

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. I have used sage for computing this program.

	# Berlekamp-Massey Algorithm
	#from __future__ import print_function
	s = [GF(2)(0), 0, 1, 0, 0, 0, 0, 0, 1, 1, 0] #input sequence
	n = len(s)
	C = [GF(2)(1)]
	B = [GF(2)(1)]
	temp = []
	T = []
	L = 0
	N = 0
	m = -1
	print '----- n',n
	print '-----------------------------------------------------------------------'
	while N < n:
	temp = B
	d = s[N]
	for i in range(1,L+1):
	d = d + C[i]*s[N-i]
	print '----- d ',d
	if d == 1:
	T = C
	temp = [ 0 for i in range(int(N-m))] + temp
	if len(C) < len(temp):
	C = C + [0 for i in range(len(temp)-len(C))]
	else:
	temp = temp + [0 for i in range(len(C)-len(temp))]
	for i in range(len(C)):
	C[i] = C[i] + temp[i]
	print '----- temp',temp
	print '----- C',C
	if L <= N/2:
	L = int(N + 1 - L)
	m = int(N)
	B = T
	N = N + 1
	print '-----------------------------------------------------------------------'
	print '----- N',N
	print '----- L',L
	j = 0
	print '-----------------------------------------------------------------------'
	print 'Solution is ', #Output registers
	for i in C:
	if j < len(C)-1:
	if i == 1:
	print i,'x^(',j,')+',
	else:
	if i == 1:
	print i,'x^(',j,')'
	j+=1

view raw Berlekamp-Massey Algorithm.py hosted with ❤ by GitHub