RU2611022C1 - Method of joint arithmetic and protective coding (versions) - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: check symbols on transmitting side are selected by allocation of a sub-interval for each check symbol among current zero symbol encoding sub-interval and current single symbol encoding sub-interval, including the middle of initial interval of arithmetic coding, and check symbols sets the symbol corresponding to the selected current sub-interval, next part of encoded sequence is transmitted on the receiving side, wherein, if the current decoding subinterval of each decoded check symbols includes the middle of initial interval of arithmetic coding, the absence of transmission errors is concluded.

EFFECT: joint arithmetic and noise protective coding of redundant binary information sequence providing reduction in requirements for transmission speed of encoded sequence through transmission channel and reduction in capacity of devices for its storage.

3 cl, 26 dwg

Description

The claimed technical solutions are united by a single inventive concept and relate to the field of telecommunications and information technologies, namely to the technique of compressing redundant binary information and its noise-resistant coding when exchanging data over transmission channels with errors.

The claimed objects of the invention can be used to compress redundant binary information and its error-correcting coding when exchanging data on transmission channels with errors.

A known method of adaptive error-correcting coding according to the patent of the Russian Federation 2375824 IPC H04L 1/20 (2006.01) dated 12/10/2009, which consists in the fact that on the transmitting side the source information is encoded by an error-correcting code with variable parameters, then the error-correcting code is transmitted to the communication channel, on the receiving side the error-correcting code is decoded with the detection and correction of errors depending on the correcting ability of the selected code, the quality of the communication channel is evaluated according to the results of decoding the error-correcting code, and variables parameters of the error-correcting code, providing a given probability of correct reception of the error-correcting code, and then these parameters of the error-correcting code are reported to the transmitting side, characterized in that on the receiving side, based on the results of decoding the error-correcting code, the initial value of the redundancy of the error-correcting code is calculated, which provides a given probability of correct reception of the error-correcting code, evaluate the probability of correct reception of the error-correcting code with the selected parameters, calculate the deviation of the obtained probability of the correct reception of the error-correcting code from the given probability of the correct reception of the code, and depending on the magnitude of this deviation, the redundancy of the error-correcting code is corrected, which is transmitted to the transmitting side, where the error-correcting code is generated with the received redundancy.

The disadvantage of this analogue is the inefficient use of transmission channel bandwidth, caused by the lack of compression of excess binary information when exchanging data on transmission channels with errors.

There is also a method of joint compression and noise-resistant coding of voice messages described, for example, in the book C.H. Kirillov, V.T. Dmitriev, D.E. Krysyaev, S.S. Popov "Study of the quality of transmitted voice information with a different combination of source and communication channel coding algorithms under the influence of interference". - Ryazan, Vestnik RGRTU, Issue 23, 2008. This method consists in preliminarily generating a plurality of methods for compressing a speech signal, such as pulse-code modulation, adaptive delta modulation, adaptive differential pulse-code modulation, and many methods of noise-resistant coding , such as Hamming coding, Bowes-Chowdhury-Hawkingham coding, on the transmitting side from the sender receive the next part of the speech signal the length of the speech phrase, which is converted into a compressed binary sequence the accuracy using one of the methods of compressing a speech signal, perform error-correcting encoding of a compressed binary sequence using one of the methods of error-correcting encoding, transmit the next part of the encoded sequence along with information about the used method of compressing the speech signal and the method of error-correcting encoding to the receiving side via direct communication channel, on the receiving side receive the next part of the received sequence, the next part of the received sequence they are decoded using the appropriate error-correcting decoding method and the method of reconstructing a speech signal, the quality estimate of the reconstructed speech signal is calculated, and the resulting estimate is compared with the threshold quality value, if the calculated quality assessment of the reconstructed speech signal is not worse than a preset threshold quality value, then the receiver receives the next part of the reconstructed information sequence and the transmitting side from the sender received they receive the next part of the speech signal and perform the following actions, otherwise they transmit via the feedback channel the requirement to change the method of compression of the speech signal and the method of error-correcting coding, and perform the following actions.

The disadvantage of this analogue is the large delay in the transmission of messages over the communication channel, due to the need to search for a suitable method for compressing a speech signal and a method of error-correcting coding.

Closest in technical essence to the claimed methods of joint compression and noise-resistant coding is the method of joint arithmetic and noise-resistant coding according to US patent 6892343 IPC Н04М 13/00 (2006.01) dated 05/10/2005. The prototype method of joint arithmetic and noise-resistant coding is that the initial arithmetic coding interval is set on the transmitting side and the initial arithmetic decoding interval corresponding to it is set on the receiving side, the next part of the information sequence of k≥1 bit length is received on the transmitting side, divide the current arithmetic coding interval into the current null character encoding sub-interval and the current the coding sub-interval of a single symbol, from the pre-formed set, test characters of r≥1 bit length are selected and the next part of the error-correcting sequence is formed from the next part of the information sequence and the selected test symbols, arithmetic coding of the next part of the error-correcting sequence into the next part of the coded sequence is converted, the next part of the coded sequences in the next part of the modulated sequence lnostities, transmit the next part of the modulated sequence to the receiving side, perform the above actions on the transmitting side until the next parts of the information sequence arrive, receive the next part of the received sequence on the receiving side, convert it to a binary sequence that is stored, share the current arithmetic interval decoding to the current decoding interval of the null symbol and to the current decoding interval of a single symbol, the aforementioned next parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, from which the next parts of the reconstructed information sequence and decoded verification symbols are extracted, if the decoded verification symbols belong to a pre-formed set of verification symbols, then they conclude that there are no transmission errors and the next part of the restored information sequence, otherwise alternately inv One or several bits in the stored successive parts of the received sequence are verified and their arithmetic decoding is performed until a conclusion about the absence of transmission errors is reached, the above actions are performed on the receiving side until the next parts of the received sequence arrive.

A feature of the prototype method is that on the transmitting side, first, the selection of test symbols is performed, which together with the next part of the information sequence make up the next part of the error-correcting sequence, and then its compression by arithmetic coding, and on the receiving side when decoding, they detect transmission channel errors when the presence, and when they are detected by trial and error, they are corrected.

The prototype method of the joint arithmetic and noise-resistant coding provides the ability to detect and correct errors of the transmission channel.

However, in this prototype method of joint arithmetic and noise-resistant coding, the verification symbols are independent of the redundant information sequence; accordingly, the statistical characteristics of the verification symbols and the information sequence are different. Therefore, in this prototype method of joint arithmetic and noise-resistant coding, the compression ratio of the next parts of the noise-resistant sequence is reduced, which leads to an increase in the length of the encoded sequence and requires an increase in the transmission speed of the encoded sequence over the transmission channel or an increase in the capacity of its storage devices.

Thus, a drawback of the closest analogue (prototype) is the need to increase the transmission rate of the encoded sequence over the transmission channel or to increase the capacity of its memory devices when arithmetic and noise-resistant coding of an excess binary information sequence is combined.

The technical result of the claimed solutions is a joint arithmetic and noise-resistant coding of an excess binary information sequence, which provides a decrease in the transmission rate over the transmission channel of the encoded sequence or a decrease in the capacity of its storage devices.

The specified technical result in the first embodiment of the proposed method of joint arithmetic and noise-resistant coding, using the choice of check characters for the coding sub-intervals, is achieved by the fact that in the known method of joint arithmetic and noise-resistant coding, which means that the initial arithmetic coding interval is set on the transmitting side and on the receiving side the corresponding initial arithmetic decoding interval, on transmitting on the other side of the information source, the next part of the information sequence of k≥1 bit length is received, the current arithmetic coding interval is divided into the current null symbol encoding subinterval and the single character encoding subinterval, the test characters are r≥1 bit long, the next part of the error-correcting sequence is formed from the next part of the information sequence and the selected check symbols, perform arithmetic coding of the next part of the noise sequence in the next part of the coded sequence, transmit the next part of the sequence to the receiving side, perform the above actions on the transmitting side until the next parts of the information sequence arrive, on the receiving side receive the next part of the received sequence, which is stored, share the current arithmetic decoding interval to the current sub-interval of decoding a null character and to the current sub-interval of decoding a single the symbol, the stored next parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, from which the next parts of the restored information sequence and decoded check symbols are extracted, they conclude that there are no transmission errors and transmit the next part of the restored information sequence to the recipient, otherwise one or more bits are inverted in the memorized regular parts of the accepted sequence and perform their ari until the next part of the received sequence arrives, additionally, on the transmitting side, the verification symbols are selected by highlighting for each verification symbol among the current null symbol coding subinterval and the single coding subinterval character the current sub-interval, including the middle of the initial interval of arithmetic coding, and set roverochnym symbol of a symbol that corresponds to the selection of the current subinterval. The next part of the encoded sequence is transmitted to the receiving side, and on the receiving side, if the current decoding sub-interval of each of the decoded check symbols includes the middle of the initial arithmetic coding interval, then a conclusion is made that there are no transmission errors.

Thus, in the first embodiment of the method of joint arithmetic and noise-resistant coding, a selection of check symbols is used corresponding to the current coding sub-interval, including the middle of the initial arithmetic coding interval.

