List decodability of symbol-pair codes

• Main Authors: Liu, Shu, Xing, Chaoping, Yuan, Chen
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2020
• Subjects: Engineering::Computer science and engineering; Block Code; Symbol-pair Metric Code
• Online Access: https://hdl.handle.net/10356/138021
• Institution: Nanyang Technological University

We investigate the list decodability of symbol-pair codes 1 in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric.