RU2319199C2 - Universal method for transmitting information with controllable parameters - Google Patents

Abstract

FIELD: engineering of devices for interference-resistant transmission of information through communication channels.

SUBSTANCE: method for transmitting information with controllable parameters includes determining information exchange conditions and quality of channel prior to beginning the transmission of information, selecting optimal parameters n, k and m of stochastic q-based (n,k,q,m)-code on basis of original binary (n,k)-code with l-interleaving (q=2^l) and transmission of m code blocks with identical values of information section, information is encoded using selected q-based code, direct stochastic transformation of q-based symbols is performed prior to transmission into the channel, during receipt, reverse stochastic transformation of q-based symbols is performed, correctly received q-based symbols are localized in m code blocks, trustworthiness of localized symbols is estimated, non-localized and non-trustworthy q-based symbols are corrected in m code blocks and trustworthy q-based symbols are accumulated for output to user after processing of m code blocks.

EFFECT: increased effective speed of information transmission.

13 cl

Description

The invention relates to technical means of noise-resistant transmission over communication channels and networks and can be used in various types of channels and networks.

Known methods for transmitting information over communication channels using error-correcting cyclic codes with error detection in the protocols of the data transmission channel (COP), in which the transmitted information is encoded in a cyclic code, received in the form of blocks of a cyclic code, checked for distortion, distorted blocks are retransmitted by feedback signal [1]. These methods have the following main disadvantages:

- with a decrease in the quality of the discrete communication channel, transmission becomes impossible, since a large number of received blocks are distorted, and the efficiency "loops",

- the error detection mode of cyclic codes does not provide an effective transmission rate close to the bandwidth of the communication channel.

Known methods for transmitting information using algebraic codes with error correction (Hamming codes, Bowes-Chowdhury-Hawkingham, Reed-Solomon, etc.) [2].

These methods have the following disadvantages:

- algebraic codes in the error correction mode turn out to be very sensitive to the error multiplicity, which leads to a large and uncontrolled probability of decoding errors in channels with grouping errors, which takes place in real communication channels;

- coding and especially decoding of known codes has a relatively complicated implementation, especially in the case of a software implementation.

A known method of adaptive transmission of information over duplex communication channels [3], which provides stable transmission of information with a maximum transmission rate for the current state of the channel. The disadvantage of this method is its use only in duplex communication channels and the inability to provide an arbitrarily low probability of error in the transmitted information within a specific device.

The aim of the invention is the universalization of the task of transmitting information within one set of operations of the method, expanding the capabilities of transmission over any communication channels and providing guaranteed parameters (probability-time characteristics of the exchange), as well as ensuring the creation of universal equipment for a wide range of types and quality of communication channels that can be configured under the conditions of use and the achieved opportunities.

In this case it must be ensured a stable exchange of information on a channel not known prior to the quality parameters to achieving effective transmission rate close to the capacity of the communication channel with guaranteed in any channel reliability, the estimated probability of error information F issued by the consumer _oui ≤R _Tp where R _Tr - the required upper limit of the probability of error. Moreover, this boundary can change during the operation of data transmission equipment for various modes or when transmitting different types of information.

When solving the problem of creating a universal method for transmitting information, three problems arise, arising from different ones, proceeding from the universality of the method, the conditions for applying the method, and the problem.

Firstly, in duplex channels of relatively high quality, it is necessary to achieve any predetermined reliability without reducing the effective (relative) transmission speed, which should not be significantly inferior to the bandwidth of the communication channel.

Secondly, to ensure any predetermined reliability of message delivery via a simplex (without feedback) channel, it is necessary to have high noise immunity while maintaining the required reliability.

Thirdly, such a method should not restrain its application at technically mastered high information transfer speeds, that is, be quick-acting (as simple as possible to implement).

To achieve the objective of the invention, stochastic (n, k, q, m) codes are used, where n, k are the parameters of the source binary code, q is the base of the code, m is the number of repetitions of the code block with the same information part (copies of code blocks), reduced to the use of ensembles of codes and ciphers, which ensure guaranteed reliability when performing localization, complicating processing with accurate calculation of outcome probabilities, overlapping the entire channel quality range in duplex and simplex modes to achieve optimal cuts tatov.

