NDLI: Efficient alphabet partitioning algorithms for low-complexity entropy coding

Content Provider	IEEE Xplore Digital Library
Author	Said, A.
Copyright Year	2005
Description	Author affiliation: Hewlett Packard Labs., Palo Alto, CA, USA (Said, A.)
Abstract	We analyze the technique for reducing the complexity of entropy coding consisting of the a priori grouping of the source alphabet symbols, and in dividing the coding process in two stages: first coding the number of the symbol's group with a more complex method, followed by coding the symbol's rank inside its group using a less complex method, or simply using its binary representation. Because this method proved to be quite effective it is widely used in practice, and is an important part in standards like MPEG and JPEG. However, a theory to fully exploit its effectiveness had not been sufficiently developed. In this work, we study methods for optimizing the alphabet decomposition, and prove that a necessary optimality condition eliminates most of the possible solutions, and guarantees that dynamic programming solutions are optimal. In addition, we show that the data used for optimization have useful mathematical properties, which greatly reduce the complexity of finding optimal partitions. Finally, we extend the analysis, and propose efficient algorithms, for finding min-max optimal partitions for multiple data sources. Numerical results show the difference in redundancy for single and multiple sources.
Sponsorship	Brandeis Univ
Starting Page	183
Ending Page	192
File Size	177612
Page Count	10
File Format	PDF
ISBN	0769523099
ISSN	10680314
DOI	10.1109/DCC.2005.35
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-03-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Partitioning algorithms Entropy coding Decoding Optimization methods Dynamic programming Algorithm design and analysis Computational complexity Facsimile MPEG standards Image coding
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

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

Alphabet Partitioning Techniques for Semiadaptive Huffman Coding of Large Alphabets

Successively refinable trellis coded quantization

Performance-complexity tradeoffs of the MPEG-4 ALS lossless coding standard

SBHP-a low complexity wavelet coder

Multiplication-free subband coding of color images

Reduced-complexity waveform coding via alphabet partitioning

Efficient Bit Allocation Algorithm For MPEG-4 Advanced Audio Coding

Hierarchical Dynamic Range Coding of Wavelet Subbands for Fast and Efficient Image Decompression

Classification oriented embedded image coding

Efficient alphabet partitioning algorithms for low-complexity entropy coding

Similar Documents

Alphabet Partitioning Techniques for Semiadaptive Huffman Coding of Large Alphabets

Successively refinable trellis coded quantization

Performance-complexity tradeoffs of the MPEG-4 ALS lossless coding standard

SBHP-a low complexity wavelet coder

Multiplication-free subband coding of color images

Reduced-complexity waveform coding via alphabet partitioning

Efficient Bit Allocation Algorithm For MPEG-4 Advanced Audio Coding

Hierarchical Dynamic Range Coding of Wavelet Subbands for Fast and Efficient Image Decompression

Classification oriented embedded image coding

Efficient alphabet partitioning algorithms for low-complexity entropy coding