The specified technical result in the second embodiment of the proposed method of joint arithmetic and noise-resistant coding, using the choice of check symbols for the probability of information sequence symbols, is achieved by the fact that in the known method of joint arithmetic and noise-resistant coding, which means that the initial arithmetic interval is preliminarily set on the transmitting side encoding and on the receiving side the corresponding initial interval arithmetic of the decoding, on the transmitting side from the information source, the next part of the information sequence of k≥1 bit length is received, the current arithmetic coding interval is divided into the current coding subinterval of the zero character and the current coding subinterval of a single character, test characters of r≥1 bit length are selected, the next part of the error-correcting sequence from the next part of the information sequence and the selected check symbols, perform arithmetic coding the next part of the error-correcting sequence into the next part of the coded sequence, the next part of the sequence is transmitted to the receiving side, the listed actions are performed on the transmitting side until the next parts of the information sequence arrive, the next part of the received sequence is received on the receiving side, which is stored, shared by the current the interval of arithmetic decoding to the current sub-interval of decoding of a null character and to the current subint tore decoding a single character, the stored next parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, from which the next parts of the restored information sequence and decoded check symbols are extracted, they conclude that there are no transmission errors and transmit the next part of the restored information sequence to the recipient, otherwise they invert one or several bits in the memorized successive parts of the received last sequence and perform their arithmetic decoding until a conclusion is reached that there are no transmission errors, perform the above actions on the receiving side until the next parts of the received sequence arrive, in addition, on the transmitting side, the test characters are selected as zero or single characters, the current probability of which is closest to defined by arithmetic coding of the current probability of information sequence symbols. The next part of the encoded sequence is transmitted to the receiving side, and on the receiving side, if the current probability of the decoded check symbols as zero or single characters corresponds to a certain arithmetic decoding of the current probability of the symbols of the restored information sequence, then a conclusion is made that there are no transmission errors.

Thus, in the second embodiment of the method of joint arithmetic and noise-resistant coding, a selection of check symbols is used, the current probability of which is closest to the current probability of the information sequence symbols determined by arithmetic coding.

The specified technical result in the third embodiment of the proposed method of joint arithmetic and noise-resistant coding, using the choice of check characters for the predominance of the characters of the information sequence, is achieved by the fact that in the known method of joint arithmetic and noise-resistant coding, which consists in the preliminary setting of the initial interval of the arithmetic encoding and on the receiving side the corresponding initial interval is arithmetic decoding, on the transmitting side from the information source, the next part of the information sequence of k≥1 bit length is received, the current arithmetic coding interval is divided into the current coding subinterval of the zero character and the current coding subinterval of a single character, test characters of r≥1 bit length are selected, the next part of the error-correcting sequence of the next part of the information sequence and the selected check symbols, perform arithmetic coding the next part of the error-correcting sequence into the next part of the coded sequence, the next part of the sequence is transmitted to the receiving side, the above actions are performed on the transmitting side until the next parts of the information sequence arrive, the next part of the received sequence is received on the receiving side, which is stored, shared by the current arithmetic decoding interval to the current null-symbol decoding sub-interval and to the current subint the decoding interval of a single symbol, the stored next parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, from which the next parts of the restored information sequence and decoded check symbols are extracted, they conclude that there are no transmission errors and transmit the next part of the restored information sequence to the recipient, otherwise they invert one or several bits in the memorized regular parts received after sequences and perform their arithmetic decoding until a conclusion is reached that there are no transmission errors, perform the above actions on the receiving side until the next parts of the received sequence arrive, additionally, on the transmitting side, the test characters are selected as zero characters if the current probability of zero characters determined by arithmetic coding information sequence greater than or equal to the current probability of single characters of the information sequence, in Alternatively, test characters are selected as single characters. The next part of the coded sequence is transmitted to the receiving side, and on the receiving side, if the decoded check symbols are null symbols, provided that the arithmetic decoding current probability of zero symbols of the restored information sequence is greater than or equal to the current probability of single symbols of this sequence, or the decoded verification symbols are single characters, provided that defined by arithmetic decoding schaya probability of single characters reconstructed information sequence greater than the current probability of null characters of the sequence, then come to the conclusion about the absence of transmission errors.

Thus, in the third embodiment of the method of joint arithmetic and noise-resistant coding, the choice of check symbols is used in accordance with the symbols of the information sequence with a greater current probability.

The indicated new sets of actions in three variants by selecting test symbols in accordance with the current probability of zero and single symbols of the information sequence make it possible to increase the compression ratio of the next parts of the error-correcting sequence, which leads to a decrease in the length of the encoded sequence and reduces the transmission rate over the transmission channel of the encoded sequence or reduction in the capacity of devices for its storage.

The claimed method (options) is illustrated by drawings, which show:

- in FIG. 1 - a General scheme of joint arithmetic and noise-resistant coding in the proposed methods;

- in FIG. 2 - algorithm for joint arithmetic and noise-resistant coding on the transmitting side;

- in FIG. 3 is a state table of the joint arithmetic and noise-resistant coding of the first six successive parts of the error-correcting sequence when selecting check symbols for the coding sub-intervals;

- in FIG. 4 - time diagrams of the joint arithmetic and noise-resistant coding of the first six successive parts of the error-correcting sequence when selecting check symbols for coding sub-intervals;

- in FIG. 5 is a timing diagram of a joint arithmetic and noise-resistant coding on the transmitting side when selecting check symbols for coding sub-intervals;

- in FIG. 6 is a timing chart of joint arithmetic decoding and error correction at the receiving side when selecting check symbols for coding sub-intervals;

- in FIG. 7 - algorithm for joint arithmetic and noise-resistant decoding at the receiving side;

- in FIG. 8 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when selecting check symbols for coding sub-intervals;

- in FIG. 9 is a timing chart of joint arithmetic and noise-resistant decoding of a received sequence with a transmission error when selecting check symbols for coding sub-intervals;

- in FIG. 10 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its first bit when selecting check symbols for coding sub-intervals;

- in FIG. 11 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its second bit when selecting check symbols for coding sub-intervals;

- in FIG. 12 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its third bit when selecting check symbols for coding sub-intervals;

- in FIG. 13 is a timing chart of joint arithmetic and noise-resistant decoding of a received sequence with a transmission error when inverting its third bit when selecting check symbols for coding sub-intervals;

- in FIG. 14 is a timing chart of the joint arithmetic and noise-resistant coding of the first six successive parts of the noise-resistant sequence when selecting test symbols for the probability of information sequence symbols;

- in FIG. 15 is a state table of joint arithmetic and noise-resistant coding of the first six successive parts of the noise-resistant sequence when selecting test symbols for the probability of information sequence symbols;

- in FIG. 16 is a timing chart of joint arithmetic decoding and error correction at the receiving side when selecting check symbols for the probability of information sequence symbols;

- in FIG. 17 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when selecting check symbols for the probability of information sequence symbols;

- in FIG. 18 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its first bit when selecting check symbols for the probability of information sequence symbols;

- in FIG. 19 is a state table of joint arithmetic and noise-resistant decoding of a received sequence with a transmission error when inverting its second bit when selecting check symbols for the probability of information sequence symbols;

- in FIG. 20 is a timing chart of the joint arithmetic and noise-resistant coding of the first five successive parts of the noise-resistant sequence when selecting test symbols for the predominance of information sequence symbols;

- in FIG. 21 is a state table of joint arithmetic and noise-resistant coding of the first five successive parts of the noise-resistant sequence when selecting test symbols for the predominance of information sequence symbols;

- in FIG. 22 is a timing chart of joint arithmetic decoding and error correction at the receiving side when selecting test symbols for the predominance of information sequence symbols;

- in FIG. 23 is a state table of joint arithmetic and noise-resistant decoding of a received sequence with a transmission error when selecting check symbols for the predominance of information sequence symbols;

- in FIG. 24 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its first bit when selecting check symbols for the predominance of information sequence symbols;

- in FIG. 25 is a state table of joint arithmetic and error-correcting decoding of a received sequence with a transmission error when inverting its second bit when selecting check symbols for the predominance of information sequence symbols;

- in FIG. 26 is a comparison of the characteristics of joint arithmetic and noise-resistant coding for the prototype method and the claimed method variants.

The implementation of the claimed methods (options) is presented on the example of the joint arithmetic and noise-resistant coding system shown in FIG. 1. On the transmitting side, joint arithmetic and noise-resistant coding of the next parts of the information sequence is performed, and on the receiving side, joint arithmetic and noise-resistant decoding of the received sequence is performed with the detection and correction of transmission channel errors. On the transmitting side, when the next part of the information sequence is received from the sender of the binary character, when the zero character is received, the counter of the number of zero characters 1 increases the number of zero coding characters by a unit value, and when a single character is received, the counter of the number of single characters 2 increases the number of coding unit characters by a unit value. Proportionally calculated numbers of null and single coding symbols in the boundary interval generator 3, the current arithmetic coding interval is divided into the current null symbol encoding sub-interval and the current single character encoding sub-interval. In the block for selecting the verification symbols 4, verification symbols are selected, which together with the symbols of the next part of the information sequence are encoded in the arithmetic encoder 5 into the next part of the encoded sequence and transmitted via the transmission channel to the receiving side.

