Способ совместного арифметического и помехоустойчивого кодирования

Способ совместного арифметического и помехоустойчивого кодирования

Иллюстрации

Показать все

Реферат

Заявленное техническое решение относится к области электросвязи и информационных технологий, а именно к технике сжатия избыточной двоичной информации и ее помехоустойчивого кодирования при обмене данными по каналам передачи с ошибками.

Заявленное изобретение может быть использовано для обеспечения достоверности избыточной двоичной информации, передаваемой по каналам с ошибками.

Известен способ адаптивного помехоустойчивого кодирования по патенту РФ 2375824, МПК Н04L 1/20 (2006.01) от 10.12.2009, заключающийся в том, что на передающей стороне исходную информацию кодируют помехоустойчивым кодом с переменными параметрами, далее помехоустойчивый код передают в канал связи, на приемной стороне помехоустойчивый код декодируют с обнаружением и исправлением ошибок в зависимости от корректирующей способности выбранного кода, по результатам декодирования помехоустойчивого кода оценивают качество канала связи и выбирают переменные параметры помехоустойчивого кода, обеспечивающие заданную вероятность правильного приема помехоустойчивого кода, и далее эти параметры помехоустойчивого кода сообщают на передающую сторону, отличающийся тем, что на приемной стороне по результатам декодирования помехоустойчивого кода рассчитывают начальную величину избыточности помехоустойчивого кода, обеспечивающую заданную вероятность правильного приема помехоустойчивого кода, оценивают вероятность правильного приема помехоустойчивого кода с выбранными параметрами, вычисляют величину отклонения полученной вероятности правильного приема помехоустойчивого кода от заданной вероятности правильного приема кода и в зависимости от величины этого отклонения корректируют величину избыточности помехоустойчивого кода, которую передают на передающую сторону, где формируют помехоустойчивый код с полученной избыточностью.

последовательность с помощью одного из способов сжатия речевого сигнала, Недостатком указанного аналога является неэффективное использование пропускной способности канала передачи, вызванное отсутствием сжатия избыточной двоичной информации при обмене данными по каналам передачи с ошибками.

Известен также способ совместного сжатия и помехоустойчивого кодирования речевых сигналов, описанный, например, в книге С.Н. Кириллов, В.Т. Дмитриев, Д.Е. Крысяев, С.С. Попов "Исследование качества передаваемой речевой информации при различном сочетании алгоритмов кодирования источника и канала связи в условиях воздействия помех". - Рязань, Вестник РГРТУ, Выпуск 23, 2008. Данный способ заключается в том, что предварительно формируют множество способов сжатия речевого сигнала, таких как импульсно-кодовая модуляция, адаптивная дельта-модуляция, адаптивная дифференциальная импульсно-кодовая модуляция, и множество способов помехоустойчивого кодирования, таких как кодирование Хэмминга, кодирование Боуз-Чоудхури-Хоквингема, на передающей стороне от отправителя получают очередную часть речевого сигнала длиною речевая фраза, которую преобразуют в сжатую двоичную затем выполняют помехоустойчивое кодирование сжатой двоичной последовательности с помощью одного из способов помехоустойчивого кодирования, передают на приемную сторону по каналу прямой связи очередную часть кодированной последовательности вместе с информацией об использованном способе сжатия речевого сигнала и способе помехоустойчивого кодирования, на приемной стороне получают очередную часть принятой последовательности, которую последовательно декодируют с использованием соответствующих способа помехоустойчивого декодирования и способа восстановления речевого сигнала, вычисляют оценку качества восстановленного речевого сигнала и полученную оценку сравнивают с пороговым значением качества, если вычисленная оценка качества восстановленного речевого сигнала не хуже порогового значения качества, то передают получателю очередную часть восстановленной информационной последовательности и от отправителя получают очередную часть речевого сигнала и выполняют последующие действия, иначе передают по каналу обратной связи требование изменить способ сжатия речевого сигнала и способ помехоустойчивого кодирования, и выполняют последующие действия.

Данный аналог обеспечивает согласованность выполнения операций сжатия и помехоустойчивого кодирования речевых сигналов, что потенциально позволяет получить сжатый до предельно достижимых значений речевой сигнал, имеющий качество восстановленного речевого сигнала не хуже порогового значения после передачи по каналу передачи с ошибками.

Недостатком указанного аналога является большая задержка передачи по каналу передачи, вызванная необходимостью перебора подходящих способа сжатия речевого сигнала и способа помехоустойчивого кодирования.

