Кодирование кодов переменной длины с эффективным использованием памяти

Кодирование кодов переменной длины с эффективным использованием памяти

Иллюстрации

Показать все

Реферат

По настоящей заявке испрашивается приоритет на основании предварительной заявки США регистрационный № 60/865,827, поданной 14 ноября 2006 г., и предварительной заявки США регистрационный № 60/867,081, поданной 22 ноября 2006 г., содержание каждой из которых полностью включено в настоящую заявку посредством ссылки.

Область техники, к которой относится изобретение

Настоящее изобретение относится к сжатию данных и, более конкретно, к сжатию данных с использованием кодов переменной длины (VLC).

Уровень техники

Сжатие данных широко используется в различных областях применения для уменьшения занимаемой области для хранения данных, полосы пропускания или и того, и другого. Примеры областей применения сжатия данных включают в себя кодирование цифровых видеоданных, данных изображения, голосовых и звуковых данных. Кодирование цифровых видеоданных используется, например, в целом ряде устройств, в том числе в цифровых телевизионных устройствах, цифровых системах прямого вещания, устройствах беспроводной связи, карманных персональных компьютерах (КПК), портативных компьютерах или настольных компьютерах, цифровых камерах, цифровых записывающих устройствах, устройствах для видеоигр, сотовых или спутниковых радиотелефонах и тому подобном. Цифровые видеоустройства реализуют способы сжатия видеоданных, такие как MPEG-2, MPEG-4 или H.264/MPEG-4 улучшенного кодирования видеоданных (AVC), для более эффективной передачи и приема цифровых видеоданных.

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

Устройство кодирования видеоданных применяет процессы кодирования с преобразованием, кодирования с квантованием и статистического кодирования для дополнительного уменьшения скорости передачи в битах остаточного блока, полученного в процессе кодирования видеоданных. Способы статистического кодирования используются на последних каскадах кодера-декодера видеосигналов (CODEC) и в различных других кодирующих приложениях перед сохранением или передачей кодированных данных. Статистическое кодирование в целом включает в себя применение арифметических кодов или кодов переменной длины (VLC) для дальнейшего сжатия остаточных коэффициентов, полученных в результате операций преобразования и квантования. Примеры способов статистического кодирования включают в себя контекстно-регулируемое двоичное арифметическое кодирование (CABAC) и контекстно-регулируемое кодирование переменной длины (CAVLC), которые можно использовать в некоторых кодерах в качестве альтернативных режимов статистического кодирования. Устройство декодирования видеоданных выполняет статистическое декодирование для распаковки остаточной информации по каждому из блоков и восстановление кодированных видеоданных с использованием информации о движении и остаточной информации.

Сущность изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое описание чертежей

Фиг.1 - блок-схема, иллюстрирующая систему кодирования и декодирования видеоданных.

Фиг.2 - блок-схема, иллюстрирующая пример кодера видеоданных.

Фиг.3 - блок-схема, иллюстрирующая пример декодера видеоданных.

Фиг.4 - схема, иллюстрирующая пример дерева двоичного кодирования.

Фиг.5 - график, иллюстрирующий степень избыточности адаптивного блочного кода с асимптотическим поведением.

Фиг.6 - схема двоичного дерева, иллюстрирующая группы блоков, подгруппы и основные кодовые слова.

Фиг.7A и 7B - графики, иллюстрирующие сравнение степеней избыточности адаптивного блочного кода с различными значениями ρ.

Фиг.8 - график, иллюстрирующий чувствительность избыточности к асимметрии исходных данных.

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

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

Фиг.11 - блок-схема последовательности операций, иллюстрирующая способ декодирования переменных кодов переменной длины, построенных согласно способу на фиг.9.

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

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

Фиг.14 - блок-схема, иллюстрирующая способ декодирования кодов переменной длины, построенных согласно способу на фиг. 12.

Подробное описание

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

