Jak na algoritmus Berlekamp

Ahoj, trápím se s algoritmem Berlekamp–Massey v pythonu a nemůžu ho rozchodit. Základ mám z githubu https://github.com/thewhiteninja/lfsr-berlekamp-massey Nedaří se mi podle získaného polynomu vygenerovat počáteční sequency. Myslím, že je tu hodně neznámých, jako pořadí polynomu, počáteční stav a zda má být přítomen člen x^0.

Kód je zde

def berlekamp_massey_algorithm(seq):
    n = len(seq)
    b, c = [0]*n, [0]*n
    b[0], c[0] = 1, 1
    L, m, i = 0, -1, 0
    for j in range(n):
        d = seq[j]
        for k in range(1, L+1):
            d ^= c[k] & seq[j-k]
        if d == 1:
            t = c.copy()
            p = [0]*n
            for k in range(n-j+m):
                p[k] = b[k+j-m] ^ t[k]
            if L <= j//2:
                L = j + 1 - L
                m = j
                b, c = t, p
            else:
                for k in range(n-j+m):
                    c[k] = b[k+j-m] ^ p[k]
    return L, b[:L+1], c[:L+1]


def generate_lfsr_output(poly, seq_len):
    n = len(poly)
    state = [0]*(n-1) + [1]
    output = []
    for i in range(seq_len):
        out = state[-1]
        for j in range(n-1):
            if poly[j+1]:
                out ^= state[j]
        state = [out] + state[:-1]
        output.append(out)
    return output

def main():
    seq = [0, 1, 1, 0, 1, 0, 0, 1]
    L, b, c = berlekamp_massey_algorithm(seq)
    print(f"Shortest LFSR length: {L}")
    print("LFSR polynomial coefficients (backward):")
    print(b[::-1])
    generated_seq = generate_lfsr_output(b[::-1], len(seq))
    print("Generated sequence:")
    print(generated_seq)
    print("Verification result:")
    print(seq == generated_seq)

if __name__ == '__main__':
    main()

Výstup vypadá takto

Shortest LFSR length: 4
Polynomial: x^4 + x^3 + x^1
LFSR polynomial coefficients (backward): [1, 1, 0, 1, 0]
original sequence:
[0, 1, 1, 0, 1, 0, 0, 1]
Generated sequence:
[1, 1, 0, 0, 1, 0, 0, 0]
Verification result:
False

Domácí úkol to není, do školy už nechodím. V úkázce výše jsem vložil starší kód, ale nový výstup, omlouvám se. Novější kód je ze stránky https://raw.githubusercontent.com/bozhu/BMA/master/bma.py je tady

def berlekamp_massey(sequence):
    n = len(sequence)
    s = list(map(int, sequence))

    k = 0
    for k in range(n):
        if s[k] == 1:
            break
    f = {k + 1, 0}
    l = k + 1

    g = {0}
    a = k
    b = 0

    for n in range(k + 1, n):
        d = 0
        for item in f:
            d ^= s[item + n - l]

        if d == 0:
            b += 1
        else:
            if 2 * l > n:
                f ^= set([a - b + item for item in g])
                b += 1
            else:
                temp = f.copy()
                f = set([b - a + item for item in f]) ^ g
                l = n + 1 - l
                g = temp
                a = b
                b = n - l + 1


    degree = max(f)
    c = [0] * (degree + 1)
    for exp in f:
        c[degree - exp] = 1

    return f, c, l

def get_polynomial_string(f):
        result = ''
        lis = sorted(f, reverse=True)
        for i in lis:
            if i == 0:
                result += '1'
            else:
                result += 'x^%s' % str(i)

            if i != lis[-1]:
                result += ' + '
        return result

def generate_lfsr_output(poly, seq_len, seq):
    n = len(poly)
    state = seq[:n-1][::-1]
    output = []
    for i in range(seq_len):
        out = state[0]
        for j in range(1, n):
            if poly[j]:
                out ^= state[j-1]
        state = [out] + state[:-1]
        output.append(out)
    return output[::-1]


def main():
    seq = [0, 1, 1, 0, 1, 0, 0, 1]
    seq2 = [1, 1, 1, 1, 1, 1, 1, 1]
    f, c, L = berlekamp_massey(seq)
    print("Shortest LFSR length: {}".format(L))
    print("Polynomial: {}".format(get_polynomial_string(f)))
    print("LFSR polynomial coefficients (backward): {}".format(c))
    generated_seq = generate_lfsr_output(c[::-1], len(seq), seq2)
    print("original sequence:")
    print(seq)
    print("Generated sequence:")
    print(generated_seq)
    print("Verification result:")
    print(seq == generated_seq)


if __name__ == '__main__':
    main()

berlekamp_massey je pravděpodobně dobře, myslím, že je problém v generování LFSR, počátečním stavu, nebo tvaru polynomu.

Dotaz: Jak na algoritmus Berlekamp–Massey ?

Odpovědi