## Abstract

The minimum expected length for fixed-to-variable length encoding of an n -block memoryless source with entropy H grows as n H + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as n H - 1\2 log n +O(1) unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.

Original language | English (US) |
---|---|

Article number | 5895099 |

Pages (from-to) | 4017-4025 |

Number of pages | 9 |

Journal | IEEE Transactions on Information Theory |

Volume | 57 |

Issue number | 7 |

DOIs | |

State | Published - Jul 2011 |

## All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences

## Keywords

- Analytic information theory
- Shannon theory
- fixed-to-variable lossless compression
- memoryless sources
- one-to-one codes
- source coding