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

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

Иллюстрации

Показать все

Реферат

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

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

Известны способы шифрования двоичной информации, описанные, например, в государственном стандарте 28147-89. Системы обработки информации. Зашита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР. 1989, стр. 9-14. В данных способах у отправителя двоичную последовательность (ДП) разделяют у отправителя на последовательные блоки длиной n бит, где обычно n=64. По криптографической функции с использованием заранее сформированного для отправителя и получателя секретного ключа (СК) последовательно из каждого блока ДП с учетом предыдущего зашифрованного блока формируют зашифрованный текущий блок до тех пор, пока поступают блоки ДП. Зашифрованные текущие блоки передают по каналу связи получателю. Принятые получателем зашифрованные текущие блоки по криптографической функции с использованием СК последовательно расшифровывают с учетом предыдущего зашифрованного принятого блока до тех пор, пока поступают зашифрованные блоки.

Недостатками указанных аналогов являются:

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

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

Известен также способ арифметического кодирования с шифрованием по патенту РФ 2226041 МПК H04L 9/08 (2006.01) от 01.11.2001. Данный способ заключается в том, что на передающей стороне исходная информация искажается с помощью ключевой последовательности, а на приемной стороне искаженная информация восстанавливается с помощью ключевой последовательности с посимвольной обработкой, отличающийся тем, что входные двоичные данные разбивают на блоки фиксированной длины и кодируют поочередно, подвергая их преобразованию методом арифметического кодирования с криптографическими функциями F₁, F₂ и

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

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

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

Способ-прототип арифметического кодирования с шифрованием обеспечивает высокую защищенность к попыткам нарушителя несанкционированного чтения зашифрованной информации. Общая схема способа-прототипа арифметического кодирования с шифрованием представлена на фиг. 1. На передающей стороне выполняют арифметическое кодирование с зашифрованием двоичной информационной последовательности (ИП), а на приемной стороне - арифметическое декодирование с ее расшифрованием. На передающей стороне очередные части двоичной информационной последовательности поступают на вход кодера с зашифрованием 1. В процессе арифметического кодирования очередных частей двоичной информационной последовательности последовательно уточняют значения первого и второго счетчиков частоты кодирования, составляющие модель кодирования, реализуемой блоком модели кодирования 2. Чем ближе значения первого и второго счетчиков частоты кодирования к действительной вероятности появления нулевых символов и единичных символов, соответственно, сжимаемой избыточной информационной последовательности, тем выше коэффициент сжатия арифметического кодирования этой информационной последовательности.

Особенностью способа-прототипа арифметического кодирования с шифрованием является генерирование случайной битовой последовательности с использованием генератора случайных чисел 3 (ГСЧ), которая вместе с главным ключом используют для криптографического изменения модели кодирования, непредсказуемого для нарушителя, пытающегося при перехвате в канале передачи 4 зашифрованной последовательности (ЗП) вычислить из нее двоичную информационную последовательность без знания конфиденциального ключа.

На приемной стороне очередные части принятой зашифрованной последовательности поступают на вход декодера с расшифрованием 6. Сгенерированная отправителем случайная битовая последовательность в составе зашифрованной последовательности передается получателю, который выделяет ее в декодере случайной последовательности 7 и вместе с главным ключом используют для криптографического изменения модели декодирования, идентичного криптографическому изменению модели кодирования. Модель декодирования реализуется блоком модели декодирования 8.

Общий принцип использования случайной битовой последовательности для шифрования двоичных информационных последовательностей известен в науке и технике и описан, например, в книге М.А. Иванов "Криптографические методы защиты информации в компьютерных системах и сетях". - М.: КУДИЦ-ОБРАЗ, 2001, стр. 254-256. Совокупность таких способов шифрования двоичных информационных последовательностей известна как способы вероятностного (рандомизированного) шифрования двоичных информационных последовательностей, обеспечивающих повышение защищенности к попыткам нарушителя несанкционированного чтения зашифрованной информации. Данное повышение защищенности обусловлено тем, что изменяющаяся каждый раз случайная битовая последовательность при арифметическом кодировании с зашифрованием существенно повышает непредсказуемость для нарушителя результата кодирования с зашифрованием, включая случай известности для нарушителя кодируемой двоичной информационной последовательности.

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

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

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

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

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

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

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

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

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

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

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