On the receiving side, in the serial decoder 7, the next parts of the received sequence are received and stored, which are decoded in the next parts of the decoded sequence in the arithmetic decoder 8. When decoding a null character, the counter of the number of zero characters 9 increases the number of null decoding characters by a unit value, and when decoding a single character, the counter of the number of unit characters 10 increases the number of unit decoding characters by a unit value. Proportionally calculated numbers of null and single decoding symbols in the boundary interval generator 11 of the current arithmetic decoding interval are divided into the current decoding interval of the zero symbol and the current decoding interval of a single symbol, in accordance with which the received sequence is decoded in the arithmetic decoder 8. In the check symbol check block 12, errors are searched for in the decoded check symbols and, if there are no errors, the next part of the restored information sequence is transmitted to the recipient, otherwise one or several bits in the next 7 parts of the received sequence stored in the serial decoder are alternately inverted and arithmetic decoding is performed until the output is reached about the absence of transmission errors.

In the method according to the first embodiment of joint arithmetic and noise-correcting coding, using the choice of check characters for the coding sub-intervals, the following sequence of actions is implemented.

The algorithm for joint arithmetic and noise-resistant coding on the transmitting side is presented in figure 2.

The methods of presetting on the transmitting side of the initial interval of arithmetic coding and on the receiving side of the corresponding initial interval of arithmetic decoding are known and described, for example, in the book “Data compression methods. Archiver device , image and video compression. " - M.: DIALOGUE-MEPhI, 2002, p. 35-43. The initial interval of arithmetic coding starts from its initial lower value and ends with its initial upper value. The initial lower value of the encoding interval is set to the minimum value, and the initial upper value of the encoding interval is set to the maximum value. For example, when representing encoding interval values with eight binary characters, the initial lower value of the arithmetic encoding encoding interval L [0] at time t = 0 is set to a minimum value equal to zero in decimal or 00000000 in binary representation, where the most significant binary characters are written on the left, and the initial upper value of the coding interval of arithmetic coding H [0] is set to a maximum value of 255 in decimal or 11111111 in binary m representation. An example of an initial arithmetic coding interval is shown in FIG. 3 at t = 0 (first row) and in FIG. 4 at t = 0.

On the transmitting side from the information source, the next part of the information sequence of length k≥1 bits is received. An exemplary view of the first six consecutive parts of a binary PI with a length of k = 2 bits is shown in FIG. 5 (a). For example, the first part of the IP has the form "11", the second part is "10", the third part is "01". Single bit values in the figures are shown in the form of shaded pulses, zero bit values in the form of unshaded pulses.

Methods for dividing the current arithmetic coding interval into the current null-character encoding sub-interval and the current single-character coding sub-interval are known and described, for example, in the book “Data compression methods. Archiver devices, D. Arthur, A. Ratushnyak, M. Smirnov, V. Yukin. image and video compression. " - M.: DIALOGUE-MEPhI, 2002, p. 35-43. The length of the initial interval of arithmetic coding I [0], equal to I [0] = H [0] -L [0], is divided into the initial values of the subinterval of the zero character D ₀ [0] and the subinterval of a single character D ₁ [0], the lengths of which are directly proportional to the initial probabilities of the encoded null characters p ₀ [0] and unit characters p ₁ [0], respectively. The length of the initial sub-interval of unit characters D ₁ [0] is determined by the formula of the form D ₁ [0] = I [0] × p ₁ [0], and the length of the initial sub-interval of unit characters of D ₀ [0] is determined by the formula of the form D ₀ [0] ] = I [0] -D ₁ [0].

, а начальное значение вероятности кодируемых единичных символов р₁[0] вычисляют по формуле вида

, где N₀[0] - начальное число закодированных нулевых символов, N₁[0] - начальное число закодированных единичных символов, а N[0] - начальное число закодированных нулевых и единичных символов, равное N[0]=N₀[0]+N₁[0]. В известных способах, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130, устанавливают начальное число закодированных нулевых символов равным N₀[0]=1, а начальное число закодированных единичных символов - равным N₁[0]=1, то есть начальные значения вероятности кодируемых единичных и нулевых символов устанавливают равными: р₁[0]=р₀[0].The initial probability value of the encoded null characters p ₀ [0] is calculated by the formula of the form

, and the initial probability value of the encoded single characters p ₁ [0] is calculated by the formula of the form

, where N ₀ [0] is the initial number of encoded zero characters, N ₁ [0] is the initial number of encoded single characters, and N [0] is the initial number of encoded zero and single characters, equal to N [0] = N ₀ [0 ] + N ₁ [0]. In the known methods described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Data compression methods. The device archivers, image and video compression." - M .: DIALOGU-MIFI, 2002, pp. 124-130, set the initial number of encoded null characters to N ₀ [0] = 1, and the initial number of encoded single characters to N ₁ [0] = 1, that is, the initial the probability values of the encoded single and zero characters are set equal to: p ₁ [0] = p ₀ [0].

For example, the length of the initial subinterval of single characters D ₁ [0] has a decimal value of 128 or 10,000,000 in binary representation, and the length of the initial subinterval of single characters D ₀ [0] has a decimal value of 127 or 01111111 in binary representation. A sub-interval of single characters is located above the sub-interval of null characters, as shown, for example, in FIG. 4. The upper limit of the null-symbol subinterval is designated as the Q value, and this subinterval starts from the bottom of the lower boundary of the arithmetic coding encoding interval inclusively to the Q value exclusively, and the single-symbol subinterval extends from the Q value inclusive to the upper limit of the arithmetic coding encoding interval exclusively. The initial Q value has a decimal value 127, as shown in FIG. 3 in the first row at t = 0.

, текущее значение вероятности кодируемых единичных символов p₁[t] вычисляют по формуле вида

, где N₀[t] - текущее число закодированных нулевых символов, N₁[t] - текущее число закодированных единичных символов, a N[t] - текущее число закодированных нулевых и единичных символов, равное N[t]=N₀[t]+N₁[t]. Соответственно, длину текущего подинтервала единичного символа D₁[t] определяют по формуле вида D₁[t]=I[t]×p₁[t], а длину текущего подинтервала нулевого символа D₀[t] определяют по формуле вида D₀[t]=I[t]-D₁[t].After encoding each successive character, the number of encoded null characters and single characters is specified. After encoding t characters, the current probability value of the encoded null characters p ₀ [t] is calculated by a formula of the form

, the current value of the probability of encoded single characters p ₁ [t] is calculated by the formula of the form

where N ₀ [t] is the current number of encoded zero characters, N ₁ [t] is the current number of encoded single characters, and N [t] is the current number of encoded zero and single characters equal to N [t] = N ₀ [t ] + N ₁ [t]. Accordingly, the length of the current sub-interval of a single symbol D ₁ [t] is determined by a formula of the form D ₁ [t] = I [t] × p ₁ [t], and the length of the current sub-interval of a single symbol D ₀ [t] is determined by a formula of the form D ₀ [t] = I [t] -D ₁ [t].

Verification characters of r≥1 bit length are selected by highlighting for each verification character among the current null character encoding subinterval and the current character encoding subinterval the current subinterval, including the middle of the initial arithmetic encoding interval, and set the character that corresponds to the highlighted current subinterval to the verification character. The way to select test characters is as follows.

The middle of the initial arithmetic coding interval is determined. For this, the initial value of the coding interval of the arithmetic coding I [0], equal to I [0] = H [0] -L [0], is divided in half. For example, when representing the values of the coding interval with eight binary characters, taking into account rounding to the nearest integer, the middle of the initial arithmetic coding interval corresponds to the value S = 127 in decimal or 01111111 in binary representation. An example of the location of the middle of the initial arithmetic coding interval with respect to the current null character coding sub-intervals denoted by D0 and the current single character coding sub-intervals denoted by D1 is shown in FIG. four.

For each successive part of the information sequence of length k≥1 bits, the corresponding binary symbols of a fixed length r≥1 bit are selected. The place of the test characters is chosen fixed relative to the location of the next part of the information sequence. For example, after the next part of the information sequence consisting of two bits shown in FIG. 5 (a), select one binary check character. Accordingly, every third input symbol at times t = 3, t = 6, t = 9, and so on, is a selectable verification symbol, a priori unknown, which is emphasized in FIG. 4 with a "?"

To select each of the test characters, the current sub-interval, including the middle of the initial arithmetic coding interval, is selected from the current null-character encoding sub-interval and the current single-character coding sub-interval. For example, after arithmetic coding of the first part of an information sequence consisting of two bits of the form “11”, the current coding subinterval D0 has boundaries from 82 to 125, and the current coding subinterval D1 has boundaries from 125 to 254, as shown in FIG. . 4 at t = 3. The middle of the initial arithmetic coding interval, corresponding to the value S = 127, of these two sub-intervals includes the current coding sub-interval of a single symbol D1. Therefore, in this case, a single character is set as a check symbol. If the middle of the initial interval of arithmetic coding included the current coding subinterval of the null character D0, then the null character would be set as a test character.

Similarly, the selection of two or more test characters for the next part of the information sequence can be performed.

