RU2718213C1 - Method of combined arithmetic and antinoise encoding and decoding - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: invention relates to telecommunication and information technologies and can be used for noise-immune encoding and decoding when transmitting information over channels with errors. Method comprises steps of transmitting, at a transmitting side, a next portion of an information sequence (IS), from the current arithmetic coding interval, the current sub-intervals of coding zero and single symbols are selected, from which depending on the previously coded IS symbols, the allowed sub-intervals of coding are selected, in accordance with which performing the arithmetic coding of the next part of IS in the next part of the coded sequence, at the receiving side, storing and continuing no more than Z≥2 alternative adopted sequences (AAS), closest to the Hamming metric to the adopted sequence, AAS is arithmetically decoded with control of conformity of current value of AAS to current permitted sub-intervals of decoding, selecting an alternative adopted sequence with the smallest metric value and decoding successive parts of the recovered information sequence are transmitted to the recipient.

EFFECT: high noise-immunity of transmitting next parts of the coded sequence when subjected to multiple transmission errors.

5 cl, 15 dwg

Description

The claimed technical solution relates to the field of telecommunications and information technology, namely to the technique of compression and recovery of redundant binary information and its noise-resistant coding and decoding when transmitting information on channels with errors.

The claimed invention can be used to ensure the reliability of redundant binary information transmitted over channels with errors.

A known method of adaptive noise-resistant coding and decoding according to the patent of the Russian Federation 2375824 IPC H04 L1 / 20 (2006.01) dated 12/10/2009, which consists in the fact that on the transmitting side the source information is encoded by a noise-resistant code with variable parameters, then the noise-resistant code is transmitted to the communication channel, 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 select variable parameters of the error-correcting code are provided, which provide a predetermined 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 code, evaluate the probability of correct reception of the error-correcting code with the selected parameter trams, 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 value of this deviation, the amount of 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 due to 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 and decoding of voice messages, described, for example, in the book of S. N. 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 of RGRTU, Issue 23, 2008. This method consists in preliminarily generating a variety of speech compression methods, such as pulse-code modulation, adaptive delta modulation, adaptive differential pulse-code modulation, and many noise-resistant coding methods , such as Hamming coding, Bowes-Chowdhury-Hockingham 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 by 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 a 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 select the appropriate method for compressing a speech signal and a noise-resistant coding method.

The closest in technical essence to the claimed method of joint arithmetic and noise-resistant coding and decoding is the method of joint arithmetic and noise-resistant coding and decoding according to US patent 6892343 IPC H04 M13 / 00 (2006.01) dated 05/10/2005. The method is a prototype of joint arithmetic and error-correcting coding and decoding: first, the initial interval of arithmetic encoding 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 length k≥1 is received from the information source bit, divide the current arithmetic coding interval of length D> 2 by the current coding subinterval of zero character D0 and for the current coding sub-interval of a single character D1, from the pre-formed set, test characters of length r≥1 bits 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 to the next part encoded sequence, convert the next part of the encoded sequence in the next hour l modulated sequence, 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, accept the next part of the sequence on the receiving side, convert it to a binary sequence that is stored, share the current interval arithmetic decoding of length DD> 2 to the current sub-interval of decoding the null character DD0 and to the current sub-interval of encoding a single symbol DD1, 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 reconstructed information sequence and the decoded check characters are extracted, if the decoded check characters belong to a pre-formed set of check characters, it is concluded that there are no transmission errors and transmit the next part of the restored information sequentially ti, or alternately inverting one or more bits stored in successive portions of the received sequence and perform their arithmetic decoding until the output of the absence of transmission errors, perform these actions on the reception side as long as the next part of the received sequence received at the receiving side.

A feature of the prototype method is that on the transmitting side, the selection of test characters is performed, and then the subsequent parts of the information sequence and test characters are compressed by arithmetic coding, and on the receiving side after arithmetic decoding, transmission errors are detected if any, and when they are detected by the sample method and errors carry out their correction. The prototype method of the joint arithmetic and noise-resistant coding and decoding provides the ability to detect and correct transmission errors.

However, in this prototype method of joint arithmetic and error-correcting coding and decoding of an information sequence, transmission errors are corrected by enumeration, inverting one or more bits in the remembered successive parts of the received sequence and performing arithmetic decoding until reaching the conclusion on the correction of these errors using check symbols . With a length of N bits of stored successive parts of the received sequence and the number W of correctable errors, this requires parallel operation of the order of N ^W / 2 arithmetic decoders with the corresponding number of error detection devices. When arithmetic decoding of compressed redundant binary sequences, transmission errors are detected with the length of the stored next parts of the received sequence up to tens of bits or more. Therefore, in this prototype method of joint arithmetic and noise-correcting coding and decoding, correction of transmission errors with an error rate of more than one requires the use of many thousands of arithmetic decoders with the corresponding number of error detection devices, which is practically impossible.

Thus, the disadvantage of the closest analogue (prototype) of joint arithmetic and noise-resistant coding and decoding of the information sequence is the low noise immunity of transmission of the next parts of the encoded sequence, due to the practical impossibility of correcting transmission errors with an error rate of more than one.

The technical result of the proposed solution is the development of a method of joint arithmetic and noise-resistant coding and decoding, which provides increased noise immunity of the transmission of the next parts of the encoded sequence when exposed to multiple transmission errors.

The specified technical result in the inventive method of joint arithmetic and noise-resistant coding and decoding is achieved by the fact that in the known method of joint arithmetic and noise-resistant coding and decoding, which consists in the preliminary setting of the initial interval of arithmetic coding on the transmitting side and the corresponding initial interval on the receiving side arithmetic decoding, on the transmitting side from the source of the information sequence take the next part of the information sequence of length k≥1 bits, divide the current arithmetic coding interval of length D> 2 into the current coding sub-interval of a zero character of length D0 and the current coding sub-interval of a single character of length D1, perform arithmetic coding of the next part of the sequence into the next part of the coded sequence, transmit the next part of the sequence to the receiving side, perform the listed actions on the transmitting side until the post the next parts of the information sequence are written, the sequence is received on the receiving side, the current arithmetic decoding interval of length DD> 2 is divided into the current decoding sub-interval of the DD0 zero symbol and the current decoding sub-interval of the single character DD1, the next parts of the received sequence are arithmetically decoded into the next parts of the sequence, the listed actions on the receiving side until the received sequence arrives, transmit to the recipient If the information sequence is set, the limit number Z≥2 of alternative received sequences and the metric value of the alternative received sequences are additionally pre-set to zero.

On the transmitting side, depending on m≥1 previously encoded symbols of information symbols from the current sub-interval of arithmetic coding of a zero symbol of length D0≥2, the current allowed sub-interval of coding of a zero symbol of length D0 _a , where 1≤D0 _a <D0, and from the current coding sub-interval of single characters of length D1≥2 highlight the current allowed coding sub-interval of _a single character of length D1 _a , where 1≤D1 _a <D1. The length D0 _{a of the} current allowed encoding subinterval of the zero symbol is chosen as D0 _a = a ^m ⋅ D0, and the length D1 _{a of the} current allowed subinterval of the encoding of a single symbol is chosen as D1 _a = a ^m ⋅ D1, where the error detection coefficient a is selected within 0 < a <1.

In accordance with the highlighted current allowed coding sub-intervals, arithmetic coding of the next part of the information sequence into the next part of the encoded sequence, which is transmitted to the receiving side, is performed.

The next bit of the sequence is received at the receiving side, the current arithmetic decoding interval of length DD of each alternative received sequence is divided into the current sub-interval of decoding a zero character of length DD0≥2 and the current sub-interval of decoding a single character of length DD1≥2, of which, depending on m characters, the restored information sequences of each alternative received sequence allocate the current allowed null symbol decoding sub-interval for hydrochloric DD0 _a, where 1≤DD0 _a <DD0, and accordingly, the current subinterval permitted symbol length decoding unit DD1 _a, where 1≤DD1 _a <DD1. The length DD0 _{a of the} current allowed decoding subinterval of the null symbol is selected as DD0 _a = a ^m ⋅ DD0, and the length DD1 _{a of the} current allowed decoding subinterval of a single symbol is selected as DD1 _a = a ^m ⋅ DD1.