- на фиг. 4 - алгоритм арифметического кодирования с зашифрованием;

- на фиг. 5 - временные диаграммы арифметического кодирования с зашифрованием;

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

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

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

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

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

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

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

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

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

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

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

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

Предварительное формирование для передающей и приемной сторон ключа заключается в следующем. Ключ в виде двоичной последовательности (ДП) формируют с использованием генератора случайных импульсов, генерирующего случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Способы формирования случайным выбором символов двоичной последовательности ключа известны и описаны, например, в книге: Д. Кнут "Искусство программирования на ЭВМ". - М.: Мир, 1977, т. 2, стр. 22. Длина ДП ключа в битах должна быть не менее 256 бит, что описано, например, в ГОСТ 28147-89. Данный ключ является конфиденциальным и известен только на передающей и приемной стороне. Примерный вид ключа показан на фиг.3(a). Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы предварительного формирования для передающей стороны начальных значений первого и второго регистров кодирования также используют генератор случайных импульсов, генерирующий случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Случайным образом формируют начальное значение первого регистра кодирования в виде двоичной последовательности длины R битов, равной разрядности устройства, реализующего арифметическое кодирование, и начальное значение второго регистра кодирования в виде двоичной последовательности удвоенной длины 2R битов. Примерный вид начального значения первого регистра кодирования (Нач. знач. 1-го рег. код.) в виде 8-битовой ДП "10011011" и начального значения второго регистра кодирования (Нач. знач. 2-го рег.код.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(б). Предварительно сформированные для приемной стороны начальные значения первого и второго регистров декодирования полностью совпадают с соответствующими предварительно сформированными начальными значениями первого и второго регистров кодирования. Примерный вид начального значения первого регистра декодирования (Нач. знач. 1-го рег. декод.) в виде 8-битовой ДП "10011011" и начального значения второго регистра декодирования (Нач. знач. 2-го рег. декод.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(в).

Способы предварительного формирования для передающей и приемной сторон криптографической функции известны и описаны, например, в книге М.Д. Смид, Д.К. Бранстед "Стандарт шифрования данных: Прошлое и будущее". ТИИЭР, 1988, - т. 76, №5, стр. 49. Они заключаются в формировании криптографической функции, используя алгоритм шифрования данных DES в режиме обратной связи по шифртексту или в режиме обратной связи по выходу. При этом шифрование выполняют над очередной частью кодированной последовательности (КП) длиной R бит. Примерный вид очередной части кодированной последовательности (Очер. часть КП) показан на фиг. 3(г). В результате использования предварительно сформированных криптографической функции, ключа и первого и второго регистров кодирования предыдущей части двоичной информационной последовательности формируют очередную часть зашифрованной последовательности (ЗП). Данные способы обеспечивают формирование каждого битового значения очередной части зашифрованной последовательности в зависимости от каждого битового значения очередной части зашифрованной, от каждого бита ключа и от каждого бита первого и второго регистров кодирования предыдущей части двоичной информационной последовательности. Примерный вид очередной части зашифрованной последовательности (Очер. часть ЗП) длиной R бит показан на фиг. 3(д).

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

На передающей стороне от отправителя получают очередную часть двоичной информационной последовательности. Кодирование информационной последовательности начинается с момента поступления первого ее бита и при кодировании первых битов очередной части двоичной информационной последовательности не требуется получения от отправителя целиком очередной части этой последовательности. Примерный вид первых трех очередных частей двоичной информационной последовательности (ИП) в виде двоичной последовательности "0111110110000100010001001" длиной 25 бит показан на фигуре 5(a).

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

единичных символов еще не подсчитано, поэтому начиная кодировать первую часть двоичной информационной последовательности значения первого и второго счетчиков частоты кодирования вычисляют, например, в соответствии с ключом. Например, в соответствии с ключом первый и второй счетчики частоты кодирования принимают значения 11 и 2, соответственно. Поэтому суммарное число кодируемых нулевых и единичных символов N принимает начальное значение, равное N=13, как показано в верхней строке начального состояния арифметического кодирования с зашифрованием на фиг. 6 в начальный момент времени t=0. Значение первого счетчика частоты кодирования определяет значение вероятности кодируемых нулевых символов р₀, а значение второго счетчика частоты кодирования определяет значение вероятности кодируемых единичных символов р₁, при этом должно выполняться ограничение вида: р₀+р₁=1 Значение вероятности кодируемых нулевых символов р₀ вычисляют по формуле вида а значение вероятности кодируемых единичных символов р₁ вычисляют по формуле вида

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

Значение интервала кодирования арифметического кодирования I, равное I=H-L, разделяют на значения подинтервала нулевых символов D₀ и подинтервала единичных символов D₁, длины которых прямо пропорциональны значениям первого и второго счетчиков частоты кодирования или, что удобнее для кодирования, значениям вероятностей кодируемых нулевых символов р₀ и единичных символов p₁, соответственно. Длину подинтервала единичных символов D₁, определяют по формуле вида D₁=I×p₁, а длину подинтервала нулевых символов D₀ определяют по формуле вида D₀=I-D₁.

Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты кодирования N₀=11 и N₁=2, соответственно, начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 38 или "00100110" в двоичном представлении, а начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 255-38=217 или "11011001" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов, как показано на фиг. 7. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Значение первого регистра кодирования устанавливают равным значению Q. Например, в момент времени r=0 значение первого регистра кодирования равно десятичному значению 217 или "11011001" в двоичном представлении, как показано на фиг. 6 в первой строке при t=0. Во второй регистр кодирования записывают, например, нижнее L и верхнее Н значения интервала кодирования. Например, в момент времени t=0 во втором регистре кодирования последовательно записаны десятичные значения 0 и 255 или "00000000" и "11111111" в двоичном представлении, как показано на фиг. 6 в первой строке при t=0, а также как показано на фиг. 7 в начальном состоянии (Нач. сост.) арифметического кодирования.

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

Примерный вид арифметического кодирования показанной на фиг. 5(a) двоичной информационной последовательности вида "0111110110000100010001001" длиною 25 двоичных символов с использованием арифметического кодирования в кодированную последовательность вида "110110001110111100101001" представлен на фиг. 6 и на фиг. 7.

При поступлении на вход арифметического кодирования первого кодируемого символа (t=1), являющегося нулевым двоичным символом, значение интервала кодирования первого символа I[1] устанавливают равным начальному значению подинтервала нулевых символов D₀[0], поэтому нижнее значение интервала кодирования первого символа L[l] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодера L[0], записанному во второй регистр кодирования, равному, например, 0, а верхнее значение интервала кодирования первого символа арифметического кодирования H[1] устанавливают равным текущему значению Q, записанному в первый регистр кодирования, равному, например, 217, как показано на фиг. 7. Самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения H[1], например, вида "00000000" и "11011001", соответственно, как показано на фиг. 6 при t=1. При их несовпадении переходят к кодированию следующего бита входных данных.

После выполнения кодирования каждого очередного бита входных данных уточняют число закодированных нулевых символов и единичных символов. Так как первый очередной бит является нулевым, то число закодированных нулевых символов увеличивают на единичное значение и оно составляет N₀[1]=12, и число закодированных нулевых и единичных символов становится равным N[1]=N₀[l]+N₁[1]=l3. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных В соответствии с этим длина подинтервала нулевых символов D₀[1] увеличивается по сравнению с длиной подинтервала единичных символов D₁[1], а параметр Q принимает десятичное значение 186 и двоичное значение "10111010", как показано на фиг. 7 и на фиг. 6, вторая строка сверху.

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