A Simple Recursive Shannon Code

doi:10.1109/TCOMM.2011.111011.110104

Return

A Simple Recursive Shannon Code

2012-02-01

PRE

Mohammadali Khosravifard *

Hamed Narimani

T. Aaron Gulliver

DOI：10.1109/TCOMM.2011.111011.110104

Original

Original request for help

Save

Abstract

En 中文

The Shannon code is a very simple suboptimal scheme for computing prefix-free codelengths for a given memoryless source. A recursive version of the well-known Shannon code (RSh) is investigated in this paper. It has a redundancy which never exceeds that of the Shannon code. Unlike the Huffman code, the RSh code and its variations can be directly applied to sources with an infinitely countable alphabet. The average redundancy, taken over the set of all n-tuple distributions, is considered as a criterion for code comparisons. For n > 40, the average redundancy is approximately 0.14 bits for the RSh code, compared to approximately 0.5 and 0.03 bits for the Shannon and Huffman codes, respectively. For large n, a constrained version of the RSh code, called CRSh, has an average redundancy of only 0.07 bits for unsorted symbol probabilities. If the symbol probabilities are sorted in descending order, then a very simple modification of the RSh algorithm results in a code which is near-optimal from the average redundancy point of view.

Keywords:

Average redundancy

Huffman code

infinitely countable alphabet

prefix-free code

Shannon code

Kraft sum

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.