We can use the F_N+1 Fibonacci codewords that are exactly N cells long as a numerical code; that is, we can use them to represent integers. Individual codewords in the Fibonacci code can be assigned numerical values, assigning each codeword of length exactly N cells a unique value between zero and F_N+1-1. This can be done by treating the codewords as belonging to a weighted code, with each cell "weight" being one of the Fibonacci numbers. The value of a particular Fibonacci codeword is obtained by simply adding together the numerical weights of any cell containing a narrow "1" element, subject to the rules:

1. The cell weights begin with F₀ for the left-most cell in the codeword, proceeding to F₁, F₂, F₃, and so on moving towards the right.
2. Each zero symbol ("0") uses up two cells.

It is important to note that the Fibonacci weights are associated with each cell in the codeword, not with each element.

As a sample codeword, consider the code "01011", of length 7 cells. Then:

One can prove that, using this weighting method, an N-cell long code generates exactly the integers from 0 through F_N+1-1; that is, F_N+1 distinct integers, with none missing, and no duplicates. This follows from the method used to generate all the codes of length N.

The figure above illustrates the simple conversion algorithm from a Fibonacci Code to its numerical value: simply line up the code with the Fibonacci cell weights, and add up the Fibonacci values of each cell containing a "1" (narrow element). Ignore all pairs of cells containing a "0" (wide element).

The steps in the conversion of the integer value 14 to a 7-cell Fibonacci code are shown below. The initial "Residue" is set to 14, the number to convert. The conversion starts with "F₆" because we have selected a 7-cell long code. If the residue is not zero at the end of the process, the code length selected was not long enough to hold the number. Following the above algorithm:

Note that in most "weighted" numerical codes, the code representing a given value is the same, except for leading zeros, regardless of the number of places in the code. For example, in decimal notation, the two-digit integer "34" becomes "034" when written with three digits, "0034" when written with four digits, and so on. In each case, the final two digits are the same.

We have chosen to write the Fibonacci code "backwards", in the sense that the Least Significant Element is on the left, so in the Fibonacci code, larger codes of the same value add trailing zeros. The Fibonacci code has the curious property that the same value is represented by one code when the overall length of the code in cells is even, and a different code when the overall length is odd. Thus, the integer "2" is represented in odd-cell-length codes by the elements "111" (or "1110" or "11100" or "111000", and so on), but in even-cell-length codes, it's represented by "101" (or "1010" or "10100" or "101000", etc.). Note that in the codes just above, the elements of the code are given, without showing that the "0" element is twice as wide in cells.

Similarly, suppose we were to convert the number that was converted just above, 14, into an 8-cell code instead of a 7-cell code. The result then would have been 01001 instead of 01011. These two codes have the same number of elements, but the former has one more cell than the latter, because it has one more zero than before. The conversion is left as an exercise for the reader (but remember to start with F₇ = 13).

Click here to return to Larry Krakauer's home page