If the current value of the alternative received sequence is not within the current allowed decoding sub-interval of the zero symbol or the current allowed decoding sub-interval of a single symbol of this alternative received sequence, then this alternative received sequence is erased, otherwise the alternative received sequence is decoded arithmetically in accordance with the current allowed decoding sub-intervals to the next parts of the corresponding alternate implicit reconstituted sequence.

For each alternative received sequence, a continuation of the sequence in the form of a null character and a continuation of the sequence in the form of a single character are formed, the value of the continuation metric in the form of a null character and the value of the continuation metric in the form of a single character relative to the next bit of the received sequence are set. The value of the continuation metric in the form of a zero symbol relative to the next bit of the received sequence is set to zero if the next bit of the received sequence is a zero bit, otherwise set to a single value. The value of the continuation sequence metric in the form of a single symbol relative to the next bit of the received sequence is set to zero if the next bit of the received sequence is a single bit, otherwise set to a single value.

For each alternative received sequence with its continuation, the value of its metric is calculated, for which the metric values of the given sequence and the metrics of its continuation of the sequence are summarized, the metrics of the alternative received sequences are compared with their continuation sequences, and no more than the maximum number Z of alternative accepted ones are selected from them sequences having the smallest metric values that complement their corresponding extensions sequences for these alternative received sequences remember the next parts of their corresponding alternative restored information sequences and metric values.

The above actions are performed on the receiving side until the next bits of the received sequence arrive, the metrics of the alternative received sequences are compared with each other and the sequence with the lowest metric value is selected from them, and then the alternative alternative received sequence is transferred to the receiver as the restored information sequence restored information sequence.

, где k≥1 есть длина очередной части информационной последовательности, а n=k+r есть длина очередной части помехоустойчивой последовательности, состоящей из k информационных символов и из r≥1 проверочных символов. Однако в заявленном способе за счет совместности выполнения действий арифметического и помехоустойчивого кодирования и декодирования проверочные символы не используются.In the proposed set of actions on the transmitting side during arithmetic coding of the next part of the information sequence into the next part of the encoded sequence, the latter is formed in accordance with the current allowed coding sub-intervals, and on the receiving side when decoding the next parts of the received sequence, those alternative received sequences that cannot be formed are erased on the transmitting side in accordance with the current allowed sub-intervals, with Among the remaining ones, a limited number Z of alternative received sequences are stored and continued with their sequence extensions having the smallest metric values, and after receiving the entire sequence, among the best continued alternative accepted sequences by the metric criterion, choose the sequence with the smallest metric value that most likely coincides with that generated on the transmitting side of the encoded sequence. Thereby, error correction of the transmission channel is performed, wherein the multiplicity of the corrected errors in the received sequence corresponds to the metric value of the selected alternative received sequence. This decoding method belongs to the class of message decoding methods in general, which are theoretically capable of achieving extremely high noise immunity of message transmission. Due to the fact that when decoding the next bits of the received sequence, the alternative received sequences are erased that do not correct the transmission channel errors that have occurred, and the limited number Z of non-erased alternative received sequences with their sequence extensions that maximize the probability of transmission error correction is maximized. transmission errors by decoding a limited number of alternatives s received sequences. The ability to detect and correct multiple errors of the transmission channel increases with decreasing values of detection errors and increase a coefficient limiting number Z alternative received sequences. In the inventive method and joint arithmetic error-correcting coding and error detection decoding coefficient and selected in the range 0 <a <1, is equivalent to the error-correcting code rate

, where k≥1 is the length of the next part of the information sequence, and n = k + r is the length of the next part of the error-correcting sequence, consisting of k information symbols and r≥1 check symbols. However, in the inventive method due to the compatibility of the actions of arithmetic and noise-correcting encoding and decoding, verification characters are not used.

Therefore, the specified new set of actions when performing joint arithmetic and noise-resistant coding and decoding of the information sequence allows to increase the noise immunity of transmission of the next parts of the encoded sequence when exposed to multiple transmission errors.

The claimed method is illustrated by drawings, which show:

- in FIG. 1 is a general diagram of joint arithmetic and noise-resistant coding and decoding;

- in FIG. 2 is a diagram of a decoding unit 8;

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

- in FIG. 4 is a state table of joint arithmetic and noise-resistant coding of the first seventeen consecutive parts of the information sequence;

- in FIG. 5 - time diagrams of joint arithmetic and noise-resistant coding of the first two successive parts of the information sequence;

- in FIG. 6 - selection of allowed coding sub-intervals depending on m≥1 previously encoded symbols of the information sequence;

- in FIG. 7 - time diagrams of joint arithmetic and noise-resistant coding of the first 17 successive parts of the information sequence;

- in FIG. 8 is a timing chart of joint arithmetic and noise-free decoding of the first 17 bits of the received sequence at the receiving side;

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

- in FIG. 10 is a representation of alternative accepted sequences in a tree structure;

- in FIG. 11 is an exemplary view of selectable no more than Z = 21 alternative received sequences;

FIG. 12 is a table of decoding conditions of an alternative received sequence of the form "0001 1110 0";

- in FIG. 13 is a table of decoding conditions of an alternative received sequence of the form "0001 1110 1";

- in FIG. 14 is a table of decoding conditions of an alternative received sequence of the form "0001 1110 1100 0110 1";

- in FIG. 15 is a decoding state table of an alternative received sequence of the form “0001 1110 0000 0110 1”.

The implementation of the claimed method is presented on the example of the joint arithmetic and noise-resistant coding and decoding system shown in FIG. 1. On the transmitting side, joint arithmetic and noise-resistant coding of the next parts of the information sequence (IP) is performed, and on the receiving side, joint arithmetic and noise-resistant decoding of the received sequence is performed with error correction of the transmission channel.

On the transmitting side, the shaper of the current encoding interval 1 generates the current arithmetic encoding interval depending on the received information sequence. From the current arithmetic coding interval, the shaper of the current zero coding sub-interval 2 forms the current coding sub-interval of the zero symbol, and, accordingly, the shaper of the current single coding sub-interval 3 forms the current coding sub-interval of 3 symbols. Upon receipt of the next part of the information sequence from the sender of the null character, the current null character encoding interval increases and the current coding sub-interval of the single character is proportionally reduced, and when the next part of the information sequence is received from the sender the next character of the information sequence, the current single character coding interval is increased and the current zero character coding interval is proportionally reduced . Next, from the current null symbol encoding subinterval in the former of the allowed zero subinterval 4, the current allowed zero character encoding subinterval is selected from the current single character encoding subinterval in the current resolved single subinterval 5 and the currently allowed single character encoding subinterval is selected depending on m≥1 previously encoded characters information symbols. Based on the data of the currently allowed sub-intervals, the next binary characters of the next part of the information sequence are arithmetically encoded in the arithmetic encoder 6 into the next part of the encoded sequence, which is transmitted via the transmission channel 7 to the receiving side.

At the receiving side, in Z decoding units 8, the next bits of the received sequence are received. A diagram of the decoding unit 8 is shown in FIG. 2. In each decoding unit 8, an alternative received sequence generator (APT) with a zero extension of 8.1 and an APT generator with a unit extension of 8.10 form alternative received sequences with corresponding sequence extensions, which in arithmetic decoder 8.2 and arithmetic decoder 8.11, respectively, are arithmetically decoded into the next parts of the corresponding alternative reconstructed information sequences.

When decoding binary symbols from an APT with zero continuation, the current arithmetic decoding interval is formed in the generator of the current decoding interval 8.3, which the generator of the current zero decoding subinterval 8.4 divides the current zero decoding subinterval of the zero symbol, and the generator of the current single decoding subinterval 8.5 divides the current decoding subinterval of a single character. In accordance with the decoding results of m≥1 successive recovered information symbols from the current sub-intervals, the current allowed decoding interval of the decoding of a single symbol and the current allowed decoding sub-interval of a single symbol are selected in the shaper of the current allowed zero decoding sub-interval 8.6 and in the shaper of the current allowed single decoding sub-interval 8.7, respectively. In the sub-interval checking unit 8.8, it is checked whether the current value of the received sequence is within the current allowed decoding sub-interval of the zero symbol or the current allowed decoding sub-interval of a single symbol of this alternative received sequence. If the test result is positive, in arithmetic decoder 8.2 the next parts of the alternative received sequence are arithmetically decoded with its continuation in accordance with the current allowed decoding sub-intervals in the next parts of the corresponding alternative restored sequence. When arithmetic decoding of the zero symbol of the next part of the restored information sequence from the APT with zero continuation further in the shaper of the current zero decoding subinterval 8.4 and the shaper of the current single decoding subinterval 8.5 increases the current decoding subinterval of the zero character and proportionally reduces the current decoding subinterval of a single character for this APT, and when single character decoding - increase the current decoding sub-interval e inichnogo symbol and proportionally reduces the current subinterval zero symbol for decoding this APP.

