Эффективное по использованию памяти адаптивное блочное кодирование

Эффективное по использованию памяти адаптивное блочное кодирование

Иллюстрации

Показать все

Реферат

Данная заявка притязает на приоритет предварительной заявки на патент (США) номер 60/865827, поданной 14 ноября 2006 года, и предварительной заявки на патент (США) номер 60/867081, поданной 22 ноября 2006 года, все содержимое каждой из которых содержится в данном документе по ссылке.

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

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

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

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

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

Видеокодер применяет процессы преобразования, квантования и энтропийного кодирования для того, чтобы дополнительно понижать скорость передачи битов остаточного блока, сформированного посредством процесса кодирования видео. Методы энтропийного кодирования используются на конечных стадиях видеокодера - декодера (кодека) и в различных других приложениях кодирования до сохранения или передачи кодированных данных. Энтропийное кодирование, в общем, влечет за собой применение арифметических кодов или кодов переменной длины (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) индикатор, инструктирующий декодеру пропускать определенное число битов до перехода к следующему уровню кодового дерева. Соответственно, структура данных дополнительно может включать в себя значения для символов, представленных посредством базовых кодовых слов и длин частичных значений базовых кодовых слов, т.е. число битов в каждом частичном значении базового кодового слова. Методы кодирования и декодирования могут использовать эту структуру данных для того, чтобы идентифицировать уровень, соответствующий кодовому слову, которое должно быть сформировано или декодировано, и затем непосредственно вычислять значение кодового слова или декодированного символа. Соответственно, структура данных может быть сохранена в запоминающем устройстве видеокодера или декодера, кодера или декодера изображений, аудиокодера или декодера или речевого кодера или декодера, некоторые из которых могут быть составлены как комбинированные кодеки.

Примеры существующих методик для кодирования или декодирования кодов переменной длины описываются в работе 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, июль 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, октябрь 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, июль 2003 года, который используется в стандартах ITU - T H.264/MPEG AVC для видеосжатия.

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

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