Berlekamp-Massey algorithm Created 2026-09-24 Updated 2026-11-05
The Berlekamp-Massey algorithm finds a shortest linear recurrence consistent with a finite sequence over a field. It returns a register length and a connection polynomial such that
Missing coefficients are zero; for a finite prefix the polynomial degree of can be less than . The output describes the shortest recurrence for the observed prefix, rather than proving how an unknown infinite sequence continues.
Initialize , , , and . At index , compute the discrepancy . If , increase by one. Otherwise save and replace by . If , also set , , , and ; if , only increase . The saved discrepancy cancels the current failure of the linear recurrence, while the update of accounts for the extra memory it requires.[ref]
For the binary prefix , the result is and , corresponding to over the field with two elements. This is useful both in analyzing a linear-feedback shift register and in constructing a BCH code error-locator polynomial.
James L. Massey 2026-11-05
James L. Massey showed that Berlekamp's iterative BCH-decoding algorithm solves a general register-synthesis problem: find a shortest linear-feedback shift register generating a prescribed finite sequence. His 1969 paper derives the algorithm through the lengths and discrepancies of successive candidate recurrences, connecting the Berlekamp-Massey algorithm to error correction.[ref]
A sequence that satisfies can be generated from stored symbols and feedback coefficients over a field. A newly observed symbol may contradict the current recurrence; the algorithm then updates the candidate using a prior discrepancy. Minimal synthesis is therefore more than finding some recurrence that happens to fit the observations.
Suppose a connection polynomial of degree at most , with recurrence span gives zero recurrence discrepancies through index but a nonzero discrepancy at . If a polynomial of span successfully explains the prefix through and , evaluate the coefficient at in the convolution . Applying first makes it zero. Applying first leaves its nonzero discrepancy at , because the earlier discrepancies vanish and has constant coefficient one. This contradiction gives the displayed lower bound. It is the minimality step used by the Berlekamp-Massey algorithm; the algorithm cancels the new discrepancy with a shifted earlier failed polynomial.
For distinct evaluation points and , the Reed-Solomon code is
This is a linear code of dimension : evaluation is linear, and a nonzero polynomial of degree less than cannot vanish at all distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set and , where generates the multiplicative group of a finite field . Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.
For this ordered full-length construction, shifting the evaluation vector to the right gives . This is the evaluation vector of , whose degree is still less than , so it is a cyclic code. Its generator polynomial follows from the finite geometric series
Here the scalar is nonzero in . Write and . For ,
since . Thus every word is divisible by . This monic divisor of generates a cyclic code of dimension , equal to the evaluation code by inclusion and dimension. Hence
It is useful to allow a starting exponent for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon code
All exponents are understood modulo . The same geometric-sum calculation shows that
Indeed evaluating its word polynomial at , , gives sums with exponents between one and . This is a generalized Reed-Solomon code, with nonzero coordinate multipliers ; is the unweighted evaluation code. Directly, a right shift corresponds to replacing by , so these offset codes are also cyclic codes.
A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with . To see the bound, deleting any coordinates is injective on a code of minimum Hamming distance , since two words with the same puncture would differ in at most positions. Therefore and . For a nonzero Reed-Solomon evaluation word, the polynomial has at most distinct polynomial roots, so at least coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any evaluation points and take their linear factors as ; it vanishes exactly at those points and has weight . Thus
The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first . A vector of has coordinates , ; a vector of has coordinates , . Their standard dot product is
Every monomial in has exponent at least one and at most , and every such power sum vanishes. Thus . Both sides have dimension , giving
In particular has generator . This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor . The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form , so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension on the same points. This convention distinction is essential. The case is the full word space and its dual is the zero code, obtained by taking .
For code encoding, use the finite-field discrete Fourier transform and its inverse:
For a message , put for , and set all other transform coordinates to zero. The inverse discrete Fourier transform returns
The zero transform coordinates are precisely the root checks defining . This gives non-systematic encoding by evaluation. For systematic polynomial encoding of a cyclic code with a message polynomial of degree less than , put and calculate the remainder of upon division by . Then is divisible by , and the last coefficients are the message coefficients. Both methods use the same generator polynomial and the same ordered powers of .
For bounded-distance decoding, let , put , and assume at most symbol errors. The following description uses the Reed-Solomon key equation and fixes the transform and locator conventions explicitly.
  • Set , all other error coordinates to zero, and output . Verify that all root checks vanish and that the correction has weight at most . Recover the message from the unconstrained transform coordinates by , or from the last coefficients if systematic encoding was used.
