СПОСОБ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ
METHOD FOR ARITHMETIC ENCODING AND DECODING

Заявленное техническое решение относится к области электросвязи и информационных технологий, а именно к технике сжатия и последующего восстановления избыточной двоичной информации.
Заявленное изобретение может быть использовано для сжатия избыточной двоичной информации для ее передачи с меньшей скоростью по каналам передачи и хранения в устройствах памяти с меньшей емкостью.
Известен способ арифметического кодирования и декодирования информационных последовательностей, описанный, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. В данном аналоге на передающей стороне от источника информационной последовательности принимают очередную информационную последовательность, устанавливают начальные значения вероятности кодирования нулевого символа и единичного символа, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередного бита очередной информационной последовательности, уточняют текущие значения вероятности кодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных битов очередной информационной последовательности, передают очередную кодированную последовательность на приемную сторону, на приемной стороне устанавливают начальные значения вероятности декодирования нулевого символа и единичного символа, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, выполняют арифметическое декодирование очередного бита очередной принятой последовательности в очередные биты очередной восстановленной информационной последовательности, уточняют текущие значения вероятности декодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных бит очередной принятой последовательности, передают получателю очередную восстановленную информационную последовательность.
Недостатком указанного аналога является кодирование избыточных информационных последовательностей только с использованием усредненных значений вероятности кодирования нулевого символа и единичного символа среди закодированных битов, что для информационных последовательностей с существенными корреляционными зависимостями приводит к неэффективному использованию пропускной способности канала передачи, вызванному неполным удалением избыточности в сжимаемых последовательностях.
Известен также способ арифметического кодирования и декодирования спектральных коэффициентов по патенту РФ 2565501 МПК Н03М 7/40 (2006.01) от 01.10.2010. Данный способ включает арифметическое кодирование текущего спектрального коэффициента с использованием предыдущих спектральных коэффициентов, причем упомянутые предыдущие спектральные коэффициенты уже закодированы, упомянутые предыдущие спектральные коэффициенты и упомянутый текущий спектральный коэффициент содержатся в одном или более квантованных спектрах, которые являются результатом квантования результата частотно-временного преобразования значений дискретизации видео-, аудио- или голосовых сигналов, и содержит этапы, на которых:
- обрабатывают предыдущие спектральные коэффициенты;
- используют обработанные предыдущие спектральные коэффициенты для определения класса контекста из по меньшей мере двух различных классов контекста, причем сумму квантованных абсолютных значений предыдущих спектральных коэффициентов используют для определения класса контекста;
- используют определенный класс контекста и отображение из по меньшей мере двух различных классов контекста по меньшей мере в две различных функции плотности вероятности для определения одной из функций плотности вероятности;
- выполняют арифметическое кодирование текущего спектрального коэффициента на основании определенной функции плотности вероятности, причем упомянутая обработка предыдущих спектральных коэффициентов содержит неравномерное квантование абсолютных значений предыдущих спектральных коэффициентов для использования при определении класса контекста.
Недостатками указанного аналога являются сужение области использования арифметического кодирования и декодирования только для источников видео, аудио или речевого сигнала, которые должны предварительно обрабатываться методами частотного преобразования с формированием спектральных коэффициентов, а также сложность достаточно точного определения типа функции плотности вероятности кодируемых спектральных коэффициентов, что приводит к снижению достигаемого коэффициента сжатия кодируемых сигналов.
Наиболее близким по своей технической сущности к заявленному способу арифметического кодирования и декодирования является способ совместного арифметического и помехоустойчивого кодирования и декодирования по патенту РФ 2611022 МПК Н04М 13/00 (2006.01) от 28.01.2016. Способ - прототип арифметического кодирования и декодирования заключается в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информации принимают очередную часть информационной последовательности (ИП) длиной k>2 бит, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выбирают проверочные символы длиной r≥1 бит, для чего для каждого проверочного символа выделяют среди текущего подинтервала кодирования нулевого символа и текущего подинтервала кодирования единичного символа текущий подинтервал, включающий середину начального интервала арифметического кодирования, и устанавливают проверочным символом такой символ, который соответствует выделенному текущему подинтервалу, выбранные проверочные символы записывают вместе с очередной частью информационной последовательности в очередную часть помехоустойчивой последовательности, выполняют арифметическое кодирование очередной части помехоустойчивой последовательности в очередную часть кодированной последовательности, передают очередную часть кодированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне получают очередную часть принятой последовательности, которую запоминают, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют в очередные части декодированной последовательности, из которых выделяют очередные части восстановленной информационной последовательности и декодированные проверочные символы, делают вывод об отсутствии ошибок передачи, если текущий подинтервал декодирования каждого из декодированных проверочных символов включает середину начального интервала арифметического кодирования, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, передают получателю очередную часть восстановленной информационной последовательности, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части принятой последовательности.
Способ-прототип арифметического кодирования и декодирования обеспечивает возможность сжатия на передающей стороне и восстановление на приемной стороне сжатой избыточной информационной последовательности, избыточность которой зависит от равномерно распределенных предыдущих закодированных двоичных символов данной последовательности.
Однако, недостатком ближайшего аналога (прототипа) является необходимость использования высокой скорости передачи по каналу передачи кодированной последовательности или большей емкости устройств ее запоминания при арифметическом кодировании и декодировании двоичных информационных последовательностей с неравномерной зависимостью от предшествующих битов, и при изменении характера этой зависимости от одной информационной последовательности к другой.
Техническим результатом заявляемого технического решения является арифметическое кодирование и декодирование избыточной двоичной информационной последовательности, обеспечивающее уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.
Указанный технический результат в заявляемом способе арифметического и кодирования и декодирования, достигается тем, что в известном способе арифметического кодирования и декодирования, заключающимся в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информационной последовательности принимают очередную информационную последовательность длиной k>2 бит, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование последовательности, и выполняют на передающей стороне перечисленные действия до исчерпания очередных бит очередной информационной последовательности, передают очередную кодированную последовательность на приемную сторону, на приемной стороне получают очередную принятую последовательность, которую запоминают, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, выполняют арифметическое декодирование очередных бит очередной принятой последовательности в очередной бит очередной последовательности, выполняют перечисленные действия на приемной стороне до исчерпания очередных бит очередной принятой последовательности, передают получателю очередную восстановленную информационную последовательность, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные принятые последовательности, дополнительно предварительно для передающей стороны и приемной стороны выбирают начальную двоичную последовательность длиной n>1 бит, на передающей стороне после получения очередной информационной последовательности вычисляют значения условной вероятности появления ее очередного бита, включая предварительно выбранную начальную двоичную последовательность, от предыдущих битов, предшествующих очередному на d, где d=1, 2, …, k-1, позиций, выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной информационной последовательности, устанавливают текущие значения условной вероятности кодирования нулевого символа и единичного символа соответствующими выбранным значениям вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования, разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условной вероятности кодирования нулевого символа и единичного символа, выполняют арифметическое кодирование очередного бита очередной информационной последовательности, с учетом предварительно выбранной начальной двоичной последовательности, в зависимости от предшествующих битов с текущими значениями условной вероятности, повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа и выполняют последующие действия до исчерпания очередных битов очередной информационной последовательности, передают m выбранных значений условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования на приемную сторону, на приемной стороне получают принятые значения условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования, которые запоминают, устанавливают текущие значения условной вероятности декодирования нулевого символа и единичного символа соответствующими принятым значениям условной вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования, разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в зависимости от текущих значений условной вероятности декодирования нулевого символа и единичного символа, выполняют арифметическое декодирование очередных бит очередной принятой последовательности в очередной бит очередной восстановленной информационной последовательности, с учетом предварительно выбранной начальной двоичной последовательности, в зависимости от предшествующих битов, с текущими значениями условной вероятности декодирования нулевого символа и единичного символа.
Указанная новая совокупность существенных признаков за счет определения наиболее значимых зависимостей очередного бита информационной последовательности от предыдущих ее битов, и арифметического кодирования очередного бита очередной информационной последовательности в зависимости от выявленных зависимостей позволяет увеличить коэффициент сжатия избыточной двоичной информационной последовательности, что обеспечивает уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.
Заявленный способ поясняется чертежами, на которых показаны:
- на фиг. 1 - система арифметического кодирования и декодирования;
- на фиг. 2 - алгоритм арифметического кодирования на передающей стороне;
- на фиг. 3 - временные диаграммы арифметического кодирования;
-на фиг. 4 - таблица состояний арифметического кодирования первых 18 битов информационной последовательности;
- на фиг. 5 - таблица наибольших значений условной вероятности появления очередного бита, равного нулевому значению, данной очередной ИП от m=8 комбинаций с наибольшими значениями условной вероятности;
- на фиг. 6 - алгоритм арифметического декодирования на приемной стороне;
- на фиг. 7 - таблица состояний арифметического декодирования первых 14 битов принятой последовательности;
Реализация заявленного способа представлена на примере системы - система арифметического кодирования и декодирования, показанной на фиг. 1. На передающей стороне при получении от отправителя очередной информационной последовательности в блоке вычисления условной вероятности 1 вычисляют значения условной вероятности появления очередного бита очередной информационной последовательности от различных сочетаний предшествующих битов, на основе которых в блоке выбора значений 2 выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной информационной последовательности, которые с выхода блока выбора значений 2 поступают в формирователь модели кодирования 3, устанавливая для очередной информационной последовательности начальные значения условных вероятностей кодирования нулевого символа и единичного символа в зависимости от предыдущих закодированных двоичных символов очередной информационной последовательности. На основе полученных с выхода формирователя модели кодирования 3 значений условной вероятности в арифметическом кодере 4 разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, и выполняют арифметическое кодирование очередного бита очередной информационной последовательности. По результатам арифметического кодирования очередного бита в формирователе модели кодирования 3 уточняются текущие значения условных вероятностей кодирования. По завершению кодирования очередной информационной последовательности кодированная последовательность через канал передачи 5 передается на приемную сторону вместе с выбранными в блоке 2 значениями условной вероятности и соответствующих им номеров позиций предшествования.
На приемной стороне в формирователе модели декодирования 6 на основе принятых значений условной вероятности и соответствующих им номеров позиций предшествования устанавливают для декодирования очередной принятой последовательности начальные значения условной вероятности декодирования нулевого символа и единичного символа в зависимости от предыдущих декодированных двоичных символов. На основе полученных с выхода формирователя модели декодирования 6 значений условных вероятностей в арифметическом декодере 7 разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, и выполняют арифметическое декодирование очередного принятого бита. По результатам арифметического декодирования очередного принятого бита в формирователе модели декодирования 6 уточняются текущие значения условной вероятности декодирования. По завершению декодирования очередной принятой последовательности очередная восстановленная информационная последовательность передается получателю.
В способе реализуют следующую последовательность действий.
Алгоритм арифметического кодирования на передающей стороне представлен на фигуре 2.
Предварительный выбор для передающей стороны и приемной стороны начальной двоичной последовательности (НДП) длиной n>1 бит заключается, например, в определении одной из наиболее часто встречающихся двоичных последовательностей заданной длины источника информационных последовательностей. Однако, даже если источник ИП является нестационарным и статистические характеристики генерируемых последовательностей меняются во времени, что затрудняет точный выбор НДП, то неточность выбора последовательности в качестве начальной двоичной последовательности, не характерной для текущего состояния источника ИП, не приводит к существенному ухудшению коэффициента сжатия, так как арифметический кодек в силу своей адаптивности быстро приспосабливается к текущим статистическим характеристикам кодируемых последовательностей. Поэтому в качестве начальной двоичной последовательности при неизвестности или непредсказуемости статистических характеристик генерируемых последовательностей также может быть использована, например, случайная последовательность. Примерный вид начальной двоичной последовательности длиной n=5 бита "10010" показан на фиг. 3(a). Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов в виде незаштрихованных импульсов.
Способы предварительной установки на передающей стороне начального интервала арифметического кодирования и на приемной стороне соответствующего ему начального интервала арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования начинается от его начального нижнего значения и заканчивается его начальным верхним значением. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования H[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического кодирования представлен на фиг. 4 при t=0 (первая строка).
На передающей стороне от источника ИП принимают очередную информационную последовательность длиной k>2 бит. Примерный вид первых 18 бит очередной ИП вида "0010 0110 0010 0010 01" показан на фиг. 3(б).
Далее вычисляют значения условной вероятности появления очередного бита очередной ИП, включая предварительно выбранную начальную двоичную последовательность, от предыдущих битов, предшествующих очередному на d, где d=1,2, …, k-l, позиций, а также выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной ИП. Это позволяет для избыточных информационных последовательностей учесть при кодировании их существенную неравномерную зависимость от предшествующих битов, причем характер этой зависимости может меняться от одной информационной последовательности к другой.
a
a
a
i
i
i
Для этого последовательно для всех битов очередной ИП, начиная с ее первого бита, определяют значения условной вероятности появления очередного бита очередной ИП от различных комбинаций предшествующих ему битов. Например, в общем случае последовательно для всех битов очередной ИП, начиная с первого бита, определяют значения условной вероятности появления очередного бита очередной ИП от одного предшествующего бита , отстоящего от него на одну, две, три и так далее позиций, не более k-1. В результате этого определяют не более k-1 значений того, что очередной бит очередной ИП примет нулевое значение, если предшествующий бит , отстоящий от него на i=1, 2, …, k-1 позиций, имеет нулевое значение. Соответственно, значение условной вероятности того, что очередной бит очередной ИП примет единичное значение, если предшествующий бит , отстоящий от него на i=1, 2, …, k-1 позиций, имеет нулевое значение, равно единица минус значение условной вероятности нулевого значения очередного бита очередной ИП при нулевом значении соответствующего предшествующего бита.
a
a
i
j
Также определяют значения условной вероятности появления очередного бита очередной ИП от двух предшествующих битов  и , отстоящих от него на i=1, 2, …, k-1 и j=1, 2, …, k-1 позиций, от трех предшествующих битов и так далее.
Из полученных значений условной вероятности появления очередного бита очередной ИП от всех комбинаций предшествующих битов выбирают 2≤m<<k наибольших значений условной вероятности появления очередного бита очередной ИП. Для этого перечисляют все полученные значения условной вероятности в порядке убывания их значений и первые m значений выбирают как наибольшие значения условной вероятности появления очередного бита очередной ИП.
Для обеспечения практической реализуемости арифметического кодирования число m выбираемых наибольших значений должно быть существенно меньше длины к кодируемых информационных последовательностей, где длина k может быть сотни и тысячи бит, поэтому целесообразно выбирать число m не более 8…10. На практике вполне допустимо определить значения условной вероятности появления очередного бита очередной ИП от одиночных предшествующих битов, и затем выбирать 2≤m<<k наибольших значений условной вероятности от комбинаций предшествующих битов, среди которых использовать только выбранные одиночные предшествующие биты с наибольшими значениями условной вероятности появления очередного бита очередной ИП от одиночных предшествующих битов.
В подавляющем большинстве источников информационных последовательностей корреляционные зависимости приблизительно экспоненциально ослабевают по мере удаления от очередного бита ИП, как описано, например, в книге Д. Прокис "Цифровая связь". - М., Радио и связь, 2000. Это позволяет на практике существенно уменьшить число перебираемых комбинаций предшествующих битов и ограничить число d не более десятков. Соответственно, это позволяет без существенной потери эффективности предлагаемого арифметического кодирования уменьшить число m выбираемых наибольших значений, а также позволяет ограничить длину n начальной двоичной последовательности не более десятков битов.
Например, для очередной ИП длиной k=1028 бита определение значений условной вероятности появления очередного бита очередной ИП, включая предварительно выбранную начальную двоичную последовательность, было ограничено комбинациями предшествующих ему битов, отстоящих от него не более чем на d=5 позиций. При этом используют, например, случайно выбранную начальную двоичную последовательность длиной n=5 бит вида "10010", представленную на фиг. 3(a). На фиг. 3(в) показано, что НДП записывают перед очередной ИП по порядку следования битов. Например, для первого по счету (i=1) очередного бита очередной ИП, имеющего нулевое значение, первый предшествующий ему (i-1)-ый бит имеет нулевое значение, второй предшествующий ему (i-2)-ый бит имеет единичное значение, третий предшествующий ему (i-3)-ый бит имеет нулевое значение и т.д. Для данной очередной ИП выявлено, что очередной бит данной очередной ИП наиболее зависит от предшествующих битов, отстоящих от него на одну, три и четыре позиции. Множество из различных комбинаций данных трех предшествующих битов составляет 8 комбинаций. На фиг. 5 представлены m=8 наибольших значений условной вероятности появления очередного бита, равного нулевому значению, данной очередной ИП от m=8 комбинаций с наибольшими значениями условной вероятности. Для удобства кодирования комбинации предшествующих битов записаны в порядке i-3, i-4), начиная слева с бита выбранной комбинации наибольших значений.
Для каждой очередной ИП длиной k=1028 бита насчитывают 1028 реализаций выбранных m=8 комбинаций наибольших значений. Комбинация (i-1=0, i-3=0, i-4=0) выпала всего 252 раза, что обозначают как число появлений этой комбинации на момент времени t=0 вида N[0]/000=252, при этом при выпадении этой комбинации 180 раз очередной бит данной очередной ИП принимал нулевое значение (N0[0]/000=180), и 72 раза очередной бит данной очередной ИП принимал единичное значение (N1[0]/000=72). В соответствии с теорией вероятности по формуле вида р0[0]/000=N0[0]/000/N[0]/000=180/252=0,714 условная вероятность появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) равна 0,714. Соответственно, условная вероятность появления очередного бита данной очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) равна 0,286.
Комбинация (i-1=0, i-3=0, i-4=1) выпала всего 161 раз (N[0]/001=161), при этом при выпадении этой комбинации 90 раз очередной бит данной очередной ИП принимал нулевое значение (N0[0]/001=90), и 71 раз очередной бит данной очередной ИП принимал единичное значение (N1[0]/001=71). Условная вероятность появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (0, 0, 1) равна 0,559, и т.д., как показано на фиг. 5.
Значения условной вероятности появления очередного бита данной очередной ИП от различных комбинаций предшествующих битов существенно различаются. Для большинства выбранных комбинаций условная вероятность появления очередного нулевого бита больше условной вероятности появления очередного единичного бита, но для некоторых комбинаций, например, комбинации предшествующих битов вида (i-1=1, i-3=1, i-4=0), это соотношение является противоположным.
Данный пример иллюстрирует факт, что корреляционные связи информационных последовательностей различных источников имеют сложный характер и меняются во времени, что не учитывается в известных способах арифметического кодирования.
Далее устанавливают текущие значения условной вероятности кодирования нулевого символа и единичного символа соответствующими выбранным значениям вероятности появления очередного бита очередной ИП с соответствующими номерами позиций предшествования. В начальный момент времени t=0 перед кодированием первого по счету очередного бита очередной ИП текущие значения условной вероятности кодирования нулевого символа и единичного символа устанавливают равными т выбранным наибольшим значениям условной вероятности появления очередного бита очередной ИП. Как показано, например, на фиг. 4, условная вероятности появления очередного бита очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) установлена равной р0/000=0,714, условная вероятности появления очередного бита очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=1) - равной р0/001=0,559, и т.д.
Разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условной вероятности кодирования нулевого символа и единичного символа заключается в следующем.
,
Для каждой из m комбинаций предшествующих битов вида  с выбранными наибольшими значениями условной вероятности появления очередного бита очередной ИП длину текущего интервала арифметического кодирования I[i-1], равную I[i-1]=H[i-1]-L[i-1], разделяют на текущее значение подинтервала нулевого символа D0[i-1] и текущее значение подинтервала единичного символа D1[i-1]длины которых прямо пропорциональны текущим значениям условной вероятности кодируемых нулевых символов  и единичных символов  соответственно.
Длину текущего подинтервала нулевых символов  определяют по формуле вида  а длину текущего подинтервала единичных символов  определяют по формуле вида
Текущее значение условной вероятности кодируемых нулевых символов  вычисляют по формуле вида  а текущее значение условной вероятности кодируемых единичных символов  вычисляют по формуле вида  где  - число подсчитанных появлений комбинации  до кодирования i-го очередного бита очередной ИП,  - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ИП принял нулевое значение, а  - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ИП принял единичное значение.
Например, в начальный момент времени t=0 длина текущего подинтервала нулевого символа D0[0]/000 относительно комбинации вида (0, 0, 0) равна D0[0]/000=256*180/252=256*0,714=183, десятичному значению 183 соответствует двоичное значение 1011 0111, а длина текущего подинтервала единичного символа D1[0]/000 равна 256-183=73. Подинтервал единичного символа расположен сверху подинтервала нулевого символа, как показано, например, на фиг. 4. Верхнюю границу подинтервала нулевого символа обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования включительно до значения Q исключительно, а подинтервал единичного символа простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, начальное значение Q имеет десятичное значение 183 относительно комбинации вида (0,0,0), как показано на фиг. 4 в первой строке при t=0. Для того, чтобы было ясно, относительно какой комбинации предшествующих битов определено значение Q, соответствующее значение условной вероятности кодируемых нулевых символов в строке на фиг. 4 выделено жирным шрифтом.
Точно так же разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в зависимости от текущих значений условных вероятностей кодирования нулевого символа и единичного символа относительно всех других комбинаций предшествующих битов, как показано на фиг. 4.
Далее выполняют арифметическое кодирование очередного бита очередной информационной последовательности, в зависимости от предшествующих битов с текущими значениями условной вероятности. Для этого считывают очередной бит очередной ИП и относительно него определяют предшествующие биты. Например, для первого по счету (i=1) очередного бита данной очередной ИП, имеющего нулевое значение, с учетом начальной двоичной последовательности, показанной на фиг. 3(в), определяют предшествующие биты в позициях (i-1, i-3, i-4). В данном случае предшествующие биты составляют комбинацию (0, 0, 0), относительно которой в первой строке фиг. 4 указано разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. Для того, чтобы указать относительно какой комбинации предшествующих битов выполняют арифметическое кодирование очередного бита, на фиг. 4 ее текущее значение условной вероятности выделяют жирным шрифтом. С момента установления зависимости очередного бита очередной ИП от конкретной комбинации предшествующих битов с текущими значениями условной вероятности, выполнение собственно действий арифметического кодирования очередного бита не отличается от действий арифметического кодирования очередного бита без учета условной вероятности, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Действия арифметического кодирования очередных битов заключаются в последовательном сжатии очередных битов очередной ИП в очередную кодированную последовательность (КП) в соответствии с текущими значениями подинтервалов кодирования.
При поступлении на вход арифметического кодирования очередного бита очередной ИП, являющегося единичным двоичным символом, текущий интервал кодирования этого бита устанавливают равным предыдущему подинтервалу кодирования единичного символа, а при поступлении на вход арифметического кодирования нулевого двоичного символа, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу нулевого символа. Например, при поступлении на вход арифметического кодирования первого бита очередной ИП, являющегося нулевым двоичным символом, нижнее значение интервала кодирования первого символа L[1] устанавливают равным значению L[0], равному, в данном примере, 0, а верхнее значение интервала кодирования первого символа арифметического кодирования устанавливают равным начальному значению Q [0], равному, например, 183, как показано на фиг. 4 при t=1.
Далее самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения, например, вида 0000 0000 и 1011 0111, соответственно, как показано на фиг. 4 при t=1. При их несовпадении переходят к арифметическому кодированию следующего символа.
После выполнения арифметического кодирования каждого очередного символа очередной ИП повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа. Для этого уточняют число появлений комбинаций предшествующих битов. Например, после кодирования первого бита очередной ИП число появлений комбинации (i-1=0, i-3=0, i-4=0) увеличилось на единицу и составило N[1]/000=253, при этом при выпадении этой комбинации 181 раз очередной бит данной очередной ИП принимал нулевое значение (N0[1]/000=181), а число появлений этой комбинации, когда очередной бит очередной ИП принимал единичное значение осталось неизменным (N1[1]/000=72). Поэтому в момент времени t=1 текущая условная вероятности появления очередного бита данной очередной ИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила р0[1]/000=N0[l]/000/N[1]/000=181/253=0,715, как показано во второй строке сверху на фиг. 4 при t=1. Соответственно, текущая условная вероятности появления очередного бита данной очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила 0,285.
Для остальных комбинаций предшествующих битов число их появлений не изменилось, поэтому не изменилась их текущая условная вероятности появления очередного бита очередной ИП, равного нулевому значению, и соответственно, единичному значению.
Для кодирования очередного (второго по счету) бита очередной ИП в соответствии с уточненными текущими значениями условной вероятности кодирования нулевого символа и единичного символа повторно разделяют текущий интервал арифметического кодирования, простирающийся от 0 до 183, на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа для каждой комбинации предшествующих битов.
При поступлении на вход арифметического кодирования второго по счету очередного бита (i=2) очередной ИП, являющегося нулевым двоичным символом, снова определяют предшествующие ему биты в позициях (i-1, i-3, i-4). В данном случае предшествующие биты составляют комбинацию (0, 1, 0), относительно которой согласно фиг. 5 условная вероятность очередного нулевого символа очередной ИП равна 0,576 и относительно которой на фиг. 4 во второй строке указано разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, десятичное значение Q [1] составило 106.
При кодировании второго бита очередной ИП, являющегося нулевым двоичным символом, нижнее значение интервала кодирования L[2] устанавливают равным значению L[1], равному, например, 0, а верхнее значение интервала кодирования H[2] устанавливают равным текущему значению Q [1], равному десятичному числу 106, или двоичному числу 0110 1010, как показано на фиг. 4 при t=2.
Самый левый бит двоичного представления значения L[2] сравнивают с самым левым битом двоичного представления значения Н[2], например, вида 0000 0000 и 0110 1010, соответственно, как показано на фиг. 4 при t=2. При их совпадении значение самого левого бита двоичных представлений значений L[2] и Н[2] считывают в качестве очередного бита кодированной последовательности (Зак. бит на фиг. 4). Например, при арифметическом кодировании второго по счету бита очередной ИП первым из очередных битов очередной КП является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 4, третья строка сверху. Считанный бит удаляют из двоичных представлений значений L[2] и Н[2], которые уменьшаются до длины 7 бит вида 0000 0000 и 1101 1010, соответственно. Двоичные символы двоичных представлений значений L[2] и сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Например, двоичные представления значений L[2] и Н[2] приобретают вид 0000 0000 и 1101 0100, соответственно. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[2] и Н[2] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.
После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений снова считывают в качестве следующего бита кодированной последовательности, иначе повторно вычисляют текущие значения условной вероятности кодирования нулевого символа и единичного символа.
Для этого заново уточняют число появлений комбинаций предшествующих битов. Например, после кодирования второго бита очередной ИП число появлений комбинации (i-1=0, i-3=1, i-4=0) увеличилось на единицу и составило N[1]/010=138, при этом при выпадении этой комбинации 80 раз очередной бит данной очередной ИП принимал нулевое значение (N0]/010=80), а число появлений этой комбинации, когда очередной бит очередной ИП принимал единичное значение, осталось неизменным (N1[1]/010=58). Поэтому пересчитывают значение р0[1]/010=N0[l]/010/N[1]/010=80/138=0,579, как показано в третьей строке сверху на фиг. 4. Соответственно, текущая условная вероятность появления очередного бита очередной ИП, равного единичному значению, от комбинации предшествующих битов вида (i-1=0, i-3=1, i-4=0) составила 0,421.
Далее арифметически кодируют очередной двоичный символ ИП и выполняют на передающей стороне перечисленные действия до исчерпания двоичных символов данной информационной последовательности.
Примерный вид арифметического кодирования первых 18 очередных битов очередной ИП вида "0010 0110 0010 0010 01" в первые 14 бит очередной кодированной последовательности вида "0100 1010 0111 10" показан на фиг. 3(г). Например, при кодировании первого, третьего, четвертого и пятого битов очередной ИП не было сформировано в явном виде кодированных битов, при кодировании второго бита - сформирован кодированный бит "1", при кодировании шестого бита - сформированы кодированные биты "100" и т.д.
Способы передачи на приемную сторону т выбранных значений условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования и очередной кодированной последовательности известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Выбранные значения условной вероятности появления очередного бита очередной информационной последовательности и соответствующие им номера позиций предшествования показаны на фиг. 5. Например, переданные на приемную сторону m=8 выбранные значения условной вероятности представлены на фиг. 7 при t=0 (первая строка).
На приемной стороне принятую последовательность (ПП) запоминают. Примерный вид первых 14 бит "0100 1010 0111 10" ПП показан на фиг. 3(д).
Предварительно на приемной стороне устанавливают начальный интервал арифметического декодирования. Например, при представлении значений интервала декодирования восемью двоичными символами, начальное нижнее значение интервала декодирования LL в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, а начальное верхнее значение интервала декодирования НН устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического декодирования представлен на фиг. 7 при t=0.
Алгоритм арифметического декодирования на приемной стороне представлен на фиг. 6.
,
На приемной стороне устанавливают текущие значения условной вероятности декодирования нулевого символа и единичного символа соответствующими принятым значениям условной вероятности появления очередного бита очередной информационной последовательности с соответствующими номерами позиций предшествования идентично соответствующим действиям на передающей стороне. Для каждой из m комбинаций предшествующих битов восстановленной информационной последовательности (ВИП) с дописанной в ее начало начальной двоичной последовательности с выбранными наибольшими значениями условной вероятности появления очередного бита очередной ВИП длину текущего интервала декодирования II[i-1], равную II[i-1]=HH[i-1]-LL[i-1] разделяют на текущее значение подинтервала декодирования нулевого символа DD0[i-1] и текущее значение подинтервала декодирования единичного символа DD1[i-1], длины которых прямо пропорциональны текущим значениям условной вероятности декодируемых нулевых символов  и единичных символов  соответственно.
Длину текущего подинтервала нулевых символов  определяют по формуле вида , а длину текущего подинтервала единичных символов  определяют по формуле вида
В каждый очередной момент декодирования текущее значение условной вероятности декодируемых нулевых символов  вычисляют по формуле вида  а текущее значение условной вероятности кодируемых единичных символов  вычисляют по формуле вида  где  - число подсчитанных появлений комбинации  до декодирования i-го очередного бита очередной ВИП,  - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял нулевое значение, а  - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял единичное значение.
Например, в начальный момент времени t=0 длина текущего подинтервала декодирования нулевого символа DD0[0]/000 относительно комбинации вида (0, 0, 0) равна DD0[0]/000=256*180/252=256*0,714=183, а длина текущего подинтервала декодирования единичного символа DD1[0]/000 равна 256-183=73. Верхнюю границу подинтервала декодирования нулевого символа обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования включительно до значения QQ исключительно, а подинтервал декодирования единичного символа простирается от значения QQ включительно до верхней границы интервала декодирования исключительно. Например, начальное значение QQ имеет десятичное значение 183 относительно комбинации вида (0,0,0), как показано на фиг. 7 в первой строке при t=0.
Например, в начальный момент времени декодирования в восстановленной информационной последовательности (в этот момент еще пустой) с дописанной в ее начало начальной двоичной последовательности, как показано на фиг. 3(e), для выбранных m комбинаций предшествующих битов, находящихся на позициях (i-1, i-3, i-4) относительно i-го декодируемого бита (в начальный момент i=0), имеет место комбинация предшествующих битов вида (0, 0, 0). Чтобы было ясно, относительно какой комбинации предшествующих битов определено значение QQ, соответствующее значение условной вероятности декодируемых нулевых символов на фиг. 7 выделено жирным шрифтом. Соответственно, для данной комбинации начальное значение текущего подинтервала декодирования нулевого символа начинается от 0 и заканчивается 183, начальное значение текущего подинтервала декодирования единичного символа начинается от 183 и заканчивается 255, как показано, на фиг. 7 в первой строке.
Разделение текущего интервала декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в зависимости от текущих значений условных вероятностей декодирования нулевого символа и единичного символа относительно всех выбранных комбинаций предшествующих битов, выполняют идентично аналогичному действию на передающей стороне.
Способы арифметического декодирования очередных бит очередной ПП в очередной бит очередной восстановленной информационной последовательности (ВИП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". -М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании очередной ПП в соответствии с текущими значениями подинтервала декодирования нулевого символа и подинтервала декодирования единичного символа.
Примерный вид арифметического декодирования очередных бит очередной принятой последовательности вида "0100 1010 0111 10" в очередные биты очередной ВИП показан на фиг. 7. Для начала декодирования из очередной ПП считывают такое количество первых бит очередной ПП, которое выбрано для представления значений интервала декодирования. Например, из очередной ПП считывают восемь двоичных символов вида "0100 1010", как показано на фиг. 7 в первой строке в графе "Счит". Очередные считанные биты составляют двоичную текущую последовательность (Тек. посл.) длиной восемь бит, десятичное значение которой равно 74, как показано на фиг. 7 в первой строке в графе "Тек. посл".
Для декодирования первого бита очередной ПП десятичное значение текущей последовательности сравнивают с границами текущего подинтервала декодирования нулевого символа и границами текущего подинтервала декодирования единичного символа, находящимися, например, в пределах от 0 до 183, и от 183 до 255, соответственно, как показано на фиг. 7 в первой строке при t=0. Если десятичное значение текущей последовательности оказалось в пределах текущего подинтервала декодирования нулевого символа, то очередной декодируемый бит имеет нулевое значение, а если в пределах текущего подинтервала декодирования единичного символа, то - единичное значение. Например, первый декодируемый бит очередной ВИП принял нулевое значение, решение о значении декодируемого бита указывается в графе "Дек. бит" фиг. 7.
Следующие границы текущего интервала декодирования устанавливают соответствующими границам выбранного подинтервала декодирования. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования LL равным значению LL0[0], например, LL0[1]=0, а верхнее значение интервала декодирования НН - равным значению QQ[0], например, НН[1]=183, как показано на фиг. 7 во второй строке при t=1.
Точно также как выполняется нормализация на передающей стороне, после каждого изменения состояния арифметического декодирования самый левый бит двоичного представления значения LL интервала декодирования сравнивают с самым левым битом двоичного представления значения НН, например, при f=1 значение LL вида "0000 0000" и значение НН вида "1011 0111", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и НН удаляют и символы двоичных представлений значений LL и НН сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. При каждой нормализации в процессе декодирования из очередной ПП считывают очередной бит, из двоичной текущей последовательности удаляют самый левый бит ее двоичного представления, двоичное представление сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают считанный из ПП очередной бит. Например, при выполнении нормализации после декодирования второго бита в текущую последовательность считан нулевой бит и текущая последовательность приняла десятичное значение 148, как показано на фиг. 7.
После декодирования очередного бита очередной ВИП уточняют текущую условную вероятность появления очередного бита данной очередной ВИП, равного нулевому значению, от выпавшей комбинации предшествующих битов. Идентично соответствующей операции на передающей стороне, в момент времени t=1 текущая условная вероятность появления очередного бита данной очередной ВИП, равного нулевому значению, от комбинации предшествующих битов вида (i-1=0, i-3=0, i-4=0) составила рр0[1]/000=NN0[1]/000/NN[1]/000=181/253=0,715, где NN[i]/000 - число подсчитанных появлений комбинации (0,0,0) до декодирования i-го очередного бита очередной ВИП, a NN0[i]/000 - число подсчитанных появлений этой комбинации, при которых очередной бит очередной ВИП принял нулевое значение.
Описанные действия выполняют до исчерпания очередных бит очередной ПП. Например, из первых бит очередной ПП вида "0100 1010 0111 10" декодированы первые восемь бит очередной ВИП вида "0010 0110", как показано на фиг. 3(e).
Очередную ВИП передают получателю, и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные принятые последовательности.
Проверка теоретических предпосылок заявленного способа арифметического кодирования и декодирования проверялась путем его аналитических исследований.
Было выполнено арифметическое кодирование и декодирование различных избыточных последовательностей с различными коррелирующими зависимостями с использованием способа-прототипа и предлагаемого способа. Выявлено, что чем выше условная зависимость текущих битов информационной последовательности от предыдущих ее битов, тем больший коэффициент их сжатия достигается при использовании предлагаемого способа по сравнению со способом-прототипом.
Проведенные исследования подтверждают, что при использовании предлагаемого способа арифметического кодирования и декодирования избыточной двоичной информационной последовательности обеспечивается уменьшение скорости передачи по каналу передачи кодированной последовательности или уменьшение емкости устройств ее запоминания.