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

Формула изобретения

1. Способ адаптированного кодирования переменной длины, содержащий этапы, на которых:

- выполняют кодирование переменной длины согласно структуре кода, при этом структура кода определяет:

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

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

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

2. Способ по п.1, в котором выполнение кодирования переменной длины содержит этапы, на которых:

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

- выполняют кодирование переменной длины с помощью структуры данных.

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

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

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

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

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

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

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

6. Способ по п.5, дополнительно содержащий этап, на котором передают кодированное значение в декодер.

7. Способ по п.1, в котором выполнение кодирования переменной длины содержит этап, на котором декодируют одно из кодовых слов с помощью структуры данных, при этом декодирование содержит этапы, на которых:

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

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

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

- определяют позицию кодового слова в группе, в которой постоянно размещается выбранная подгруппа, на основе того, является ли выбранная подгруппа первой подгруппой или второй подгруппой для группы;

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

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

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

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

10. Устройство адаптированного кодирования переменной длины, содержащее:

- средство выполнения кодирования переменной длины согласно структуре кода, при этом структура кода определяет:

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

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

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

11. Устройство по п.10, в котором средство выполнения кодирования переменной длины содержит:

- средство осуществления доступа к структуре данных, которая указывает базовые кодовые слова для каждой из подгрупп, позиции кодовых слов в каждой из групп, число кодовых слов в каждой из первых подгрупп и длины кодовых слов в каждой из подгрупп; и

- средство выполнения кодирования переменной длины с помощью структуры данных.

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

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

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

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

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

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

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

15. Устройство по п.14, дополнительно содержащее средство передачи кодированного значения в декодер.

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

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

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

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

- средство определения позиции кодового слова в группе, в которой постоянно размещается выбранная подгруппа, на основе того, является ли выбранная подгруппа первой подгруппой или второй подгруппой для группы;

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

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

17. Устройство по п.16, дополнительно содержащее средство представления вывода пользователю, по меньшей мере, частично на основе выбранного значения.

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

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

- выполнять кодирование переменной длины согласно структуре кода, при этом структура кода определяет:

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

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

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

20. Машиночитаемый носитель по п.19, дополнительно содержащий инструкции для того, чтобы предписывать процессору:

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

- выполнять кодирование переменной длины с помощью структуры данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28. Устройство адаптированного кодирования переменной длины, содержащее:

- процессор, выполненный с возможностью выполнять кодирование переменной длины согласно структуре кода, при этом структура кода определяет:

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

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

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

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

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

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

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

33. Устройство по п.32, дополнительно содержащее передающее устройство, которое передает кодированное значение в декодер.

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

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

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

37. Способ адаптированного кодирования переменной длины, содержащий этапы, на которых:

- для структуры кода определяют:

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

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

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

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

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

39. Способ по п.38, в котором кодирование содержит этапы, на которых:

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

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

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

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

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

41. Способ по п.40, в котором декодирование содержит этапы, на которых:

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

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

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

- определяют позицию кодового слова в группе, в которой постоянно размещается выбранная подгруппа, на основе того, является ли выбранная подгруппа первой подгруппой или второй подгруппой для группы;

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

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

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

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

44. Устройство адаптированного кодирования переменной длины, содержащее:

- для структуры кода средство для определения:

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

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

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

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

45. Устройство по п.44, в котором средство выполнения кодирования переменной длины содержит средство кодирования, по меньшей мере, некоторых из значений, и результатом кодирования переменной длины является одно или более кодовых слов.

46. Устройство по п.45, в котором средство кодирования содержит:

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

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

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

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

47. Устройство по п.44, в котором средство выполнения кодирования переменной длины содержит средство декодирования, по меньшей мере, некоторых из кодовых слов, и результатом кодирования переменной длины является одно или более значений.

48. Устройство по п.47, в котором средство декодирования содержит:

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

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

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

- средство определения позиции кодового слова в группе, в которой постоянно размещается выбранная подгруппа, на основе того, является ли выбранная подгруппа первой подгруппой или второй подгруппой для группы;

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

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

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

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

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

- для структуры кода определять:

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

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

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

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

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

53. Машиночитаемый носитель по п.52, в котором инструкции предписывают процессору:

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

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

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

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

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

55. Машиночитаемый носитель по п.54, в котором инструкции предписывают процессору:

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

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

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

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

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

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

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

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

58. Устройство адаптированного кодирования переменной длины, содержащее:

- для структуры кода определение:

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

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

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

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

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

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

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

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

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

65. Аппарат для беспроводной связи, содержащий:

- процессор, выполненный с возможностью выполнять кодирование переменной длины согласно структуре кода, при этом структура кода задает:

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

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

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

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

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

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

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

70. Аппарат по п.69, дополнительно содержащий беспроводное передающее устройство, которое передает кодированное значение в декодер.

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

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

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

74. Устройство адаптированного кодирования переменной длины на интегральных схемах, содержащее:

- процессор, выполненный с возможностью выполнять кодирование переменной длины согласно структуре кода, при этом структура кода определяет:

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

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

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

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

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

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

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

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

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

Описание изобретения к патенту

Данная заявка притязает на приоритет предварительной заявки на патент (США) номер 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 для видеосжатия.

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

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

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

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

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

Фиг. 1 является блок-схемой, иллюстрирующей систему 10 кодирования и декодирования видео. Как показано на фиг. 1, система 10 включает в себя исходное устройство 12, которое передает кодированное видео в принимающее устройство 14 через канал 16 связи. Исходное устройство 12 может включать в себя видеоисточник 18, видеокодер 20 и передающее устройство 22. Принимающее устройство 14 может включать в себя приемное устройство 24, видеодекодер 26 и видеодисплейное устройство 28. Система 10 может быть выполнена с возможностью применять методы для эффективного по использованию памяти адаптивного кодирования переменной длины (VLC) с низкой сложностью цифровых видеоданных. В частности, эффективные по использованию памяти методы адаптивного VLC с низкой сложностью могут использоваться для того, чтобы энтропийно кодировать остаточные блочные коэффициенты, сформированные посредством процесса прогнозирующего кодирования видео. Методы могут быть применены к схемам кодирования видео, которые кодируют позиции ненулевых коэффициентов преобразования с помощью серий нулей, или к другим схемам кодирования видео.

В примере по фиг. 1 канал 16 связи может содержать любую беспроводную и проводную среду связи, такую как радиочастотный (RF) спектр или одна или более физических линий передачи, либо любую комбинацию беспроводной и проводной среды. Канал 16 может формировать часть сети с коммутацией пакетов, такой как локальная вычислительная сеть, глобальная вычислительная сеть либо глобальная сеть, такая как Интернет. Канал 16 связи, в общем, представляет любую надлежащую среду связи или набор различных сред связи для передачи видеоданных из исходного устройства 12 в принимающее устройство 14.

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

Видеоисточник 18 может включать в себя устройство видеозахвата, такое как одна или более видеокамер, видеоархив, содержащий ранее захваченное видео, или передачу видео вживую от поставщика видеосодержимого. В качестве дополнительной альтернативы видеоисточник 18 может формировать основанные на компьютерной графике данные в качестве исходного видео или комбинацию живого видео и сформированного компьютером видео. В некоторых случаях, если видеоисточником 18 является камера, исходное устройство 12 и принимающее устройство 14 могут формировать так называемые камерофоны или видеофоны. Следовательно, в некоторых аспектах, исходное устройство 12, принимающее устройство 14 или и то, и другое могут формировать переносной телефонный аппарат для беспроводной связи, такой как мобильный телефон. В любом случае, захваченное, предварительно захваченное или сформированное компьютером видео может быть кодировано посредством видеокодера 20 для передачи из устройства 12 видеоисточника в видеокодер 26 устройства 14 приема видео через передающее устройство 22, канал 16 и приемное устройство 24. Дисплейное устройство 28 может включать в себя любое из множества дисплейных устройств, к примеру, жидкокристаллический дисплей (LCD), плазменный дисплей или дисплей на органических светодиодах (OLED).

Видеокодер 20 и видеодекодер 26 могут быть выполнены с возможностью поддерживать масштабированное видеокодирование для пространственного, временного масштабирования и/или масштабирования отношения "сигнал - шум" (SNR). В некоторых аспектах видеокодер 20 и видеодекодер 22 могут быть выполнены с возможностью поддерживать кодирование с масштабированием SNR с высокой степенью детализации (FGS) для SVC. Кодер 20 и декодер 26 могут поддерживать различные степени масштабирования посредством поддержки кодирования, передачи и декодирования базового слоя и одного или более масштабируемых улучшающих слоев. Для масштабированного видеокодирования базовый слой переносит видеоданные с минимальным уровнем качества. Один или более улучшающих слоев переносят дополнительный поток битов, чтобы поддерживать более высокие пространственные, временные уровни и/или уровни SNR.

Видеокодер 20 и видеодекодер 26 могут работать согласно такому стандарту видеосжатия, как MPEG - 2, MPEG - 4, ITU - T H.263 или ITU - T H.264/MPEG - 4 улучшенное видеокодирование (AVC). Хотя не показано на фиг. 1, в некоторых аспектах видеокодер 20 и видеодекодер 26 могут быть интегрированы с аудиокодером и декодером, соответственно, и включать в себя соответствующие модули MUX - DEMUX либо другие аппаратные средства и программное обеспечение, чтобы обрабатывать кодирование аудио и видео в общем потоке данных или в отдельных потоках данных. Если применимо, модули MUX - DEMUX могут соответствовать протоколу мультиплексора ITU H.223 или другим протоколам, таким как протокол пользовательских дейтаграмм (UDP).

Стандарт H.264/MPEG - 4 (AVC) сформулирован Экспертной группой в области кодирования видео (VCEG) ITU - T совместно с Экспертной группой по киноизображению (MPEG) ISO/IEC как продукт коллективного партнерского проекта, известного как Объединенная группа по видеостандартам (JVT). Стандарт H.264 описан в ITU - T Recommendation H.264 "Advanced video coding for generic audiovisual services" посредством Исследовательской группы ITU - T и датирован 03/2005, который может упоминаться в данном документе как стандарт H.264 или спецификация H.264 либо стандарт или спецификация H.264/AVC.

Объединенная группа по видеостандартам (JVT) продолжает работать над дополнением по масштабированному видеокодированию (SVC) в H.264/MPEG - 4 AVC. Спецификация развивающегося дополнения SVC приводится в форме совместного проекта (JD). Объединенная модель масштабированного видео (JSVM), созданная посредством JVT, реализует средства для использования в масштабированном видео, которые могут быть использованы в рамках системы 10 для различных задач кодирования, описанных в данном изобретении. Подробную информацию, касающуюся кодирования с масштабированием SNR с высокой степенью детализации (FGS), можно найти в документах Совместного проекта, к примеру, в Joint Draft 6 (SVC JD6), Thomas Wiegand, Gary Sullivan, Julien Reichel, Heiko Schwarz и Mathias Wien, "Joint Draft 6: Scalable Video Coding", JVT - S 201, апрель 2006 года, Женева, и в Joint Draft 9 (SVC JD9), Thomas Wiegand, Gary Sullivan, Julien Reichel, Heiko Schwarz и Mathias Wien, "Joint Draft 9 of SVC Amendment", JVT - V 201, январь 2007 года, Marrakech, Марокко.

В некоторых аспектах для широковещательной передачи видео методы, описанные в данном раскрытии сущности, могут быть применены к улучшенному видеокодированию H.264 для доставки видеоуслуг реального времени в системах наземной многоадресной передачи мобильного мультимедиа (TM3), использующих спецификацию радиоинтерфейса только прямой линии связи (FLO), "Forward Link Only Air Interface Specification for Terrestrial Mobile Multimedia Multicast", которая должна быть опубликована как Технический стандарт TIA - 1099 ("FLO Specification"), к примеру, через сервер беспроводной широковещательной передачи видео или переносной телефонный аппарат для беспроводной связи. Спецификация FLO включает в себя примеры, задающие синтаксис и семантику потока битов и процессы декодирования, подходящие для радиоинтерфейса FLO. Альтернативно, видео может передаваться в широковещательном режиме согласно другим стандартам, таким как DVB - H (цифровая широковещательная передача видео для карманных устройств), ISDB - T (комплексные службы цифровой наземной широковещательной передачи) или DMB (цифровая широковещательная передача мультимедиа). Следовательно, исходным устройством 12 может быть мобильный беспроводной терминал, сервер потоковой передачи видео и сервер широковещательной передачи видео. Тем не менее, методы, описанные в данном документе, не ограничены каким-либо конкретным типом системы широковещательной передачи, многоадресной передачи или передачи "точка - точка". В случае широковещательной передачи исходное устройство 12 может передавать в широковещательном режиме несколько каналов видеоданных в несколько принимающих устройств, каждое из которых может быть аналогичным принимающему устройству 14 по фиг. 1.

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

Видеопоследовательность включает в себя серии видеокадров. Видеокодер 20 оперирует с блоками пикселей в рамках отдельных видеокадров, чтобы кодировать видеоданные. Видеоблоки могут иметь фиксированный или изменяющийся размер и могут отличаться по размеру согласно заданному стандарту кодирования. Каждый видеокадр включает в себя серии секций. Каждая серия секций может включать в себя серии макроблоков, которые могут быть скомпонованы в субблоки. В качестве примера, стандарт ITU - T H.264 поддерживает внутреннее прогнозирование для различных размеров блоков, таких как 16 на 16, 8 на 8, 4 на 4 для компонентов сигнала яркости и 8×8 для компонентов сигнала цветности, а также взаимное прогнозирование для различных размеров блоков, таких как 16 на 16, 16 на 8, 8 на 16, 8 на 8, 8 на 4, 4 на 8 и 4 на 4 для компонентов сигнала яркости и соответствующих масштабированных размеров для компонентов сигнала цветности.

Меньшие видеоблоки могут предоставлять лучшее разрешение и могут быть использованы для позиций видеокадра, которые включают в себя более высокие уровни детальности. В общем, макроблоки (MB) и различные субблоки могут считаться видеоблоками. Помимо этого, секция может считаться серией видеоблоков, таких как MB и/или субблоки. Каждая секция может быть независимо декодируемой единицей. После прогнозирования преобразование может быть выполнено для остаточного блока 8×8 или остаточного блока 4×4, и дополнительное преобразование может быть применено к DC - коэффициентам блоков 4×4 для компонентов сигнала цветности или компонентов сигнала яркости, если используется режим прогнозирования intra_16×16.

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

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

Как показано на фиг. 2, видеокодер 20 принимает текущий видеоблок 30 в видеокадре, который должен быть кодирован. В примере по фиг. 2, видеокодер 20 включает в себя модуль 32 оценки движения, модуль 34 хранения опорных кадров, модуль 36 компенсации движения, модуль 38 блочного преобразования, модуль 40 квантования, модуль 42 обратного квантования, модуль 44 обратного преобразования и модуль 46 энтропийного кодирования. Модуль 46 энтропийного кодирования может осуществлять доступ к одной или более структур данных, сохраненных в запоминающем устройстве 45, чтобы получать данные, полезные при кодировании. Внутриконтурный деблокирующий фильтр (не показан) может быть применен для того, чтобы фильтровать блоки, чтобы удалять артефакты разделения на блоки. Видеокодер 20 также включает в себя сумматор 48 и сумматор 50. Фиг. 2 иллюстрирует компоненты временного прогнозирования видеокодера 20 для взаимного кодирования видеоблоков. Хотя не показано на фиг. 2 для упрощения иллюстрации, видеокодер 20 также может включать в себя компоненты пространственного прогнозирования для внутреннего кодирования некоторых видеоблоков.

Модуль 32 оценки движения сравнивает видеоблок 30 с блоками в одном или более соседних кадров, чтобы сформировать один или более векторов движения. Соседний кадр или кадры могут извлекаться из модуля 34 хранения опорных кадров, который может включать в себя любой тип запоминающего устройства или устройства хранения данных, чтобы сохранять видеоблоки, восстановленные из ранее кодированных блоков. Оценка движения может выполняться для блоков переменного размера, к примеру, 16×16, 16×8, 8×16, 8×8 или меньших размеров блоков. Модуль 32 оценки движения идентифицирует один или более блоков соседних кадров, в наибольшей степени совпадают с текущим видеоблоком 30, к примеру, на основе модели искажения в зависимости от скорости передачи, и определяет смещение между блоками в соседних кадрах и текущим видеоблоком. На этой основе модуль 32 оценки движения формирует один или более векторов движения (MV), которые указывают абсолютную величину и траекторию смещения между текущим видеоблоком 30 и одним или более совпадающих блоков от опорных кадров, используемых для того, чтобы кодировать текущий видеоблок 30.

Векторы движения могут иметь точность в пол- или четверть пикселя или даже большую точность, позволяя видеокодеру 20 отслеживать движение с более высокой точностью, чем целочисленные позиции пикселей, и получать более оптимальный прогнозный блок. Когда векторы движения с дробными пиксельными значениями используются, операции интерполяции выполняются в модуле 36 компенсации движения. Модуль 32 оценки движения идентифицирует оптимальные блочные сегменты и вектор движения или векторы движения для видеоблока с помощью определенного критерия, такого как модель искажения в зависимости от скорости передачи. Например, может быть несколько векторов движения в случае двунаправленного прогнозирования. Используя результирующие блочные сегменты и векторы движения, модуль 36 компенсации движения формирует прогнозный видеоблок.

Видеокодер 20 формирует остаточный видеоблок посредством вычитания прогнозного видеоблока, сформированного посредством модуля 36 компенсации движении, из оригинального текущего видеоблока 30 в сумматоре 48. Модуль 38 блочного преобразования применяет преобразование, такое как целочисленное преобразование 4×4 или 8×8, используемое в H.264/AVC, к остаточному блоку, формируя коэффициенты остаточного преобразования блоков. Модуль 40 квантования квантует коэффициенты остаточного преобразования блоков, чтобы дополнительно уменьшать скорость передачи битов. Модуль 46 энтропийного кодирования энтропийно кодирует квантованные коэффициенты, чтобы еще более уменьшать скорость передачи битов.

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

Модуль 42 обратного квантования и модуль 44 обратного преобразования применяют обратное квантование и обратное преобразование, соответственно, для того, чтобы восстановить остаточный блок. Сумматор 50 прибавляет восстановленный остаточный блок к прогнозному блоку с компенсацией движения, сформированному посредством модуля 36 компенсации движения, чтобы сформировать восстановленный видеоблок для хранения в модуле 34 хранения опорных кадров. Восстановленный видеоблок используется посредством модуля 32 оценки движения и модуля 36 компенсации движения для того, чтобы кодировать блок в последующем видеокадре.

Фиг. 3 является блок-схемой, иллюстрирующей пример видеодекодера 26. Видеодекодер 26 может быть сформирован, по меньшей мере, частично как одно или более устройств на интегральных схемах, которые могут упоминаться совместно как устройство на интегральных схемах. В некоторых аспектах видеодекодер 26 может формировать часть портативного телефонного аппарата для беспроводной связи. Видеодекодер 26 может выполнять внутреннее и взаимное декодирование блоков в видеокадрах. Как показано на фиг. 3, видеодекодер 26 принимает кодированный поток битов, который кодирован посредством видеокодера 20. В примере на фиг. 3 видеодекодер 26 включает в себя модуль 52 энтропийного декодирования, модуль 54 компенсации движения, модуль 56 обратного квантования, модуль 58 обратного преобразования и модуль 62 хранения опорных кадров. Видеодекодер 26 также может включать в себя внутриконтурный деблокирующий фильтр (не показан), который фильтрует вывод сумматора 64. Видеодекодер 26 также включает в себя сумматор 4. Фиг. 3 иллюстрирует компоненты временного прогнозирования видеодекодера 26 для взаимного кодирования видеоблоков. Хотя не показано на фиг. 3, видеодекодер 26 также может включать в себя компоненты пространственного прогнозирования для внутреннего кодирования некоторых видеоблоков.

Модуль 52 энтропийного декодирования принимает кодированный поток видеобитов и декодирует из потока битов остаточные коэффициенты, режим кодирования макроблоков и информацию движения, которая может включать в себя векторы движения и блочные сегменты. Следовательно, модуль 52 энтропийного декодирования выступает в качестве модуля VLC-декодирования. Например, чтобы декодировать квантованные остаточные коэффициенты из кодированного потока битов, аналогично модулю 46 энтропийного кодирования по фиг. 2, модуль 52 энтропийного декодирования по фиг. 3 может выполнять эффективное по использованию памяти адаптивное VLC-декодирование с низкой сложностью цифровых коэффициентов видеоблока, как описано в этом раскрытии сущности. Тем не менее, модуль 52 энтропийного декодирования может выполнять VLC-декодирование обратным способом относительно модуля 46 энтропийного кодирования по фиг. 2, чтобы извлекать квантованные блочные коэффициенты из кодированного потока битов. Следовательно, различные процессы декодирования, описанные в этом раскрытии сущности, могут быть реализованы в модуле 52 энтропийного декодирования для того, чтобы выполнять декодирование видеоданных. Альтернативно, такой модуль 52 энтропийного декодирования может выполнять процессы, описанные в этом раскрытии сущности, для того чтобы декодировать любые из множества данных, включая, но не только, видео, изображения, речь и аудиоданные. Так или иначе, результат кодирования переменной длины, выполняемого посредством модуля 52 энтропийного декодирования может быть выведен пользователю, сохранен в запоминающем устройстве и/или передан в другое устройство или модуль обработки.

