Iterative construction of reversible variable-length codes and variable-length error-correcting codes

We propose a generic algorithm for the construction of efficient reversible variable-length codes (RVLCs) and variable-length error-correcting (VLEC) codes, which optimizes the codeword length distribution. The algorithm may be applied to any existing codeword selection mechanism, and it is capable of generating codes of higher efficiency in comparison to the algorithms disseminated in the literature.     

Unified variable-length transform coding and image-adaptive vectorquantization

The authors introduce an image coding method which unifies two image coding techniques: variable-length transform coding (VLTC) and image-adaptive vector quantization (IAVQ). In both VLTC and IAVQ, the image is first decomposed into a set of blocks. VLTC encodes each block in the transform domain very efficiently: however, it ignores the interblock correlation completely. IAVQ addresses the interblock correlation by using a codebook generated from a subset of the blocks to vector-quantize all blocks. Although the resulting codebook represents the input image better than a universal codebook generated from a large number of training images, it has to be transmitted separately as an overhead, therefore degrading the coding performance at high bit rates     

Memory allocation for Huffman coding of multiple sources

The authors propose an efficient memory allocation method for memory-constrained Huffman coding of multiple sources which employs the iterative bisection algorithm. The proposed method provides better performance over conventional allocation methods and can be applied to many adaptive variable-length coders with memory constraints     

A variable-length source coding theorem for correlated information sources

A variable-length source coding theorem is proved for a pair of discrete memoryless correlated information sources. The average length of codewords per source letter for source X provided the side information Y is bounded below by the conditional entropy H(X|Y) and above by the same entropy plus J/L where L is the number of source letters encoded and J is the size of ensemble Y. The Huffman encoding procedure is also generalized for this case.     

Xilinx哈夫曼编码系统设计

在图像处理、文件传真、视频压缩编码中,哈夫曼编码是最常用的一种编码方式.本文设计并实现了对一段数字序列进行哈夫曼编码并将编码结果串行输出的电路模块,电路由输入数据的排序、数据的哈夫曼编码、数据序列编码的结果输出三个核心模块组成,在Xilinx平台上通过硬件描述语言实现该电路.仿真结果表明,该电路编码正确,并具有较高的工作频率和编码效率.     

High-capacity reversible data hiding in encrypted image based on Huffman coding and differences of high nibbles of pixels

In this paper, we propose a new reversible data hiding method in encrypted images. Due to spatial correlation, there is a large probability that the adjacent pixels of the image have small differences, which is especially obvious on the high four most significant bits (high nibbles) of the pixels. If the high nibble of each pixel is regarded as a 4-bit value, the differences between the high nibbles of the adjacent pixels are mostly concentrated in a small range. Based on this fact, Huffman coding was used to encode all the differences between the high nibbles of the adjacent pixels in order to compress the four most significant bit (MSB) planes efficiently and create a large-capacity room. After creating room, a stream cipher is used to encrypt the image, and the room is reserved in the encrypted image for data hiding without losing information. The experimental results showed that the proposed method can achieve a larger embedding rate and better visual quality of the marked decrypted image than other related methods.     

Memory efficient and high-speed search Huffman coding

Code compression is a key element in high-speed digital data transport. A major compression is performed by converting the fixed-length codes to variable-length codes through a (semi-)entropy coding scheme. Huffman coding is shown to be a very efficient coding scheme. To speed up the process of search for a symbol in a Huffman tree and to reduce the memory size we have proposed a tree clustering algorithm to avoid high sparsity of the tree. The method is shown to be extremely efficient in memory requirement, and fast in searching for the symbol. For an experimental video data with Huffman codes extended up to 13 bits in length, the entire memory space is shown to be 122 words, compared to 2¹³=8192 words in a normal situation     

Weak variable-length Slepian-Wolf coding with linked encoders for mixed sources

