RU2752868C1

RU2752868C1 - Method for arithmetic encoding and decoding

Info

Publication number: RU2752868C1
Application number: RU2020128345A
Authority: RU
Inventors: Игорь Николаевич Оков; Андрей Александрович Устинов
Priority date: 2020-08-24
Filing date: 2020-08-24
Publication date: 2021-08-11

Abstract

FIELD: information technology.

SUBSTANCE: invention relates to the field of electrocommunication and information technology. The technical result is achieved by the fact that the next information sequence with a length of k>2 bits is received by the transmitting side, the values of the conditional probability of the appearance of the next bit thereof from the previous bits are calculated, 2≤m<<k of the largest values of the conditional probability of the appearance of the next bit of the next information sequence are selected, the current values of the conditional probability of encoding the null character and the single character are set corresponding with the selected values of the probability, the current arithmetic encoding interval is divided into the current sub-interval of encoding the null character and the current sub-interval of encoding the single character, depending on the current values of the conditional probability of encoding the null character and the single character, arithmetic encoding of the next bit is executed, depending on the previous bits with the current values of the conditional probability, the current values of the conditional probability of encoding the null character and the single character are recalculated and subsequent actions are performed until the next bits of the next information sequence are exhausted, and similar actions of arithmetic decoding are performed on the receiving side, depending on the previous decoded bits with the current values of the conditional probability.

EFFECT: reduced rate of transmission over the transmission channel of the en coded sequence.

1 cl, 7 dwg

Description

Заявленное техническое решение относится к области электросвязи и информационных технологий, а именно к технике сжатия и последующего восстановления избыточной двоичной информации.The claimed technical solution relates to the field of telecommunications and information technology, namely to the technique of compression and subsequent recovery of redundant binary information.

Заявленное изобретение может быть использовано для сжатия избыточной двоичной информации для ее передачи с меньшей скоростью по каналам передачи и хранения в устройствах памяти с меньшей емкостью.The claimed invention can be used to compress redundant binary information for transmission at a lower rate through transmission channels and storage in memory devices with a lower capacity.

Известен способ арифметического кодирования и декодирования информационных последовательностей, описанный, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. В данном аналоге на передающей стороне от источника информационной последовательности принимают очередную информационную последовательность, устанавливают начальные значения вероятности кодирования нулевого символа и единичного символа, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередного бита очередной информационной последовательности, уточняют текущие значения вероятности кодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных битов очередной информационной последовательности, передают очередную кодированную последовательность на приемную сторону, на приемной стороне устанавливают начальные значения вероятности декодирования нулевого символа и единичного символа, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, выполняют арифметическое декодирование очередного бита очередной принятой последовательности в очередные биты очередной восстановленной информационной последовательности, уточняют текущие значения вероятности декодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных бит очередной принятой последовательности, передают получателю очередную восстановленную информационную последовательность.The known method of arithmetic coding and decoding of information sequences, described, for example, in the book D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Methods of data compression. The device of archivers, compression of images and video." - M., DIALOG-MEPhI, 2002, pp. 35-43. In this analogue, on the transmitting side from the source of the information sequence, the next information sequence is received, the initial values of the probability of encoding the zero symbol and the single symbol are set, the current arithmetic coding interval is divided into the current coding sub-interval of the zero symbol and into the current coding sub-interval of a single character, arithmetic coding of the next bit is performed the next information sequence, specify the current values of the probability of encoding the zero symbol and the single symbol and perform subsequent actions until the next bits of the next information sequence are exhausted, transmit the next encoded sequence to the receiving side, set the initial values of the probability of decoding the zero symbol and the single symbol on the receiving side, divide the current arithmetic decoding interval for the current decoding subinterval of the null symbol and for the current decoding subinterval of a single symbol, perform arithmetic decoding of the next bit of the next received sequence into the next bits of the next restored information sequence, clarify the current values of the decoding probability of the zero symbol and the single symbol and perform subsequent actions until the next bits of the next received sequence are exhausted, transmit the next restored information sequence to the recipient ...

Недостатком указанного аналога является кодирование избыточных информационных последовательностей только с использованием усредненных значений вероятности кодирования нулевого символа и единичного символа среди закодированных битов, что для информационных последовательностей с существенными корреляционными зависимостями приводит к неэффективному использованию пропускной способности канала передачи, вызванному неполным удалением избыточности в сжимаемых последовательностях.The disadvantage of this analogue is the coding of redundant information sequences only using the averaged values of the probability of encoding the zero symbol and the single symbol among the encoded bits, which for information sequences with significant correlation dependences leads to inefficient use of the transmission channel capacity caused by incomplete removal of redundancy in the compressed sequences.

Известен также способ арифметического кодирования и декодирования спектральных коэффициентов по патенту РФ 2565501 МПК Н03М 7/40 (2006.01) от 01.10.2010. Данный способ включает арифметическое кодирование текущего спектрального коэффициента с использованием предыдущих спектральных коэффициентов, причем упомянутые предыдущие спектральные коэффициенты уже закодированы, упомянутые предыдущие спектральные коэффициенты и упомянутый текущий спектральный коэффициент содержатся в одном или более квантованных спектрах, которые являются результатом квантования результата частотно-временного преобразования значений дискретизации видео-, аудио- или голосовых сигналов, и содержит этапы, на которых:There is also known a method of arithmetic coding and decoding of spectral coefficients according to RF patent 2565501 IPC Н03М 7/40 (2006.01) dated 01.10.2010. This method includes arithmetic coding of the current spectral coefficient using previous spectral coefficients, wherein said previous spectral coefficients have already been encoded, said previous spectral coefficients and said current spectral coefficient are contained in one or more quantized spectra, which are the result of quantizing the result of time-frequency transform of sampling values video, audio or voice signals, and contains the stages at which:

- обрабатывают предыдущие спектральные коэффициенты;- process the previous spectral coefficients;

- используют обработанные предыдущие спектральные коэффициенты для определения класса контекста из по меньшей мере двух различных классов контекста, причем сумму квантованных абсолютных значений предыдущих спектральных коэффициентов используют для определения класса контекста;- use the processed previous spectral coefficients to determine the class of the context from at least two different classes of the context, and the sum of the quantized absolute values of the previous spectral coefficients is used to determine the class of the context;

- используют определенный класс контекста и отображение из по меньшей мере двух различных классов контекста по меньшей мере в две различных функции плотности вероятности для определения одной из функций плотности вероятности;- using a certain class of context and a mapping from at least two different classes of context to at least two different probability density functions to determine one of the probability density functions;

- выполняют арифметическое кодирование текущего спектрального коэффициента на основании определенной функции плотности вероятности, причем упомянутая обработка предыдущих спектральных коэффициентов содержит неравномерное квантование абсолютных значений предыдущих спектральных коэффициентов для использования при определении класса контекста.- performing arithmetic coding of the current spectral coefficient based on the determined probability density function, and the said processing of the previous spectral coefficients contains non-uniform quantization of the absolute values of the previous spectral coefficients for use in determining the class of the context.

Недостатками указанного аналога являются сужение области использования арифметического кодирования и декодирования только для источников видео, аудио или речевого сигнала, которые должны предварительно обрабатываться методами частотного преобразования с формированием спектральных коэффициентов, а также сложность достаточно точного определения типа функции плотности вероятности кодируемых спектральных коэффициентов, что приводит к снижению достигаемого коэффициента сжатия кодируемых сигналов.The disadvantages of this analogue are the narrowing of the area of use of arithmetic coding and decoding only for video, audio or speech signal sources, which must be pre-processed by frequency conversion methods with the formation of spectral coefficients, as well as the complexity of a sufficiently accurate determination of the type of the probability density function of the encoded spectral coefficients, which leads to reduction of the achieved compression ratio of the encoded signals.

Наиболее близким по своей технической сущности к заявленному способу арифметического кодирования и декодирования является способ совместного арифметического и помехоустойчивого кодирования и декодирования по патенту РФ 2611022 МПК Н04М 13/00 (2006.01) от 28.01.2016. Способ - прототип арифметического кодирования и декодирования заключается в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информации принимают очередную часть информационной последовательности (ИП) длиной k>2 бит, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выбирают проверочные символы длиной r≥1 бит, для чего для каждого проверочного символа выделяют среди текущего подинтервала кодирования нулевого символа и текущего подинтервала кодирования единичного символа текущий подинтервал, включающий середину начального интервала арифметического кодирования, и устанавливают проверочным символом такой символ, который соответствует выделенному текущему подинтервалу, выбранные проверочные символы записывают вместе с очередной частью информационной последовательности в очередную часть помехоустойчивой последовательности, выполняют арифметическое кодирование очередной части помехоустойчивой последовательности в очередную часть кодированной последовательности, передают очередную часть кодированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне получают очередную часть принятой последовательности, которую запоминают, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют в очередные части декодированной последовательности, из которых выделяют очередные части восстановленной информационной последовательности и декодированные проверочные символы, делают вывод об отсутствии ошибок передачи, если текущий подинтервал декодирования каждого из декодированных проверочных символов включает середину начального интервала арифметического кодирования, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, передают получателю очередную часть восстановленной информационной последовательности, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части принятой последовательности.The closest in technical essence to the claimed method of arithmetic coding and decoding is a method of joint arithmetic and noise-immune coding and decoding according to RF patent 2611022 IPC Н04М 13/00 (2006.01) dated 28.01.2016. The method - a prototype of arithmetic coding and decoding consists in the fact that the initial arithmetic coding interval is preliminarily set on the transmitting side and the corresponding initial arithmetic decoding interval on the receiving side, the next part of the information sequence (IP) of length k> 2 is received on the transmitting side from the information source bit, divide the current arithmetic coding interval into the current coding subinterval of the zero symbol and into the current coding subinterval of a single symbol, select check symbols of length r ≥ 1 bit, for which, for each check symbol, the current subinterval, including the middle of the initial interval of arithmetic coding, and set the check symbol to such a symbol that corresponds to the selected current subinterval, the selected check symbols they are written together with the next part of the information sequence into the next part of the noise-immune sequence, perform arithmetic coding of the next part of the noise-resistant sequence into the next part of the coded sequence, transmit the next part of the coded sequence to the receiving side, perform the listed actions on the transmitting side until the next parts arrive information sequence, on the receiving side, the next part of the received sequence is obtained, which is stored, the current arithmetic decoding interval is divided into the current decoding subinterval of the zero symbol and into the current decoding subinterval of a single symbol, the stored successive parts of the received sequence are arithmetically decoded into the next parts of the decoded sequence, from which successive parts of the recovered information sequence and decoded check symbols , it is concluded that there are no transmission errors if the current decoding subinterval of each of the decoded check symbols includes the middle of the initial arithmetic coding interval, otherwise one or more bits in the stored successive parts of the received sequence are inverted one by one and their arithmetic decoding is performed until the conclusion that there are no transmission errors is reached, the next part of the restored information sequence is transmitted to the recipient, the listed actions are performed on the receiving side until the next parts of the received sequence arrive.