The denominator in the Forney algorithm is nonzero for distinct locations. The minimum-distance error-detection and correction guarantee gives unique recovery because . If the required locator or a valid correction cannot be found, declare decoding failure. Beyond errors, a received word may lie near a different codeword, so successful root checks alone do not certify recovery of the originally transmitted message. The guaranteed correction radius is symbol errors.
A linear-feedback shift register of length has binary state and update
Its output obeys over . Since the state space is finite, its trajectory consists of a transient of length followed by a cycle of length , and the output satisfies for .
If the trajectory never reaches zero, all its distinct transient and cyclic states are nonzero; hence . If it reaches zero, let be its first zero-state time. The vectors are linearly independent: in a dependence, apply where is the smallest index with a nonzero coefficient; every later term vanishes and the remaining term is . Therefore . The zero cycle has , and for . This proves the requested bound for all , and for every invertible register.
The unrestricted printed assertion has one exception: at , the zero-feedback register with initial state one outputs . It requires , so . The universally valid finite-state bound is . A register with feedback from its oldest bit is invertible, in which case a nonzero state never reaches zero and the sharper bound holds already with .
To recover an unknown register from a known plaintext/ciphertext keystream, the Berlekamp-Massey algorithm finds a shortest linear recurrence consistent with the observed bits. Use a connection polynomial , so the recurrence discrepancy at index is . Initialize . Process the bits in order. If , increment . If , save and replace
If , also replace by , set ; otherwise retain and increment . Arithmetic is binary, so every nonzero discrepancy equals one. The stored polynomial last failed at an earlier index with discrepancy ; its shifted contribution cancels the new failure without changing previous successful discrepancies.
Here is the minimum recurrence length after a new discrepancy argument behind the update, not just its name. Suppose a span- recurrence succeeds through index but fails at . If another polynomial of span succeeded through and , compute the convolution at in two ways. Applying first gives zero, since all indices used by lie at least at . Applying first gives its nonzero discrepancy at , since its earlier discrepancies used by vanish and . This contradiction proves . The shifted-polynomial update attains the larger of the existing minimum length and this new lower bound; induction therefore gives the shortest recurrence for every prefix. Once at least twice the true linear complexity has been observed, this recurrence determines the whole stream: the difference from a true degree- recurrent stream satisfies a recurrence of degree at most , and a prefix of that many zeros forces every later value to be zero. Without any bound on complexity, a finite observed prefix cannot exclude a longer register that diverges later; the breaking claim uses the finite-register hypothesis and adequate known data.
Finally each of the three input streams is eventually periodic. Let be the maximum of their transient lengths and a common multiple of their periods. Their joint triple, and hence the bit chosen by the specified rule, repeats after once . Therefore
This itself is a linear recurrence of length , so it constructs a linear-feedback shift register producing the selected stream from its first bits. No closure theorem is being assumed: eventual periodicity and this explicit recurrence prove the combined stream is also an LFSR stream, even though the combining rule is nonlinear in its three inputs.
A binary linear-feedback shift register of length keeps bits and produces a sequence satisfying a recurrence
After each output it shifts its stored bits and inserts the feedback bit. Its connection polynomial is . This convention reverses the usual characteristic polynomial .
The Berlekamp-Massey algorithm recovers the shortest recurrence compatible with observed bits. Maintain the current , length , an earlier polynomial that last caused a length increase, and the offset since that increase. Initially . At position calculate the discrepancy . If , advance . If , save and replace by . If also , replace by , by and by one; otherwise increase . Over a general field the correction is , where is the saved nonzero discrepancy. The correction cancels the failed equation while retaining the previous successful ones; when it forces a length increase the smallest possible new length is .
Here, indexing the first bit by zero, the nonzero discrepancies occur at positions . The corresponding updates are
Every subsequent supplied discrepancy is zero. Thus
Equivalently the characteristic feedback polynomial is . No length-three recurrence works: positions force , but position six then has nonzero discrepancy. The recovered length is therefore minimal. Observing at least twice the true linear complexity ordinarily identifies the recurrence, after which a known consecutive block determines all future key bits. This is why a bare register is unsuitable as a cryptographic keystream generator; a finite prefix alone does not exclude a longer generator that later diverges.
A binary linear-feedback shift register stores bits, shifts them at each clock step, and inserts a fixed linear combination over of the stored bits. Its output obeys a recurrence . Write its connection polynomial as ; the corresponding monic feedback polynomial is .
The Berlekamp-Massey algorithm maintains the shortest recurrence fitting the observed prefix. Initialize , length , displacement , and previous nonzero discrepancy . At symbol , calculate . If , increase . If , save and replace by . If , replace by , by , by , and by ; otherwise only increase . In the binary field subtraction equals addition. The shifted previous discrepancy polynomial cancels the current discrepancy while preserving earlier equations. A failed recurrence of length at position requires a corrected length at least when this exceeds , explaining the length update. Thus the algorithm recovers the shortest compatible register; a known bound and at least output symbols suffice to identify its minimal recurrence.
For the printed twelve-bit prefix, the nonzero discrepancies occur at positions (indexing from zero). The successive updated pairs are
All remaining discrepancies vanish. Therefore
The first four observed bits are the fill. Length four is necessary: a length-three recurrence would need to hold already at and no such recurrence fits the prefix. Indeed the equations at force , , , a contradiction. Finite observations cannot rule out longer nonminimal registers.
A binary linear-feedback shift register of length stores bits. At each clock it outputs one bit, shifts the state, and inserts a fixed linear combination over of the stored bits. Equivalently, its output obeys a recurrence
The Berlekamp-Massey algorithm processes the observed symbols from left to right. It maintains the shortest current connection polynomial , its degree , and a saved polynomial from the most recent degree increase. At step it computes the discrepancy
If , the current recurrence already predicts the new symbol. If , a shifted multiple of the saved polynomial is added to to cancel the discrepancy; when , the algorithm also replaces by and saves the old polynomial.
For the observed binary sequence, the nonzero-discrepancy updates are
All discrepancies through then vanish. Thus the shortest recurrence is
or, equivalently, . The connection polynomial is , and with the reciprocal convention the feedback polynomial is
A general binary feedback shift register of length has state
and a feedback function . One update outputs the oldest bit, shifts the state, and inserts
The initial fill is . It is a linear-feedback shift register when
for fixed .
The Berlekamp-Massey algorithm reads an intercepted sequence from left to right while maintaining the shortest connection polynomial that reproduces the prefix. At each new symbol it computes the discrepancy between the observed bit and that predicted by the current recurrence. A zero discrepancy leaves the polynomial unchanged; a nonzero discrepancy adds a suitably shifted copy of the connection polynomial saved at the previous increase in linear complexity. After at least twice the unknown register length, it recovers the shortest recurrence, after which the entire keystream can be predicted.
Applying those discrepancy updates to
returns the connection polynomial
Equivalently, the sequence obeys
Indeed this predicts successively . No recurrence of length one or two fits the prefix, so its linear complexity is three.
Reed-Solomon key equation Created 2026-10-14 Updated 2026-11-05
With syndromes and distinct error-location values , form and the error locator polynomial . There is an error evaluator polynomial of degree less than the number of errors satisfying the key equation. When the number of errors is at most , the Berlekamp-Massey algorithm or extended Euclidean algorithm recovers these polynomials, normalized by .
By James L. Massey. Published in IEEE Transactions on Information Theory 15(1), pages 122–127.
Sections II–III develop minimal-register synthesis and the Berlekamp-Massey algorithm; Sections IV–V apply it to BCH code decoding.