An exemplary view of the selected first verification symbol (1st verification symbol) of the form "1" for the first part of the information sequence of the form "11" is shown in FIG. 5 B).

The formation of the next part of the error-correcting sequence from the next part of the information sequence and the selected check symbols can be performed, for example, by reading into the next part of the error-correcting sequence first the next part of the information sequence, and after it, reading the selected test symbols. Methods for reading test characters together with the next part of the information sequence into the next part of the noise-tolerant sequence are known and described, for example, in the book by W. Shilo "Popular digital circuits." - M .: Radio and communication, 1987, 104-123, using shift registers with parallel and sequential write / read of binary sequences. For this, the next part of the binary information sequence from the first to the kth bit is written in parallel to the first memory cell shift register of length k + r bits. Check characters in the form of a binary sequence of length r bits are written in parallel to the subsequent, starting from k + 1, memory cells of the same shift register. As a result, the next part of the error-correcting sequence of length k + r bits is recorded in the shift register. For example, the first part of the error-correcting sequence (PP) has the form “111”, the second part is “101”, the third part is “011”, as shown in FIG. 5 (c).

The methods of arithmetic coding of the next part of the error-correcting sequence into the next part of the encoded sequence are known and described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin, “Data compression methods. Archiver device, image and video compression”. - M.: DIALOGUE-MEPhI, 2002, p. 35-43. They consist in sequentially compressing the binary symbols of the next part of the error-correcting sequence into the next part of the encoded sequence in accordance with the current values of the coding interval of the arithmetic coding and the current values of the probabilities of the encoded zero characters and single characters. As binary symbols are input to the input, the number of coding zero characters and the number of single coding characters are calculated, proportionally to which the coding interval of the arithmetic coding is divided into the coding sub-interval of the zero character and the coding sub-interval of a single character, according to which the arithmetic encoder sequentially generates an encoded sequence (CP).

When the next binary symbol arrives at the input of the arithmetic coding of the next part of the error-correcting sequence, which is a single binary symbol, the current encoding interval of this symbol is set equal to the previous encoding sub-interval of a single symbol, and when the binary symbol enters the arithmetic encoding input, the current encoding interval of this symbol is set equal to previous sub-interval of a null character. For example, when the first binary character of the first part of the error-correcting sequence, which is a single binary character, arrives at the input of the arithmetic coding, the lower value of the encoding interval of the first character L [1] is set to the value of Q, for example, 127, and the upper value of the encoding interval of the first character of the arithmetic encodings H [1] are set equal to the initial upper value of the arithmetic encoding encoding interval H [0], for example, equal to 255, as shown in FIG. 3 and in FIG. 4 at t = 1.

The leftmost bit of the binary representation of the value L [1] is compared with the leftmost bit of the binary representation of the value H [1], for example, of the form 01111111 and 11111111, respectively, as shown in FIG. 3 at t = 1. If they do not match, they proceed to the arithmetic coding of the next character.

и текущее значение вероятности кодируемых единичных

. В соответствии с этим длина подинтервала нулевого символа D₀[1] становится в 2 раза меньше длины подинтервала единичного символа D₁[1], а параметр Q принимает значение 170, как показано на фиг. 3, вторая строка сверху и на фиг. 4 при t=1.After arithmetic coding of each successive character, the number of encoded null characters and single characters is specified. Since the first encoded character is single, the number of encoded single characters is increased by a single value and it is N ₁ [1] = 2, and the number of encoded zero and single characters becomes N [1] = N ₀ [1] + N ₁ [1] = 3. Recalculate the current probability value of encoded null characters

and the current probability value of the encoded units

. Accordingly, the length of the sub-interval of the null symbol D ₀ [1] becomes 2 times less than the length of the sub-interval of a single symbol D ₁ [1], and the parameter Q takes on the value 170, as shown in FIG. 3, the second row from above and in FIG. 4 at t = 1.

Upon receipt of the input of the arithmetic coding of the second character, which is a single binary character, the lower value of the coding interval of the second character L [2] is set equal to the value of Q, for example, 170, and the upper value of the coding interval of the second character of the arithmetic coding H [2] is set to the upper value of the coding interval of the arithmetic coding H [1], for example, equal to 255, as shown in FIG. 3 at t = 2.

и текущее значение вероятности кодируемых единичных символов

. В соответствии с этим длина подинтервала нулевого символа D₀[2] становится в 3 раза меньше длины подинтервала единичного символа D₁[2], как показано на фиг. 3, третья строка сверху и на фиг. 4 при t=2.After arithmetic coding of each successive character, the number of encoded null characters and single characters is specified. Since the second compressed symbol is single, the number of encoded single characters is increased by a single value and it is N ₁ [2] = 3, and the number of encoded zero and single characters becomes N [2] = N ₀ [2] + N ₁ [2] = 4. Recalculate the current probability value of encoded null characters

and the current probability value of the encoded unit characters

. Accordingly, the length of the sub-interval of the null symbol D ₀ [2] becomes 3 times less than the length of the sub-interval of a single symbol D ₁ [2], as shown in FIG. 3, the third row from above and in FIG. 4 at t = 2.

The leftmost bit of the binary representation of the value L [2] is compared with the leftmost bit of the binary representation of the value H [2], for example, of the form 10101001 and 11111111, respectively, as shown in FIG. 3 at t = 2. When they coincide, the value of the leftmost bit of the binary representations of the values L [2] and H [2] is read as the next bit of the compressed sequence (code symbol in Fig. 3). For example, when encoding the first part of the error-correcting sequence, the first bit of the first part of the encoded sequence is the matching binary symbol as compared, as shown in FIG. 3, the fourth line from the top. The read bit is removed from the binary representations of the values L [2] and H [2], which are reduced to a length of 7 bits of the form 0101001 and 1111111, respectively. Binary symbols of binary representations of the values of L [2] and H [2] are shifted from right to left by one digit and are added to the right by a zero binary symbol. For example, binary representations of the values L [2] and H [2] take the form 01010010 and 11111110, respectively. Methods for reading binary characters with the removal of read characters are known and described, for example, in the book: V. Shilo "Popular digital circuits." - M .: Radio and communication, 1987, 104-123, using shift registers with parallel and sequential write / read of binary sequences. The operations of shifting from right to left by one bit and appending a binary binary symbol to the right increase the values of L [2] and H [2] by 2 times and are called normalization of arithmetic coding parameters. Methods of shifting one bit in the direction of the higher bits of binary sequences and writing to the freed low order of the zero binary symbol are known and described, for example, in the book: V. Shilo "Popular Digital Circuits". - M .: Radio and communications, 1987, 104-123, using shift registers with parallel and sequential write / read of binary sequences, and in essence are multiplication by two decimal values of the lower and upper values of the encoding interval.

After each normalization run, the leftmost bit of the binary representation of the lower value of the encoding interval is compared again with the leftmost bit of the binary representation of the upper value of the encoding interval. If they coincide, the value of the leftmost bit of these binary representations is read as the next bit of the encoded sequence, otherwise they proceed to the encoding of the next character and so on, as shown in FIG. 3.

For example, when the second binary symbol of the second part of the error-correcting sequence, which is a zero binary symbol, arrives at the input of the arithmetic encoding, the lower value of the current encoding interval L [5] of this symbol, which is the fifth in a row, is set equal to the lower value of the previous encoding subinterval of the zero symbol, equal to for example, 44, and the upper value of the current coding interval of this symbol H [5] is set equal to the value Q, numerically equal to, for example, 79, as shown in FIG. 3 and in FIG. 4 at t = 5.

The arithmetic coding of the selected check symbols that are part of the next part of the error-correcting sequence does not differ from the arithmetic coding of information sequence symbols.

An approximate form of arithmetic coding of the first six successive parts of an error-correcting sequence of the form "111", "101", "011", "101", "111" and "001" into the corresponding subsequent parts of the encoded sequence of the form "1", "10", " 0111 "," 010 "," 1 "and" 001 "are shown in FIG. 5 (g).

Methods of transmitting to the receiving side the next part of the encoded sequence are known and described, for example, in the book of A.G. Zyuko, D.D. Klovsky, M.V. Nazarov, L.M. Fink "Theory of signal transmission." - M .: Radio and communications, 1986, p. 11. An exemplary view of the first six parts of the received sequence (Pr. P) is shown in FIG. 6 (a). The received sequence during transmission is distorted in the third bit and has the form "1", "11", "0111", "010", "1", "001".

The algorithm for joint arithmetic and error-correcting decoding at the receiving side is shown in FIG. 7.

Methods of storing the next parts of the received sequence are known and described, for example, in the book: V. Shilo "Popular Digital Circuits". - M .: Radio and communication, 1987, pages 104-123, using shift registers with parallel and sequential write / read of binary sequences.

, текущее значение вероятности декодируемых единичных символов pp₁[t] вычисляют по формуле вида

