Способ аутентификации электронного изображения

Способ аутентификации электронного изображения

Иллюстрации

Показать все

Реферат

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

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

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

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

- невозможность проверки подлинности части аутентифицированного с использованием имитовставки ЭИ;

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

Известны также способы аутентификации ЭИ на основе вычисления и встраивания цифровых водяных знаков (ЦВЗ) в электронное изображение. Эти способы относятся к стеганографическим способам контроля подлинности ЭИ и описаны, например, в способе аутентификации ЭИ по патенту США 7313696 МПК H04L 9/00 (2006.01) от 25.12.07. Данный способ аутентификации ЭИ заключается в предварительном формировании для отправителя и получателя ДП СК, криптографической функции хэширования и криптографической функции шифрования. У отправителя разделяют ЭИ на М≥2 блоков каждый размером n₁×n₂ пикселов, где n₁≥2 и n₂≥2, над каждым m-ым, где m=1,2,…,М, блоком ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и преобразуют в ДП вейвлет коэффициентов m-го блока ЭИ, которые преобразуют в N≥2 УДП вейвлет коэффициентов m-го блока ЭИ. Из K, где K=N-1, УДП ВК m-го блока ЭИ вычисляют его хэширующую последовательность с помощью предварительно сформированной криптографической функции хэширования. Затем из хэширующей последовательности m-го блока ЭИ вычисляют его ДП цифрового водяного знака с помощью предварительно сформированных криптографической функции шифрования и ДП СК. Аутентифицируют m-й блок ЭИ, для чего встраивают ДП ЦВЗ m-го блока ЭИ в N-ую УДП ВК этого блока ЭИ заменой N-ой УДП ВК этого блока ЭИ на его ДП ЦВЗ.

Полученные УДП ВК с встроенной ДП ЦВЗ m-го блока ЭИ кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, включающие маркеры, причем действия по аутентификации у отправителя блоков ЭИ повторяют до завершения их поступления.

Передают аутентифицированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков, которые разделяют на кодированные последовательности m-го принятого блока ЭИ, декодируют их и выделяют N УДП ВК m-го принятого блока ЭИ. Выделяют из N-ой УДП ВК m-го принятого блока ЭИ ДП ЦВЗ m-го принятого блока ЭИ и запоминают ее.

Из К УДП ВК m-го принятого блока ЭИ вычисляют его хэширующую последовательность с помощью предварительно сформированной криптографической функции хэширования. Затем из хэширующей последовательности m-го принятого блока ЭИ вычисляют его ДП ЦВЗ с помощью предварительно сформированных криптографической функции шифрования и ДП СК и сравнивают ее с ранее выделенной и запомненной ДП ЦВЗ m-го принятого блока ЭИ. При их совпадении m-ый принятый блок ЭИ считают подлинным. Повторяют действия по проверке подлинности принятых блоков ЭИ до завершения их приема. Принятое ЭИ считают подлинным, если подлинными оказываются М принятых блоков ЭИ.

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

Наиболее близким по своей технической сущности к заявленному способу аутентификации ЭИ является способ аутентификации ЭИ, описанный в международном стандарте защиты ЭИ: Документ ISO/IEC FCD15444-8: Information technology - JPEG2000 image coding system. Part 8. Secure JPEG2000. Женева, 2004, стр. 66-89. Способ - прототип аутентификации ЭИ заключается в предварительном формировании для отправителя и получателя ДП СК и криптографической функции хэширования. У отправителя над ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и разделяют на N≥2 кодовых блоков квантованных вейвлет коэффициентов каждый размером n₁×n₂ коэффициентов, где n₁≥2 и n₂≥2, квантованные вейвлет коэффициенты n-го, где n=1,2,…,N, кодового блока квантованных вейвлет коэффициентов преобразуют в двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока, которые преобразуют в L≥2 упорядоченные двоичные последовательности (УДП) квантованных вейвлет коэффициентов n-го кодового блока, из первых K, где 1≤K≤L, УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием предварительно сформированных криптографической функции хэширования и ДП СК вычисляют ДП цифрового водяного знака (ЦВЗ) n-го кодового блока, которую встраивают в последние Т, где K≤Т≤L, УДП квантованных вейвлет коэффициентов этого же блока, номера которых определяют предварительно сформированной ДП СК, УДП квантованных вейвлет коэффициентов n-го кодового блока, включая УДП вейвлет коэффициентов с встроенной ДП ЦВЗ n-го кодового блока, кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, по окончании арифметического кодирования каждой очередной УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер УДП, а после кодирования L УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер кодового блока, причем действия по аутентификации у отправителя кодовых блоков повторяют до завершения их поступления.