Модуль 54 компенсации движения принимает векторы движения и блочные сегменты и один или более восстановленных опорных кадров из модуля 62 хранения опорных кадров, чтобы сформировать прогнозный видеоблок. Модуль 56 обратного квантования обратно квантует, т.е. деквантует квантованные блочные коэффициенты. Модуль 58 обратного преобразования применяет обратное преобразование, к примеру, обратное DCT или обратное целочисленное преобразование 4×4 или 8×8, к коэффициентам, чтобы сформировать остаточные блоки. Прогнозные видеоблоки затем суммируются посредством сумматора 64 с остаточными блоками, чтобы сформировать декодированные блоки. Деблокирующий фильтр (не показан) может быть применен, чтобы фильтровать декодированные блоки, чтобы удалять помехи блокирования. Фильтрованные блоки затем помещаются в модуль 62 хранения опорных кадров, который предоставляет опорный кадр для декодирования последующих видеокадров и также формирует декодированное видео, чтобы активировать дисплейное устройство 28 (фиг. 1).

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

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

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

a) частичное значение лексикографически наименьшего (или наибольшего) кодового слова на текущем уровне в кодовом дереве,

b) число битов в частичном значении,

c) значение символа, соответствующего лексикографически наименьшему (или наибольшему) кодовому слову,

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

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

Эта методика может разрешать использование гораздо меньшего объема памяти для кодирования и декодирования вследствие того, что только частичные значения лексикографически наименьших кодовых слов сохраняются. Структура данных может быть любой из широкого спектра структур данных, таких как таблицы, связные списки, двоичные деревья, базисные деревья, неструктурированные файлы и т.п. и может быть сохранена в любом из множества различных запоминающих устройств, к примеру, во многих формах оперативного запоминающего устройства (RAM), постоянного запоминающего устройства (ROM) или и того, и другого. Структура данных может быть сохранена в таком запоминающем устройстве в кодере или декодере, к примеру, в запоминающем устройстве 45 или запоминающем устройстве 51, показанных на фиг. 2 и 3 соответственно. К тому же, по меньшей мере, некоторые из уровней кодового дерева включают в себя кодовые слова, упорядоченные в лексикографическом порядке относительно порядка значений символов, представленных посредством кодовых слов. Соответственно, каждое из базовых кодовых слов является лексикографически наименьшим кодовым словом на соответствующем уровне в кодовом дереве. Помимо этого, данная методика разрешает использование инкрементального доступа к данным потока битов, давая возможность буферу потоков битов быть представленным посредством достаточно короткого регистра. Например, 32-битовый регистр мог быть достаточным даже для очень длинных кодов. Регистр может быть обновлен через удобные интервалы (к примеру, 8 битов), дополнительно снижая сложность реализации. В целом, в различных аспектах, методика может допускать существенное уменьшение сложности представления и кодирования/декодирования кодов переменной длины, что позволяет предоставлять возможность проектировщикам алгоритмов сжатия использовать большие, более эффективные, таблицы кодирования.

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

Примерами кодов переменной длины, используемых в сжатии данных, являются коды Хаффмана, к примеру, как описано в работе D. A. Huffman "The method for the construction of minimum - redundancy codes. Proc. IRE, vol 40", стр. 1098-1101, сентябрь 1952 года, коды Шеннона, к примеру, как описано в работе C. E. Shannon "A mathematical theory of communication, Bell Syst. Tech J. Vol. 27, стр. 379-423, июль 1948 года, коды Шеннона - Фано, к примеру, как описано в работе R M. Fano "The transmission of information", Res. Lab. Electronics, Massachusetts Inst. of Technology, Cambridge, Mass. Tech. Rep. No 65, 1949 год, и коды Гильберта - Мура, к примеру, как описано в работе E. N. Gilbert и E. F. Moore, "Variable - Length Binary Encodings", Bell Syst. Tech. J., Vol. 7, стр. 932-967, 1959 год (также иногда называемые кодами Шеннона - Фано - Элиаса).

Коды, описанные выше, принадлежат классу беспрефиксных кодов, к примеру, как описано работе в T. Cover и J. Thomas, "Elements of Information Theory", Wiley, 1991 год. Фиг. 4 является схемой, иллюстрирующей пример двоичного кодового дерева. Коды, описанные выше, могут быть удобно представлены посредством двоичного дерева, такого как показано на фиг. 4. Следовательно, кодер может кодировать значения символов, согласованные с кодовым деревом. Значения согласно дереву могут представлять любые из множества данных, такие как видеоданные, данные изображений, речевые данные или аудиоданные. Каждый внутренний узел в таком дереве соответствует двоичному символу, значение в 0 которого вызывает перемещение к правому, а значение в 1 которого вызывает перемещение к левому дочернему узлу в дереве. Самый верхний узел называется корневым узлом, который является узлом, с которого начинается кодирование/декодирование.

Каждый внешний узел в дереве - это узел, где процесс кодирования/декодирования перезапускается, формируя либо кодовое слово, т.е. в качестве последовательности битов от корня до текущего узла, либо декодированное значение символа, ассоциативно связанного с текущим кодовым словом. В примерном кодовом дереве по фиг. 4, предусмотрено шестнадцать кодовых слов, соответствующих символам, индексированным с 0 до 15. В этом примере самое короткое кодовое слово имеет длину в 1 бит, а самые длинные кодовые слова имеют длину по 10 битов каждое. Число уровней, содержащих внешние узлы (кодовые слова) в этом дереве, равно 7, т.е. на 1-м, 3-м, 4-м, 6-м, 7-м, 9-м и 10-м уровнях.

Вновь ссылаясь на фиг. 4, пусть n обозначает число внешних узлов в кодовом дереве (и, соответственно, число кодовых слов в коде), пусть L обозначает длину самого длинного кодового слова и пусть K обозначает число уровней, заполненных внешними узлами в кодовом дереве. Следующее пояснение использует O - нотацию P. Bachmann. Например, выражение y(n)=O(x(n)) указывает существование некоторой константы M>0, так что |y()|<=M|x(n)| для всех достаточно больших n.

Чтобы поддерживать процесс кодирования, кодер или декодер, такой как модуль 46 энтропийного кодирования или модуль 52 энтропийного декодирования, в общем, должен сохранять двоичное дерево в компьютерном запоминающем устройстве, таком как запоминающее устройство 45 или запоминающее устройство 51. Помимо этого, процессы кодирования и декодирования должны заключать в себе побитовый (т.е. узел за узлом), обход кодового дерева, сохраненного в запоминающем устройстве. Следовательно, эта реализация должна заключать в себе затраты на хранение O(n) и может занимать до O(L) этапов. Однако в некоторых частных случаях, когда деревья кодирования имеют некоторую конкретную структуру, могут быть более эффективные способы сохранения таких структур кода и выполнения операций кодирования или декодирования.

Например, при рассмотрении кода, представленного в примерном кодовом дереве по фиг. 4, можно заметить, что кодовые слова являются неубывающими по длине и что все кодовые слова на одном уровне кодового дерева имеют смежные значения. Например, кодовые слова на 4-м уровне дерева на фиг. 4 являются более длинными, чем кодовые слова на 3-м уровне дерева, т.е. 0001 по сравнению с 011, 010, 001 и 000. Помимо этого, кодовые слова на 3-м уровне имеют смежные значения 011, 010, 011 000, 000. Следовательно, вместо сохранения всех кодов может быть достаточным сохранять только наименьшее или наибольшее кодовое слово для каждого уровня кодового дерева, т.е. в качестве базового кодового слова, из которого смежные кодовые слова могут быть вычислены.

Вышеупомянутое наблюдение является ключевым для понимания методик декодирования кодов переменной длины на основе их преобразования в так называемую каноническую форму, к примеру, как описано в работе A. Moffat и A. Turpin "On the Implementation of Minimum - Redundancy Prefix Codes", IEEE Trans. Communications, 45 (10) (1997) 1200-1207. В простых терминах канонический код имеет неубывающее распределение длин и поддерживает лексикографический порядок относительно индексов, назначенных его узлам. Довольно просто показать, что любой данный источник может быть переупорядочен так, что результирующий код имеет вышеупомянутые свойства.

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

Таблица 1
Пример канонического кода переменной длины
Символ	Вероят-ность	Индекс символа после переупорядочения	Длина кода	Код
0	0,6561	15	1	1
1	0,0729	12	3	011
2	0,0729	13	3	010
3	0,0081	5	7	0000101
4	0,0729	14	3	001
5	0,0081	6	7	0000100
6	0,0081	10	6	000011
7	0,0009	1	10	0000000001
8	0,0729	11	4	0001
9	0,0081	7	7	0000011
10	0,0081	8	7	0000010
11	0,0009	2	9	000000011
12	0,0081	9	7	0000001
13	0,0009	3	9	000000010
14	0,0009	4	9	000000001
15	0,0001	0	10	0000000000

В таблице 1, символ 0 имеет самую высокую вероятность, за которым следуют 1 и 2. Тем не менее, символ 3 имеет более низкую вероятность, чем 4, и 4 и 8 имеют такую же вероятность, как 1 и 2. После переупорядочения все вероятности символов монотонно увеличиваются (не убывают) и приводят к показанному каноническому коду, представленному в кодовом дереве по фиг. 4. Так называемый алгоритм Моффата - Турпина, как описано в работе 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, похожи на алгоритм Моффата - Турпина и также могут быть улучшены посредством использования раскрытых методик аналогичным образом.

Алгоритм Моффата - Турпина для декодирования кодов переменной длины описывается ниже. Предположим, что входной алфавит A содержит n символов: , переупорядочение применяется, таким образом, что результирующие вероятности удовлетворяют: . Далее, алгоритм Хаффмана или другой алгоритм составления минимальной избыточности может быть применен, который назначает длины кодовых слов l_i для каждого индекса , где L - это длина самого длинного кодового слова. Как результат, "номера совокупности" формируются как m _l, т.е. число кодовых слов длины l.

Используя эти параметры, так называемые "базовые" значения вычисляются для каждого уровня в дереве следующим образом:

Эти значения базовых кодовых слов представляют лексикографически наименьшие канонические кодовые слова на каждом уровне дерева. С учетом значения базового кодового слова в теперь можно вычислять значение (j+1^st) - го кодового слова из m_l кодовых слов длины l:

Для работы декодера более удобно сохранять выровненную по левому краю версию значения базового кодового слова следующим образом:

где W - это длина разрядного буфера или регистра, используемого для того, чтобы сохранять новые загруженные биты из потока битов. Предполагается, что W>=L.

Наконец, в дополнение к значениям базовых кодовых слов, декодер Моффата - Турпина также сохраняет индексы соответствующих символов в переупорядоченной матрице. Эти индексы сохраняются как значения offset[i] для каждого заполненного уровня в дереве. Конечная примерная структура, поддерживаемая посредством алгоритма Моффата - Турпина для кода, представленного посредством дерева по фиг. 4, представлена в таблице 2