, где NN[t] - текущее число декодированных нулевых и единичных символов, равное NN[t]=NN₀[t]+NN₁[t]. Соответственно, длину текущего подинтервала декодирования единичного символа DD₁[t] определяют по формуле вида DD₁[t]=II[t]×pp₁[t], a длину текущего подинтервала декодирования нулевого символа DD₀[t] определяют по формуле вида DD₀[t]=II[t]-DD₁[t], где II[t] - длина текущего интервала арифметического декодирования.The methods for dividing the current arithmetic decoding interval into the current null symbol decoding subinterval and the current decoding subinterval of a single character are identical to the methods for dividing the current arithmetic decoding subinterval into the current null character encoding subinterval and the current single character encoding subinterval. Accordingly, the current decoding interval of a single symbol is located above the current decoding interval of a null symbol, as shown, for example, in FIG. 8 and FIG. 9. The upper boundary of the current decoding interval of the null symbol is denoted as the QQ value, and this sub-interval starts from the bottom of the current boundary of the decoding interval to the QQ value exclusively, and the current decoding interval of a single symbol extends from the QQ value inclusive to the upper boundary of the current decoding interval exclusively. Similarly to arithmetic coding, after the decoding of each successive symbol, the current number NN ₀ [t] of decoded zero characters and the current number NN ₁ [t] of decoded single characters are specified. After decoding t symbols, the current probability value of decoded zero symbols pp ₀ [t] is calculated by the formula of the form

, the current probability value of decoded unit symbols pp ₁ [t] is calculated by the formula of the form

where NN [t] is the current number of decoded zero and one characters equal to NN [t] = NN ₀ [t] + NN ₁ [t]. Accordingly, the length of the current decoding sub-interval of a single symbol DD ₁ [t] is determined by a formula of the form DD ₁ [t] = II [t] × pp ₁ [t], and the length of the current decoding sub-interval of a zero character DD ₀ [t] is determined by a formula of the form DD ₀ [t] = II [t] -DD ₁ [t], where II [t] is the length of the current arithmetic decoding interval.

Identical to arithmetic coding, set the initial number of decoded zero characters to NN ₀ [0] = 1, and the initial number of decoded single characters to NN ₁ [0] = 1, that is, the initial probability values of decoded single and zero characters are set to: pp ₁ [0] = pp ₀ [0]. An example of the initial state of arithmetic decoding is shown in FIG. 8 at t = 0.

Methods for arithmetic decoding of remembered successive parts of a received sequence into successive parts of a decoded sequence are known and described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin, “Data compression methods. Archiver device, image and video compression”. - M.: DIALOGUE-MEPhI, 2002, p. 35-43. They consist in sequential decoding of the next parts of the received sequence in accordance with the current values of the decoding interval of the arithmetic decoding and the current values of the probability of decoded zero characters and single characters.

The unit symbol decoding sub-interval is located on top of the null character decoding sub-interval. The upper limit of the null-symbol decoding interval is designated as the QQ value, and this sub-interval starts from the bottom of the lower boundary of the arithmetic coding decoding interval to the QQ value exclusively, and the unit decoding interval of the single symbols extends from the QQ value inclusive to the upper limit of the arithmetic decoding decoding interval exclusively. The initial QQ value has a decimal value of 127, as shown in FIG. 8 in the first row and in FIG. 9 at t = 0.

An exemplary arithmetic decoding of the memorized successive parts of the received sequence of the type “11101110101001” into the next parts of the decoded sequence distorted in the third bit is shown in FIG. 8 and FIG. 9.

The arithmetic decoding input receives a part of the received sequence of length R bits equal to the bit depth of the arithmetic coding and decoding operations. Initially, the first 8 bits of the form “11101110” are read in turn at the input of arithmetic decoding, which corresponds to the decimal number 238. The current read bits (count) are shown in the second column, the third value of the same sequence is shown in the third column of the same figure (Input data) and the place of the current value of the read sequence relative to the current decoding sub-intervals is shown in the form of an arrow in FIG. 9. The current value of the read sequence is compared with the boundaries of the initial value of the decoding subinterval of the zero characters DD ₀ [0], which are, for example, in the range from 0 to 127 and with the boundaries of the initial values of the subinterval of the decoding subinterval of the single characters D ₁ [0], located, for example, ranging from 127 to 255. Depending on the limits within which the character decoding sub-interval the current value of the read sequence has turned out, a decision is made on the value of the current character of the decoded sequence.

For example, since the current value of the read sequence turned out to be greater than the QQ value (238> 127), the first decoded symbol is single and the following boundaries of the decoding interval are set to the corresponding limits of the value of the decoding sub-interval of single characters DD ₀ [0]. As a result of decoding the first symbol, the lower value of the decoding interval of the arithmetic coding LL [1] is set to QQ, for example, LL [1] = 127, and the upper value of the decoding interval of the arithmetic coding HH [1] is equal to the previous value of HH [0], for example , HH [1] = 255, as shown in FIG. 8 in the second line at t = 1.

и по формуле вида

, соответственно. Устанавливают текущее значение QQ и текущие подинтервал декодирования единичных символов и подинтервал декодирования нулевых символов, как показано на фиг. 8 и на фиг. 9.After decoding each symbol, the current probability value of the decoded zero characters and the current probability value of the decoded zero characters are recalculated, for example, after decoding the first character that is single, according to the formula

and according to the formula of the form

, respectively. The current QQ value and the current decoding interval of single symbols and the decoding interval of zero symbols are set, as shown in FIG. 8 and in FIG. 9.

After each change in the arithmetic decoding state, the leftmost bit of the binary representation of the LL value is compared with the leftmost bit of the binary representation of the HH value, for example, at t = 2 of the form “10101001” and “11111111”, respectively. If they coincide, the arithmetic decoding is normalized: the value of the leftmost bit of the binary representations of the LL and LV values is removed and the binary symbols of the binary representations of the LL and LV values are shifted from right to left by one digit and appended to the lower order by the binary binary symbol. At the same time, the value of the leftmost bit of the read sequence is deleted and the binary characters of the read sequence are shifted from right to left by one bit and the next read binary symbol of the received sequence is added to them, for example, the ninth character of the received sequence, which is a single character, as shown in FIG. 8 in the fourth line above the "normalization". Taking into account the added binary character, the read sequence acquires the binary representation "11011101" and the decimal value 221. The variable LL takes the decimal value 82 and the binary representation "01010010", and the HH decimal value 254 and the binary representation "11111110". Again, the leftmost bit of the binary representation of the LL value is compared with the leftmost bit of the binary representation of the HH value, and if they coincide again, they perform normalization again in the same way, etc.

As a result of arithmetic decoding of the first eleven characters of the error-received sequence, the first to fifth part of the decoded sequence (DP) is decoded, having, for example, the form “1P”, “1P”, “111”, “111” and “101”, as shown for example in FIG. 6 (b) and in FIG. 8 and FIG. 9.

Methods for extracting from the next part of the decoded sequence the next part of the reconstructed information sequence and decoded check symbols are known and described, for example, in the book by V. Shilo "Popular Digital Circuits". - M .: Radio and communication, 1987, 104-123, using shift registers with parallel and sequential write / read of binary sequences. The next part of the decoded sequence is sequentially recorded in the memory cells of the shift register of length k + r bits. From the first memory cells of this shift register, the next part of the reconstructed information sequence of length k bits is read in parallel. From the subsequent, starting from k + 1, memory cells of the same shift register, decoded check symbols of r bit length are read in parallel. For example, from the first part of the DP of the type "111", the first part of the restored information sequence (VIP) of the type "11" and the decoded verification symbol of the type "1" are extracted.

If the current decoding sub-interval of each of the decoded check symbols includes the middle of the initial arithmetic coding interval, then a conclusion is made that there are no transmission errors. For example, the first decoded check symbol is a single character and its current decoding sub-interval is the current decoding sub-interval of a single character, including values from 125 to 254. This decoding sub-interval includes the middle of the initial arithmetic coding interval corresponding to S = 127. Therefore, an existing transmission error was not detected when checking the first decoded check symbol. Similarly, an existing transmission error was not detected during the subsequent verification of the second, third and fourth decoded check symbols. When decoding the fifth check symbol, the corresponding single character decoding subinterval, including values from 110 to 119, does not include the value S = 127 of the middle of the initial arithmetic coding interval, which unambiguously indicates the detection of a transmission error. For example, an error in the third character of the received sequence was detected while decoding the fifteenth character of the decoded sequence.

To correct transmission errors, one or more bits are inverted in turn in the remembered successive parts of the received sequence. Methods for inverting bits in the stored next parts of the received sequence are known and described, for example, in the book by W. Shilo "Popular digital circuits." - M .: Radio and communications, 1987, 104-123, using shift registers with parallel writing / reading of binary sequences and binary inverters. The invertible bit from the shift register is read in parallel to the inverter input and from the inverter output is written in parallel to the same shift register memory cell.

For example, in the stored received sequence, the first bit is inverted (In1. Pr.P) and the first four parts of the stored received sequence take the form “0110111010” shown in FIG. 6 (c). The arithmetic decoding order of the stored received sequence with the inverted first bits is shown in FIG. 10. As a result of the arithmetic decoding of In1.Pr.P, the first part of the decoded sequence is decoded with the inverted first bit (DP1) having, for example, the form “011”, as shown, for example, in FIG. 6 (d) and in FIG. 10. When checking the first decoded check character, the corresponding single character decoding subinterval, including values from 167 to 252, does not include the value S = 127 of the middle of the initial arithmetic coding interval, which unambiguously indicates the detection of a transmission error.