Thus, to achieve this goal, three ideas are used:

- the use of random transformations that introduce an element of randomness into a process that reduces the transmission process to the use of all possible signals or to an ensemble of codes and ciphers (a game approach that minimizes the gain of the “opponent”);

- application of the principle and operations of decoding several copies of the code block to increase the reliability of bringing and ensure high reliability of the information brought;

- the use of means for verifying the reliability of decision-making in the process of identifying correctly received characters, which in the decoding process ensures that any constructively specified probability of decoding errors is achieved by checking accurately calculated decoding outcomes.

In accordance with the invention, the method is proposed to be constructed as follows.

A universal method of transmitting information with controlled parameters, characterized in that before the transfer of information the conditions for the exchange of information and the quality of the channel are determined, the optimal values of the parameters of the used code n, k and m of the stochastic q-ary (n, k, m) code are selected based on the source binary (n, k) -code with l-interleaving (q = 2 ^l), and m transmission code blocks with the same values of the information part, information is encoded using the selected q-ary code, to operate in transmission channel direct stochastic Conversion q-ary characters, at the reception they perform the inverse stochastic transformation of q-ary characters, localize correctly received q-ary characters in m code blocks, evaluate the reliability of localized characters, correct non-localized and unreliable q-ary characters in m code blocks, accumulate for issuing reliable q-ary characters after processing m code blocks to the consumer.

For the method under consideration, the basic operations are performed as follows.

The selection of the optimal code parameters for duplex public channels is carried out according to the criterion of the maximum transmission speed while ensuring the required reliability required in advance, estimated by the probability of error in the information issued to the consumer.

The selection of optimal code parameters for simplex channels is carried out according to the criterion of ensuring the required reliability of message delivery, estimated by the probability of message delivery from the first transmission, while ensuring the required reliability.

Guaranteed randomly set reliability is provided by correcting errors of a certain multiplicity t with a stochastic q-ary code (q = 2 ^l ) based on a binary code with the required code distance d, determined depending on the required probability of decoding error not higher than _Рш = 2 ^{- (dlt) l,} the code blocks with an error when an error is corrected multiplicity t≤d-1- (log ₂ P _err) / l distorted q-ary symbol in a given block are issued to the consumer units with greater magnification errors do not give the consumer and store copies for decoding im ste repeated with the value of the block with the same value of the information part.

Guaranteed bringing messages required probability or exchange in real time reaches the transmission m blocks with the same information part and correcting errors in the copy decoding mode, wherein the copy number m is determined depending on the desired probability of message delivery to the first transmitting _rows = P (≤ t, N _messages ), where t is the number of corrected distorted q-ary characters along the message length N _messages expressed in the number of q-ary characters.

The quality control of the channel, necessary to adapt the protocol parameters to the state of the used communication channel, is carried out by transmitting the test sequence in the form of a q-ary stochastic (n, l, q) code, the probability of distortion of a q-ary character is determined by pairwise comparison of q-ary characters of the received block (n, l, q) -code, counting the number of matching b characters and calculating this probability as a (nb) / n ratio.

The use of any duplex channels with nonzero bandwidth (that is, including very low quality) achieves the reliability control of each block and the adaptive choice of the (n, k, q) code that is optimal for the current channel state.

The use of any simplex channels with non-zero bandwidth is achieved by checking the reliability of each code block and q-ary symbol and m-times transmitting code blocks with decoding copies, where m is determined depending on the required probability of bringing the message from the first transmission over the channel used using the selected ( n, k, q) code.

The decoding process is based on sequentially performed operations of extracting correctly received q-ary code characters (localization) and subsequent correction of non-localized or unreliably localized characters. Such an implementation of error correction makes it possible in an arbitrary channel, including with intentional interference, to achieve a guaranteed reliability specified in the design, estimated by the probability of decoding error. In this case, the localization of correctly received q-ary characters of (n, k, q) -codes is performed using N = 2 ^nk -1 code verification ratios, which are strings of the binary H matrix verification matrix and their linear combinations, checking the correct reception of q-ary characters for the j-th relation, it is carried out by modulo 2 summing of those of n q-ary symbols that correspond to the symbol 1 in the given j-th verification relation and checking the value of the sum obtained, the relation is considered fulfilled, and the q-ary symbols are recognized correctly without any appearances, if this sum is equal to a combination of l zero binary characters, the number of localized characters N _l (N _l ⊂ [0, n]), the number of satisfied relations N _c (N _c ⊂ [0.2 ^nk -1]) are calculated and for each q-ary symbol with the number i is the number of fulfilled relations, which included this symbol, - M _i .

