Research map / Architectures and efficiency / RNNs and normalization
DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DoDo-Code, a 4-ary single-IDS-correcting code built by greedy codeword search and K-d tree segment correction in a deep Siamese embedding space that approximates Levenshtein distance.
Problem
Designing high-code-rate single-IDS-correcting codes over a 4-ary alphabet for short codeword lengths, where existing combinatorial codes (VT-type, order-optimal) have poor constant redundancy terms and Levenshtein-based decoding is computationally expensive.
Approach
Train a Siamese 1D-CNN embedding so squared Euclidean distance approximates Levenshtein distance (with a truncated, radius-2-focused PNLL loss), then select codewords greedily by the Gaussian PDF score in embedding space and correct segments via K-d tree nearest-neighbor search instead of Levenshtein brute force.
Key results
- For n=11 the DoDo-Code achieves a code rate of 68.9%, reported as exceeding the state-of-the-art combinatorial codes at short lengths.
- Embedding-based greedy search finds 16.8% more codewords than random selection at n=11 (max over 10 runs).
- With k=4 neighbors queried in the K-d tree, zero failed segment corrections out of 10^8 attempts for n=7 to 11; k=1 gives 0.3% to 0.9% failures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use embedding-space PDF selection instead of random codeword selection (ablation) | DoDo-Code greedy codeword search · 4-ary IDS code, n=11 | maximum codebook cardinality: +16.8% | Helped |
| Use revised PNLL loss instead of original PNLL loss (ablation) | DoDo-Code embedding-based greedy search · 4-ary IDS code, n=7 to n=11 | codebook cardinality: 267.5 vs 264.5; 884.8 vs 873.3; 3001.6 vs 2963.5; 10325.4 vs 10199.4; 35973.1 vs 35720.4 | Helped |
| Increase the number of queried neighbors from k=1 to k=4 (ablation) | DoDo-Code segment correction · 4-ary IDS code, n=11, 10^8 attempts | failed corrections: 828,885 -> 0 | Helped |
| Increase queried neighbors from k=1 to k=2 (ablation) | DoDo-Code segment correction · 4-ary IDS code, n=7 to n=11 | failed corrections: 328,142 -> 0; 398,439 -> 4,411; 465,080 -> 2,330; 740,468 -> 7,060; 828,885 -> 10,869 | Helped |
| Increase queried neighbors from k=2 to k=3 (ablation) | DoDo-Code segment correction · 4-ary IDS code, n=7 to n=11 | failed corrections: 0 -> 0; 4,411 -> 0; 2,330 -> 754; 7,060 -> 0; 10,869 -> 121 | Helped |
| Increase queried neighbors from k=3 to k=4 (ablation) | DoDo-Code segment correction · 4-ary IDS code, n=7 to n=11 | failed corrections: 0 -> 0; 0 -> 0; 754 -> 0; 0 -> 0; 121 -> 0 | Helped |
| Increase queried neighbors from k=4 to k=5 (ablation) | DoDo-Code segment correction · 4-ary IDS code, n=7 to n=11 | failed corrections: 0 -> 0; 0 -> 0; 0 -> 0; 0 -> 0; 0 -> 0 | No clear effect |
| Use DoDo-Code instead of state-of-the-art combinatorial codes | 4-ary IDS code · Short code lengths | code rate | Helped |
Surprising findings
- The random-search baseline and the VT code show that VT codewords have biased embedding distributions and leave isolated sequences uncovered, suggesting modifications to VT could improve rate.
- The achieved redundancy curve overlaps log n + log log n + log 3, suggesting it may approach the minimal redundancy for single-IDS correction.
Limitations
- No explicit mathematical rules describing the codewords are provided.
- Greedy codeword search can become computationally expensive for large code lengths.
- Embedding approximation error requires querying multiple neighbors and double-checking with Levenshtein distance.
Experimental setup
Datasets: randomly generated 4-ary sequences
Benchmarks: codebook cardinality and code rate for n=7 to 11 segment correction failure counts over 10^8 trials segment correction time
Metrics: code rate codebook cardinality failed corrections time complexity
Baselines: VT code Cai et al. order-optimal code Garbys et al. code random codeword selection brute-force Levenshtein segment correction
Builds on: Siamese neural network PNLL loss VT code bounded distance decoder
Closest papers by meaning
- Levenshtein Distance Embedding with Poisson Regression for DNA Storage (AAAI 2024 · similarity 0.83)
- Towards A Generalist Code Embedding Model Based On Massive Data Synthesis (NeurIPS 2025 · similarity 0.80)
- Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks (ICLR 2025 · similarity 0.80)
- DOMAINEVAL: An Auto-Constructed Benchmark for Multi-Domain Code Generation (AAAI 2025 · similarity 0.80)
- LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code (ICLR 2025 · similarity 0.80)
- Privacy-Preserving Embedding via Look-up Table Evaluation with Fully Homomorphic Encryption (ICML 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.