Since the inversion of the first bit of the received sequence did not correct the transmission error, the second bit is inverted in the stored received sequence (In2. Pr.P) and the first four parts of the stored received sequence take the form "1010111010" shown in FIG. 6 (d). The arithmetic decoding order of the stored received sequence with the inverted second bits is shown in FIG. 11. As a result of the arithmetic decoding of In2.P.R, the first part of the decoded sequence is decoded with the inverted second bit (DP2) having, for example, the form “110”, as shown, for example, in FIG. 6 (e) and in FIG. 11. When checking the first decoded check character, the corresponding single character decoding subinterval, including values from 84 to 127 exclusively, does not include the value S = 127 of the middle of the initial arithmetic coding interval, which unambiguously indicates the detection of a transmission error.

Since inverting the second bit of the received sequence did not correct the transmission error, the third bit (In3. Pr.P) is inverted in the stored received sequence and the first parts of the stored received sequence take the form "11001110101001" shown in FIG. 6 (g). The arithmetic decoding order of the stored received sequence with the inverted third bits is shown in FIG. 12. As a result of the arithmetic decoding of In3.Pr.P, the first, second and partially third parts of the decoded sequence are decoded with the inverted third bit (DPS) having, for example, the form “111”, “101”, “01 ..”, as shown for example in FIG. 6 (h), FIG. 13 and FIG. 14. When checking the first and second decoded check symbols (DPS) shown in FIG. 6 (i), the corresponding current unit symbol decoding sub-intervals thereof include the value S = 127 of the middle of the initial arithmetic coding interval, based on which it is concluded that there are no transmission errors.

If there are no transmission errors, the next part of the restored information sequence, for example, the first part of the restored information sequence of the form “11” shown in FIG. 6 (k), receive the next part of the received sequence, etc.

The differences between the second variant of the method of joint arithmetic and noise-resistant coding from the first variant of the method are in the selection of test symbols in terms of the probability of information sequence symbols.

Timing diagrams of joint arithmetic and error-correcting coding of the first six consecutive parts of an information sequence of the form "11", "10", "01", "10", "11" and "00" when selecting test symbols for the probability of information sequence symbols are shown in FIG. 14. The state table of joint arithmetic and noise-tolerant coding of data of parts of the information sequence when selecting test symbols for the probability of the symbols of the information sequence is shown in FIG. 15. Compared to the previously described first option, the number of encoded zero and single characters of the information sequence and check characters is calculated separately and together. To do this, set the values of the initial number of encoded zero characters of the information sequence, for example, Ninf ₀ [0] = 1 and the initial number of encoded single characters of the information sequence, for example, Ninf ₁ [0] = 1, and as described earlier, calculate the probability of the encoded zero characters information sequence pinf ₀ and the probability of encoded single characters of the information sequence pinf ₁ . At the same time, the values of the initial number of encoded zero check symbols, for example, Nproν ₀ [0] = 1 and the initial number of encoded single check symbols, for example, Nproν ₁ [0] = 1, are set, and in the same way, the probability of the encoded zero check symbols pproν _{1 is} calculated . and the probability of encoded unit check symbols pproν ₁ . Then, the initial number of all encoded zero characters is calculated by summing the initial number of encoded zero characters of the information sequence and the initial number of encoded zero check characters, for example, символов _∑0 [0] = Ninf ₀ [0] + Nproν ₀ [0] = 1 + 1 = 2 and the initial number of all encoded unit characters by summing the initial number of encoded unit characters of the information sequence and the initial number of encoded unit check characters, for example, Ν _∑1 [0] = Ninf ₁ [0] + Npr oν ₁ [0] = 1 + 1 = 2. The probability of all coded zero characters p _{∑ 0} and the probability of all coded single characters p _{∑ 1} are previously calculated in the manner described. The obtained values are recorded, for example, when each character is encoded sequentially from top to bottom for information sequence symbols, for verification symbols, and for all symbols, as shown in FIG. 15. The current arithmetic coding interval is divided into the current null character encoding subinterval and the single character encoding subinterval in accordance with the probability of all coded zero characters p _{∑ 0} and the probability of all coded single characters p _{∑ 1} .

The selection of the next test characters in terms of the probability of the characters of the information sequence is as follows. Let the probability of encoded zero characters of the information sequence pinf ₀ [t] and the probability of encoded single characters of the information sequence pinf ₁ [t] be calculated at the t-th moment of time, and the probability of encoded zero check characters pproν ₀ [t -1] and the probability of encoded unit check symbols pproν ₁ [t-1]. If the next check character has a zero value, then the probability of encoded zero check characters at a zero value of the next check character will take the value pproν _{0 at 0} [t], and if the next check character will have a single value, then the probability of the coded zero check characters at a single value the next check character will take the value pproν _{0 at 1} [t]. Of the two possible variants of the values of the next verification symbol, choose the value that provides the probability value of the encoded verification symbols closest to the probability value of the encoded symbols of the information sequence. To do this, calculate the difference value pinf ₀ [t] -pproν _{0 at 0} [t] and the difference value pinf ₀ [t] -pproν _{0 at 1} [t] and compare them in absolute value. If the first value of the difference is less than or equal to the second value of the difference, then select the next test character with a zero value, otherwise select the next test character with a single value. For example, as shown in FIG. 15, at time t = 3, after encoding the first two information symbols, the first verification symbol is selected. At this moment, the probability of encoded null characters of the information sequence is pinf ₀ [3] = 1/4 and the probability of encoded single characters of the information sequence is pinf ₁ [3] = 3/4, and the probability of encoded zero characters of the information sequence is pproν ₀ [2] = 1 / 2 and the probability of encoded unit check symbols pproν ₁ [2] = 1/2. If the first check character takes a zero value, then pproν ₀ [3] = 2 / 3≈0.67, and if the first check character takes a single value, then pproν ₀ [3] = 1 / 3≈0.33. The difference value pinf ₀ [3] -pproν _{0 at 0} [3] = 1 / 4-2 / 3≈-0.42 and the difference value pinf ₀ [3] -pproν _{0 at 1} [3] = 1 / 4- are calculated 1/3 = -0.08. The absolute value of the second value of the difference is less, so choose the next test character as a single character, while the current value of the probability of the test characters will be closest to the current value of the probability of the characters of the information sequence.

An exemplary view of the selected check symbols for the first six successive parts of the error-correcting sequence is shown in FIG. 14 (b), and the next parts of the error-correcting sequence formed with their use are shown in FIG. 14 (c). An approximate form of arithmetic coding of the first six successive parts of an error-correcting sequence of the form "111", "100", "010", "101", "111" and "000" into the corresponding subsequent parts of the encoded sequence of the form "11", "0111", " 100 "," 10 "and" 1001 "is shown in FIG. 14 (g).

An exemplary view of the first six parts of the received sequence (Ex. P) is shown in FIG. 16 (a). The received sequence during transmission is distorted in the second bit and has the form "10", "_", "0111", "100", "10" and "1001".

It is identical to how, when encoding, the values of the number of encoded symbols of the information sequence and their probability, the number of encoded test symbols and their probability, the number of all encoded symbols and their probability are calculated, when decoding, the values of the number of decoded zero and single symbols of the information sequence NNinf ₀ and NNinf _{1 are} calculated , and their probabilities ppinf ₀ and ppinf ₁ , the values of the number of decoded zero and unit check symbols NNproν ₀ and NNproν ₁ and their probabilities pp proν ₀ and pp proν ₁ , values of zero, and all the decoded symbols unit ΝΝ _Σ0 and ΝΝ _Σ1 and their probabilities pp _Σ0 and pp _Σ1. The obtained values are recorded, for example, when decoding each symbol sequentially for the symbols of the reconstructed information sequence (above), for decoded verification symbols, and for all decoded symbols (below), as shown in FIG. 17. The current arithmetic decoding interval is divided into the current null symbol decoding sub-interval and the single symbol decoding sub-interval in accordance with the probability of all decoded zero symbols p _{∑ 0} and the probability of all decoded single symbols p _{∑ 1} .

An exemplary arithmetic decoding of the memorized successive parts of the received sequence of the form “100111100101001” into the next parts of the decoded sequence distorted in the second bit is shown in FIG. 17. Due to the error of the received sequence after decoding the second symbol, the current value of the read sequence, equal to 60, was outside the current interval of arithmetic decoding, extending from 82 to 254, which clearly indicates the detection of a transmission error. For example, an error in the second symbol of the received sequence is detected when decoding the second symbol of the decoded sequence, as shown in FIG. 16 (6).

To correct transmission errors, one or more bits are inverted in turn in the remembered successive parts of the received sequence. For example, in the stored received sequence, the first bit is inverted (In1. Pr.) And the first six parts of the stored received sequence take the form “00011110010001” shown in FIG. 16 (c). The decoding order of the stored received sequence with the inverted first bit is shown in FIG. 18. As a result of decoding, In1.Pr.P decodes the first three parts of the sequence with the inverted first bit (DP1), having, for example, the form “000”, “010” and “010”, as shown, for example, in FIG. 16 (d) and in FIG. eighteen.

