We investigate the redundancy that arises from adding a worst case length c
onstraint to uniquely decodable fixed-to-variable codes over achievable Huf
fman codes. This is in contrast to the traditional metric of the redundancy
over the entropy. We show that the cost for adding constraints on the wors
t case coding length is small, and that the resulting bound is related to t
he Fibonacci numbers.