削除符号論文メモ:2021/01/13

タイトル: List-decodable Codes for Single-deletion Single-substitution with List-size Two
著者名: Wentu Song, Kui Cai, and Tuan Thanh Nguyen
アクセス: https://arxiv.org/abs/2201.02013v1

Abstract: In this paper, we present an explicit construction of list-decodable codes for single-deletion and single-substitution with list size two and redundancy 3 log n+4, where n is the block length of the code. Our construction has lower redundancy than the best known explicit construction by Gabrys et al. (arXiv 2021), whose redundancy is 4 log n + O(1)


 

タイトル: A new construction of linear codes with one-dimensional hull
著者名: Lin Sok
ジャーナル: Designs, Codes and Cryptography
アクセス: https://link.springer.com/article/10.1007/s10623-021-00991-4

Abstract: The hull of a linear code C is the intersection of C with its dual C⊥. The hull with low dimensions gets much interest due to its crucial role in determining the complexity of algorithms for computing the automorphism group of a linear code and for checking permutation equivalence of two linear codes. The hull of linear codes has recently found its application to the so-called entanglement-assisted quantum error-correcting codes (EAQECCs). In this paper, we provide a new method to construct linear codes with one-dimensional hull. This construction method improves the code lengths and dimensions of the recent results given by the author. As a consequence, we derive several new classes of optimal linear codes with one-dimensional hull. Some new EAQECCs are presented.


 

タイトル: Design and Performance of Low-Density Parity-Check Codes for
Noisy Channels with Synchronization Errors
著者名: Ryo SHIBATA, Hiroyuki YASHIMA
ジャーナル: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
DOI: https://doi.org/10.1587/transfun.2021EAL2013

Abstract:  In this letter, we study low-density parity-check (LDPC)
codes for noisy channels with insertion and deletion (ID) errors. We
first propose a design method of irregular LDPC codes for such channels,
which can be used to simultaneously obtain degree distributions for
different noise levels. We then show the asymptotic/finite-length
decoding performances of designed codes and compare them with the
symmetric information rates of cascaded ID-noisy channels. Moreover, we
examine the relationship between decoding performance and a code
structure of irregular LDPC codes.


 

タイトル: Coding for Sequence Reconstruction for Single Edits
著者名: Kui Cai, Han Mao Kiah, Tuan Thanh Nguyen, Eitan Yaakobi
ジャーナル: IEEE Transactions on Information Theory
DOI:https://10.1109/TIT.2021.3122798

Abstract: The sequence reconstruction problem, introduced by
Levenshtein in 2001, considers a communication scenario where the sender
transmits a codeword from some codebook and the receiver obtains
multiple noisy reads of the codeword. The common setup assumes the
codebook to be the entire space and the problem is to determine the
minimum number of distinct reads that is required to reconstruct the
transmitted codeword. Motivated by modern storage devices, we study a
variant of the problem where the number of noisy reads N is fixed.
Specifically, we design reconstruction codes that reconstruct a codeword
from N distinct noisy reads. We focus on channels that introduce a
single edit error (i.e. a single substitution, insertion, or deletion)
and their variants, and design reconstruction codes for all values of N . In particular, for the case of a single edit, we show that as the
number of noisy reads increases, the number of redundant symbols
required can be gracefully reduced from logqn+O(1) to logqlogqn+O(1) ,
and then to O(1) , where n denotes the length of a codeword. We also
show that these reconstruction codes are asymptotically optimal. Finally,
via computer simulations, we demonstrate that in certain cases,
reconstruction codes can achieve similar performance as classical error-
correcting codes with less redundant symbols.