If the current probability of decoded check symbols as zero or single characters corresponds to a certain arithmetic decoding of the current probability of the symbols of the restored information sequence, then a conclusion is made that there are no transmission errors.

When checking the first decoded check character at time t = 3, the probability of decoded zero characters of the information sequence ppinf ₀ [3] = 3/4 and the probability of decoded single characters of the information sequence ppinf ₁ [3] = 1/4, as well as from the moment of selection of the previous check symbol, the probability of decoded zero check symbols pp proν ₀ [2] = 1/2 and the probability of decoded single check symbols p ppropro ₁ [2] = 1/2 are calculated. The first decoded check symbol has a zero value, and the probability of decoded zero check symbols has taken the value pp proν ₀ [3] = 2/3, as shown in FIG. 18 at t = 3. The difference value ppinf ₁ [3] -pr proν ₀ [3] = 3 / 4-2 / 3≈0.08 and the difference value are calculated if the decoded check character accepts a single value: ppinf ₁ [3] -r proν _{0 at 1} [3] = 3 / 4-1 / 3≈0.42. Obviously, the current probability of the first decoded check symbol as a null symbol corresponds to a certain arithmetic decoding of the current probability of the symbols of the restored information sequence, therefore, when checking the first decoded check symbol, transmission errors were not detected.

No transmission errors were detected when checking the second decoded check character at t = 6, and when checking the third decoded check character at t = 9, the probability of decoded zero characters of the information sequence ppinf ₀ [9] = 5/8 and the probability of decoded single characters of information of the sequence pp inf ₁ [9] = 3/8, and also from the moment of selecting the previous check character, the probability of decoded zero check characters pp proν ₀ [8] = 3/4 and the probability of decoded single check characters are calculated characters pp proν ₁ [8] = 1/4. The third decoded check symbol has a zero value, and the probability of decoded zero check symbols has taken the value pp proν ₀ [9] = 4/5, as shown in FIG. 18 at t = 9. The difference value ppinf ₁ [9] -pr proν ₀ [9] = 5 / 8-4 / 5 = -0.175 and the difference value are calculated if the decoded check character accepts a single value: ppinf ₁ [9] -pr proν _{0 with 1} [9] = 5 / 8-3 / 5 = 0.025. Comparison of the two calculated values in absolute value shows that the current probability of the third decoded check character as a null character does not correspond to a certain arithmetic decoding of the current probability of the characters of the restored information sequence, therefore, when checking the third decoded check character, transmission errors were detected, i.e., the inversion of the first bit of the received sequence does not led to the correction of transmission errors.

Therefore, in the stored received sequence, the second bit (In2. Pr.P) is inverted and the first six parts of the stored received sequence take the form "11011110010001" shown in FIG. 16 (d). The decoding order of the stored received sequence with the inverted second bit is shown in FIG. 19. As a result of decoding, In2.P.P completely decodes the first three parts of the sequence with the inverted second bit (DP2), having, for example, the form “111”, “100” and “010”, as shown, for example, in FIG. 16 (e) and in FIG. 19. When checking decoded check symbols shown, for example, in FIG. 16 (g), it was revealed that their current probability corresponds to a certain arithmetic decoding of the current probability of the symbols of the restored information sequence, therefore, there are no transmission errors. If there are no transmission errors, the next part of the restored information sequence, for example, the first part of the restored information sequence of the form “11” shown in FIG. 16 (h).

The differences of the third variant of the method of joint arithmetic and noise-resistant coding from the first variant of the method are in the selection of test symbols for the predominance of symbols of the information sequence.

Timing diagrams of joint arithmetic and noise-resistant coding of the first five successive parts of the information sequence of the form "11", "10", "01", "10", "11" and "00" when selecting test characters for the predominance of information sequence symbols are shown in FIG. 20. The state table of joint arithmetic and noise-resistant coding of data of parts of the information sequence when selecting test symbols for the predominance of information sequence symbols is shown in FIG. 21. Compared with the previously described first option, separately count the number of encoded zero and single characters of the information sequence and together count the number of encoded zero and single characters of the information sequence and check characters. To do this, set the values of the initial number of encoded zero characters of the information sequence, for example, Ninf ₀ [0] = 1 and the initial number of encoded single characters of the information sequence, for example, Ninf ₁ [0] = 1, and as described earlier, calculate the current probability of the encoded zero characters of the information sequence pinf ₀ and the current probability of encoded single characters of the information sequence pinf ₁ .

The current value of the number of all encoded null characters is also calculated by summing the current number of encoded null characters of the information sequence and the current number of encoded null check characters when selected, for example, Ν _∑0 [t] = Ninf ₀ [t] + Nproν ₀ [t] and the current number of all encoded unit characters by summing the current number of encoded unit characters of the information sequence and the current number of encoded unit check characters when selected, for example, N _{∑ 1} [t] = Ninf ₁ [t] + Nproν ₁ [t]. Manner previously described current calculated probability of all encoded symbols of zero p _Σ0 [t] and the probability of the current encoded symbol unit p _Σ1 [t]. The obtained values are recorded, for example, when each character is encoded sequentially from top to bottom for information sequence symbols and for all symbols, as shown in FIG. 21. Separate the current interval arithmetic coding to encode the current subinterval zero symbol and the current symbol subinterval coding unit according to the probability of the current encoded zero symbols p _Σ0 [t] and the probability of the current encoded symbol unit p _Σ1 [t].

The selection of the next test characters for the predominance of the characters of the information sequence is as follows. Suppose that before the t-th point selection verification symbol time computed probability zero symbols encoded information sequence pinf ₀ [t-1] and probability characters encoded information unit sequence pinf ₁ [t-1], and the calculated probability of all encoded symbols of zero p _Σ0 [t-1] and the probability of all encoded unit characters p _∑1 [t-1]. If a relation of the form pinf ₀ [t-1] ≥pinf ₁ [t-1] holds, then the zero character of the information sequence prevails and the next check character is selected as having a zero value, otherwise the single character of the information sequence prevails and the next check character is selected as having a single value. For example, as shown in FIG. 21, at time t = 3, after encoding the first two information symbols, the first verification symbol is selected. At this point, the probability of encoded zero characters of the information sequence is pinf ₀ [2] = 3/4 and the probability of encoded single characters of the information sequence is pinf ₁ [2] = 1/4. Due to the predominance of zero characters in the information sequence, the next check character is selected as having a zero value. For symbols of the information sequence, the probability values do not change: pinf ₀ [3] = pinf ₀ [2] = 3/4 and pinf ₁ [3] = pinf ₁ [2] = 1/4, and the probability of all encoded zero characters and the probability of all encoded unit characters get the values p _∑1 [t] = _4/5 and p _∑0 [t] = _1/5 , respectively, etc.

An exemplary view of selected check symbols for the first five successive parts of the error-correcting sequence is shown in FIG. 20 (b), and the subsequent parts of the error-correcting sequence formed with their use are shown in FIG. 20 (b). An approximate form of arithmetic coding of the first five successive parts of an error-correcting sequence of the form "000", "010", "010", "000" and "100" into the corresponding subsequent parts of the encoded sequence of the form "00", "1", "011", " _ "and" 100001 "are shown in FIG. 20 (g). An exemplary view of the first five parts of the received sequence (Ex. P) is shown in FIG. 22 (a). The received sequence during transmission is distorted in the second bit and has the form "01", "1", "011", "_" and "100001". An example of decoding distorted in the second bit stored next parts of a received sequence of the form “011011100001” into next parts of a decoded sequence is shown in FIG. 23.

It is identical to how, when encoding, the values of the number of encoded symbols of the information sequence and their probability, the number of all encoded symbols and their probabilities are calculated, when decoding, the values of the number of decoded zero and single symbols of the information sequence NN inf ₀ and NN inf ₁ and their probabilities pp inf _{0 1} and pp inf values of all zeros and decoded symbols unit ΝΝ _Σ0 and ΝΝ _Σ1 and their probabilities pp _Σ0 and pp _Σ1. The obtained values are recorded, for example, when decoding each symbol sequentially for the symbols of the reconstructed information sequence (above) and for all decoded symbols (below), as shown in FIG. 23. Divide the current arithmetic decoding interval into the current null-symbol decoding sub-interval and the current single-symbol decoding sub-interval in accordance with the probability of all decoded zero characters p _{∑ 0} and the probability of all decoded single characters p _{∑ 1} .

An exemplary type of decoding of the memorized successive parts of the received sequence of the type “011011100001” into the first part of the decoded sequence of the type “011” distorted in the second bit is shown in FIG. 23.

Check for the absence of transmission errors as follows: if the decoded check symbols are zero characters, provided that the arithmetic decoding current probability of zero characters of the restored information sequence is greater than or equal to the current probability of single characters in this sequence, or the decoded check characters are single characters, provided that arithmetic decoding current probability of single characters the reconstructed information sequence is greater than the current probability of zero characters of this sequence, then conclude that there are no transmission errors.

