Berlekamp–Massey input sequence length

For a given periodic sequence of length $N$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $2N$, i.e., the repeated input sequence or just the input sequence itself? The doubt arise because by taking the original sequence $S$ of length $N$, and the sequence $S \| S$ (concatenation) of length $2N$, I found that the minimal polynomial value changes but I am unable to understand why the minimal polynomial should change.

SageMath

Example 1:

If I consider the sequence to be s=0101110 and then it repeats. Then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^3+x+1$$

code:

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

(Here I have to repeat the sequence because the length must be even)

Example 2:

If I consider the sequence to be s=011101 and then it repeats then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^3+x^2+1$$

code:

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

(since the length is even the berlekamp massey function accepts this)

Example 3:

If I consider the sequence to be s=011101 and then it repeats; then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^5+x^4+x^3+x^2+1$$

code:

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

(Here I intentionally repeated this)

So, My question is how to actually compute the linear complexity of sequence in SageMath using Berlekamp–Massey function? which of the above examples are correct and which are incorrect?

ฉันใช้รหัสหลามของ bma.bozhu.me (ไซต์ไม่ทำงานเมื่อเร็ว ๆ นี้ (ปัญหา HTTP) รอคำตอบนาน..)

1. ตัวอย่าง : ลำดับการทำซ้ำ $s=(0, 1, 0, 1, 1, 1, 0)$

    ลำดับ = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0)
    (โพลี, สแปน) = Berlekamp_Massey_algorithm(seq)
   

   เอาต์พุต

   ลำดับอินพุตคือ (0, 1, 0, 1, 1, 1, 0) พหุนามลักษณะเฉพาะของมันคือ (x^3 + x^1 + 1) และสแปนเชิงเส้นคือ 3

2. ตัวอย่าง: ลำดับการทำซ้ำ $s=(0, 1, 1, 1, 0, 1)$

   วินาที = (0,1,1,1,0,1)
   (โพลี, สแปน) = Berlekamp_Massey_algorithm(seq)
   

   ลำดับอินพุตคือ (0, 1, 1, 1, 0, 1) พหุนามลักษณะเฉพาะของมันคือ (x^3 + x^2 + 1) และสแปนเชิงเส้นคือ 3

3. ตัวอย่าง : ลำดับการทำซ้ำ $s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)$

   ลำดับ = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)
   (โพลี, สแปน) = Berlekamp_Massey_algorithm(seq)
   

   ลำดับอินพุตคือ (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1) พหุนามลักษณะเฉพาะของมันคือ (x^5 + x^4 + x^3 + x^2 + x^1 + 1) และสแปนเชิงเส้นคือ 5

ใช่, ดูเหมือนว่าจะเป็นปัญหา แต่ไม่ใช่!

เมื่อ Belekamp-Massey สร้างผลลัพธ์ BM สร้างพหุนามขั้นต่ำ. นี้ ไม่ได้หมายความว่าจะตรงกับอินพุตถัดไปของคุณ.

จดจำ, LFSR ของความยาว $L$ สามารถสร้างลำดับความยาวเป็นช่วงๆ $2^L-1$; ทั้งหมด $L$ความยาวสตริงไบนารียกเว้นศูนย์ทั้งหมด ดังนั้นการมีปริญญา $3$ หมายความว่า LFSR สูงสุดสามารถสร้างลำดับขนาดได้ $7$. ลำดับธาตุที่แท้จริงคือ $(0, 1, 1, 1, 0, 1,0)$ สังเกตว่าเรามีสามเท่าทั้งหมดยกเว้นศูนย์

อาจมี LFSR ที่มีพหุนามที่ไม่ใช่แบบดั้งเดิมที่สามารถสร้างลำดับของคุณได้ นี่ไม่ใช่งานของ BM

กรณีที่สามก็มีปัญหาคล้ายๆ กัน เหลือให้ท่านผู้อ่าน

กำลังดูโปรไฟล์ความซับซ้อนเชิงเส้น

เมื่อพิจารณาถึงคุณภาพของการสุ่มของลำดับ จะมีการเสนอโปรไฟล์เชิงเส้นที่ซับซ้อนด้วย ในกรณีนี้ ลำดับจะได้รับและสร้างโปรไฟล์ของความซับซ้อนเชิงเส้น Rainer A. Rueppel^* วิเคราะห์อย่างกว้างขวางในเรื่องนี้ การวิเคราะห์และออกแบบรหัสสตรีม

ลำดับ PN ถูกสร้างขึ้นโดย LFSR ดังที่เราเห็น LCP ไม่เติบโต! (ลำดับของคุณมี LCP 3 และ 5) การโยนเหรียญเป็นกุญแจสู่ความเข้าใจ

• เมื่อมีการป้อนอินพุตใหม่ให้กับ BM หากสเตจปัจจุบันสามารถสร้างได้ คอมเพล็กซ์เชิงเส้นจะคงเดิม หากไม่ปรับความซับซ้อนเชิงเส้นเพื่อให้ LFST ที่ผลิตยอมรับอันก่อนหน้าและอันใหม่ด้วย

