Files in this item
Files  Description  Format 

application/pdf 8302809.pdf (2MB)  (no description provided) 
Description
Title:  Bounds on the Redundancy of Noiseless Source Coding 
Author(s):  Blumer, Anselm Cyril 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  The Renyi redundancy, R(,s)(p,w), is the difference between the exponentially weighted average codeword length, (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) is the best possible. and the Renyi entropy, (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) (Here s > 0 is a parameter, p = (p(,1),p(,2),...,p(,m)), and w = (w(,1),w(,2),...,w(,m)), where p(,i) is the probability that the i('th) codeword, consisting of w(,i) bits, is used.) As s (>) 0('+) this approaches the usual redundancy. Huffman's algorithm generalizes in a natural way to the s > 0 case. Let R(,s)(p) be the Renyi redundancy of the Huffman code for p and s. The main result of Chapter II is a technique for computing bounds L(,s)(p) and U(,s)(p), satisfying 0 (LESSTHEQ) L(,s)(p) (LESSTHEQ) R(,s)(p) (LESSTHEQ) U(,s)(p) < 1. In the case of block to variablelength (BV) coding of a binary memoryless source, these bounds are shown to be asymptotically equal as the block length increases, generalizing a result mentioned by Krichevskii (1966). Chapter III treats the problem of minimizing the oridinary (s = 0) redundancy when p is not entirely known. Let p be a probability vector containing the probabilities of blocks of length n from some Jstate unifilar (Markov) source with aphabet size A. Let P denote the class of such probability vectors, and let W denote the class of uniquely decodable codes with A('n) codewords. The minimax redundancy is (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) The main result of Chapter III is a technique for generating a sequence of BV codes for which the minimax redundancy is bounded above by 
Issue Date:  1982 
Type:  Text 
Description:  59 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1982. 
URI:  http://hdl.handle.net/2142/71205 
Other Identifier(s):  (UMI)AAI8302809 
Date Available in IDEALS:  20141216 
Date Deposited:  1982 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois