Module p25::coding::bmcf

Decodes Reed Solomon and BCH codes using the Berlekamp-Massey, Chien Search, and Forney algorithms.

Decoding Procedure

The standard [1]-[11] procedure for Reed Solomon/BCH error correction has the following steps:

1. Generate the syndrome polynomial s(x) = s₁ + s₂x + ··· + s_2tx^2t-1, where s_i = r(αⁱ) using the received word polynomial r(x).
2. Use s(x) to build the error locator polynomial Λ(x) = (1 + a₁x) ··· (1 + a_ex), where deg(Λ(x)) = e ≤ t is the number of detected errors.
3. Find the roots a₁^-1, ..., a_E^-1 of Λ(x), such that Λ(a_i^-1) = 0. Then for each, if a_i^-1 = α^k_i, the error location within the received word is taken as m_i in α^m_i ≡ α^-k_i (modulo the field).
4. Verify that e = E.
5. Construct the error evaluator polynomial Ω(x) = Λ(x)s(x) mod x^2t and compute each error pattern b_i = Ω(a_i^-1) / Λ'(a_i^-1).
6. For each (m_i, b_i) pair, correct the symbol at location m_i using the bit pattern b_i.

This module implements steps 2 through 5. The implementation uses several well-known techniques exist to perform these steps relatively efficiently: the Berlekamp-Massey algorithm for step 2, Chien Search for step 3, and the Forney algorithm for step 5.

Berlekamp-Massey Algorithm

The Berlekamp-Massey algorithm has many variants [1], [2], [9], [12], [13] mostly with subtle differences. The key observation from Massey's generalization is to view Λ(x) as the "connection polynomial" of a linear feedback shift register (LFSR) that generates the sequence of syndromes s₁, ..., s_2t. The algorithm then synthesizes Λ(x) when constructing the corresponding unique shortest LFSR that generates those syndromes.

Chien Search

With Λ(x) = Λ₀ + Λ₁x + Λ₂x² + ··· + Λ_ex^e (where Λ₀ = 1), let P_i = [p₀, ..., p_e], 0 ≤ i < n, which is indexed as P_i[k], 0 ≤ k ≤ e.

Starting with the base case i = 0, let P₀[k] = Λ_k so that Λ(α⁰) = Λ(1) = Λ₀ + Λ₁ + ··· + Λ_e = sum(P₀).

Then for i > 0, let P_i[k] = P_i-1[k]⋅α^k so that Λ(αⁱ) = sum(P_i).

Forney Algorithm

The Forney algorithm reduces the problem of computing error patterns to evaluating Ω(x) / Λ'(x), where Ω(x) = s(x)Λ(x) mod x^2t. This requires no polynomial long division, just a one-time polynomial multiplication and derivative evaluation to create Ω(x), then two polynomial evaluations and one codeword division for each error.

Structs

ErrorDescriptions	Computes error locations and patterns from the roots of the error locator polynomial Λ(x).
ErrorLocator	Finds the error location polynomial Λ(x) from the syndrome polynomial s(x).
Errors	Decodes and iterates over codeword errors.
PolynomialRoots	Finds the roots of the given error locator polynomial Λ(x).