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í
×
    dnes 06:00 | Komunita

    Na čem aktuálně pracují vývojáři GNOME a KDE Plasma? Pravidelný přehled novinek v Týden v GNOME a Týden v KDE Plasma. Vypíchnout lze, že v Plasmě byl implementován 22letý požadavek. Historie schránky nově umožňuje ohvězdičkovat vybrané položky a mít k ním trvalý a snadný přístup.

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

    Wayfire, kompozitní správce oken běžící nad Waylandem a využívající wlroots, byl vydán ve verzi 0.10.0. Zdrojové kódy jsou k dispozici na GitHubu. Videoukázky na YouTube.

    Ladislav Hagara | Komentářů: 0
    včera 04:00 | Komunita

    Před necelými čtyřmi měsíci byl Steven Deobald jmenován novým výkonným ředitelem GNOME Foundation. Včera skončil, protože "nebyl pro tuto roli v tento čas ten pravý".

    Ladislav Hagara | Komentářů: 7
    29.8. 18:33 | Zajímavý článek

    Nové číslo časopisu Raspberry Pi zdarma ke čtení: Raspberry Pi Official Magazine 156 (pdf).

    Ladislav Hagara | Komentářů: 0
    29.8. 15:11 | Nová verze

    Armbian, tj. linuxová distribuce založená na Debianu a Ubuntu optimalizovaná pro jednodeskové počítače na platformě ARM a RISC-V, ke stažení ale také pro Intel a AMD, byl vydán ve verzi 25.8.1. Přehled novinek v Changelogu.

    Ladislav Hagara | Komentářů: 0
    29.8. 12:11 | IT novinky

    Včera večer měl na YouTube premiéru dokumentární film Python: The Documentary | An origin story.

    Ladislav Hagara | Komentářů: 0
    28.8. 23:33 | Nová verze

    Společnost comma.ai po třech letech od vydání verze 0.9 vydala novou verzi 0.10 open source pokročilého asistenčního systému pro řidiče openpilot (Wikipedie). Zdrojové kódy jsou k dispozici na GitHubu.

    Ladislav Hagara | Komentářů: 0
    28.8. 21:55 | Nová verze Ladislav Hagara | Komentářů: 4
    28.8. 14:11 | IT novinky

    Řada vestavěných počítačových desek a vývojových platforem NVIDIA Jetson se rozrostla o NVIDIA Jetson Thor. Ve srovnání se svým předchůdcem NVIDIA Jetson Orin nabízí 7,5krát vyšší výpočetní výkon umělé inteligence a 3,5krát vyšší energetickou účinnost. Softwarový stack NVIDIA JetPack 7 je založen na Ubuntu 24.04 LTS.

    Ladislav Hagara | Komentářů: 4
    28.8. 00:44 | Bezpečnostní upozornění

    Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) spolu s NSA a dalšími americkými úřady upozorňuje (en) na čínského aktéra Salt Typhoon, který kompromituje sítě po celém světě.

    Ladislav Hagara | Komentářů: 26
    Pro otevření více webových stránek ve webovém prohlížečí používám
     (80%)
     (9%)
     (3%)
     (3%)
     (4%)
     (1%)
    Celkem 115 hlasů
     Komentářů: 9, poslední 28.8. 11:53
    Rozcestník

    Dotaz: Jak na algoritmus Berlekamp–Massey ?

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