The decoding of m copies of the (n, k, q) code is performed by localizing and accumulating correctly received characters in three stages, counting the total number of fulfilled relationships and the number of fulfilled relationships for each character, in this case pairwise comparison of m characters of the same name as for the q- block of the egg (m, l, q) code, matching characters accumulate as localized, localize correctly received characters for each of m blocks according to the decoding rules of the (n, k, q) code, characters localized in any block accumulate, for previously n The localized characters are cross-localized with the substitution of the values of non-localized q-ary characters from different copies into the checked verification ratio, after the localization, the correct localization is checked, unreliable and non-localized characters are corrected, expressing their values through the values of authentically localized characters.

The verification of localization for code blocks is carried out by checking the conditions Nc = 2 ^{rt *} -1, t * ≤d-2, where t * = nN _l , d is the code distance of the binary (n, k) code.

Reliability assessment when decoding copies is performed by the values of the number of fulfilled relations for each of k information q-ary symbols of the code.

The guaranteed randomly set probability of decoding error _Posh when decoding m copies in a block of (n, k, q, m) code is provided by correcting errors up to a certain multiplicity t not exceeding t≤dm-1- (log _{2 Posh} ) / l, moreover, when the error rate exceeds this value, the information is not issued to the consumer or issued with an indication of non-compliance with the requirements for reliability.

Consider the order and features of the application of the method in the typical conditions of information and telecommunication systems.

The following main options for applying the method in terms of use:

- duplex public channels,

- simplex (unidirectional) channels,

- duplex channels of real time,

- channels of very poor quality,

- data transmission channels to ensure very high reliability,

- information storage medium (computer memory, databases, etc.),

- Session layer protocols for monitoring and restoring message integrity.

An example of the implementation of a typical task of transmitting information over duplex communication channels is an adaptive transmission method [4].

In addition to this method, greater reliability is achieved for the most important messages extracted from the data stream (with a general reliability of 10 ^-9, for the most important information, 10 ^-18 or 10 ^{-27 are} provided using codes with a large initial code distance d by reducing the number of correctable errors with t = d-2 to t = d-3 or t = d-4, respectively). Moreover, this additional service is provided on the same set of code set parameters while maintaining the size of the q-ary character, along the length of which a stochastic cryptographic conversion is performed. It is also important that changes in the reception conditions to increase the level of confidence are performed only on the receiving side of the channel, the increase in reliability is reflected only in the refusal to receive (no receipt for the block), which leads to its retransmission with possible decoding in copy mode for two values blocks (previously accepted and repeated)

The second example of the implementation of the method is the real-time mode, including when reducing the quality of the channel, by transmitting immediately 2 (in the general case, m identical code blocks with their subsequent decoding according to the decoding algorithm of copies).

Message transmission over a simplex channel with the required reliability of message delivery for a given channel quality, it is proposed to use m-fold transmission of code blocks and a copy decoding mode.

Due to the implementation of the method provides:

- combining in one equipment the means of achieving various reliability requirements with a simple adjustment of the required reliability by the filter at the reception by filtering the reliability by issuing blocks with a given number of correctable characters;

- for an existing device with a specific value of the length of the q-ary character, an additional reduction in the probability of decoding errors is possible by additionally including a new code with a larger distance d compared to the previously used code distance of the original binary code, by entering such a code into the device’s binary verification matrix H;

- you can achieve arbitrarily high reliability without changing in all cases of code redundancy. If for a cyclic code it is possible to obtain the probability of error by introducing the number of redundant symbols log ₂ Р _Ош , then in our case we can take the length of the q-ary character to a minimum and provide ultra-high reliability with one or two codes with a large code distance, estimated using expressions Р _Ош = 2 ^{- (dlt) l} , that is, due to the correction of less than the maximum possible t = d-2 number of distorted q-ary characters.

