# Finding the LFSR and connection polynomial for binary sequence.

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence:

$0110010101101$ producing LFSR $\langle{}7, 1 + x^3 + x^4 + x^6\rangle{}$

i.e. coefficients $c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, c_6 = 1, c_7 = 0$

However, when using the recurrence relation

\begin{equation} s_j = (c_1s_{j-1} + c_2s_{j-2} + \cdots + c_Ls_{j-L}) \mbox{ for } j \geq L. \end{equation} to check the result, I get back:

0110010001111, which is obviously not right.

Using the Berlekamp-Massey Algorithm calculator they say the (I believe) characteristic polynomial should be $x^7 + x^4 + x^3 + x^1$. Which, according to my paper working, the reciprocal should indeed be $1 + x^3 + x^4 + x^6$.

What am I doing wrong? Where is my understanding lacking?

-

## 2 Answers

This is probably just a difference in notation than any failure in understanding or implementation. Some people define recurrence relations with subscripts in reverse order than others; the original description given by Berlekamp in his 1968 book Algebraic Coding Theory began counting from $1$ instead of $0$ etc. Observe that $$x^7 + x^4 + x^3 + x^1 = x^7(1 + x^{-3} + x^{-4} + x^{-6})$$ in comparison to your $1 + x^3 + x^4 + x^6$ which you say is the correct reciprocal of what the web site's answer should be. So I would say that the web site seems to be following Berlekamp's original description and giving you an answer that is "off-by-one".

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9157570004463196, "perplexity_flag": "middle"}