Abstract
One-to-one codes are nonsingular codes that assign a distinct codeword to each source symbol. One-to-one encodings are also known as "one-shot" encodings as they could be employed when one only needs to transmit a single source symbol rather than a sequence of source symbols. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. In this paper, we consider two slightly different types of one-to-one encodings, namely, {0, 1} + -encodings and {0,1}*-encodings, depending on whether the empty codeword is used or not. Given that the probability p 1 of the most likely source symbol is available, we derive a new upper bound on the redundancy of the optimal {0, l} + -encoding which is tight for 1/3 ≤ p 1 ≤ 1, and a new upper bound on the redundancy of the optimal {0, l}*-encoding which is tight for 0.3136 ≤ p 1 ≤ 1. Our results improve on the best known upper bounds in the literature. © 2007 IEEE.