Revision as of 18:09, 1 November 2024 edit LR.127 (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 25,442 edits Adding local short description: "Algorithm on linear-feedback shift registers", overriding Wikidata description "algorithm" Tag: Shortdesc helper ← Previous edit		Revision as of 03:42, 22 November 2024 edit undo Beland (talk \| contribs) Autopatrolled, Administrators 259,081 edits de-subst to make wikitext readable Next edit →
Line 104: T(D) T(x) polynomial --> ~~<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr">~~ <syntaxhighlight lang="c"> <span class="n">polynomial</span><span class="p">(</span><span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="cm">/* coeffs are s_j; output sequence as N-1 degree polynomial) /</span> polynomial(field K) s(x) = ... / coeffs are s_j; output sequence as N-1 degree polynomial) / ~~<span class="cm">~~/ connection polynomial /~~</span>~~ <span class="n">polynomial</span><span class="p">(</span><span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="p">)</span><span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"> </span><span class="cm">/ coeffs are c_j /</span> polynomial(field K) C(x) = 1; / coeffs are c_j / <span class="n">polynomial</span><span class="p">(</span><span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="p">)</span><span class="w"> </span><span class="n">B</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span> polynomial(field K) B(x) = 1; ~~<span class="kt">int</span><span class="w"> </span><span class="n">L</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span>~~ int L = 0; ~~<span class="kt">int</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span>~~ int m = 1; <span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span> field K b = 1; ~~<span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="p">;</span>~~ int n; ~~<span class="cm">~~/ steps 2. and 6. /~~</span>~~ <span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">N</span><span class="p">;</span><span class="w"> </span><span class="n">n</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> for (n = 0; n < N; n++) { ~~<span~~ ~~class="w">~~ ~~</span><span class="cm">~~/ step 2. calculate discrepancy /~~</span>~~ <span class="w"> </span><span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">s_n</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><math>\sum_{i=1}^L c_i \cdot s_{n-i}</math><span class="p">;</span> field K d = s_n + ∑i=1Lci⋅sn−i; <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">d</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> if (d == 0) { ~~<span~~ ~~class="w">~~ ~~</span><span class="cm">~~/ step 3. discrepancy is zero; annihilation continues /~~</span>~~ <span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span> m = m + 1; <span class="w"> </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="mi">2</span><span class="w"> </span><span class="o"></span><span class="w"> </span><span class="n">L</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">n</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> } else if (2 * L <= n) { ~~<span class="w"> </span><span class="cm">/* step 5. /</span>~~ / step 5. / ~~<span~~ ~~class="w">~~ ~~</span><span class="cm">~~/ temporary copy of C(x) /~~</span>~~ <span class="w"> </span><span class="n">polynomial</span><span class="p">(</span><span class="n">field</span><span class="w"> </span><span class="n">K</span><span class="p">)</span><span class="w"> </span><span class="n">T</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> polynomial(field K) T(x) = C(x); <span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><math>b^{-1} x^m</math><span class="w"> </span><span class="n">B</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> C(x) = C(x) - d b−1xm B(x); <span class="w"> </span><span class="n">L</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">L</span><span class="p">;</span> L = n + 1 - L; <span class="w"> </span><span class="n">B</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">T</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> B(x) = T(x); ~~<span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">d</span><span class="p">;</span>~~ b = d; ~~<span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span>~~ m = 1; ~~<span class="w"> </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span>~~ } else { ~~<span class="w"> </span><span class="cm">/ step 4. /</span>~~ / step 4. */ <span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">C</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><math>b^{-1} x^m</math><span class="w"> </span><span class="n">B</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> C(x) = C(x) - d b−1xm B(x); <span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span> m = m + 1; ~~<span class="w"> </span><span class="p">}</span>~~ } ~~<span class="p">}</span>~~ } ~~<span class="k">return</span><span class="w"> </span><span class="n">L</span><span class="p">;</span>~~ return L; ~~</div>~~ </syntaxhighlight> In the case of binary GF(2) BCH code, the discrepancy d will be zero on all odd steps, so a check can be added to avoid calculating it.

Berlekamp–Massey algorithm: Difference between revisions