University of Illinois Urbana-Champaign

Bounds on the Redundancy of Noiseless Source Coding

Blumer, Anselm Cyril

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/71205

Description

Title
Bounds on the Redundancy of Noiseless Source Coding
Author(s)
Blumer, Anselm Cyril
Issue Date
1982
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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,
  • (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 variable-length (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 J-state 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
  • 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
Graduation Semester
1982
Type of Resource
text
Permalink
http://hdl.handle.net/2142/71205

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics