DIMACS TR: 98-11

Nonexhaustive Generalized Fibonacci Trees in Unequal Costs Coding Problems

Author: Julia Abrahams


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