Наиболее близким по своей технической сущности к заявленному способу совместного арифметического и помехоустойчивого кодирования является способ совместного арифметического и помехоустойчивого кодирования по патенту США 6892343, МПК Н03M 13/00 (2006.01) от 10.05.2005. Способ - прототип совместного арифметического и помехоустойчивого кодирования заключается в том, что на передающей стороне от отправителя получают очередной символ информационной последовательности, из предварительно сформированного множества выбирают проверочные символы, которые записывают вместе с очередными символами информационной последовательности, разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередных символов из числа символов информационной последовательности и проверочных символов в очередную часть сжатой последовательности, преобразуют очередную часть сжатой последовательности в очередную часть модулированной последовательности, передают очередную часть модулированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные символы информационной последовательности, на приемной стороне получают очередную часть принятой последовательности, которую запоминают, разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют, из декодированных символов выделяют очередные символы восстановленной информационной последовательности и декодированные проверочные символы, если декодированные проверочные символы принадлежат предварительно сформированному множеству проверочных символов, то делают вывод об отсутствии ошибок передачи и передают получателю очередной символ восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части принятой последовательности.

Способ-прототип совместного арифметического и помехоустойчивого кодирования обеспечивает возможность обнаружения и исправления ошибок канала передачи кодированной информационной последовательности.

Общая схема способа-прототипа совместного арифметического и помехоустойчивого кодирования представлена на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных символов информационной последовательности (ИП), а на приемной стороне - совместное декодирование с обнаружением и исправлением ошибок канала передачи. На передающей стороне при получении от отправителя от одного до нескольких символов информационной последовательности в блоке проверочных символов 1 из предварительно сформированного множества проверочных символов выбирают проверочные символы (ПС), которые последовательно записывают вместе с очередными символами информационной последовательности и кодируют в арифметическом кодере 2 в очередную часть сжатой последовательности (СП). Текущее состояние арифметического кодера определяется текущими значениями счетчика числа нулевых кодируемых символов 3 и счетчика числа единичных кодируемых символов 4, в соответствии с которыми в формирователе границ подинтервалов кодирования 5 разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа. Затем в модуляторе 6 преобразуют очередную часть сжатой последовательности в очередную часть модулированной последовательности, которую передают по каналу передачи 7. На приемной стороне получают очередную часть принятой последовательности и в демодуляторе - последовательном декодере 8 демодулируют ее в двоичную последовательность, которую запоминают. Запомненные очередные части принятой последовательности декодируют в арифметическом декодере 9. Текущее состояние арифметического декодера определяется текущими значениями счетчика числа нулевых декодируемых символов 10 и счетчика числа единичных декодируемых символов 11, в соответствии с которыми в формирователе границ подинтервалов декодирования 12 разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа. Из очередной части декодированной последовательности выделяют очередную часть восстановленной информационной последовательности и декодированные проверочные символы. Декодированные проверочные символы из очередных частей декодированной последовательности в блоке сравнения 13 сравнивают со считанными из блока проверочных символов 14 соответствующими проверочными символами, и при нахождении случая совпадения делают вывод об отсутствии ошибок передачи и передают получателю очередную часть восстановленной информационной последовательности. Иначе в демодуляторе - последовательном декодере 8 поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности, которые арифметически декодируют и выполняют последующие действия до достижения вывода об отсутствии ошибок передачи.

Особенностью способа-прототипа является то, что на передающей стороне выполняют сначала внесение помехоустойчивой избыточности в информационную последовательность, а затем ее сжатие, а на приемной стороне при разжатии обнаруживают ошибки канала передачи при их наличии, а при их обнаружении методом проб и ошибок выполняют их исправление.

Однако в данном способе-прототипе совместного арифметического и помехоустойчивого кодирования с момента возникновения ошибки канала передачи до ее обнаружения арифметический декодер выполняет декодирование значительного числа Μ двоичных символов принятой последовательности. Для исправления обнаруженной ошибки приходится выполнять большое число вариантов инвертирования от одного до Μ битов в запомненных очередных частях принятой последовательности с их последующим арифметическим декодированием и проверкой отсутствия ошибок передачи. Число возможных вариантов инвертирования для исправления многократных ошибок достигает величины вплоть до 2^M, что приводит к высокой трудоемкости исправления ошибок канала передачи, и с ростом числа Μ исправление становится технически невозможным.

