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 20:22 | Zajímavý software

    Navigace se soukromím CoMaps postavena nad OpenStreetMap je nově k dispozici v Google Play, App Store i F-Droid. Jedná se o komunitní fork aplikace Organic Maps.

    Ladislav Hagara | Komentářů: 1
    včera 19:33 | Nová verze

    Vývojáři OpenMW (Wikipedie) oznámili vydání verze 0.49.0 této svobodné implementace enginu pro hru The Elder Scrolls III: Morrowind. Přehled novinek i s náhledy obrazovek v oznámení o vydání.

    Ladislav Hagara | Komentářů: 1
    včera 15:22 | IT novinky

    Masivní výpadek elektrického proudu zasáhl velkou část České republiky. Hasiči vyjížděli k většímu počtu lidí uvězněných ve výtazích. Výpadek se týkal zejména severozápadu republiky, dotkl se také Prahy, Středočeského nebo Královéhradeckého kraje. Ochromen byl provoz pražské MHD, linky metra se už podařilo obnovit. Výpadek proudu postihl osm rozvoden přenosové soustavy, pět z nich je nyní opět v provozu. Příčina problémů je však stále neznámá. Po 16. hodině zasedne Ústřední krizový štáb.

    Ladislav Hagara | Komentářů: 39
    včera 02:33 | Nová verze

    Po více než roce vývoje od vydání verze 5.40 byla vydána nová stabilní verze 5.42 programovacího jazyka Perl (Wikipedie). Do vývoje se zapojilo 64 vývojářů. Změněno bylo přibližně 280 tisíc řádků v 1 500 souborech. Přehled novinek a změn v podrobném seznamu.

    Ladislav Hagara | Komentářů: 7
    včera 01:33 | Nová verze

    Byla vydána nová stabilní verze 7.5 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 138. Přehled novinek i s náhledy v příspěvku na blogu.

    Ladislav Hagara | Komentářů: 0
    3.7. 16:33 | Zajímavý software

    Sniffnet je multiplatformní aplikace pro sledování internetového provozu. Ke stažení pro Windows, macOS i Linux. Jedná se o open source software. Zdrojové kódy v programovacím jazyce Rust jsou k dispozici na GitHubu. Vývoj je finančně podporován NLnet Foundation.

    Ladislav Hagara | Komentářů: 0
    3.7. 12:33 | Nová verze

    Byl vydán Debian Installer Trixie RC 2, tj. druhá RC verze instalátoru Debianu 13 s kódovým názvem Trixie.

    Ladislav Hagara | Komentářů: 0
    3.7. 03:33 | Komunita

    Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za červen (YouTube).

    Ladislav Hagara | Komentářů: 0
    3.7. 02:33 | Nová verze

    Libreboot (Wikipedie) – svobodný firmware nahrazující proprietární BIOSy, distribuce Corebootu s pravidly pro proprietární bloby – byl vydán ve verzi 25.06 "Luminous Lemon". Přidána byla podpora desek Acer Q45T-AM a Dell Precision T1700 SFF a MT. Současně byl ve verzi 25.06 "Onerous Olive" vydán také Canoeboot, tj. fork Librebootu s ještě přísnějšími pravidly.

    Ladislav Hagara | Komentářů: 0
    3.7. 01:33 | Komunita

    Licence GNU GPLv3 o víkendu oslavila 18 let. Oficiálně vyšla 29. června 2007. Při té příležitosti Richard E. Fontana a Bradley M. Kuhn restartovali, oživili a znovu spustili projekt Copyleft-Next s cílem prodiskutovat a navrhnout novou licenci.

    Ladislav Hagara | Komentářů: 0
    Jaký je váš oblíbený skriptovací jazyk?
     (59%)
     (27%)
     (7%)
     (2%)
     (1%)
     (1%)
     (3%)
    Celkem 355 hlasů
     Komentářů: 16, poslední 8.6. 21:05
    Rozcestník

    Dotaz: Jak na algoritmus Berlekamp–Massey ?

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