Coding problems for correlated information sources were first investigated by Slepian and Wolf. They considered the data compression system, called the SW system, where two sequences emitted from correlated sources are separately encoded to codewords, and sent to a single decoder which has to output the original sequence pairs with a small probability or error. In this paper, we investigate the coding problem of a modified SW system allowing two encoders to communicate with zero rate. First, we consider the fixed-length coding and clarify that the admissible rate region for general sources is equal to that of the original SW system. Next, we investigate the variable-length coding having the asymptotically vanishing probability of error. We clarify the admissible rate region for mixed sources characterized by two ergodic sources and show that this region is strictly wider than that for fixed-length codes. Further, we investigate the universal coding problem for memoryless sources in the system and show that the SW system with linked encoders has much more flexibility than the original SW system.     

On error detection and error synchronization of reversible variable-length codes

Reversible variable-length codes (RVLCs) are not only prefix-free but also suffix-free codes. Due to the additional suffix-free condition, RVLCs are usually nonexhaustive codes. When a bit error occurs in a sentence from a nonexhaustive RVLC, it is possible that the corrupted sentence is not decodable. The error is said to be detected in this case. We present a model for analyzing the error detection and error synchronization characteristics of nonexhaustive VLCs. Six indices, the error detection probability, the mean and the variance of forward error detection delay length, the error synchronization probability, the mean and the variance of forward error synchronization delay length are formulated based on this model. When applying the proposed model to the case of nonexhaustive RVLCs, these formulations can be further simplified. Since RVLCs can be decoded in backward direction, the mean and the variance of backward error detection delay length, the mean and the variance of backward error synchronization delay length are also introduced as measures to examine the error detection and error synchronization characteristics of RVLCs. In addition, we found that error synchronization probabilities of RVLCs with minimum block distance greater than 1 are 0.     

An efficient repetition finder for improving dynamic Huffman coding

In this paper, a new repetition finder to be used with dynamic Huffman (1952) coding is proposed to improve the compression efficiency by reducing the redundancy due to string repetitions. Compared to the repetition finder proposed by Yokoo (1991), the proposed scheme effectively increases the numbers of consecutive symbols in the repetition mode and the total number of symbols in the repetition mode. Experimental results show that the proposed method outperforms the repetition finder of Yokoo by 14-40% in compression ratios with about the same memory requirement and running time     

Split variable-length input Huffman code with application to test data compression for embedded cores in SOCs

In this article, a run length encoding-based test data compression technique has been addressed. The scheme performs Huffman coding on different parts of the test data file separately. It has been observed that up to a 6% improvement in compression ratio and a 29% improvement in test application time can be achieved sacrificing only about 6.5% of the decoder area. We have compared our results with the other contemporary works reported in the literature. It has been observed that for most of the cases, our scheme produces a better compression ratio and that the area requirements are much less.     

多进制霍夫曼编码方法及最优性证明

信源编码最常用的翟夫曼可变长编码是性能最优的唯一可译即时码。在讨论编码方法时常以二进制为例进行。多进制的霍夫曼编码如何进行,怎样证明得到的编码一定是平均码长最短的唯一可译即时码,是本文讨论和证明的主题。     

Condensed table of Huffman coding, a new approach to efficient decoding

This letter introduces a new technique for designing and decoding Huffman codes. The key idea is to define a condensed Huffman table (CHT) that is smaller than the ordinary Huffman table and which leads to fast decoding. For example, the new approach has been shown to reduce the memory consumption by a factor of eight, compared with the single-side grown Huffman table.     

基于verilog实现哈夫曼编码的新方法