Способ-прототип арифметического кодирования и декодирования обеспечивает возможность сжатия на передающей стороне и восстановление на приемной стороне сжатой избыточной информационной последовательности, избыточность которой зависит от равномерно распределенных предыдущих закодированных двоичных символов данной последовательности.The prototype method of arithmetic coding and decoding provides the possibility of compression on the transmitting side and recovery on the receiving side of the compressed redundant information sequence, the redundancy of which depends on the uniformly distributed previous coded binary symbols of the given sequence.

Однако, недостатком ближайшего аналога (прототипа) является необходимость использования высокой скорости передачи по каналу передачи кодированной последовательности или большей емкости устройств ее запоминания при арифметическом кодировании и декодировании двоичных информационных последовательностей с неравномерной зависимостью от предшествующих битов, и при изменении характера этой зависимости от одной информационной последовательности к другой.However, the disadvantage of the closest analogue (prototype) is the need to use a high transmission rate through the transmission channel of the coded sequence or a larger capacity of storage devices for arithmetic coding and decoding of binary information sequences with an uneven dependence on the previous bits, and when the nature of this dependence on one information sequence changes. to another.

Техническим результатом заявляемого технического решения является арифметическое кодирование и декодирование избыточной двоичной информационной последовательности, обеспечивающее уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.The technical result of the proposed technical solution is arithmetic coding and decoding of a redundant binary information sequence, providing a reduction in the transmission rate through the transmission channel of the coded sequence or a decrease in the capacity of its storage devices.

Указанный технический результат в заявляемом способе арифметического и кодирования и декодирования, достигается тем, что в известном способе арифметического кодирования и декодирования, заключающимся в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информационной последовательности принимают очередную информационную последовательность длиной k>2 бит, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование последовательности, и выполняют на передающей стороне перечисленные действия до исчерпания очередных бит очередной информационной последовательности, передают очередную кодированную последовательность на приемную сторону, на приемной стороне получают очередную принятую последовательность, которую запоминают, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, выполняют арифметическое декодирование очередных бит очередной принятой последовательности в очередной бит очередной последовательности, выполняют перечисленные действия на приемной стороне до исчерпания очередных бит очередной принятой последовательности, передают получателю очередную восстановленную информационную последовательность, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные принятые последовательности, дополнительно предварительно для передающей стороны и приемной стороны выбирают начальную двоичную последовательность длиной n>1 бит, на передающей стороне после получения очередной информационной последовательности вычисляют значения условной вероятности появления ее очередного бита, включая предварительно выбранную начальную двоичную последовательность, от предыдущих битов, предшествующих очередному на d, где d=1, 2, …, k-1, позиций, выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной информационной последовательности, устанавливают текущие значения условной вероятности кодирования нулевого символа и единичного символа соответствующими выбранным значениям вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условной вероятности кодирования нулевого символа и единичного символа, выполняют арифметическое кодирование очередного бита очередной информационной последовательности, с учетом предварительно выбранной начальной двоичной последовательности, в зависимости от предшествующих битов с текущими значениями условной вероятности, повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных битов очередной информационной последовательности, передают m выбранных значений условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования на приемную сторону, на приемной стороне получают принятые значения условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования, которые запоминают, устанавливают текущие значения условной вероятности декодирования нулевого символа и единичного символа соответствующими принятым значениям условной вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в зависимости от текущих значений условной вероятности декодирования нулевого символа и единичного символа, выполняют арифметическое декодирование очередных бит очередной принятой последовательности в очередной бит очередной восстановленной информационной последовательности, с учетом предварительно выбранной начальной двоичной последовательности, в зависимости от предшествующих битов, с текущими значениями условной вероятности декодирования нулевого символа и единичного символа.The specified technical result in the inventive method of arithmetic and coding and decoding is achieved by the fact that in the known method of arithmetic coding and decoding, which consists in the fact that the initial arithmetic coding interval is preliminarily set on the transmitting side and the corresponding initial arithmetic decoding interval is set on the receiving side, on the transmitting side from the source of the information sequence receive the next information sequence with a length of k> 2 bits, divide the current arithmetic coding interval into the current coding subinterval of the zero symbol and the current coding subinterval of a single character, perform arithmetic coding of the sequence, and perform the listed actions on the transmitting side until the next bit of the next information sequence, transmit the next coded sequence to the receiving side, on the receiving side receive the next th received sequence, which is stored, divide the current interval of arithmetic decoding into the current sub-interval of decoding of the zero symbol and into the current sub-interval of decoding of a single symbol, perform arithmetic decoding of the next bits of the next received sequence into the next bit of the next sequence, perform the listed actions on the receiving side until the next bits are exhausted of the next received sequence, transmit the next recovered information sequence to the receiver, perform the listed actions on the receiving side until the next received sequences arrive, additionally, for the transmitting side and the receiving side, an initial binary sequence with a length of n> 1 bit is selected, on the transmitting side after receiving the next information sequence, the values of the conditional probability of the appearance of its next bit are calculated, including the preselected start the actual binary sequence, from the previous bits preceding the next one by d, where d = 1, 2, ..., k-1, positions, select 2≤m << k of the largest values of the conditional probability of the appearance of the next bit of the next information sequence, set the current values of the conditional the probabilities of coding a zero symbol and a single character corresponding to the selected values of the probability of the appearance of the next bit of the next information sequence with the corresponding precedence position numbers, divide the current arithmetic coding interval into the current coding sub-interval of the zero character and into the current coding sub-interval of a single character, depending on the current values of the conditional probability of coding of the zero character and single symbol, perform arithmetic coding of the next bit of the next information sequence, taking into account the preselected initial binary sequence, depending on the previous bits with current values of the conditional probability, recalculate the current values of the conditional probability of encoding a zero symbol and a single symbol and perform subsequent actions until the next bits of the next information sequence are exhausted, transmit m selected values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding precedence position numbers to the receiving side , on the receiving side, the received values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding precedence position numbers are obtained, which are stored, the current values of the conditional probability of decoding the zero symbol and the single character are set corresponding to the accepted values of the conditional probability of the appearance of the next bit of the next information sequence with the corresponding numbers precedence positions, split the current interval arithmetic decoded for the current decoding subinterval of the zero symbol and for the current decoding subinterval of a single symbol, depending on the current values of the conditional probability of decoding the zero symbol and the single symbol, perform arithmetic decoding of the next bits of the next received sequence into the next bit of the next restored information sequence, taking into account the preselected initial binary sequences, depending on the preceding bits, with the current values of the conditional decoding probability of the zero symbol and the single symbol.

Указанная новая совокупность существенных признаков за счет определения наиболее значимых зависимостей очередного бита информационной последовательности от предыдущих ее битов, и арифметического кодирования очередного бита очередной информационной последовательности в зависимости от выявленных зависимостей позволяет увеличить коэффициент сжатия избыточной двоичной информационной последовательности, что обеспечивает уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.The specified new set of essential features by determining the most significant dependencies of the next bit of the information sequence on its previous bits, and arithmetic coding of the next bit of the next information sequence, depending on the identified dependencies, makes it possible to increase the compression ratio of the redundant binary information sequence, which ensures a decrease in the transmission rate over the transmission channel coded sequence or a decrease in the capacity of devices for storing it.

Заявленный способ поясняется чертежами, на которых показаны:The claimed method is illustrated by drawings, which show:

- на фиг. 1 - система арифметического кодирования и декодирования;- in Fig. 1 - system of arithmetic coding and decoding;

- на фиг. 2 - алгоритм арифметического кодирования на передающей стороне;- in Fig. 2 - an arithmetic coding algorithm on the transmitting side;

- на фиг. 3 - временные диаграммы арифметического кодирования;- in Fig. 3 - timing diagrams of arithmetic coding;

-на фиг. 4 - таблица состояний арифметического кодирования первых 18 битов информационной последовательности;- in fig. 4 is a table of states of arithmetic coding of the first 18 bits of the information sequence;

- на фиг. 5 - таблица наибольших значений условной вероятности появления очередного бита, равного нулевому значению, данной очередной ИП от m=8 комбинаций с наибольшими значениями условной вероятности;- in Fig. 5 - table of the highest values of the conditional probability of occurrence of the next bit, equal to zero, given the next IP from m = 8 combinations with the highest values of the conditional probability;

- на фиг. 6 - алгоритм арифметического декодирования на приемной стороне;- in Fig. 6 - an algorithm for arithmetic decoding on the receiving side;

- на фиг. 7 - таблица состояний арифметического декодирования первых 14 битов принятой последовательности;- in Fig. 7 is a table of states of arithmetic decoding of the first 14 bits of the received sequence;

