Description
An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(GF(q)\).
A narrow-sense RS code encodes a message \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(1),\{f_\mu(\alpha),\cdots,f_\mu(\alpha^{n-1})\}\) using a message-dependent polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \tag*{(1)}\end{align} In other words, each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha^{i-1}\), \begin{align} \mu\to\left( f_{\mu}\left(1\right),f_{\mu}\left(\alpha\right),\cdots,f_{\mu}\left(\alpha^{n-1}\right)\right) \,. \tag*{(2)}\end{align}
In an alternative convention (not used here), this code is called an RS code, and the general-root case is a generalized RS code.
Parents
- Reed-Solomon (RS) code — A narrow-sense RS is an RS code with length \(n=q-1\) whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element of \(GF(q)\).
- Bose–Chaudhuri–Hocquenghem (BCH) code — Narrow-sense RS codes are \(q\)-ary BCH codes [4; Remark 15.3.21][5; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [6; pg. 81].
Cousins
- Extended GRS code — A narrow-sense RS code can be extended once, twice, or three times.
- Maximum distance separable (MDS) code — Extended and doubly extended narrow-sense RS codes are MDS [5; Thms. 5.3.2 and 5.3.4], and there is an equivalence between the two for odd prime \(q\) [7].
- Projective geometry code — Columns of parity-check matrices of doubly extended narrow-sense RS codes consist of points of a normal rational curve [8; Def. 14.2.6].
References
- [1]
- Bush, K. A. “Orthogonal Arrays of Index Unity.” The Annals of Mathematical Statistics 23, no. 3 (1952): 426–34.
- [2]
- K. A. Bush, “Orthogonal Arrays of Index Unity”, The Annals of Mathematical Statistics 23, 426 (1952) DOI
- [3]
- I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields”, Journal of the Society for Industrial and Applied Mathematics 8, 300 (1960) DOI
- [4]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [6]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [7]
- S. Ball, “On sets of vectors of a finite vector space in which every subset of basis size is a basis”, Journal of the European Mathematical Society 14, 733 (2012) DOI
- [8]
- L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log
- Victor V. Albert (2024-08-13) — most recent
Cite as:
“Narrow-sense RS code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/narrow_sense_reed_solomon