In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most D ones, where D is a given input parameter. We provide an O(n2D)-time complexity algorithm for the construction of such codes, where n is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. Our algorithms allow us to construct both optimal average-length prefix binary codes and optimal average-length alphabetic binary codes. In the former case, our O(n2D)-time algorithm substantially improves on the previously known O(n2+D)-time complexity algorithm for the same problem. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword.
Optimal Binary Variable-Length Codes with a Bounded Number of 1's Per Codeword: Design, Analysis, and Applications
Bruno R.;De Prisco R.;Vaccaro U.
2025
Abstract
In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most D ones, where D is a given input parameter. We provide an O(n2D)-time complexity algorithm for the construction of such codes, where n is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. Our algorithms allow us to construct both optimal average-length prefix binary codes and optimal average-length alphabetic binary codes. In the former case, our O(n2D)-time algorithm substantially improves on the previously known O(n2+D)-time complexity algorithm for the same problem. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
