DIMACS TR: 98-11
Nonexhaustive
Generalized Fibonacci Trees in Unequal Costs Coding Problems
Author: Julia Abrahams
ABSTRACT
In a sequence of generalized Fibonacci trees, the k-th tree has the
(k-c(i))-th tree as its i-th subtree for a nondecreasing sequence of
positive integers c(i), i=1,...,r. For particular initializations, each
tree in the generalized Fibonacci sequence solves a minimax coding problem
related to Varn coding. Specifically, each symbol from a uniformly
distributed source is to be encoded by a string of code symbols associated
with the path through the tree from the root to the leaf associated with
the source symbol, the i-th code symbol costs c(i), and the goal is to
minimize maximum codeword cost.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-11.ps.gz
DIMACS Home Page