BCH Encoding/Decoding

[Randy Yates]

I've notieced that in order to decode a page of in-band data, the linux
kernel code first computes the out-of-band ECC bytes on the given
in-band data (calc_ecc). It is also passed the received oob data
recv_ecc.

If (byte-by-byte) the calc_ecc does not match the recv_data, then
the page is decoded.

Why not compute the decoded ECC and compute the locator
vector/polynomial right off? Are these operations much
more expensive than encoding and comparing?

--Randyh

[Steve Pope]

Post by Randy Yates
I've notieced that in order to decode a page of in-band data, the linux
kernel code first computes the out-of-band ECC bytes on the given
in-band data (calc_ecc). It is also passed the received oob data
recv_ecc.
If (byte-by-byte) the calc_ecc does not match the recv_data, then
the page is decoded.
Why not compute the decoded ECC and compute the locator
vector/polynomial right off? Are these operations much
more expensive than encoding and comparing?

TL;dr it comes down to evaulating a lower-degree polynomial,
thus requires less computation.

Assume it is a systematic (n,k) BCH code, it is most efficient to
re-encode the message part of the codeword, and then XOR the
resulting (n-k) check symbols with the (n-k) received check
symbols. Then the syndrome (power sum symmetric function)
can be computed by evaluating using these (n-k) polynomial coefficients
instead of all n coefficients.

The quick exit if there is no mismatch is an optimization.