Field Guide · algorithm

Also known as: Berlekamp–Massey, BM algorithm, Berlekamp-Massey

The Berlekamp–Massey algorithm finds the shortest linear-feedback shift register (equivalently, the lowest-degree polynomial) that produces a given sequence of field elements.1 In algebraic decoding it is the step that turns a block of computed syndromes into the error-locator polynomial, the object whose roots reveal where a Reed–Solomon or BCH codeword was damaged.2 It is fast, exact, and works entirely in the code’s finite field.

syndromes Sₖ Berlekamp–Massey grow shortest LFSR Λ(x) error locator each step: measure discrepancy, update Λ(x), extend register length only when forced
Berlekamp–Massey iteratively builds the shortest recurrence that fits the syndromes, yielding the error-locator polynomial Λ(x).

How it works

A received word is checked against the code’s parity structure to produce a short list of syndromes — numbers that are all zero when there are no errors and otherwise encode a system of nonlinear equations in the unknown error positions and values. The classical way to solve that system is to first find the error-locator polynomial Λ(x), whose roots point at the corrupted symbols.

Berlekamp–Massey builds Λ(x) incrementally. It processes the syndromes one at a time and maintains a current candidate LFSR:

  • At each step it computes a discrepancy: how far the current register’s prediction of the next syndrome is from the actual value.
  • If the discrepancy is zero, the current polynomial still works — nothing changes.
  • If not, it corrects Λ(x) using a saved copy of the last polynomial that forced a length increase, scaled by the discrepancy. Register length grows only when unavoidable, which is exactly what makes the result the shortest generator.

After all 2t syndromes are consumed (for a code that corrects t errors), the degree of Λ(x) equals the number of errors that actually occurred, provided that number is within the code’s capability. The whole procedure is O(t²) in the field — dramatically cheaper than solving the syndrome equations by brute force, and numerically exact because finite-field arithmetic has no rounding.

In practice

Berlekamp–Massey is one stage of a three-stage algebraic RS/BCH decoder, and it is almost always followed by two companions:

  • Chien search evaluates Λ(x) at every field element to find its roots, giving the error positions.
  • The Forney algorithm uses Λ(x) together with an error-evaluator polynomial to compute the error values at those positions.

An equivalent alternative to BM is the extended Euclidean algorithm applied to the syndrome polynomial; the two produce the same locator and are chosen mostly by implementation convenience. Massey’s key insight was that “synthesise the shortest LFSR for a sequence” and “decode a BCH code” are the same problem, which is why the algorithm is also a staple of linear-complexity analysis and cryptanalysis of stream ciphers.

Relevance to SDR

Reed–Solomon and BCH codes appear throughout the digital land-mobile radio world — P25 protects control-channel and header fields with short RS codes, and BCH guards sync and signalling words in several formats — so a hard-decision algebraic decoder for those fields runs some equivalent of Berlekamp–Massey to locate errors before correcting them. The algorithm is a building block of the forward error correction stage rather than something a listener sees directly. GopherTrunk performs the FEC checks that these formats require to validate frames; the BM/Chien/Forney trio is the standard math behind that class of block code, whether implemented as a full solver or as a table-driven correction for the small codes GT encounters.

Sources

  1. Berlekamp–Massey algorithm — Wikipedia, for the shortest-LFSR formulation and its use in RS/BCH decoding. ↩

  2. Shift-register synthesis and BCH decoding — J. L. Massey, IEEE Trans. Information Theory (1969), the paper linking LFSR synthesis to error correction. ↩

See also