Таким образом, недостатком ближайшего аналога (прототипа) является сравнительно большая трудоемкость исправления ошибок передачи.

Техническим результатом заявляемого решения является совместное арифметическое и помехоустойчивое кодирование избыточной двоичной информационной последовательности с уменьшением трудоемкости исправления ошибок передачи.

Указанный технический результат в заявляемом способе совместного арифметического и помехоустойчивого кодирования достигается тем, что в известном способе совместного арифметического и помехоустойчивого кодирования, заключающимся в том, что на передающей стороне от отправителя получают очередной символ информационной последовательности, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередных символов информационной последовательности в очередную часть сжатой последовательности, передают очередную часть последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные символы информационной последовательности, на приемной стороне получают очередную часть принятой последовательности, которую запоминают, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют, делают вывод об отсутствии ошибок передачи и передают получателю очередной символ восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части принятой последовательности, дополнительно на передающей стороне разделяют текущий подинтервал кодирования нулевого символа на подинтервал кодирования нулевого символа после нулевого символа и на подинтервал кодирования нулевого символа после единичного символа, а текущий подинтервал кодирования единичного символа разделяют на подинтервал кодирования единичного символа после нулевого символа и на подинтервал кодирования единичного символа после единичного символа, выполняют арифметическое кодирование очередных символов информационной последовательности с учетом предыдущего кодированного символа в очередную часть сжатой последовательности, которую передают на приемную сторону, на приемной стороне разделяют текущий подинтервал декодирования нулевого символа на подинтервал декодирования нулевого символа после нулевого символа и на подинтервал декодирования нулевого символа после единичного символа, а текущий подинтервал декодирования единичного символа разделяют на подинтервал декодирования единичного символа после нулевого символа и на подинтервал декодирования единичного символа после единичного символа, запомненные очередные части принятой последовательности арифметически декодируют с учетом предыдущего декодированного символа, если предыдущие декодированные символы совпадают с соответствующими предыдущими декодированными символами из текущих подинтервалов декодирования, то делают вывод об отсутствии ошибок передачи.

В предлагаемой совокупности действий на передающей стороне выполняют арифметическое кодирование очередных символов информационной последовательности с учетом предыдущего кодированного символа в очередную часть сжатой последовательности. Возможный порядок кодирования показан на решетчатой диаграмме допустимых путей совместного арифметического и помехоустойчивого кодирования двоичной информационной последовательности, представленной на рис. 2. Данная решетчатая диаграмма представляет собой ориентированный граф, который в начальный момент времени t₀ начинается с одного из двух начальных состояний, обозначенных как начальное состояние предыдущего символа "0" или начальное состояние предыдущего символа "1". Если первый кодируемый символ ИП является нулевым, то при установленном начальном состоянии "0" кодирование в момент времени t₁ переходит в состояние "кодирование нулевого символа после нулевого символа" или кратко состояние "0/0". Если первый кодируемый символ ИП является единичным, то при установленном начальном состоянии "0" кодирование в момент времени t₁ переходит в состояние "кодирование единичного символа после нулевого символа" или кратко состояние "1/0". При установленном начальном состоянии "1" кодирование в момент времени t₁ при единичном первом кодируемом символе ИП переходит в состояние "кодирование единичного символа после единичного символа" или кратко "1/1" и при нулевом первом кодируемом символе ИП кодирование переходит в состояние "кодирование нулевого символа после единичного символа" или кратко "0/1". Аналогичным образом, начиная с момента времени t₂ и до тех пор, пока поступают очередные символы информационной последовательности, из текущего состояния кодирования переходит в последующее состояние с учетом предыдущего кодированного символа. Таким образом, решетчатая диаграмма допустимых путей кодирования, показанная на рис. 2, состоит из четырех состояний кодирования, обозначенных вершинами "0/0", "1/0", "0/1" и "1/1", из каждого текущего состояния при кодировании очередного нулевого или единичного символа ИП возможен переход в одно из двух соответствующих последующих состояний, а в каждое последующее состояние возможен переход из двух соответствующих предыдущих состояний. Например, из состояния "0/0" при кодировании очередного нулевого символа ИП кодирование переходит в состояние "0/0", а при кодировании очередного единичного символа ИП кодирование переходит в состояние "1/0" и т.д. Соответственно, в очередное состояние "0/0" можно перейти из предыдущего состояния "0/0" при предыдущем нулевом кодированном символе, или из предыдущего состояния "1/0" при предыдущем единичном кодированном символе и т.д. Из каждого текущего состояния кодирования можно перейти в 2 соответствующих последующих состояний из общего числа четырех состояний, и в каждое текущее состояние кодирования можно перейти из 2 соответствующих предыдущих состояний из общего числа четырех состояний, что составляет множество допустимых путей кодирования. В сжатой последовательности, сформированной в соответствии с данной решетчатой диаграммой допустимых путей кодирования, имеется помехоустойчивая избыточность, позволяющая обнаружить факт искажения сжатой последовательности из-за ошибок передачи. Если при декодировании принятой последовательности обнаруживают, что хотя бы один переход из предыдущего состояния в последующее состояние не принадлежит множеству допустимых путей кодирования, то это однозначно свидетельствует о наличии ошибки передачи.

