The problem of constructing quasi equidistant and reflected binary Gray code sequences and code in a mixed factorial, Fibonacci and binomial numeration systems is considered in the article. Some combinatorial constructions and machine algorithms synthesis sequences, based on the method of directed enumeration are offered. For selected parameters of sequences all quasi equidistant (for individual cases - reflected) codes with Hamming distance equal to 1 are found.
Coding theory is one of the most important areas of modern applied mathematics. Beginning of the formation of mathematical coding theory dates back to 1948, when it was published a famous article by Claude Shannon [1]. The growth of codes originally was stimulated by tasks of communication. Later constructed codes found many other applications. Now codes are using to protect data in a computer memory, cryptography, data compression, etc.
The work is devoted to a rather small, but extremely important for applications subset of so-called quasi-equidistant and reflected codes. The class of quasi equidistant codes are sequences of uniform (i.e., containing the same number of bits) of binary code combinations in which any adjacent (neighboring) code sets (words) are at the same Hamming d distance equal to a fixed number of natural numbers (i.e. d = 1, 2, …) [2]. Equidistant sets include such codes in which any two words (code combinations) are at the same distance d [3].
Finally, we shall refer to the reflected subset quasi equidistant codes with distance d =1, the formation of which is based on the principle of mirror reflection? [4]. But if we restrict ourselves to only one mirror, the code sequence will contain the original sequence, after which is the same sequence just re-written in reverse order, which is unacceptable, since it leads to code repetition. The elimination of repetition can be provided by initial expansion of the number of digits combinations. The essence of the "mirror" reflection of the expansion is explained below as an example of canonical reflected Gray codes and in other sections of this article.
The main objective of this study is to develop algorithms for constructing quasiequidistant and reflected binary Gray codes as well as code sequences in a mixed factorial, Fibonacci and binomial bases. The method of direct enumeration is the base of algorithms of computer sequences synthesis. 2
The history of discrete mathematics and computer science is directly related to the development and introduction of newer principles of representation and encoding digital information, which are based on the numeration system of numbers. By a numeration system we understand the way of image sets of numbers using a limited set of characters that form its alphabet, in which the characters (elements of the alphabet) are located in the established order, occupying a certain positions [5]. Any numeration system should be composed of a finite set of non-negative numbers — a range that it encodes. It always includes the number 0 and then follows the natural numbers starting with 1 [6].
There are various numeration system (as well as methods for their classification), whose number is constantly growing. All systems can be divided into the following main classes: positional, not positional and mixed. In the positional numeration systems the same numeric characters (digit) has different meanings in its description depending on the location (level) where it is resides.
By positional numeration system is generally understood the p numeration system,
which is defined by an integer p 1 — is called a base of numeration system.
Unsigned integer N in p numeration system is represented as a finite linear
combination of powers of
digits of the number. The simplest examples of positioning systems (
In no positional numeration systems the value which indicated by the digit does not depend on the position in a number. At the same time the system may impose restrictions on the position of numbers, for example, that they are in descending order. The Roman and many other systems belong to not positional systems.
The mixed numeration system is a generalization of the p system, and often refers to the positional numeration systems. The base of mixed numeration system is an increasing sequence of numbers pk , k 1, 2, , and each N number is presented like linear combination: n N k pk ,
k1 there are some restrictions exist for k coefficient.
One of the known examples of the mixed system is a factorial numeration system, in which the bases are the sequence of factorials pk k! . Another commonly used Fibonacci numeration system is a system that is based on Fibonacci numbers. The Binomial system in the form in which it is presented in the relevant section of this article, we will also include to a mixed numeration system.
A positive integer is depicted in an arbitrary numeration system as a sequence of symbols N nn1k 21, where N - the number representation in this numeration system, besides each k symbol takes rk bit in general case (if binary alphabet is using).
Note the following general characteristics of quasi equidistant codes with
Hamming distance d 1 . Let’s agree each code sequence starts with zero code. And as
result of this agreement the following code after the zero code should be placed with
weights 1 and 2, and Further weight codes must alternate even (E) — odd (O) under
the scheme
(
0 (ne no ) 1 ,
Scheme (
Statement 1. Inequality is a necessary (but not always sufficient) condition for the construction of quasi equidistant codes. 3
Classic Gray codes [7] may be called canonical, since for arbitrary length sequence of combinations are not only quasi equidistant, but also reflected. Let’s G(n) sequence of n-bites classical Gray codes. To construct (n 1) bites reflected Gray Codes, let’s us note as Grc (n 1) codes, it is just enough to prefix for each source code G(n) the 0 digit and 1 to the left of code group G R (n) constructed by reflected (reflex or reverse) mirror of G(n) sequence, i.e.
Grc (n 1) 0G(n) ||1G R (n) ,
(
According to (
The first six variants of sequences in the table constructed of canonical option 1 as a result of a variety column rearrangement saving the Hamming distance d 1 of related code combinations. Variants 7-12 are formed as a result of inverse none zero rearrangements of code combinations from appropriate variants 1-6.
The first six variants of sequences in the table constructed of canonical option 1 as
a result of a variety column rearrangement saving the Hamming distance d 1 of
related code combinations. Variants 7-12 are formed as a result of inverse none zero
rearrangements of code combinations from appropriate variants 1-6. As follows from
Tab. 1 the only variants 1 (canonical) and 6 of Gray codes belong to a set of three
bites reflected codes. At the same time each three bite sequence by (
Statement 2. All amounts L(оGт ) (n) of reflected Gray codes of n number of digits is defined by
n, if n 2; L(rGc) (n 1)
2n!, if n 3.
The integer positive number N in factorial number of numeration system can be
represented as
(
k 1
where k 1, 2,, n; 0 k k. Extended form of (
N n n! n1 (n 1)! 2 2! 1 1! ,
Statement (
Let’s mark Ф(k ) sequence of n bite factorial codes. In the case where number of digits of code combination from code set Ф(k ) less than k , it is prefixed with required amount of zeros. Let’s Фd (k ) sequence of quasi equidistant k bite factorial codes with Hamming distances among related combinations equal to d . Based on data from Tab. 2 it is easy to create (Tab. 3) sequences Ф1(k ) for k 1 (singular case), and also k 2 and k 3 created by columns rearrangement of base sequences (variant 1).
Let’s discuss the problem of synthesis of quasi equidistant factorial codes with a
number of digits n 4, 7 . So taking the data from Tab. 3 let’s construct a preliminary
weights distribution of n bite code combinations resulting in Tab. 4. The amount of
codes with even and odd weights in current table for all variants n are satisfying
inequality (
At that from 5 odd elements (O) of sequence (
The symbolic form of the tree of code combination sequence Ф1(
Let’s go to validation to the whole amount of trees variants Ф1(
There are group of nine odd (O) code combinations which contains four codes with
weight equal to 1 and five with weight equal to 3 in the schema (
In correspondence with a schema of sixth tree variant (Tab. 5) the first two code sequences, which will be called layers of tree branch, choose 0000 and 0001 codes.
We could choose 0010 layer instead of 0001. The third layer to choose would be a
code with weight equal to 2, the one which consist of 0001 code with Hamming
distance equal to 1. Suitable ones are codes in columns with 1, 2 and 4 numbers of Tab.
6. The code with smaller number will be considered as a base, the rest – alternative.
Keep moving the same way with codes choosing for Ф1(
The ninth layer of tree under synthesis should be a code with weight equal to 2, moreover it must reside from previous code with distance equal to 1.
But there is no such a code, which were not used in Tab. 6. In order to cope with
this deadlock we will do the following. We will go up through columns of and will do
a substitution in this row with a nearest alternative code located from the right of it. In
this case we should substitute base code 0011 with alternative code 0101 and
afterwards continue the synthesis procedure for Ф1(
Fibonacci codes are generalized concept of classical binary code [9]. Any nonnegative integer N 0, 1, 2, … can be exclusively represented by a numerical Fibonacci function
N nFn n1Fn1 k Fk 2F2 1F1 .
Besides the sequence { k } in (
For example, [10],
01111011001 10011100001 10100100001 .
The codes which are underlined in example (
Using the folding operation it is easy to come to a representational algorithm of
multidigit binary Fibonacci numbers. As an example let’s consider a method of
representation of natural sequence of decimal numbers (including zero) by four digits
numbers of Fibonacci codes. We need to agree to label code numbers from right to
left assuming the smaller (the very right) number the correspond to number 1, then
number 2 and so on. We choose such a coding method of first three decimal numbers
0, 1 and 2:
(
A conversion from decimal number k10 to (k 1)10 number in Fibonacci codes
(label them as Fk and Fk 1 correspondingly) will be performed using a rule: if there is
0 in a smaller position Fk then it is substituted with 1 in Fk 1 code. If there is 1 in a
smaller position Fk then this 1 goes to the second position and writes as 0 in a
smaller position. This rule is using in system (
Let’s represent number 310 with Fibonacci code. But before we go, following the rule described above we will get code 310 00011 which by folding operation would be represented in its minimal form
According to statements (
Statement 4. A set of k bite Fibonacci numbers of the same length is defined by recurrent correlation
F (k ) 10 || F (k 2) . 310 0100. (13) (14)
The proving of just formulated statement can be easily performed by a method of direct verification. In the right part of (14) the F (k 2) set is consisted of (k 2) position numbers.
From this it is followed that if any subset of Fibonacci numbers, included in F (k 2) , contain digits the number of digits of whose are less than k 2 then those numbers are prefixed with required amount of zeros. Algorithm (14) is right for any value k 2 . Indeed, if k 2 then
F (
As long as F (0) set is empty then F (
There are Fibonacci codes for limited sequence of decimal numbers calculated
using recurrent formula considering initial condition (
You can see values n in column F of Tab. 9, equal to number of codes which can be created by a fixed number of binary positions. For example, F 3 means the four bite combinations, which contain 1 in its older position, can be created three Fibonacci codes. Writing down the values from F column we will get sequence 1, 1, 2, 3, 5, 8, 13,… which is classical sequence of Fibonacci numbers.
Now go to estimation of variants of quasi equidistant Fibonacci code trees. For this purpose based on data from Tab. 9 let’s create a preliminary table of distribution of code combinations weights, included in F (k ) , k 4, 7 , (Tab. 10). By analysis of data from Tab. 10 we have the following conclusion. Quasi equidistant sequences of four digit Fibonacci numbers are end up with code combinations with weight of 1, five or six number of digits with weight of 2 and seven numbers of digits with odd weight equal to 1 or 3. 0 1 2 3 4 5 6 7 8 9 10 11 12 k10
Fk
F
It is not that complicated to perform a calculation LF (k ) of quantity of variants for quasi equidistant Fibonacci sequence F1(k ) trees.
The result of this calculation for chosen k parameters is shown in Tab. 11. For reflected Fibonacci codes it is right the following
Statement 5. A set of even k bite reflected Fibonacci codes is defined by recurrent correlation
Фот (k ) 00F1(k 2) 10F1R (k 2) , where F1R (k ) sequence is inversed to F1(k ) , i.e. the sequence of quasi equidistant codes F1(k ) written in reverse order.
As an example (Tab. 12) of calculated using a computer a branch of one tree
F1(
There are many known methods for binomial codes creation and based on them – binomial sequences [11]. We will consider two ways of even binomial codes synthesis in this unit. First of them we will call an “algorithm A. Borysenko”, and the second one an “algorithm of A. Beletsky”, which is called as alternative algorithm here in after.
The whole idea of first algorithm of uneven binary binomial codes, which correlate to algorithm of full summarized binomial arithmetic, is described in [12], page 124. Of course any uneven binary code can be converted to even code of n number of digits (length). For this purpose it is just enough to prefix the code combination such amount of zeros so the common number of digits became equal to n .
To construct algorithms of binomial arithmetic by Borysenko it is enough to define two parameters k and n, the first one defines the maximal amount of units in codes, the second one by value r n 1 , defines the maximal length of uneven binomial number. A decimal zero in Borysenko’s binomial code is written down as l n k of zeros, the range P of binomial numbers is defined by formula Fmax P 1 . Here are a number of examples of binomial numbers Bx (algorithm A. Borysenko), creation whose correspond to decimal value x (Tab. 13).
Statement 6. Direct and inverse binomial sequences are linked with correlation B(n, k ) BR (n, n k ) , where BR (n, n k ) sequence of binomial codes, which first of all is written in reverse order to codes in B(n, k ) and secondly each position of BR (n, n k ) forms by result of inversion (i.e. substitution of 0 to 1 and vice versa) of corresponding positions B(n, k ) .
Let’s find out a possibility of quasi equidistant codes B1(n, k ) creation based on
set of binomial numbers B(n, k ) . For this purpose using the data from Tab. 13 lets
create a table of code combination weights distribution (Tab. 14) included in B(n, k )
set. According to data from Tab. 14 and also values ne and no comparison, received
for many other parameters n and k , we can conclude the inequality (
k Clk l k (k 1)(k 1 l)
, l! - binomial coefficient which is equal to number of k and l combinations. The coefficients k are defined by a correlation k 0, k / 2 , in which x means rounding of number x to the nearest integer above.
Series (15) is presented in form of binary coefficients k for each of who’s the limited number of positions equal to number of digits and required for binary value k / 2 representation is assigned.
Coefficient unambiguously defines the value of monomial kCkk , as it is shown in Tab. 15 (in which for example purpose the value k 7 is chosen).
1 7 7 N 4 5 6 7 8 Even Odd In all Sign
As an example check Tab. 18, where results of quasi equidistant codes creation by
a method of direct enumeration based on one of trees for B(
A feature of alternative binomial codes is that they do not allow creating quasi
equidistant codes in a full manner as it is visible from Tab. 18. In particular, for all
sequences shown in Tab. 18, the latest codes (highlighted) reside from previous codes
with a Hamming distance equal 3 but not 1, as it is required for sequence B1(
The main result of this research is formation of generalized conditions for quasi equidistant and reflected codes existence which are produced by even consistent binary code combinations in a mixed numeration systems. Except of Gray codes the Fibonacci, factorial and binomial codes with Hamming distance between related code combinations equal to 1, are also included in a set of such codes. The main method for synthesis of quasi equidistant codes is a method of computer direct enumeration. The results of this research can be easily generalized and applied for cases where Hamming distance is more than 1.