Передают кодированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков, декодируют кодированные последовательности n-го принятого кодового блока с использованием арифметического декодирования и выделяют L УДП квантованных вейвлет коэффициентов n-го принятого кодового блока, из последних Г УДП квантованных вейвлет коэффициентов n-го принятого кодового блока, номера которых определяют предварительно сформированной ДП СК, выделяют ДП ЦВЗ n-го принятого кодового блока, которую запоминают, из первых К УДП квантованных вейвлет коэффициентов n-го принятого кодового блока с использованием предварительно сформированных криптографической функции хэширования и ДП СК вычисляют ДП ЦВЗ n-го принятого кодового блока, которую побитно сравнивают с запомненной выделенной ДП ЦВЗ этого блока, при их совпадении n-ый принятый кодовый блок считают подлинным, повторяют действия по проверке подлинности принятых кодовых блоков до завершения их приема, принятое ЭИ считают подлинным, если подлинными оказываются N принятых кодовых блоков.

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

Недостатком ближайшего аналога (прототипа) является сравнительно небольшая защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ. Данный недостаток обусловлен тем, что при аутентификации в каждый n-ый кодовый блок кодированного ЭИ встраивается двоичная последовательность ЦВЗ длиной b бит. Численно защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ на каждый кодовый блок оценивается вероятностью необнаруживаемой подмены, вычисляемой по формуле Р_необн≈2^-b, как описано, например, в ГОСТ 28147-89 "Алгоритмы криптографической защиты данных". Длину двоичной последовательности ЦВЗ, как правило, выбирают равной b=32 бита, что обеспечивает вероятность необнаруживаемой подмены 2^-32≈10^-9. При необходимости повышения защищенности от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ снижение вероятности необнаруживаемой подмены достигается только путем увеличения длины двоичной последовательность ЦВЗ, что вызывает увеличение длины аутентифицированного ЭИ и требует при его передаче увеличения скорости передачи по каналам передачи или при хранении использования запоминающих устройств большей емкости.

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

Указанный технический результат в заявляемом способе аутентификации ЭИ достигается тем, что в известном способе аутентификации ЭИ, заключающемся в предварительном формировании для отправителя и получателя двоичной последовательности секретного ключа, у отправителя над ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и разделяют на N≥2 кодовых блоков квантованных вейвлет коэффициентов каждый размером n₁×n₂ коэффициентов, где n₁≥2 и n₂≥2, квантованные вейвлет коэффициенты n-го, где n=1,2,…,N, кодового блока квантованных вейвлет коэффициентов преобразуют в двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока, которые преобразуют в L≥2 упорядоченных двоичных последовательностей квантованных вейвлет коэффициентов n-го кодового блока, упорядоченные двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, по окончании арифметического кодирования очередной УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер УДП, а после кодирования L УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер кодового блока, причем действия по аутентификации у отправителя кодовых блоков повторяют до завершения их поступления, передают кодированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков с использованием разделительного маркера каждого кодового блока, декодируют кодированные последовательности n-го принятого кодового блока с использованием арифметического декодирования в L упорядоченных двоичных последовательностей квантованных вейвлет коэффициентов n-го принятого кодового блока, повторяют действия по проверке подлинности принятых кодовых блоков до завершения их приема, принятое ЭИ считают подлинным, если подлинными оказываются N принятых кодовых блоков, дополнительно у отправителя перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования изменяют разрядность представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го кодового блока, разделительный маркер УДП выбирают случайным образом в подинтервале кодирования последнего двоичного символа данной УДП.

У получателя перед декодированием очередной кодированной последовательности n-го принятого кодового блока с использованием арифметического декодирования изменяют разрядность представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК и номером n-го принятого кодового блока, n-ый принятый кодовый блок считают подлинным, если декодировано L×n₁×n₂ его битов.

Указанная новая совокупность действий за счет изменения разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го кодового блока, у отправителя перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования вносит для нарушителя дополнительную неопределенность о длине кодированной последовательности, которая должна быть сформирована в результате арифметического кодирования очередной УДП квантованных вейвлет коэффициентов n-го кодового блока при использовании неизвестного для нарушителя секретного ключа. Тем самым нарушитель без знания ключа не может сформировать из неподлинного электронного изображения кодированное электронное изображение, которое будет признано получателем подлинным. Поэтому указанная новая совокупность действий позволяет повысить защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ.

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