Реализация заявленного способа представлена на примере системы - система арифметического кодирования и декодирования, показанной на фиг. 1. На передающей стороне при получении от отправителя очередной информационной последовательности в блоке вычисления условной вероятности 1 вычисляют значения условной вероятности появления очередного бита очередной информационной последовательности от различных сочетаний предшествующих битов, на основе которых в блоке выбора значений 2 выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной информационной последовательности, которые с выхода блока выбора значений 2 поступают в формирователь модели кодирования 3, устанавливая для очередной информационной последовательности начальные значения условных вероятностей кодирования нулевого символа и единичного символа в зависимости от предыдущих закодированных двоичных символов очередной информационной последовательности. На основе полученных с выхода формирователя модели кодирования 3 значений условной вероятности в арифметическом кодере 4 разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, и выполняют арифметическое кодирование очередного бита очередной информационной последовательности. По результатам арифметического кодирования очередного бита в формирователе модели кодирования 3 уточняются текущие значения условных вероятностей кодирования. По завершению кодирования очередной информационной последовательности кодированная последовательность через канал передачи 5 передается на приемную сторону вместе с выбранными в блоке 2 значениями условной вероятности и соответствующих им номеров позиций предшествования.The implementation of the claimed method is presented on the example of the system - the arithmetic coding and decoding system shown in Fig. 1. On the transmitting side, upon receipt of the next information sequence from the sender in the block for calculating the conditional probability 1, the values of the conditional probability of the appearance of the next bit of the next information sequence from various combinations of previous bits are calculated, on the basis of which 2≤m << k largest values of the conditional probability of the appearance of the next bit of the next information sequence, which from the output of the value selection unit 2 enter the coding model generator 3, setting for the next information sequence the initial values of the conditional probabilities of encoding the zero symbol and the single symbol, depending on the previous encoded binary symbols of the next information sequence. Based on the values of the conditional probability obtained from the output of the coding model generator 3 in the arithmetic encoder 4, the current arithmetic coding interval is divided into the current coding subinterval of the zero symbol and into the current coding subinterval of a single symbol, and arithmetic coding of the next bit of the next information sequence is performed. According to the results of the arithmetic coding of the next bit in the coding model generator 3, the current values of the conditional coding probabilities are refined. Upon completion of the coding of the next information sequence, the coded sequence is transmitted through the transmission channel 5 to the receiving side together with the values of the conditional probability selected in block 2 and the corresponding precedence position numbers.

На приемной стороне в формирователе модели декодирования 6 на основе принятых значений условной вероятности и соответствующих им номеров позиций предшествования устанавливают для декодирования очередной принятой последовательности начальные значения условной вероятности декодирования нулевого символа и единичного символа в зависимости от предыдущих декодированных двоичных символов. На основе полученных с выхода формирователя модели декодирования 6 значений условных вероятностей в арифметическом декодере 7 разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, и выполняют арифметическое декодирование очередного принятого бита. По результатам арифметического декодирования очередного принятого бита в формирователе модели декодирования 6 уточняются текущие значения условной вероятности декодирования. По завершению декодирования очередной принятой последовательности очередная восстановленная информационная последовательность передается получателю.On the receiving side, in the decoding model generator 6, on the basis of the received conditional probability values and their corresponding precedence position numbers, the initial values of the conditional probability of decoding the zero symbol and the single symbol are set for decoding the next received sequence, depending on the previous decoded binary symbols. Based on the values of conditional probabilities obtained from the output of the decoding model generator 6 in the arithmetic decoder 7, the current arithmetic decoding interval is divided into the current decoding subinterval of the zero symbol and the current decoding subinterval of a single symbol, and arithmetic decoding of the next received bit is performed. According to the results of arithmetic decoding of the next received bit in the decoding model generator 6, the current values of the conditional decoding probability are refined. Upon completion of decoding of the next received sequence, the next recovered information sequence is transmitted to the recipient.

В способе реализуют следующую последовательность действий.The method implements the following sequence of actions.

Алгоритм арифметического кодирования на передающей стороне представлен на фигуре 2.The arithmetic coding algorithm on the transmitting side is shown in figure 2.

Предварительный выбор для передающей стороны и приемной стороны начальной двоичной последовательности (НДП) длиной n>1 бит заключается, например, в определении одной из наиболее часто встречающихся двоичных последовательностей заданной длины источника информационных последовательностей. Однако, даже если источник ИП является нестационарным и статистические характеристики генерируемых последовательностей меняются во времени, что затрудняет точный выбор НДП, то неточность выбора последовательности в качестве начальной двоичной последовательности, не характерной для текущего состояния источника ИП, не приводит к существенному ухудшению коэффициента сжатия, так как арифметический кодек в силу своей адаптивности быстро приспосабливается к текущим статистическим характеристикам кодируемых последовательностей. Поэтому в качестве начальной двоичной последовательности при неизвестности или непредсказуемости статистических характеристик генерируемых последовательностей также может быть использована, например, случайная последовательность. Примерный вид начальной двоичной последовательности длиной n=5 бита "10010" показан на фиг. 3(a). Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов в виде незаштрихованных импульсов.The pre-selection for the transmitting side and the receiving side of the initial binary sequence (NDS) with a length of n> 1 bits consists, for example, in determining one of the most common binary sequences of a given length of the source of information sequences. However, even if the IP source is non-stationary and the statistical characteristics of the generated sequences change over time, which makes it difficult to accurately select the NDP, then the inaccuracy of the choice of the sequence as the initial binary sequence, which is not typical for the current state of the IP source, does not lead to a significant deterioration in the compression ratio, so as an arithmetic codec, due to its adaptability, it quickly adapts to the current statistical characteristics of the encoded sequences. Therefore, when the statistical characteristics of the generated sequences are unknown or unpredictable, a random sequence can also be used as an initial binary sequence. An exemplary view of an initial n = 5 bit "10010" binary sequence is shown in FIG. 3 (a). One bit values in the figures are shown as shaded pulses, zero bit values are shown as unshaded pulses.