For example, taking the length of the q-ary character l = 32 bits, you can provide the following set of properties. In the error detection mode (one check q-ary character), in the mode of decoding copies and correcting errors at the maximum correcting ability (t = d-2), the probability of error is not more than 10 ^-9 with a decrease in correcting ability by 1 (t = d- 3, for example, for Hamming codes with an additional parity check at d = 4 due to a decrease in the correction ability in two to one distorted q-ary character) the probability of decoding error is reduced to 10 ^-18 . To achieve an even greater increase in the level of provided reliability (to reduce the probability of decoding errors), you can use a code with a large code distance d, for example, taking the BCH code (16.7) with code distance 6, you can achieve the following set of decoding error probability values at l = 32 :

At t = 4 (maximum correcting ability), the decoding error probability is not higher than 10 ^-9 . When t = 3, the decoding error probability is not higher than 10 ^-18 . When t = 2, the decoding error probability is not higher than 10 ^-27 . When t = 1, the decoding error probability is not higher than 10 ^-36 . At t = 0 (error detection), the decoding error probability is not higher than 10 ^-45 .

At the same time, it is understood that all hardware and algorithmic decisions in the data transmission channel do not change, with the exception of setting the filtering procedure of the blocks at the decoder output when issued to the consumer. If the error probability of 10 ^{-9 is} sufficient for this mode of operation (when transmitting this message), then all blocks with corrected errors (with an error multiplicity of 1 to 4) are issued to the consumer and acknowledged on the return channel, if the error probability is not higher than 10 ^-18 , then blocks are issued to the consumer and acknowledged with the number of corrected errors from 1 to 3, blocks with a multiplicity of corrected error 4 are not acknowledged on the return channel and will be retransmitted in accordance with the exchange protocol used. Moreover, a block with 4 corrected errors will be accumulated for subsequent decoding in the decoding mode of copies together with the retransmitted value of this block.

In simplex communication channels, the application of the method provides, with guaranteed reliability, any arbitrarily set reliability of message delivery from the first transmission, including in a low-quality channel, where copy decoding mode can be used. Moreover, the mode of decoding copies provides the maximum possible corrective ability for the design of the extended code. If the source binary code has, for example, a code distance of d = 4 (a Hamming code with an additional parity check), then the original stochastic code (m = 1) corrects two distorted q-ary characters, then the extended stochastic code with a double repetition of the source code ( m = 2) allows you to correct six distorted q-ary characters (t = 6), with three repetitions of a block, 10 characters are corrected, or, in general, at least t = md-2 is corrected.

That is, for an (n, k, q, m) code based on an initial binary (n, k) code with a code distance d that has a code distance md, a correction power is saved that differs from the code distance by 2.

This method of error correction allows you to bring information on a channel of very low, almost arbitrary quality with a non-zero throughput. The possibilities of a stochastic code in an arbitrarily low quality channel can be illustrated by a code with the repetition of (n, 1), which allows you to successfully bring a message the size of one q-ary character (l bits) in case of distortion to n-2 q-ary characters. For example, if n = 20, then decoding is successful with distortion from 1 to 18 q-ary characters from 20. At the same time, high reliability of decision-making during decoding is ensured. For example, if a code with a repetition (20.1) shows at decoding that 10 characters are distorted, and the value matching the remaining 10 characters is given to the consumer as the correct character, then the probability of error during decoding in this case is q ^-9 .

The most important stochastic transformation operation used as part of the error-correcting error-correcting code used is performed in any way to ensure the properties of the q-ary symmetric channel, i.e. transforming the error vector in a q-ary symbol into one of its possible values with equal probability. The application of such an operation provides the guaranteed reliability of the information given to the consumer in an arbitrary channel. For fast and efficient implementation of stochastic transformation, it can be performed using operations based on tables with random filling [4]. The values of the transformation parameter ξ of length l are generated using a register with nonlinear functions in feedback circuits based on tables with random filling [5]. Moreover, when implementing the method, the initial filling of tables with random numbers and a shift register with feedback are the key to cryptographic protection.

