12,633,079 members (33,641 online)
alternative version

45.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 `s<sub>n</sub>` of length `n`. The algorithm takes `n `iterations, with the `N`th iteration computing the linear complexity of the subsequence `s<sub>N</sub>` consisting of the first `N `terms of `s<sub>n</sub>`. Returned value (`L`) is the length of the shortest linear feedback shift register sequence that generates all bits in sequence `s<sub>n</sub>`.
(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

 Pro

## Comments and Discussions

 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
 Re: Just Curious vadivhere15-Sep-05 8:10 vadivhere 15-Sep-05 8:10
 Re: Just Curious Miroslav Stampar15-Sep-05 23:47 Miroslav Stampar 15-Sep-05 23:47
 Last Visit: 31-Dec-99 19:00     Last Update: 8-Dec-16 22:18 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.