The article solves the problem of protecting decimal numbers used in systems of information transmission, processing and storage from unauthorized access with simultaneous correction of single errors in them and detection of error bursts. To protect the decimal number, each of its digits is first converted to a binary-decimal digit, and then, using a special table, into a binarycoded permutation. After that, the digits of the decimal number themselves are mixed. The paper gives estimates of the level of secrecy of decimal numbers encoded in this way. Since each digit of a decimal number can contain one of 10 digits, 10 permutations are required to encode them. To obtain them, at least 4 elements 0, 1, 2, 3 are required. They form 24 permutations, of which 14 are redundant. Specially selected 10 binary-coded permutations out of 24 form a binary-coded permutation code with a minimum code distance equal to 4. This allows correction of any single error and detection of double errors on the set of permutations.
In practice, binary-decimal codes have become widespread, with the help of which information from various sensors is extracted and transmitted, for example, information about the amount of consumed thermal and electrical energy, water and other similar indications. Usually, each binary-decimal digit taken from the sensor is transmitted over a communication channel, essentially a telecommunication system, which includes a buffer memory with an encoder, a communication line, an information display device, and a receiver with a decoder [1]. The communication line can be both wired and mobile, using radio communication. In the latter case, information can be transmitted directly to moving objects, such as cars. 1
However, the transmitted information in some cases must be protected from unauthorized access. To do this, the binary-decimal digits of each decimal number are uniformly mixed using the appropriate tables. At the receiving end, these tables allow to restore the original information. They are, in essence, cipher keys. Moreover, the secrecy of the mixed each binary-decimal place can be significantly increased by additional mixing of the bits of binary-decimal numbers.
However, in addition to protecting against unauthorized access, it is often required to further increase the noise immunity of the transmitted binary-decimal numbers.
Binary-decimal coding protects to a certain extent the transmitted or stored decimal digits from interference due to the redundancy of a binary-decimal code containing sixteen four-bit binary-decimal code words. However, the level of protection against interference is still low, although for a number of practical cases it may be acceptable. Therefore, it became necessary to increase it.
It was proposed to solve this problem in [
To assess the noise immunity of such codes, it was proposed to use formulas for the probabilities of transition of code combinations into classes of correct combinations, allowed erroneous combinations that are not detected and forbidden combinations that can be detected [5]. According to the results of the analysis, it was concluded that the use of equilibrium codes provides the requirements of the reliability class I1 of the international standard IEC 870-5-1-95 in the whole range of failure levels of one bit of information [1]. At the same time, the secrecy of information was increased, since there was no reliable test for unravelling their values, because statistics for decimal digits presented in the form of equilibrium code combinations does not help well, unlike text information, for the decoding of which the statistical probabilities of letters play an essential role.
However, errors in the transmission of decimal digits by equilibrium code combinations are difficult to eliminate, and the implementation of ARQ in mobile communications is sometimes difficult. Therefore, the task arose of developing a telecommunication system that would not only detect errors, but also correct them, using inseparable codes, in order to hide the true value of decimal digits during transmission.
The task of this work is to increase the noise immunity of transmitted binary-decimal digits, accompanied by error correction, with sufficient protection against unauthorized access.
For this, it is proposed to enhance the noise immunity of binary-decimal information by using inseparable codes on permutations, since, on the one hand, they allow error detection and correction, and on the other hand, they can hide the true information deeper.
Permutations are widespread in mathematics. Permutations are used in abstract algebra, and they are also used to solve combinatorial optimization problems, for example, the travelling salesman problem [6-8].
In addition to solving mathematical problems,
permutations are used in practical problems of
protecting information from unauthorized access
[
Any finite sequence of distinct elements of length n is a permutation. While any symbols can be elements of permutations, most often numbers are used as them. For example, a sequence of four different digits 0123 would be a permutation of length n = 4. At the same time, a sequence of 1011 of length n = 4 would not be a permutation, since it only consists of two different repeating elements 0 and 1.
The set of n! permutations of length n forms a permutation code. The difference n·log2n - log2n! forms redundant information of this code, which with increasing of n can reach a significant value, determining the high noise immunity of codes on permutations. In addition, permutations do not have repeating elements and, therefore, obtaining their statistics is difficult. It can be obtained, with high effort, only on a large number of permutations, which greatly complicates the deciphering of information hidden in the permutations.
In the tasks of anti-jamming coding and information protection the elements of permutations are represented in binary form. Such their representation will be called binary-coded. The number of binary bits in binary-coded permutations is defined as the whole logarithm of the permutation elements number n:
m=⌈ log2n ⌉ (1) 10 different binary-coded permutations are required to encode binary-decimal information. Therefore, the minimum value of n that can provide the required number of permutations will be 4, since 4 × 3 × 2 = 24 > 10. Of these 24 permutations, 10 permutations are used to encode 10 binary-decimal digits. Each of them encodes one of the digits, for example, permutation 0123 is used to encode 0. The remaining 14 possible permutations are redundant. One of the possible variants of representation of binary-decimal digits by permutations is shown in Table 1. Together, binary-decimal digits in Table 1 form a binarydecimal code (2-10 code).
The number of encoding variants of binarydecimal digits by permutations will be equal to the number of combinations 10 out of 24, each of which can be specified by the corresponding table, like Table 1. Each of these variants, in turn, can be represented by one of 10! permutations encoding 10 digits, each of which can also be represented in the form of a table. Each of these tables can act as a cipher key, consisting of 10!·C1024 permutations for one decimal place.
In addition, the decimal digits, the number of which is equal to k, can also be shuffled in various ways during their transmission. Accordingly, the total number of permutation variants that can be used to encrypt the decimal permutation code will be equal to M = k!·10!· ·C1024. If k, for example, equals 10, then the number of variants of the cipher M = 10!·10· ·C1024= 2.58·1019. This is a fairly large number of brute force options required to break the cipher. It should be borne in mind that the statistics of the numbers in the permutation cipher is poorly expressed, which greatly complicates its disclosure. The dependence of the M value, which characterizes the complexity of 1 3 5 7 9 3.2. Evaluation immunity of permutations of the the code noise on
In addition to secrecy, permutations can significantly increase the noise immunity of the binary-decimal code. This is due to the fact that the binary-coded representation of such permutations according to formula (1) will contain four digits of length m = 2. Permutations P of length n = 4 and their binary-coded representation BCP are presented in Table 3.
Each permutation differs from others by at least two elements, and therefore, the minimum code distance in a binary code on permutations is 2. Such a code distance allows detecting in binarycoded permutations all single errors, as well as all errors of odd multiplicity 1, 3, 5, ...
Increasing the code distance will improve the noise immunity of binary-coded permutations. To achieve this, out of all 24 permutations of length n = 4, 10 allowed permutations should be selected, as shown in Table 4, which differ from each other by three elements, and thereby ensure the minimum code distance between their binary representations equal to 4. This allows not only detecting double errors in binary-coded permutations, but also correcting any single error in them.
The noise immunity of a code on binary-coded permutations can be estimated using a characteristic called the fraction of detected errors D [5, 18]. It shows the probability with which any error translates the permutation into a forbidden combination that can be detected. The D value is defined as the ratio of the number of forbidden combinations Zf to the total number of combinations D = Zf / nn = 246 / 256 = 0.96.
A transmission error can translate a binarycoded permutation into either a forbidden combination that is not a permutation, or into one of the permutations. In the case where an error converts a permutation to a non-permutation combination, it can be easily detected as follows.
First, since all permutations contain the same elements, arranged in a different order, the sum of the binary numbers encoding these elements must remain constant. It forms a checksum, the same for all permutations, equal to
S = n·(n - 1) / 2 . (2)
It can be used to detect erroneous combinations, the checksum of which does not coincide with the value determined by the formula (2) [17]. For the considered code on permutations, such a checksum is equal to S = 4·(4 - 1) / 2 = 6.
Example 1. On the receiving side, during permutation transmitting, a sequence of elements 1231 was received, which is not a permutation. Counting the sum of these elements gives the result 1 + 2 + 3 + 1 = 7. This number does not coincide with the checksum value obtained above for the code on permutations S = 6. This means that the resulting sequence is not a permutation and contains an error.
Second, the appearance of two or more identical elements in a permutation, during its transmission or storage obviously transforms it into a combination that is not a permutation. Then, by comparing the elements of the transmitted combinations on the receiving side, it is possible to establish whether they are permutations or not.
Example 2. On the receiving side, a sequence of elements 1231 was obtained. As a result of comparing the first element of this sequence with all other elements, it is found that it coincides with the fourth element: 1 23 1. Therefore, the resulting sequence is not a permutation and contains an error. 4.1.
In the case when a double error occurs during the transmission of a binary-coded permutation, it can translate into one of the 14 forbidden permutations. The fact that the allowed permutation can translate solely into the forbidden permutation is explained by using for the encoding of numerical information only permutations with the minimum code distance 4. Such an error can be detected on the receiving side by comparing the received permutation with all allowed permutations given in Table. 4. If a match of the received permutation with one of the 10 allowed permutations is found, then the decision is made that it is correct; otherwise it is forbidden and contains a double error.
Example 3. Permutation 0123 (00 01 10 11) after the interference translated into permutation 1023 (01 00 10 11). Comparing this permutation with all allowed permutations presented in Table 4, shows no coincidence with any of them and, accordingly, indicates that it is forbidden. Therefore, it contains a double error. Indeed, in the permutation 0123 0 transformed into to 1, and 1 into 0. 4.2.
Comparing a binary-coded permutation containing an error in any element with all 10 allowed permutations allows a single error to be corrected. All permutations except one will differ from the erroneous sequence by more than one element. Any permitted permutation that differs from a permutation with an error in one element will be considered its corrected value.
Example 4. On the receiving side, a sequence of elements 1231 was received. By calculating the checksum and comparing the elements with each other, it is found that this sequence is not a permutation, which means that it contains an error. Since the minimum coding distance for permutations of Table 4 is 4, it is possible to correct a single error. To correct it, the erroneous sequence 1231 is compared with all allowed permutations in Table 4. As a result of this comparison, it is found that among the allowed permutations only one permutation 0231 differs from the obtained sequence by one element. This permutation is recorded as the correct value of the received sequence: 1231 → 0231.
However, the use of specially selected permutations for detecting double errors and correcting single errors reduces the level of secrecy of information, since the opponent can start breaking the cipher just from the analysis of these permutations. Therefore, it is necessary to weigh what is more important for the transmission of information, its noise immunity or secrecy, and accordingly choose the method of protecting decimal digits from interference.
The error detection and correction algorithm contains the following steps.
Step 1. In the received binary combination of 8 bits, the sum of its permutation elements, each of which consists of 2 binary digits, is calculated. If the calculated value equals 6, then it is considered as one of 24 binary-coded permutations, which may be correct or incorrect.
Step 2. The received permutation is compared with 10 allowed binary-coded permutations representing decimal digits. In the case when there is allowed permutation that coincides with the received permutation, then it is written as correct. If it differs from all the allowed permutations by the value of two or more elements, then it is erroneous and can be corrected by ARQ.
Step 3. If the calculated value doesn’t equal 6, then the received binary combination is an erroneous sequence that is not a permutation. In this case, some of its elements have the same value. If the received sequence differs from one of the 10 allowed permutations in only one element, then this one permutation will be the corrected permutation. In other case the error can only be corrected by ARQ.
The inseparable code on permutations proposed in the work for encoding digits allows solving the problem of digital information transmission secrecy, and at the same time ensures its noise immunity. Wherein, the secrecy of information can reach acceptable values for many applications due to the special properties of the permutations, which make it possible to hide the statistics of the transmitted decimal digits.
Along with the secrecy the permutations can effectively solve the problem of increasing the noise immunity of the transmitted digits. They allow detection of errors bursts and fix single errors. It is also important that the considered methods of detecting and correcting errors in permutations, used to encode decimal digits, are quite simple to implement.