5 ms·
That’s an interesting duality between the coefficient and pointwise representation. I wonder whether this connects to the discrete Fourier transform, which can
by aaaaaaaaaaab 8y ago
That’s an interesting duality between the coefficient and pointwise representation. I wonder whether this connects to the discrete Fourier transform, which can be viewed as the evaluation of a polynomial at the complex n-th roots of unity. (and the inverse DFT must be equivalent to Lagrange interpolation I guess - insert some handwaving here)
Also, the BCH encoder multiplies the input sequence with the generator polynomial, which is a convolution of their coefficients. Fourier-type transforms (i.e. number theoretic transform) relate convolution and pointwise multiplication, so I feel there’s an underlying connection here, but I don’t have enough experience with finite fields to connect the dots...
- JadeNB 8y agoYou seem to have answered your own question! For any set of `n + 1` sample values for degree-at-most-`n` polynomials, there's a map from the coefficient representation to the pointwise representation (obvious), and one going the other way (Lagrange interpolation). The DFT is just one instance of this, but a particularly nice one, because the map is essentially involutive, and subject to considerable computational speed-up. What dots do you want to connect? (Anyway you can connect them with a high-degree polynomial curve. :-) )
- aaaaaaaaaaab 8y agoIndeed, the wikipedia article on RS codes [1] mentions this equivalence between the DFT and RS encoding/decoding. They mention that both procedures are basically a multiplication by a Vandermonde matrix, with the Fourier transform having the additional requirement of using the n-th roots of unity. https://en.m.wikipedia.org/wiki/Reed–Solomon_error_correction#Reed_&_Solomon's_original_view:_The_codeword_as_a_sequence_of_values https://en.m.wikipedia.org/wiki/Reed–Solomon_error_correctio...