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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В предлагаемой совокупности действий на приемной стороне при декодировании каждого очередного бита очередной части принятой последовательности сохраняют и продолжают ограниченное число Z альтернативных принятых последовательностей с их продолжениями, имеющих наименьшие значения метрики, то есть обеспечивающих максимизацию вероятности исправления ошибок передачи, а все остальные последовательности стирают. Сложность декодирования ограниченного число Z альтернативных принятых последовательностей с их продолжениями существенно меньше сложности декодирования N^W/2 принятых последовательностей, как предлагается в способе-прототипе.

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

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

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

- на фиг. 2 - схема блока декодирования 7;

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

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

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

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

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

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

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

- на фиг. 10 - примерный вид выбираемых не более L=8 альтернативных принятых последовательностей;

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

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

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

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

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

- на фиг. 16 - таблица состояний декодирования альтернативной принятой последовательности вида "00101110 010110";

- на фиг. 17 - таблица состояний декодирования альтернативной принятой последовательности с ее последовательными продолжениями вида "00101110 000110";

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

Реализация заявленного способа представлена на примере системы совместного арифметического и помехоустойчивого кодирования и декодирования, показанной на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных частей информационной последовательности, а на приемной стороне - совместное арифметическое и помехоустойчивое декодирование принятой последовательности с обнаружением и исправлением ошибок канала передачи. На передающей стороне при получении от отправителя двоичного символа очередной части информационной последовательности при получении нулевого символа счетчик числа нулевых символов 1 увеличивает число нулевых символов кодирования на единичное значение, а при получении единичного символа счетчик числа единичных символов 2 увеличивает число единичных символов кодирования на единичное значение. Пропорционально подсчитанным числам нулевых и единичных символов кодирования в формирователе границ подынтервалов 3 текущий интервал арифметического кодирования разделяют в арифметическом кодере 5 на текущий подынтервал кодирования нулевого символа и на текущий подынтервал кодирования единичного символа. В блоке выбора проверочных символов 4 выбирают проверочные символы, которые вместе с символами очередной части информационной последовательности кодируют в арифметическом кодере 5 в очередную часть кодированной последовательности и передают по каналу передачи на приемную сторону.

На приемной стороне в Z блоках декодирования 7 принимают очередные части принятой последовательности. Схема блока декодирования 7 показана на фиг. 2. В блоке декодирования 7 формирователь альтернативной принятой последовательности (АПП) с нулевым продолжением 7.1 и формирователь АПП с единичным продолжением 7.8 формируют альтернативные принятые последовательности с соответствующими продолжениями, которые в арифметическом декодере 7.2 и арифметическом декодере 7.9, соответственно, арифметически декодируют в очередные части соответствующих им альтернативных декодированных последовательностей. При декодировании нулевого символа из АПП с нулевым продолжением счетчик числа нулевых символов 7.3 увеличивает число нулевых символов декодирования этой последовательности на единичное значение, а при декодировании единичного символа счетчик числа единичных символов 7.4 увеличивает число единичных символов декодирования на единичное значение. Пропорционально подсчитанным числам нулевых и единичных символов декодирования в формирователе границ подынтервалов 7.6 текущий интервал арифметического декодирования АПП с нулевым продолжением разделяют на текущий подынтервал декодирования нулевого символа и на текущий подынтервал декодирования единичного символа для данной последовательности.

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

В блоке вычисления метрики АПП 7.7 для каждой альтернативной принятой последовательности с ее продолжением вычисляют значение ее метрики суммированием метрики самой последовательности и ее продолжения, где метрику продолжения вычисляют как степень подобия соответствующего продолжения очередному биту очередной части принятой последовательности. В арифметических декодерах 7.2 и 7.9 из очередных частей соответствующих альтернативных декодированных последовательностей выделяют очередные части альтернативной восстановленной информационной последовательности и альтернативные декодированные проверочные символы (АВПС). Если при проверке в блоке проверки проверочных символов 7.5 АВПС, соответствующие альтернативной принятой последовательности с нулевым продолжением, являются допустимыми, то в блоке выбора АПП 8 запоминают очередные части альтернативной восстановленной информационной последовательности соответствующие альтернативной принятой последовательности с нулевым продолжением, иначе в блоке вычисления метрики АПП 7.7 устанавливают значение метрики этой альтернативной принятой последовательности с нулевым продолжением в максимальное значение.

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

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

Начиная с T-го бита принятой последовательности в блоке выбора АПП 8 сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них альтернативную принятую последовательность с наименьшим значением метрики и передают получателю в качестве очередной части восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности очередную часть альтернативной восстановленной информационной последовательности.

В способе реализуется следующая последовательность действий.

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

