2024/03/27 by Roni Con, Con, Roni, Ryan Gabrys +3
Computer Science · #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Numerical Methods and Algorithms #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2403.19061
openalex publication_date 2024/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we consider a generalization of the well-studied problem of coding for ``stuck-at'' errors, which we refer to as ``strong stuck-at'' codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are 'frozen', meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not know also the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first, fully explicit construction of stuck-at codes that approach capacity.