TY - JOUR
T1 - On Overflow and Underflow Problems in Buffer-Instrumented Variable-Length Coding of Fixed-Rate Memoryless Sources
AU - Farvardin, Nariman
AU - Modestino, James W.
PY - 1986/11
Y1 - 1986/11
N2 - 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 underflow. 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.
AB - 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 underflow. 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.
UR - http://www.scopus.com/inward/record.url?scp=0022810671&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022810671&partnerID=8YFLogxK
U2 - 10.1109/TIT.1986.1057235
DO - 10.1109/TIT.1986.1057235
M3 - Article
AN - SCOPUS:0022810671
SN - 0018-9448
VL - 32
SP - 839
EP - 845
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 6
ER -