Таблица 2
Структура декодера Моффата - Турпина для кода на фиг. 4
i	lj_base[i] (W=16)	level[i]	offset[i]
0	1000000000000000	1	15
1	0010000000000000	3	12
2	0001000000000000	4	11
3	0000110000000000	6	10
4	0000001000000000	7	5
5	0000000010000000	9	2
6	0000000000000000	10	0

Примерный псевдокод для реализации алгоритма декодирования Моффата - Турпина с использованием структуры таблицы 2 представлен в таблице 3.

Таблица 3
Алгоритм декодера Моффата - Турпина
Строка	Инструкция	Комментарий
1	V = bitstream_buffer;	получение последних W битов из потока битов
2	For (i=0; i<K; i++) {
3	if (lj_base[i ]<=V)	поиск уровня,
4	break;	содержащего текущее кодовое слово
5	}
6	l = level[ i];	получение длины
7	scroll_bitstream( l);	просмотр потока битов на l битов
8	symbol = offset[ i] + ((V - base[i])>>(W - l));	декодирование символа

Из таблицы 3 выше можно отметить, что весь процесс декодирования заключает в себе до K (W - битовых) сравнений текущего буфера потоков битов с выровненными по левому краю значениями базовых кодовых слов, за которым следует простое прямое вычисление индекса декодированного символа. Можно также отметить, что матрица lj_base[], используемая посредством этой структуры, требует O(K*W) битов памяти, что могло бы быть проблемой, если бы кодовые слова были длинными, поскольку W должно использоваться таким образом, что W>= l.

В примере таблицы 3 декодер принимает W битов из потока битов и как V и сравнивает V с базовыми кодовыми словами (lj_base[i]) для последовательных уровней i кодового дерева. Когда найдено базовое кодовое слово, которое меньше или равно V, поиск уровня кодового слова заканчивается. Далее, декодер определяет длину, ассоциативно связанную с уровнем i, прокручивает поток битов на l битов и декодирует символ. В частности, декодированный символ определяется посредством суммы значения смещения для уровня i и разности между кодовым словом V из потока битов и базовым кодовым словом для уровня i, сдвинутым вправо на W - l битов.

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

В соответствии с первым общим аспектом методы, описанные в этом раскрытии сущности, предоставляют усовершенствования, которые предоставляют дополнительное сжатие структур данных, используемых в алгоритме Моффата - Турпина или в других алгоритмах, и поддерживают инкрементное декодирование кодов переменной длины. Усовершенствования далее поясняются более подробно. Со ссылкой на таблицу 2 очевидно, что значения lj_base[i] имеют большие величины начальных битов справа налево. Следовательно, частичные значения базовых кодовых слов представляют удаление фиксированного числа начальных битов из базовых кодовых слов. В большинстве случаев начальные биты, которые удаляются, будут нулями. Эти числа нулей монотонно увеличиваются по мере того, как кодовое дерево продлевается к более глубоким уровням. Следовательно, если биты последовательно декодируются, начиная с самого первого уровня кодового дерева и переходя вниз, можно пропускать некоторые из начальных нулевых битов без влияния на корректность декодирования. Посредством пропуска, по меньшей мере, некоторых из начальных нулей, методы, описанные в этом раскрытии сущности, разрешают очень сжатые структуры данных и инкрементное декодирование кодов переменной длины.

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

Таблица 4 ниже иллюстрирует примерную реализацию процесса кодирования, в котором начальные нули удаляются, в соответствии с аспектом этого раскрытия сущности, чтобы дополнительно сжимать структуру данных, используемую для того, чтобы представлять и обрабатывать кодовые слова. В примере таблицы 4 начальные нули удаляются с приращениями в 8, что удобно для управления буфером потоков битов в традиционных 8-битовых/байтовых компьютерах. Чтобы управлять удалением начальных нулей, дополнительная таблица индикаторов (skip_8[i]) предоставляется, как описано выше. Следовательно, таблица 4, в общем, соответствует таблице 2, но удаляет начальные нули из каждого из кодовых слов и добавляет столбец индикатора пропуска.

Таблица 4
Модифицированная структура декодера Моффата - Турпина
i	r_lj_base[i] (W=8)	skip_8[i]	r_level[i]	offset[i]
0	10000000	0	1	15
1	00100000	0	3	12
2	00010000	0	4	11
3	00001100	0	6	10
4	00000010	1	7	5
5	10000000	0	9-8=1	2
6	00000000	0	10-8=2	0

В примере таблицы 4, значение r_lj_base[i] представляет значение базового кодового слова в каждой позиции индекса, значение r_level[i] указывает уровень в кодовом дереве для позиции индекса и длины кодовых слов на этом уровне, значение offset[i] указывает число начальных нулей справа налево для значения базового кодового слова, а значение skip_8[i] указывает то, должен ли декодер пропускать 8 битов для следующего значения базового кодового слова, при этом 1 обозначает пропуск, а 0 обозначает отсутствие пропуска. Эта операция пропуска периодически обновляет разрядный буфер c выбранными интервалами, чтобы разрешать декодеру идентифицировать кодовые слова, которые в противном случае будут потеряны, когда начальные нули удалены. Например, если крайние правые восемь начальных нулей выровненного по левому краю кодового слова удалены, кодовое слово, которое расширяется в крайние правые восемь битов, будет частично или полностью потеряно. Соответственно, пропуск крайних левых восьми битов в ответ на индикатор пропуска должен перемещать кодовое слово в диапазон битов, которые не удалены, тем самым сохраняя кодовое слово для использования в декодировании.

Следовательно, индикатор пропуска сообщает, когда декодер должен пропускать вперед на указанное приращение пропуска для следующего уровня кода, к примеру 8 в примере таблицы 4. В качестве иллюстрации: в таблице 2 значения базовых кодовых слов в позициях индекса 5 и 6 (уровни дерева 9 и 10) - это 0000000010000000 и 0000000000000000, соответственно. Когда крайние правые восемь начальных нулей (выровненных по левому краю) удалены из этих значений базовых кодовых слов, необходимо для декодера пропускать вперед восемь битов так, чтобы фактическое значение базового кодового слова (0000000010000000) не терялось при удалении восьми начальных нулей. Вместо этого фактическое значение базового кодового слова (0000000010000000) преобразуется в другое значение базового кодового слова (10000000) посредством пропуска первых восьми битов (00000000) и последующего удаления крайних правых восьми начальных нулей.

Вследствие удаления начальных нулей ширина модифицированной матрицы lj_base[i] намного меньше. В коде таблицы 4, в качестве примера, ширина W модифицированной матрицы lj_base[i] составляет W=8, вместо W=16 в случае таблицы 2. Пример реализации алгоритма, который использует такую дополнительную таблицу пропуска для того, чтобы периодически обновлять битовый буфер, показан ниже в таблице 5. Алгоритм, составленный так, как показано в таблице 5, может быть выполнен с возможностью поддерживать очень длинные кодовые слова или очень компактные таблицы значений базовых кодовых слов (lj_base).

Таблица 5
Модифицированный алгоритм декодера Моффата - Турпина
Строка	Инструкция	Комментарий
1	V=bitstream_buffer;	получение последних W битов из потока битов
2	for (i=0; i<K; i++) {
3	if (lj_base[i]<=V)	поиск уровня,
4	break;	содержащего текущее кодовое слово
5	if (skip_B[i ])	следует пропустить следующие биты B?
6	V=scroll_bitstream(B);	просмотр потока битов на B битов
7	}
8	l=level[i ];	получение остаточной длины
9	scroll_bitstream(l );	просмотр потока битов на l битов
10	symbol=offset[ i]+((V - base[i])>>(W - l));	декодирование символа

Как показано в таблице 5, декодер получает последние W битов из потока битов, представленного посредством значения V=bitstream_buffer. Декодер затем выполняет поиск на уровнях i кодового дерева значения базового кодового слова lj_base[i], которое меньше или равно кодовому слову V, из буфера потоков битов. Если текущий уровень i дерева соответствует уровню пропуска (skip_B[i ]), к примеру, как указано в таблице 5, то декодер прокручивает поток битов вправо на B битов, к примеру, на 8 битов в некоторых реализациях, так чтобы кодовое слово на следующем уровне, где выполнял поиск декодер, могло быть сохранено, а не потеряно посредством удаления B крайних правых начальных нулей.

После определения остаточной длины l = level[i] для кодовых слов на текущем уровне дерева, к примеру, как указано в таблице 5, декодер прокручивает поток битов на длину l. Затем декодер напрямую вычисляет индекс символа на основе суммы смещения для текущего уровня i и разности между содержимым буфера потоков битов V и базовым кодовым словом для текущего уровня i, сдвинутым вправо на W - l битов.

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

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

Если i - это индекс следующего непустого уровня, то:

Здесь основная интересующая величина - это , которая влияет на эту разность. В самом простом случае, когда i=1, очевидно, что эта разность зависит просто от числа внешних узлов и, следовательно, W может быть выбрано так, что:

,

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

Например, если входными символами являются блоки из m битов с вероятностями Бернулли , то наиболее заполненный уровень должен содержать приблизительно кодовых слов, что означает то, что приблизительно битов должно быть использовано для того, чтобы различать между кодовыми словами, где H(p) является функцией энтропии, к примеру, как описано в работе T. Cover и J. Thomas "Elements of Information Theory", Wiley, 1991 год.

С другой стороны, самое длинное кодовое слово в этом случае должно иметь приблизительно битов, где известно то, что для асимметричных распределений:

где - это частный случай энтропии Реньи, к примеру, как описано в работе W. Szpankowski "Average Case Analysis of Algorithms on Sequences" (New York, John Wiley & Sons, 2001 год). Эта разность может быть произвольно большой с p - >0 или p - >1.

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

Например, очень популярные коды Голомба, к примеру, как описано в работе S. Golomb Run - length coding", IEEE Trans. Inform. Theory, vol. IT - 12, стр. 399-401, июль 1966 года, и в работе R. Gallager и D. van Voorhis "Optimal source codes for geometrically distributed integer alphabets", IEEE Trans. Inform. Theory, vol. IT - 21, стр. 228-230, март 1975 года, представляют коды переменной длины с особенно простой структурой, но они оптимальны только для класса геометрических распределений и только для многосчетных значений параметров таких распределений. Инженеры стараются использовать их даже для значительно расходящихся распределений, что обусловлено главным образом соображениями сложности. Такие решения могут стать как субоптимальными, так и сложными в расширении или модификации из-за неявных ограничений производительности таких кодов.

Другое решение, ассоциированное со схемой кодов Линча - Дэвиссона, описанное в работе T. J. Lynch "Sequence time coding for data compression", Proc. IEEE (Lett.), 54 (1966) 1490-1491, и в работе L. D. Davisson "Comments on Sequence time coding for data compression", Proc. IEEE (Lett.), 54 (1966) 2010-2011, состоит в том, чтобы разбивать коды на две части, при этом только первая подвергается кодированию переменной длины, а оставшаяся передается как расширение с использованием фиксированного числа битов. К сожалению, в таком разбиении заложена потеря эффективности, иногда порядка 1,5-2 бита на символ.