Similar actions are performed when decoding binary characters from an APT with a single continuation using an APT shaper with a single continuation of 8.10, an arithmetic decoder 8.11, a shaper of the current decoding interval 8.12, a shaper of the current zero decoding subinterval 8.13, a shaper of the current single decoding subinterval 8.14, a shaper of the current allowed zero subinterval 8.15 decoding, shaper of the current allowed single decoding subinterval 8.16 and block checking of sub-intervals 8.17.

In the calculation block of the APT 8.9 metric, for each alternative received sequence with its continuation, the value of its metric is calculated by summing the metric of the sequence itself and the metric of its continuation, where the values of the continuation metric are set to the appropriate value depending on the relationship between the binary value of the continuation of the sequence and the value of the next bit received sequence. From the APT 8.9 metric calculation block, the calculated metric value of each alternative received sequence with its continuation is passed to the block of the alternative received APP 9 sequence selection.

If during the check in the check section of sub-intervals 8.8, respectively, in the check-block of sub-intervals 8.17, the current value of the alternative received sequence is within the current allowed sub-intervals of arithmetic decoding of the corresponding alternative received sequence with its continuation, then in the block of the selection of APT 9 the next parts of the alternative restored information sequence corresponding to the alternative accepted sequence with its pro olzheniem, or erase this alternative received sequence with its continuation.

In the selection block APP 9, the metric values of the alternative received sequences are compared with their sequence extensions, and no more than the maximum number Z of alternative received sequences having the smallest metric values that complement the corresponding sequence extensions is selected from them, the next parts are remembered for these alternative received sequences the corresponding alternative reconstructed information sequence and metric value.

After all bits of the received sequence are received on the receiving side, the metric of the alternative received sequences is compared to each other in the APT 9 selection block and the only alternative received sequence with the lowest metric value is selected from them and the alternative restored received information corresponding to the selected alternative received sequence is transmitted to the recipient as the restored information sequence sequence.

The method implements the following sequence of actions.

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

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” by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin image and video compression. " - M., DIALOGUE-MEPhI, 2002, pp. 35-43. The initial interval of arithmetic coding of length D> 2 begins from its initial lower value L, inclusively, and ends with its initial upper value H exclusively. The initial lower value of the encoding interval is set to the minimum value of the encoding interval, and the initial upper value of the encoding interval is set to the maximum value of this interval. For example, when representing the values of the encoding interval with eight binary characters (the bit depth of the intervals N _R = 8 bits), the initial lower value of the encoding interval of the arithmetic encoding L [0] at time t = 0 is set to the minimum value equal to a zero value in decimal representation or 0000 0000 in binary representation, where high-order binary characters are written to the left, and the initial upper value of the coding interval of the arithmetic coding H [0] is set to the maximum value equal to 255 in decimal or 1111 1111 in binary representation. An example of an initial arithmetic coding interval of length D [0] = 256 is shown in FIG. 4 at t = 0 (first row) and in FIG. 5 at t = 0.

The limit number Z≥2 of the alternative received sequences and the metric value of the alternative received sequences are also pre-set to zero. Methods for pre-setting the limit number Z of alternative received sequences are known and described, for example, in the book D. Prokis "Digital Communication". - M., Radio and Communications, 2000, pp. 328-349. For example, to correct twofold errors, it is recommended to choose the limit number Z of alternative received sequences from a range of values of 8 ... 24, to correct three-fold errors, it is recommended to choose a limit number Z of alternative received sequences from a range of values of 24 ... 48, taking into account that when the selected number Z increases a larger number of transmission errors can be corrected, but the complexity of error correction implementation devices is increasing linearly. For example, for the example considered below, we set the limit number Z of alternative received sequences to Z = 21.

Methods for pre-setting the metric value of alternative accepted sequences to zero are known and described, for example, in B. Sklar's book "Digital Communication. Theoretical Foundations and Practical Applications". - M., Publishing House "William", 2003, pp. 432-434. Initially, before receiving a sequence at the receiving side, the alternative received sequences are of zero length.

On the transmitting side from the source of the information sequence, the next part of the information sequence of length k≥1 bits is received. An exemplary view of the first 17 consecutive parts of a binary IP of length k = 1 bit is shown in FIG. 7 (a). For example, the first part of the IP has the form "0", the second part is "0", the fourth part is "1", etc. Single bit values in the figures are shown as shaded pulses, zero bits are shown as open shaded pulses.

The current arithmetic coding interval of length D> 2 is divided into the current coding subinterval of the zero character D0≥2 and the current encoding subinterval of a single character D1≥2. 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, pp. 35-43. For arithmetic coding of the next tth character, where t = 1, 2, ..., the length D of the current arithmetic coding interval, where D = H-L, is divided by the length D _{0 of the} current coding subinterval and the length D _{1 of the} current subinterval encoding a single character. To do this, calculate the current number of zero characters SP N ₀ and the current number of unit characters SP N ₁ encoded at this point in time in an arithmetic encoder. For example, at the initial moment at t = 0, the current number of zero characters of PI N ₀ [0] is set to 1 and the current number of unit characters of PI N ₁ [0] is set to 1. Ways to set the number of zero and one at the initial moment of arithmetic coding IP symbols in a single value 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, pp. 124-130. For example, as shown in FIG. 4, in the first line at t = 0, the unit number of zero symbols of the PI (column N0) and the unit number of unit symbols of the PI (column N1) are indicated. Column N indicates the total number of received symbols, taking into account the zero and single symbols of the IP set at the initial moment, equal to N = 2 at t = 0.

The current probability of encoding the null symbols of the IP p ₀ [t] is calculated according to the rule: p ₀ [t] = N ₀ [t] / (N ₀ [t] + N ₁ [t]) and the current probability of encoding the individual symbols of the IP p ₁ [ t] by the rule: p ₁ = N ₁ [t] / (N ₀ [t] + N ₁ [t]). For example, as shown in FIG. 4 in the first line at t = 0, the value of the current probability of coding of zero symbols of PI (column p0) and the value of the current probability of coding of single symbols of PI (column p1) are indicated, where the initial values are 0.5.

The length of the current coding sub-interval of the zero character D ₀ [t] is determined by a formula of the form D ₀ [t] = D [t] × p ₀ [t], and the length of the current coding sub-interval of a single character D ₁ [t] is determined by a formula of the form D ₁ [t] = D [t] -D ₀ [t]. For example, the length of the initial coding interval D [0] has a decimal value of 255, and the length of the initial subinterval of null characters D ₀ [0] has a decimal value of 127 or 01111111 in binary representation, and the length of the initial subinterval of single characters D ₁ [0] has a decimal value 255-127 = 128 or 10,000,000 in binary representation. The single-character encoding sub-interval is located on top of the zero-character encoding sub-interval, as shown, for example, in FIG. 5. The upper boundary of the null-symbol encoding subinterval is designated as the Q value, and this subinterval starts from the bottom of the lower boundary of the arithmetic coding encoding interval L inclusive to the value Q exclusively, and the single-symbol subinterval extends from the Q value inclusive to the upper boundary of the arithmetic coding encoding interval H exclusively . For example, the initial Q value has a decimal value 127, as shown in FIG. 4 in the second line at t = 0.

