New Lower Bounds on the Expected Length of One-to-One Codes
Conference: TURBO - CODING - 2006 - 4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding
04/03/2006 - 04/07/2006 at Munich, Germany
Proceedings: TURBO - CODING - 2006
Pages: 6Language: englishTyp: PDF
Personal VDE Members are entitled to a 10% discount on this title
Authors:
Cheng, Jay (Department of Electrical Engineering and Institute of Communications Engineering, National Tsing Hua University, Hsinchu 30013, Taiwan, ROC)
Huang, Tien-Ke (Institute of Communications Engineering, National Tsing Hua University, Hsinchu 30013, Taiwan, ROC)
Abstract:
We consider one-to-one encodings for a discrete memoryless source, which are “one-shot” encodings associating a distinct codeword with each source symbol. Such encodings can arise when only a single source symbol rather than a sequence of source symbols needs to be transmitted. We consider two slightly different types of one-to-one encodings and provide new lower bounds on the expected length of optimal one-to-one codes. We obtain lower bounds when the size of the source alphabet is finite and its value is known, and partial information about the source symbol probabilities is available. Our lower bounds are tight and improve on a previously known tight lower bound obtained without any side information about the source symbol probabilities. We also derive several new lower bounds as well as an iterative procedure for computing sharper lower bounds for the general case that no side information about the size of the source alphabet and the source symbol probabilities is available.