Notes on impulse equivalent pulse trains (Corresp.)

A subclass of Huffman sequences is examined and evaluated in terms of an analytically defined figure of merit which would be optimal for sequences of pulses of equal amplitude.     

Complementary Huffman sequences

The theories of complementary and Huffman sequences have been two distinct areas. It is shown that each Huffman sequence has its complementary pair. In radar applications, these pairs can be used, in the same way as other binary and nonbinary complementary sequences. They have the added advantage of zero autocorrelation sidelobes at all time shifts except the largest one. Even these sidelobes are cancelled if the autocorrelation functions are summed because of the complementarity.<>     

一种基于浓缩Huffman表的Huffman算法的研究与实现

Huffman编码是一种广泛使用的,非常有效的数据压缩技术。为了取得高压缩率,讨论了规范Huffman树的性质,研究了一种基于浓缩Huffman表的Huffman算法并加以实现。新的浓缩Huffman表可以减少Huffman编码表的开销,与传统Huffman表和其他改进的浓缩Huffman表相比,其最大的优点是空间大小显著减少。     

Polyphase Barker sequences up to length 36

Originally, Barker (1953) presented binary sequences for synchronization purposes in telecommunications. A sequence is called a generalized Barker sequence if the magnitude of all autocorrelation sidelobes is less or equal to one. It is shown that uniform complex sequences up to length 36, meeting the Barker (1953) condition, do exist. Examples are given for length 32-36. The sequences were obtained with a stochastic optimization algorithm, that was run with properly selected starting vectors     

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.     

On the redundancy of binary Huffman codes (Corresp.)

Some properties of Huffman codes are presented. It is shown that knowing the probabilityP_{1}of the most likely source letter, there exist new lower and upper bounds on the redundancy of the Huffman code which are tighter forP_{1} geq 0.4than those given by Shannon's first theorem or by the more recent results of Gallager. It is also shown that the new bounds are the tightest possible forP_{1} geq 0.4when it is supposed that PI is the only known probability.     

On overflow and underflow problems in buffer-instrumented variable-length coding of fixed- rate memoryless sources (Corresp.)

It is well-known that variable-length coding schemes can be employed in entropy encoding of finite-alphabet sources. To transmit these codes over a synchronous channel, however, requires a buffer. Since in practice this buffer is of finite size, it is subject to both overflow and undertow. The buffer behavior is studied with particular application to Huffman coding of the outputs of an optimum uniform-threshold quantizer driven by a memoryless Gaussian source. Fairly general upper and lower bounds on the average terminal time are developed. Under certain conditions, the tightness of these bounds is verified, and asymptotic formulas are developed. As an example, an encoding scheme employing Huffman codes in conjunction with uniform quantization of memoryless Gaussian sources is considered, and the buffer behavior as a function of the buffer size and output rate is studied.     

Spreading sequences for multicarrier CDMA systems

The paper contains an analysis of the basic criteria for the selection of spreading sequences for the multicarrier CDMA (MC-CDMA) systems with spectrum spreading in the frequency domain. It is shown that the time-domain crosscorrelation function between the spreading sequences is not a proper interference measure for the asynchronous MC-CDMA users. Therefore, the spectral correlation function is introduced and, together with the crest factor and the dynamic range of the corresponding multicarrier waveforms, is used for the evaluation of MC-CDMA sequences. Some well-known classes of sequences, such as Walsh, Gold, orthogonal Gold, and Zadoff-Chu sequences, as well as Legandre and Golay complementary sequences, are evaluated with respect to the aforementioned basic criteria. It is also shown that the crest factors of the multicarrier spread spectrum waveforms based on the multilevel Huffman sequences are very close to or even lower than the crest factor of a single sine wave     

Self-synchronizing Huffman codes (Corresp.)

A problem associated with the use of variable-length source codes is that loss of synchronization may lead to extended errors in the decoded text. In this correspondence it is shown that some binary Huffman codes contain a codeword that resynchronizes the decoder regardless of the synchronization slippage preceding that codeword. Such codes are self-synchronizing in a probabilistic sense, yet require no additional system overhead. Some sufficient conditions are found for the existence or nonexistence of self-synchronizing Huffman codes for many classes of source probabilities. One of our results shows that many common languages can be encoded with self-synchronizing Huffman codes.     

An application of informational divergence to Huffman codes

A classification of all probability distributions over the finite alphabet of an information source is given, where the classes are the sets of distributions sharing the same binary Huffman code. Such a classification can be used in noiseless coding, when the distribution of the finite memoryless source varies in time or becomes gradually known. Instead of applying the Huffman algorithm to each new estimate of the probability distribution, if a simple test based on the above classification is passed, then the Huffman code used previously is optimal also for the new distribution.     

最优二叉树的生成及应用

衡量一个算法的优劣有许多因素,效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决,在同等条件下,执行时间短的算法其效率是最高的。从霍夫曼树的定义以及霍夫曼算法出发,介绍如何构造霍夫曼树以及利用霍夫曼算法优化程序设计的原理,重点讨论在判定类问题中利用霍夫曼树可以建立最佳判定算法,提高程序的执行速度。     

Low power parallel Huffman decoding

A low power design technique for a parallel Huffman decoder is presented. According to the length of the incoming Huffman codeword, the proposed strategy makes the barrel shifter in the parallel Huffman decoder turn off the unnecessary shifting bits to reduce power dissipation. The result of a SPICE simulation indicates that up to 50 percent power reduction in the barrel shifter may be achieved with the proposed technique     

MP3／AAC解码器中Huffman硬件加速器设计与实现

Huffman解码是感知音频解码过程的重要部分。软件实现Huffman解码运算,计算速度慢、功耗高,采用硬件实现的方法,设计并实现了一个兼容MP3与AAC标准的Huffman解码硬件加速器。采用十六叉树搜索算法．在存储空间增加不大的情况下,有效减少了Huffman码字的搜索深度,简化寻址操作,加快了搜索速度。通过直接外设访问的接口设计,该硬件加速器还可快速进行音频码流的数据读取。在XilinixFPGA上的功能和性能验证表明。该Huffman硬件加速器可成功应用于MP3和AAC解码器。     

基于XScale平台的MPEG-4 AAC解码器Huffman算法优化

Huffman算法的实现是MPEG-4 AAC解码的一个关键部分,它在整个解码算法中占有很大的运算比重和内存开销。讨论了不同的Huffman解码算法及其改进,结合AAC解码器不同码表的特点,针对XScale处理器选择了其合适的Huffman解码算法,并对每种选择的算法从提高解码效率、减少内存开销的角度进行了优化．达到了理想的效果。     

基于编码压缩和加密的图像可逆信息隐藏算法

提出一种编码压缩和加密的图像可逆信息隐藏算 法。计算载体像素预测值与其像素值的差值, 对差值进行哈夫曼编码压缩,通过压缩数据和随机数据加密重构图像,得到载体数据。将哈 夫曼编码的码 表和秘密信息隐藏在载体数据中,实现信息隐藏。在载密数据中提取码表数据和秘密信息, 对加密压缩数 据进行解密,结合码表和预测方法恢复原始图像。实验结果表明,本文算法具有较大的隐藏 容量,不仅能 正确提取秘密信息,还能无损恢复原始图像。     

Tight bounds on the redundancy of Huffman codes

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p₁ of the most likely source letter is presented. This method will be used to compute bounds for all p₁⩾1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D-ary Huffman codes, 2⩽D<∞, are given, which are the tightest possible for all p₁⩾1/2     

Data structure of Huffman codes and its application to efficient encoding and decoding (Corresp.)

The data structure of Huffman codes and its application to efficient encoding and decoding of Huffman codes are studied in detail. The tree structure is presented by a two-dimensional array which can be applied for the decoding of Huffman codes as a state transition table of the finite-state decoding automaton. Inversion produces a one-dimensional state transition table of the semiautonomous finite-state sequential machine which can be used as a Huffman encoder with a push-down stack. The encoding and decoding procedures are simple and efficient. It is not only possible to implement by simple hardware but is also applicable to software implementation.     

一种基于八叉树的Huffman解码方法及其在MPEG-4中的应用

传统的二值Huffman解码方法的解码效率较低。为了提高解码速度,该文提出了一种基于八叉树的Huffman解码方法。该方法将Huffman码表示为八叉树结构,并根据各个节点在树中的位置将码表重建为一维数组。解码时,每次从码流中读取3 bit码元,并使用数值计算代替判断和跳转操作,从而提高了解码效率。将本文方法应用于MPEG-4 VLC和RVLC解码的实验结果表明,该方法在内存增加不大的情况下能大幅度提高Huffman解码效率,其性能优于其它方法。     

面向监控系统的计算机屏幕图像编码/解码器的研制

在空中交通管制等关键系统中要求7×24 h不停机对系统计算机屏幕进行无损记录,同时记录的存储代价不能过大。针对屏幕图像序列的特点,采用图像差异提取、LZSS压缩Huffman编码等技术,实现了一个性能良好的Codec,其CPU占用率比XviD低50%左右,存储代价低40%左右。