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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На передающей стороне вычисляют значения первого и второго счетчиков частоты кодирования в соответствии с двоичной информационной последовательностью, после чего из основного ключа по криптографической функции вычисляют очередную часть оперативного ключа, по которой устанавливают длину очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования, причем вычисляют очередную часть оперативного ключа в виде десятичного числа n, где n≥1, по которой устанавливают длину n бит очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования равной 2ⁿ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На приемной стороне в формирователе оперативного ключа 10 по криптографической функции из основного ключа вычисляют очередную часть оперативного ключа в виде числа n и устанавливают очередную размерность алфавита декодирования равной 2ⁿ . В считывателе очередной части принятой зашифрованной последовательности (ПШП) 11 считывают очередную часть принятой ШП. В первом счетчике частоты декодирования 12 и втором счетчике частоты декодирования 13 в соответствии с уже обработанными частями принятой ИП вычисляют значение первого счетчика частоты декодирования, подсчитывающего частоту декодированных нулевых символов, и значение второго счетчика частоты декодирования, подсчитывающего частоту декодированных единичных символов, соответственно. В первом регистре декодирования 14 и втором регистре декодирования 15 устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, очередной размерностью алфавита декодирования и очередной частью принятой ШП. В арифметическом декодере 16 в соответствии со значениями первого и второго регистров декодирования выполняют арифметическое декодирование очередной части принятой ШП в очередную часть принятой ИП, которую передают получателю.

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

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

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

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

Способы вычисления значений первого и второго счетчиков частоты кодирования в соответствии с двоичной информационной последовательностью известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130. Для этого первый счетчик частоты кодирования подсчитывает число кодируемых нулевых символов N₀ в обработанной части ИП, а второй счетчик частоты кодирования подсчитывает число кодируемых единичных символов N_l в обработанной части ИП. Числа N₀ и N₁ являются неотрицательными ненулевыми целыми числами. Также подсчитывают суммарное число кодируемых нулевых и единичных символов N, равное N=N₀+N₁. Значение частоты кодируемых нулевых символов р₀ вычисляют по формуле вида , а значение частоты кодируемых единичных символов р₁ вычисляют по формуле вида .

В начальном состоянии число кодируемых нулевых и единичных символов еще не подсчитано, поэтому в начальном состоянии устанавливают число кодируемых нулевых символов N₀=1 и число кодируемых единичных символов N_r=1. Соответственно, в начальный момент времени t=0 частота кодируемых нулевых символов равна и частота кодируемых единичных символов равна . После арифметического кодирования нулевых и единичных символов уточняют значения первого и второго счетчиков частоты кодирования.

Способы вычисления из основного ключа по криптографической функции очередной части оперативного ключа, по которой устанавливают длину очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования, заключаются в следующем. Очередную часть оперативного ключа вычисляют по предварительно сформированной криптографической функции с использованием предварительно сформированного основного ключа. Для этого зашифровывают предыдущий криптографический блок, применяя, например, алгоритм шифрования данных DES в режиме обратной связи по шифртексту или в режиме обратной связи по выходу с использованием в качестве ключа шифрования предварительно сформированный основной ключ. Для формирования первого криптографического блока используют нулевой криптографический блок, вид которого общеизвестен. Например, вид нулевого криптографического блока показан на фиг. 4(a). При использовании предварительного сформированной криптографической функции и основного ключа из нулевого криптографического блока формируют первый криптографический блок вида, например, "10111…1011", как показано на фиг. 4(a). Из сформированного очередного криптографического блока выделяют очередную часть двоичной последовательности (ДП), например, фиксированной длины в четыре бита из начала очередного криптографического блока, как показано на фиг. 4(б). Из очередной части ДП вычисляют очередную часть оперативного ключа (ОК) в виде десятичного числа n, где n≥1, для этого подсчитывают число единичных символов данной двоичной последовательности. Например, из первого криптографического блока вида "10111…1011" выделяют первую часть двоичной последовательности вида "1011", в которой имеется 3 единичных символа, соответственно, первая часть оперативного ключа имеет десятичное значение n=3. Из второго криптографического блока вида "10011…1110" выделяют вторую часть двоичной последовательности вида "1001", в которой имеется 2 единичных символа, соответственно, вторая часть оперативного ключа имеет десятичное значение n=2 и т.д., как показано на фиг. 4(в).

Устанавливают очередную размерность алфавита кодирования, равную 2ⁿ. Очередная размерность алфавита кодирования может принимать значения 2, 4, 8,... Например, при длине первой части ИП n=3 бит первая размерность алфавита кодирования равна 8, при n=2 бит вторая размерность алфавита кодирования равна 4, при n=1 бит пятая размерность алфавита кодирования равна 2 и т.д.

