On the Proportion of Digits in Redundant Numeration Systems
Abstract
In the standard binary numeration system, an n-bit integer N is uniquely represented as the sum of powers of 2. Instead of powers of 2's, if Fibonacci numbers are used, then an alternate numeration system (viz. Zeckendorf [14]) occurs in which an integer N may have more than one representative. Representations of this type have important advantages. For example, in a CD-ROM, three or more consecutive 1's cannot be reliably read (Davies [4]). The question posed and answered in this paper is: To what extent does redundancy occur in redundant numeration systems? The question has important consequences for both the efficiency of number representations and the transmission of data. We analyze redundancy in two ways 1) the number of distinct representative n-tuples for some given n, and 2) the proportion of digits used in non-redundant representatives.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 08, 1996
- Accession Number
- ADA620836
Entities
People
- Jon T. Butler
- Tsutomu Sasao
Organizations
- Naval Postgraduate School