Complete decoding method revealed for special error-correcting codes
Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes
Information Theory
Summary
The paper studies a particular family of error-correcting codes called Gashkov-Sidel'nikov codes used in digital communication. It shows how to break down the decoding problem into two parts: finding the smallest number of errors that caused a problem, and then fixing those errors exactly. The authors identify mathematical properties that let them do this efficiently and provide a full method for maximum-likelihood decoding, guaranteeing the best possible error correction.
What this means in practice
- •For digital communication engineers: Implement efficient exact decoders for Gashkov-Sidel'nikov codes to improve error correction in communication channels.
- •For storage system developers: Use the decoding techniques to enhance reliability and error recovery in data storage systems employing related cyclic codes.
Authors
Minjia Shi, Shitao Li, Yuhong Xia, Tor Helleseth, Ferruh Ozbudak
Abstract
Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages: determining the minimum error weight associated with a syndrome $S$ and constructing an error vector attaining this minimum. We identify the former quantity with the minimum additive length of $S$ with respect to $\mathcal T$ and determine it exactly by the norm and the quadratic character of $\mathbb F_q$. We also determine the complete coset-weight distribution and recover the known covering radius $3$. For the constructive part, we use quadratic-character sums and Weil bounds to construct a coset leader for every syndrome of coset weight three. The resulting procedures give complete maximum-likelihood decoders.