The described method has the following advantages:

1) ensures the unification of the means of transmission and protection of information and their hardware, software and software;

2) provides an arbitrarily small, almost zero, the probability of decoding errors in the channel with an arbitrary nature and the law of distribution of interference;

3) the required probability of bringing the message from the first transmission in the error correction mode, including in the decoding mode of m copies of code blocks with a low channel quality, is ensured;

4) provides a stable exchange of information on the channel with unknown characteristics; sufficient for the exchange of information using this method is the nonzero bandwidth of the provided channel, that is, the presence of connectivity or the ability to transmit information;

5) provides the maximum effective data transfer rate for a given channel, close to the channel capacity;

6) through the use of a set of M stochastic codes with error correction, the advantages resulting from the properties of these codes are achieved, namely:

- ensuring comprehensive protection within a single set of information processing operations with a single input redundancy

- increase the efficiency of information processing with the achievement of:

- guaranteed reliability in the error correction mode with an arbitrary nature and intensity of distortion in the communication channel

- increase in the effective speed of information transfer

- providing real time

7) a high speed of information processing is achieved, not restraining the physical speed in the communication channel, expressed in bits per second;

8) widespread use of error-correcting codes with direct code error correction in channels with an arbitrary distribution law and error rate in a communication channel, including with deliberate distortions with the aim of destructive effects on communication channels and communication networks and information systems.

The method allows information exchange through duplex and simplex channels, in all possible transmission conditions, including in which it is impossible to use other methods (low channel quality, intentional interference), to ensure the guaranteed nature of the probability-time characteristics, the accuracy of the calculation of these characteristics due to randomization signals in and perform all the functions of information security comprehensively with higher efficiency, in all possible conditions, within the framework of a single information processing algorithm when nokratnom introducing redundancy.

The method can be applied in all cases where error-correcting codes are used with error detection and correction.

Thus, the method can be applied in:

- networks like Internet / Inranet;

- in networks using various protocol stacks;

- in radio networks and communication channels, including in broadband wireless networks such as Wi-Fi, Wi-Max;

- in broadcast systems to ensure noise immunity of the transmission with the expansion of the reach of the signal and control the use of the network by subscribers;

- in operating systems and databases;

- mobile telephone networks;

- in applied software of information systems and control systems, etc.

Literature

1. CCITT X.25 recommendation and its application in computer networks. Description of recommendation X.25. International Center for Scientific and Technical Information. Moscow, 1983.

2. W. Peterson, E. Weldon. Error correction codes. World, M., 1976.

3. Patent of the Russian Federation No. 2264647. The method of adaptive information transfer. Author Osmolovsky S.A., 2004.03.29.

4. Patent of the Russian Federation No. 2254685. A method of encrypting information conversion. Author Osmolovsky S.A., 2003.01.13.

5. Patent of the Russian Federation No. 2226129. A way to generate random numbers. Author Osmolovsky S.A., 2003.01.13.

Claims (13)

