Reed-Solomon codes with folding transformation achieving list-decoding capacity. Bundles consecutive symbols into super-symbols for improved error correction. Enables list decoding beyond the unique decoding bound up to (1-R-Ξ΅) fraction of errors. First explicit codes achieving list-decoding capacity with efficient algorithms. Educational implementation demonstrates folding concept and systematic encoding over GF(256).
| Property | Value |
|---|---|
| Category | Error Correction |
| Sub-category | Algebraic Code |
| Security status | π§ͺ Experimental |
| Complexity | Expert |
| Inventor | Venkatesan Guruswami, Atri Rudra |
| Year | 2006 |
| Origin | πΊπΈ United States |
| Source | algorithms/ecc/folded-reed-solomon.js |
Status: π§ͺ Experimental
| Issue | Description | Mitigation |
|---|---|---|
| List Decoding Complexity | List decoding is computationally more complex than unique decoding, requiring polynomial interpolation and root-finding. | β |
| Field Size Requirements | Requires large field sizes for good parameters. Field size must be at least n for [n,k] base RS code. | β |
| Folding Overhead | Folding reduces the code rate by factor of s (folding parameter), trading rate for list-decodability. | β |
5 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 β Folded RS [8,4] zero data round-trip
| Field | Value |
|---|---|
input |
0000000000000000 |
expected |
(empty) |
Vector 2 β Folded RS [8,4] sequential data round-trip
| Field | Value |
|---|---|
input |
0102030405060708 |
expected |
(empty) |
Vector 3 β Folded RS [8,4] max value data round-trip
| Field | Value |
|---|---|
input |
fffefdfc80402010 |
expected |
(empty) |
Vector 4 β Folded RS [8,4] repeated pattern round-trip
| Field | Value |
|---|---|
input |
2a2a2a2a63636363 |
expected |
(empty) |
Vector 5 β Folded RS [8,4] alternating pattern round-trip
| Field | Value |
|---|---|
input |
01ff02fe03fd04fc |
expected |
(empty) |