传统的硬件实现哈夫曼编码的方法主要有:预先构造哈夫曼编码表,编码器通过查表的方法输出哈夫曼编码[1];编码器动态生成哈夫曼树,通过遍历节点方式获取哈夫曼编码[2-3].第一种方法从平均码长角度看,在很多情况下非最优;第二种方法需要生成完整的哈夫曼树,会产生大量的节点,且需遍历哈夫曼树获取哈夫曼编码,资源占用多,实现较为麻烦.本文基于软件实现[4]时,使用哈夫曼树,会提出一种适用于硬件并行实现的新数据结构——字符池,通过对字符池的频数属性比较和排序来决定各个字符节点在字符池中的归属.配置字符池的同时逐步生成哈夫曼编码,可以提高硬件利用率,并且无需额外操作来提取哈夫曼编码.     

Unary prefixed Huffman coding for a group of quantized generalized Gaussian sources

We propose a coding algorithm called unary prefixed Huffman (UPH) coding for a family of infinite sources called quantized generalized Gaussian (GG) sources. Compared with the existing codes for these GG sources, the UPH algorithm provides a more adaptive approach, and its coding efficiency is upper bounded by entropy +2.     

Interval and recency rank source coding: Two on-line adaptive variable-length schemes

In the schemes presented the encoder maps each message into a codeword in a prefix-free codeword set. In interval encoding the codeword is indexed by the interval since the last previous occurrence of that message, and the codeword set must be countably infinite. In recency rank encoding the codeword is indexed by the number of distinct messages in that interval, and there must be no fewer codewords than messages. The decoder decodes each codeword on receipt. Users need not know message probabilities, but must agree on indexings, of the codeword set in an order of increasing length and of the message set in some arbitrary order. The average codeword length over a communications bout is never much larger than the value for an off-line scheme which maps thejth most frequent message in the bout into thejth shortest codeword in the given set, and is never too much larger than the value for off-line Huffman encoding of messages into the best codeword set for the bout message frequencies. Both schemes can do much better than Huffman coding when successive selections of each message type cluster much more than in the independent case.     

An improvement of dynamic Huffman coding with a simple repetitionfinder

A mixed-mode file compression scheme that incorporates interval encoding for finding duplicate occurrences of strings without storing or parsing the past sequence and a one-pass scheme for dynamic Huffman codes is presented. Results from experiments performed on various types of files are discussed. The proposed method runs in linear time, and the memory requirement depends only on the alphabet size. The code efficiency is compared experimentally to that of other schemes     

Huffman coding of DCT coefficients using dynamic codeword assignment and adaptive codebook selection

In many image sequence compression applications, Huffman coding is used to eliminate statistical redundancy resident in given data. The Huffman table is often pre-defined to reduce coding delay and table transmission overhead. Local symbol statistics, however, may be much different from the global ones manifested in the pre-defined table. In this paper, we propose three Huffman coding methods in which pre-defined codebooks are effectively manipulated according to local symbol statistics. The first proposed method dynamically modifies the symbol-codeword association without rebuilding the Huffman tree itself. The encoder and decoder maintain identical symbol-codeword association by performing the same modifications to the Huffman table, thus eliminating extra transmission overhead. The second method adaptively selects a codebook from a set of given ones, which produces the minimum number of bits. The transmission overhead in this method is the codebook selection information, which is observed to be negligible compared with the bit saving attained. Finally, we combine the two aforementioned methods to further improve compression efficiency. Experiments are carried out using five test image sequences to demonstrate the compression performance of the proposed methods.     

基于3D-DPCM和变长编码的超光谱图像无损压缩

剖析了干涉成像光谱仪拍摄图像的空间和谱间相关性,提出一种三维DPCM无损压缩方案。首先做谱间DPCM预测,再应用帧内DPCM预测于残差图像,最后对差分码流实施变长编码。实验表明,该算法能完成无损压缩,平均压缩比为1.486,相比整数小波变换（二维）算法提高3.3%,且算法复杂度较低,仅有加、减法和移位运算,便于硬件实现。     

A generalization of Huffman coding for messages with frequencies given by upper and lower bounds (Corresp.)

A generalization of the Huffman coding procedure is given for cases in which the source letter probabilities are known only to fall in certain ranges.