Code correcting single deletion errors using balanced binary sequences. All codewords have equal number of 0s and 1s (balanced). Can correct one deletion error. Efficient for synchronization in data transmission. Related to Varshamov-Tenengolts codes but simpler construction.
| Property | Value |
|---|---|
| Category | Error Correction |
| Sub-category | Deletion Code |
| Security status | 🎓 Educational Only |
| Complexity | Advanced |
| Inventor | Vladimir Levenshtein |
| Year | 1965 |
| Origin | 🇷🇺 Russia |
| Source | algorithms/ecc/levenshtein-code.js |
Status: 🎓 Educational Only
| Issue | Description | Mitigation |
|---|---|---|
| Single Deletion Only | Can only correct single deletion, not multiple deletions or insertions. | — |
| Balance Requirement | Requires even-length codes with equal 0s and 1s, limiting code rate. | — |
4 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 — Levenshtein [4] balanced 1010
| Field | Value |
|---|---|
input |
01000100 |
expected |
01000100 |
Vector 2 — Levenshtein [4] balanced 0110
| Field | Value |
|---|---|
input |
00010100 |
expected |
00010100 |
Vector 3 — Levenshtein [6] balanced 101010
| Field | Value |
|---|---|
input |
010001000100 |
expected |
010001000100 |
Vector 4 — Levenshtein [6] balanced 110010
| Field | Value |
|---|---|
input |
010100000100 |
expected |
010100000100 |