When Variable-Length Codes Meet the Field of Error Detection
This work addresses a theoretical problem in coding theory for researchers, but it appears incremental as it builds on existing frameworks without introducing new methods or broad advancements.
The paper tackles the problem of determining the error detection and correction capabilities of variable-length codes under various quasi-metrics, focusing on whether these conditions are decidable for regular codes. It examines specific metrics like the prefix and factor metrics, but does not provide concrete numerical results or performance gains.
Given a finite alphabet $A$ and a binary relation $τ\subseteq A^*\times A^*$, a set $X$ is $τ$-{\it independent} if $ τ(X)\cap X=\emptyset$. Given a quasi-metric $d$ over $A^*$ (in the meaning of \cite{W31}) and $k\ge 1$, we associate the relation $τ_{d,k}$ defined by $(x,y)\inτ_{d,k}$ if, and only if, $d(x,y)\le k$ \cite{CP02}.In the spirit of \cite{JK97,N21}, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $τ_{d,k}$. With respect to the prefix metric, the factor one, and every quasi-metric associated to (anti-)automorphisms of the free monoid, we examine whether those conditions are decidable for a given regular code.