По значению очередной части оперативного ключа устанавливают длину n бит очередной части двоичной информационной последовательности. От отправителя получают очередную часть ИП установленной длины. Например, первая часть ИП имеет длину n=3 бита и вид "000", вторая часть ИП имеет длину n=2 бита и вид "01", пятая часть ИП имеет длину n=1 бит и вид "0", как показано на фиг. 4(г). Очередная часть ИП длиною n бит имеет общий вид a_n, a_n-l,…,a_i,…,a₂, а₁, где очередные биты а_i, i=1,2,…..., n, принимают нулевое или единичное значение, первым по времени появления является бит a₁ и т.д.

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

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

Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты кодирования N₀=1 и N_t=1, соответственно, начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 127 или "01111111" в двоичном представлении, а начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 255-127=128 или "10000000" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, в начальный момент времени t=0 значение Q равно десятичному значению 127 или "01111111" в двоичном представлении.

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

Если длина очередной части двоичной информационной последовательности равна n=1, то интервал кодирования разделяют на значения подинтервала нулевых символов D₀ и подинтервала единичных символов D₁ один раз, если n=2, то разделение в соответствии с очередной частью двоичной информационной последовательности выполняют итеративно 2 раза и т.д. Например, первая часть ИП имеет длину n=3 бит и вид "000". Сначала интервал кодирования (в данный момент начальный интервал кодирования) от 0 до 255 разделяют на подинтервал нулевых символов от нижней границы интервала кодирования L=0 до значения Q=127 исключительно, а подинтервал единичных символов простирается от значения Q=127 включительно до верхней границы интервала кодирования арифметического кодирования Н=255, исключительно. Далее при n>1 в зависимости от первого бита а₁ очередной части ИП выбирают текущий интервал кодирования: если первый бит а₁ очередной части ИП имеет нулевое значение, то текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, если первый бит а₁ очередной части ИП имеет единичное значение, то текущий интервал кодирования становится равным текущему подинтервалу единичных символов. Текущий интервал кодирования I повторно разделяют на текущий подинтервал нулевых символов длиною D₀=I×р₀, и текущий подинтервал единичных символов длиною D₁=I-D₀ и т.д.

Например, для первой части ИП вида "000" в зависимости от первого бита а₁=0 текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, в пределах от L=0 до значения Q=127. Затем текущий интервал кодирования I разделяют на текущий подинтервал нулевых символов D₀ длиною D₀=64 и подинтервал единичных символов D₁ длиною D₁=63. Текущее значение Q стало равным Q=64. В зависимости от второго бита а₂=0 первой части ИП текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, в пределах от L=0 до значения Q=64.

В соответствии с очередной частью двоичной информационной последовательности и очередной размерностью алфавита кодирования 2ⁿ, где n=3, в третий раз текущий интервал кодирования I разделяют на текущий подинтервал нулевых символов D₀ длиною D₀=I×р₀=64×1/2=32 и текущий подинтервал единичных символов D₁ длиною D₁=I-D₀=64-32=32. Текущее значение Q стало равным Q=32 или "0010 0000" в двоичном представлении, текущее значение нижней границы интервала кодирования L=0 и текущее значение верхней границы интервала кодирования Н=64 или "0100 0000" в двоичном представлении, как показано во второй строке фиг. 5, обозначенной Формирование модели для первой части ИП (Форм, модели для 1-ой части ИП).

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

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

Если символ а_n очередной части ИП является нулевым двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала нулевых символов D₀, и текущее нижнее значение интервала кодирования L устанавливают равным текущему нижнему значению интервала кодирования, записанному в первый регистр кодирования, а текущее верхнее значение интервала кодирования Н устанавливают равным текущему значению Q, записанному во второй регистр кодирования. А при поступлении на вход арифметического кодирования очередной части двоичной информационной последовательности, символ а_n которой является единичным двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала единичных символов D₁, и текущее нижнее значение интервала кодирования L устанавливают равным текущему значению Q, записанному во второй регистр кодирования, а текущее верхнее значение интервала кодирования H устанавливают равным текущему верхнему значению интервала кодирования, записанному в первый регистр кодирования.

Например, при поступлении на вход арифметического кодирования первой части двоичной информационной последовательности, символ а_n которой (третий по счету) является нулевым двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала нулевых символов D₀, и текущее нижнее значение интервала кодирования L устанавливают равным текущему нижнему значению интервала кодирования L=0, а текущее верхнее значение интервала кодирования H устанавливают равным текущему значению Q=32, как показано в третьей строке фиг. 5 в момент времени t=1 при кодировании первой части двоичной информационной последовательности (t=1: код. 1-ой части ИП).

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

Например, как показано на фиг. 5 в третьей строке, после кодирования первой части двоичной информационной последовательности двоичное представление текущего нижнего значения интервала кодирования L равно "0000 0000", а двоичное представление текущего верхнего значения интервала кодирования Я равно "0010 0000". Выявлено совпадение самого левого бита этих двоичных представлений и самый левый бит двоичных представлений значений L и H считывают в качестве очередного закодированного бита кодированной последовательности (Зак. сим.), как показано в правом столбце на фиг. 5. Считанный бит удаляют из двоичных представлений, которые уменьшаются до длины 7 бит вида "000 0000" для L и "010 0000" для H, соответственно. Двоичные символы двоичных представлений значений L и H сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L и Н в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, наприме