NDLI: An A*-Based Algorithm for Constructing Reversible Variable Length Codes with Minimum Average Codeword Length

Content Provider	IEEE Xplore Digital Library
Author	Yuh-Ming Huang Ting-Yi Wu Han, Y.S.
Copyright Year	1972
Abstract	Variable length codes (VLCs) are widely adopted in many compression standards due to their good coding efficiency on average codeword length. However, an inherent problem with a VLC is that an error of even one bit can cause serious error propagation and thus loss of synchronization at the receiver, which would lead to a series of non-correctly decoded symbols. Reversible variable length codes (RVLCs) were introduced to significantly mitigate this phenomenon. In this work, a method to find an optimal RVLC in terms of the minimum average codeword length is first formulated as a tree-searching problem, and then, instead of performing an exhaustive search, an A*-based construction algorithm is proposed to find an optimal RVLC. The proposed algorithm has been applied to several benchmarks for sources and has found respective optimal symmetric and asymmetric RVLCs.
Starting Page	3175
Ending Page	3185
Page Count	11
File Size	498565
File Format	PDF
ISSN	00906778
Volume Number	58
Issue Number	11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-11-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	Encoding Binary trees Construction industry Search problems Upper bound Transform coding Standards A* algorithm Source coding reversible variable length codes
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

On Optimal and Achievable Fix-Free Codes

On the Design of Variable-Length Error-Correcting Codes

A lower bound on average codeword length of variable length error-correcting codes

The Construction of Variable Length Codes With Good Synchronization Properties

On the Construction of (Explicit) Khodak's Code and Its Analysis

On the Relationships Among Optimal Symmetric Fix-Free Codes

On constructing symmetrical reversible variable-length codes independent of the Huffman code

Distribution of Distributed Arithmetic Codewords for Equiprobable Binary Sources

The minimum codeword length and redundancy in the binary Huffman code for uncertain sources

An A*-Based Algorithm for Constructing Reversible Variable Length Codes with Minimum Average Codeword Length

Similar Documents

On Optimal and Achievable Fix-Free Codes

On the Design of Variable-Length Error-Correcting Codes

A lower bound on average codeword length of variable length error-correcting codes

The Construction of Variable Length Codes With Good Synchronization Properties

On the Construction of (Explicit) Khodak's Code and Its Analysis

On the Relationships Among Optimal Symmetric Fix-Free Codes

On constructing symmetrical reversible variable-length codes independent of the Huffman code

Distribution of Distributed Arithmetic Codewords for Equiprobable Binary Sources

The minimum codeword length and redundancy in the binary Huffman code for uncertain sources

An A*-Based Algorithm for Constructing Reversible Variable Length Codes with Minimum Average Codeword Length