В предлагаемом способе обнаружение ошибок выполняют при декодировании каждого очередного символа восстановленной ИП, а не после нескольких очередных символов восстановленной ИП с соответствующими им проверочными символами, как выполняют в способе-прототипе, что позволяет выполнять декодирование меньшего числа Μ двоичных символов принятой последовательности от момента возникновения ошибки канала передачи до ее обнаружения.

Поэтому указанная новая совокупность действий позволяет при выполнении совместного арифметического и помехоустойчивого кодирования избыточной двоичной информационной последовательности сократить число перебираемых вариантов исправления ошибок передачи и тем самым уменьшить трудоемкость исправления ошибок передачи.

Заявленный способ поясняется чертежами, на которых показаны:

- на фиг. 1 - общая схема совместного арифметического и помехоустойчивого кодирования в ближайшем аналоге (прототипе);

- на фиг. 2 - решетчатая диаграмма допустимых путей совместного арифметического и помехоустойчивого кодирования двоичной информационной последовательности;

- на фиг. 3 - общая схема совместного арифметического и помехоустойчивого кодирования в предлагаемом способе;

- на фиг. 4 - алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне;

- на фиг. 5 - временные диаграммы совместного арифметического и помехоустойчивого кодирования на передающей стороне;

- на фиг. 6 - таблица состояний совместного арифметического и помехоустойчивого кодирования информационной последовательности;

- на фиг. 7 - последовательность состояний совместного арифметического и помехоустойчивого кодирования информационной последовательности;

- на фиг. 8 - временные диаграммы совместного арифметического декодирования и исправления ошибок на приемной стороне;

- на фиг. 9 - алгоритм совместного арифметического декодирования и исправления ошибок на приемной стороне;

- на фиг. 10 - таблица состояний совместного декодирования с ошибкой передачи в третьем бите;

- на фиг. 11 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее первого бита;

- на фиг. 12 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее второго бита;

- на фиг. 13 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее третьего бита;

- на фиг. 14 - сравнение трудоемкости исправления ошибок передачи для способа-прототипа и заявленного способа.

Реализация заявленного способа представлена на примере системы совместного арифметического и помехоустойчивого кодирования, показанной на фиг. 3. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных символов информационной последовательности, а на приемной стороне - совместное декодирование с обнаружением и исправлением ошибок канала передачи. На передающей стороне полученный от отправителя очередной символ информационной последовательности кодируют в арифметическом кодере 2. Текущее состояние арифметического кодера определяется текущими значениями счетчика числа нулевых кодируемых символов 3 и счетчика числа единичных кодируемых символов 4, в соответствии с которыми в формирователе границ подинтервалов кодирования 5 сначала разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, а затем указанные подинтервалы разделяют на подинтервал кодирования нулевого символа после нулевого символа, на подинтервал кодирования нулевого символа после единичного символа, на подинтервал кодирования единичного символа после нулевого символа, и на подинтервал кодирования единичного символа после единичного символа, соответственно. Поэтому в арифметическом кодере 2 очередной символ информационной последовательности кодируют с учетом предыдущего кодированного символа в очередную часть сжатой последовательности, которую передают по каналу передачи 7. На приемной стороне получают очередную часть принятой последовательности и в последовательном декодере 15 ее запоминают. Запомненные очередные части принятой последовательности декодируют в арифметическом декодере 9 с учетом предыдущего декодированного символа. Текущее состояние арифметического декодера определяется текущими значениями счетчика числа нулевых декодируемых символов 10 и счетчика числа единичных декодируемых символов 11, в соответствии с которыми в формирователе границ подинтервалов декодирования 12 сначала разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа, а затем указанные подинтервалы разделяют на подинтервал декодирования нулевого символа после нулевого символа, на подинтервал декодирования нулевого символа после единичного символа, на подинтервал декодирования единичного символа после нулевого символа, и на подинтервал декодирования единичного символа после единичного символа, соответственно.

