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.
DIMACS Home Page