New bounds on Huffman codes and design techniques for error-control codes

We obtain two bounds for Huffman codes, an upper bound on data expansion of Huffman codes and an upper bound on the redundancy of Huffman codes. In addition, we investigate two issues of error control codes, the codeword length modification problem for multidimensional delta-set codes and the channel modeling problem for bursty channels.; Data expansion of Huffman codes is a measure of the worst case temporary increase of file size in the data compression process. It has been conjectured that the Huffman data expansion is at most 0.8 bits per symbol. We find a new upper bound on Huffman data expansion that is 4.4% above the conjectured bound, in contrast to the previous best known bound, which is 57% larger than the conjectured bound.; The redundancy of a code is the average codeword length minus the entropy of the source probability distribution. Shannon showed the redundancy of optimal codes is less than 1. Thus the redundancy of Huffman codes is less than 1. Let p₁ be the largest source symbol probability. Gallager obtained a tight upper bound on redundancy of binary Huffman codes for p₁ ≥ 0.5 and a nontight upper bound for p₁ < 0.5. Our new bound on redundancy of binary Huffman codes for p₁ < 0.5 is better than Gallager's except at a set of discrete points, where they are equal.; Error control system designers frequently encounter the codeword length truncation problem because symbol sizes are often fixed but flexible code parameters are wanted. We find sufficient conditions for puncturing multidimensional delta-set codes without reducing the designed distances. Higher rates can be achieved for some code parameters than those of comparable codes with the same decoding complexity.; Channel modeling is critical in system design and evaluation. We propose an error model for bursty channels that applies to error characteristics beyond the few special simple forms of polygeometric functions that most widely used models can represent. We derive closed-form expressions for capacity and statistics of the model. We demonstrate how to parameterize the model and how to evaluate error control block codes based on this model.