[Jump to code hierarchy]

Linearized RS code[1–3]

Description

A code obtained by linearizing a skew RS code, i.e., by translating evaluations of skew polynomials into operator evaluations over blocks.

The general definition over arbitrary division rings was introduced in [3]. Earlier finite-field subfamilies include skew-polynomial constructions and the pasting MDS construction [1,2].

Protection

Linearized RS codes satisfy \(d_{\text{SR}}=n-k+1\), so they are MSRD and attain the sum-rank Singleton bound [3; Prop. 34, Thm. 4].

Decoding

Berlekamp-Welch-type decoder [2] and its sum-rank version [4].

Realizations

Network coding [4].Code-based cryptography [5,6].

Cousins

  • Reed-Solomon (RS) code— Choosing \(\sigma=\operatorname{Id}\) and \(\delta=0\) makes linearized RS codes coincide with conventional RS codes, and the sum-rank metric reduces to the Hamming metric [3; Ex. 36].
  • Gabidulin code— Choosing one conjugacy class with \(\sigma\neq\operatorname{Id}\) and \(\delta=0\) recovers Gabidulin codes, and the sum-rank metric reduces to the rank metric [3; Ex. 37]. Over \(\mathbb{F}_{q^m}\) viewed over \(\mathbb{F}_q\), linearized RS codes can have length up to \((q-1)m\), whereas Gabidulin codes over the same extension have maximum length \(m\) [3; Sec. 4.2].
  • Locally recoverable code (LRC)— Linearized RS codes can be used to construct locally recoverable codes [7].

Member of code lists

Primary Hierarchy

Classical Domain
Matrix Kingdom
Matrix-based codeECC
Sum-rank-metric codeDistributed-storage ECC
Maximum-sum-rank distance (MSRD) code
Parents
Maximum-sum-rank distance (MSRD) code
Linearized RS code

References

[1]
D. Boucher and F. Ulmer, “Linear codes using skew polynomials with automorphisms and derivations”, Designs, Codes and Cryptography 70, 405 (2012) DOI
[2]
S. Liu, F. Manganiello, and F. R. Kschischang, “Construction and decoding of generalized skew-evaluation codes”, 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT) 9 (2015) DOI
[3]
U. Martínez-Peñas, “Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring”, (2018) arXiv:1710.03109
[4]
U. Martinez-Penas and F. R. Kschischang, “Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes”, IEEE Transactions on Information Theory 65, 4785 (2019) arXiv:1805.03789 DOI
[5]
F. Hörmann, H. Bartz and A. L. Horlemann (2022). “Security considerations for Mceliece-like cryptosystems based on linearized Reed-Solomon codes in the sum-rank metric”
[6]
F. Hörmann, H. Bartz, and A.-L. Horlemann, “Distinguishing and Recovering Generalized Linearized Reed–Solomon Codes”, Lecture Notes in Computer Science 1 (2023) arXiv:2304.00627 DOI
[7]
U. Martínez-Peñas and F. R. Kschischang, “Universal and Dynamic Locally Repairable Codes with Maximal Recoverability via Sum-Rank Codes”, (2019) arXiv:1809.11158
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: linearized_reed_solomon

Cite as:
“Linearized RS code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/linearized_reed_solomon
BibTeX:
@incollection{eczoo_linearized_reed_solomon, title={Linearized RS code}, booktitle={The Error Correction Zoo}, year={2026}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/linearized_reed_solomon} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/linearized_reed_solomon

Cite as:

“Linearized RS code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/linearized_reed_solomon

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/sum-rank-metric/linearized_reed_solomon.yml.