Linear Feedback Shift Registers

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

$s_{i+4} = s_i + s_{i+1} + s_{i+3}$, seed/IV $[1, 1, 0, 0]$

In [1]:
seed = [1, 1, 0, 0]
coef = [1, 1, 0, 1]
In [2]:
from numpy import dot
In [3]:
dot(seed, coef) % 2 #dot product modulo 2
Out[3]:
0
In [4]:
#next bit
state = [1, 0, 0, 0]
dot(state, coef) % 2
Out[4]:
1
In [5]:
state = state[1:]+[dot(state, coef) % 2] #next state
In [6]:
state
Out[6]:
[0, 0, 0, 1]
In [7]:
state = state[1:]+[dot(state, coef) % 2] #next state
state
Out[7]:
[0, 0, 1, 1]
In [8]:
state = state[1:]+[dot(state, coef) % 2] #next state
state
Out[8]:
[0, 1, 1, 1]
In [178]:
def lfsr_first(seed, coef, n): 
    """
        generates first n bits of LFSR with the given seed and coefficients
    """    
    result = []
    state = seed
    for i in range(n):
        result.append(state[0])
        state = state[1:]+[dot(state, coef) % 2] #next state
    return result
In [173]:
lfsr_first([1, 1, 0, 0], [1, 1, 0, 1], 10)
Out[173]:
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]

Python's iterator

In [179]:
#Python iterator
def lfsr(seed, coef):
    """
        generates bits of LFSR with the given seed and coefficients
        seed and coef can be list/tuple of int or string of digits 0/1
    """    
    assert len(seed) == len(coef), "Lengths of SEED and COEF differ"
    state = list(map(int, seed))
    coef = list(map(int, coef))
    while True:
        yield state[0] #next value from list
        state = state[1:]+[dot(state, coef) % 2] #next state
In [12]:
from itertools import islice

islice(lfsr([1, 1, 0, 0], [1, 1, 0, 1]), 30) #creates new iterator
Out[12]:
<itertools.islice at 0x19f51a081d8>
In [177]:
list(islice(lfsr("1100", "1101"), 10))
Out[177]:
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]
In [180]:
tuple(islice(lfsr([1, 1, 0, 0], [1, 1, 0, 1]), 10))
Out[180]:
(1, 1, 0, 0, 0, 1, 1, 1, 0, 0)
In [114]:
print(*islice(lfsr([1, 1, 0, 0], [1, 1, 0, 1]), 30), sep=",")

1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1
In [182]:
print(*islice(lfsr([1, 1, 0, 0], [1, 1, 0, 1]), 30))

1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1

c = a+b

In [17]:
a = [0,1,0]
b = [1,1,1]
In [18]:
a+b
Out[18]:
[0, 1, 0, 1, 1, 1]
In [19]:
[ (a[i]+b[i]) % 2 for i in range(len(a))] #by index
Out[19]:
[1, 0, 1]

Python's List comprehension

In [20]:
[ (x+y) % 2 for x, y in zip(a,b) ] #list comprehension
Out[20]:
[1, 0, 1]
In [21]:
a = [0,1,0]
b = [1,1,1]
c = [1,0,0]
In [22]:
[ sum(vals) % 2 for vals in zip(a,b,c) ] #a+b+c
Out[22]:
[0, 0, 1]
In [23]:
print(a)
print(b)
print(*zip(a,b))

[0, 1, 0]
[1, 1, 1]
(0, 1) (1, 1) (0, 1)
In [24]:
print(*zip(a,a[1:]))

(0, 1) (1, 0)
In [25]:
[1, 0, 1, 0]
Out[25]:
[1, 0, 1, 0]
In [26]:
0b1010
Out[26]:
10

Berlekamp–Massey algorithm

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

http://crypto.stanford.edu/~mironov/cs359/massey.pdf

In [223]:
def berlekamp_massey(sequence):
    s = list(map(int, sequence))
    c = [1 if i==0 else 0 for i in range(len(s))]
    b = c.copy()
    l, m = 0, -1
    for n in range(len(s)):
        d = s[n]
        for i in range(1, l+1):
            d ^= c[i] & s[n-i]
        if d == 1:
            t = c.copy()
            for i in range(len(s)-n+m):
                c[i+n-m] ^= b[i]
            if l <= n >> 1:
                l, m = n+1-l, n
                b = t
    return sequence[:l], c[:l]
In [224]:
berlekamp_massey([1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1])
Out[224]:
([1, 1, 0, 0], [1, 1, 0, 1])
In [205]:
lfsr_first(*berlekamp_massey([1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1]), 25)
Out[205]:
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1]

Python's reduce

In [221]:
from operator import xor
from functools import reduce

def berlekamp_massey(sequence):
    s = list(map(int, sequence))
    c = [1 if i==0 else 0 for i in range(len(s))]
    b = c.copy()
    l, m = 0, -1
    for n in range(len(s)):
        if s[n] ^ reduce(xor, [c[i] & s[n-i] for i in range(1, l+1)], 0) == 1:
            tmp = c.copy()
            for i in range(len(s)-n+m):
                c[i+n-m] ^= b[i]
            if l <= n >> 1:
                l, m = n+1-l, n
                b = tmp
    return sequence[:l], c[:l]
In [222]:
berlekamp_massey([1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1])
Out[222]:
([1, 1, 0, 0], [1, 1, 0, 1])
In [ ]: