A suboptimum variable-length encoding procedure for discrete quantized data.

Abstract

A method has been devised which allows to encode the quantized output of a discrete-time memoryless Gaussian source nearly as efficiently as Huffman's optimum variable-length encoding procedure. With respect to the mean code-word length the performance of the two methods typically differs only by 0.1-0.2 bit. The basic idea of the new method is that each code word is made up of two components: the prefix and the kernel. The prefix specifies the length of the kernel and is encoded by means of Huffman's method. Despite the fact that the kernel length may vary from one code word to the other, the code used for the kernel is basically a fixed-length code, because once the prefix has been decoded, the begin of the next code word is known without decoding the kernel. The advantage of the new method as compared to Huffman's method is that only few variable-length codes have to be distinguished so that both encoding and decoding can be accomplished by means of quite simple algorithms requiring only few compare and branch operations and one single addition or subtraction per code word. Areas of application, especially when combining the method with predictive coding, are time series (e.g. the electroencephalogram) and other kind of quantized data.