Skip to content

Instantly share code, notes, and snippets.

@vijayanandrp
Created June 14, 2017 21:41
Show Gist options
  • Save vijayanandrp/689b9747e89325b1ae07d9fd434e89f2 to your computer and use it in GitHub Desktop.
Save vijayanandrp/689b9747e89325b1ae07d9fd434e89f2 to your computer and use it in GitHub Desktop.
Berlekamp–Massey algorithm implemented in Python. (Easy)
# 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
@NickNck
Copy link

NickNck commented Jan 22, 2019

Hi im getting an error with the GF method since its not defined. How do i go about this?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment