List Permutation Invariant Linear Codes: Theory and Applications

The class of q-ary list permutation invariant linear codes is introduced in this paper along with probabilistic arguments that validate their existence when certain conditions are met. The specific class of codes is characterized by an upper bound that is tighter than the generalized Shulman-Feder bound and relies on the distance of the codes´ weight distribution to the binomial (multinomial, respectively) one. The bound applies to cases where a code from the proposed class is transmitted over a q-ary output symmetric discrete memoryless channel and list decoding with fixed list size is performed at the output. In the binary case, the new upper bounding technique allows the discovery of list permutation invariant codes whose upper bound coincides with sphere-packing exponent. Furthermore, the proposed technique motivates the introduction of a new class of upper bounds for general q-ary linear codes whose members are at least as tight as the DS2 bound as well as all its variations for the discrete channels treated in this paper.