12,503,591 members (50,247 online)
alternative version

44.6K views
12 bookmarked
Posted

# 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.

## About the Author

 Software Developer (Senior) Croatia
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 berelekamp massey raza817-May-09 11:37 raza81 7-May-09 11:37
 Just Curious JohnDeHope315-Sep-05 4:18 JohnDeHope3 15-Sep-05 4:18
 Re: Just Curious vadivhere15-Sep-05 7:10 vadivhere 15-Sep-05 7:10
 Re: Just Curious Miroslav Stampar15-Sep-05 22:47 Miroslav Stampar 15-Sep-05 22:47
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Sep-16 7:45 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.