Более тщательно разработанная версия методы разбиения таблицы кодирования создана под названием "группировка алфавита", к примеру, как описано в работе Boris Ryabko, Jaakko Astola, Karen Egiazarian "Fast Codes for Large Alphabets", Communications in Information and Systems, v. 3, n. 2, стр. 139-152, и в работе Boris Ryabko, Jorma Rissanen "Fast Adaptive Arithmetic Code for Large Alphabet Sources with Asymmetrical Distributions", IEEE Communications Letters, v. 7, no. 1, 2003, стр. 33-35. Тем не менее, этот подход также осуществляется за счет некоторой потери эффективности сжатия.

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

Двоичное адаптивное блочное кодирование

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

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

Наиболее часто используемые реализации таких двоичных адаптивных алгоритмов типично основаны на арифметических кодах с некоторыми приближениями и сокращениями, применяемыми для того, чтобы уменьшать их сложность. Два известных примера таких алгоритмов - это алгоритм 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 для видеосжатия.

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

Этот метод может рассматриваться в контексте источника без запоминания, формирующего символы из двоичного алфавита (0,1) с вероятностями p и q=1-p, соответственно. Если w - это слово длины n, сформированное посредством этого источника, то его вероятность равна:

где k обозначает число единиц в этом слове. Значение k также может упоминаться как весовой коэффициент w.

Блочный код является инъективным отображением между словами w длины |w|=n и двоичными последовательностями (или кодовыми словами) (w):

где кодовые слова (w) представляют уникально декодируемый набор, к примеру, как описано в работе T. M. Cover и J. M. Thomas "Elements of Information Theory" (John Wiley & Sons, New York, 1991).

Как правило, когда источник (т.е. его вероятность p) известен, такой код проектируется так, чтобы минимизировать его среднюю длину или, в относительных терминах, его среднюю избыточность:

В вышеупомянутом уравнении H(p)= - p log p - q log q обозначает энтропию источника.

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

