Negafibonacci coding

1

In mathematics, negafibonacci coding is a universal code which encodes nonzero integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end.

Encoding method

The following steps describe how to encode a nonzero integer x. Note that f denotes the Negafibonacci sequence. If x is negative, compute the greatest even negative integer n such that the sum of the even negative terms of the Negafibonacci sequence from 0 to n with a step of -2, is less than or equal to x: To decode an encoded binary word, remove the leftmost 1 from the binary word, since it is used only to denote the end of the encoded number. Then assign the remaining bits the values of the Negafibonacci sequence from -1 (1, −1, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

Negafibonacci representation

Negafibonacci coding is closely related to negafibonacci representation, a positional numeral system sometimes used by mathematicians. The negafibonacci code for a particular nonzero integer is exactly that of the integer's negafibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end. The negafibonacci code for all negative numbers has an odd number of digits, while those of all positive numbers have an even number of digits.

Table

The code for the integers from −11 to 11 is given below.

This article is derived from Wikipedia and licensed under CC BY-SA 4.0. View the original article.

Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.
Bliptext is not affiliated with or endorsed by Wikipedia or the Wikimedia Foundation.

Edit article