0
$\begingroup$

I am preparing a presentation about the Reed Solomon code for a course I follow at uni. However, I have a question:

$\textbf{Why should the Reed Solomon code be narrow sense?}$

What I understand is: consider a BCH code with design parameters $b$ and design distance $d_{\text{BCH}}$ of length $n$ over a field $\mathbb{F}_q$ of cardinality $q$, with $q = p^k$ for some prime $p$. In order to find a generator polynomial of the BCH code, we need to factorize $x^n -1$ over this field $\mathbb{F}_q$. Let $\beta$ be a primitive $n$th root of unity, then I will denote the minimal polynomial of $\beta^i$, with $i \in \{0, 1, \ldots, n-1\}$ by $m^{(i)}(x)$. As a result, the generator polynomial of the given BCH code would be $$\text{lcm}(m^{(b)}(x), \ldots, m^{(b + d_{\text{BCH}} - 2)}(x)).$$ (I learned this in a course where we saw the BCH code).

What I understand from the text I read (being 'Coding Theory: a first course' by Henk C.A. van Tilborg) is that the Reed Solomon code is a BCH code where $b = 1$ (indicated as 'narrow sense') and $n = q -1$, excluding binary codes. Now I know that $x^{q-1} -1$ factors into linear factors over $\mathbb{F}_q$, showing that the generator polynomial has degree $d_{\text{BCH}} - 1$. From this and the fact that cyclic codes satisfy $$k \leq n - d +1$$ where $k$ is the dimension of the cyclic code (so the cardinality of the code is $q^k$), $d$ is the minimal distance of the code, we find that $$d_{\text{BCH}} = d.$$

$\textbf{ACTUAL QUESTION}$: However, all of this does not require that the code is narrow sense... Is there anyone who knows why this should hold? Or is it just some convention?

$\textbf{REMARK}$: The course notes I used (Coding theory, a first course) as additional lecture about Reed Solomon, does not use $b$, but the 'defining set of a cyclic code $I$'. This is the union of the cyclotomic cosets of corresponding to the minimal polynomials used in the generator polynomial of the BCH code. However, I figured out that these two should correspond (the $b$ was introduced in the course I followed).

$\endgroup$
1
$\begingroup$

It is not necessary for a Reed-Solomon code to be a narrow-sense BCH code. Indeed, the $[255,223]$ "NASA standard" cyclic Reed-Solomon code over $\mathbb F_{2^8}$ that was widely used many years ago (and still survives today in various other standards) is not a narrow-sense BCH code. One reason for that particular choice of $b$ (and the choice of minimal polynomial of degree $8$ whose root was $\beta$) was that it led to the fewest number of transistors in the decoder implementation in the hardware technology of the 1970s.

However, the choice $b=1$ (which gives a narrow-sense BCH code) is convenient for the purposes of exposition and in connecting together different descriptions of Reed-Solomon codes. See, for example, this answer of mine which shows that a code obtained via the original definition of Reed-Solomon codes is in fact a narrow-sense BCH code.

$\endgroup$
5
  • $\begingroup$ This explains a lot! I really appreciate your answer and I will accept as soon as possible. For now, +1 sir! However, could you explain what the $[255, 223]$ stands for? I know that 225 is because of $q -1$, so its the length of the code, but what is the 223? $\endgroup$ – Student Mar 6 '17 at 16:43
  • $\begingroup$ @Student An $[n,k]$ code over $\mathbb F_q$ is a $k$-dimensional subspace of the $n$-dimensional vector space $\mathbb F_q^n$. This is standard notation and I am surprised that you have not encountered it before. $\endgroup$ – Dilip Sarwate Mar 6 '17 at 17:03
  • $\begingroup$ This was not my smartest question, I have encountered it (of course). Thanks for the clarification (although this was one I really should have known). $\endgroup$ – Student Mar 6 '17 at 17:05
  • $\begingroup$ The "original definition" (original view) of Reed Solomon code was not a BCH code, and normally not cyclic. Instead, the message to be encoded is interpreted to be a set of coefficients of a polynomial, or the message to be encoded is interpreted to be a set of output values of a polynomial (determined by Lagrange) for a given set of input values (these input values would be known to both encoder and decoder). At this time (1960), decoders weren't practical except for the simplest of cases. $\endgroup$ – rcgldr Aug 30 '19 at 1:40
  • $\begingroup$ Continuing, by 1963 or sooner, BCH codes were expanded to handling symbols instead of single bits, and since BCH codes had practical decoders going back to 1960, Reed Solomon was changed to be a class of BCH code. It wasn't until decades later that practical decoders for the original view were determined, and they are still relatively slow, as they operate on the entire message as opposed to BCH decoders which operate on syndromes. $\endgroup$ – rcgldr Aug 30 '19 at 1:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.