В блоке сравнения предыдущих символов 13 сравнивают предыдущие декодированные символы с соответствующими предыдущими декодированными символами из текущих подинтервалов декодирования и при их совпадении делают вывод об отсутствии ошибок передачи и передают получателю очередную часть восстановленной информационной последовательности, иначе в последовательном декодере 15 поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности, которые декодируют в арифметическом декодере 9 до достижения вывода об отсутствии ошибок передачи.

Алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне представлен на фигуре 4.

В способе совместного арифметического и помехоустойчивого кодирования реализуется следующая последовательность действий.

На передающей стороне от отправителя получают очередной двоичный символ информационной последовательности. Примерный вид первых восемнадцати символов ИП вида "111111111011111010" показан на фиг. 5(a). Видно, что информационная последовательность является избыточной: вероятность получения единичных символов существенно превышает вероятность получения двоичных символов. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы разделения текущего интервала арифметического кодирования на подинтервал кодирования нулевого символа после нулевого символа, на подинтервал кодирования нулевого символа после единичного символа, на подинтервал кодирования единичного символа после нулевого символа, и на подинтервал кодирования единичного символа после единичного символа заключаются в следующем. Сначала разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, что описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43.

Текущий интервал арифметического кодирования состоит из множества значений от нижнего значения интервала кодирования до верхнего значения интервала кодирования. В начальном состоянии арифметического кодирования начальное нижнее значение интервала кодирования устанавливают в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 11111111 в двоичном представлении. Пример начального состояния (Нач. сост.) арифметического кодирования представлен на фиг. 6 при t₀ и на фиг. 7. Например, произвольно выбрано единичное начальное состояние предыдущего символа (нач. сост.) "1", как показано в первой строке на фиг. 7 при t₀.

Текущий интервал арифметического кодирования разделяют на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в соответствии с текущими значениями вероятности кодируемых нулевых символов p₀[i] и вероятности кодируемых единичных символов p₁[i]. Текущее значение вероятности кодируемых нулевых символов p₀[i] при арифметическом кодировании i-го очередного двоичного символа информационной последовательности вычисляют по формуле вида , а текущее значение вероятности кодируемых единичных символов p₁[i] вычисляют по формуле вида , где N₀[i] - текущее число закодированных нулевых символов, N₁[i] - текущее число закодированных единичных символов, a N[i] - текущее число закодированных нулевых и единичных символов, равное N[i]=Ν₀[i]+Ν₁[i]. Соответственно, для текущего значения вероятности кодируемых нулевых символов p₀[i] и текущего значения вероятности кодируемых нулевых символов p₁[i] должно выполняться ограничение вида: p₀[i]+p₁[i]=1. В известных способах, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ - МИФИ, 2002, стр. 124-130, в начальном состоянии кодирования устанавливают начальное число закодированных нулевых символов равным N₀[0]=1, а начальное число закодированных единичных символов - равным N₁[0]=1, то есть начальные значения вероятности кодируемых единичных и нулевых символов устанавливают равными: p₁[0]=p₀[0]=1/2.

Начальное значение интервала кодирования арифметического кодирования I[0], равное I[0]=H[0]-L[0], разделяют на начальные значения подинтервала нулевых символов D₀[0] и подинтервала единичных символов D₁[0], длины которых прямо пропорциональны начальным значениям вероятностей кодируемых нулевых символов р₀[0] и единичных символов p₁[0], соответственно. Начальную длину подинтервала единичных символов D₁[0] определяют по формуле вида D₁[0]=I[0]×p₁[0], а начальную длину подинтервала нулевых символов D₀[0] определяют по формуле вида D₀[0]=I[0]-D₁[0]. Например, начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 128 или 10000000 в двоичном представлении, а начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 127 или 01111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 7. Верхнюю границу подинтервала нулевых символов обозначают как значение , и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения исключительно, а подинтервал единичных символов простирается от значения включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Начальное значение имеет десятичное значение 127, как показано на фиг. 6 в первой строке при t=0.

