Design and Analysis of the Two-level Scalar Quantizer with Extended Huffman Coding

Abstract

Entropy coding is a type of lossless coding to compress digital data by representing frequently occurring patterns with few bits and rarely occurring patterns with many bits. Two most popular entropy coding schemes are Huffman coding and arithmetic coding. The basic idea in Huffman coding is to assign short codewords to those input blocks with high probabilities and long codewords to those with low probabilities. Extended Huffman coding is the procedure of determining the optimal length of codewords for blocks of two or more symbols. In this paper we concerned with blocks of two, three, four and five symbols. In this paper we propose a model of the two-level scalar quantizer with extended Huffman coding and variable decision threshold. We decide that the new quantizer model has only two representation levels due to small model complexity and the possibility of the efficient use of the Huffman coding procedure. Variable decision threshold is proposed so the representation levels’ assymetry can be achieved. The basic idea described in this paper is that, unlike to the Lloyd-Max's quantizer, the asymmetry of the representation levels is assumed such that to provide an unequal probability of representation levels for the symmetric Gaussian probability density function (PDF). Representation levels are determined from the centroid condition. Variable decision threshold is determined depending on signal quality that wants to be achieved. The proposed quantizer model is optimal when the variable decision threshold is equal to zero. The goal of designing the proposed model is the approaching of the average bit rate to the source entropy as close as possible. The performances of the quantizer are often determined by SQNR. The optimal SQNR value of the Lloyd-Max's quantizer having two quantization levels is 3 dB for Laplacian PDF, and 4.3965 dB for Gaussian PDF. Therefore, the SQNR range in which we consider the performance of the proposed quantizer is from 3 dB to 4.3965 dB, that is we considered the range of decision variable t1 from 0 to 1.2 with step 0.1. Comparing numerical results for the proposed quantizer and results obtained in case when the signal at the entrance of the proposed quantizer is described by Laplacian PDF, it is shown that better performances are achieved with the proposed quantizer model for Gaussian PDF. Also, it is shown that with the increase of symbol blocks’ number that make one block the average bit rate of the proposed quantizer with extended Huffman coding converges more closely to the source entropy. However with the symbol increase in one block, the complexity of designing the proposed quatizer model increases too. Therefore it is important to compromise between the complexity of designing the proposed quantizer model and signal quality that wants to be achieved.