Способы предварительной установки на передающей стороне начального интервала арифметического кодирования и на приемной стороне соответствующего ему начального интервала арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования начинается от его начального нижнего значения и заканчивается его начальным верхним значением. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования H[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического кодирования представлен на фиг. 4 при t=0 (первая строка).Methods for presetting the initial arithmetic coding interval on the transmitting side and on the receiving side of the corresponding initial arithmetic decoding interval are known and described, for example, in the book D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Data compression methods. , Image and Video Compression ". - M., DIALOG-MEPhI, 2002, pp. 35-43. The initial arithmetic coding interval starts from its initial low value and ends with its initial high 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 the coding interval values with eight binary symbols, the initial lower value of the coding interval of the arithmetic coding L [0] at time t = 0 is set to the minimum value equal to zero value in decimal notation or 0000 0000 in binary representation, where the upper binary characters recorded from the left, and the initial upper value of the arithmetic coding interval H [0] is set to a maximum value of 255 in decimal representation or 1111 1111 in binary representation. An example of an arithmetic coding start interval is shown in FIG. 4 at t = 0 (first line).

На передающей стороне от источника ИП принимают очередную информационную последовательность длиной k>2 бит. Примерный вид первых 18 бит очередной ИП вида "0010 0110 0010 0010 01" показан на фиг. 3(б).On the transmitting side, the next information sequence of length k> 2 bits is received from the IP source. An exemplary view of the first 18 bits of the next IP of the form "0010 0110 0010 0010 01" is shown in FIG. 3 (b).

Далее вычисляют значения условной вероятности появления очередного бита очередной ИП, включая предварительно выбранную начальную двоичную последовательность, от предыдущих битов, предшествующих очередному на d, где d=1,2, …, k-l, позиций, а также выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной ИП. Это позволяет для избыточных информационных последовательностей учесть при кодировании их существенную неравномерную зависимость от предшествующих битов, причем характер этой зависимости может меняться от одной информационной последовательности к другой.Next, the values of the conditional probability of the appearance of the next bit of the next IP are calculated, including the preselected initial binary sequence, from the previous bits preceding the next one by d, where d = 1,2, ..., kl, positions, and 2≤m << k largest values of the conditional probability of the appearance of the next bit of the next IP. This allows for redundant information sequences to take into account when coding their significant uneven dependence on the previous bits, and the nature of this dependence can vary from one information sequence to another.

Для этого последовательно для всех битов очередной ИП, начиная с ее первого бита, определяют значения условной вероятности появления очередного бита очередной ИП от различных комбинаций предшествующих ему битов. Например, в общем случае последовательно для всех битов очередной ИП, начиная с первого бита, определяют значения условной вероятности появления очередного бита очередной ИП от одного предшествующего бита a _i, отстоящего от него на одну, две, три и так далее позиций, не более k-1. В результате этого определяют не более k-1 значений того, что очередной бит очередной ИП примет нулевое значение, если предшествующий бит a _i, отстоящий от него на i=1, 2, …, k-1 позиций, имеет нулевое значение. Соответственно, значение условной вероятности того, что очередной бит очередной ИП примет единичное значение, если предшествующий бит a _i, отстоящий от него на i=1, 2, …, k-1 позиций, имеет нулевое значение, равно единица минус значение условной вероятности нулевого значения очередного бита очередной ИП при нулевом значении соответствующего предшествующего бита.To do this, sequentially for all bits of the next IP, starting from its first bit, the values of the conditional probability of the appearance of the next bit of the next IP from various combinations of the bits preceding it are determined. For example, in the general case, sequentially for all bits of the next IP, starting from the first bit, the values of the conditional probability of the appearance of the next bit of the next IP from one previous bit a _i , spaced from it by one, two, three and so on, are determined, no more than k -1. As a result, no more than k-1 values are determined that the next bit of the next IP will take a zero value if the previous bit a _i , located at i = 1, 2, ..., k-1 positions from it, has a zero value. Accordingly, the value of the conditional probability that the next bit of the next IP will take one value if the previous bit a _i , located at i = 1, 2, ..., k-1 positions from it, has a zero value, is equal to one minus the value of the conditional probability of zero the value of the next bit of the next MT at the zero value of the corresponding previous bit.

Также определяют значения условной вероятности появления очередного бита очередной ИП от двух предшествующих битов a _i и a _j, отстоящих от него на i=1, 2, …, k-1 и j=1, 2, …, k-1 позиций, от трех предшествующих битов и так далее.Also determine the values of the conditional probability of the appearance of the next bit of the next IP from the two previous bits a _i and a _j , spaced from it by i = 1, 2, ..., k-1 and j = 1, 2, ..., k-1 positions, from the three preceding bits, and so on.

Из полученных значений условной вероятности появления очередного бита очередной ИП от всех комбинаций предшествующих битов выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной ИП. Для этого перечисляют все полученные значения условной вероятности в порядке убывания их значений и первые m значений выбирают как наибольшие значения условной вероятности появления очередного бита очередной ИП.From the obtained values of the conditional probability of the appearance of the next bit of the next IP from all combinations of the previous bits, 2≤m << k of the largest values of the conditional probability of the appearance of the next bit of the next IP are selected. To do this, list all the obtained values of the conditional probability in descending order of their values and the first m values are selected as the largest values of the conditional probability of the appearance of the next bit of the next IP.

Для обеспечения практической реализуемости арифметического кодирования число m выбираемых наибольших значений должно быть существенно меньше длины к кодируемых информационных последовательностей, где длина k может быть сотни и тысячи бит, поэтому целесообразно выбирать число m не более 8…10. На практике вполне допустимо определить значения условной вероятности появления очередного бита очередной ИП от одиночных предшествующих битов, и затем выбирать 2≤m<<k наибольших значений условной вероятности от комбинаций предшествующих битов, среди которых использовать только выбранные одиночные предшествующие биты с наибольшими значениями условной вероятности появления очередного бита очередной ИП от одиночных предшествующих битов.To ensure the practical feasibility of arithmetic coding, the number m of the selected maximum values should be significantly less than the length k of the encoded information sequences, where the length k can be hundreds and thousands of bits, therefore it is advisable to choose the number m no more than 8 ... 10. In practice, it is quite acceptable to determine the values of the conditional probability of the appearance of the next bit of the next IP from single preceding bits, and then choose 2≤m << k of the largest values of the conditional probability from combinations of previous bits, among which to use only the selected single preceding bits with the highest values of the conditional probability of occurrence the next bit of the next IP from the single preceding bits.

В подавляющем большинстве источников информационных последовательностей корреляционные зависимости приблизительно экспоненциально ослабевают по мере удаления от очередного бита ИП, как описано, например, в книге Д. Прокис "Цифровая связь". - М., Радио и связь, 2000. Это позволяет на практике существенно уменьшить число перебираемых комбинаций предшествующих битов и ограничить число d не более десятков. Соответственно, это позволяет без существенной потери эффективности предлагаемого арифметического кодирования уменьшить число m выбираемых наибольших значений, а также позволяет ограничить длину n начальной двоичной последовательности не более десятков битов.In the overwhelming majority of sources of information sequences, the correlation dependences approximately exponentially weaken with distance from the next bit of the IP, as described, for example, in the book by D. Prokis "Digital Communication". - M., Radio and Communication, 2000. This allows in practice to significantly reduce the number of combinations of previous bits to be searched and limit the number d to no more than tens. Accordingly, this allows, without significant loss of efficiency of the proposed arithmetic coding, to reduce the number m of selected maximum values, and also allows limiting the length n of the initial binary sequence to no more than tens of bits.

Например, для очередной ИП длиной k=1028 бита определение значений условной вероятности появления очередного бита очередной ИП, включая предварительно выбранную начальную двоичную последовательность, было ограничено комбинациями предшествующих ему битов, отстоящих от него не более чем на d=5 позиций. При этом используют, например, случайно выбранную начальную двоичную последовательность длиной n=5 бит вида "10010", представленную на фиг. 3(a). На фиг. 3(в) показано, что НДП записывают перед очередной ИП по порядку следования битов. Например, для первого по счету (i=1) очередного бита очередной ИП, имеющего нулевое значение, первый предшествующий ему (i-1)-ый бит имеет нулевое значение, второй предшествующий ему (i-2)-ый бит имеет единичное значение, третий предшествующий ему (i-3)-ый бит имеет нулевое значение и т.д. Для данной очередной ИП выявлено, что очередной бит данной очередной ИП наиболее зависит от предшествующих битов, отстоящих от него на одну, три и четыре позиции. Множество из различных комбинаций данных трех предшествующих битов составляет 8 комбинаций. На фиг. 5 представлены m=8 наибольших значений условной вероятности появления очередного бита, равного нулевому значению, данной очередной ИП от m=8 комбинаций с наибольшими значениями условной вероятности. Для удобства кодирования комбинации предшествующих битов записаны в порядке i-3, i-4), начиная слева с бита выбранной комбинации наибольших значений.For example, for the next MT with a length of k = 1028 bits, the determination of the values of the conditional probability of the appearance of the next bit of the next MT, including the preselected initial binary sequence, was limited to combinations of the preceding bits, no more than d = 5 positions away from it. In this case, for example, a randomly selected initial binary sequence of length n = 5 bits of the form "10010" shown in FIG. 3 (a). FIG. 3 (c) shows that the PDT is written before the next IP in the order of the bits. For example, for the first (i = 1) sequential bit of the next MT, which has a zero value, the first preceding (i-1) -th bit has a zero value, the second preceding (i-2) -th bit has a one value, the third preceding (i-3) -th bit is zero, and so on. For this next IP, it was found that the next bit of this next IP most depends on the previous bits, which are one, three and four positions away from it. The plurality of different combinations of the data of the three preceding bits is 8 combinations. FIG. 5 shows the m = 8 highest values of the conditional probability of the appearance of the next bit, equal to zero, given the next MT from m = 8 combinations with the highest values of the conditional probability. For coding convenience, the preceding bit patterns are written in the order i-3, i-4), starting from the left of the bit of the selected highest value pattern.

Для каждой очередной ИП длиной k=1028 бита насчитывают 1028 реализаций выбранных m=8 комбинаций наибольших значений. Комбинация (i-1=0, i-3=0, i-4=0) выпала всего 252 раза, что обозначают как число появлений этой комбинации на момент времени t=0 вида N[0]/000=252, при этом при выпадении этой комбинации 180 раз очередной бит данной очередной ИП принимал нулевое значение (N0[0]/000=180), и 72 раза очередной бит данной очередной ИП принимал единичное значение (N1[0]/000=72). В соответствии с теорией вероятности по формуле вида р0[0]/000=N0[0]/000/N[0]/000=180/252=0,714 условная вероятность появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) равна 0,714. Соответственно, условная вероятность появления очередного бита данной очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) равна 0,286.For each successive IP with a length of k = 1028 bits, there are 1028 realizations of the selected m = 8 combinations of the largest values. The combination (i-1 = 0, i-3 = 0, i-4 = 0) fell out only 252 times, which is denoted as the number of occurrences of this combination at time t = 0 of the form N [0] / 000 = 252, while when this combination is dropped 180 times, the next bit of this next PI took zero value (N0 [0] / 000 = 180), and 72 times the next bit of this next PI took a single value (N1 [0] / 000 = 72). In accordance with the theory of probability according to the formula of the form p0 [0] / 000 = N0 [0] / 000 / N [0] / 000 = 180/252 = 0.714 bits of the form (i-1 = 0, i-3 = 0, i-4 = 0) is 0.714. Accordingly, the conditional probability of the appearance of the next bit of this next IP, equal to one, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 0) is equal to 0.286.

Комбинация (i-1=0, i-3=0, i-4=1) выпала всего 161 раз (N[0]/001=161), при этом при выпадении этой комбинации 90 раз очередной бит данной очередной ИП принимал нулевое значение (N0[0]/001=90), и 71 раз очередной бит данной очередной ИП принимал единичное значение (N1[0]/001=71). Условная вероятность появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (0, 0, 1) равна 0,559, и т.д., как показано на фиг. 5.The combination (i-1 = 0, i-3 = 0, i-4 = 1) fell out only 161 times (N [0] / 001 = 161), while when this combination fell 90 times, the next bit of this next PI took zero value (N0 [0] / 001 = 90), and 71 times the next bit of this next IP took a single value (N1 [0] / 001 = 71). The conditional probability of the appearance of the next bit of this next IP, equal to zero, from the combination of the previous bits of the form (0, 0, 1) is equal to 0.559, etc., as shown in Fig. 5.

Значения условной вероятности появления очередного бита данной очередной ИП от различных комбинаций предшествующих битов существенно различаются. Для большинства выбранных комбинаций условная вероятность появления очередного нулевого бита больше условной вероятности появления очередного единичного бита, но для некоторых комбинаций, например, комбинации предшествующих битов вида (i-1=1, i-3=1, i-4=0), это соотношение является противоположным.The values of the conditional probability of the appearance of the next bit of this next IP from various combinations of the previous bits differ significantly. For most of the selected combinations, the conditional probability of the appearance of the next zero bit is greater than the conditional probability of the appearance of the next one bit, but for some combinations, for example, a combination of the previous bits of the form (i-1 = 1, i-3 = 1, i-4 = 0), this is the relationship is the opposite.

Данный пример иллюстрирует факт, что корреляционные связи информационных последовательностей различных источников имеют сложный характер и меняются во времени, что не учитывается в известных способах арифметического кодирования.This example illustrates the fact that the correlations of information sequences from different sources are complex and change over time, which is not taken into account in the known methods of arithmetic coding.