ดังนั้น, BM จะสร้าง LFSR ที่สั้นที่สุดให้กับส่วนที่กำหนดให้เท่านั้น ไม่ได้ระบุว่าอินพุตถัดไปจะคำนวณทางคณิตศาสตร์กับ LFSR ปัจจุบัน

หมายเหตุ: ดูเหมือนว่า SageMath กำลังทำงานอยู่

^* Rainer A. Rueppel เป็นนักเรียนของ เจมส์ แอล. แมสซีย์. ดูเหมือนว่านี่จะเป็นหนังสือเล่มแรกในซีรี่ส์ Springer ที่อุทิศให้กับการเข้ารหัส

แง่มุมหนึ่งของสิ่งนี้คือหากการคำนวณการเกิดซ้ำสำหรับลำดับ $(s_t)_{t \geq 0}$ คือความยาว $L$คุณต้องรอจนกว่าจะสังเกต $2L$ สัญลักษณ์เพื่อตรวจสอบว่า LFSR ที่สร้างขึ้นจนถึงปัจจุบันนั้นถูกต้องจริง เนื่องจากค่าสัมประสิทธิ์ต้องเป็นไปตามสมการเมทริกซ์ $$ \left[\begin{อาร์เรย์}{ccccc} s_0 & s_1 & s_2 & \cdots & s_{L-1} \ s_1 & s_2 & s_3 & \cdots & s_{L} \ & \vจุด & & \vจุด & \ s_{L-1} & s_{L} & s_{L+1} & \cdots & s_{2L-2} \ \end{อาร์เรย์} \right] \ซ้าย[ \begin{อาร์เรย์}{c} c_L \ c_{L-1} \ \vdots \ c_1\end{อาร์เรย์} \right] = \ซ้าย[ \begin{อาร์เรย์}{c} s_L \ s_{L+1} \ \vdots \ s_{2L-1}\end{อาร์เรย์} \right] $$

ที่ไหน $c_1,\ldots,c_L$ เป็นค่าสัมประสิทธิ์ของสมการคุณลักษณะเพื่อให้ใช้ได้

นี่เป็นเพราะลักษณะการเกิดขึ้นซ้ำซ้อนกันจึงต้องถือต่อไปจนกระทั่งสัญลักษณ์สุดท้าย ($s_L$) ตามที่คำนวณไม่ได้เป็นส่วนหนึ่งของสมการเมทริกซ์อีกต่อไป

กำหนดลำดับ $S$ ความยาว $2N$ อัลกอริทึม Berlekamp-Massey ค้นหา LFSR ซึ่งสร้างลำดับเดียวกัน $S$ (โดยเฉพาะอย่างยิ่งมันสั้นที่สุด) แต่คุณไม่รู้ว่าลำดับนั้นมีช่วงเวลาหรือไม่ $N$. คุณรู้เพียงว่าด้วยสถานะเริ่มต้นที่ถูกต้อง ลำดับที่ผลิตจะเท่ากับสถานะในอินพุต การคำนวณทั้งหมดจะอยู่ใน $GF(2)$.

ตัวอย่างที่ 2: LFSR ที่มีพหุนามน้อยที่สุด $x^3+x^2+1$ เป็น $s_{n+3}=s_{n+2}+s_n$ และเราต้องการ 3 ค่าเริ่มต้นเพื่อสร้างลำดับ (เพราะมันขึ้นอยู่กับ $s_n$ และ $s_{n+2}$). ในตัวอย่าง สถานะเริ่มต้นคือ $S=011$, นั่นคือ $s_0=0$, $s_1=1$, $s_2=1$. คุณจะเห็นว่าค่าถัดไปจะเหมือนกับในลำดับ $s_3=s_2+s_0=1$, $s_4=0$, $s_5=1$. อย่างไรก็ตาม คาบของลำดับนี้ไม่ใช่ 6 ดังนั้น LFSR นี้จึงไม่ถูกต้องสำหรับลำดับนี้ $S || เหรียญสิงคโปร์ (นั่นคือถ้าคุณดำเนินการผลิตบิตด้วย LFSR นี้ คุณจะได้รับลำดับที่แตกต่างจาก $S||S$).

ตัวอย่างที่ 3: บิตเริ่มต้นของลำดับนี้เหมือนกัน แต่คราวนี้ลำดับที่สั้นที่สุดนั้นซับซ้อนกว่า $s_{n+5}=s_{n+4}+s_{n+3}+s_{n+2}+s_{n+1}+s_{n}$ และรัฐคือ $5$ บิตยาว แน่นอนถ้าคุณใช้ลำดับนี้กับสถานะเริ่มต้น $01110$ บิตที่หกเท่ากับลำดับในตัวอย่างที่ 2 (นั่นคือบิต $0+1+1+1+0=1$) แต่ให้สถานะเริ่มต้น $01110$ คุณสามารถสร้างลำดับได้ $011101011101$.