2026/07/21 by Shengwei Liu, Chunyan Qin
#cs.IT #math.IT
A code C⊆ Fqn is (τ,L)-list-decodable if every Hamming ball of radius τ contains at most L codewords of C. Here τ is the list-decoding radius, and L is the list size. Singleton-type bounds constrain the radius and the rate when L is fixed. These bounds are not the only possible constraints on list-decodable codes. In this paper, we derive an upper bound on the list-decoding radius in terms of generalized Hamming weights. As a consequence, for 1≤ L≤ q-1, every (τ,L)-list-decodable q-ary linear code has minimum distance at least τ+\lfloor \fracτL\rfloor+1. Combining this lower bound with the classical Griesmer bound gives a Griesmer-type lower bound on the block length. For q=3a, we construct an explicit family of q-ary linear [q+3,2,q+1] codes. These codes are (2q/3,2)-list-decodable and meet the Griesmer-type bound with equality. They do not attain the Singleton-type bound. Thus the Griesmer-type bound can be a strict improvement over the Singleton-type bound.