In this article, models of discrete channels are analyzed. It is proposed to use the L.P. Purtov for building channels of information systems. Redundant binary and non-binary codes and their error-correcting capability are analyzed. Formulas are derived for finding the probability of an uncorrected error for errorcorrecting codes, for codes that find errors, and for codes that detect and correct errors. The coefficient of increasing the information array is calculated for different probabilities of the detection of one element of the codeword in the channel and different error rates. Calculation of the redundancy of the error burst correction codes is performed. The use of Fire codes as anti-noise codes in the channels of the information system is proposed.
The issue of transmitting discrete information in information systems and networks in the case when it is impossible or unprofitable from an economic point of view to use a reverse communication channel to increase the reliability of messages is of interest to a wide range of specialists in the field of security, wire and radio communications. A large number of articles and monographs are devoted to this topic. However, most of the publications are devoted to the coverage of information channels in which binary correction codes are used as error-correcting codes. This is mainly due to the simplicity of operations in the binary number system, which are performed by various computer devices in the processing, accumulation and storage of information in information systems and networks.
The use of combined types of modulation in information channels allows to
significantly increase the data transmission rate in comparison with binary systems. And
the use of error-correcting codes with q 2 alphabet, which allow you to identify and
correct errors, in such systems is quite a logical step. Such codes are called Non-binary
(multi-positional, multi-base or q-ary) [
Statement of research problem
Discrete channel mathematical model The description of the channel consists of determining the restrictions on the signals S(t), the transmission of which it provides, and the nature of the transformation S(t)→ S*(t), which it performs. For discrete channels, it is enough to indicate the allowed signals (symbols) or simply their number m and the allowed moments of signal change. For m = 2 (such channels are called binary), the allowed times of signal change (significant moments) are completely determined by the modulation rate. The transformation S(t) → S*(t) in the ideal case reduces to the equality S(t)=S*(t). The difference arises from the non-improvement of the communication line. The transformation S(t)→S*(t) has two components - deterministic and random. Deterministic changes in the signal in a discrete channel are delayed (time offset). The resolving device is a threshold device, it emits signals of a fixed form, so no signal changes are observed. Random signal changes are caused by interference.
When converting symbols in a discrete channel, the received sequence of message elements
differs from the transmitted one . In the general case, the probabilistic laws of transformation
→ ∗ are very complex due to the complex nature of the interference. The influence of noise can be represented as an elemental summation of a sequence with a sequence of errors. Then ∗
0 → 1 , the errors are considered symmetric. The multiplicity (number of errors) is the number of errors t, which accounted for a given number of unit elements: errors can be single, double, etc.
From the point of view of the influence of interference on the fidelity of the transmission, the channels are divided into symmetrical and asymmetrical, channels with memory and without memory, stationary and non-stationary. In a symmetric channel, the transmission probability does not depend on the statistics of the transmitted sequence, but is completely determined by the error statistics. A stationary channel without memory is called one in which the probability of an error in receiving an element does not depend on the number of an element in the transmitted sequence and does not depend on the values (zero or one) of the elements preceding or following it.
The probabilistic model of a discrete channel is called the final description of the channel, which allows, with known probabilities of the input signal, to find expensive probabilities of the characteristics of a discrete channel without resorting to experimental data or additional assumptions. Since statistics in a symmetric channel are completely determined by the error statistics and do not depend on statistics, an error stream is sufficient to describe it. binomial distribution
For independent errors, it is enough to know the only parameter to find the distributions of the random variable. Based on Bernoulli's theorem, the probability of occurrence in an n-element combination is equal to errors , is found by the for 0 0 the above equation becomes: it is seen that the probability of receiving an undistorted combination ,
1 0, 1
, (1) (2) (3) (4) In the case of the probability of receiving a false combination, that is, a combination that contains at least one error, the above equation becomes: , ∑
1 1, 1 0, 1 , In the case of the probability of occurrence of m or more errors in a combination of length n, the above equation becomes: A simple error model gives only an approximate state in real channels. Further investigation of the stream of errors in real channels showed that errors in communication channels are grouped. The probability of an error in a group (pack) of errors increases sharply and is significantly greater than . Let there be possible independent errors with conditional probabilities P0 P1 1 in a "good" state mula: and in both channel states. Then the error probabilities are calculated by the for .
The mathematical model of the channel should provide the engineering ability to
calculate the basic characteristics [
Discrete Channel Models with Error Bursts As a general mathematical model of an information system channel, the model of L.P. Purtov is used most of all. Models with Markov chains require a more accurate description of the initial parameters and a large amount of computation, so they are used to describe specific channels. L.P. Purtov's model describes the probability of a multiplicity error equal to or greater than t in a block of length n elements, depending on the error probability in the p element and the error grouping coefficient α: ∝ , where is the length of the codeword.
typical for most channels.
The error grouping factor varies within 0.5 ... 0.7 - for cable and 0.2 ... 0.4 - for radio channels. Limit values: ∝ = 0 - independent errors and ∝ = 1 - all errors are collected in one batch.
Let us investigate the dependences of the error probability of multiplicity t in the code word using the above model. Let the code combination have = 128 bits with the probability of an independent error 10 and the error grouping factors ∝ = 0.5; 0.6 and 0.7. Figure 1 shows graphs of these dependencies.
Figure 1 shows that, firstly, with an increase in the error grouping coefficient, all other things being equal, the probability of an error of the multiplicity t decreases, and this pattern remains in the entire field of application of the L.P. Purtov. In other cases, the probability of an error of multiplicity t is always greater than the probability of an error of multiplicity 1. And finally, with an increase in the error grouping coefficient, the difference between the probabilities of errors of multiplicity and + 1 changes.
Analyzing the above figure, we can conclude that in real transmission channels of control information, errors tend to be grouped. In this case, there is a tendency, for a given number of bits of information ( = 128), the greatest probability of occurrence of a burst of errors is when the length of this burst is → 5. So, suppose that the multiplicity of the error will be 4. To correct this error, it will be necessary apply noise immunity code, will have a large correcting ability, with little redundancy. (6) , which are 0.02 0.015 P(t0.5) P(t0.6) 0.01 P(t0.7) 0.005 0 0 5 10 15 20
25 t There are such coding methods that increase the efficiency of information transmission: optimal coding, error detection coding and error correction coding [3].
Error detection and correction codes increase the noise immunity of information transmission.
To select the type of correction code that is used for secondary coding, consider the error rate and the nature of their distribution in time.
A careful distribution of the statistical characteristics of the sequence of errors in real communication channels showed that the errors are dependent and have a tendency to grouping (batching), that is, there is a correlation between them.
Most of the time, information on communication channels passes without interference, and at some points in time there are bursts of errors, within which the error probability turns out to be much higher than the average error probability, which is found for a sufficiently long transmission time interval.
With the group nature of the distribution of errors, one parameter - the probability of error - does not fully characterize the channel; additional parameters are needed that reflect the degree of grouping of errors in various types of channels.
The reasons for the group nature of errors in channels of various types are as follows: tropospheric radio links - fading and interference; radio relay lines - short-term interruptions and impulse noise; over cable communication lines - overload of group paths of high-frequency equipment, short-term interruptions and various kinds of station and operational interference.
For dedicated telephone cable channels, the error rate ranges from (2 ... 5) * 10-4 to 10-5. In switching telephone channels p = 10-3 ... 10-4, depending on the length of the channel, the number and load of automatic telephone exchanges involved in the connection of subscribers. For radio relay and tropospheric channels p = 10-3 ... 10-4 [3].
In all real channels, the errors are very unevenly distributed over time. This is especially typical for cable channels, in which the bulk of errors are concentrated at certain hours of the day, responding mainly to an increase in the load of channel-forming equipment and the3 time of changing the duty of the service personnel.
The assessment of the reliability of information exchange, when designing information transmission systems, is determined by the permissible probability of interference in messages int, At the same time, the probability of interference of the binary symbol of the transmitted message bs is indicated., In the event of independent errors in the communication channels and (1- Pbs) - the probability of no interference. Then for a binary sequence, that has n characters [4], equation becomes: ─ for the probability of a correctly received sequence: , . , ─ for the probability of error in the received sequence: When using redundant codes, it becomes possible to find and correct one or another error rate depending on the code distance: where i = 1,2,3, etc. is frequency of errors, and determined from the formula: ∙ ∑ ∙ ∑ ∙ ∙ mission channels. to the formula: This expression allows you to calculate the probability of an uncorrectable error in transmitting information using a code that corrects t-fold errors.
In practice, communication channels are characterized by the dependence of the probability of interference of the next transmitted symbol on the distortion of the previous one, as well as seasonal and daily changes in the weather, the presence of industrial interference that changes the intensity at the time of the day and days of the week, mutual interference, etc. All this leads to an abrupt nature errors in information trans
The calculation of error probabilities for batch distribution is carried out according
Then four situations can be formulated: 2) The code word was received with an error (probability ). 1) The code word was received without errors (the probability of this event is ∑ 1 .
Let us substitute formulas (8) and (11) into this expression and obtain: -∑ 1 3) The code word was received with an error, which is corrected with the probability of
. ability of this event is
, then 4) The code word was received in error and cannot be corrected by this code. The prob
or 1 1 1 1 1 1
! ∑ ! ! 1 (7) (8) (9) (10) is: (11) ). (12) (13) (14) (15) a packet of errors of length b; where b is the length of the error packet; a packet to the length of this packet b. is the density of errors in a packet, which is equal to the ratio of the number of errors in - conditional probability of occurrence of is the probability of distortion of a binary symbol; q
Probability ∑ 1 and ∑ for codes that determine bursts of errors, are calculated ∙ ∙ ∑ ∑ 1 1 ∙ ∑ ∑ ∙ ∙ ; ∑ where is the length of the error packet found.
Approximate formulas for determining ─ for error-correcting codes: look like: where t is the multiplicity of the error being corrected; s - error grouping indicator; ─ for codes that find errors: ∑ , , . ─
for codes that detect and correct errors: These formulas give good results if the number of errors e in combination with n symbols satisfying the requirements e
0.3n [
When transmitting information with a simple non-redundant code, the reliability of reception depends on the type of channel and the type of interference in it. In most cases, the reliability that is found is insufficient. It must be increased so that the probability of erroneous reception of the message by the consumer is less than the probability of errors in the message without special measures.
─ identification of errors; ─ error correction; ─ identification and correction of errors.
In order to increase the reliability with the help of codes designed to detect errors, it is necessary to introduce a feedback channel. Then the code word received on the forward channel is analyzed to determine if it belongs to the allowed combination. The allowed combination comes to the consumer after the check bits are rejected. If an error is detected, a request signal is sent over the reverse channel, through which the transmitter repeats the transmission of information. Therefore, the transmitting device must (17)
, (18) (19) (20) (21) store information about the sent signals for a period of time sufficient for the receiving device to analyze the combination and receive a possible error request.
Error correction is usually applied when there are independent errors or short bursts of errors in the communication channel. If the error weight is the same as the codeword length, then the error burst corrections lead to unjustified losses of equipment for encoders and decoders.
Error-correcting codes can correct errors, the weight of which numerically does not exceed 20-25% of the length of the code combination. Most probable errors with a weight close to 50% of the length of the code word. Therefore, if it is necessary to correct, those methods are appropriate that allow you to determine the verification pulses from the information for a time exceeding the probable length of the burst of errors [8].
Thus, the choice of a method for increasing the reliability of information transmission depends on many factors: the reliability of reception, the permissible transmission rate, and dependence on errors in the communication channel are necessary.
The degree of information protection from errors by the appropriate coding method depends mainly on the minimum coding distance dmin of the given code.
There are three types of code distance: Hamming, Lee and matrix. The first is most widely used in coding theory. The Hamming code distance is inextricably linked with the concept of the weight w of the code combination - the number of its elements that are not equal to zero. Hamming code distance d between two combinations of the same length n is defined as the number of similarly named bits (positions) that have unequal elements. So, for binary codes, since in binary arithmetic adding identical elements gives 0, and unequal ones - 1, the Hamming distance between two code combinations can be determined by adding them bitwise modulo 2 and then counting the number of nonzero elements, that is, determining the weight w of such a sum.
The total number of code combinations of length n is equal to 2n, and the number of those of them that are distant from the given in view d is the number of messages from n to d: In the Lie metric , 0, ! ! 2 !
1.. ∑ error correction with multiplicity rors, the condition must be satisfied:
Due to the fact that, on the whole, each element (bit) of a combination of a Non-binary (multi-position) code can have, in contrast to a binary, and more than one position (m
where m is the number of positions in each bit (single new interval, corresponding to the duration of one element) of the code combination.
In the Hamming metric, the code distance, as for a binary code, is determined by the number of bits of the same name with different positions (symbols): (22) 1, and (23) (24) (25) |.
|, | | = , , (26)
, where ulo q. plement.
|
|, that is, you should perform subtraction mod
The most rational should be considered information transmission systems in which redundant codes are used only for detecting errors, because in real channels there are often bursts of errors with a length of several tens or hundreds of symbols and to correct them one would need a code with a code combination length that is measured in thousands and tens of thousands of discharges, which is technically difficult to im
If the nature of the distribution of errors in a channel is known, this does not mean that such errors are present only in this channel, and not in the modem, which is used for research and can only change when the transmission rate, signal power, etc. The nature of the errors is highly dependent on the modem being used. Therefore, it is always necessary to consider the choice of modem and code as a single task and find the optimal solution.
After determining the characteristics of the communication channel, further selection of the code is characterized by the error probability. By this parameter, codes are selected in which the probability of detecting an error less . .
.
To ensure a given information transfer rate, you need to choose a code with the
minimum required number of check bits, which provide
. In this case, one should not
forget that the detecting properties are determined not only by the number of check bits,
but also by the type of check ratios, and for cyclic codes - a generating polynomial.
Compared to other codes, the best code that not only detects but also corrects
independent (single) errors and has recommendations of international organizations and is
relatively simple to implement is Hamming code, both binary and generic. As for both
packets and independent errors, the BCH, Fire and Reed-Solomon codes are the best
for the same parameters. These codes can be used for the transmission the ring codes
shift indexes vectors that are described in [
Despite all the advantages of error-correcting coding, one of its disadvantages is an increase in the information array. Table 1 shows the coefficient of increasing the information array for the above defined optimal codes for various error probabilities of one element in the communication line (channel).
According to the OSI hierarchy, the control information transmission channel consists of physical and data link layers.
The physical layer of the channel ensures that the parameters of the signal are matched to such characteristics of the physical channel as the amplitude-frequency characteristic and the distribution of the noise power density, and must provide the specified constant component of the signal delay and the probability of an error in the binary bit of the transmitted digital stream, which, in turn, defines the requirements for the average bit rate. Building a physical layer subsystem is a multi-criteria optimization problem, the criteria of which are:
ement in a line Coefficient of increasing the information array (at k = 8)
3 n o ita 2,5 m fro 2 n i teh 8=1,5 isegan kt(a 1 r a0,5
y c r ifn ra o 0 t n e i c i f f e o C
Distortion probability of one element in the channel
─ constant value of the digital stream delay in the channel;
─ the value of the error probability in a binary digit of a digital stream;
─ average bit rate of digital stream; the cost of the physical layer subsystem.
The link layer provides the combination of control messages into a single stream for
transmission to the physical layer, control of the error probability of the received
information, control of the message delay in the channel depending on the probability of
drinking, which is provided by the physical layer subsystem and the length of a specific
control message transmitted by the upper layers of the network control system. The
construction of the link level subsystem is also a multi-criteria optimization problem,
the criteria of which are:
─ variance of the control message delay value in the channel;
─ the value of the error probability in the control message;
─ average transmission rate of the message flow [
The random nature of the message delay in the channel and the error probability in the message are determined by the non-stationarity of the interference characteristics in most physical channels and, as a consequence, by the variable value of the bit error probability itself and the message processing time at the channel layer. There are possibilities to reduce the variance of the message error probability and the variance of the message delay in the channel: ─ the use of correction codes with a large correction capacity (for example, convolutional ones, which leads to the introduction of significant redundancy, will not be effectively used when reducing the probability of an error in a bit and will significantly reduce the channel capacity; ─ block coding when transmitting very large blocks, the length of which is so large that the probability of errors in a block differs very little from the average. It is widely known block codes with optimal redundancy for a given correction ability, however, coding in very large blocks leads to an unacceptable value for control information of a constant value of the digital stream delay in the channel and an increased complexity of correction code decoders.
The following restrictions are most typical for such a control information transmission channel: ─ control information arrives at the channel input in the form of messages (blocks) with a length that is a multiple of 8 bits (due to the specifics of the development of a modern element base); ─ the block nature of the control information determines the use of block codes (more often Bose-Chowdhury-Hawkingham (BCH) codes or their non-binary subclass
─ the physical layer provides the error probability for the binary symbol y, but errors are grouped into packets. and the number of information items - by the expression:
Among the anti-jamming codes, we will choose a code, using which, the indicators of quality and survivability of the information system will increase.
code, it is necessary that the total number of characters is approximately the same. Then, comparing the redundancy of the codes with the redundancy of the BCH code, namely, it is used as a noise immunity code when transmitting information in information systems, where bursts of errors prevail.
For BCH codes to correct 4 errors, it is necessary that the code distance adheres to the condition dmin = +
+ 1, therefore dmin = 4 + 4 + 1 = 9 the length n of the BCH code combination can be determined as follows: an odd number. Thus, the length n can only have an odd number of elements. where h > 0 is integer; is an odd positive number, when divided by which n becomes The number of verification code elements is determined by the expression: 2
1 or 2 ,
, 1 or 28, Thus, n = 127 = 27 - 1 = 127, redundancy R = 28/127 = 0,22.
For the Fire code, we find h, provided that the length of the error burst is 4. h = 24 - 1 = 15. For this situation, the generating polynomial for the Fire code is PF(х) = (х4 + х + 1)( х7 + 1) = х11 + х8 + х7 + х4 + х + 1, then the degree of the irreducible polynomial P(х) is l = 4, c = 7. Referring to formulas (3.12), (3.13), (3.14), we find n, r, k.
n = НСК (7, 15) = 715 = 105; r = 4 + 7 = 11; k = 105 - 7 - 4 = 94. Redundancy of the code R = 11/105 = 0,1.
It follows from this that it is much easier to correct four errors that are in the same place than the same four errors, which are randomly distributed over the entire length of the . k = 127 - 28 = 99. Code (27) (28) (29) combination.
BCH
BCH
Reed-Solomon 5 7 9 11 13
15 After analyzing the data obtained, we can conclude that the Fire code provides a lower probability of an uncorrected error than the BCH, compound, or Reed-Solomon codes at the same coding distance, that is, these codes require greater message redundancy to provide the same probability uncorrected error as the Fire code.
So, after considering the codes that allow you to correct single bursts of errors, you can propose the use of the Fire code instead of the BCH or Reed-Solomon code, since it has less redundancy compared to other noise immunity codes that correct bursts of errors.