abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    včera 15:33 | Nová verze

    Open source platforma Home Assistant (Demo, GitHub, Wikipedie) pro monitorování a řízení inteligentní domácnosti byla vydána v nové verzi 2025.8.

    Ladislav Hagara | Komentářů: 2
    včera 14:22 | IT novinky

    Herní studio Hangar 13 vydalo novou Mafii. Mafia: Domovina je zasazena do krutého sicilského podsvětí na začátku 20. století. Na ProtonDB je zatím bez záznamu.

    Ladislav Hagara | Komentářů: 0
    včera 13:22 | IT novinky

    Operátor O2 má opět problémy. Jako omluvu za pondělní zhoršenou dostupnost služeb dal všem zákazníkům poukaz v hodnotě 300 Kč na nákup telefonu nebo příslušenství.

    Ladislav Hagara | Komentářů: 5
    včera 05:55 | IT novinky

    Společnost OpenAI představila GPT-5 (YouTube).

    Ladislav Hagara | Komentářů: 0
    včera 05:00 | Nová verze

    Byla vydána (𝕏) červencová aktualizace aneb nová verze 1.103 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a videi v poznámkách k vydání. Ve verzi 1.103 vyjde také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.

    Ladislav Hagara | Komentářů: 0
    7.8. 17:33 | IT novinky

    Americký prezident Donald Trump vyzval nového generálního ředitele firmy na výrobu čipů Intel, aby odstoupil. Prezident to zdůvodnil vazbami nového šéfa Lip-Bu Tana na čínské firmy.

    Ladislav Hagara | Komentářů: 8
    7.8. 16:55 | Nová verze

    Bylo vydáno Ubuntu 24.04.3 LTS, tj. třetí opravné vydání Ubuntu 24.04 LTS s kódovým názvem Noble Numbat. Přehled novinek a oprav na Discourse.

    Ladislav Hagara | Komentářů: 0
    7.8. 16:44 | Nová verze

    Byla vydána verze 1.89.0 programovacího jazyka Rust (Wikipedie). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example.

    Ladislav Hagara | Komentářů: 0
    7.8. 12:22 | IT novinky

    Americká technologická společnost Apple uskuteční v USA další investice ve výši sta miliard dolarů (2,1 bilionu korun). Oznámil to ve středu šéf firmy Tim Cook při setkání v Bílém domě s americkým prezidentem Donaldem Trumpem. Trump zároveň oznámil záměr zavést stoprocentní clo na polovodiče z dovozu.

    Ladislav Hagara | Komentářů: 5
    7.8. 04:55 | Nová verze

    Zálohovací server Proxmox Backup Server byl vydán v nové stabilní verzi 4.0. Založen je na Debianu 13 Trixie.

    Ladislav Hagara | Komentářů: 0
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (47%)
     (20%)
     (4%)
     (5%)
     (3%)
     (1%)
     (1%)
     (18%)
    Celkem 314 hlasů
     Komentářů: 23, poslední 4.8. 13:01
    Rozcestník

    Dotaz: Jak na algoritmus Berlekamp–Massey ?

    3.4.2023 17:19 Lamada
    Jak na algoritmus Berlekamp–Massey ?
    Přečteno: 548×
    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

    Odpovědi

    3.4.2023 17:45 X
    Rozbalit Rozbalit vše Re: Jak na algoritmus Berlekamp–Massey ?
    Jeste jedna a druha implementace..
    3.4.2023 17:47 X
    Rozbalit Rozbalit vše Re: Jak na algoritmus Berlekamp–Massey ?
    Mimochodem, domaci ukol?
    3.4.2023 21:01 rastos | skóre: 63 | blog: rastos
    Rozbalit Rozbalit vše Re: Jak na algoritmus Berlekamp–Massey ?
    Keby aj bol, tak si zaslúži odpoveď, pretože vyvinul vlastné úsilie a potrebuje len poradiť. Nechce, aby niekto problém vyriešil za neho.
    3.4.2023 22:08 Lamada
    Rozbalit Rozbalit vše Re: Jak na algoritmus Berlekamp–Massey ?
    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.

    Založit nové vláknoNahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.