Namespaces
Variants
Actions

Difference between revisions of "Berlekamp-Massey algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(details)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 57 formulas, 57 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
A procedure for solving an equation of the form
 
A procedure for solving an equation of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201401.png" /></td> </tr></table>
+
\begin{equation*} \sigma ( z ) S ( z ) \equiv \omega ( z ) ( \operatorname { mod } z ^ { 2 t } ) \end{equation*}
  
for the polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201402.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201403.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201404.png" />, given the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201405.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201406.png" />. Originally intended for the decoding of certain cyclic error-correcting codes (cf. also [[Error-correcting code|Error-correcting code]]), it has since found wide application in unrelated areas.
+
for the polynomials $\sigma ( z )$, $\omega ( z )$, $\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z ) \leq t$, given the polynomial $S ( z )$, $\operatorname { deg } S ( z ) < 2 t$. Originally intended for the decoding of certain cyclic error-correcting codes (cf. also [[Error-correcting code|Error-correcting code]]), it has since found wide application in unrelated areas.
  
The decoding of cyclic error-correcting codes defined over a [[Finite field|finite field]], such as Bose–Chaudhuri–Hocquenghem and Reed–Solomon codes, can be achieved by solving the above equation, referred to as the key equation [[#References|[a1]]] in this context, where the minimum distance of the code is at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201407.png" />. For cyclic codes of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201408.png" /> over the finite field with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b1201409.png" /> elements, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014010.png" />, codewords are viewed as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014011.png" />-tuples over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014012.png" />, and also naturally identified with polynomials over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014013.png" /> of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014014.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014015.png" /> be a primitive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014016.png" />-th root of unity in an extension field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014017.png" />. The coordinate positions of the code are identified with the distinct powers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014018.png" />. Cyclic codes with designed distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014019.png" /> consist of all codeword polynomials having a common set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014020.png" /> consecutive powers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014021.png" /> as zeros, the zero set of the code. The polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014022.png" /> is the syndrome polynomial whose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014023.png" />th coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014025.png" />, is the evaluation of the received word, at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014026.png" />th element of the zero set of the code. The received word is the sum of the transmitted codeword with an error word, over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014027.png" />, whose non-zero coordinate positions correspond to error locations. It is assumed there are at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014028.png" /> coordinate positions in error. The decoding process retrieves the transmitted codeword. The unique solution to the key equation gives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014029.png" />, the error locator polynomial, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014030.png" />, the error evaluator polynomial. The zeros of the error evaluator polynomial yield the coordinate positions at which errors occur and the error value at such an error position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014031.png" /> is given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014033.png" /> indicates the formal derivative.
+
The decoding of cyclic error-correcting codes defined over a [[Finite field|finite field]], such as Bose–Chaudhuri–Hocquenghem and Reed–Solomon codes, can be achieved by solving the above equation, referred to as the key equation [[#References|[a1]]] in this context, where the minimum distance of the code is at least $2 t + 1$. For cyclic codes of length $n$ over the finite field with $q$ elements, $\mathbf{F} _ { q }$, codewords are viewed as $n$-tuples over $\mathbf{F} _ { q }$, and also naturally identified with polynomials over $\mathbf{F} _ { q }$ of degree at most $n - 1$. Let $\alpha$ be a primitive $n$-th root of unity in an extension field of $\mathbf{F} _ { q }$. The coordinate positions of the code are identified with the distinct powers of $\alpha$. Cyclic codes with designed distance $2 t + 1$ consist of all codeword polynomials having a common set of $2 t$ consecutive powers of $\alpha$ as zeros, the zero set of the code. The polynomial $S ( z )$ is the syndrome polynomial whose $i$th coefficient $S_i \in \mathbf{F} _ { q }$, $i = 0 , \ldots , 2 t - 1$, is the evaluation of the received word, at the $i$th element of the zero set of the code. The received word is the sum of the transmitted codeword with an error word, over $\mathbf{F} _ { q }$, whose non-zero coordinate positions correspond to error locations. It is assumed there are at most $t$ coordinate positions in error. The decoding process retrieves the transmitted codeword. The unique solution to the key equation gives $\sigma ( z )$, the error locator polynomial, and $\omega ( z )$, the error evaluator polynomial. The zeros of the error evaluator polynomial yield the coordinate positions at which errors occur and the error value at such an error position $\beta$ is given by $\omega ( \beta ) / \sigma ^ { \prime } ( \beta )$, where $\sigma ^ { \prime }$ indicates the formal derivative.
  
 
E.R. Berlekamp [[#References|[a1]]] gave a computationally efficient iterative algorithm to solve the key equation for the two polynomials. J.L. Massey [[#References|[a4]]] showed that this algorithm gives a general solution to the problem of synthesizing the shortest linear feedback shift register that generates the syndrome sequence. At each stage the algorithm incrementally adjusts the length of the shift register and the feedback multiplier taps to generate the syndrome sequence to that point and terminates when the whole sequence is generated. In this formulation, the set of shift register feedback tap values yields the coefficients of the error locator polynomial. The iterative algorithm of Berlekamp and the feedback shift register synthesis interpretation is known as the Berlekamp–Massey algorithm.
 
E.R. Berlekamp [[#References|[a1]]] gave a computationally efficient iterative algorithm to solve the key equation for the two polynomials. J.L. Massey [[#References|[a4]]] showed that this algorithm gives a general solution to the problem of synthesizing the shortest linear feedback shift register that generates the syndrome sequence. At each stage the algorithm incrementally adjusts the length of the shift register and the feedback multiplier taps to generate the syndrome sequence to that point and terminates when the whole sequence is generated. In this formulation, the set of shift register feedback tap values yields the coefficients of the error locator polynomial. The iterative algorithm of Berlekamp and the feedback shift register synthesis interpretation is known as the Berlekamp–Massey algorithm.
  
The solution to the key equation, and hence the Berlekamp–Massey algorithm, has connections to several other algorithms, most notably the extended [[Euclidean algorithm|Euclidean algorithm]] [[#References|[a5]]], [[#References|[a3]]] and continued fractions [[#References|[a6]]] (cf. also [[Continued fraction|Continued fraction]]). The extended Euclidean algorithm iteratively determines the [[Greatest common divisor|greatest common divisor]] of two elements in a Euclidean domain, in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014034.png" />. Specifically, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014035.png" />, define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014037.png" /> and define a sequence of quotient and remainder polynomials by
+
The solution to the key equation, and hence the Berlekamp–Massey algorithm, has connections to several other algorithms, most notably the extended [[Euclidean algorithm|Euclidean algorithm]] [[#References|[a5]]], [[#References|[a3]]] and continued fractions [[#References|[a6]]] (cf. also [[Continued fraction|Continued fraction]]). The extended Euclidean algorithm iteratively determines the [[Greatest common divisor|greatest common divisor]] of two elements in a Euclidean domain, in this case $\mathbf F _ { q }  [ z ]$. Specifically, for $a ( z ) , b ( z ) \in \mathbf{F} _ { q } [ z ]$, define $r_{ - 1} ( z ) = a ( z )$ and $r_0 ( z ) = b ( z )$ and define a sequence of quotient and remainder polynomials by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014038.png" /></td> </tr></table>
+
\begin{equation*} r _ { i - 2} ( z ) = q _ { i } ( z ) r _ { i - 1} ( z ) + r _ { i } ( z ) , \quad i = 1,2 ,\dots . \end{equation*}
  
The degrees of the remainder polynomials are strictly decreasing and the last non-zero remainder polynomial is the greatest common divisor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014040.png" />. The quotient polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014041.png" /> can be used to define a sequence of subsidiary polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014043.png" /> with strictly increasing degrees, such that at each stage of the algorithm
+
The degrees of the remainder polynomials are strictly decreasing and the last non-zero remainder polynomial is the greatest common divisor of $a ( z )$, $b ( z )$. The quotient polynomials $q_i( z )$ can be used to define a sequence of subsidiary polynomials $s _ { i } ( z )$ and $t _ { i } ( z )$ with strictly increasing degrees, such that at each stage of the algorithm
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014044.png" /></td> </tr></table>
+
\begin{equation*} s _ { i } ( z ) a ( z ) + t _ { i } ( z ) b ( z ) = r _ { i } ( z ), \end{equation*}
  
so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014045.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014046.png" />. Applied to the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014048.png" />, since the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014049.png" /> have strictly decreasing degrees and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014050.png" /> strictly increasing degrees, it can be shown that the algorithm reaches a unique point where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014051.png" />, yielding a solution to the key equation.
+
so that $s _ { i } ( z ) a ( z ) \equiv r _ { i } ( z ) ( \operatorname { mod } b ( z ) )$ for all $i$. Applied to the case $a ( z ) = S ( z )$ and $b ( z ) = z ^ { 2 t }$, since the $r_i$ have strictly decreasing degrees and the $s_i$ strictly increasing degrees, it can be shown that the algorithm reaches a unique point where $t \geq \operatorname { deg } s _ { i } > \operatorname { deg } r _ { i }$, yielding a solution to the key equation.
  
 
Recasting the key equation as
 
Recasting the key equation as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014052.png" /></td> </tr></table>
+
\begin{equation*} S ( z ) \equiv \frac { \omega ( z ) } { \sigma ( z ) } ( \operatorname { mod } z ^ { 2 t } ), \end{equation*}
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014053.png" />, the problem is to determine the smallest degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014054.png" />, of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014056.png" /> such that the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120140/b12014057.png" /> terms of the expansion of the fraction about the origin yields the sequence of syndromes. Such a partial fraction expansion leads naturally to an equivalent continued fraction interpretation of the Berlekamp–Massey algorithm [[#References|[a6]]].
+
$\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z ) \leq t$, the problem is to determine the smallest degree $\sigma ( z )$, of degree at most $t$, $\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z )$ such that the first $2 t$ terms of the expansion of the fraction about the origin yields the sequence of syndromes. Such a partial fraction expansion leads naturally to an equivalent continued fraction interpretation of the Berlekamp–Massey algorithm [[#References|[a6]]].
  
 
The Berlekamp–Massey algorithm has found numerous applications outside of the coding context. These include fast algorithms in numerical analysis such as Lanczos recursion and Levinson–Shur algorithms for Toeplitz matrices, as well as problems of minimal realizations in system theory [[#References|[a2]]].
 
The Berlekamp–Massey algorithm has found numerous applications outside of the coding context. These include fast algorithms in numerical analysis such as Lanczos recursion and Levinson–Shur algorithms for Toeplitz matrices, as well as problems of minimal realizations in system theory [[#References|[a2]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E.R. Berlekamp,  "Algebraic coding theory" , McGraw-Hill  (1968)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T. Kailath,  "Encounters with the Berlekamp–Massey algorithm"  R.E. Blahut (ed.)  D.J. Costello Jr. (ed.)  U. Maureer (ed.)  T. Mittelholzer (ed.) , ''Communications and Cryptography, Two Sides of One Tapestry'' , Kluwer Acad. Publ.  (1994)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.J. McEliece,  "The theory of information and coding" , ''Encycl. Math. Appl.'' , '''3''' , Addison-Wesley  (1977)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J.L. Massey,  "Shift register synthesis and BCH decoding"  ''IEEE Trans. Inform. Th.'' , '''IT-19'''  (1969)  pp. 122–127</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Y. Sugiyama,  S. Kasahara,  S. Hirasawa,  T. Namekawa,  "A method for solving key equation for decoding Goppa codes"  ''Inform. Control'' , '''27'''  (1975)  pp. 87–99</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  L.R. Welch,  R.A. Scholtz,  "Continued fractions and Berlekamp's algorithm"  ''IEEE Trans. Inform. Th.'' , '''IT-25'''  (1979)  pp. 19–27</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  E.R. Berlekamp,  "Algebraic coding theory" , McGraw-Hill  (1968)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  T. Kailath,  "Encounters with the Berlekamp–Massey algorithm"  R.E. Blahut (ed.)  D.J. Costello Jr. (ed.)  U. Maureer (ed.)  T. Mittelholzer (ed.) , ''Communications and Cryptography, Two Sides of One Tapestry'' , Kluwer Acad. Publ.  (1994)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  R.J. McEliece,  "The theory of information and coding" , ''Encycl. Math. Appl.'' , '''3''' , Addison-Wesley  (1977)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  J.L. Massey,  "Shift register synthesis and BCH decoding"  ''IEEE Trans. Inform. Th.'' , '''IT-19'''  (1969)  pp. 122–127</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  Y. Sugiyama,  S. Kasahara,  S. Hirasawa,  T. Namekawa,  "A method for solving key equation for decoding Goppa codes"  ''Inform. Control'' , '''27'''  (1975)  pp. 87–99</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  L.R. Welch,  R.A. Scholtz,  "Continued fractions and Berlekamp's algorithm"  ''IEEE Trans. Inform. Th.'' , '''IT-25'''  (1979)  pp. 19–27</td></tr></table>

Latest revision as of 18:48, 26 January 2024

A procedure for solving an equation of the form

\begin{equation*} \sigma ( z ) S ( z ) \equiv \omega ( z ) ( \operatorname { mod } z ^ { 2 t } ) \end{equation*}

for the polynomials $\sigma ( z )$, $\omega ( z )$, $\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z ) \leq t$, given the polynomial $S ( z )$, $\operatorname { deg } S ( z ) < 2 t$. Originally intended for the decoding of certain cyclic error-correcting codes (cf. also Error-correcting code), it has since found wide application in unrelated areas.

The decoding of cyclic error-correcting codes defined over a finite field, such as Bose–Chaudhuri–Hocquenghem and Reed–Solomon codes, can be achieved by solving the above equation, referred to as the key equation [a1] in this context, where the minimum distance of the code is at least $2 t + 1$. For cyclic codes of length $n$ over the finite field with $q$ elements, $\mathbf{F} _ { q }$, codewords are viewed as $n$-tuples over $\mathbf{F} _ { q }$, and also naturally identified with polynomials over $\mathbf{F} _ { q }$ of degree at most $n - 1$. Let $\alpha$ be a primitive $n$-th root of unity in an extension field of $\mathbf{F} _ { q }$. The coordinate positions of the code are identified with the distinct powers of $\alpha$. Cyclic codes with designed distance $2 t + 1$ consist of all codeword polynomials having a common set of $2 t$ consecutive powers of $\alpha$ as zeros, the zero set of the code. The polynomial $S ( z )$ is the syndrome polynomial whose $i$th coefficient $S_i \in \mathbf{F} _ { q }$, $i = 0 , \ldots , 2 t - 1$, is the evaluation of the received word, at the $i$th element of the zero set of the code. The received word is the sum of the transmitted codeword with an error word, over $\mathbf{F} _ { q }$, whose non-zero coordinate positions correspond to error locations. It is assumed there are at most $t$ coordinate positions in error. The decoding process retrieves the transmitted codeword. The unique solution to the key equation gives $\sigma ( z )$, the error locator polynomial, and $\omega ( z )$, the error evaluator polynomial. The zeros of the error evaluator polynomial yield the coordinate positions at which errors occur and the error value at such an error position $\beta$ is given by $\omega ( \beta ) / \sigma ^ { \prime } ( \beta )$, where $\sigma ^ { \prime }$ indicates the formal derivative.

E.R. Berlekamp [a1] gave a computationally efficient iterative algorithm to solve the key equation for the two polynomials. J.L. Massey [a4] showed that this algorithm gives a general solution to the problem of synthesizing the shortest linear feedback shift register that generates the syndrome sequence. At each stage the algorithm incrementally adjusts the length of the shift register and the feedback multiplier taps to generate the syndrome sequence to that point and terminates when the whole sequence is generated. In this formulation, the set of shift register feedback tap values yields the coefficients of the error locator polynomial. The iterative algorithm of Berlekamp and the feedback shift register synthesis interpretation is known as the Berlekamp–Massey algorithm.

The solution to the key equation, and hence the Berlekamp–Massey algorithm, has connections to several other algorithms, most notably the extended Euclidean algorithm [a5], [a3] and continued fractions [a6] (cf. also Continued fraction). The extended Euclidean algorithm iteratively determines the greatest common divisor of two elements in a Euclidean domain, in this case $\mathbf F _ { q } [ z ]$. Specifically, for $a ( z ) , b ( z ) \in \mathbf{F} _ { q } [ z ]$, define $r_{ - 1} ( z ) = a ( z )$ and $r_0 ( z ) = b ( z )$ and define a sequence of quotient and remainder polynomials by

\begin{equation*} r _ { i - 2} ( z ) = q _ { i } ( z ) r _ { i - 1} ( z ) + r _ { i } ( z ) , \quad i = 1,2 ,\dots . \end{equation*}

The degrees of the remainder polynomials are strictly decreasing and the last non-zero remainder polynomial is the greatest common divisor of $a ( z )$, $b ( z )$. The quotient polynomials $q_i( z )$ can be used to define a sequence of subsidiary polynomials $s _ { i } ( z )$ and $t _ { i } ( z )$ with strictly increasing degrees, such that at each stage of the algorithm

\begin{equation*} s _ { i } ( z ) a ( z ) + t _ { i } ( z ) b ( z ) = r _ { i } ( z ), \end{equation*}

so that $s _ { i } ( z ) a ( z ) \equiv r _ { i } ( z ) ( \operatorname { mod } b ( z ) )$ for all $i$. Applied to the case $a ( z ) = S ( z )$ and $b ( z ) = z ^ { 2 t }$, since the $r_i$ have strictly decreasing degrees and the $s_i$ strictly increasing degrees, it can be shown that the algorithm reaches a unique point where $t \geq \operatorname { deg } s _ { i } > \operatorname { deg } r _ { i }$, yielding a solution to the key equation.

Recasting the key equation as

\begin{equation*} S ( z ) \equiv \frac { \omega ( z ) } { \sigma ( z ) } ( \operatorname { mod } z ^ { 2 t } ), \end{equation*}

$\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z ) \leq t$, the problem is to determine the smallest degree $\sigma ( z )$, of degree at most $t$, $\operatorname { deg } \omega ( z ) < \operatorname { deg } \sigma ( z )$ such that the first $2 t$ terms of the expansion of the fraction about the origin yields the sequence of syndromes. Such a partial fraction expansion leads naturally to an equivalent continued fraction interpretation of the Berlekamp–Massey algorithm [a6].

The Berlekamp–Massey algorithm has found numerous applications outside of the coding context. These include fast algorithms in numerical analysis such as Lanczos recursion and Levinson–Shur algorithms for Toeplitz matrices, as well as problems of minimal realizations in system theory [a2].

References

[a1] E.R. Berlekamp, "Algebraic coding theory" , McGraw-Hill (1968)
[a2] T. Kailath, "Encounters with the Berlekamp–Massey algorithm" R.E. Blahut (ed.) D.J. Costello Jr. (ed.) U. Maureer (ed.) T. Mittelholzer (ed.) , Communications and Cryptography, Two Sides of One Tapestry , Kluwer Acad. Publ. (1994)
[a3] R.J. McEliece, "The theory of information and coding" , Encycl. Math. Appl. , 3 , Addison-Wesley (1977)
[a4] J.L. Massey, "Shift register synthesis and BCH decoding" IEEE Trans. Inform. Th. , IT-19 (1969) pp. 122–127
[a5] Y. Sugiyama, S. Kasahara, S. Hirasawa, T. Namekawa, "A method for solving key equation for decoding Goppa codes" Inform. Control , 27 (1975) pp. 87–99
[a6] L.R. Welch, R.A. Scholtz, "Continued fractions and Berlekamp's algorithm" IEEE Trans. Inform. Th. , IT-25 (1979) pp. 19–27
How to Cite This Entry:
Berlekamp-Massey algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Berlekamp-Massey_algorithm&oldid=11537
This article was adapted from an original article by Ian F. Blake (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article