Greedy construction method for error correction codes. Builds codebook by adding codewords in lexicographic order that maintain minimum distance constraint. Simple construction yields codes including Hamming and Golay codes. Demonstrates fundamental code construction principles.
| Property | Value |
|---|---|
| Category | Error Correction |
| Sub-category | Constructed Code |
| Security status | š Educational Only |
| Complexity | Intermediate |
| Inventor | Unknown (classical technique) |
| Year | 1960 |
| Origin | Not specified |
| Source | algorithms/ecc/lexicographic-code.js |
Status: š Educational Only
| Issue | Description | Mitigation |
|---|---|---|
| Suboptimal Parameters | Greedy construction does not always yield optimal codes. May have fewer codewords than best-known codes. | ā |
| Construction Complexity | Building codebook requires checking all previous codewords, O(nĀ²) complexity. | ā |
4 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 ā Lexicographic (7,3) zeros
| Field | Value |
|---|---|
n |
7 |
d |
3 |
input |
00000000 |
expected |
00000000000000 |
Vector 2 ā Lexicographic (7,3) pattern 1
| Field | Value |
|---|---|
n |
7 |
d |
3 |
input |
00000001 |
expected |
00000000010101 |
Vector 3 ā Lexicographic (7,3) pattern 2
| Field | Value |
|---|---|
n |
7 |
d |
3 |
input |
00000100 |
expected |
00000101000001 |
Vector 4 ā Lexicographic (7,3) pattern 3
| Field | Value |
|---|---|
n |
7 |
d |
3 |
input |
00010000 |
expected |
00010001000100 |