- на фиг. 1 - общая схема аутентификации ЭИ;

- на фиг. 2 - рисунки, поясняющие предварительное формирование ДП СК;

- на фиг. 3 - алгоритм формирования аутентифицированного ЭИ;

- на фиг. 4 - временные диаграммы формирования аутентифицированного n-го кодового блока;

- на фиг. 5 - временные диаграммы кодирования УДП КВК n-го кодового блока с использованием арифметического кодирования в кодированные последовательности этого блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;

- на фиг. 6 - таблица состояний арифметического кодирования УДП КВК n-го кодового блока в кодированные последовательности этого блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;

- на фиг. 7 - временные диаграммы проверки подлинности n-го принятого кодового блока;

- на фиг. 8 - алгоритм проверки подлинности принятого ЭИ;

- на фиг. 9 - временные диаграммы декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;

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

- на фиг. 11 - временные диаграммы декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования без установки разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;

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

Реализация заявленного способа представлена на примере системы аутентификации ЭИ, включающей блок формирования кодированного ЭИ 1 и блок проверки принятого ЭИ 2, которые взаимодействуют через канал передачи 4 (фиг. 1). У отправителя на первый и второй входы блока формирования кодированного ЭИ 1 принимают ЭИ и ДП СК соответственно. С выхода блока формирования кодированного ЭИ 1 кодированное с обеспечением аутентификации ЭИ передают по каналу передачи 4 получателю. Также в канале передачи 4 нарушителем с использованием блока перехвата и навязывания неподлинного ЭИ 3 может осуществляться перехват переданного отправителем кодированного с обеспечением аутентификации ЭИ. Нарушитель пытается модифицировать перехваченное ЭИ в выгодное ему неподлинное ЭИ, которое нарушитель передает получателю по каналу передачи 4. У получателя проверку подлинности принятого ЭИ осуществляют в блоке проверки принятого ЭИ 2 с использованием ДП СК. Результат проверки подлинности принятого ЭИ считывают с выходов блока проверки принятого ЭИ 2 "подлинное ЭИ " и "неподлинное ЭИ ", соответственно.

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

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

Алгоритм формирования аутентифицированного ЭИ представлен на фигуре 3. Аутентифицируемое ЭИ представлено матрицей пикселей электронного изображения размером w₁×w₂ пикселов, где w₁≥2 и w₂≥2. Примерный вид значений яркости пикселей (ЯП) ЭИ, поочередно считанных слева направо строка за строкой сверху вниз, представлен на фигуре 4(a).

Известные способы выполнения над ЭИ вейвлет преобразования описаны, например, в книге S. Lyu, Н. Farid "Steganalysis Using Higher-Order Image Statistics", IEEE Transactions on Information Security and Forensics, vol. 1, pp. 111-119, 2006. Над ЭИ выполняют k - уровневое, где k=1,2,3,…K, а 1≤K≤10, вейвлет преобразование с формированием матрицы коэффициентов вейвлет преобразования ЭИ такого же размера, как и размер исходного ЭИ в пикселях. Матрица коэффициентов вейвлет преобразования ЭИ состоит из матриц горизонтальных, вертикальных, высокочастотных и низкочастотных коэффициентов вейвлет преобразования ЭИ. На фиг. 4(б) показан пример значений низкочастотных коэффициентов (низ. коэф.), вертикальных коэффициентов (вер. коэф.), высокочастотных коэффициентов (выс. коэф.) и горизонтальных коэффициентов (гор. коэф.) первого уровня вейвлет преобразования ЭИ. Видно, что вейвлет коэффициенты ЭИ принимают как положительные, так и отрицательные значения и могут быть нецелочисленными.

Способы квантования полученных в результате преобразования значений ВК ЭИ известны и описаны, например, в книге Я. Ричардсон "Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения". - М.: Техносфера, 2005, стр. 78-80. Значения ВК ЭИ квантуют путем их округления до ближайшего целого значения. Примерный вид квантованных вейвлет коэффициентов (КВК) ЭИ показан на фигуре 4(в).

