NDLI: A Simple Recursive Shannon Code

Content Provider	IEEE Xplore Digital Library
Author	Khosravifard, M. Narimani, H. Gulliver, T.A.
Copyright Year	1972
Abstract	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.
Starting Page	295
Ending Page	299
Page Count	5
File Size	217393
File Format	PDF
ISSN	00906778
Volume Number	60
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Redundancy Optimization Sorting Upper bound Computational modeling Computers Context Kraft sum Average redundancy Huffman code infinitely countable alphabet prefix-free code Shannon code
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal Codes With Limited Kraft Sum

The Redundancy of an Optimal Binary Fix-Free Code Is Not Greater Than 1 bit

On the Structure of the Minimum Average Redundancy Code for Monotone Sources

How Suboptimal Is the Shannon Code?

Redundancy-Related Bounds for Generalized Huffman Codes

Some Upper Bounds on the Redundancy of Optimal Binary Fix-Free Codes

Optimal Prefix Codes for Pairs of Geometrically Distributed Random Variables

Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

A Simple Recursive Shannon Code

Similar Documents

Optimal Codes With Limited Kraft Sum

The Redundancy of an Optimal Binary Fix-Free Code Is Not Greater Than 1 bit

On the Structure of the Minimum Average Redundancy Code for Monotone Sources

How Suboptimal Is the Shannon Code?

Redundancy-Related Bounds for Generalized Huffman Codes

Some Upper Bounds on the Redundancy of Optimal Binary Fix-Free Codes

Optimal Prefix Codes for Pairs of Geometrically Distributed Random Variables

Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

A Simple Recursive Shannon Code