For example, the first decoded check symbol is a single symbol, as shown in FIG. 23 at t = 3. The current probability of unit symbols of the restored information sequence determined by arithmetic decoding is equal to ppinf ₁ [3] = 2/4 and equal to the current probability of zero symbols of this sequence is equal to ppinf ₀ [3] = 2/4. According to the above condition, the first decoded check symbol must be a null symbol, therefore, transmission errors are detected.

To correct transmission errors, one or more bits are inverted in turn in the remembered successive parts of the received sequence. For example, in the stored received sequence, the first bit is inverted (In1. Pr.P) and the first five parts of the stored received sequence take the form “111011100001” shown in FIG. 22 (c). The decoding order of the stored received sequence with the inverted first bit is shown in FIG. 24. As a result of decoding In1.Pr.P decode the first five parts of the sequence with the inverted first bit (DP1), having, for example, the form "111", "111", "111", "111" and "100", as shown for example in FIG. 22 (d) and in FIG. 24. An error is detected in the fifth decoded check symbol, which is a null symbol, as shown in FIG. 24 at t = 15. The current probability of unit symbols of the reconstructed information sequence determined by arithmetic decoding is ppinf ₀ [15] = 3/13 and less than the current probability of unit symbols of this sequence equal to ppinf ₁ [15] = 10/15. In accordance with the above condition, the fifth decoded check symbol must be a single symbol, therefore, transmission errors are detected.

Therefore, in the stored received sequence, the second bit (In2. Pr.P) is inverted and the first five parts of the stored received sequence take the form “001011100001” shown in FIG. 22 (d). The decoding order of the stored received sequence with the inverted second bit is shown in FIG. 25. As a result of decoding, In2.P.P completely decodes the first two parts of the sequence with the inverted second bit (DP2) having, for example, the form “000” and “010”, as shown, for example, in FIG. 22 (e) and in FIG. 25. When checking decoded check symbols shown, for example, in FIG. 22 (g), it was revealed that they correspond to the prevailing in the current probability symbols of the restored information sequence, therefore, there are no transmission errors. If there are no transmission errors, the next part of the restored information sequence, for example, the first part of the restored information sequence of the form “00” shown in FIG. 22 (h).

Verification of the theoretical background of the claimed variants of the method of joint arithmetic and noise-correcting coding was verified by its analytical studies.

Joint arithmetic and error-correcting coding of several successive parts of the information sequence was performed using the prototype method and variants of the proposed method, the results are shown in FIG. 26. A joint arithmetic and error-correcting coding of N = 1024 consecutive parts of the information sequence of 2 bits in length was carried out using 1-bit verification characters. The subsequent parts of the binary information sequence were subjected to coding with the probability of zero characters being 0.3, 0.2, 0.1, 0.01, and 0.005, respectively. The compressed sequence transmitted over the transmission channel was randomly distorted by one error. At the receiving side, the probability of error detection and the average error detection delay, calculated as the number of decoded symbols from the moment of transmission channel error to the moment of its detection, were calculated. The claimed variants of the method of joint arithmetic and noise-resistant coding provide a significant increase in the compression ratio of redundant information sequences in comparison with the prototype method for all values of the probability of a zero symbol. For comparison, the results of compression of redundant information sequences by arithmetic coding without noise-resistant coding are also obtained. In FIG. 26 shows that the third variant of the method of joint arithmetic and noise-resistant coding provides compression values close to the values of the compression coefficient of arithmetic coding without noise-resistant coding.

The claimed first variant of the method of joint arithmetic and noise-resistant coding provides a higher probability of detecting errors in comparison with the second and third options, but is inferior to the second option in the average delay of error detection and the third option in the achieved compression ratio. The second variant of the method of joint arithmetic and noise-resistant coding provides the smallest average delay of error detection, and the third version of the method of joint arithmetic and noise-resistant coding provides the largest compression ratio among the claimed variants.

The conducted studies confirm that when using the proposed variants of the method of joint arithmetic and noise-resistant coding of an excess binary information sequence, a reduction in the transmission rate of the encoded sequence over the transmission channel or a decrease in the capacity of its storage devices is provided.

Claims (3)

1. The method of joint arithmetic and noise-resistant coding, which consists in the fact that the initial arithmetic coding interval is set on the transmitting side and the initial arithmetic decoding interval corresponding to it is received on the receiving side, the next part of the information sequence of k≥1 bit length is received on the transmitting side divide the current arithmetic coding interval into the current null symbol coding sub-interval and the current the encoding interval of a single symbol, test characters of length r≥1 bits are selected, the next part of the error-correcting sequence is formed from the next part of the information sequence and the selected test symbols, arithmetic coding of the next part of the error-correcting sequence to the next part of the coded sequence is transmitted to the receiving side, perform the listed actions on the transmitting side until the next As part of the information sequence, on the receiving side, receive the next part of the received sequence, which is stored, divide the current arithmetic decoding interval into the current decoding sub-interval of a single character and the current decoding sub-interval of a single symbol, the remembered subsequent parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, of which separate the next parts of the restored information sequence and de encoded check characters, make a conclusion about the absence of transmission errors and transmit to the recipient the next part of the restored information sequence, otherwise they invert one or more bits in the memorized next parts of the received sequence and perform their arithmetic decoding until reaching the conclusion that there are no transmission errors, perform the above actions on the receiver side until the next part of the received sequence arrives, characterized in that on transmitting On the other side, the test characters are selected by highlighting for each test character among the current null character encoding sub-interval and the current character encoding sub-interval the current sub-interval including the middle of the initial arithmetic coding interval, and set the character that matches the selected current sub-interval with the test character, transmit the next part of the coded sequence on the receiving side, and on the receiving side, if the current sub-interval is decoded tions of each of the decoded middle parity includes initial interval arithmetic coding, it concluded the absence of transmission errors. 2. The method of joint arithmetic and noise-resistant coding, which consists in the fact that the initial arithmetic coding interval is set on the transmitting side and the initial arithmetic decoding interval corresponding to it is set on the receiving side, the next part of the information sequence of k≥1 bit length is received from the information source divide the current arithmetic coding interval into the current null symbol coding sub-interval and the current the encoding interval of a single symbol, test characters of length r≥1 bits are selected, the next part of the error-correcting sequence is formed from the next part of the information sequence and the selected test symbols, arithmetic coding of the next part of the error-correcting sequence to the next part of the coded sequence is transmitted to the receiving side, perform the listed actions on the transmitting side until the next As part of the information sequence, on the receiving side, receive the next part of the received sequence, which is stored, divide the current arithmetic decoding interval into the current decoding sub-interval of a single character and the current decoding sub-interval of a single symbol, the remembered subsequent parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, of which separate the next parts of the restored information sequence and de encoded check characters, make a conclusion about the absence of transmission errors and transmit to the recipient the next part of the restored information sequence, otherwise they invert one or more bits in the memorized next parts of the received sequence and perform their arithmetic decoding until reaching the conclusion that there are no transmission errors, perform the above actions on the receiver side until the next part of the received sequence arrives, characterized in that on transmitting On the other side, the verification symbols are selected as zero or single symbols, the current probability of which is closest to the current probability of the information sequence symbols determined by arithmetic coding, the next part of the encoded sequence is transmitted to the receiving side, and on the receiving side, if the current probability of the decoded verification symbols is zero or single symbols corresponds to a certain arithmetic decoding of the current probability of the symbols of the restored information sequence, then conclude that there are no transmission errors. 3. The method of joint arithmetic and noise-resistant coding, which consists in the fact that the initial arithmetic coding interval is set on the transmitting side and the initial arithmetic decoding interval corresponding to it is received on the receiving side, the next part of the information sequence of k≥1 bit length is received on the transmitting side divide the current arithmetic coding interval into the current null symbol coding sub-interval and the current the encoding interval of a single symbol, test characters of length r≥1 bits are selected, the next part of the error-correcting sequence is formed from the next part of the information sequence and the selected test symbols, arithmetic coding of the next part of the error-correcting sequence to the next part of the coded sequence is transmitted to the receiving side, perform the listed actions on the transmitting side until the next As part of the information sequence, on the receiving side, receive the next part of the received sequence, which is stored, divide the current arithmetic decoding interval into the current decoding sub-interval of a single character and the current decoding sub-interval of a single symbol, the remembered subsequent parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, of which separate the next parts of the restored information sequence and de encoded check characters, make a conclusion about the absence of transmission errors and transmit to the recipient the next part of the restored information sequence, otherwise they invert one or more bits in the memorized next parts of the received sequence and perform their arithmetic decoding until reaching the conclusion that there are no transmission errors, perform the above actions on the receiver side until the next part of the received sequence arrives, characterized in that on transmitting on the other side, the verification characters are selected as zero characters, if the current probability of zero characters of the information sequence determined by arithmetic coding is greater than or equal to the current probability of the unit characters of the information sequence, otherwise the test characters are selected as unit characters, the next part of the coded sequence is transmitted to the receiving side, and on the receiving side if the decoded check characters are null characters, provided that a certain arithmetic By decoding the current probability of zero characters of the restored information sequence is greater than or equal to the current probability of the unit characters of this sequence, or the decoded check characters are unit characters, provided that the arithmetic decoding current probability of the unit characters of the restored information sequence is greater than the current probability of the zero characters of this sequence, then conclusion about the absence of transmission errors.

Images