Когда источник неизвестен, лучший доступный вариант состоит в том, чтобы создавать универсальный код ^*, который минимизирует избыточность наихудшего случая для класса источников, к примеру, как описано в работе B. M. Fitingof "Optimal Coding in the Case of Unknown and Changing Message Statistics", Probl. Inform. Transm., 2, (2) (1965) 3{11 (in Russian) 1-7 (English Transl.), в работе L. D. Davisson "Universal Noiseless Coding", IEEE Trans. Inform. Theory, 19 (6) (1973), 783-795, и в работе R. E. Krichevsky и V. K. Trofimov "The Performance of Universal Encoding", IEEE Trans. Information Theory, 27 (1981) 199-207, и как указано ниже:

Пример такого кода может быть составлен с помощью следующих оценок вероятностей слова:

где - это Г - функция, k - это весовой коэффициент слова w, а n - это его длина. Вышеупомянутая формула описывается в работе R. E. Krichevsky и V. K. Trofimov "The Performance of Universal Encoding", IEEE Trans. Information Theory, 27 (1981) 199-207, и обеспечивает равномерную (в ) конвергенцию к истинным вероятностям по мере того, как n стремится к бесконечности (n - > ).

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

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

где s - это весовой коэффициент выборки u, а t - это ее длина.

Идея и анализ основанных на выборке кодов, использующих функцию (1) модуля оценки, указанную непосредственно выше, описываются R. E. Krichevsky в работе R. E. Krichevsky "Universal Data Compression and Retrieval" (Kluwer, Norwell, MA, 1993). Средний коэффициент избыточности адаптивного блочного кода вычисляется асимптотически:

где n - это размер блока, а t - это размер выборок.

Из уравнения (2) выше очевидно, что посредством использования выборок длины t=O(n) можно понижать коэффициент избыточности данных кодов до O(1/n), что соответствует порядку коэффициента избыточности блочных кодов для известных источников. Тем не менее, чтобы иметь возможность понимать полный потенциал таких кодов, нужно знать более точное выражение для их избыточности, включая члены, затронутые выбором фактического алгоритма составления кода, такого как алгоритм Хаффмана, Шеннона и т.п.

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

Теорема 1: Средний коэффициент избыточности адаптивного блочного кода имеет следующий асимптотический характер изменения (n, t - > ):

(3A)

при этом n - это размер блока, а t - это объем выборки, p, q=1 - p - это вероятности символов источника ввода, и где:

- это средняя избыточность кода относительно оцененного распределения в уравнении (1) выше.

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

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

который является функцией от параметра источника p. Фиг. 5 является графиком, иллюстрирующим коэффициент избыточности адаптивного блочного кода с асимптотическим характером изменения, и иллюстрирует эту величину. Для укороченных блоков/выборок, производительность таких кодов становится чувствительной к асимметрии источника. Доказательство этой теоремы можно найти, например, в работе "Asymptotic average redundancy of adaptive block codes", Y.A. Reznik, W. Szpankowski, Proceedings of IEEE International Symposium on Information Theory (ISIT), 2003 год.

Далее поясняются примеры эффективных алгоритмов для реализации кодов, описанных выше. В модели без запоминания вероятность слова w (или его оценки) зависит только от весового коэффициента k, а не от фактической комбинации его битов. Следовательно, с учетом набора всех возможных n-битовых слов, можно разбивать набор на n + 1 групп:

содержащих слова с одинаковым весовым коэффициентом (k=0,..., n) и с одинаковой вероятностью. Размеры таких групп равны . Для дополнительного удобства предполагается, что каждая группа W_n,k сохраняет слова в лексикографическом порядке. Значение I_n,k(w) обозначает индекс (позицию) слова w в группе W_n,k . Таблица 6 является примером кода, составляемого для 4 - битовых блоков с вероятностями Бернулли: p^kq ^n-k, p=0,9.

Таблица 6
Пример кода, составляемого для 4-битовых блоков с вероятностями Бернулли: pkqn-k, p=0,9

Примерный код в таблице 6 должен быть использован для того, чтобы описывать структуру предложенного отображения между словами в группе W_n,k и ее кодовыми словами в соответствии с определенными аспектами этого раскрытия сущности. Код составлен с помощью модификации алгоритма Хаффмана, в который дополнительные этапы вставлены для того, чтобы обеспечить то, что кодовые слова, находящиеся на одном уровне, имеют такой же лексикографический порядок, как входные блоки, которые они представляют. Хорошо известно, что такое переупорядочение возможно без какой-либо потери эффективности сжатия. Примеры предшествующих алгоритмов, которые использовали эту идею переупорядочения, включают в себя коды Хаффмана - Шеннона - Фано и канонические коды, описанные Моффатом и Турпиным.

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

Пример группы обозначен ссылкой с номером 66 на фиг. 6. Примеры первой и второй подгрупп обозначены ссылками с номерами 68A, 68B, соответственно, на фиг. 6. Аналогичные группы и подгруппы предусмотрены для каждого весового коэффициента в рамках кодового дерева. Группа содержит блоки, имеющие одинаковый весовой коэффициент k. Подгруппа содержит блоки, имеющие одинаковый весовой коэффициент и одинаковый уровень в кодовом дереве. Это вытекает из того факта, что все слова в группе W_n,k имеют одинаковую вероятность и так называемое братское свойство кодов Хаффмана. Это наблюдение также справедливо для кодов Шеннона, обобщенных кодов Шеннона и, возможно, других алгоритмов. Как упомянуто выше, группа W_n,k включает в себя самое большее две подгруппы, содержащие кодовые слова одинаковой длины, и может быть представлена как:

где - это наименьшая длина кода, которая может быть назначена блокам из группы W_n,k. Кроме того, поскольку слова в группе W_n,k следуют лексикографическому порядку, то разбиение между W_n,k,l и W _{n,k, l+1} является простым:

где n_k обозначает размер подгруппы с более короткими кодовыми словами. Следовательно, если первая подгруппа имеет три кодовых слова с длиной 3, а вторая подгруппа в той же группе имеет одно кодовое слово с длиной 4, то n_k (размер подгруппы с более короткими кодовыми словами, т.е. первой подгруппы) равно 3. Этот пример соответствует подгруппам в группе, связанной с уровнями 3 и 4 кодового дерева по фиг. 6, где подгруппа 68A имеет кодовые слова 001, 010 и 011 с длиной по три каждое, а подгруппа 68B имеет кодовое слово 0001 с длиной четыре.

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

где w_i - это i - й блок в группе W_n,k. Отметим, что, как пояснено выше, оставшиеся кодовые слова в обеих подгруппах могут быть вычислены следующим образом:

В качестве иллюстрации, предполагается, что есть первая подгруппа 68A с тремя кодовыми словами длины 3 и вторая подгруппа 68B с одним кодовым словом длины 4, к примеру, как в примере уровней 3 и 4 кодового дерева по фиг. 6. В этом случае, если позиция данного блока - это i=2, то i<n _k (n_k равно 3), и результирующее кодовое слово является применимым базовым кодовым словом + i. В этом примере, базовое кодовое слово для подгруппы равно 001, а результирующее кодовое слово равно 001+2=011. Для уровней 3 и 4 кодового дерева на фиг. 6, если позицией применимого кодового слова являлось i>=n_k, то кодовое слово должно быть во второй подгруппе и должно равняться базовому кодовому слову 0000+i-n_k, которое равно 0000+4-3=0001.

Базовые кодовые слова задаются только посредством непустых подгрупп, и число таких подгрупп S в дереве, составляемом для n-битовых блоков, находится в пределах:

Помимо этого, несколько подгрупп могут постоянно размещаться на одном уровне, и число таких соотнесенных подгрупп не может быть больше n+1. На 10-м уровне дерева на фиг. 6, например, есть две подгруппы, соответствующие кодовым словам 1110 и 1111. Тем не менее, эти подгруппы не принадлежат к одной группе. Это является существенным отличием от других алгоритмов, которые назначают единственные базовые кодовые слова для каждого уровня, но затем требуют таблицы переупорядочения размера O(n2 ⁿ), чтобы работать с этими кодами. В данном случае вся структура имеет размер O(n²) битов.

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

С учетом вышеприведенного пояснения ниже описан простой алгоритм для прямого вычисления блочных кодов. Предполагается, что параметры n_k(0 k n) доступны и что уровень l и базовое кодовое слово B_n,k,l может быть получено для каждой непустой подгруппы. Затем, процесс кодирования блока w может быть выполнен, по существу, посредством набора следующих этапов:

1. С учетом блока w получение его весового коэффициента k и индекса I_n,k(w ).

2. Если I_n,k(w)< n_k, выбор первой подгруппы W_n,k,l ; иначе, выбор второй подгруппы W_n,k,l+1.

3. После этого, извлечение базового кодового слова (B_n,k,l или B_n,k,l-1) для выбранной подгруппы (W_n,k,l или W _n,k,l+1), и вычисление применимого кода согласно следующему уравнению:

Согласно вышеприведенному уравнению, если позиция i=I_n,k(w) блока w в выбранной подгруппе (W_n,k,l или W_n,k,l+1) меньше, чем число n_k блоков в подгруппе, то кодовое слово - это B_n,k,l +i. Альтернативно, если позиция i блока w в выбранной подгруппе (W_n,k,l или W _n,k,l+1) больше или равна числу n_k блоков в подгруппе, то кодовое слово - это B_n,k,l+1 + i-n_k.

Как описано ранее, в качестве иллюстрации, для уровней 3 и 4 кодового дерева по фиг. 6, вышеупомянутый процесс предоставляет в результате кодовое слово 011, когда позиция данного блочного кода - это i=2<n_k, и кодовое слово 0001, когда позиция данного блочного кода - это i=3>=n_k . В этом примере n_k равно 3, т.е. число кодовых слов в первой подгруппе 68A для весового коэффициента k =1. Порядок позиции i развивается лексикографически, начиная с базового кодового слова, к примеру, от 0 до 3 в случае весового коэффициента k=1 в примере по фиг. 6. В частности, позиция 0 соответствует базовому кодовому слову 001, позиция 1 соответствует кодовому слову 010, позиция 2 соответствует кодовому слову 011, все находятся в первой подгруппе 68A (i<n _k), а позиция 3 соответствуют кодовому слову 0001 в подгруппе 68B (i>=n_k).

Этот процесс может быть легко выполнен посредством обеспечения того, что кодовые слова, находящиеся на одном уровне, переупорядочиваются так, чтобы они имели такой же лексикографический порядок, как входные блоки, которые они представляют. Например, кодовые слова, описанные выше, следуют лексикографическому порядку входных блоков 0001, 0010, 0100 и 1000. Далее, лексикографически наименьшие кодовые слова в каждой подгруппе, к примеру, 001 в подгруппе 68A или 0001 в подгруппе 68B, могут использоваться в качестве базовых кодовых слов в целях вычисления кодового слова, описанного выше. Программный код на языке C, представляющий примерную реализацию процесса прямого составления блочных кодов, описанного выше, изложен в таблице 7 ниже.

Таблица 7
Процесс для прямого составления блочных кодов

В вышеупомянутом коде на языке C значение k указывает весовой коэффициент блока w, значение i указывает позицию (I_n,k(w)) блока в группе с весовым коэффициентом k, а nk[ k] указывает число кодовых слов в первой подгруппе группы с весовым коэффициентом k. Если i больше чем или равен nk[k], то i уменьшен так, чтобы корректировать индекс, и подгруппа задается равной второй подгруппе (1) для соответствующего весового коэффициента k. Эта вторая подгруппа идентифицируется посредством j=sg[k][1]. Если i меньше nk[k], i не уменьшается, и подгруппа задается равной первой подгруппе (0) для применимого весового коэффициента k. Эта первая подгруппа идентифицируется посредством j=sg[k][0].

После этого кодовое слово формируется как сумма базового кодового слова для применимой подгруппы j (base[j ]) и значения i. Для примера по фиг. 6, если значение i равно 2, то код должен быть суммой базового кодового слова 001 для подгруппы 68A и значения i (2), которое равно 001+010=011. В отношении уравнения (13), в зависимости от подгруппы, базовое кодовое слово - это B_n,k,l или B_n,k,l+1, а значение i - это i или i - nk[k]. Следовательно, вышеупомянутый код, в общем, соответствует результату, предоставляемому посредством уравнения (13). После вычисления кодового слова (code) длина (len) кодового слова указывается как len[j], что является длиной кода для соответствующей подгруппы, где вторая подгруппа имеет длину кода, которая больше, чем для первой подгруппы. Далее, процесс кодирования записывает коды в поток битов через операцию put_bits(code, len, bs), которая записывает значение code и len в поток битов bs. Поток битов передается для декодирования посредством другого устройства. Процесс возвращает весовой коэффициент k для вычисления следующего кодового слова.

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

С точки зрения запоминающего устройства процессу, показанному в таблице 7, требуется только S базовых кодовых слов (длиной в O(n) битов), n + 1 значений nk (длиной в O(n) бито), S длин кода (длиной в O(log n) битов) и 2( n+1) индексов подгруппы (длиной в O(log n) битов). Дополнительное уменьшение памяти возможно посредством сохранения возрастающих значений базовых кодовых слов, как пояснено в другом месте в этом раскрытии сущности. Учитывая, что S =O(n), вся структура данных требует только O (n₂) битов. В конкретной реализации, показанной в таблице 7, при условии, к примеру, что n=20 и S =32, размер этой структуры данных становится равен 244 байтам. Это гораздо меньше, чем 220 слов, которые потребовались бы для того, чтобы представлять этот код в форме прямой таблицы. Для достаточно коротких блоков, к примеру n<=12...16, вычисление весовых коэффициентов и индексов (функции weight(.) и index(.,.) в процессе таблицы 7) может быть вопросом одного поиска. В этом случае весь процесс кодирования, возможно, требует самое большее одного сравнения, двух сложений и четырех поисков.

Для больших блоков может использоваться следующая известная комбинаторная формула:

где w_j представляет отдельные биты слова w, и предполагается, что =0 для всех k>n. Чтобы реализовать эту формулу, можно или предварительно вычислять все биномиальные коэффициенты до уровня n в треугольнике Паскаля, или вычислять их динамически с помощью следующих простых тождеств:

Реализация на основе заранее вычисленных коэффициентов требует слов (O(n3) битов) памяти и O (n) сложений. Динамическое вычисление коэффициентов должно потребовать O(n) сложений, умножений и делений. Тем не менее, весь процесс может требовать только нескольких регистров и не требовать статической памяти. Дополнительное пояснение сложности вычисления индекса можно найти в работе T. Tjalkens "Implementation cost of the Huffman - Shannon - Fano code", in Proc. Data Compression Conference (DCC'05) (Snowbird, Utah, 29-31 марта 2005 года) 123-132.

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

где T - это длина машинного слова (T>maxl). В таком случае примерный процесс декодирования может быть описан следующим образом:

1. Нахождение самой верхней подгруппы с меньше, чем T битов, в потоке битов.

2. Декодирование индекса блока I_n,k(w) на основе уравнения (13) выше.

3. Формирование восстановленного блока с помощью его весового коэффициента k и индекса.

Код на языке C, представляющий примерную реализацию процесса декодирования, описанного выше, предоставлен в таблице 8.

Таблица 8
Декодирование блочных кодов

Примерный процесс декодирования, показанный в таблице 8, использует выровненные по левому краю базовые кодовые слова lj_base[S]. При работе процесс декодирования принимает содержимое val буфера потоков битов и идентифицирует подгруппу в кодовом дереве, имеющую базовое кодовое слово, соответствующее содержимому val буфера потоков битов. Например, процесс продолжает проходить вниз через подгруппы на различных уровнях в кодовом дереве до тех пор, пока базовые кодовые слова превышают принимаемое кодовое слово val. Когда подгруппа с базовым кодовым словом, которое меньше или равно val, достигнута, тем не менее, эта подгруппа выбирается. После обнаружения соответствующей подгруппы процесс определяет длину кода для подгруппы и затем прокручивает поток битов на эту длину так, чтобы пропускать декодированные биты и изолировать кодовое слово. Процесс декодирования определяет позицию индекса i кодового слова в подгруппе посредством вычитания значения базового кодового слова из содержимого буфера потоков битов.

Если кодовое слово - это 011, а базовое кодовое слово - это 010, например, то результат этой разности равен 2, указывая то, что кодовое слово находится в позиции 2 среди возможных позиций 0, 1 и 2 в подгруппе. Для примера 32-битового регистра эта разность может быть сдвинута вправо на 32 минус длина кода len. Процесс декодирования после этого извлекает применимый весовой коэффициент k и индекс подгруппы j и восстанавливает индекс i. Процесс далее формирует i-е слово в выбранной группе как кодовое слово и возвращает весовой коэффициент k. Выражение kj[j].k возвращает весовой коэффициент подгруппы, а выражение kj[j].j возвращает индекс подгруппы или как 0, или как 1, указывая или первую подгруппу (0), или вторую подгруппу (1) для данного весового коэффициента. Если вторая подгруппа выбрана так, что j =1, то индекс i корректируется посредством прибавления значения nk[k]. В противном случае, индекс i не корректируется, если первая подгруппа выбрана. Функция word() возвращает i-ое слово в группе n, k в качестве декодированного значения слова, к примеру, используя уравнение (13) выше.

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

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

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

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

В конце процесса декодирования, как описано выше, весовой коэффициент k и индекс I_n,k( w) для кодового слова преобразуются в фактические значения (к примеру, посредством функции word() в таблице 8). Если блоки являются достаточно короткими, это может быть осуществлено посредством простого поиска. В противном случае слово может быть синтезировано посредством использования формулы перечисления, к примеру, как описано в работе D. A. Huffman "A method for the construction of minimum - redundancy codes". Proc. IRE, 40 (сентябрь 1952 года) 1098-1101. С точки зрения сложности этот процесс аналогичен вычислению индекса в кодере.

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

1. Нет контекста, т.е. реализуется универсальный код.

2. Контекст задается посредством одного ранее наблюдаемого блока, т.е. t=n.

3. Контекст задается посредством двух ранее наблюдаемых блоков, т.е. t=2n.

Вместо использования фактических блоков в качестве контекстов достаточно (вследствие природы источника без запоминания) использовать их весовые коэффициенты. Это означает, что для t - битовых выборок предусмотрена матрица из t+1 структур кода, индексированная посредством их весовых коэффициентов s. Чтобы дополнительно сэкономить свободное место, симметрия KT - распределений относительно s и k может быть использована. В частности, процесс может заменять s =t-s и переключать биты (т.е. принудительно задавать k=n-k) каждый раз, когда s>t/2. Таким образом, необходимо задавать только t/2+1 таблиц. В этом примере общий объем памяти, требуемый посредством адаптивного кода, становится 1+n/2+1+n+1=1,5n+3 таблицы. Конкретные оценки памяти для размеров блоков n=8...20 показаны в таблице 9 ниже.

Таблица 9
Оценки использования памяти (в байтах) для различных размеров блока

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

Экспериментальные результаты оценки производительности процесса адаптивного кодирования, описанного в данном документе, при размере блока n=16 описываются далее и сравниваются с другими известными алгоритмами. В частности, процесс адаптивного кодирования сравнивается с алгоритмом 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 для видеосжатия.

Чтобы выполнять испытания, создаваемые компьютером последовательности битов использовались для того, чтобы моделировать вывод из двоичного источника Бернулли с вероятностью p. Длины таких последовательностей колеблются от 16 до 1024, и для каждой конкретной длины сформировано Q = 1000000 выборок этих последовательностей. Относительные коэффициенты избыточности вычислены следующим образом:

Для процесса адаптивного кодирования, описанного в этом раскрытии сущности, использовалась следующая структура контекстов:

1) первый 16 - битовый блок кодирован без контекста (универсальный код);

2) второй блок кодирован, используя первый в качестве своего контекста (код при t=16); и

