# DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel

arXiv: https://arxiv.org/abs/2312.12717 · HTML: https://mlsanity.com/paper/2312.12717/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 51 references that are in the map.
- First posted on arXiv 20 Dec 2023.

## Builds on (most cited first, 10 of 10)

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [k-Nearest Neighbour Classifiers: 2nd Edition (with Python examples)](https://mlsanity.com/paper/2004.04523/) (2020)
- [Error Correction Code Transformer](https://mlsanity.com/paper/2203.14966/) (2022)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [ProductAE: Towards Training Larger Channel Codes based on Neural Product Codes](https://mlsanity.com/paper/2110.04466/) (2021)
- [Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions](https://mlsanity.com/paper/2112.09971/) (2021)
- [Deep Squared Euclidean Approximation to the Levenshtein Distance for DNA Storage](https://mlsanity.com/paper/2207.04684/) (2022)
- [Tutorial on algebraic deletion correction codes](https://mlsanity.com/paper/1906.07887/) (2019)
- [Levenshtein Distance Embedding with Poisson Regression for DNA Storage](https://mlsanity.com/paper/2312.07931/) (2023)

## Built on by (most cited first, 1 of 1)

- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)

## Abstract (arXiv)

With the emergence of new storage and communication methods, the insertion, deletion, and substitution (IDS) channel has attracted considerable attention. However, many topics on the IDS channel and the associated Levenshtein distance remain open, making the invention of a novel IDS-correcting code a hard task. Furthermore, current studies on single-IDS-correcting code misalign with the requirements of applications which necessitates the correcting of multiple errors. Compromise solutions have involved shortening codewords to reduce the chance of multiple errors. However, the code rates of existing codes are poor at short lengths, diminishing the overall storage density. In this study, a novel method is introduced for designing high-code-rate single-IDS-correcting codewords through deep Levenshtein distance embedding. A deep learning model is utilized to project the sequences into embedding vectors that preserve the Levenshtein distances between the original sequences. This embedding space serves as a proxy for the complex Levenshtein domain, within which algorithms for codeword search and segment correcting is developed. While the concept underpinning this approach is straightforward, it bypasses the mathematical challenges typically encountered in code design. The proposed method results in a code rate that outperforms existing combinatorial solutions, particularly for designing short-length codewords.