Upper bounds refined for codes with fixed symbol weights and compositions
Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes
Information Theory
Summary
Codes with specific patterns, like fixed numbers of certain symbols, are important in reliable data transmission. The authors studied and extended classic ways to calculate the maximum size of such codes. They connected these calculations to ideas from information theory and found new mathematical properties and better bounds. Their work helps us understand and improve limits on code sizes more precisely.
What this means in practice
- •For communication system designers: Develop tighter constraints on code sizes for systems requiring fixed symbol weights to improve error detection and correction analysis.
- •For data storage engineers: Optimize storage encoding schemes with constant-composition constraints to better estimate capacity and reliability limits.
A theory result. No direct application yet.
Authors
Artur Akhiiarov, Peter Boyvalenkov, Danila Cherkashin, Andrei Raigorodskii
Abstract
Deriving upper bounds on code size from existing bounds is a classical approach in coding theory, dating back to the seminal results of Elias, Bassalygo, and Levenshtein. We study a framework encompassing the Bassalygo--Elias and Levenshtein inequalities for binary and nonbinary (constant-weight) codes and provides certain generalizations. The asymptotic cost of transferring a bound between different symbol compositions is expressed in terms of mutual information, yielding an information-theoretic optimal transport formulation. We determine the optimal permutation-transport cost between arbitrary compositions in terms of their least common majorant in the majorization order. Specializing to symmetric constant-weight compositions yields explicit transport profiles. As a byproduct, we establish unimodality of the asymptotic constant-weight rate as a function of the relative weight. We prove that the resulting closure operators are idempotent and that applying transport before outer Bassalygo--Elias averaging leaves the unrestricted bound obtained from the same input unchanged. We also establish necessary and sufficient conditions for an upper bound to be a fixed point of the closure operator. Since the asymptotic rate function is an upper bound for itself and it is a fixed point, we conclude the Schur concavity of the constant-composition rate function. Finally, we survey existing upper bounds for binary and nonbinary constant-weight and constant-composition codes, combine them into optimized envelopes within the transport framework, and obtain improved theoretical and numerical bounds.