3) третий и все последующие блоки кодированы, используя два предыдущих блока в последовательности в качестве контекстов (основанный на выборке код при t=32).

Фиг. 7A и 7B являются графиками, иллюстрирующими сравнение коэффициентов избыточности адаптивного блочного кода с методиками Q - кодера и CABAC при различных значениях p . Фиг. 7A показывает результаты для p=0,1, тогда как фиг. 7B показывает результаты для p=0,5. Фиг. 8 является графиком, иллюстрирующим чувствительность избыточности к асимметрии исходных данных для методик адаптивного блочного кода, Q - кодера и CABAC. Результаты экспериментального исследования показаны на фиг. 7A, 7B и 8. Фиг. 7A и 7B графически иллюстрируют число битов, кодированных по оси X, в сравнении с (средняя длина кода - энтропия)/энтропия на оси Y.

Фиг. 8 графически иллюстрирует вероятность на оси X в сравнении с (средняя длина кода - энтропия)/энтропия на оси Y. Каждый график на фиг. 7A, 7B, и 8 показывает графики для Q - кодера, CABAC и адаптивного кодирования с соответствующими пометками. Из экспериментальных результатов можно заметить, что адаптивный код, описанный в этом раскрытии сущности, может иметь намного более высокую скорость конвергенции, чем алгоритмы Q - кодера и CABAC. Процесс адаптивного кодирования превосходит по быстродействию алгоритмы Q - кодера и CABAC для более коротких последовательностей и становится сопоставимым с алгоритмами Q - кодера и CABAC, когда общая длина кодированных битов достигает 1024. Как дополнительно показано на фиг. 8, после 160 кодированных битов (или в таком случае 16 - битовых блоков) процесс адаптивного кодирования может предоставлять меньшую избыточность по сравнению с алгоритмами Q - кодера и CABAC. Этот характер изменения соответствует теореме 1, поясненной выше.

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

Как показано на фиг. 9, процессор получает алфавит входных символов, которые должны быть кодированы (70). Символы имеют соответствующие весовые коэффициенты, указывающие вероятность или частоту наличия или использования символов в данном наборе или последовательности данных. После определения применимых весовых коэффициентов символов (72) процесс назначает индексы символам на основе их весовых коэффициентов (74) и назначает коды символам на основе индексов и лексикографического порядка символов (76). Следовательно, символы, имеющие одинаковые весовые коэффициенты, могут быть упорядочены лексикографически для того, чтобы упрощать методы кодирования, описанные в этом раскрытии сущности.

Коды могут быть организованы согласно структуре кода, представленной посредством двоичного кодового дерева. Процессор идентифицирует базовое кодовое слово для каждого уровня в кодовом дереве (78). Базовое кодовое слово - это наименьшее кодовое слово на данном уровне в дереве и соответствует лексикографически самому раннему символу среди символов на этом уровне в дереве. Чтобы предоставлять компактную структуру данных, процессор удаляет фиксированное число B начальных битов из базовых кодовых слов, чтобы сформировать частичные базовые кодовые слова (80). Базовые кодовые слова могут быть сформулированы как выровненные по левому краю кодовые слова, и начальными битами могут быть M начальных битов, идущих справа налево в выровненных по левому краю кодовых словах. В некоторых реализациях число начальных битов, которые удаляются, может быть 8. В других реализациях число начальных битов, которые удаляются, может быть меньше или больше чем 8.

Для многих уровней кодового дерева M начальных битов являются нулями. На некоторых уровнях, тем не менее, начальные биты могут формировать все или часть базового кода для соответствующего уровня в дереве. На этих выбранных уровнях процессор формирует индикаторы пропуска (82). Индикаторы пропуска предоставляют инструкцию для декодера, чтобы прокручивать поток битов на B битов так, чтобы базовый код не терялся при удалении B начальных битов. Процесс может сохранять, в структуре данных, результирующие частичные базовые кодовые слова, длины, связанные с кодовыми словами на соответствующих уровнях кодового дерева, смещения, указывающие индексы соответствующих символов, связанных с кодовыми словами в кодовом дереве, и один или более индикаторов пропуска, которые указывают, когда поток битов должен быть прокручен на B битов, чтобы не допускать потерю базового кодового слова, которое попадает, по меньшей мере, частично в пределы B начальных битов (84). Структура данных может быть предоставлена в модуль 46 энтропийного кодирования и модуль 52 энтропийного декодирования, чтобы помочь при выполнении операций кодирования и энтропийного декодирования с составленными переменными кодами. Структура данных может принимать множество форм, включая одну или более одно- или многомерных таблиц поиска, связные списки, двоичные деревья, базисные деревья, неструктурированные файлы и т.п.

Фиг. 10 является блок-схемой последовательности операций, иллюстрирующей способ для кодирования символов с помощью кодов переменной длины, составляемых согласно способу по фиг. 9, в соответствии с первым общим аспектом этого раскрытия сущности. Как показано на фиг. 10, модуль 46 энтропийного кодирования принимает символ (86), определяет индекс для символа (87) и сравнивает индекс символа с таблицей смещения, чтобы идентифицировать соответствующий уровень в кодовом дереве. В частности, модуль 46 энтропийного кодирования определяет, больше ли индекс символа или равен смещению для данного уровня дерева (88). Индекс символа представляет порядок символа среди других символов, ранжированных в порядке весового коэффициента, при этом символы одного весового коэффициента упорядочиваются лексикографически согласованно с символьным алфавитом. Смещение - это разность между длиной кода или кодов для применимого уровня дерева и максимальной длиной кода. В дереве на фиг. 4, если максимальная длина кода равна 16, например, и длина кода на уровне 3 дерева равна 3, то применимое смещение для базового кодового слова равно 12.

Если индекс символа не превышает смещение для текущего уровня дерева, модуль 46 энтропийного кодирования переходит вниз к следующему уровню (90) кодового дерева в нисходящем поиске и повторяет сравнение индекса символа со смещением для этого следующего уровня (88). Когда модуль 46 энтропийного кодирования определяет то, что индекс символа больше чем или равен смещению для конкретного уровня кодового дерева (88), модуль энтропийного кодирования вычисляет соответствующее кодовое слово для символа. В частности, модуль 46 энтропийного кодирования задает кодовое слово для символа равным сумме базового кодового слова для текущего уровня дерева плюс разность между индексом символа и смещением для этого уровня (92).

Используя примерное дерево по фиг. 4, если индекс символа равен 14, модуль 46 энтропийного кодирования определяет то, что код для символа постоянно размещается на уровне 3 дерева, поскольку 14 больше, чем смещение в 12, назначенное базовому кодовому слову для этого уровня. Модуль 46 энтропийного кодирования затем вычисляет кодовое слово как базовое кодовое слово (001) + (индекс символа (14) - смещение (12)), т.е. 001+2+001+010=011. После задания кода для принимаемого символа (92) модуль 46 энтропийного кодирования выводит кодовое слово в поток битов (94) для передачи, к примеру, в приемное устройство с помощью модуля 52 энтропийного декодирования. Модуль 46 энтропийного кодирования затем повторяет процесс для следующего символа в применимой последовательности данных.

Фиг. 11 является блок-схемой последовательности операций, иллюстрирующей способ для декодирования кодов переменной длины, составляемых согласно способу по фиг. 9, в соответствии с первым общим аспектом этого раскрытия сущности. Способ, показанный на фиг. 11, может быть выполнен с помощью алгоритма, идентичного или аналогичного показанному в таблице 5. В примерной реализации коды могут быть приняты посредством модуля 52 энтропийного декодирования и кодированы посредством модуля 46 энтропийного кодирования так, как описано со ссылкой на фиг. 10. Способ, проиллюстрированный на фиг. 11, может использовать эффективные по использованию памяти методы декодирования, описанные в этом раскрытии сущности, и может воспользоваться преимуществом компактной структуры данных, с которой могут быть составлены такие коды. Как показано на фиг. 11, модуль 52 энтропийного декодирования принимает кодовое слово из входящего потока битов (96). Кодовое слово может быть получено из фиксированной ширины W битов, извлеченных от буфера потоков битов. Кодовое слово может быть выровнено по левому краю или преобразовано в выровненный по левому краю формат, и ширина W может быть сокращена за счет удаления B начальных битов из кодового слова справа налево.

Модуль 52 энтропийного декодирования сравнивает кодовое слово с базовыми кодовыми словами для различных уровней кодового дерева, начиная с верхнего уровня и продолжая глубже в дерево в нисходящем поиске до тех пор, пока соответствующее базовое кодовое слово не будет найдено. В частности, модуль 52 энтропийного декодирования может определять то, меньше или равно ли базовое кодовое слово для текущего уровня дерева кодовому слову (98). Если нет, модуль энтропийного декодирования продвигается вниз к следующему уровню дерева (100) и повторяет сравнение (98) для базового кодового слова, связанного со следующим уровнем. После перехода к следующему уровню (100), тем не менее, модуль 52 энтропийного декодирования определяет то, является ли индикатор пропуска (102) связанным с текущим уровнем. Если так, модуль 52 энтропийного декодирования прокручивает буфер потоков битов на фиксированное приращение (104) до перехода к следующему уровню (100). В частности, модуль 52 энтропийного декодирования может прокручивать буфер потоков битов на M битов так, чтобы кодовое слово не терялось вследствие отбрасывания M начальных битов. Если нет индикатора пропуска (102), модуль 52 энтропийного декодирования просто переходит к следующему уровню (100).

Так или иначе, модуль 52 энтропийного декодирования снова сравнивает кодовое слово с базовым кодовым словом для текущего уровня (98). Когда модуль 52 энтропийного декодирования находит уровень, на котором базовое кодовое слово меньше или равно кодовому слову (98), модуль 52 энтропийного декодирования определяет остаточную длину базовых кодовых слов на соответствующем уровне (106) и прокручивает поток битов на остаточную длину (108). Модуль 52 энтропийного декодирования затем вычисляет символ, связанный с кодовым словом (110), на основе смещения для уровня и разности между базовым кодовым словом и декодируемым кодовым словом.

В отношении дерева на фиг. 4, например, если кодовое слово равно 0110000000000000, то частичное обрезанное кодовое слово с отброшенными 8 начальными битами равно 01100000. В этом случае модуль 52 энтропийного декодирования идентифицирует частичное базовое кодовое слово на уровне 3 (00100000) как меньшее чем или равное кодовому слову и идентифицирует остаточную длину в 3. Модуль 52 энтропийного декодирования прокручивает поток битов на 3 бита вперед, чтобы принимать следующее кодовое слово. Помимо этого, модуль 52 энтропийного декодирования вычисляет символ для кодового слова посредством прибавления смещения для уровня 3 к разности между кодовым словом в буфере потоков битов и базовым кодовым словом для уровня. Например, модуль 52 энтропийного декодирования вычисляет код как offset[3]=12 плюс кодовое слово 01100000 минус 00100000, что эквивалентно 12 плюс 2=14. В этом случае 14 - это индекс символа, представленного посредством кода 011.

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

