Example of Berlekamp-Massey algorithm

berlekamp_massey.py

def linear_sequence( modulus, a_i, x_i, length ):
    if len( a_i ) > len( x_i ):
        raise Exception( "not enough seed elements" )
    
    x_i = list( x_i )
    n = len( x_i )
    while n < length:
        x_n = sum( c * x_i[n-i-1] for i, c in enumerate(a_i) ) % modulus
        x_i.append( x_n )
        n += 1
        
    return x_i

# Example
# >>> linear_sequence( 5, [1, 0, 0, 1], [0, 0, 0, 1 ], 40 )
# [0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 0, 2, 0, 4, 4, 1, 1, 0, 4, 0, 1, 1, 0, 0, 1, 2, 2, 2, 3, 0, 2, 4, 2, 2, 4, 3, 0, 2, 1, 4]

class BK(object):
    def __init__( self, modulus ):
        self.modulus = modulus
        self.L = 0   # "number of errors", i.e., degree of C as a polynomial
        self.m = 1   # count since last discrepancy
        self.b = 1   # last discrepancy
        self.C = [ 1 ]   # current coefficients
        self.B = [ 1 ]   # previous coefficients

    def __str__( self ):
        return "L={} m={} b={} C={} B={}".format(
            self.L, self.m, self.b, self.C, self.B )
    
    def step( self, n, seq ):
        print( "### iteration", n , "###" )
        linear_sum = sum( self.C[i] * seq[n-i]
                          for i in range( 1, self.L+1 ) ) % self.modulus
        print( "Predicted: ", (-linear_sum) % self.modulus )
        print( "Actual: ", seq[n] )
        d = (seq[n] + linear_sum ) % self.modulus
        if d == 0:
            print( "No discrepancy" )
            self.m = self.m + 1
        elif 2 * self.L <= n:
            print( "Discrepancy", d, "adjusting C, L, and B" )
            T = list( self.C )
            b_inv = pow( self.b, -1, self.modulus )
            for i in range( len( self.B ) ):
                degree = i + self.m
                coeff = d * b_inv
                while len( self.C ) <= degree:
                    self.C.append( 0 )
                self.C[degree] = ( self.C[degree] - coeff * self.B[i] ) % self.modulus
            self.L = n + 1 - self.L
            self.B = T
            self.b = d
            self.m = 1
        else:
            print( "Discrepancy", d, "adjusting C only")
            b_inv = pow( self.b, -1, self.modulus )
            for i in range( len( self.B ) ):
                degree = i + self.m
                coeff = d * b_inv
                while len( self.C ) <= degree:
                    self.C.append( 0 )
                self.C[degree] = ( self.C[degree] - coeff * self.B[i] ) % self.modulus
            self.m = self.m + 1

bk = BK( 5 )
seq = [2, 3, 4, 0, 2, 0, 4, 4, 1, 1, 0, 4, 0, 1, 1, 0, 0, 1, 2, 2, 2, 3, 0, 2, 4, 2, 2, 4, 3, 0, 2, 1, 4]

def test():
    print( bk )
    for n in range( 0, len( seq ) ):
        bk.step( n, seq )
        print( bk )

Code follows https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm