Reed-Solomon Error Correction Codes

There are two views of Reed-Solomon codes, Original view and BCH view, make sure which view you are reading about.

It seems to me, BCH view is most common used (QR codes, CD/DVD, FEC in communications like DVB or 100GbE), and can do both erasure and error corrections. Original view is mainly used for erasure codes in (distributed) storage systems.

	Original view	BCH view
Message $\boldsymbol m = [m_0, m_1, \ldots, m_{k-1}]$	As coefficients of polynomial $p(x) = m_0 + m_1x + m_2x^2 + \cdots + m_{k-1}x^{k-1}$
Codeword $\boldsymbol c = [c_0, c_1, \ldots, c_{n-1}]$	As values of $p(x)$ at $a_0, a_1, \ldots, a_{n-1}$	As coefficients of polynomial $s(x)$
Characteristic	Vandermonde matrix $V$	Generator polynomial $g(x)$
$(n, k)$	Usuall small, for erasure codes in storage systems	$n=2^m-1$, usually $n=255$
Basic encoding	$V_{n \times k} \cdot \boldsymbol m$	$s(x) = p(x) \cdot g(x)$
Systematic encoding	$$\begin{bmatrix}I_k\\G\end{bmatrix} \cdot \boldsymbol m$$	$p(x) \cdot x^{n-k} \mod g(x)$
Implementation	More memory for $V$ or $G$	linear feedback shift register (LFSR)
Erasure decoding	Inverse of matrix $O(n^3)$	Forney algorithm $O(n^2)$
Error correction decoding	Berlekamp-Welch (1983), Shuhong Gao (2002)	PGZ (1960), Berlekamp-Massey (1967)

$$V_{n\times k} = \begin{pmatrix} 1 & a_0 & a_0^2 & \cdots & a_0^{k-1} \\[1mm] 1 & a_1 & a_1^2 & \cdots & a_1^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_{n-1} & a_{n-1}^2 & \cdots & a_{n-1}^{k-1} \end{pmatrix}, \quad g(x) = (x-\alpha^i)(x-\alpha^{i+1})\cdots (x-\alpha^{i+n-k-1})$$

Reed-Solomon error correction in Python

https://github.com/chenshuo/notes/blob/master/notebooks/ReedSolomonErasureCodes.ipynb

Reference

• https://en.wikipedia.org/wiki/Reed-Solomon_error_correction

Tutorials

Starts here

• "Practical Reed-Solomon for Programmers" https://berthub.eu/articles/posts/reed-solomon-for-programmers/ (BCH view)
• https://www.akalin.com/intro-erasure-codes (Original view)

Polynomial visualize

• "Reed-Solomon Error Correcting Codes from the Bottom Up" https://tomverbeure.github.io/2022/08/07/Reed-Solomon.html
• "Introduction to Reed-Solomon" https://innovation.vivint.com/introduction-to-reed-solomon-bc264d0794f8
  • https://github.com/vivint/infectious

Finite Field

• "Finite Field Arithmetic and Reed-Solomon Coding" https://research.swtch.com/field (BCH view)
  • https://github.com/rsc/qr/blob/master/gf256/gf256.go
• "The mathematics of RAID-6" https://www.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf (Finite Field Arithmetic)

Error correction decoding in BCH view

• Reed–Solomon codes for coders (BCH view with Python code)
• https://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031.pdf (BCH view)
• https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder (BCH view, PGZ decoder)

Erasure decoding in original view

• Erasure Codes for Storage Applications https://web.eecs.utk.edu/~jplank/plank/papers/FAST-2005.pdf
• Tutorial: Erasure Coding for Storage Applications https://web.eecs.utk.edu/~jplank/plank/papers/FAST-2013-Tutorial.html
• All About Erasure Codes by James Plank https://web.eecs.utk.edu/~jplank/plank/classes/cs560/560/notes/Erasure/2004-ICL.pdf

Videos

• vcubingx - What are Reed-Solomon Codes?
• Isabel Vogt - Error Correcting Curves - Numberphile
• Mary Wootters - Lecture 4: Reed-Solomon Codes! of Stanford CS250/EE387: Algebraic Error Correcting Codes
  • Her 1-hr long public lecture for wider audience

Course notes

• Stanford CS250/EE387: Algebraic Error Correcting Codes https://web.stanford.edu/class/cs250/
• Berkeley CS 294-226: Advances in Error-Correcting Codes https://people.eecs.berkeley.edu/~venkatg/teaching/ECC-fall22/
• MIT 6.451: Principles Of Digital Communication II https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/resources/mit6_451s05_fulllecnotes/

Open source

Original view (Vandermonde Reed-Solomon)

• James S. Plank: A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems, SPE97 paper and correction 2003.

• Luigi Rizzo: Software FEC in computer communications, RFC 5510

• JavaReedSolomon by Backblaze.
  • Blog post Backblaze Open-sources Reed-Solomon Erasure Coding Source Code and 5-minute video tutorial by Brian Beach
• Python pyfinite package.

BCH view

• Error Correcting Codes (ECC) Page by Robert Morelos-Zaragoza.
• FEC Library by Phil Karn, KA9Q.
  • Adapted into Linux kernel 2.6.10 by Thomas Gleixner.
• Russ Cox blog Finite Field Arithmetic and Reed-Solomon Coding with source code in Go.
• Python galois package.

History and People

• https://en.wikipedia.org/wiki/Irving_S._Reed
• https://en.wikipedia.org/wiki/Gustave_Solomon
• https://en.wikipedia.org/wiki/Elwyn_Berlekamp
• https://en.wikipedia.org/wiki/James_Massey
• https://en.wikipedia.org/wiki/Lloyd_R._Welch
• https://en.wikipedia.org/wiki/Robert_Tienwen_Chien
• https://en.wikipedia.org/wiki/Dave_Forney