| Positive integer no more than 1 million |
|
|
| Original natural number |
| Result of encoding into Fibonacci code |
| Translation of the calculated code into the decimal system |
We all know how to encode a number into one or another number system: binary, octal, hexadecimal. In this article I will introduce you to coding based on Fibonacci numbers.
These numbers have already been mentioned in the material calculation of an arbitrary number of the Fibonacci series online and now I just want to remind you of 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 a binary system.
Coding algorithm (or rather its description) we will take 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 by tracking the remainder.
- If the subtracted number was the i-th Fibonacci number F(i), put 1 instead of i - 2 in the codeword (counting the leftmost digit as the place 0).
- Repeat the previous steps, replacing the remainder with N until the remainder of 0 is reached.
- Put another 1 after the rightmost digit in the codeword."
But the calculator that performs coding on this page is built on a completely different principle.
At least point 4 is not fulfilled. He puts one as a marker of the end of the word. This is not in my calculator.
As for the algorithm...
In fact, this is a side effect of implementing the solution algorithm a partial solution of a diophantine equation with several unknowns. I discovered it (the effect) and decided to make a calculator.
The calculator has a top limit of one million. In order to understand the structure and applicability of the code, this is quite enough.
In addition, the code converts the resulting set of zeros and ones into a decimal system based on a binary base.
What is interesting about the built code?
Firstly, it is redundant, even too much. For any number, the Fibonacci code will have the form that between 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 as if the encoding were carried out by a binary system.
What is the plus: The redundancy of the code allows us to easily detect errors during transmission. This is indispensable in case of poor communication, when communicating with settlements on various planets.
The transmission of messages in a continuous stream with the help of Fibonacci coding, allows you to correct errors in real time (in the stream), according to the criterion that has already been announced: there cannot be standing units in the code.
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 fit there, but 287 (2 * 144-1). Taking into account the already "built-in noise immunity", it's 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 (21*2-1-33) are placed in the same size. We can reduce our alphabet to 31 (assuming that e-e, i-th is one letter) and we get that we have placed the Russian alphabet and all the numbers in 7 bits.
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 the numbers, but also 8 more characters, for example punctuation marks, mathematical signs, etc.).
I'm even a little jealous...
Some examples
|
Original natural number
|
 |
|
The result of encoding into the Fibonacci code
|
 |
|
Translation of the calculated code into the decimal system
|
 |
|
Original natural number
|
 |
|
The result of encoding into the Fibonacci code
|
 |
|
Translation of the calculated code into the decimal system
|
 |