On Some Properties for Universal Coding of Integers and Its Generalization

In the field of lossless source coding, universal coding of integers (UCI) and generalized universal coding of integers (GUCI) are binary codes that are suitable for probability distributions without prior knowledge. UCI <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is defined as a prefix coding in which the constant expansion factor KC times max{1,<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i>} is greater than or equal to the expected codeword length, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i> is the decreasing probability distribution of the source and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i> is the entropy of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i>. Since <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i> is decreasing, when the set of codewords of the prefix code <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is determined, the length of the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>+1-th codeword of the prefix code <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is greater than or equal to the length of the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-th codeword for any positive integer n, at which time the expected codeword length of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is minimized, and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is said to be minimal. GUCI <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</i> is defined as a prefix variable-to-variable length (VV) coding for which the constant expansion factor KG times <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i> is greater than or equal to the coding rate. In this paper, we prove two important theorems for UCI. First, we provide and prove the necessary and sufficient conditions for a minimal prefix code to be UCI. Second, we provide the first proof of an essential theorem for VV codes. This theorem can reveal the connection between UCI and GUCI and prove the converse part of Shannon’s first theorem concerning VV codes.