11,428,497 members (66,210 online)

# Implementation of Berlekamp-Massey Algorithm

, 15 Sep 2005 CPOL
 Rate this:
Implementation of Berlekamp-Massey algorithm

## Introduction

The Berlekamp-Massey algorithm is an efficient algorithm for determining the linear complexity of a finite binary sequence `sn` of length `n`. The algorithm takes `n `iterations, with the `N`th iteration computing the linear complexity of the subsequence `sN` consisting of the first `N `terms of `sn`. Returned value (`L`) is the length of the shortest linear feedback shift register sequence that generates all bits in sequence `sn`.
(Used in NIST statistical test suite - "Linear Complexity Test".)

## The Code

```    // Implementation of Berlekamp-Massey algorithm for calculating linear
// complexity of binary sequence
// s = byte array with binary sequence
// returns Length of LFSR with smallest length which generates s
// for an example: int L=BerlekampMassey(new byte[] {1,0,1,0,1,1,1,0,1,0})
//        reference: "Handbook of Applied Cryptography", p201

public static int BerlekampMassey(byte[] s)
{
int L, N, m, d;
int n=s.Length;
byte[] c=new byte[n];
byte[] b=new byte[n];
byte[] t=new byte[n];

//Initialization
b[0]=c[0]=1;
N=L=0;
m=-1;

//Algorithm core
while (N<n)
{
d=s[N];
for (int i=1; i<=L; i++)
d^=c[i]&s[N-i];            //(d+=c[i]*s[N-i] mod 2)
if (d==1)
{
Array.Copy(c, t, n);    //T(D)<-C(D)
for (int i=0; (i+N-m)<n; i++)
c[i+N-m]^=b[i];
if (L<=(N>>1))
{
L=N+1-L;
m=N;
Array.Copy(t, b, n);    //B(D)<-T(D)
}
}
N++;
}
return L;
}
}```

## Finally

Sorry, but this might only be useful to those freaks (like me that work on statistical tests and/or cryptanalysis. I just needed to put this on the Web because I couldn't find some useful implementation out there.

## Share

Software Developer (Senior)
Croatia
No Biography provided

 First Prev Next
 berelekamp massey raza817-May-09 12:37 raza81 7-May-09 12:37
 Just Curious JohnDeHope315-Sep-05 5:18 JohnDeHope3 15-Sep-05 5:18