From the current encoding sub-interval of the zero symbol D0 and the current encoding sub-interval of a single symbol D1, depending on m≥1 previously encoded symbols of the information sequence, the current allowed encoding sub-interval of the zero symbol D0 _a , where 1≤D0 _a <D0, and, accordingly, the current allowed sub-interval encoding a single character D1 _a , where 1≤D1 _a <D1. D0 _a length permitted current subinterval null character is selected as a coding D0 _a = _a ^m ⋅D0, and D1 _a length permitted current subinterval encoding unit is selected as a symbol D1 _a = _a ^m ⋅D1, wherein the coefficient of the error detection and is selected in the range 0 <a <1. In the claimed method the joint of the arithmetic and error-correcting coding and decoding error rate detection and is equivalent to the speed error-correcting code R, defined as the ratio of the information symbols to the length of the coded symbols R = k / n, where error-correcting code rate is selected in the range 0 <R <1. The smaller the value of the error detection and ratio, the greater the number of transmission channel errors is possible to fix the joint in the inventive method, the arithmetic and error-correcting coding and decoding. For example, let the value of the error detection coefficient a = 0.8 and the number of symbols previously coded information sequence m = 1, and also at the initial moment t = 0 encoding establish the sender and the receiver that the previous coded symbol information sequence has a zero value. The length D0 _{a of the} current allowed encoding subinterval of the null character is selected as D0 _a = a ⋅ D0 = 0.8⋅127 = 102 (rounded to the nearest integer), and the length D1 _{a of the} current allowed encoding subinterval of a single character is chosen as D1 _a = a ⋅D1 = 0.8⋅128 = 102.

Separation of the current allowed coding subinterval D0 _a from the current coding subinterval D0 and, accordingly, the current allowed coding subinterval D1 _a from the current coding subinterval D1 depending on m≥1 previously encoded information sequence symbols can be performed different ways: starting from the lower or upper values of the corresponding coding sub-interval, or in the central part of the coding sub-interval knowledge, in the form of a continuous subinterval or in the form of a set of allowed subintervals, interspersed by subintervals from unauthorized coding regions. The ability to detect and correct transmission errors in this case in the inventive method does not change. For example, for m = 1, for convenience of implementation, with a previously previously encoded zero IP symbol, it is proposed to isolate the current allowed encoding sub-interval of the zero symbol of length D0 _a in the form of one sub-interval starting from the lower value of the encoding interval L to the upper value L _{in the} current allowed encoding sub-interval of such a symbol so that the length of the currently allowed encoding subinterval of the null character is equal to D0 _a , and this subinterval starts from its lower value L _n = L inclusive and nchivaetsya its upper value of L _{in the} exclusively. For example, as shown in FIG. 4 in the second row at t = 0 the lower value of current allowed subslot encoding zero symbol is equal to L _n = 0 (binary value 0000 0000), and the upper limit of the subinterval is equal _to L = 102 (binary value 0110 0110). In FIG. 6, the location of the currently allowed encoding subinterval of the null symbol with the previously zero previously encoded IP symbol is shown as D0 / 0 _a . If the previously encoded symbol is zero, it is proposed to isolate the current allowed encoding subinterval of a single character of length D1 _a in the form of one subinterval starting from the top from the upper value H of the encoding interval to the lower value H _{n of the} current allowed encoding subinterval of a single character so that the length of the current allowed encoding subinterval a single symbol is equal to D1 _a , as shown in FIG. 6.

Thus, in this example, when the previously encoded IP symbol is null at m = 1 previously encoded IP symbols, the current allowed null symbol encoding sub-range ranging from L _n = 0 to L _at = 102 and the current single character encoding sub-interval ranging from N _H = 153 to H _B = 255, as shown in FIG. 4 in the second line of the line highlight the allowed encoding interval "Highlighted. Resol. Int".

In the general case, for m> 1, the current allowed encoding sub-interval of the zero character D0 _a and the current allowed encoding sub-interval of a single character D1 _a are first allocated, depending on the first previously encoded character of the information sequence. Then, from the currently allowed zero-character encoding subinterval of the form D0 / 0 _a or D0 / 1 _a , the current permitted zero-character encoding subinterval is selected depending on two previously encoded IP symbols of the form D0 / 00 _a (D0 / 01 _a ) or D0 / 11 _a ( D0 / 10 _a ) as shown in FIG. 6, and so on, until the required number m of previously encoded IP symbols is reached.

As a result, the arithmetic encoding interval, depending on the previously encoded symbols, is divided into the allowed encoding interval and the unresolved encoding interval. Similarly, in error-correcting error-coding coding, the set of all code combinations is divided into a set of allowed code combinations, consisting of undistorted transmission of code sequences, and a set of unresolved code combinations, consisting of distorted transmission of code sequences. If, at reception, the received sequence belongs to a plurality of unresolved code combinations, then using error-correcting coding an error has been detected in the received data. In contrast, in the proposed method for joint arithmetic and error-correcting coding and decoding, an error in the received sequence is detected if the current state of the arithmetic decoding does not correspond to the allowed decoding subintervals, taking into account the restored IP symbols.

The methods of arithmetic coding of the next part of the IP in accordance with the current allowed sub-intervals of coding in the next part of the coded sequence (KP) are known and described, for example, in the book D. Data compression methods. Device by D. Watolin, A. Ratushnyak, M. Smirnov, V. Yukin archivers, image and video compression. " - M., DIALOGUE-MEPhI, 2002, pp. 35-43. They consist in sequentially compressing the binary characters of the next part of the IP to the next part of the CP in accordance with the current values of the allowed sub-interval of encoding a zero character and the allowed sub-interval of encoding a single character. When the next binary symbol of the next part of the IP, which is a single binary symbol, is received at the input of arithmetic encoding, the current interval of arithmetic encoding is set equal to the current allowed sub-interval of encoding a single symbol, and when the input receives arithmetic encoding of a zero binary symbol, the current interval of arithmetic encoding is set to the current allowed null character encoding subinterval.

For example, when a binary character of the first part of an IP, which is a binary binary character, is received at the coding input, the current coding interval is set equal to the current allowed coding sub-interval of the zero character, starting from L _H [0] = 0 and ending with Z _B [0] = 102, lower the value L [1] of the current arithmetic coding interval is set to 0, and the upper value H [1] to the decimal value 102, as shown in FIG. 4 and in FIG. 5 at t = 1.

In arithmetic coding, 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 0000 0000 and 0110 0110, respectively, as shown in FIG. 4 at t = 1. When they coincide, the value of the leftmost bit of the binary representations of the values L [1] and H [1] is read as the next bit of the next part of the encoded sequence (Code symbol, as shown in Fig. 4). For example, when encoding the first part of the IP, the first bit of the first part of the KP is the zero binary symbol that coincides when comparing, as shown in FIG. 4, the fourth line from the top. The read bit is removed from the binary representations of the values L [1] and H [1], which are reduced to a length of 7 bits of the form 0000 000 and 110 0110, respectively. Binary symbols of binary representations of the values of L [1] and H [1] are shifted from right to left by one digit and are added to the right by a zero binary symbol. For example, the binary representations of the values L [1] and H [1] take the form 0000 0000 and 1100 1100, respectively, as shown in FIG. 4, the fourth line from the top. 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 Communications, 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 [t] and H [t] by 2 times and are called normalization of arithmetic coding parameters. The 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 a multiplication by two decimal values of the lower and upper values of the arithmetic coding 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 next part of the CP, otherwise they proceed to the encoding of the next character and so on, as shown in FIG. 4.

As a result of encoding the first part of the information sequence of the form “0” shown in FIG. 7 (a), the first part of the encoded sequence of the form “0” shown in FIG. 7 (b), which is transmitted to the receiving side.

Upon receipt of the next part of the IP, its coding in the next part of the KP is performed identically. After arithmetic coding of each successive symbol, the number of encoded zero symbols of the IP and the number of encoded unit symbols of the IP are specified. Since the encoded character in this example is zero, the number of encoded zero characters of the PI is increased by a unit value and it is N ₀ [1] = 2, the number of encoded single characters of the information sequence remains equal to N ₁ [1] = 1, respectively, the total the number of coded zero and unit information symbols becomes equal to the current value of 3. recalculated probabilities encoding zero symbols SP ₀ p [1] = 2/3 and the current probability value encoding unit symbols SP ₁ p [1] = 1/3 as dormancy Zano in the third row from above in FIG. 4.

Before arithmetic coding of the next character is performed again, the current arithmetic coding interval is divided into the current null character encoding subinterval and the current single character encoding subinterval, from which the current allowed zero character encoding subinterval and the current allowed single character encoding subinterval are selected. For example, before encoding the second PI symbol in a row, the current arithmetic encoding interval is in the range from L [1] = 0 to H [1] = 204, the current zero-character encoding interval is in the range of L [1] = 0 to Q [1 ] = 136, and the current coding sub-interval of a single symbol is in the range from Q [1] = 136 to H [1] = 204, where the value of Q [1] is determined by the rule Q [1] = D [1] × p ₀ [ 1] = 204 × 2/3 = 136.

