List decoding of cover metric codes up to the singleton bound

Abstract

Wachter-Zeh showed that every cover metric code can be list decoded up to the Johnson-like bound. Furthermore, it was shown that the efficient list decoding of cover metric codes up to the Johnson-like bound can be performed. From the work of Wachter-Zeh, one natural question is whether the Johnson-like bound can be improved. In this paper, we give a confirmative answer to this question by showing that the cover metric codes can be list decoded up to the Singleton bound. Our contributions consist of three parts. First, we prove that the list decodability of cover metric codes does not exceed the Singleton bound. Second, we show that, with high probability, a random cover metric code can be list decoded up to the Singleton bound, which is better than the Johnson-like bound. Third, by applying the existing decoding algorithms for Hamming metric and rank metric codes, we present explicit constructions of cover metric codes that can be efficiently list decoded up to the Singleton bound.