List Decodability of Symbol-Pair Codes

Understand

We investigate the list decodability of symbol-pair codes in the present paper.

• Firstly, we show that 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.