Фиг. 12 является блок-схемой последовательности операций, иллюстрирующей способ для составления адаптивных блочных кодов в соответствии со вторым общим аспектом этого раскрытия сущности. Способ по фиг. 12 может быть реализован в процессоре в устройстве кодирования или в процессоре общего назначения, чтобы поддерживать эффективное, прямое составление адаптивных блочных кодов. Как показано на фиг. 12, процессор получает набор слов (112), которые должны быть кодированы. Структура данных, представляющая результирующую структуру кода, может быть сохранена в запоминающем устройстве в рамках устройства кодирования, устройства декодирования или и того, и другого. Слова могут быть блоками двоичных кодов. После определения весовых коэффициентов слов (114) процессор назначает группы кодового слова словам на основе весовых коэффициентов (116). Группы кодового слова включают в себя кодовые слова для слов с одинаковым весовым коэффициентом k и могут охватывать два смежных уровня кодового дерева, к примеру, как показано на фиг. 6.

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

Процессор идентифицирует базовое кодовое слово для каждой подгруппы (120). Базовое кодовое слово - это наименьшее кодовое слово в подгруппе. В примере по фиг. 6 базовое кодовое слово для подгруппы 68A - это 001. Тем не менее, подгруппа 68A дополнительно включает в себя кодовые слова 010 и 011 в дополнение к базовому кодовому слову 001. В этом примере кодовые слова в подгруппе упорядочиваются на основе лексикографического порядка слов, которые они представляют, так что коды могут быть легко и непосредственно вычислены при условии относительно небольшого объема вычислений.

Число элементов в первой подгруппе каждой группы может использоваться для того, чтобы вычислять кодовые слова. С этой целью процессор сохраняет число элементов в первой подгруппе каждой группы (122), а также сохраняет отображение индекса группы (124), отображение длины кода подгруппы (126) и отображение базового кодового слова подгруппы (128). Отображение индекса группы может идентифицировать позицию кодового слова для слова в группе, в которой кодовое слово постоянно размещается. Отображение длины кода подгруппы может идентифицировать длину кодов в рамках конкретной подгруппы. Отображение базового кодового слова подгруппы может идентифицировать базовое кодовое слово, связанное с каждой подгруппой. В общем, код может быть составлен из базового кодового слова для конкретной подгруппы с учетом индекса слова в группе. Сохраненная информация может быть сохранена в структуре данных, к которой может осуществлять доступ кодер, декодер или и то, и другое.

Фиг. 13 является блок-схемой последовательности операций, иллюстрирующей способ для кодирования блоков с помощью кодов переменной длины, составляемых согласно способу по фиг. 12, и в соответствии со вторым общим аспектом этого раскрытия сущности. Способ по фиг. 13 может быть реализован, например, в модуле энтропийного кодирования, таком как модуль 46 энтропийного кодирования по фиг. 2. Способ, показанный на фиг. 13, может быть выполнен с помощью алгоритма, идентичного или аналогичного показанному в таблице 7. Как показано на фиг. 13, для того чтобы кодировать данное слово, модуль 46 энтропийного кодирования получает свой весовой коэффициент (130) и индекс группы (132). Используя весовой коэффициент слова, модуль 46 энтропийного кодирования определяет индекс группы для слова (132) в рамках применимого кодового дерева. Индекс группы I _n,k(w) указывает индекс (позицию) слова w в группе W_n,k, которая сохраняет слова в лексикографическом порядке.

Модуль 46 энтропийного кодирования сравнивает индекс группы с числом элементов n_k в первой подгруппе группы, в которой постоянно размещается кодовое слово для входного слова. В частности, модуль 46 энтропийного кодирования определяет то, является ли индекс группы большим чем или равным числу элементов в первой подгруппе (134). Если так, модуль 46 энтропийного кодирования выбирает вторую подгруппу (138), т.е. подгруппу 1, в группе и снижает значение индекса группы (140). В частности, значение индекса группы снижается на число элементов в первой подгруппе n_k. Если индекс группы не больше чем или равен числу элементов в первой подгруппе (134), модуль 46 энтропийного кодирования выбирает первую подгруппу (136), т.е. подгруппу 0. Каждая подгруппа имеет собственное базовое кодовое слово. Модуль 46 энтропийного кодирования получает базовое кодовое слово для выбранной подгруппы (142) и вычисляет кодовое слово на основе суммы базового кодового слова и значения индекса группы (144).

В отношении примерного кодового дерева по фиг. 6, в качестве иллюстрации, если предполагается, что весовой коэффициент слова, которое должно быть кодировано, равен 2, то значение индекса группы равно 2 и число элементов в первой подгруппе равно 3, к примеру, соответствуя группе на уровнях 3 и 4 кодового дерева. В этом случае модуль 46 энтропийного кодирования выбирает первую подгруппу (подгруппу 0), поскольку значение индекса группы (2) меньше числа элементов (3) в первой подгруппе. Как результат, базовое кодовое слово - это 001. Чтобы кодировать слово, модуль 46 энтропийного кодирования прибавляет значение индекса группы равное 2 к базовому кодовому слову 001, имея результатом кодовое слово 011.

Для той же группы, если значение индекса группы равно 3, модуль 46 энтропийного кодирования должен выбирать вторую подгруппу (подгруппу 1). Тем не менее, модуль 46 энтропийного кодирования должен уменьшать на значение индекса группы на число n_k элементов в первой подгруппе (подгруппе 0). В этом случае значение индекса группы 3 должно быть сокращено на 3 до нуля, и кодовое слово должно быть вычислено как базовое кодовое слово в 0001 для второй подгруппы плюс значение индекса группы равное 0, имея результатом кодовое слово в 0001.

В дополнение к вычислению кодового слова для входного слова, модуль 46 энтропийного кодирования может получать длину кодов в выбранной подгруппе (146). В примере выше, для подгруппы 0 на уровне 3, длина кодов должна быть равной 3. Модуль энтропийного кодирования выводит вычисленное кодовое слово и длину кода подгруппы в поток битов для хранения и/или передачи в другое устройство, такое как устройство декодирования, включающее в себя модуль энтропийного декодирования, такой как модуль 52 энтропийного декодирования.

Фиг. 14 является блок-схемой, иллюстрирующей способ для декодирования кодов переменной длины, составляемых согласно способам по фиг. 12 и фиг. 13, и в соответствии со вторым общим аспектом этого раскрытия сущности. Способ, показанный на фиг. 14, может быть выполнен с помощью алгоритма, идентичного или аналогичного показанному в таблице 8. Коды переменной длины могут быть приняты от устройства кодирования, такого как устройство кодирования, включающее в себя модуль 46 энтропийного кодирования. Коды переменной длины могут быть приняты и декодированы посредством модуля 52 энтропийного декодирования. Как показано на фиг. 14, модуль 52 энтропийного декодирования принимает кодовое слово от входящего потока битов (150) и сравнивает кодовое слово с базовым кодовым словом подгруппы. В частности, модуль 52 энтропийного декодирования может выполнять поиск в соответствующем кодовом дереве, чтобы идентифицировать выровненное по левому краю базовое кодовое слово подгруппы, которое меньше или равно содержимому кодового слова, полученному из буфера потоков битов (152).

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

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

В качестве примера, в отношении кодового дерева по фиг. 6, если входящее кодовое слово - это 0110000000000000, модуль 52 энтропийного декодирования идентифицирует базовое кодовое слово 0010000000000000 как самое верхнее базовое кодовое слово подгруппы, которое меньше или равно кодовому слову. Это базовое кодовое слово связано с первой подгруппой в группе на уровнях 3 и 4. После определения длины кода (3) подгруппы, связанной с базовым кодовым словом, модуль 52 энтропийного декодирования может прокручивать поток битов, чтобы пропускать декодированные биты. Модуль 52 энтропийного декодирования может определять индекс группы кодового слова посредством вычитания базового кодового слова из кодового слова из потока битов. В этом примере 011 минус 001 дает в результате 010, который формирует значение индекса группы, равного 2.

Модуль 52 энтропийного декодирования также может определять весовой коэффициент кодового слова (160), к примеру, на основе уровня подгруппы в рамках кодового дерева. Помимо этого, модуль 52 энтропийного декодирования может определять индекс подгруппы (162), т.е. индекс выбранной подгруппы в рамках кодового дерева. Используя весовой коэффициент, позицию и индекс подгруппы, модуль 52 энтропийного декодирования определяет индекс слова (164), тем самым декодируя кодовое слово из потока битов, чтобы сформировать слово, представленное посредством кодового слова. К тому же, в некоторых реализациях, способ декодирования, выполняемый посредством модуля 52 энтропийного декодирования, может соответствовать процессу, показанному в таблице 8.

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

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

Методы, описанные в данном документе, могут быть реализованы в аппаратных средствах, программном обеспечении, микропрограммном обеспечении или в любой их комбинации. Такие методы могут быть реализованы в любых из множества устройств, таких как компьютеры общего назначения, переносные телефонные аппараты для беспроводной связи или устройства на интегральных схемах, имеющие несколько применений, включая вариант применения в переносных телефонных аппаратах для беспроводной связи и других устройствах. Любые признаки, описанные как модули или компоненты, могут быть реализованы совместно в интегральном логическом устройстве или отдельно как дискретные, но имеющие возможность взаимодействовать логические устройства. Если реализованы в программном обеспечении, методы могут быть осуществлены, по меньшей мере, частично посредством машиночитаемого носителя хранения данных, содержащего программный код, включающий в себя инструкции, которые, когда приводятся в исполнение, выполняют один или более способов, описанных выше. Машиночитаемый носитель хранения данных может формировать часть компьютерного программного продукта. Машиночитаемые носители могут содержать оперативное запоминающее устройство (RAM), такое как синхронное динамическое оперативное запоминающее устройство (SDRAM), постоянное запоминающее устройство (ROM), энергонезависимое оперативное запоминающее устройство (NVRAM), электрически стираемое программируемое постоянное запоминающее устройство (EEPROM), флэш-память, магнитные или оптические носители хранения данных и т.п. Дополнительно или альтернативно, методы могут быть реализованы, по меньшей мере, частично посредством машиночитаемой среды связи, которая переносит или передает программный код в форме инструкций или структур данных и которая может быть доступна, считываема и/или приводима в исполнение посредством компьютера, к примеру, распространяемые сигналы или волны.

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

Описаны различные варианты осуществления раскрытия сущности. Эти и другие варианты осуществления находятся в пределах объема прилагаемой формулы изобретения.