Generalization of Fibonacci Codes to the Non-Binary Case

Abstract

Motivated by expected technological developments in which the basic unit of storage might possibly be $d$ -ary elements, with $d > 2$ , and not just bits, we extend the traditional Fibonacci code to non-binary codes of higher order, and prove their theoretical properties, as follows: (1) these codes are fixed in advance, and therefore do not need to be generated for each new probability distribution, yielding very simple and fast encoding and decoding procedures; (2) the codes are prefix-free: no codeword in the code is the prefix of any other codeword; (3) the codes are complete: if one adjoins any other $d$ -ary string as an additional codeword, the obtained extended set of codewords is not uniquely decipherable anymore, and is therefore not useful as it might lead to ambiguities; and (4) the codes provide robustness against decoding errors: the number of lost codewords in case of an error will be limited. An error is defined as a $d$ -ary digit changing its value, or an insertion of an extraneous $d$ -ary digit, or an erroneous deletion of a $d$ -ary digit. We provide experimental results on the compression performance, illustrating that the compression efficiency of non-binary Fibonacci codes is very close to the savings achieved by the corresponding non-binary Huffman coding of the same order, while providing simplicity and robustness.

Keywords

• Data compression
• Fibonacci codes
• Huffman coding