1. A universal method of transmitting information with controlled parameters, characterized in that prior to the transfer of information determine the conditions for the exchange of information and channel quality, select the optimal parameters n, k and m of the stochastic q-ary (n, k, m) -code code based on the original binary (n, k) -code with l-interleaving (q = 2 ^l ) and transmitting m code blocks with the same values of the information part, encode information using the selected q-ary code, perform direct stochastic q- transformation before transmitting to the channel egg characters at the reception, they perform the inverse stochastic transformation of q-ary characters, localize correctly received q-ary characters in m code blocks, evaluate the reliability of localized characters, correct non-localized and unreliable q-ary characters in m code blocks, and accumulate valid q-ary characters for delivery to a consumer after processing m code blocks. 2. The method according to claim 1, characterized in that the selection of the optimal code parameters for duplex public channels is carried out according to the criterion of maximum transmission speed while ensuring the required reliability in advance, estimated by the probability of error in the information issued to the consumer. 3. The method according to claim 1, characterized in that the selection of optimal code parameters for simplex channels is carried out according to the criterion of ensuring the required reliability of message delivery, estimated by the probability of message delivery from the first transmission, while ensuring the required reliability. 4. The method according to claim 1, characterized in that the guaranteed randomly set reliability is provided by correcting errors of a certain multiplicity t with a stochastic q-ary code (q = 2 ^l ) based on a binary (n, k) code with a code distance d defined depending on the required probability of decoding error no higher than P _Osh = 2 ^{- (dlt) l} , code blocks with a corrected error for error multiplicity t≤d-1- (log ₂ P _Osh ) / l distorted q-ary characters in this block give to the consumer, blocks with a higher error rate do not give out to the consumer and accumulate d For decoding together with the value of the repeated block with the same value of the information part. 5. The method according to claim 1, characterized in that the guaranteed message delivery with the required probability or exchange in real time is achieved by transmitting m blocks with the same information part and correcting errors in decoding mode, while the number m is determined depending on the required probability of bringing messages from the first transmitting _rows = P (≤t, N _MSG), where t - the number of correctable distorted q-ary symbols on message length N _MSG, a pronounced among the q-ary symbols. 6. The method according to claim 1, characterized in that the quality of the channel is checked by transmitting a test sequence in the form of a q-ary stochastic (n, l, q) code, the probability of distortion of a q-ary character is determined by pairwise comparison of q-ary characters received block (n, l, q) -code, counting the number of matching characters b and calculating this probability as a ratio (nb) / n. 7. The method according to claim 1, characterized in that the use of any duplex channels with non-zero throughput achieves the control of the reliability of each block and the adaptive selection of the (n, k, q) -code that is optimal for the current channel state at m = 1. 8. The method according to claim 1, characterized in that the use of any simplex channels with non-zero bandwidth is achieved by checking the reliability of each code block and q-ary symbol and m-times transmitting code blocks and decoding, where m is determined depending on the required probability of bringing messages from the first transmission on the used channel using the selected (n, k, q) code. 9. The method according to claim 1, characterized in that the localization of correctly received q-ary characters of the (n, k, q) code is performed using N = 2 ^nk -1 code verification ratios, which are the rows of the verification matrix of the binary code H and their linear combinations, checking the correct reception of q-ary symbols for the j-th relation is carried out by summing modulo 2 of those n q-ary symbols that correspond to symbol 1 in this j-th verification relation, and checking the value of the received sum, the relation is considered to be fulfilled , and q-ary characters are recognized I correctly accepted without distortion, if this sum is equal to a combination of l zero binary characters, the number of localized characters N _l (N _l ⊂ [0, n]), the number of relations N _c (N _c ⊂ [0.2 ^nk -1 ]) and for each q-ary symbol with number i - the number of fulfilled relations that included this symbol - М _i . 10. The method according to claim 1 or 9, characterized in that the localization and accumulation of correctly received characters m of the code blocks of the (n, k, q) code is performed by counting the total number of fulfilled relationships and the number of fulfilled relationships for each character, pairwise comparison of m characters of the same name as for a block of q-ary (m, l, q) code, matching characters accumulate as localized, localize correctly received characters for each of m blocks according to the decoding rules of (n, k, q) code, localized characters in any block ivayutsya for previously unlocated symbols carried localization cross-checked with the substitution in relation verification values unlocated q-ary symbols from different code blocks after localization check correct localization, unreliable and uncontained correcting code, expressing the values of the values significantly localized symbols. 11. The method according to claim 1, characterized in that the correctness of localization for code blocks is carried out by checking the conditions Nc = 2 ^{rt *} -1, t * ≤d-2, where t * = nN _l , d is the binary code distance ( n, k) code. 12. The method according to claim 1, characterized in that the reliability assessment when decoding the code blocks is performed by the values of the number of fulfilled relations for each of k information q-ary characters of the code. 13. The method according to claim 1, characterized in that the guaranteed randomly set probability of decoding error R _OSh when decoding m code sides in a block of (n, k, m) code is provided by correcting errors to a certain multiplicity t not exceeding the value t≤ dm-1- (log _{2 Рш} ) / l, moreover, when the error ratio exceeds this value, the information is not issued to the consumer or issued with an indication of the failure to fulfill the reliability requirements.