В соответствии с первым общим аспектом настоящего изобретения раскрытым способам нет необходимости опираться на какую-либо определенную схему построения кода для поддержки компактных структур данных. Например, можно использовать схемы Хаффмана, Шеннона, Шеннона-Фано, Гилберта-Мура или другие схемы построения кодов. Однако для этого первого общего аспекта предполагается, что такой код строится для источника с монотонно возрастающими вероятностями символов из входного алфавита символов. Более конкретно, предполагается, что длина кодовых слов монотонно уменьшается или, по меньшей мере, не увеличивается, и что кодовые слова одинаковой длины имеют тот же лексикографический порядок, что и символы во входном алфавите, который они представляют.

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

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

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

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

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

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

Примеры существующих способов кодирования или декодирования кодов переменной длины описаны в работе A. Moffat и A. Turpin, On the Implementation of Minimum-Redundancy Prefix Codes, IEEE Trans. Communications, 45 (10) (1997) 1200-1207; J. B. Connell, A Huffman-Shannon-Fano Code, Proc. IEEE, July 1973, 1046-1047; и A. Brodnik и S. Carlsson, Sublinear Decoding of Huffman Codes Almost in Place, DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches, October 1998, Rutgers University, DIMACS Center, NJ. По сравнению с этими существующими способами раскрытые способы обеспечения компактных структур данных могут предлагать определенные преимущества.

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

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

В соответствии со вторым общим аспектом настоящего изобретения для поддержки адаптивного кодирования и декодирования с низкой степенью сложности для двоичных последовательностей, созданных источниками без памяти, раскрытые способы позволяют реализовать универсальные блочные коды, построенные для набора контекстов, идентифицируемых по числу ненулевых битов среди предыдущих битов в последовательности. Этот второй общий аспект может обеспечиваться и применяться независимо или совместно с первым общим аспектом, описанным выше в отношении генерации очень компактных структур данных. Способы адаптивного кодирования и декодирования с низкой степенью сложности могут, в соответствии с этим вторым общим аспектом, опираться на раскрытую формулу для асимптотической избыточности таких кодов, которая уточняет оценку, описанную в работе R. E. Krichevsky и V. K. Trofimov, The Performance of Universal Encoding, IEEE Trans. Information Theory, 27 (1981) 199-207.

Способы в соответствии с этим вторым общим аспектом могут использовать массив кодов Хаффмана, предназначенный для нескольких оцениваемых плотностей и индексированный числом ненулевых битов в предыдущих блоках (контекстах) в последовательности. При использовании блоков даже умеренного размера n = 8…16 (и использовании соответствующих 1,5…5 килобайт памяти) такие способы могут обеспечивать эффективность сжатия, сравнимую или превосходящую другие существующие алгоритмы, такие как алгоритм Q-кодирования, описанный в работе W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, Jr, R. B. Arps, An overview of the basic principles of the Q-coder adaptive binary arithmetic coder, IBM J. Res. Dev., 32 (6) (1988) 717, который используется в стандарте кодирования изображений JBIG, или алгоритм CABAC, описанный в работе D. Marpe, H. Schwartz и T. Wiegand, Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC video compression standard, IEEE Trans. on CSVT, 13(7):620 636, July 2003, который используется в стандартах ITU-T H.264/MPEG AVC для сжатия видеосигнала.

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

Известно свойство кодов с минимальной избыточностью (такие как коды Хаффмана или Шеннона), что каждая группа равновероятных блоков может включать в себя максимум две подгруппы, причем блоки в каждой такой подгруппе закодированы кодовыми словами одной и той же длины. Без ограничения общности можно дополнительно предположить, что длина кодовых слов в первой подгруппе короче длины кодовых слов во второй подгруппе. Поскольку блоки (или слова) внутри группы следуют в лексикографическом порядке, ее можно просто поделить на подгруппы с более длинными кодовыми словами и подгруппы с менее длинными кодовыми словами. На положение блока внутри группы указывает значение индекса. Лексикографически наименьшему блоку (или слову) в каждой подгруппе присваивается базовое кодовое слово. При наличии базового кодового слова можно легко вычислить остальные кодовые слова в каждой подгруппе.

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