Puncte:1

Berlekamp Massey ar putea greși SAGEMATH

drapel cn

Acest lucru este în context cu funcția încorporată berlekamp_massey în SAGEMATH.

În timp ce calculez polinomul minim al secvențelor folosind funcția Berlekamp Massey, am simțit că funcția Berlekamp Massey din Sagemath este astfel proiectată încât necesită ca secvența periodică să fie repetată de două ori pentru rezultate corecte. Având în vedere problema calculării complexității liniare a șirului periodic $$s = 110010100001110$$

Funcția Berlekamp Massey cu intrare concatenată $$intrare = s+s$$ dă rezultatul corect.

Cod: berlekamp_massey([GF(2)(1), 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0 , 1, 0, 0, 0, 0, 1, 1, 1, 0])

De ce este necesară dublarea secvenței pentru a calcula polinomul minim corect în SAGEMATH. Totuși, algoritmul original nu spune așa ceva. Este ceva legat de motivul pentru care această funcție acceptă intrare cu lungime egală, acesta este modul în care este definit modulul în sagemath?

Notă: Uneori pentru o secvență s = $(s_0, s_1,......, s_{N-1})$, polinomul minim pentru cazurile care au în vedere șirul $s$ și secvența $s+s$ sunt diferite și în unele cazuri este același. Deci, în cazul în care este diferit, ar trebui să luăm polinomul minim pentru secvența dublu repetată, deoarece este de acord cu considerentele matricei Hankel?

Notă: am făcut multe alte exemple în ultimele zile și apoi prezint acest argument. Multumesc pentru ajutor.

Puncte:2
drapel sa

BMA este un algoritm recursiv. Ieșirea sa este valabilă pentru intrarea cu care o prezentați.

Ieșirea sa este un polinom caracteristic care poate genera $$(s_1,\ldots,s_N)\quad(1)$$ dar așa cum am explicat într-un răspuns la întrebarea dvs. conexă Aici cu formula Hankel, în general, recurența se poate schimba pe măsură ce luați în considerare segmente mai lungi

$$(s_1,\ldots,s_{N+i})$$

a secvenței și este posibil să nu se stabilească într-un polinom caracteristic final până când dvs considera $$(s_1,\ldots,s_{2N}).$$

Alegerea dvs. de a repeta segmentul inițial este doar unul posibil asemenea extindere. Și prin definiție ieșirea BMA după această extensie este valabilă și pentru prima $N$ biți ai secvenței din (1).

Mathpdegeek497 avatar
drapel cn
mulțumesc, cred că acum încep să fac mireasă câteva lacune în timp ce studiez algoritmul Berlekamp Massey, doar un lucru care acum mă deranjează este „ar trebui să luăm extensia secvenței $s_N$ până când recurența se stabilește sau ieșirea algoritmului pentru primii N biți poate fi considerată un răspuns corect în fiecare caz”? Această întrebare despre stabilirea polinomului minim cu extensie crescândă este ceea ce mă deranjează peste zile. M-aș bucura dacă m-ați ajuta să rezolv asta.
kodlu avatar
drapel sa
De fapt, nu ar trebui să te deranjeze deloc. Este așa cum ar trebui să fie. Având în vedere primii $N$ biți ai secvenței, există $2^N$ moduri diferite de extindere a secvenței la $2N$ biți. Doar *unul* dintre acestea este concatenarea ta. Desigur, pentru ca BMA să fie validă, fiecare dintre aceste extensii poate avea, în principiu, propriul polinom caracteristic definit pe o secvență de lungime $2N.$

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.