Далее устанавливают текущие значения условной вероятности кодирования нулевого символа и единичного символа соответствующими выбранным значениям вероятности появления очередного бита очередной ИП с соответствующими номерами позиций предшествования. В начальный момент времени t=0 перед кодированием первого по счету очередного бита очередной ИП текущие значения условной вероятности кодирования нулевого символа и единичного символа устанавливают равными т выбранным наибольшим значениям условной вероятности появления очередного бита очередной ИП. Как показано, например, на фиг. 4, условная вероятности появления очередного бита очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) установлена равной р0/000=0,714, условная вероятности появления очередного бита очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=1) - равной р0/001=0,559, и т.д.Next, the current values of the conditional probability of encoding the zero symbol and the single symbol are set corresponding to the selected values of the probability of the appearance of the next bit of the next IP with the corresponding precedence position numbers. At the initial moment of time t = 0, before the coding of the first consecutive bit of the next IP, the current values of the conditional probability of encoding the zero symbol and the single symbol are set equal to the selected highest values of the conditional probability of the appearance of the next bit of the next IP. As shown, for example, in FIG. 4, the conditional probability of the appearance of the next bit of the next IP, equal to zero, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 0) is set equal to p0 / 000 = 0.714, the conditional probability of the appearance of the next bit of the next IP, equal to zero, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 1) - equal to p0 / 001 = 0.559, etc.

Разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условной вероятности кодирования нулевого символа и единичного символа заключается в следующем.The division of the current arithmetic coding interval into the current coding sub-interval of the null symbol and into the current coding sub-interval of a single symbol, depending on the current values of the conditional probability of encoding the null symbol and a single symbol, is as follows.

Для каждой из m комбинаций предшествующих битов вида

с выбранными наибольшими значениями условной вероятности появления очередного бита очередной ИП длину текущего интервала арифметического кодирования I[i-1], равную I[i-1]=H[i-1]-L[i-1], разделяют на текущее значение подинтервала нулевого символа D0[i-1] и текущее значение подинтервала единичного символа D1[i-1]_,длины которых прямо пропорциональны текущим значениям условной вероятности кодируемых нулевых символов

и единичных символов

соответственно.For each of m combinations of preceding bits of the form

with the selected maximum values of the conditional probability of the appearance of the next bit of the next IP, the length of the current arithmetic coding interval I [i-1], equal to I [i-1] = H [i-1] -L [i-1], is divided by the current value of the subinterval the zero symbol D0 [i-1] and the current value of the subinterval of the single symbol D1 [i-1] _{, the} lengths of which are directly proportional to the current values of the conditional probability of the encoded zero symbols

and single characters

respectively.

Длину текущего подинтервала нулевых символов

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

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

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

Length of the current null character subinterval

determined by a formula of the form

and the length of the current subinterval of single characters

determined by a formula of the form

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

вычисляют по формуле вида

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

вычисляют по формуле вида

где

- число подсчитанных появлений комбинации

до кодирования i-го очередного бита очередной ИП,

- число подсчитанных появлений этой комбинации, при которых очередной бит очередной ИП принял нулевое значение, а

- число подсчитанных появлений этой комбинации, при которых очередной бит очередной ИП принял единичное значение.The current value of the conditional probability of encoded null symbols

calculated by a formula of the form

and the current value of the conditional probability of the encoded single symbols

calculated by a formula of the form

where

- the number of counted occurrences of the combination

before coding the i-th next bit of the next IP,

is the number of counted occurrences of this combination, at which the next bit of the next IP took a zero value, and

- the number of counted occurrences of this combination, at which the next bit of the next IP took a single value.

Например, в начальный момент времени t=0 длина текущего подинтервала нулевого символа D0[0]/000 относительно комбинации вида (0, 0, 0) равна D0[0]/000=256*180/252=256*0,714=183, десятичному значению 183 соответствует двоичное значение 1011 0111, а длина текущего подинтервала единичного символа D1[0]/000 равна 256-183=73. Подинтервал единичного символа расположен сверху подинтервала нулевого символа, как показано, например, на фиг. 4. Верхнюю границу подинтервала нулевого символа обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования включительно до значения Q исключительно, а подинтервал единичного символа простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, начальное значение Q имеет десятичное значение 183 относительно комбинации вида (0,0,0), как показано на фиг. 4 в первой строке при t=0. Для того, чтобы было ясно, относительно какой комбинации предшествующих битов определено значение Q, соответствующее значение условной вероятности кодируемых нулевых символов в строке на фиг. 4 выделено жирным шрифтом.For example, at the initial moment of time t = 0, the length of the current subinterval of the zero character D0 [0] / 000 relative to a combination of the form (0, 0, 0) is equal to D0 [0] / 000 = 256 * 180/252 = 256 * 0.714 = 183, the decimal value 183 corresponds to the binary value 1011 0111, and the length of the current subinterval of the single character D1 [0] / 000 is 256-183 = 73. The sub-slot of a single character is located on top of the sub-slot of the null character, as shown, for example, in FIG. 4. The upper limit of the zero symbol subinterval is denoted as the Q value, and this subinterval starts from the lower limit of the arithmetic coding interval inclusively to the Q value exclusively, and the single symbol subinterval extends from the Q value inclusively to the upper limit of the arithmetic coding coding interval exclusively. For example, the initial Q value has a decimal value of 183 with respect to a combination of the form (0,0,0), as shown in FIG. 4 in the first line at t = 0. In order to make it clear with respect to which combination of preceding bits the value of Q is determined, corresponding to the value of the conditional probability of encoded null symbols in the string in FIG. 4 in bold.

Точно так же разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условных вероятностей кодирования нулевого символа и единичного символа относительно всех других комбинаций предшествующих битов, как показано на фиг. 4.Likewise, the current arithmetic coding interval is divided into the current null symbol coding sub-interval and the current single-symbol coding sub-interval depending on the current values of the conditional probabilities of the null symbol and the single symbol coding with respect to all other combinations of the previous bits, as shown in FIG. 4.

Далее выполняют арифметическое кодирование очередного бита очередной информационной последовательности, в зависимости от предшествующих битов с текущими значениями условной вероятности. Для этого считывают очередной бит очередной ИП и относительно него определяют предшествующие биты. Например, для первого по счету (i=1) очередного бита данной очередной ИП, имеющего нулевое значение, с учетом начальной двоичной последовательности, показанной на фиг. 3(в), определяют предшествующие биты в позициях (i-1, i-3, i-4). В данном случае предшествующие биты составляют комбинацию (0, 0, 0), относительно которой в первой строке фиг. 4 указано разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. Для того, чтобы указать относительно какой комбинации предшествующих битов выполняют арифметическое кодирование очередного бита, на фиг. 4 ее текущее значение условной вероятности выделяют жирным шрифтом. С момента установления зависимости очередного бита очередной ИП от конкретной комбинации предшествующих битов с текущими значениями условной вероятности, выполнение собственно действий арифметического кодирования очередного бита не отличается от действий арифметического кодирования очередного бита без учета условной вероятности, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Действия арифметического кодирования очередных битов заключаются в последовательном сжатии очередных битов очередной ИП в очередную кодированную последовательность (КП) в соответствии с текущими значениями подинтервалов кодирования.Next, arithmetic coding of the next bit of the next information sequence is performed, depending on the previous bits with the current values of the conditional probability. For this, the next bit of the next IP is read and the previous bits are determined relative to it. For example, for the first (i = 1) sequential bit of this sequential IP having a zero value, taking into account the initial binary sequence shown in FIG. 3 (c) define the preceding bits at positions (i-1, i-3, i-4). In this case, the preceding bits constitute the pattern (0, 0, 0), with respect to which, in the first row of FIG. 4 indicates the division of the current arithmetic coding interval into the current coding sub-interval of the null symbol and into the current coding sub-interval of a single symbol. In order to indicate with respect to which combination of the preceding bits the arithmetic coding of the next bit is performed, FIG. 4, its current value of the conditional probability is highlighted in bold. From the moment the dependence of the next bit of the next IP on a specific combination of previous bits with the current values of the conditional probability is established, the actual actions of the arithmetic coding of the next bit does not differ from the actions of the arithmetic coding of the next bit without taking into account the conditional probability, described, for example, in the book by D. Vatolin, A Ratushnyak, M. Smirnov, V. Yukin "Methods of data compression. The device of archivers, compression of images and video". - M., DIALOG-MEPhI, 2002, pp. 35-43. Actions of arithmetic coding of the next bits consist in sequential compression of the next bits of the next IP into the next coded sequence (CS) in accordance with the current values of the coding sub-intervals.

При поступлении на вход арифметического кодирования очередного бита очередной ИП, являющегося единичным двоичным символом, текущий интервал кодирования этого бита устанавливают равным предыдущему подинтервалу кодирования единичного символа, а при поступлении на вход арифметического кодирования нулевого двоичного символа, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу нулевого символа. Например, при поступлении на вход арифметического кодирования первого бита очередной ИП, являющегося нулевым двоичным символом, нижнее значение интервала кодирования первого символа L[1] устанавливают равным значению L[0], равному, в данном примере, 0, а верхнее значение интервала кодирования первого символа арифметического кодирования устанавливают равным начальному значению Q [0], равному, например, 183, как показано на фиг. 4 при t=1.When the next bit of the next IP arrives at the input of the arithmetic coding, which is a single binary symbol, the current coding interval of this bit is set equal to the previous coding subinterval of a single symbol, and when a zero binary symbol arrives at the arithmetic coding input, the current coding interval of this symbol is set equal to the previous symbol. For example, when the first bit of the next IP arrives at the input of the arithmetic coding, which is a zero binary symbol, the lower value of the coding interval of the first symbol L [1] is set equal to the value L [0], equal, in this example, to 0, and the upper value of the coding interval of the first the arithmetic coding symbol is set to an initial value Q [0] of, for example, 183, as shown in FIG. 4 at t = 1.