Способы разделения квантованных вейвлет коэффициентов на N≥2 кодовых блоков каждый размером n₁×n₂ коэффициентов, где n₁≥2 и n₂≥2, известны и описаны, например, в книге Я. Ричардсон "Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения". - М., Техносфера, 2005, стр. 38-40. Из матрицы квантованных вейвлет коэффициентов ЭИ, начиная, например, с ее левого верхнего угла, выделяют матрицу коэффициентов размера n₁ строк и n₂ столбцов, которая образует n-ый, где n=1,2,…,N, кодовый блок, в данном случае первый кодовый блок. Затем справа или снизу от выделенной матрицы коэффициентов выделяют следующую матрицу коэффициентов такого же размера, которая образует следующий кодовый блок и так пока из матрицы квантованных вейвлет коэффициентов ЭИ не выделены все коэффициенты. Размер кодовых блоков выбирают, например, порядка 16×16, 32×32 коэффициентов и т.д., что определяется числом формируемых вейвлет коэффициентов кодового блока. Примерный вид квантованных вейвлет коэффициентов n-го кодового блока представлен на фигуре 4(г).

Способы преобразования квантованные вейвлет коэффициенты n-го кодового блока в их ДП известны и описаны, например, в книге: ISO/IES 15444-1. Information technology - JPEG2000 image coding system. Женева. 2001, стр. 219-222. КВК n-го кодового блока по фиксированному правилу кодирования преобразовывают в ДП КВК этого блока. Оно заключается в преобразовании целочисленного значения каждого КВК n-го кодового блока в двоичную последовательность, в которой каждый последующий бит отличается по информационной значимости в 2 раза, а старший двоичный символ этой двоичной последовательности кодирует знак квантованного вейвлет коэффициента. Положительное значение квантованного вейвлет коэффициента кодируют, например, единичным двоичным символом, а отрицательное значение - нулевым двоичным символом. Например, значение первого КВК n-го кодового блока, равное -8=-(8+0+0+0), преобразовывают в первую ДП КВК этого блока вида 01000, а значение второго КВК этого блока, равное +273=256+16+1, преобразовывают во вторую ДП КВК этого блока вида 1110010001, а значение последнего n₁×n₂-го КВК этого блока, равное +241=128+64+32+16+1, преобразовывают в n₁×n₂-ю ДП КВК этого блока вида 111110001. Примерный вид ДП КВК n-го кодового блока показан на фигуре 4(д).

Способы преобразования двоичных последовательностей КВК n-го кодового блока в L≥2 упорядоченных двоичных последовательностей КВК этого блока известны и описаны, например, в книге В. Воробьев, В. Грибунин "Теория и практика вейвлет-преобразования". - СПб., ВУС, 1999, стр. 159-161. Они заключаются в последовательной записи первых битов всех двоичных последовательностей КВК n-го кодового блока в первую упорядоченную двоичную последовательность КВК этого блока, последовательной записи вторых битов всех двоичных последовательностей КВК n-го кодового блока во вторую УПД КВК этого блока и т.д. Упорядоченность двоичных последовательностей КВК n-го кодового блока заключается в выбранном порядке последовательной записи битов двоичных последовательностей КВК n-го кодового блока ЭИ в УДП КВК этого блока. Число L выбирают как наименьшее целое число, обеспечивающее соотношение вида: значение 2^L-1 должно быть не меньше абсолютной величины наибольшего значения квантованных вейвлет коэффициентов n-го кодового блока с учетом знака. Примерный вид УДП КВК n-го кодового блока показан на фиг. 4(e). Например, первая УДП КВК первого кодового блока имеет вид 0111…1.

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

