Fibonacci Coding. Number system

A positive integer not exceeding 1 million

Original natural number

Fibonacci coding result

Convert selected code to decimal system

We all know how you can encode a number in one or another number system: binary, octal, hexadecimal.In this article I will introduce you to coding based on Fibonacci numbers.

We have already talked about these numbers , and now I just want to remind you this series

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946

By this series, you can also bring any natural number into a set of zeros and ones, as is done for example in the binary system.

We will take the encoding algorithm (or rather its description) from Wikipedia without any changes

"To encode an integer N:

Find the largest Fibonacci number equal to or less than N; subtract this number from N, keeping track of the remainder.

If the number subtracted was the ith Fibonacci number F(i), put a 1 in place i−2 in the code word (counting the left most digit as place 0).

Repeat the previous steps, substituting the remainder for N, until a remainder of 0 is reached.

Place an additional 1 after the rightmost digit in the code word."

But the calculator that encodes on this page is built on a completely different principle.

At least 4 points are not fulfilled.He puts the unit as a marker for ending the word.This is not in my calculator.

As for the algorithm ...

In fact, this is a side effect of the implementation of the algorithm for solving Diophantine equations.I discovered it (effect) and decided to make a calculator.

The calculator has a top limit of one million.In order to understand the structure, the applicability of the code is quite enough.

In addition, the code converts the resulting set of zeros and ones to a decimal system using a binary base.

What is interesting about the built code?

Firstly, it is redundant, even too much.For any number, the Fibonacci code will look like that between the units at least (!) There will be one zero.

On the one hand, this is bad.It will take almost twice as long to transmit such a code than if the encoding was carried out by a binary system.

What is the plus: In that code redundancy allows us to easily detect errors during transmission.This is indispensable for poor communication, when communicating with settlements on different planets.

Messaging in a continuous stream using Fibonacci coding allows real-time (in a stream) correction of errors that have arisen, by the criterion that has already been voiced: there can not be any units in the code nearby.

Encoding an 8-bit ASCII character table with a new code would require 11 bits (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144), but not 256 characters would be placed there, but 287 (2 * 144-1).Given the already "built-in noise immunity" it is not bad to get an extra 31 characters.

Since there are 33 letters in the alphabet, we can encrypt each letter with 7 bits (1,2,3,5,8,13,21).An additional 8 characters are placed in the same size (21 * 2-1-33).We can reduce our alphabet to 31 (assuming that it is its ith one letter) and we get that in 7 bits we put the Russian alphabet and all the numbers.

English is even easier.There are only 23 letters and encoding with a 7-bit code, we fit (not only the English alphabet and all numbers, but also 8 more characters, such as punctuation marks, mathematical signs, etc.).

I even envy a little ...

A few examples