Далее самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения, например, вида 0000 0000 и 1011 0111, соответственно, как показано на фиг. 4 при t=1. При их несовпадении переходят к арифметическому кодированию следующего символа.Next, the leftmost bit of the binary representation of the L [1] value is compared with the leftmost bit of the binary representation of the value, for example, 0000 0000 and 1011 0111, respectively, as shown in FIG. 4 at t = 1. If they do not match, proceed to the arithmetic coding of the next character.

После выполнения арифметического кодирования каждого очередного символа очередной ИП повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа. Для этого уточняют число появлений комбинаций предшествующих битов. Например, после кодирования первого бита очередной ИП число появлений комбинации (i-1=0, i-3=0, i-4=0) увеличилось на единицу и составило N[1]/000=253, при этом при выпадении этой комбинации 181 раз очередной бит данной очередной ИП принимал нулевое значение (N0[1]/000=181), а число появлений этой комбинации, когда очередной бит очередной ИП принимал единичное значение осталось неизменным (N1[1]/000=72). Поэтому в момент времени t=1 текущая условная вероятности появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила р0[1]/000=N0[l]/000/N[1]/000=181/253=0,715, как показано во второй строке сверху на фиг. 4 при t=1. Соответственно, текущая условная вероятности появления очередного бита данной очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила 0,285.After performing arithmetic coding of each next symbol of the next IP, the current values of the conditional probability of encoding the zero symbol and the single symbol are recalculated. For this, the number of occurrences of the preceding bit combinations is specified. For example, after coding the first bit of the next IP, the number of occurrences of the combination (i-1 = 0, i-3 = 0, i-4 = 0) increased by one and amounted to N [1] / 000 = 253, while when this combination occurs 181 times, the next bit of this next MT took a zero value (N0 [1] / 000 = 181), and the number of occurrences of this combination when the next bit of the next MT took one value remained unchanged (N1 [1] / 000 = 72). Therefore, at time t = 1, the current conditional probability of the appearance of the next bit of this next IP, equal to zero, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 0) was p0 [1] / 000 = N0 [l] / 000 / N [1] / 000 = 181/253 = 0.715, as shown in the second row from the top in FIG. 4 at t = 1. Accordingly, the current conditional probability of the appearance of the next bit of this next IP, equal to one, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 0) was 0.285.

Для остальных комбинаций предшествующих битов число их появлений не изменилось, поэтому не изменилась их текущая условная вероятности появления очередного бита очередной ИП, равного нулевому значению, и соответственно, единичному значению.For the remaining combinations of the previous bits, the number of their occurrences has not changed, therefore, their current conditional probability of the appearance of the next bit of the next IP, equal to zero value, and, accordingly, to one value, has not changed.

Для кодирования очередного (второго по счету) бита очередной ИП в соответствии с уточненными текущими значениями условной вероятности кодирования нулевого символа и единичного символа повторно разделяют текущий интервал арифметического кодирования, простирающийся от 0 до 183, на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа для каждой комбинации предшествующих битов.To encode the next (second in a row) bit of the next IP in accordance with the updated current values of the conditional probability of encoding a zero symbol and a single character for each combination of the preceding bits.

При поступлении на вход арифметического кодирования второго по счету очередного бита (i=2) очередной ИП, являющегося нулевым двоичным символом, снова определяют предшествующие ему биты в позициях (i-1, i-3, i-4). В данном случае предшествующие биты составляют комбинацию (0, 1, 0), относительно которой согласно фиг. 5 условная вероятность очередного нулевого символа очередной ИП равна 0,576 и относительно которой на фиг. 4 во второй строке указано разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, десятичное значение Q [1] составило 106.When the next bit (i = 2) of the next IP arrives at the input of arithmetic coding, which is a zero binary symbol, the preceding bits in positions (i-1, i-3, i-4) are again determined. In this case, the preceding bits constitute the pattern (0, 1, 0), relative to which, according to FIG. 5 the conditional probability of the next zero symbol of the next IP is equal to 0.576 and relative to which in FIG. 4, the second line indicates the division of the current arithmetic coding interval into the current coding sub-interval of the null symbol and into the current coding sub-interval of a single symbol, the decimal value Q [1] was 106.

При кодировании второго бита очередной ИП, являющегося нулевым двоичным символом, нижнее значение интервала кодирования L[2] устанавливают равным значению L[1], равному, например, 0, а верхнее значение интервала кодирования H[2] устанавливают равным текущему значению Q [1], равному десятичному числу 106, или двоичному числу 0110 1010, как показано на фиг. 4 при t=2.When encoding the second bit of the next IP, which is a zero binary symbol, the lower value of the coding interval L [2] is set equal to the value of L [1], for example, 0, and the upper value of the coding interval H [2] is set equal to the current value of Q [1 ] equal to decimal 106, or binary 0110 1010, as shown in FIG. 4 at t = 2.

Самый левый бит двоичного представления значения L[2] сравнивают с самым левым битом двоичного представления значения Н[2], например, вида 0000 0000 и 0110 1010, соответственно, как показано на фиг. 4 при t=2. При их совпадении значение самого левого бита двоичных представлений значений L[2] и Н[2] считывают в качестве очередного бита кодированной последовательности (Зак. бит на фиг. 4). Например, при арифметическом кодировании второго по счету бита очередной ИП первым из очередных битов очередной КП является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 4, третья строка сверху. Считанный бит удаляют из двоичных представлений значений L[2] и Н[2], которые уменьшаются до длины 7 бит вида 0000 0000 и 1101 1010, соответственно. Двоичные символы двоичных представлений значений L[2] и сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Например, двоичные представления значений L[2] и Н[2] приобретают вид 0000 0000 и 1101 0100, соответственно. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[2] и Н[2] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.The left-most bit of the binary representation of the L [2] value is compared to the left-most bit of the binary representation of the H [2] value, for example, 0000 0000 and 0110 1010, respectively, as shown in FIG. 4 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 coded sequence (Zak. Bit in Fig. 4). For example, when arithmetic coding of the second bit of the next IP, the first of the next bits of the next CP is the zero binary symbol that matched during the comparison, as shown in FIG. 4, third 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 0000 0000 and 1101 1010, respectively. Binary symbols of binary representations of values L [2] and are shifted from right to left by one bit and from the right to them in the least significant bit are added along a zero binary symbol. For example, the binary representations of the values L [2] and H [2] take the form 00000000 and 1101 0100, respectively. Methods for reading binary characters with the removal of the read characters are known and are described, for example, in the book: V. Shiloh "Popular digital microcircuits". - M., Radio and Communication, 1987, 104-123, using shift registers with parallel and sequential writing / reading of binary sequences. The operations of shifting from right to left by one bit and adding a zero 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 for shifting one bit towards the higher bits of binary sequences and writing a zero binary character into the vacant least significant bit are known and described, for example, in the book: V. Shilo "Popular digital microcircuits". - M., Radio and Communication, 1987, 104-123, using shift registers with parallel and sequential writing / reading of binary sequences, and in essence are multiplication by two decimal values of the lower and upper values of the coding interval.

После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений снова считывают в качестве следующего бита кодированной последовательности, иначе повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа.After each normalization is performed, the leftmost bit of the binary representation of the lower coding interval value is compared with the leftmost bit of the binary representation of the upper coding interval value. If they match, the value of the leftmost bit of these binary representations is again read as the next bit of the coded sequence, otherwise the current values of the conditional probability of encoding the zero symbol and the single symbol are recalculated.

Для этого заново уточняют число появлений комбинаций предшествующих битов. Например, после кодирования второго бита очередной ИП число появлений комбинации (i-1=0, i-3=1, i-4=0) увеличилось на единицу и составило N[1]/010=138, при этом при выпадении этой комбинации 80 раз очередной бит данной очередной ИП принимал нулевое значение (N0]/010=80), а число появлений этой комбинации, когда очередной бит очередной ИП принимал единичное значение, осталось неизменным (N1[1]/010=58). Поэтому пересчитывают значение р0[1]/010=N0[l]/010/N[1]/010=80/138=0,579, как показано в третьей строке сверху на фиг. 4. Соответственно, текущая условная вероятность появления очередного бита очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=1, i-4=0) составила 0,421.For this, the number of occurrences of the preceding bit combinations is re-specified. For example, after coding the second bit of the next IP, the number of occurrences of the combination (i-1 = 0, i-3 = 1, i-4 = 0) increased by one and amounted to N [1] / 010 = 138, while when this combination occurs 80 times the next bit of this next IP took zero value (N0] / 010 = 80), and the number of occurrences of this combination, when the next bit of the next IP took one value, remained unchanged (N1 [1] / 010 = 58). Therefore, the value p0 [1] / 010 = N0 [l] / 010 / N [1] / 010 = 80/138 = 0.579 is recalculated, as shown in the third row from the top in FIG. 4. Accordingly, the current conditional probability of the appearance of the next bit of the next IP, equal to one, from the combination of the previous bits of the form (i-1 = 0, i-3 = 1, i-4 = 0) was 0.421.

Далее арифметически кодируют очередной двоичный символ ИП и выполняют на передающей стороне перечисленные действия до исчерпания двоичных символов данной информационной последовательности.Next, the next binary symbol of the IP is arithmetically encoded and the listed actions are performed on the transmitting side until the binary symbols of this information sequence are exhausted.

Примерный вид арифметического кодирования первых 18 очередных битов очередной ИП вида "0010 0110 0010 0010 01" в первые 14 бит очередной кодированной последовательности вида "0100 1010 0111 10" показан на фиг. 3(г). Например, при кодировании первого, третьего, четвертого и пятого битов очередной ИП не было сформировано в явном виде кодированных битов, при кодировании второго бита - сформирован кодированный бит "1", при кодировании шестого бита - сформированы кодированные биты "100" и т.д.An exemplary view of the arithmetic coding of the first 18 consecutive bits of the next IP of the form "0010 0110 0010 0010 01" into the first 14 bits of the next coded sequence of the form "0100 1010 0111 10" is shown in FIG. 3 (d). For example, when encoding the first, third, fourth and fifth bits of the next IP, coded bits were not generated explicitly, when encoding the second bit, coded bit "1" was generated, when coding the sixth bit, coded bits "100" were generated, etc. ...