Since in this example, with m = 1 previously encoded IP symbols, the second symbol of the IP having zero value is subject to arithmetic encoding, the current allowed sub-interval of encoding the zero symbol is selected from the current sub-interval of encoding the zero symbol, taking into account the previous encoded zero symbol. The length D0 _a [1] of the currently allowed null symbol encoding sub-interval is chosen as D0 _a [1] = a ⋅ D0 [1] = 0.8⋅126 = 109, respectively, this sub-interval is in the range from L _n [1] = 0 to L _in [1] = 109, as shown in FIG. 4 in the fifth row and in FIG. 5 at t = 1.

Arithmetic coding of the second and subsequent binary symbols of the PI is performed, as shown in FIG. 4. For example, when encoding the fourth symbol of the IP, which is a single character, from the current sub-coding interval of a single character, select the current allowed coding sub-interval of a single character, ranging from H _n [3] = 105 to H _at [3] = 126, as shown in FIG. 4 in the tenth line from above.

Each time normalization is performed, binary characters are read into the next part of the encoded sequence. An approximate type of arithmetic coding of the first 17 consecutive parts of the IP of the form "0001 0000 0000 0010 0" in the corresponding next parts of the KP of the form "0", "0", "_", "_", "01111", "0", "_" , "0" and so on is shown in FIG. 7 (b). Note that with a fixed length of the next parts of the IP as a result of their arithmetic coding, the next parts of the CP of variable length are formed, which, in particular, is determined by the variable redundancy of the compressible parts of the IP. For example, the third, fourth, seventh, tenth, etc. KP parts have zero length (do not contain transmitted characters). In general, the KP with a length of 17 bits has the form "0001 1110 0000 0110 1".

Methods of transmitting to the receiving side of the next part of the CP 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 17 parts of the received sequence (Pr. P) is shown in FIG. 8 (a). Let the received sequence with a total length of 17 bits during transmission be distorted in the ninth and tenth bits of the received sequence and have the form "0001 1110 1100 0110 1".

The algorithm for joint arithmetic and error-correcting decoding at the receiving side is shown in FIG. 9. In FIG. 10 shows alternative accepted sequences in a tree structure, and FIG. 11 is an exemplary view of selectable no more than Z = 21 alternative received sequences.

To initiate arithmetic decoding, it is necessary to take the first N _R binary symbols of the Ave. P, where N _R is the number of binary symbols representing the values of the encoding intervals and, accordingly, the decoding intervals. For example, when presenting the values of the coding interval and the decoding interval with eight binary characters (N _R = 8 bits), the first eight bits of Pr.P of the form “0001 1110” are received, as shown in FIG. 12 in the column read binary characters "Count" at the initial time t = 0. The received sequence "0001 1110" at the initial moment of time has a current value of 30, calculated as the decimal value of this binary sequence, in which the most significant bit is on the left (at the beginning of the sequence) and the least significant bit is on the right (at the end of the sequence).

Let us describe in general terms the joint arithmetic and noise-resistant decoding of Pr.P on the receiving side. The actions of joint arithmetic and noise-correcting decoding of Ave.P on the receiving side are performed by parallel decoding of several alternative received sequences (APP). For example, at the initial moment of time, there is a single alternative received sequence coinciding with the first eight bits of Pr. P of the form "0001 1110". At the time of reading the first bit after the initial N _R bit of the next bit of the received sequence, denoted by the time t = 1, for the initial received sequence consisting of the first N _R binary symbols of the received sequence, the continuation of the AMS in the form of a null character and the continuation of the sequence in as a single character, as shown in FIG. 10. When reading the next bit of the received sequence (time t = 2), for each of the two AMSs, extensions are formed in the form of a null character and a continuation in the form of a single character, as a result, at the time t = 2, the number of AMS becomes 4, at the time t = 3 the number of AMS reaches 8, etc. A representation of the alternative received sequences in the form of the described tree structure is shown in FIG. 10. This structure of the AMS potentially allows you to correct multiple transmission errors in the adopted sequence, and the place of errors in Pr. May be arbitrary. For each APP, the following actions are performed together arithmetic and noise-free decoding.

For example, with a pre-set limit number Z = 21 APP, an exemplary view of selectable no more than Z alternative received sequences is shown in FIG. 11. It can be seen that in this structure, called the truncated tree of alternative received sequences, the number of continued APPs at each moment t does not exceed a given value of Z. For example, for the initial alternative received sequence of the form “0001 1110”, 2 extensions are formed: the APT with the continuation of the sequence in in the form of a null character "0001 1010 0", and the APT with the continuation of the sequence in the form of a single character "0001 1010 1". For an APT with the continuation of the sequence in the form of a null character "0001 1010 0" the value of the metric of continuation of the sequence in the form of a null character relative to the next single, ninth in fig. 11 characters of the received sequence are set to a single value. Since the metric of the initial alternative received sequence is pre-set to zero, the APT with the continuation of the sequence in the form of a null character "0001 1110 0" has a metric value of M = 1, as shown in FIG. 11. For APP with the continuation of the sequence in the form of a single character "0001 1110 1", the value of the metric of the continuation of the sequence in the form of a single character relative to the next, ninth in FIG. 11 bits of a received sequence having a unit value are set to zero. Accordingly, the APT with the continuation of the sequence in the form of a single symbol “0001 1110 1” has a metric value of M = 0, as shown in FIG. eleven.

The number of continued APTs when decoding the ninth symbol of the received sequence is 2, this number does not exceed the limit number Z = 21 APTs and both alternative received sequences continue, forming, when decoding, the next tenth in FIG. 11 characters of the received sequence are four sequences with metric values from M = 0 to M = 2, which, when decoding the next, eleventh in a row in FIG. 11 bits of the received sequence form 8 sequences with metric values from M = 0 to M = 3, which when decoding the next, twelfth in a row in FIG. 11 characters of the received sequence form 16 sequences with metric values from M = 0 to M = 4, etc. When the number of APP exceeds the limiting number Z of APP, then no more than Z = 21 alternative accepted sequences with the lowest metric values are selected from these sequences. By the principle of maximum likelihood in the theory of error-correcting coding, as described in the book by B. Sklar "Digital Communication. Theoretical Foundations and Practical Applications". - M., Williams Publishing House, 2003, pp. 422-431, the more the alternative accepted sequence differs from the accepted sequence in terms of the value of the metric M, the less likely it is that it will correct transmission errors, which gives the basis for such a sequence wash.

" на фиг. 11. При этом оказалась стертой альтернативная принятая последовательность с ее продолжением вида "0001 1110 1100 0110 1" со значением метрики М=0, которая по этой причине ранее считалась наиболее предпочтительной при выборе среди альтернативных принятых последовательностей.In the given example, in many ongoing APPs, the current value of the alternative received sequence turned out to be outside the current allowed arithmetic decoding interval of these APPs, that is, such sequences could not be formed on the transmitting side and, accordingly, they should be erased and they would not continue further, as shown by the symbol "

"in Fig. 11. At the same time, the alternative accepted sequence with its continuation of the form" 0001 1110 1100 0110 1 "with the value of the metric M = 0, which for this reason was previously considered the most preferred when choosing among alternative accepted sequences, was erased.

We describe in detail the actions of joint arithmetic and noise-resistant decoding at the receiving side.

Methods for dividing the current interval of arithmetic decoding by the length DD of each alternative received sequence into the current decoding sub-interval of the null character DD0, where DD0≥2, and the current decoding sub-interval of a single symbol DD1, where DD1≥2, are identical to the methods of dividing the current arithmetic coding interval of length D into the current the coding sub-interval of the zero symbol D0 and the current coding sub-interval of a single symbol D1 on the transmitting side.

