1
$\begingroup$

I am having trouble understanding the spectral characterization of Reed-Solomon codes. My script states the following:

An evaluation codes is defined as:

$$C = \{(c_0, \ldots, c_n) : c_l = a(\beta_l) \text{ for some } a(x) \in F[x] \text{ with deg } a(x) < k \text{ and F = some field}\}$$

(($\beta_0, \ldots, \beta_{n-1}) \in F^n \text{ is fixed}$). It is easy to see that this set constitutes a linear code which can thus be attributed a minimum Hamming distance (= minimum Hamming weight) as follows:

If for $i \neq j: \beta_i \neq \beta_j$ (i.e. all betas are different) the minimum Hamming weight may be determined by noting that for a polynomial of degree k-1 there may be at most k-1 zeros. Thus, the Hamming weight of $(a(\beta_0), \ldots, a(\beta_{n-1}))$ is at least n-(k-1). By the Singleton bound, however, the Hamming weight is upper-bounded by n-(k-1), thus: $d_{min} = n - k + 1$.

Reed-Solomon codes correspond to the above definition with $\beta_l = \alpha^l$ where $\alpha$ is primitive n-th root in F. One can thus state that we are dealing with a DFT (ignoring scale factors) and write:

$$C = \{(b_0, \ldots, b_{n-1}) \in F^n : B_l = 0 \text{ for } k \leq l < n\}$$

($B$ is the DFT of $b$.)

My question concerns the following part:

It is subsequently stated that one may chose to write

$$C = \{(b_0, \ldots, b_{n-1}) \in F^n : B_l = 0 \text{ for } l_0 \leq l < l_0 + n - k\} \text{ with } 0 \leq l_0 \leq k$$

Supposedly (by the script) it is obvious that this definition doesn't change the minimum hamming distance (i.e. still $d_{min} = n - k + 1$) but I don't see why this follows for the argument stated in the initial part is no longer applicable. Any help on clarifying why Hamming weight is still given by $d_{min} = n - k + 1$ is greatly appreciated!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.