GF(2) variant of the Berlekamp-Massey algorithm, i.e. for binary sequences (a list of zero and one integers)

berlekamp_massey.py

from copy import copy

def berlekamp_massey(sequence: List[int]) -> int:
    n = len(sequence)

    error_locator = [0 for _ in range(n)]
    error_locator[0] = 1

    error_locator_prev = copy(error_locator)

    min_size = 0  # of the LSFR
    nloops = -1  # since error_locator_prev and min_size were updated

    for i, seq_bit in enumerate(sequence):
        discrepancy = seq_bit
        seq_window = reversed(sequence[i-min_size:i])
        errloc_window = error_locator[1:min_size+1]
        for seq_bit, errloc_bit in zip(seq_window, errloc_window):
            product = seq_bit & errloc_bit
            discrepancy = discrepancy ^ product

        if discrepancy:
            error_locator_temp = copy(error_locator)

            recalc_bits = []
            for errloc_bit, prev_bit in zip(error_locator[i-nloops:n], error_locator_prev):
                bit = errloc_bit ^ prev_bit
                recalc_bits.append(bit)
            error_locator[i-nloops:n] = recalc_bits

            if min_size <= i / 2:
                min_size = i + 1 - min_size
                nloops = i
                error_locator_prev = error_locator_temp

    return min_size