Способы предварительной установки на передающей стороне начального интервала арифметического кодирования и на приемной стороне соответствующего ему начального интервала арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования начинается от его начального нижнего значения и заканчивается его начальным верхним значением. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение интервала кодирования, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования H[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 11111111 в двоичном представлении. Пример начального интервала арифметического кодирования представлен на фиг. 4 при t=0 (первая строка) и на фиг. 5 при t=0.

Также предварительно устанавливают предельное число альтернативных принятых последовательностей Z≥2 и величину задержки декодирования Т≥2, а также устанавливают значения метрики альтернативных принятых последовательностей в нулевое значение. Способы предварительной установки предельного числа альтернативных принятых последовательностей Z и величины задержки декодирования Т, известны и описаны, например, в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М, Издательский дом "Вильяме", 2003, стр. 430-439. Например, рекомендуется выбирать предельное число альтернативных принятых последовательностей Z из ряда значений вида 2, 4, 8, 16 с учетом того, что при увеличении выбранного числа Z можно исправить большее число ошибок передачи, но при этом линейно растет сложность реализации исправления ошибок.

Величина задержки декодирования Т численно равна количеству битов очередных частей принятой последовательности, после декодирования которых принимают решение об очередной части восстановленной информационной последовательности. Например, рекомендуется выбирать величину задержки декодирования численно равную (2…4)×Z, что позволяет исправлять наиболее часто встречающиеся комбинации ошибок передачи без существенного роста сложности реализации исправления ошибок. Способы предварительной установки значения метрики альтернативных принятых последовательностей в нулевое значение известны и описаны, например, в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М., Издательский дом "Вильямс", 2003, стр. 432-434.

На передающей стороне от источника информации принимают очередную часть информационной последовательности длиной k≥1 бит. Примерный вид первых шести очередных частей двоичной ИП длиной k=2 бита показан на фиг. 6(a). Например, первая часть ИП имеет вид "00", вторая часть - "01", третья часть - "01" и т.д. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы разделения текущего интервала арифметического кодирования на текущий подынтервал кодирования нулевого символа и на текущий подынтервал кодирования единичного символа известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Для арифметического кодирования очередного по счету, t-го символа, где t=1, 2,…, длину текущего интервала арифметического кодирования I[t-1], равную I[t-1]=H[t-1]-L[t-1], разделяют на значение текущего подынтервала нулевого символа D₀[t-1] и значение текущего подынтервала единичного символа D₁[t-1]. Для этого подсчитывают текущее число нулевых символов информационной последовательности и проверочных символов N_∑0[t-1], суммируя текущее число нулевых символов информационной последовательности Ninf₀[7-1] и текущее число нулевых проверочных символов Nproν₀[t-1] в виде: N_∑0[t-1]=Ninf₀[t+1]+Nproν₀[t-1]. Аналогичным образом подсчитывают текущее число единичных символов информационной последовательности и проверочных символов N_∑1[t-1], суммируя текущее число единичных символов информационной последовательности и текущее число единичных проверочных символов: N_∑1[t-1]=Ninf₁[t-1]+Nproν₁[t-1]. Например, в начальный момент при t=0 текущее число нулевых символов информационной последовательности и проверочных символов N_∑0[0] установлено в значение 1, где Ninf₀[0]=1 и Nproν₀[0]=0, и текущее число единичных символов информационной последовательности и проверочных символов N_∑1[0] установлено в значение 1, где Ninf₁[0]=1 и Nproν₁[0]=0. Способы установки в начальный момент арифметического кодирования числа нулевых и единичных символов информационной последовательности в единичное значение известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 124-130. Например, как показано на фиг. 4 в первой строке при t=0, в верхней строчке указано единичное число нулевых символов информационной последовательности (графа N0) и единичное число единичных символов информационной последовательности (графа N1). Соответственно, там же в нижней строчке при t=0 указано единичное число нулевых символов информационной последовательности и проверочных символов (графа N0) и единичное число единичных символов информационной последовательности и проверочных символов (графа N1). В графе N указывается общее число нулевых и единичных символов, в верхней строчке только для символов информационной последовательности, а в нижней строчке для символов информационной последовательности и проверочных символов. При кодировании первого по счету информационного символа, являющегося, например, нулевым символом, текущее число нулевых символов информационной последовательности увеличивается на единичное значение: Ninf₀[1]=2, соответственно, текущее число нулевых символов информационной последовательности и проверочных символов становится равным N_∑0[1]=2, как показано на фиг. 4 во второй строке при t=1.

Начиная с момента кодирования первого и последующих проверочных символов при t=3, t=6, t=9 и так далее, текущее число нулевых или единичных символов информационной последовательности начинает отличаться от текущего числа нулевых или единичных, соответственно, символов информационной последовательности и проверочных символов, как показано, например, на фиг. 4 в пятой строке при t=3.

Затем вычисляют текущую вероятность нулевых символов информационной последовательности и проверочных символов P_∑0[t] по правилу: p_∑0[t]=N_∑0[t]/(N_∑0[t]+N_∑1[t]) и текущую вероятность единичных символов информационной последовательности и проверочных символов p_∑1[t] по правилу: p_∑1[t]=N_∑1[t]/(N_∑0[t]+N_∑1[t). Например, как показано на фиг. 4 в первой строке при t=0, в нижней строчке указано значение текущей вероятности нулевых символов информационной последовательности и проверочных символов (графа р0) и значение текущей вероятности единичных нулевых символов информационной последовательности и проверочных символов (графа p1), где начальные значения равны 0,5.

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

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

Выбор очередных проверочных символов выполняют следующим образом. Для выбора очередного проверочного символа, являющегося t-ым по сч