Способы передачи на приемную сторону т выбранных значений условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования и очередной кодированной последовательности известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Выбранные значения условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования показаны на фиг. 5. Например, переданные на приемную сторону m=8 выбранные значения условной вероятности представлены на фиг. 7 при t=0 (первая строка).Methods for transmitting to the receiving side m the selected values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding position numbers of the precedence and the next coded sequence are known and described, for example, in the book by A.G. Zyuko, D.D. Klovsky, M.V. Nazarov, L.M. Fink "Theory of signal transmission". - M .: Radio and communication, 1986, p. 11. The selected values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding precedence position numbers are shown in FIG. 5. For example, the selected conditional probability values transmitted to the receiving side m = 8 are shown in FIG. 7 at t = 0 (first line).

На приемной стороне принятую последовательность (ПП) запоминают. Примерный вид первых 14 бит "0100 1010 0111 10" ПП показан на фиг. 3(д).On the receiving side, the received sequence (PS) is stored. An exemplary view of the first 14 bits of the "0100 1010 0111 10" PP is shown in FIG. 3 (e).

Предварительно на приемной стороне устанавливают начальный интервал арифметического декодирования. Например, при представлении значений интервала декодирования восемью двоичными символами, начальное нижнее значение интервала декодирования LL в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, а начальное верхнее значение интервала декодирования НН устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического декодирования представлен на фиг. 7 при t=0.The initial arithmetic decoding interval is preliminarily set on the receiving side. For example, when the decoding interval values are represented by eight binary symbols, the initial lower value of the decoding interval LL at time t = 0 is set to the minimum value equal to zero value in decimal notation or 00000000 in binary representation, and the initial upper value of the decoding interval HH is set to a maximum value of 255 decimal or 1111 1111 binary. An example of an arithmetic decoding start interval is shown in FIG. 7 at t = 0.

Алгоритм арифметического декодирования на приемной стороне представлен на фиг. 6.The arithmetic decoding algorithm on the receiving side is shown in FIG. 6.

На приемной стороне устанавливают текущие значения условной вероятности декодирования нулевого символа и единичного символа соответствующими принятым значениям условной вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования идентично соответствующим действиям на передающей стороне. Для каждой из m комбинаций предшествующих битов восстановленной информационной последовательности (ВИП) с дописанной в ее начало начальной двоичной последовательности с выбранными наибольшими значениями условной вероятности появления очередного бита очередной ВИП длину текущего интервала декодирования II[i-1], равную II[i-1]=HH[i-1]-LL[i-1]_, разделяют на текущее значение подинтервала декодирования нулевого символа DD0[i-1] и текущее значение подинтервала декодирования единичного символа DD1[i-1], длины которых прямо пропорциональны текущим значениям условной вероятности декодируемых нулевых символов

и единичных символов

соответственно.On the receiving side, the current values of the conditional probability of decoding the zero symbol and the single symbol are set corresponding to the received values of the conditional probability of the appearance of the next bit of the next information sequence with the corresponding precedence position numbers, identical to the corresponding actions on the transmitting side. For each of the m combinations of previous bits of the recovered information sequence (VIP) with the initial binary sequence added to its beginning with the selected highest values of the conditional probability of the next bit of the next VIP, the length of the current decoding interval II [i-1], equal to II [i-1] = HH [i-1] -LL [i-1] _, divided into the current value of the decoding subinterval of the null symbol DD0 [i-1] and the current value of the decoding subinterval of the single symbol DD1 [i-1], the lengths of which are directly proportional to the current values of the conditional probabilities of decoded null symbols

and single characters

respectively.

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

, а длину текущего подинтервала единичных символов

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

Length of the current null character subinterval

determined by a formula of the form

, and the length of the current subinterval of single characters

determined by a formula of the form

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

вычисляют по формуле вида

где

- число подсчитанных появлений комбинации

до декодирования i-го очередного бита очередной ВИП,

- число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял нулевое значение, а

- число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял единичное значение.At each next moment of decoding, the current value of the conditional probability of decoded zero symbols

calculated by a formula of the form

where

- the number of counted occurrences of the combination

before decoding the i-th next bit of the next VIP,

- the number of counted occurrences of this combination at which the next bit of the next VIP took zero value, and

- the number of counted occurrences of this combination, at which the next bit of the next VIP took a single value.

Например, в начальный момент времени t=0 длина текущего подинтервала декодирования нулевого символа DD0[0]/000 относительно комбинации вида (0, 0, 0) равна DD0[0]/000=256*180/252=256*0,714=183, а длина текущего подинтервала декодирования единичного символа DD1[0]/000 равна 256-183=73. Верхнюю границу подинтервала декодирования нулевого символа обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования включительно до значения QQ исключительно, а подинтервал декодирования единичного символа простирается от значения QQ включительно до верхней границы интервала декодирования исключительно. Например, начальное значение QQ имеет десятичное значение 183 относительно комбинации вида (0,0,0), как показано на фиг. 7 в первой строке при t=0.For example, at the initial moment of time t = 0, the length of the current decoding subinterval of the zero symbol DD0 [0] / 000 relative to the combination of the form (0, 0, 0) is DD0 [0] / 000 = 256 * 180/252 = 256 * 0.714 = 183 , and the length of the current decoding subinterval of a single symbol DD1 [0] / 000 is 256-183 = 73. The upper boundary of the null symbol decoding sub-interval is denoted as a QQ value, and this sub-slot starts from the lower edge of the decoding interval inclusively to the QQ value exclusively, and the decoding sub-interval of a single symbol extends from the QQ value inclusively to the upper boundary of the decoding interval exclusively. For example, the initial QQ value has a decimal value of 183 with respect to a combination of the form (0,0,0), as shown in FIG. 7 in the first line at t = 0.

Например, в начальный момент времени декодирования в восстановленной информационной последовательности (в этот момент еще пустой) с дописанной в ее начало начальной двоичной последовательности, как показано на фиг. 3(e), для выбранных m комбинаций предшествующих битов, находящихся на позициях (i-1, i-3, i-4) относительно i-го декодируемого бита (в начальный момент i=0), имеет место комбинация предшествующих битов вида (0, 0, 0). Чтобы было ясно, относительно какой комбинации предшествующих битов определено значение QQ, соответствующее значение условной вероятности декодируемых нулевых символов на фиг. 7 выделено жирным шрифтом. Соответственно, для данной комбинации начальное значение текущего подинтервала декодирования нулевого символа начинается от 0 и заканчивается 183, начальное значение текущего подинтервала декодирования единичного символа начинается от 183 и заканчивается 255, как показано, на фиг. 7 в первой строке.For example, at the initial moment of decoding in the recovered information sequence (at this moment it is still empty) with the initial binary sequence appended to its beginning, as shown in FIG. ( 0, 0, 0). To make it clear with respect to which combination of preceding bits the QQ value is determined, the corresponding value of the conditional probability of decoded null symbols in FIG. 7 in bold. Accordingly, for a given combination, the start value of the current null symbol decoding sub-slot starts at 0 and ends at 183, the start value of the current single symbol decoding sub-slot starts at 183 and ends at 255, as shown in FIG. 7 on the first line.

Разделение текущего интервала декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в зависимости от текущих значений условных вероятностей декодирования нулевого символа и единичного символа относительно всех выбранных комбинаций предшествующих битов, выполняют идентично аналогичному действию на передающей стороне.Dividing the current decoding interval into the current decoding subinterval of the zero symbol and into the current decoding subinterval of a single symbol, depending on the current values of the conditional probabilities of decoding the zero symbol and the single symbol with respect to all selected combinations of the previous bits, is performed identically to a similar action on the transmitting side.

