When Variable-Length Codes Meet the Field of Error Detection
Given a finite alphabet $A$ and a binary relation $\tau\subseteq A^*\times A^*$, a set $X$ is $\tau$-{\it independent} if $ \tau(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 $\tau_{d,k}$ defined by $(x,y)\in\tau_{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 $\tau_{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.
Code (0)
등록된 구현이 없습니다.
Tasks
RelationSimilar Papers 제목 키워드 기반
Deep Recurrent Quantization for Generating Sequential Binary Codes
Quantization has been an effective technology in ANN (approximate nearest neighbour) search due to its high accuracy and fast search speed. To meet the requirement of different applications, there is always a trade-off b…
Image RetrievalQuantizationRetrievalDeep Learning-Based Decoding of Constrained Sequence Codes
Constrained sequence (CS) codes, including fixed-length CS codes and variable-length CS codes, have been widely used in modern wireless communication and data storage systems. Sequences encoded with constrained sequence …
Deep LearningOptimal Formats for Weight Quantisation
Weight quantisation is an essential technique for enabling efficient training and deployment of modern deep learning models. However, the recipe book of quantisation formats is large and the formats are often chosen empi…
Variable-Length Codes Independent or Closed with respect to Edit Relations
We investigate inference of variable-length codes in other domains of computer science, such as noisy information transmission or information retrieval-storage: in such topics, traditionally mostly constant-length codewo…
Information RetrievalRetrievalFactor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding
The design of optimal linear block codes capable of being efficiently decoded is of major concern, especially for short block lengths. As near capacity-approaching codes, Low-Density Parity-Check (LDPC) codes possess sev…