При кодировании очередного, i-го по счету символа ИП, соответственно, текущий интервал кодирования арифметического кодирования равный I[i]=H[i]-L[i], разделяют на текущие значения подинтервала нулевых символов D₀[i] и подинтервала единичных символов D₁[i], длины которых прямо пропорциональны текущим значениям вероятностей кодируемых нулевых символов p₀[i] и единичных символов p₁[i], соответственно.

Затем текущий подинтервал кодирования нулевого символа разделяют на текущий подинтервал кодирования нулевого символа после нулевого символа и на текущий подинтервал кодирования нулевого символа после единичного символа, а текущий подинтервал кодирования единичного символа разделяют на текущий подинтервал кодирования единичного символа после нулевого символа и на текущий подинтервал кодирования единичного символа после единичного символа в соответствии с текущими значениями вероятности кодируемых нулевых символов р₀[i] и вероятности кодируемых единичных символов p₁[i]. Текущий подинтервал кодирования единичного символа после единичного символа D_1/1[i] вычисляют по формуле D_1/1[i]=D_l[i]×p_l[i], текущий подинтервал кодирования единичного символа после нулевого символа D_1/0[i] вычисляют по формуле D_1/0[i]=D₁[i]-D_1/1[i]. Текущий подинтервал кодирования нулевого символа после нулевого символа D_0/0[i] вычисляют по формуле D_0/0[i]=D₀[i]×p₀[i], текущий подинтервал кодирования нулевого символа после единичного символа D_0/1[i] вычисляют по формуле D_0/1[i]=D₀[i]-D_0/0[i]. Например, начальная длина подинтервала кодирования единичного символа после единичного символа D_1/1[0] имеет десятичное значение 64, и начальная длина подинтервала кодирования нулевого символа после нулевого символа D_0/0[0] имеет десятичное значение 64. Обозначим верхнюю границу подинтервала кодирования нулевого символа после нулевого символа как значение , равное , а верхнюю границу подинтервала кодирования единичного символа после нулевого символа как значение , равное . В соответствии с этим подинтервал кодирования нулевого символа после нулевого символа D_0/0 начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения исключительно, а подинтервал кодирования нулевого символа после единичного символов D_0/1 простирается от значения включительно до значения исключительно. Соответственно, подинтервал кодирования единичного символа после нулевого символа D_1/0 начинается снизу от значения включительно до значения исключительно, а подинтервал кодирования единичного символа после единичного символа D_1/1 простирается от значения включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Пример начальных значений L, , , и H показан на фиг. 6 в первой строке при t=0 и на фиг. 7.

Способы арифметического кодирования очередных символов информационной последовательности с учетом предыдущего кодированного символа в очередную часть сжатой последовательности заключаются в последовательном сжатии очередных двоичных символов информационной последовательности в очередную часть сжатой последовательности в соответствии с текущим значением подинтервала кодирования очередного символа при условии, что ранее был кодирован конкретный предыдущий символ, и в соответствии с текущими значениями вероятностей кодируемых нулевых символов и единичных символов. В результате кодирования очередного символа ИП в качестве следующего интервала кодирования выбирают текущий подинтервал кодирования символа, идентичного с очередным двоичным символом ИП с учетом предыдущего кодированного символа.

Например, первый символ информационной последовательности является единичным символом, а в качестве предыдущего кодированного символа в начальном состоянии установлен единичный символ. Среди имеющихся четырех текущих подинтервалов кодирования, таких как D_0/0[0], D_0/1[0], D_1/0[0] и D_1/1[0] выбирают текущий подинтервал кодирования единичного символа после единичного символа D_1/1[0] и текущий интервал кодирования первого символа ИП I[1] становится равным I[1]=D_1/1[0]. Нижняя граница текущего интервала кодирования первого символа становится равной , соответствующей десятичному числу 191 или 10111111 в двоичном представлении. Верхняя граница текущего интервала кодирования первого символа становится равной H[1]=H[0], соответствующей десятичному числу 255 или 11111111 в двоичном представлении, как показано на фиг. 6 и на фиг. 7 при t=1.

Самый левый бит двоичного представления значения L[l] сравнивают с самым левым битом двоичного представления значения H[1], например, вида 10111111 и 11111111, соответственно. При их несовпадении переходят к сжатию следующего символа.

Иначе при их совпадении значение самого левого бита двои