Считанную двоичную подпоследовательность преобразуют в десятичное число, считая, например, ее левый символ наиболее значимым. Например, при k=6 бит десятичное представление считанной двоичной подпоследовательности принадлежит интервалу значений от 0 до 63. Десятичный номер n-го кодового блока преобразуют в его двоичную последовательность. Считанную двоичную подпоследовательность СК и двоичную последовательность номера n-го кодового блока суммируют, начиная с одноименных младших двоичных битов, по модулю 2. Способы суммирования двух двоичных последовательностей известны и описаны, например, в книге: А. Сикарев, О. Лебедев "Микроэлектронные устройства формирования и обработки сложных сигналов". - М.: Радио и связь, 1983, стр. 107-108 на основе сумматоров по модулю 2. Устанавливают разрядность r представления интервала арифметического кодирования перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования, например, равной сумме десятичного представления суммированной двоичной последовательности и фиксированного числа w>0. Фиксированное число w исключает возможность установки недопустимо малой разрядности представления интервала арифметического кодирования, пусть, например, фиксированное число равно w=3. Например, считанная первая двоичная подпоследовательность имеет вид "001000", как показано на фиг. 2, а ее десятичное представление равно 8. При w=3 разрядность r представления интервала арифметического кодирования перед кодированием первой УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования равна r=11. Разрядность r определяет диапазон возможных значений интервала кодирования арифметического кодирования в пределах от 0 до 2^r-1. При установленной таким образом разрядности r устанавливают начальное нижнее значение интервала кодирования в минимальное значение, равное, например, нулю, и начальное верхнее значение интервала кодирования в максимальное значение, равное, например, 2^r-1. Например, при r=11 начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000000 в двоичном представлении длиной 11 символов, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 2047 в десятичном представлении или 11111111111 в двоичном представлении. Пример начального состояния (Нач. сост.) интервала кодирования арифметического кодирования представлен на фиг. 5.

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

Начальное значение интервала кодирования арифметического кодера I[0], равное I[0]=Н[0]-L[0], разделяют на начальные значения подинтервала нулевых символов D₀[0] и подинтервала единичных символов D₁[0], длины которых прямо пропорциональны начальным значениям вероятностей кодируемых нулевых символов р₀[0] и единичных символов р₁[0] соответственно. Начальную длину подинтервала единичных символов D₁[0] определяют по формуле вида D₁[0]=I[0]×р₁[0], а начальную длину подинтервала нулевых символов D₀[0] определяют по формуле вида D₀[0]=I[0]-D₁[0]. Например, начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 1024 или 10000000000 в двоичном представлении, а начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 1023 или 01111111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 5. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, начальное значение Q имеет десятичное значение 1023, как показано на фиг. 6 в первой строке при t=0.

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

Примерный вид кодирования показанной на фиг. 4(e) первой УДП КВК n-го кодового блока в виде двоичной последовательности "011111" длиною 6 двоичных символов с использованием арифметического кодирования в кодированные последовательности n-го кодового блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК представлен на фиг. 5.

При поступлении на вход арифметического кодирования первого кодируемого символа, являющегося нулевым двоичным символом, значение интервала кодирования первого символа I[1] устанавливают равным начальному значению подинтервала нулевых символов D₀[0], поэтому нижнее значение интервала кодирования первого символа L[1] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодера L[0], равному, например, нулю, а верхнее значение интервала кодирования первого символа арифметического кодирования Н[1] устанавливают равным текущему значению Q, равному, например, 1023, как показано на фиг. 6 при t=1. Самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения Н[1], например, вида 000…0 и 0111…1 соответственно. При их совпадении значение самого левого бита двоичных представлений значений L[1] и H[1] считывают в качестве закодированного бита кодированной последовательности n-го кодового блока. Например, при кодировании УДП КВК n-го кодового блока в виде двоичной последовательности "0111111" первым закодированным битом кодированной последовательности этого блока является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 6, вторая строка сверху при t=1. Считанный бит удаляют из двоичных представлений значений L[1] и Н[1], которые уменьшаются до длины 10 бит вида 00…0 и 11…1 соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[1] и H[1] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.

В результате нормализации нижнее значение интервала кодирования первого символа приняло значение 0, а верхнее значение интервала кодирования приняло двоичное значение 111…10 или десятичное значение 2046, как показано на фиг. 6.

После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений считывают в качестве следующего закодированного бита кодированной последовательности n-го кодового блока. Например, после выполнения описанной нормализации между собой сравнивают самые левые биты двоичных представлений вида 000…0 и 111…10 и при их несовпадении переходят к кодированию следующего бита УДП КВК n-го кодового блока и так далее до окончания кодируемых битов УДП КВК этого блока.

После выполнения кодирования каждого очередного бита УДП КВК n-го кодового блока уточняют число закодированных нулевых символов и единичных символов. Так как первый кодированный бит является нулевым, то число закодированных нулевых символов увеличивают на единичное значение и оно составляет N₀[1]=2, и число закодированных нулевых и единичных символов становится равным N[1]=N₀[l]+N₁[l]=3. Пересчитывают текущее значение вероятности кодируемых нулевых символов p 0 [ 1 ] = N 0 [ 1