Linear error-correcting codes based on expander graphs with strong connectivity properties. Used in modern LDPC constructions, polar codes, and theoretical computer science. Parameters depend on graph expansion properties. Achieve capacity on erasure channels with efficient iterative decoding. Foundation for modern capacity-achieving codes.
| Property | Value |
|---|---|
| Category | Error Correction |
| Sub-category | Expander Code |
| Security status | 🎓 Educational Only |
| Complexity | Expert |
| Inventor | Michael Sipser, Daniel Spielman |
| Year | 1996 |
| Origin | 🇺🇸 United States |
| Source | algorithms/ecc/expander-code.js |
Status: 🎓 Educational Only
| Issue | Description | Mitigation |
|---|---|---|
| Graph Construction | Requires explicit expander graph construction or random sampling. Graph quality critically affects error correction performance. | — |
| Iterative Decoding | Message-passing decoding may not converge for all error patterns. Convergence depends on graph expansion properties. | — |
| Error Floor | Like LDPC codes, expander codes may have error floors at low bit error rates due to suboptimal graph structures. | — |
4 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 — Expander code (12,6) all-zero codeword
| Field | Value |
|---|---|
input |
000000000000 |
expected |
000000000000000000000000 |
Vector 2 — Expander code (12,6) single bit position 0
| Field | Value |
|---|---|
input |
010000000000 |
expected |
010000010100000100010000 |
Vector 3 — Expander code (12,6) single bit position 1
| Field | Value |
|---|---|
input |
000100000000 |
expected |
000100010001010000000100 |
Vector 4 — Expander code (12,6) two bits pattern
| Field | Value |
|---|---|
input |
010100000000 |
expected |
010100000101010100010100 |