Field Guide · algorithm

Also known as: Forney algorithm, Forney's formula

The Forney algorithm computes the magnitude of each error once its position is known, finishing the correction of a Reed–Solomon or BCH codeword.1 Where Chien search answers which symbols are wrong, Forney answers by how much — for each error position it evaluates a simple rational formula built from the error-locator and error-evaluator polynomials, giving the exact value to subtract from the received symbol.2

Ω(x) evaluator Λ′(x) locator deriv. Forney: eᵢ = −Ω(X⁻¹)/Λ′(X⁻¹) error value eᵢ evaluated once per error position Xᵢ found by Chien search
Forney's rational formula turns each known error position into an exact error value, using the evaluator polynomial over the locator's derivative.

How it works

Algebraic decoding factors the problem into “where” and “how much.” The Berlekamp–Massey algorithm produces the error-locator polynomial Λ(x); Chien search finds its roots to give the error positions Xᵢ. That leaves the error values eᵢ still unknown. In principle you could set up and solve a system of linear equations from the syndromes, but Forney found a closed-form shortcut.

The key is a second polynomial, the error-evaluator (or “omega”) polynomial Ω(x), obtained from the syndrome polynomial and Λ(x) via the key equation Ω(x) = S(x)·Λ(x) mod x^(2t). Forney’s formula then gives each error magnitude directly:

  • Take the formal derivative Λ′(x) of the locator polynomial.
  • For each error position Xᵢ, evaluate eᵢ = −Ω(Xᵢ⁻¹) / Λ′(Xᵢ⁻¹) (with a scaling factor that depends on the code’s exact definition).
  • Subtract eᵢ from the received symbol at that position to correct it.

Because everything is finite-field arithmetic, the division is a multiply by a precomputed inverse and the result is exact — no rounding, no iteration. The cost is a couple of polynomial evaluations per error, similar in structure to Chien search, so the two share hardware in real decoders.

In practice

Forney is the final stage of the classic syndrome → Berlekamp–Massey → Chien → Forney pipeline. It is what distinguishes a symbol code like Reed–Solomon from a purely binary BCH code: in a binary BCH code every error value is simply 1, so locating the error is enough and Forney reduces to a no-op. In Reed–Solomon over a byte-sized field the value can be any nonzero symbol, so Forney’s magnitude computation is essential to actually repair the data. The same three-stage flow underpins the erasure-and-error decoding used with interleaving to survive burst damage: known erasure positions are folded into Λ(x), and Forney still supplies the values.

Relevance to SDR

Reed–Solomon protection appears in digital radio signalling — parts of P25 header and control data, and the RS/BCH-guarded words in other land-mobile formats — and in nearly all broadcast and storage systems a receiver might touch. Whenever such a symbol-oriented code is corrected, some equivalent of Forney’s formula computes the repair values; it is an internal step of the forward error correction stage, not something a user observes. GopherTrunk performs the FEC these formats mandate to validate frames; Forney names the standard method for the “how much” half of block-code correction, whether run as a full solver or, for the very short codes GT meets, a table-driven equivalent.

Sources

  1. Forney algorithm — Wikipedia, for the error-value formula and the error-evaluator polynomial. ↩

  2. On decoding BCH codes — G. D. Forney, IEEE Trans. Information Theory (1965), the original derivation. ↩

See also