For arithmetic decoding of the next tth character, where t = 1, 2, ..., the length DD of the current arithmetic decoding interval, where DD = HH-LL, of each alternative received sequence is divided by the length DD _{0 of the} current decoding subinterval of the zero symbol and the length of DD _{1 of the} current sub-interval of decoding a single symbol of this APP. The current arithmetic decoding interval of each APT extends from its lower value of the LL decoding interval to the upper value of the LV decoding interval. For example, in the initial state at t = 0 LL = 0 and HH = 255, as shown in FIG. 12 in the first line. To determine the values of DD ₀ and DD _{1, the} current number of zero characters of the recovered UE of each APP NN ₀ and the current number of unit characters of the recovered UE of each APP NN ₁ , decoded at this point in time in the arithmetic decoder, are calculated. For example, at the initial moment at t = 0, the current number of zero characters of the restored UI NN ₀ [0] is set to 1 and the current number of unit characters of the restored UI NN ₁ [0] is set to 1. For example, as shown in FIG. 12 in the first line at t = 0 indicates the unit number of zero characters of the restored PI (column NN0) and the unit number of unit characters of the restored PI (column NN1). The NN column indicates the total number of decoded symbols, taking into account the zero and single symbols of the restored IP set at the initial moment, equal to NN = 2 at t = 0.

The current probability of decoding the null symbols of the recovered IP pp ₀ [t] of each APP is calculated according to the rule: pp ₀ [t] = NN ₀ [t] / (NN ₀ [t] + NN ₁ [t]) and the current probability of decoding single symbols of the recovered PI pp ₁ [t] of each APP according to the rule: pp ₁ [t] = NN ₁ [t] / (NN ₀ [t] + NN ₁ [t]). For example, as shown in FIG. 12 in the first line at t = 0, the value of the current probability of decoding the zero characters of the restored SP (column pp0) and the value of the current probability of decoding the single characters of the restored SP (column pp1) are indicated, where the initial values are 0.5.

The length of the current sub-interval for decoding the null symbol DD ₀ [t] of each APT is determined by the formula of the form DD ₀ [t] = DD [t] × pp ₀ [t], and the length of the current sub-interval of decoding a single character DD ₁ [t] of each APP is determined by a formula of the form DD ₁ [t] = DD [t] -DD ₀ [t]. For example, the length of the initial decoding interval DD [0] the APT has a decimal value of 255, the length of the initial subinterval of decoding the null characters DD ₀ [0] the AMS has the decimal value 127 or 01111111 in binary representation, and the length of the initial subinterval of the decoding of single characters DD ₁ [0] The APP has a decimal value of 255-127 = 128 or 10,000,000 in binary representation. The APT unit symbol decoding interval is located on top of the APT zero symbol decoding interval, as shown, for example, in FIG. 12. The upper boundary of the decoding interval of the decoding interval of the zero symbol of the AMS is designated as the QQ value, and this sub-interval starts from the bottom of the lower boundary of the arithmetic decoding interval LL inclusive to the QQ value exclusively, and the sub-interval of a single symbol extends from the QQ value inclusive to the upper boundary of the decoding interval of the arithmetic coding HH exclusively. The initial QQ value has a decimal value of 127, as shown in FIG. 12 in the second row at t = 0.

Methods of extracting, depending on m symbols, the reconstructed information sequence of each alternative received sequence from the current decoding sub-interval of the DD0 zero symbol and from the current decoding sub-interval of the DD1 single symbol of the currently allowed decoding subinterval of the DD0 _a zero symbol, where 1≤DD0 _a <DD0, and, accordingly, the current allowed decoding sub-interval of _a single symbol DD1 _a , where 1≤DD1 _a <DD1, are identical to the previously described methods for extracting coding from the current sub-interval of the zero character D0 and from the current encoding subinterval D1 of the unit character of the current allowed encoding subinterval D0 _a and, accordingly, of the current allowed encoding subinterval D1 _a . The length DD0 _{a of the} current allowed decoding subinterval of the null symbol is selected as DD0 _a = a ^m ⋅ DD0, and the length DD1 _{a of the} current allowed decoding subinterval of a single symbol is selected as DD1 _a = a ^m ⋅ DD1.

For example, when the selected value of the coefficient error detecting a = 0.8 and the number m = 1, the length DD0 _a current allowed subslot decoding APP null character is selected as a DD0 _a = _a ⋅DD0 = 0,8⋅127 = 102 and length DD1 _a the current allowed decoding sub-interval of a single symbol of the APT is selected as DD1 _a = a ⋅DD1 = 0.8⋅128 = 102. For example, it is established for the sender and receiver at the initial moment of encoding / decoding t = 0 that the previous encoded / decoded symbol of the information sequence has a zero value. For example, for implementation convenience, with zero previous decoded symbol restored SP in each APT proposed allocation of current permitted subslot decoding null character APP length DD0 _a as one subinterval, starting from the lower value LL interval decoding APP to an upper value LL _B current permitted subslot decoding the APT zero symbol in such a way that the length of the currently allowed decoding subinterval of the APT zero symbol is DD0 _a , and this subinterval starts from its lower value LL _H = LL inclusive and ends with its upper value LL _B exclusively. For example, as shown in FIG. 12 in the second line, at t = 0, the lower value of the current allowed decoding subinterval of the APT zero symbol is LL _H = 0 (binary value 0000 0000), and the upper value of this subinterval is LL _B = 102 (binary value 0110 0110). Accordingly, the current allowed sub-interval of decoding a single APT symbol is in the range from the lower value of HH _H = 153 to the upper value of this sub-interval HH _B = 255, as shown in FIG. 12 in the second line.

If the current value of the alternative received sequence is not within the current allowed decoding subinterval of the APT zero symbol or the current allowed decoding subinterval of a single APT symbol, then this alternative received sequence is erased. For example, when presenting the values of an encoding interval with eight binary characters, the current value of the alternative received sequence is determined from the last eight bits of this APP. For example, the received binary sequence of the form “0001 1110” of the APT of the form “0001 1110” has the decimal value 30 shown in FIG. 12 in the column "Pr. Ambassador". The current allowed decoding sub-interval of the APT null symbol of the type “0001 1110” extends from LL _H = 0 to LL _B = 102, and the current allowed decoding sub-interval of a single APT symbol extends from LV _H = 153 to LV _B = 255. Since the current value of the alternative received sequence is within one of the current allowed decoding sub-intervals of the APT, in this case, within the current allowed decoding sub-interval of the zero character of the APT, this APP is stored and is then subject to decoding.

The methods of arithmetic decoding of each APP into successive parts of the corresponding alternative reconstructed information sequence (WUA) are known and described, for example, in the book “Data compression methods. Archiver device, image compression, D. Watolin, A. Ratushnyak, M. Smirnov, V. Yukin and video. " - M., DIALOGUE-MEPhI, 2002, pp. 35-43. They consist in sequential decoding of each APT in accordance with the current allowed values of the decoding sub-interval of the zero symbol and the sub-interval of decoding a single symbol of this APP.

An exemplary arithmetic decoding of the initial AMS of the form “0001 1110” into the symbols of the next part of the corresponding WUA is shown in FIG. 12. To decode the first character of the next part of the WUA, the current value of the alternative received sequence equal to 30 is compared with the boundaries of the current allowed decoding sub-interval of the APT zero symbol DD ₀ [0], which are, for example, in the range from 0 to 102, and with the boundaries of the current allowed the sub-interval of decoding a single APT symbol DD ₁ [0], for example, ranging from 153 to 255, as shown in FIG. 12 in the second row at t = 0. Depending on the range within which the symbol decoding sub-interval turned out to be the current value of the alternative received sequence, a decision is made on the value of the current decoded symbol (Dec. Char.) Of the alternative restored information sequence indicated in the right column of FIG. 12. Since in this example, the current value of the alternative received sequence was within the allowed decoding subinterval of the null symbol, the decoded symbol is zero and the following boundaries of the current decoding interval are set to the corresponding boundaries of the allowed decoding subinterval of the given symbol of the APT of length DD ₀ [0]. As a result of decoding the first symbol, the lower value of the arithmetic decoding decoding interval LL [1] is set to LL _H [0], for example, LL _H = 0, and the upper value of the arithmetic decoding decoding interval HH [1] is set to LL _B = 102, as shown in FIG. 12 in the third row at t = 1.

After decoding each symbol, the current probability value of the WUA zero symbol and the current probability value of a single symbol of the same sequence are recalculated, for example, after decoding the first symbol that is zero, according to the formula pp ₀ [1] = NN ₀ [1] / (NN ₀ [ 1] + NN [1]) = 2/3 and according to a formula of the form pp ₁ [1] = NN ₁ [1] / (NN ₀ [1] + NN ₁ [1]) = 1/3, respectively, as shown in FIG. 11 in the third row at t = 1.