Способы арифметического декодирования очередных бит очередной ПП в очередной бит очередной восстановленной информационной последовательности (ВИП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". -М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании очередной ПП в соответствии с текущими значениями подинтервала декодирования нулевого символа и подинтервала декодирования единичного символа.Methods of arithmetic decoding of the next bits of the next SP into the next bit of the next recovered information sequence (VIP) are known and described, for example, in the book D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Methods of data compression. The device of archivers, image compression and video ". -M., DIALOG-MEPhI, 2002, pp. 35-43. They consist in sequential decoding of the next PN in accordance with the current values of the decoding subinterval of the zero symbol and the decoding subinterval of the single symbol.

Примерный вид арифметического декодирования очередных бит очередной принятой последовательности вида "0100 1010 0111 10" в очередные биты очередной ВИП показан на фиг. 7. Для начала декодирования из очередной ПП считывают такое количество первых бит очередной ПП, которое выбрано для представления значений интервала декодирования. Например, из очередной ПП считывают восемь двоичных символов вида "0100 1010", как показано на фиг. 7 в первой строке в графе "Счит". Очередные считанные биты составляют двоичную текущую последовательность (Тек. посл.) длиной восемь бит, десятичное значение которой равно 74, как показано на фиг. 7 в первой строке в графе "Тек. посл".An exemplary view of arithmetic decoding of the next bits of the next received sequence of the form "0100 1010 0111 10" into the next bits of the next VIP is shown in Fig. 7. To start decoding, from the next PN, the number of the first bits of the next PN is read, which is selected to represent the values of the decoding interval. For example, eight binary symbols of the form "0100 1010" are read from the next PN, as shown in FIG. 7 on the first line in the "Count" column. The next read bits constitute an eight bit long binary current sequence (Current seq.), The decimal value of which is 74, as shown in FIG. 7 on the first line in the "Current last" column.

Для декодирования первого бита очередной ПП десятичное значение текущей последовательности сравнивают с границами текущего подинтервала декодирования нулевого символа и границами текущего подинтервала декодирования единичного символа, находящимися, например, в пределах от 0 до 183, и от 183 до 255, соответственно, как показано на фиг. 7 в первой строке при t=0. Если десятичное значение текущей последовательности оказалось в пределах текущего подинтервала декодирования нулевого символа, то очередной декодируемый бит имеет нулевое значение, а если в пределах текущего подинтервала декодирования единичного символа, то - единичное значение. Например, первый декодируемый бит очередной ВИП принял нулевое значение, решение о значении декодируемого бита указывается в графе "Дек. бит" фиг. 7.To decode the first bit of the next PN, the decimal value of the current sequence is compared with the boundaries of the current sub-interval for decoding the null symbol and the boundaries of the current sub-interval for decoding a single symbol, which are, for example, in the range from 0 to 183 and from 183 to 255, respectively, as shown in FIG. 7 in the first line at t = 0. If the decimal value of the current sequence is within the current decoding subinterval of the zero symbol, then the next decoded bit has a zero value, and if within the current decoding subinterval of a single symbol, then it has a one value. For example, the first decoded bit of the next TTI has taken a zero value, the decision on the value of the decoded bit is indicated in the "Dec. Bit" column of FIG. 7.

Следующие границы текущего интервала декодирования устанавливают соответствующими границам выбранного подинтервала декодирования. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования LL равным значению LL0[0], например, LL0[1]=0, а верхнее значение интервала декодирования НН - равным значению QQ[0], например, НН[1]=183, как показано на фиг. 7 во второй строке при t=1.The next boundaries of the current decoding interval are set corresponding to the boundaries of the selected decoding sub-interval. As a result of decoding the first symbol, the lower value of the LL decoding interval is set equal to LL0 [0], for example, LL0 [1] = 0, and the upper value of the HH decoding interval is set equal to QQ [0], for example, HH [1] = 183, as shown in FIG. 7 in the second line for t = 1.

Точно также как выполняется нормализация на передающей стороне, после каждого изменения состояния арифметического декодирования самый левый бит двоичного представления значения LL интервала декодирования сравнивают с самым левым битом двоичного представления значения НН, например, при f=1 значение LL вида "0000 0000" и значение НН вида "1011 0111", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и НН удаляют и символы двоичных представлений значений LL и НН сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. При каждой нормализации в процессе декодирования из очередной ПП считывают очередной бит, из двоичной текущей последовательности удаляют самый левый бит ее двоичного представления, двоичное представление сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают считанный из ПП очередной бит. Например, при выполнении нормализации после декодирования второго бита в текущую последовательность считан нулевой бит и текущая последовательность приняла десятичное значение 148, как показано на фиг. 7.Just as normalization is performed on the transmitting side, after each change of the arithmetic decoding state, the leftmost bit of the binary representation of the LL value of the decoding interval is compared with the leftmost bit of the binary representation of the HH value, for example, for f = 1, the LL value of the form "0000 0000" and the HH value of the form "1011 0111", respectively. If they match, normalization of arithmetic decoding is performed: the value of the leftmost bit of the binary representations of LL and HH values is removed and the symbols of the binary representations of LL and HH values are shifted from right to left by one bit and from the right to them in the least significant bit are added along the zero binary symbol. At each normalization in the decoding process, the next bit is read from the next PN, the leftmost bit of its binary representation is removed from the current binary sequence, the binary representation is shifted from right to left by one bit, and the next bit read from the PN is added to them from the right to the least significant bit. For example, when performing normalization after decoding the second bit, a zero bit is read into the current sequence and the current sequence takes the decimal value 148, as shown in FIG. 7.

После декодирования очередного бита очередной ВИП уточняют текущую условную вероятность появления очередного бита данной очередной ВИП, равного нулевому значению, от выпавшей комбинации предшествующих битов. Идентично соответствующей операции на передающей стороне, в момент времени t=1 текущая условная вероятность появления очередного бита данной очередной ВИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила рр0[1]/000=NN0[1]/000/NN[1]/000=181/253=0,715, где NN[i]/000 - число подсчитанных появлений комбинации (0,0,0) до декодирования i-го очередного бита очередной ВИП, a NN0[i]/000 - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял нулевое значение.After decoding the next bit of the next VIP, the current conditional probability of the appearance of the next bit of this next VIP, equal to zero, from the dropped combination of the previous bits, is specified. Identical to the corresponding operation on the transmitting side, at time t = 1, the current conditional probability of the appearance of the next bit of this next VIP, equal to zero, from the combination of the previous bits of the form (i-1 = 0, i-3 = 0, i-4 = 0 ) was pp0 [1] / 000 = NN0 [1] / 000 / NN [1] / 000 = 181/253 = 0.715, where NN [i] / 000 is the number of counted occurrences of the combination (0.0.0) before decoding of the i-th next bit of the next VIP, and NN0 [i] / 000 is the number of counted occurrences of this combination, at which the next bit of the next VIP took zero value.

Описанные действия выполняют до исчерпания очередных бит очередной ПП. Например, из первых бит очередной ПП вида "0100 1010 0111 10" декодированы первые восемь бит очередной ВИП вида "0010 0110", как показано на фиг. 3(e).The described actions are performed until the next bits of the next PP are exhausted. For example, from the first bits of the next TTI of the form "0100 1010 0111 10", the first eight bits of the next TTI of the form "0010 0110" are decoded, as shown in FIG. 3 (e).

Очередную ВИП передают получателю, и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные принятые последовательности.The next VIP is transmitted to the recipient, and the listed actions are performed on the receiving side until the next received sequences arrive.

Проверка теоретических предпосылок заявленного способа арифметического кодирования и декодирования проверялась путем его аналитических исследований.Verification of the theoretical premises of the claimed method of arithmetic coding and decoding was verified by analytical research.

Было выполнено арифметическое кодирование и декодирование различных избыточных последовательностей с различными коррелирующими зависимостями с использованием способа-прототипа и предлагаемого способа. Выявлено, что чем выше условная зависимость текущих битов информационной последовательности от предыдущих ее битов, тем больший коэффициент их сжатия достигается при использовании предлагаемого способа по сравнению со способом-прототипом.Was performed arithmetic coding and decoding of various redundant sequences with different correlating dependencies using the prototype method and the proposed method. It was revealed that the higher the conditional dependence of the current bits of the information sequence on its previous bits, the greater their compression ratio is achieved when using the proposed method in comparison with the prototype method.

Проведенные исследования подтверждают, что при использовании предлагаемого способа арифметического кодирования и декодирования избыточной двоичной информационной последовательности обеспечивается уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.The studies carried out confirm that when using the proposed method of arithmetic coding and decoding of a redundant binary information sequence, a decrease in the transmission rate through the transmission channel of the coded sequence or a decrease in the capacity of its storage devices is provided.

Claims

The method of arithmetic coding and decoding, which preliminarily sets the initial arithmetic coding interval on the transmitting side and the corresponding initial arithmetic decoding interval on the receiving side, on the transmitting side from the source of the information sequence, the next information sequence with a length of k> 2 bits is arithmetic coding interval for the current coding subinterval of the zero symbol and for the current coding subinterval of a single character, perform arithmetic coding of the next bit of the next information sequence and perform the listed actions on the transmitting side until the next bits of the next information sequence are exhausted, transmit the next coded sequence to the receiving side, perform on the transmitting side of the listed actions as long as the next information sequences arrive, on to the receiving side, the next received sequence is received, which is stored, the current arithmetic decoding interval is divided into the current decoding subinterval of the zero symbol and into the current single symbol decoding subinterval, arithmetic decoding of the next bits of the next received sequence in the next bit of the next sequence is performed, the current values of the conditional decoding probability are recalculated a zero symbol and a single symbol and perform the listed actions on the transmitting side until the next bits of the next received sequence are exhausted, transmit the next restored information sequence to the receiver, perform the listed actions on the receiving side until the next received sequences arrive, characterized in that it is preliminary for the transmitting the sides and the receiving side choose an initial binary sequence of length n> 1 bit, on the transmitting side after of obtaining the next information sequence, the values of the conditional probability of the appearance of its next bit are calculated, including the pre-selected initial binary sequence, from the previous bits preceding the next one by d, where d = 1, 2, ..., k-1, positions, 2≤m << k of the largest values of the conditional probability of the next bit of the next information sequence, set the current values of the conditional probability of encoding the zero symbol and the single symbol corresponding to the selected values of the probability of the next bit of the next information sequence with the corresponding precedence position numbers, divide the current arithmetic coding interval into the current coding subinterval of the zero symbol and for the current sub-interval of encoding a single symbol, depending on the current values of the conditional probabilities of encoding the zero symbol and the single symbol, perform arithmetic encoding of the next bi that next information sequence, taking into account the preselected initial binary sequence, depending on the previous bits with the current values of the conditional probability, recalculate the current values of the conditional probability of encoding the zero symbol and the single symbol and perform subsequent actions until the next bits of the next information sequence are exhausted, transmit m of the selected values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding position numbers of precedence on the receiving side, on the receiving side receive accepted values of the conditional probability of the appearance of the next bit of the next information sequence and the corresponding position numbers of precedence, which are stored, set the current values of the conditional probability of decoding a zero character and a single character corresponding to the accepted values of the conditional probability of queue occurrence first bit of the next information sequence with the corresponding precedence position numbers, divide the current arithmetic decoding interval into the current decoding subinterval of the zero symbol and into the current decoding subinterval of a single symbol, depending on the current values of the conditional probability of decoding the zero symbol and the single symbol, perform arithmetic decoding of the next bits of the next received sequences in the next bit of the next recovered information sequence, taking into account the pre-selected initial binary sequence, depending on the previous bits, with the current values of the conditional probability of decoding the zero symbol and the single symbol.