For each APT form the continuation of the sequence in the form of a null character and the continuation in the form of a single character. For example, from the initial APT of the form “0001 1110”, an APT is formed with a continuation in the form of a zero character of the form “0001 1110 0”, and an APT with a continuation in the form of a single character of the form “0001 1110 1”, as shown in FIG. 11. The top edge of the graphic representation of each APT in the figure is indicated as a continuation of the sequence in the form of a null character "0", and the lower edge - as a continuation of the sequence in the form of a single character "1".

After the continuation of the sequence is formed, the continuation metric value is calculated in the form of a null character and the continuation metric value is in the form of a single character relative to the next bit of the received sequence, while the continuation metric value in the form of a zero character relative to the next bit of the received sequence is calculated as zero if the next bit of the next part the received sequence is a zero bit, otherwise it is calculated as a unit value, as well as the value of the metric services in the form of a single symbol relative to the next bit of the received sequence are calculated as a zero value if the next bit of the received sequence is a single bit, otherwise calculated as a single value. For example, as shown in FIG. 11, the next bit Ave.P, the next after reading the eight bits of the initial decoding path, has a single value. Therefore, with respect to this bit, the sequence continuation metric in the form of a null character has a unit value, and the sequence continuation metric in the form of a single character has a null value.

Then, for each APT with its continuation of the sequence, the value of its metric is calculated, for which the values of the metrics of this sequence and the metrics of its continuation are summed. For example, taking into account the fact that the initial APT metric of the type “0001 1110” has a zero value, the APT metric of the type “0001 1110 0” with the continuation in the form of a zero symbol gets a single value (M = 1), and the APT metric “0001 1110 1” continued with a single character, it receives a null value (M = 1), as shown in FIG. eleven.

After each change in the arithmetic decoding state, the leftmost bit of the binary representation of the LL value of the APT decoding interval is compared with the leftmost bit of the binary representation of the LV value of this APP, for example, for the APP of the form “0001 1110 0” at t = 1, the LL value of the form “0000 0000” is compared and an LV value of the form "0110 0110", 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 deleted and the binary representations of the LL and LV values are shifted from right to left by one digit and are added to the least significant bit to the right with the zero binary symbol. For example, while the variable LL saved the decimal value 0, and HH received the decimal value 204 and the binary representation "1100 1100", as shown in FIG. 12 in the line "normalization". At the same time, the leftmost bit of the current value of the alternative received sequence is deleted and the binary characters of this sequence are shifted from right to left by one bit and the next read binary character of the alternative received sequence, that is, the continuation symbol of this APT, is added to them. For example, for an APT of the form “0001 1010 0” followed by a null character, the next binary character read is the ninth character of an alternative received sequence having a null value, as shown in FIG. 12 in the column "Count." Based on the read binary character, the current value of this APP has received the decimal value 52 and the binary representation “0011 0100”, as shown in FIG. 12 in the line "normalization".

For an APT of the form “0001 1010 1”, continued as a single character, as shown in FIG. 13, the next binary symbol read is the ninth symbol of this alternative received sequence having a single value, as shown in FIG. 13 in the column "Count." Based on the read binary character, the current value of this APP has received the decimal value 53 and the binary representation “0011 0101”, as shown in FIG. 13 in the line "normalization".

For all APPs, the leftmost bit of the binary representation of the LL value is compared again with the leftmost bit of the binary representation of the HH value, and if they coincide again, then they perform normalization in the same way, etc.

For all APPs, the lengths of the current decoding sub-intervals are again determined, and I highlight their current allowed decoding sub-intervals. For example, for AMSs of the types “0001 1110 0” and “0001 1110 1”, the current allowed decoding intervals of the null symbol and the current allowed decoding intervals of a single symbol at the time of decoding of the second information symbol are the same. For an APT of the type "0001 1110 0", its current value of 60 is within the current allowed decoding subinterval of the null character (from 0 to 109), as well as for an APT of the form "0001 1110 1", its current value of 61 is within its current allowed subinterval decoding the null character (0 to 109), and for both AMSs, the next decoded information symbol is the null character, as shown in FIG. 12 and FIG. thirteen.

As a result of the arithmetic decoding of the APT of the form “0001 1110 0” shown in FIG. 8 (b), decode, for example, the symbols of the first two parts of its corresponding WUA, having the form “0 0”, as shown in FIG. 8 (c), similarly, from an APP of the form “0001 1110 1” shown in FIG. 8 (d) decode, for example, the symbols of the first two parts of its corresponding WUA, having the form “0 0”, as shown in FIG. 8 (d).

Compare with each other the metric values of the alternative received sequences with their sequence extensions and choose from them no more than the maximum number Z of alternative received sequences having the smallest metric values that complement the corresponding sequence extensions. These methods are known and described, for example, in the book by M. Shibuya, T. Yamamoto "Data Processing Algorithms". - M., Mir, 1986, pp. 122-134, and consist in alternately comparing the values of the AMP metric with their extensions, sorting the sequences as the values of the metric increase, and choosing among the sorted sequences of the first Z sequences with the lowest metric values.

For example, at the time of receiving the ninth character of the received sequence, there are only two APTs: APP with continuation of the sequence in the form of a zero character of the form “0001 1110 0” and APP with continuation of the sequence in the form of a single character of the form “0001 1110 1” with the metric values M = 1 and M = 0, respectively. Since the number of these APPs does not exceed the limit number Z = 21 alternative received sequences having the smallest metric values, both sequences are selected and stored.

For selected APPs, the next parts of the alternative reconstructed information sequence corresponding to this alternative received sequence and metric values are stored. For example, at the moment of receiving the ninth character of the received sequence for an APT of the form “0001 1110 0” and an APT of the form “0001 1110 1”, the first two consecutive parts of the corresponding alternative restored information sequences of the form “0 0” and the metric value M = 1 and M = 0, respectively.

Upon receipt of the next bit of the received sequence, each of the two stored APT receives two continuation sequences, etc. In processing the thirteenth in FIG. 11 characters of the received sequence form 32 APPs with metric values from M = 0 to M = 4, from which Z = 21 are selected according to the APT metric, etc. The erasure of the worst-case AMP metrics is indicated by the symbol “X” in FIG. eleven.

" на фиг. 11. Например, при обработке семнадцатого по счету на фиг. 11 символа принятой последовательности оказалась стертой альтернативная принятая последовательность с ее продолжением вида "0001 1110 1100 0110 1" со значением метрики М=0, которая по этой причине ранее считалась наиболее предпочтительной при выборе среди альтернативных принятых последовательностей. Действия декодирования для этой альтернативной принятой последовательности, идентичной принятой последовательности, показаны на фиг. 14. В результате декодирования символов данной последовательности, показанной на фиг. 8(e), получена АВП вида "0 0 0 1 0 0 1 0", показанная на фиг. 8(ж). Например, после декодирования восьмого по счету символа очередной части АВП при выделении разрешенных подинтервалов, показанных на фиг. 14 (продолжение) в предпоследней строке, текущее значение данной альтернативной принятой последовательности, равное 141, сравнивают с границами текущего значения подинтервала декодирования нулевого символа АПП DD₀, находящимися в пределах от 96 до 132, и с границами текущего значения подинтервала декодирования единичного символа АПП DD₁, находящимися в пределах от 142 до 143. Так как текущее значение альтернативной принятой последовательности не находится в пределах разрешенных подинтервалов декодирования, то стирают данную альтернативную принятую последовательность.Starting from a certain point in time, the number of alternative alternate received sequences continues to decrease because in many APPs their current value is outside the limits of the current allowed decoding sub-intervals of these APPs, that is, such sequences could not be formed on the transmitting side and, accordingly, they must be erased and they do not continue further, as shown by the symbol "

"in Fig. 11. For example, when processing the seventeenth in a row in Fig. 11 character of the received sequence, the alternative accepted sequence was deleted with its continuation of the form" 0001 1110 1100 0110 1 "with the metric value M = 0, which for this reason was previously considered the most preferred when choosing among alternative received sequences. The decoding steps for this alternative received sequence identical to the received sequence are shown in Fig. 14. As a result of decoding the symbols of this sequence, the sequence shown in Fig. 8 (e), a WUA of the form “0 0 0 1 0 0 1 0” is shown in Fig. 8 (g). For example, after decoding the eighth symbol of the next part of the WUA when highlighting the allowed sub-intervals, shown in Fig. 14 (continued) in the penultimate line, the current value of this alternative received sequence, equal to 141, is compared with the boundaries of the current value of the decoding sub-interval of the zero symbol of the APP DD ₀ , ranging from 96 to 132, and with the boundaries of the current value of the decoding sub-interval single character of the APT DD ₁ , ranging from 142 to 143. Since the current value of the alternative received sequence is not within the allowed decoding sub-intervals, this alternative received sequence is erased.

Similarly, the number of APPs is erased and the number of continued APPs is reduced to 17, and then to 8, as shown in FIG. eleven.

Decoding APP of the form "0001 1110 0000 01110 1" with a metric value of M = 2 is shown in FIG. 15. In the arithmetic decoding of seventeen characters of a given APP shown in FIG. 8 (h), the first nine parts of the alternative reconstructed information sequence of the form “0 0 0 1 0 0 0 0 1” shown in FIG. 8 (s). As shown in FIG. 11, this APP has a metric of M = 2 and is one of eight APPs preserved from all APPs upon receipt of the first seventeen bits of the received sequence. However, the remaining APPs have metric values of M = 3 or more. In the course of further decoding, the alternative accepted sequence will continue to have the smallest metric value, continuing the identified APP with the metric M [17] = 2, since the rest of the APP with any possible continuations cannot provide a metric value less than M = 3.

After the receipt of the next bits of the received sequence stops, the metric values of the alternative received sequences are compared and the sequence with the lowest metric value is selected from them. In the given example, the continuation of the AMS of the form “0001 1110 0000 01110 1” with the metric value on the seventeenth received bit M [17] = 2, for which two transmission errors are corrected on the first seventeen bits of the received sequence, will be selected.

Next, the recipient, as the reconstructed information sequence, corresponds to the selected alternative received alternative sequence, the reconstructed alternative information sequence. The first continuation of the AMS of the type "0001 1110 0000 01110 1" selected in the example corresponds to the first nine parts of the alternative reconstructed information sequence of the form "0 0 0 1 0 0 0 0 1" shown in FIG. 8 (s).

In this example, joint arithmetic and noise-correcting coding and decoding provides the correction of two transmission errors in the received sequence.

Verification of the theoretical premises of the claimed method of joint arithmetic and noise-correcting coding and decoding was carried out by means of its analytical studies.

Joint arithmetic and noise-resistant coding and decoding of the next parts of length k = 1 bit of the excess information sequence with a total length of 1024 bits was performed using the prototype method for which the error-correcting code speed values R = 1/2 and R = 2/3 were selected. We also performed joint arithmetic and noise-resistant coding and decoding of the next parts of length k = 1 bit of the same redundant information sequence with a total length of 1024 bits using the proposed method when choosing the error detection coefficient and equal to the speed of the error-correcting code R = 1/2 and R = 2 / 3. It was revealed that when transmitting encoded sequences over the communication channel with errors, in all cases, correction of a larger number of transmission errors using the proposed method is provided in comparison with the prototype method. Moreover, with an increase in the limit number Z of alternative received sequences to 24 ... 32, in addition to single and double errors, the correction of triple and some quadruple transmission errors is provided.

The conducted studies confirm that when using the proposed method of joint arithmetic and noise-resistant coding and decoding, the noise immunity of the transmission of the next parts of the encoded sequence under the influence of multiple transmission errors is increased.

Claims (5)

1. The method of joint arithmetic and error-correcting encoding and decoding, which consists in first setting the initial interval of arithmetic encoding on the transmitting side and the initial arithmetic decoding interval corresponding to it, on the transmitting side, the next part of the information sequence of length k ≥1 bit, divide the current arithmetic coding interval of length D> 2 into the current subinterval Al encoding a zero character of length D0 and to the current sub-interval of encoding a single character of length D1, perform arithmetic coding of the next part of the sequence into the next part of the encoded sequence, transmit the next part of the sequence to the receiving side, perform the above actions on the transmitting side until the next parts arrive information sequence, on the receiving side, the sequence is received, the current interval of arithmetic decoding is shared With a length of DD> 2, to the current sub-interval of decoding the null character DD0 and to the current sub-interval of decoding a single character DD1, the next parts of the received sequence are arithmetically decoded into the next parts of the sequence, the above actions are performed on the receiving side until the received sequence arrives, and the recipient is restored information sequence, characterized in that pre-set the limit number Z≥2 alternative received sequence to it and the metric value of the alternative received sequences to zero, on the transmitting side, depending on m≥1 previously encoded symbols of information symbols from the current sub-interval of arithmetic coding of a zero symbol of length D0≥2, the current allowed sub-interval of coding of a zero symbol of length D0 _a is selected, where 1≤ D0 _a <D0, and from the current coding subinterval of a single symbol of length D1≥2, the current allowed coding subinterval of a single character of length D1 _a is selected, where 1≤D1 _a <D1, in accordance with which they perform arithmetic coding of the next part of the information sequence into the next part of the encoded sequence that is transmitted to the receiving side, the next bit of the sequence is received on the receiving side, the current arithmetic decoding interval of length DD of each alternative received sequence is divided into the current decoding sub-interval of the length of the symbol DD0≥2 and to the current sub-interval of decoding a single symbol of length DD1≥2, of which, depending on m characters of the restored information sequence of each alternative received sequence allocate the current allowed decoding sub-interval of _a null symbol of length DD0 _a , where 1≤DD0 _a <DD0, and, accordingly, the current allowed decoding sub-interval of _a single character of length DD1 _a , where 1≤DD1 _a <DD1, if the current value of the alternative received sequence is not within the current allowed decoding subinterval of a null character or the current allowed decoding subinterval of one symbol of this alternative received sequence, then this alternative received sequence is erased, otherwise the alternative received sequence is arithmetically decoded in accordance with the current allowed decoding sub-intervals into successive parts of the corresponding alternative restored sequence, for each alternative received sequence, the sequence is continued in the form of a null character and continued sequences in the form of a unit si ox, set the metric of the continuation of the sequence in the form of a null character and the value of the metric of the continuation of the sequence in the form of a single symbol relative to the next bit of the received sequence, for each alternative received sequence with its continuation of the sequence, calculate the value of its metric, which sums up the metric of this sequence and its metric continuation of the sequence, compare the values of the metrics of alternative accepted identities with their sequence extensions and choose from them no more than the maximum number Z of alternative received sequences having the smallest metric values that complement the corresponding sequence extensions, for these alternative received sequences the next parts of the corresponding alternative restored information sequences and metric values are stored, the listed actions on the receiving side until the next bits arrive at of the selected sequence, the metric values of the alternative received sequences are compared and the sequence with the lowest metric value is selected from them, and then the recipient receives, as the restored information sequence, the alternative alternative information sequence corresponding to the selected alternative received sequence. 2. The method according to claim 1, characterized in that, on the transmitting side, depending on m previously encoded symbols of the information sequence, the length D0 _{a of the} current allowed coding sub-interval of the zero symbol is selected as D0 _a = a ^m, D0, and the length D1 _{a of the} current allowed sub-interval the encoding unit is selected as a symbol D1 _a = _a ^m ⋅D1, wherein the coefficient of the error detection and is selected in the range 0 <a <1. 3. The method according to p. 1, characterized in that, on the receiving side, depending on m characters of the restored information sequence of each alternative received sequence, the length DD0 _{a of the} current allowed decoding interval of the zero symbol is selected as DD0 _a = a ^m ⋅ DD0, and the length DD1 _a the current allowed decoding sub-interval of a single symbol is selected as DD1 _a = a ^m ⋅DD1. 4. The method according to p. 1, characterized in that the value of the continuation metric in the form of a zero symbol relative to the next bit of the received sequence is set to zero if the next bit of the received sequence is a zero bit, otherwise set to a single value. 5. The method according to claim 1, characterized in that the value of the continuation metric in the form of a single symbol relative to the next bit of the received sequence is set to zero if the next bit of the received sequence is a single bit, otherwise set to a single value.

Images