БЫСТРЫЕ АЛГОРИТМЫ ДЛЯ ВЫЧИСЛЕНИЯ 5-ТОЧЕЧНОГО DCT-II, DCT-IV И DST-IV, И АРХИТЕКТУРЫ
FAST ALGORITHMS FOR COMPUTATION OF 5-POINT DCT-II, DCT-IV, AND DST-IV, AND ARCHITECTURES

Уровень техники
Испрашивание приоритета по §119 раздела 35 Кодекса законов США
K
Настоящая заявка на патент испрашивает приоритет предварительной заявки США № 61/013579, озаглавленной «Fast Algorithms for Computation of 5-Point DCT-II, DCT-IV, and DST-V, and Architecture for Design of Transforms of Size N=5*2», поданной 13 декабря 2007 г., предварительной заявки США № 61/016106, озаглавленной «Fast Algorithms for Computation of 5-point DCT-II, DCT-IV, and DST-IV, and Architecture for Design of Transforms of sizes N=5*2k», поданной 21 декабря 2007 г., и предварительной заявки США № 61/039194, озаглавленной «G.EV-VBR MDCT Module», поданной 25 марта 2008 г., обе переданы правопреемнику настоящей заявки и таким образом в явной форме включены в настоящий документ по ссылке.
Область техники, к которой относится изобретение
Нижеследующее описание, в основном, относится к кодерам и декодерам и, в частности, к эффективной реализации MDCT/IMDCT для речевых и аудиокодеков.
Уровень техники
Одной целью аудиокодирования является сжатие аудиосигнала до требуемого ограниченного количества информации, в то же время сохраняя насколько возможно исходное качество звука. В процессе кодирования аудиосигнал во временной области преобразуется в частотную область, и соответствующий процесс декодирования осуществляет такую обратную операцию.
В качестве части такого процесса кодирования сигнал может обрабатываться модифицированным дискретным косинусным преобразованием (MDCT). Модифицированное дискретное косинусное преобразование (MDCT) представляет собой преобразование, относящееся к анализу Фурье, основанное на дискретном косинусном преобразовании типа IV (DCT-IV), с дополнительным свойством, что блоки перекрываются, так что окончание одного блока совпадает с началом следующего блока. Это перекрытие способствует тому, чтобы избегать паразитных артефактов, и, в дополнение к свойствам уплотнения энергии дискретного косинусного преобразования (DCT), делает MDCT особенно привлекательным для применений сжатия сигнала.
Вокодеры работают с частотами дискретизации входного сигнала или 8 кГц, или 16 кГц, и с кадрами 10 или 20 миллисекунд. Следовательно, их банки фильтров MDCT представляют собой или 160-, или 320-точечные преобразования.
Однако, если будущие речевые кодеры будут поддерживать функциональную возможность переключения блоков, также может потребоваться поддержка прореженных размеров (например, 160, 80, 40 точек). Следовательно, эффективные реализации преобразований малых размеров желательны для реализации большего преобразования, использующего базовое преобразование малого размера.
Сущность изобретения
Нижеследующее представляет упрощенное изложение сущности одного или нескольких вариантов осуществления, чтобы обеспечить базовое понимание некоторых вариантов осуществления. Это изложение сущности не является исчерпывающим обзором всех рассматриваемых вариантов осуществления и не предназначено, чтобы определять ключевые или критические элементы всех вариантов осуществления, или определять объем любого или всех вариантов осуществления. Его единственной целью является представление некоторых принципов одного или нескольких вариантов осуществления в упрощенном виде в качестве вводной части к более подробному описанию, которое представлено ниже.
Способ и/или устройство кодирования обеспечиваются для вычисления значений преобразования. Принимаются входные значения временной области, представляющие аудиосигнал. Входные значения преобразуются в спектральные коэффициенты, используя модифицированное дискретное косинусное преобразование (MDCT), которое рекурсивно прореживается в множество 5-точечных преобразований. Могут быть реализованы многочисленные разложения для эффективной обработки 5-точечного преобразования.
В одном примере (фиг.5) по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (502), раскладываемое на двенадцать (12) операций сложения, восемь (8) операций умножения, и длину наибольшего пути в три (3) операции. Например, по меньшей мере одно из множества 5-точечных преобразований включает в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (502), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.6) по меньшей мере одно из множества 5-точечных преобразований включает в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (602), раскладываемое на двенадцать (12) операций сложения, пять (5) операций умножения, две (2) операции сдвига, и длину наибольшего пути в четыре (4) операции. Например, по меньшей мере одно из множества 5-точечных преобразований включает в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (602), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.7) по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (702), раскладываемое на двенадцать (12) операций сложения, пять (5) операций умножения, одну (1) операцию сдвига, и длину наибольшего пути в четыре (4) операции. Например, по меньшей мере одно из множества 5-точечных преобразований включает в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (702), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается тем, что имеет промежуточные результаты:
так что
В другом примере (фиг.8) по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (802), раскладываемое на двенадцать (12) операций сложения, четыре (4) операции умножения, две (2) операции сдвига, и длину наибольшего пути в четыре (4) операции. Например, по меньшей мере одно из множества 5-точечных преобразований включает в себя по меньшей мере одно дискретное косинусное преобразование типа II (DCT-II) (802), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
Альтернативно, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно преобразование (802), раскладываемое на двенадцать (12) операций сложения, пять (5) операций умножения, одну (1) операцию сдвига, и длину наибольшего пути в четыре (4) операции.
В другом примере (фиг.9) по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (902), раскладываемое на двадцать (20) операций сложения, шестнадцать (16) операций умножения, и длину наибольшего пути в три (3) операции. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (902), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
где
В другом примере (фиг.10) по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (1002), раскладываемое на двадцать (20) операций сложения, двенадцать (12) операций умножения, и длину наибольшего пути в четыре (4) операции. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1002), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
где
В другом примере (фиг.14) по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (1402), раскладываемое на шестнадцать (16) операций сложения, девять (9) операций умножения, и длину наибольшего пути в пять (5) операций. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1402), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.15), в котором по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (1502), раскладываемое на пятнадцать (15) операций сложения, десять (10) операций умножения, две (2) операции сдвига, и длину наибольшего пути в пять (5) операции. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1502), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.16) по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (1602/1702), раскладываемое на пятнадцать (15) операций сложения, одиннадцать (11) операций умножения, две (2) операции сдвига, и длину наибольшего пути в пять (5) операций. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1602), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.17) по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1702), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается по меньшей мере множеством промежуточных результатов:
так что
В другом примере (фиг.18) по меньшей мере одно из множества 5-точечных преобразований может включать в себя дискретное косинусное преобразование типа IV (DCT-IV) (1802), раскладываемое на пятнадцать (15) операций сложения, двенадцать (12) операций умножения, две (2) операции сдвига, и длину наибольшего пути в пять (5) операций. Например, по меньшей мере одно из множества 5-точечных преобразований может включать в себя по меньшей мере одно дискретное косинусное преобразование типа IV (DCT-IV) (1802), которое принимает входной вектор [x0, x1, x2, x3, x4] для получения выходного вектора [X0, X1, X2, X3, X4], и отличается промежуточными результатами:
так что
Кроме того, способ и/или устройство преобразования могут выполнять операцию создания окна над входными значениями перед выполнением преобразования, причем операция создания окна реализует функцию асимметричного окна.
В некоторых реализациях MDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное дискретное косинусное преобразование типа II.
В других реализациях MDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное дискретное косинусное преобразование типа IV.
В еще других реализациях MDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное дискретное косинусное преобразование типа II и 5-точечное дискретное косинусное преобразование типа IV.
В еще других реализациях MDCT реализует по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное дискретное синусное преобразование типа IV.
Способ и/или устройство декодирования обеспечиваются для вычисления значений обратного преобразования. Принимаются входные значения спектральных коэффициентов, представляющие аудиосигнал. Входные значения спектральных коэффициентов затем преобразуются в выходные значения временной области, используя обратное модифицированное дискретное косинусное преобразование (IMDCT), которое рекурсивно прореживается на множество 5-точечных обратных преобразований.
В одном примере (фиг.32) по меньшей мере одно из множества 5-точечных обратных преобразований может включать в себя по меньшей мере одно обратное дискретное косинусное преобразование типа II (DCT-II) (3202), раскладываемое на двенадцать (12) операций сложения, четыре (4) операции умножения, две (2) операции сдвига и длину наибольшего пути в четыре (4) операции. Например, по меньшей мере одно из множества 5-точечных обратных преобразований может включать в себя по меньшей мере одно обратное дискретное косинусное преобразование типа II (IDCT-II) (3202), которое принимает входной вектор [X0, X1, X2, X3, X4] для получения выходного вектора [x0, x1, x2, x3, x4], и отличается по меньшей мере множеством промежуточных результатов:
так что
Кроме того, способ и/или устройство преобразования могут выполнять операцию создания окна над входными значениями после выполнения обратного преобразования, причем операция создания окна реализует функцию асимметричного окна.
В одной реализации IMDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное обратное дискретное косинусное преобразование типа II.
В другой реализации IMDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное обратное дискретное косинусное преобразование типа IV.
В еще другой реализации IMDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное обратное дискретное косинусное преобразование типа II и 5-точечное обратное дискретное косинусное преобразование типа IV.
В одной реализации IMDCT может реализовывать по меньшей мере одно из 640-, 320-, 160-, 80-, 40-точечного преобразования, используя 5-точечное обратное дискретное синусное преобразование типа IV.
Краткое описание чертежей
Различные признаки, особенности и преимущества могут стать очевидными из подробного описания, изложенного ниже, при рассмотрении вместе с чертежами, на которых подобные позиции идентифицируют соответствующие элементы по всем чертежам.
Фиг.1 представляет собой блок-схему, иллюстрирующую пример кодера, который может включать в себя банк фильтров анализа MDCT.
Фиг.2 представляет собой блок-схему, иллюстрирующую пример того, как преобразование может быть реализовано меньшими преобразованиями.
Фиг.3 представляет собой блок-схему, иллюстрирующую пример декодера, который может включать в себя банк фильтров синтеза IMDCT.
Фиг.4 представляет собой блок-схему, иллюстрирующую пример того, как обратное преобразование может быть реализовано меньшими обратными преобразованиями.
Фиг.5 представляет собой блок-схему последовательности операций, иллюстрирующую первый пример разложения 5-точечного DCT-II преобразования.
Фиг.6 представляет собой блок-схему последовательности операций, иллюстрирующую второй пример разложения 5-точечного DCT-II преобразования.
Фиг.7 представляет собой блок-схему последовательности операций, иллюстрирующую третий пример разложения 5-точечного DCT-II преобразования.
Фиг.8 представляет собой блок-схему последовательности операций, иллюстрирующую альтернативный пример разложения 5-точечного DCT-II преобразования.
Фиг.9 представляет собой блок-схему последовательности операций, иллюстрирующую первый пример разложения 5-точечного DCT-IV преобразования.
Фиг.10 представляет собой блок-схему последовательности операций, иллюстрирующую второй пример того, как может быть реализовано 5-точечное DCT-IV преобразование.
Фиг.11 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование может отображаться на DCT-II преобразование для преобразования входных коэффициентов в выходные коэффициенты.
Фиг.12 представляет собой блок-схему, иллюстрирующую 5-точечное DCT-IV преобразование, которое может быть реализовано с использованием 5-точечного DCT-II преобразования для преобразования входных коэффициентов в выходные коэффициенты.
Фиг.13 представляет собой блок-схему, иллюстрирующую пример разложения 5-точечного DCT-IV преобразования по фиг.12, которое может быть реализовано с использованием 5-точечного DCT-II преобразования.
Фиг.14 представляет собой блок-схему, иллюстрирующую то, как отображение DCT-IV преобразования на фиг.13 может быть объединено с DCT-II преобразованием по фиг.6.
Фиг.15 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование по фиг.14 может быть дополнительно модифицировано в эквивалентное преобразование.
Фиг.16 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование по фиг.15 может быть дополнительно модифицировано в эквивалентное преобразование.
Фиг.17 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование по фиг.16 может быть дополнительно модифицировано в эквивалентное преобразование.
Фиг.18 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование по фиг.17 может быть дополнительно модифицировано в эквивалентное преобразование.
Фиг.19 представляет собой блок-схему, иллюстрирующую то, как преобразование размера N может рекурсивно разбиваться на меньшие преобразования размера N/2 до тех пор, пока оно не будет представлено множеством 5-точечных преобразований.
Фиг.20 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения преобразования, при котором 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших 5-точечных DCT-II преобразований.
Фиг.21 представляет собой блок-схему, иллюстрирующую то, как обратное преобразование размера N может рекурсивно разбиваться на меньшие обратные преобразования размера N/2 до тех пор, пока оно не будет представляться множеством 5-точечных обратных преобразований.
Фиг.22 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения обратного преобразования, при котором обратное 10-точечное IDCT-IV преобразование рекурсивно разбивается на множество меньших обратных преобразований 5-точечного IDCT-II.
Фиг.23 иллюстрирует форму асимметричного окна, которая может использоваться для снижения задержки, ассоциированной с этапом преобразования, до 10 мс, в то же время сохраняя такое же количество частотных коэффициентов.
Фиг.24 представляет собой блок-схему, иллюстрирующую устройство для вычисления значений преобразования.
Фиг.25 иллюстрирует пример способа кодирования сигнала, использующего MDCT преобразование, основанное на 5-точечном базовом преобразовании.
Фиг.26 представляет собой блок-схему, иллюстрирующую устройство для вычисления значений преобразования.
Фиг.27 иллюстрирует пример способа декодирования сигнала, использующего IMDCT преобразование, основанное на базовом IDCT-II преобразовании.
Фиг.28 иллюстрирует альтернативный пример прореживания и разбиения преобразования, при котором 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших 5-точечных DCT-II преобразований.
Фиг.29 иллюстрирует 10-точечное IDCT-IV преобразование, которое представляет собой преобразование, обратное преобразованию по фиг.28.
Фиг.30 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения преобразования, при котором обратное 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших 5-точечных DCT-II преобразований и 5-точечных DCT-IV.
Фиг.31 представляет собой блок-схему, иллюстрирующую пример обратного преобразования для прямого преобразования по фиг.30.
Фиг.32 иллюстрирует обратное преобразование, соответствующее прямому преобразованию по фиг.8.
Подробное описание
Ниже описываются различные варианты осуществления с ссылкой на чертежи, на которых идентичные позиционные обозначения используются для ссылки на идентичные элементы по всем чертежам. В нижеследующем описании, для целей объяснения, различные специфические детали излагаются для того, чтобы обеспечить полное понимание одного или нескольких вариантов осуществления. Может быть очевидным, однако, что такой вариант(ы) осуществления может быть осуществлен на практике без этих специфических деталей. В других случаях общеизвестные конструкции и устройства показаны в виде блок-схемы, чтобы способствовать описанию одного или нескольких вариантов осуществления.
Обзор
Один признак предусмотрен для осуществления N-точечного MDCT преобразования (где N=5*2∧K, для некоторого целого числа K>=1) посредством отображения его на N/2-точечных DCT-IV, DST-IV и/или DCT-II преобразований меньшего размера. В одном примере MDCT может систематически прореживаться с коэффициентом 2 и использовать масштабированную 5-точечную базовую функцию на последнем этапе. Один признак обеспечивает несколько быстрых алгоритмов для вычисления базовых DCT-II, DCT-IV и DST-IV преобразований с размером пять (5). Общая архитектура преобразования, которая заявляется здесь, представляет собой обобщенный процесс прореживания, рекурсивно разбивающий преобразования размера N на два преобразования размера N/2, где N=5*2∧K, и где окончательные (наименьшие) 5-точечные преобразования реализуются с использованием быстрых методов, описанных в данном документе. Преобразования такого размера возникают в структуре банков фильтров MDCT для применений речевого и аудиокодирования, таких как недавние и новые стандарты G.729.1, G.718 и EVRC-WB (широкополосный усовершенствованный кодек с переменной скоростью).
Другой признак предусмотрен для использования этапа модифицированного создания окна MDCT, который объединяет вышеописанную архитектуру для вычисления MDCT с асимметричным окном для снижения задержки, ассоциированной с этапом преобразования, в то же время сохраняя такое же количество частотных коэффициентов.
Структура кодека
Фиг.1 представляет собой блок-схему, иллюстрирующую пример кодера, который может включать в себя банк фильтров анализа MDCT. Кодер 102 может принимать входной аудиосигнал 104. Банк 106 фильтров анализа MDCT (т.е. модифицированное дискретное косинусное преобразование, основанное на дискретном косинусном преобразовании типа IV) работает для разложения входного аудиосигнала 104 временной области на множество субполосных сигналов и преобразования сигналов в частотную область, где каждый субполосный сигнал преобразуется в коэффициент преобразования на субполосу на блок. Результирующий сигнал затем квантуется квантователем 108 и кодируется статистическим кодером 110 для получения битового потока 112 оцифрованного аудиосигнала. Согласно одному примеру банк 106 фильтров анализа MDCT может быть реализован функцией 114 создания окна, преобразованием 116 (например, временной области в частотную область) и/или функцией 118 масштабирования. Банк 106 фильтров анализа MDCT, включающий в себя функцию 114 создания окна, преобразование 116 и/или функцию 116 масштабирования, может быть реализован аппаратными средствами (например, в виде процессора, схемы, программируемого логического устройства и т.д.), программными средствами (например, инструкциями, исполняемыми процессором) и/или их комбинацией.
Фиг.2 представляет собой блок-схему, иллюстрирующую пример того, как преобразование может быть реализовано посредством меньших преобразований. В данном примере преобразование 116 по фиг.1 может принимать множество входных сигналов 202 и создавать множество выходных сигналов 204. Для выполнения этого преобразование 116 может быть представлено одним или несколькими преобразованиями этого же или меньшего размера. Например, преобразование 116 может быть реализовано множеством k-точечных DCT-IV преобразований 206а и 206b. В свою очередь, каждое k-точечное DCT-IV преобразование 206а и 206b может быть реализовано одним или несколькими n-точечными DCT-II преобразованиями 208а, 208b или 210а, 210b. Отметьте, что в некоторых реализациях могут использоваться дискретные синусные преобразования (DST)-IV вместо DCT-IV преобразований. Посредством рекурсивного разбиения большего преобразования 116 на множество меньших преобразований 208 упрощается реализация большего преобразования 116. Однако желательна реализация эффективного алгоритма меньших преобразований для достижения быстрой производительности преобразования, которая минимизирует операции. В одном примере преобразование 116 может принимать входные значения x(0) … x(m) 202 временной области, представляющие аудиосигнал, и преобразовывать их в спектральные коэффициенты X(0) … X(m) 204 частотной области. Ниже описываются различные реализации этих меньших преобразований.
Фиг.3 представляет собой блок-схему, иллюстрирующую пример декодера, который может включать в себя банк фильтров синтеза IMDCT. Декодер 302 может принимать битовый поток 304. Статистический декодер 306 декодирует битовый поток 304, который затем деквантуется устройством 308 деквантования для получения сигнала частотной области. Банк 310 фильтров синтеза IMDCT (т.е. обратное модифицированное дискретное косинусное преобразование, основанное на дискретном косинусном преобразовании типа IV) работает для преобразования сигнала 304 частотной области обратно в аудиосигнал 312 временной области. Банк 310 фильтров синтеза IMDCT может изменять на обратные операции банка 106 фильтров анализа MDCT. Согласно одному примеру банк 310 фильтров синтеза IMDCT может быть реализован посредством функции 314 масштабирования, обратного преобразования 316 (например, частотной области во временную область) и функции 318 создания окна плюс перекрытия и сложения. Банк 310 фильтров синтеза IMDCT, включающий в себя функцию 314 масштабирования, обратное преобразование 316 и/или функцию 318 создания окна, может быть реализован аппаратными средствами (например, процессором, схемой, программируемым логическим устройством и т.д.), программными средствами (например, инструкциями, исполняемыми процессором) и/или их комбинацией.
Фиг.4 представляет собой блок-схему, иллюстрирующую пример того, как обратное преобразование может быть реализовано меньшими обратными преобразованиями. В данном примере обратное преобразование 316 по фиг.3 может принимать множество входных сигналов 402 и создавать множество выходных сигналов 404. Для выполнения этого обратное преобразование 316 может быть представлено одним или несколькими преобразованиями этого же или меньшего размера. Например, обратное преобразование 316 может быть реализовано множеством обратных k-точечных IDCT-IV преобразований 406а и 406b. В свою очередь, каждое обратное k-точечное IDCT-IV преобразование 406а и 406b может быть реализовано одним или несколькими n-точечными IDCT-II преобразованиями 408а, 408b или 410а, 410b. Отметьте, что в некоторых реализациях могут использоваться обратные дискретные синусные преобразования (IDST)-IV вместо IDCT-IV преобразований. В одном примере преобразование 316 может принимать спектральные коэффициенты X(0) … X(m) 402 частотной области, представляющие аудиосигнал, и преобразовывать их в восстановленные выходные значения x(0) … x(m) 404 временной области. Однако желательна эффективная реализация алгоритма меньших обратных преобразований для достижения быстрых рабочих характеристик преобразования, которые минимизируют операции.
Отметьте, что входные сигналы для преобразований MDCT 102 и IMDCT 302 могут обрабатываться в качестве кадров или блоков, имеющих множество точек данных. Следовательно, чтобы основанный на MDCT вокодер (такой как, например, G.722.1 или G.722.1C) поддерживал блоки данных, имеющие длину кадра, меньшую 320, необходимы преобразования прореженных размеров. Для блоков, имеющих длину кадра 160, 80, 40 и т.д., наблюдается, что эти размеры все являются кратными 5. Поэтому последний неуменьшаемый (посредством методов прореживания) размер блока может использовать преобразование с размером 5. Обращается внимание, что с точки зрения сложности вычислений является более эффективным разработать 5-точечное DCT-II преобразование, чем или DCT-IV преобразование, или быстрое преобразование Фурье (FFT).
Определение преобразований MDCT
Используя матричное представление, MDCT преобразование может быть представлено матрицей М:
x
X
Следовательно,  и , где  представляет матрицу входных отсчетов ,  представляет матрицу результирующих коэффициентов MDCT , и  представляет матрицу восстановленных выходных результатов .
Чтобы реализовать преобразование MDCT, оно может отображаться на функцию N/2-точечного базового преобразования. Например, преобразование 116 на фиг.1 может быть реализовано как одно или несколько N/2-точечных DCT-IV преобразований.
DCT-IV преобразование может быть определено как:
В то же время IDCT-IV преобразование может быть определено как:
MDCT преобразование может отображаться на N/2-точечное DCT-IV преобразование как:
и IMDCT преобразование может отображаться на N/2-точечное IDCT-IV преобразование как
где
I
J
N/4
N/4
где  представляет собой единичную матрицу размера N/4×N/4, и  представляет собой инверсную матрицу порядка размера N/4×N/4, и матрица S определяется как
и  представляет собой матрицу DCT-IV размера N/2×N/2, которая может быть определена как
Посредством использования свойств симметрии и инволютивности матрицы DCT-IV, она может отображаться на DCT-II преобразование. DCT-II преобразование может определяться как:
Аналогично, IDCT-II преобразование может определяться как:
k
где , если =0, иначе 1.
Определение преобразований DCT-IV, DST-IV и DCT-II
Согласно признаку преобразование 116 (фиг.1) и обратное преобразование 316 (фиг.3) могут прореживаться и реализоваться при помощи одного или нескольких DCT-IV преобразований или DST-IV преобразований (и IDCT-IV или DST-IV), которые могут быть реализованы в виде одного или нескольких DCT-II преобразований (и IDCT-II), соответственно.
DCT-IV и IDCT-IV могут быть определены, соответственно, как:
DST-IV и IDST-IV могут быть определены, соответственно, как:
Аналогично, DCT-II и его обратные преобразования могут быть определены, соответственно, как:
k
где , если =0, иначе 1
N
X(k)
В уравнениях 1-6 {x(n)}, для n=0,1,…N-1, представляет входную последовательность отсчетов,  обозначает длину кадра,  представляет собой результирующие коэффициенты MDCT.
В случае, когда N=5, матрицы C_IV для DCT-IV преобразования, S_IV для DST-IV преобразования и C_II для DCT-II преобразования могут быть представлены, соответственно, как:
(Матрица А)
(Матрица В)
(Матрица С)
Для упрощения представления DCT-II множители  могут игнорироваться, и все коэффициенты могут умножаться на , при использовании следующей системы обозначений:
таким образом получая:
a
b
c
d
c
d
2
2
2
2
В данном случае отметьте, что +=1,25, и что +=0,75. Кроме того, также отметьте, что -=0,5. Это следует из алгебраических выражений для участвующих значений косинуса:
Аналогично, в случае DCT-IV все коэффициенты умножаются на  и используют систему обозначений:
получая:
2
2
2
2
i
g
h
f
i
c
h
g
a
Отметьте, что f+=2, и аналогично +=2. Кроме того, отметьте, что +=×, и что +=×. Это следует из алгебраических выражений для участвующих значений косинуса:
Наконец, в случае DST-IV все коэффициенты могут умножаться на  и используют систему обозначений:
для получения:
2
2
2
2
i
g
h
Аналогично для случая DCT-IV, отметьте, что в данном случае f+=2, и аналогично +=2.
Вывод быстрых алгоритмов для вычисления 5-точечного DCT-II
Чтобы достичь эффективности обработки, преобразования самых меньших размеров, используемые большими преобразованиями, должны быть быстрыми и эффективными. Это достигается посредством минимизации операций (например, умножения, сложения и сдвига), выполняемых этими преобразованиями малого размера. Следовательно, для достижения этого могут реализовываться различные разложения для преобразований самого малого размера. Выбор того, какое разложение преобразования реализуется, может зависеть от различных факторов, включая возможности используемого процессора.
Эффективное DCT-II преобразование может реализовываться различными способами. Например, предполагая, что вход для преобразования обеспечивается входным вектором x, так что
X
произведение вектора x на масштабированную матрицу DCT-II (масштабированную на , как в матрице D) дает матрицу  DCT-II:
X
Рассмотрим вычисление нечетных коэффициентов X1 и X3 в данной матрице :
X
Это предполагает, что оба коэффициента Х1 и Х3 могут быть вычислены в виде простой «бабочки» по x0-x4 и x1-x3. Теперь рассмотрим вычисление четных коэффициентов X2 и X4 в данной матрице :
В данном случае снова оказывается, что вычисления могут быть организованы в виде простой «бабочки» по x0+x4 и x1+x3.
Фактические операции преобразования могут эффективно реализоваться посредством переупорядочения внутренних операций преобразования для снижения общего количества сложений, умножений и/или сдвигов. Следовательно, могут достигаться разные промежуточные результаты посредством разных разложений преобразования, и такие промежуточные результаты характеризуют каждое соответствующее преобразование.
X
Фиг.5 представляет собой блок-схему последовательности операций, иллюстрирующую первый пример разложения преобразования 502 5-точечного DCT-II. В данном примере зависимости между нечетными коэффициентами X1 и X3 и четными коэффициентами X2 и X4 матрицы , отмеченной выше, используются для представления 5-точечного DCT-II преобразования 502, так что вычисляются следующие промежуточные результаты:
и
для получения выходных результатов:
где входные коэффициенты 504 (x0, x1, x2, x3, x4) преобразуются в выходные коэффициенты 506 (X0, X1, X2, X3 и X4). Сложность данной схемы по фиг.5 составляет двенадцать (12) сложений и восемь (8) умножений. В частности, первая «бабочка» 508 реализуется для получения выходных коэффициентов X1 и X3, и вторая «бабочка» 510 реализуется для получения выходных коэффициентов X2 и X4. Наибольший путь в данном преобразовании 502 составляет только три (3) операции (сложения и/или умножения, предполагая, что «бабочке» необходимо только 1 умножение с накоплением (MAC) для каждого пути). Операции, выполняемые «бабочкой», часто упоминаются как плоское вращение или вращение Гивенса.
Фиг.6 представляет собой блок-схему последовательности операций, иллюстрирующую второй пример разложения 5-точечного DCT-II преобразования 602. Данное преобразование 602 может выводиться из преобразования 502 по фиг.5 для преобразования входных коэффициентов 504 в выходные коэффициенты 506. В данной реализации входы для второй «бабочки» 510 (фиг.5) представлены в виде значений z4=x0+x4 и z2=x1+x3 и могут складываться по прямому пути к X0.
Следовательно, промежуточные результаты вычисляются как:
Кроме того, тот факт, что c-d=0,5, используется для представления выходных результатов X0, X2 и X4 как:
Следовательно, 5-точечное DCT-II преобразование 602 отличается:
Сложность данного преобразования 602 составляет двенадцать (12) сложений, пять (5) умножений и два (2) сдвига. Следует заметить, что множители 1/2 в данном преобразовании являются двоично-рациональными, и, поэтому, такое «умножение» на 1/2 представляет собой просто операцию двоичного сдвига (т.е. сдвиг). Длина наибольшего пути в данном случае составляет четыре (4) операции.
Фиг.7 представляет собой блок-схему последовательности операций, иллюстрирующую третий пример разложения 5-точечного DCT-II преобразования 702. Данное преобразование 702 может выводиться из преобразования 602 по фиг.6 для преобразования входных коэффициентов 504 в выходные коэффициенты 506. Уравнения для коэффициентов X2 и X4 могут быть представлены как:
где значения c' и d' выбираются так, что:
Уравнение 7 может быть переставлено, так что:
Следовательно, можно показать, что:
и
Вычитая оба эти уравнения, можно показать, что:
Следовательно, выходные коэффициенты X2 и X4 могут быть представлены как:
что приводит к преобразованию 702 на фиг.7.
Следовательно, промежуточные результаты вычисляются как:
Следовательно, преобразование 702 5-точечного DCT-II отличается:
Данное преобразование 702 может быть реализовано двенадцатью (12) сложениями, пятью (5) умножениями и одним (1) сдвигом. Следует заметить, что множитель 1/4 в данном преобразовании 702 представляет собой двоично-рациональное, и такое «умножение» на 1/4 представляет собой просто операцию двоичного сдвига (т.е. сдвиг). Длина наибольшего пути в данном случае составляет также четыре (4) операции.
α
x
X
Фиг.8 представляет собой блок-схему последовательности операций, иллюстрирующую альтернативный пример разложения 5-точечного DCT-II преобразования 802. Следует заметить, что коэффициент  в данном преобразовании является двоично-рациональным, и, поэтому, умножение на него представляет собой просто операцию двоичного сдвига. Это 5-точечное преобразование может реализовываться или используя плоское вращение и 5 умножений, или посредством использования 4 умножений посредством разложения плоского вращения, или используя этапы поднятия. Для 5-точечной последовательности входов  504 выходные результаты  506 для преобразования 802 5-точечного DCT-II могут генерироваться с использованием 4 нетривиальных умножений, двенадцати (12) сложений и двух (2) сдвигов или пяти (5) умножений, двенадцати (12) сложений и одного (1) сдвига.
В данном примере множителями являются:
DCT-II преобразование 802 может включать в себя промежуточные результаты, так что:
Следовательно, выходные результаты X0, X1, X2, X3 и X4 для DCT-II преобразования 802 могут быть представлены как:
Следует заметить, что промежуточные результаты для преобразований, изображенных на фиг.5-9 (и других преобразований в данном документе), могут изменяться, если выбирается другая точка на блок-схеме последовательности операций. Следовательно, большее или меньшее количество промежуточных результатов и/или другие промежуточные результаты (например, в других точках на блок-схеме последовательности операций) рассматриваются и предполагаются из блок-схем последовательности операций этих преобразований.
Вывод обратного преобразования
Преобразования, изображенные на фиг.4-20, могут быть инвертированы для изменения на обратные прямые преобразования, изображенные в данном документе. Фиг.32 изображает обратное преобразование (обратное 5-точечное IDCT-II преобразование), соответствующее прямому преобразованию на фиг.8. Обратное преобразование 3202 преобразует входы 3204 (спектральные коэффициенты) в выходные результаты (значения временной области) 3206 и могут характеризоваться промежуточными результатами:
//используя отрицательные множители в программном обеспечении, по сравнению с блок-схемой//
где
Следовательно, выходные результаты x0, x1, x2, x3 и x4 3206 для IDCT-II преобразования 3202 могут вычисляться как:
Вывод быстрых алгоритмов для вычисления 5-точечного DCT-IV и DST-IV
Эффективные DCT-IV преобразования и/или DST-IV преобразования могут быть реализованы различными путями. Например, предполагая, что вход для преобразования обеспечивается вектором x, так что
X
произведение вектора x на масштабированную матрицу DCT-IV (масштабируемую на , как в матрице Е) дает матрицу  DCT-IV:
Фиг.9 представляет собой блок-схему последовательности операций, иллюстрирующую первый пример разложения 5-точечного DCT-IV преобразования 902. Преобразование 902 конвертирует входные коэффициенты х 904 в выходные коэффициенты Х 906. Преобразование 902 получается посредством следующего простого переупорядочения членов:
где
Следует заметить, что преобразование 902 может вычисляться с использованием промежуточных результатов, где:
Следовательно, преобразование 902 может быть представлено как:
Поэтому выходные коэффициенты X0, X1, X2, X3 и X4 могут вычисляться с использованием четырех (4) «бабочек» 908а, 908b, 908с и 908d, как показано в преобразовании 902 на фиг.9. Сложность данной реализации составляет двадцать (20) сложений и шестнадцать (16) умножений. Длина наибольшего пути данной реализации составляет только три (3) операции.
Фиг.10 представляет собой блок-схему последовательности операций, иллюстрирующую второй пример того, как может быть реализовано преобразование 1002 5-точечного DCT-IV. Каждая «бабочка» в преобразовании 902 по фиг.9 может быть модифицирована, так что необходимо выполнять только три (3) умножения. Например, составные операции для выходных коэффициентов X0 и X4 могут быть записаны как:
Аналогично, составные операции для выходных коэффициентов Х1 и Х3 могут быть записаны как:
Посредством использования такого разложения выходные коэффициенты для преобразования 1002 могут характеризоваться:
Следует заметить, что преобразование 1002 может вычисляться с использованием промежуточных результатов, где:
Следовательно, преобразование 902 может быть представлено как:
Сложность данного преобразования 1002 составляет теперь двадцать (20) сложений и двенадцать (12) умножений. Длина наибольшего пути в данном случае составляет четыре (4) операции.
В альтернативном подходе DCT-IV преобразования могут выводиться посредством отображения его на DCT-II преобразование.
Например, фиг.11 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование 1102 может отображаться на DCT-II преобразование 1104 для преобразования входных коэффициентов 1106 в выходные коэффициенты 1108.
Фиг.12 представляет собой блок-схему, иллюстрирующую то, как 5-точечное DCT-IV преобразование 1202 может быть реализовано с использованием 5-точечного DCT-II преобразования для преобразования входных коэффициентов 1206 в выходные коэффициенты 1208. Это конкретный случай отображения преобразования, изображенного на фиг.11. В данном примере обозначение для углов может быть представлено как:
Фиг.13 представляет собой блок-схему, иллюстрирующую пример, как разложение 5-точечного DCT-IV преобразования по фиг.12 может быть реализовано с использованием 5-точечного DCT-II преобразования. В данном примере 5-точечное DCT-IV преобразование по фиг.12 умножается на 2, и множители  перенесены. Это отображение эквивалентно отображению на фиг.12.
Фиг.14 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование 1202, отображающееся на фиг.13, может объединяться с DCT-II преобразованием 602 на фиг.6. Т.е. DCT преобразование 1402 может представлять собой объединение преобразования 1202 по фиг.13 и может быть реализовано как DCT-II преобразование 602 по фиг.6. Следовательно, выходные коэффициенты для преобразования 1402 могут характеризоваться:
Следует заметить, что промежуточные результаты могут вычисляться следующим образом:
Следовательно, выходные результаты могут быть представлены как:
Данное преобразование 1402 DCT-IV использует только шестнадцать (16) сложений, девять (9) умножений и два (2) сдвига. Следует заметить, что множители 2 в данном преобразовании являются двоично-рациональными, и, поэтому, такое «умножение» на 2 представляет собой просто операцию двоичного сдвига (т.е. сдвиг).
Фиг.15 представляет собой блок-схему, иллюстрирующую то, как преобразование 1402 DCT-IV по фиг.14 может дополнительно модифицироваться в эквивалентное преобразование 1502. В данном примере последние каскадные операции в преобразовании 1502 позволяют получить дополнительные упрощения. Следовательно, выходные коэффициенты для преобразования 1502 могут характеризоваться:
Следует заметить, что промежуточные результаты могут вычисляться следующим образом:
Следовательно, выходные результаты могут быть представлены как:
Следовательно, данное DCT-IV преобразование 1502 использует только пятнадцать (15) сложений, десять (10) умножений и два (2) сдвига. Следует заметить, что множители «2» в данном преобразовании являются двоично-рациональными, и, поэтому, такое «умножение» на 2 представляет собой просто операцию двоичного сдвига (т.е. сдвиг). Длина наибольшего пути данной реализации составляет только пять (5) операций.
Фиг.16 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование 1502 по фиг.15 может дополнительно модифицироваться в эквивалентное преобразование 1602. Выходные коэффициенты для преобразования 1602 могут характеризоваться:
Следует заметить, что промежуточные результаты могут вычисляться как:
Следовательно, выходные результаты могут быть представлены как:
Следовательно, данное DCT-IV преобразование 1602 использует только пятнадцать (15) сложений, одиннадцать (11) умножений и два (2) сдвига. Следует заметить, что множители 2 в данном преобразовании являются двоично-рациональными, и, поэтому, такое «умножение» на 2 представляет собой просто операцию двоичного сдвига (т.е. сдвиг). Длина наибольшего пути данной реализации составляет только пять (5) операций.
Фиг.17 представляет собой блок-схему, иллюстрирующую то, как DCT-IV преобразование 1602 по фиг.16 может дополнительно модифицироваться в эквивалентное преобразование 1702. Выходные коэффициенты для преобразования 1702 могут характеризоваться:
Следует заметить, что промежуточные результаты могут вычисляться следующим образом:
Следовательно, выходные результаты могут быть представлены как:
Следовательно, данное преобразование 1702 DCT-IV использует только пятнадцать (15) сложений, одиннадцать (11) умножений и два (2) сдвига. Следует заметить, что множители «2» в данном преобразовании являются двоично-рациональными, и, поэтому, такое «умножение» на 2 представляет собой просто операцию двоичного сдвига (т.е. сдвиг). Длина наибольшего пути в данной реализации составляет только пять (5) операций.
Фиг.18 представляет собой блок-схему, иллюстрирующую то, как преобразование 1702 DCT-IV по фиг.17 может дополнительно модифицироваться в эквивалентное преобразование 1802. В данном примере достигается длина более короткого пути и повышенная численная устойчивость вследствие исключения рекурсивных сложений на оконечном этапе. Выходные коэффициенты для преобразования 1802 могут характеризоваться:
Следует заметить, что промежуточные результаты могут вычисляться как:
Следовательно, выходные результаты могут быть представлены как:
Данное преобразование 1802 использует только пятнадцать (15) сложений, двенадцать (12) умножений и два (2) сдвига. Следует заметить, что умножения на «2» считаются сдвигами. Длина наибольшего пути данной реализации составляет только пять (5) операций.
Следует заметить, что DCT и DST преобразования, изображенные на фиг.5-18, могут быть обратимыми как IDCT и IDST преобразования для отмены или обращения операций преобразования DCT и DST в данном документе.
Вычисление преобразований размером N=5*2
K
Согласно одной реализации N-размерное преобразование, где N=5*2K, может рекурсивно разбиваться в цепочку меньших N/2-размерных преобразований, которые могут быть основаны на DCT-II, DCT-IV, DST-IV или подобных ядрах, и где последний 5-точечный каскад реализуется посредством использования одного из описанных быстрых алгоритмов для вычисления 5-точечных преобразований.
Фиг.19 представляет собой блок-схему, иллюстрирующую то, как N-размерное преобразование может рекурсивно разбиваться на меньшие N/2-размерные преобразования до тех пор, пока оно не будет представлено множеством 5-точечных преобразований. Например, N-размерное (точечное) преобразование 1902 принимает N входных коэффициентов 1910 и преобразует их в N выходных коэффициентов 1912. N-размерное преобразование 1902 может прореживаться в два N/2-размерных преобразования 1904а и 1904b. Аналогично, каждое N/2-размерное преобразование 1904а и 1904b может дополнительно прореживаться в множество меньших преобразований до тех пор, пока меньшие преобразования не будут 5-точечными преобразованиями 1906а, 1906b, 1908а и 1908b. В различных реализациях 5-точечные преобразования 1906а, 1906b, 1908а и 1908b могут реализоваться любым из 5-точечных преобразований, изображенных на фиг.5-18.
Фиг.20 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения преобразования, в котором 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших преобразований 2004а и 2004b 5-точечного DCT-II. В данном примере десять входных коэффициентов 2006 преобразуются парой меньших 5-точечных преобразований 2004а и 2004b для получения десяти выходных коэффициентов 2008.
Фиг.28 иллюстрирует альтернативный пример прореживания и разбиения преобразования, в котором 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших 5-точечных DCT-преобразований 2804а и 2804b II. В данном примере десять входных коэффициентов 2806 преобразуются парой меньших 5-точечных преобразований 2804а и 2804b для получения десяти выходных коэффициентов 2808. По сравнению с фиг.20 данный альтернативный процесс прореживания для DCT-IV требует больше операций, но он является численно более робастным. Т.е. выполнение последовательности вычитаний после преобразования 2004b на схеме фиг.20 может потенциально увеличить величину промежуточных переменных на N/2, где N представляет собой размер преобразования. Альтернативная схема на фиг.28 не имеет такие выполнения, и она использует только плоские вращения (которые представляют собой ортонормальные операции) для вычисления преобразования. Процедура разбиения для DCT-II также имеет такие свойства. Необходимо отметить, что окончательный алгоритм также может рекурсивно чередовать типы преобразований в процессе разбиения. Т.е. он может разбить DCT-II на DCT-II и DCT-IV половинных размеров; затем он разбивает DCT-IV на 2 DCT-II, тогда как DCT-II будут разбиваться на дальнейшие меньшие DCT-II и DCT-IV; и т.д.
Фиг.29 иллюстрирует 10-точечное IDCT-IV преобразование, которое представляет собой преобразование, обратное показанному на фиг.28.
Фиг.21 представляет собой блок-схему, иллюстрирующую то, как N-размерное обратное преобразование может рекурсивно разбиваться на меньшие N/2-размерные обратные преобразования до тех пор, пока оно не будет представлено множеством 5-точечных обратных преобразований. Например, N-размерное (точечное) обратное преобразование 2102 принимает N входных коэффициентов 2110 и преобразует их в N выходных коэффициентов 2112. N-размерное обратное преобразование 2102 может прореживаться в два N/2-размерных обратных преобразования 2104а и 2104b. Аналогично, каждое N/2-размерное обратное преобразование 2104а и 2104b может дополнительно прореживаться на множество меньших обратных преобразований до тех пор, пока наименьшие обратные преобразования не будут являться 5-точечными обратными преобразованиями 2106а, 2106b, 2108а и 2108b. В различных реализациях 5-точечные обратные преобразования 2106а, 2106b, 2108а, и 2108b могут быть реализованы любым 5-точечным обратным преобразованием, соответствующим преобразованиям, изображенным на фиг.5-18.
Фиг.22 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения обратного преобразования, при котором обратное 10-точечное IDCT-IV преобразование 2202 рекурсивно разбивается на множество меньших обратных 5-точечных IDCT-II преобразований 2204а и 2204b. В данном примере десять входных коэффициентов 2206 преобразуются парой меньших 5-точечных обратных преобразований 2204а и 2204b для получения десяти выходных коэффициентов 2208.
Фиг.30 представляет собой блок-схему, иллюстрирующую пример прореживания и разбиения преобразования, при котором обратное 10-точечное DCT-IV преобразование рекурсивно разбивается на множество меньших 5-точечных DCT-II преобразований и 5-точечных DCT-IV преобразований.
Фиг.31 представляет собой блок-схему, иллюстрирующую пример обратного преобразования для прямого преобразования по фиг.30.
Банк фильтров MDCT с этапом создания асимметричного окна
Согласно другому признаку этап создания асимметричного окна может быть реализован в качестве части банка фильтров MDCT. В некоторых применениях банк фильтров MDCT может реализовываться в масштабируемом речевом кодеке, имеющем многочисленные уровни, где некоторые такие уровни могут использовать MDCT для преобразования сигнала ошибки от предыдущего уровня. MDCT взвешенного сигнала ошибки werr_sp(k) с 40 миллисекундным этапом создания окна задается выражением:
Фиг.23 иллюстрирует форму асимметричного окна, которая может использоваться для уменьшения задержки, ассоциированной с этапом преобразования, до 10 мс, в то же время сохраняя такое же количество частотных коэффициентов. Уменьшение задержки становится возможным вследствие того факта, что первые 80 множителей в такой функции асимметричного окна превращаются в 0. Поэтому не следует обращаться к этим отсчетам.
В противоположность традиционным окнам MDCT это окно 2302 не является симметричным; по существу, вторая половина окна отличается от обратного во времени варианта первой половины. Форма асимметричного окна анализа определяется следующим уравнением:
где
D
n
и () определяется посредством
M
M
M
Z
где =320 обозначает количество частотных составляющих MDCT, и =/4 - количество конечных нулей.
Объяснение матрицы отображения MDCT на DCT-IV
werr_sp(k)
werr
n
T
M×2M
Вычисление коэффициентов MDCT  выполняется посредством применения сначала окна и множителей  нормализации к входному сигналу () и затем вычисления произведения на матрицу  размера :
посредством использования ее разложения в
где
M×M
представляет собой матрицу размера  DCT-IV преобразования,
I
J
N/2
N/2
N/2
N/2
где  и  обозначают единичную матрицу и инверсную матрицу порядка ×, соответственно.
Вычисление DCT-IV
M
5*2
k
1
6
k
Вычисление DCT-IV размера = (=,…,) выполняется посредством разбиения его на DCT-II преобразования в два раза меньшего размера:
где:
P
M
представляет собой матрицу перестановок, создающую переупорядочение
D
M
представляет собой диагональную знакопеременную матрицу
R
M
представляет собой матрицу вращения Гивенса:
и  обозначает матрицы остальных DCT-II преобразований:
M
10
M
5
Примерная реализация такого процесса разбиения DCT-IV преобразования размера = в DCT-II преобразования в два раза меньшие (=) изображена на фиг.20.
M
5*2
k
Вычисление DCT-II преобразований размеров = (k=1,…,5) также может выполняться посредством разбиения его на меньшие преобразования:
M=10
M=5
Примерная реализация такого процесса разбиения DCT-II преобразования размера  на меньшие преобразования () изображена на фиг.30.
Вышеупомянутый процесс может повторяться рекурсивно до тех пор, пока останутся только 5-точечные преобразования. Остальные 5-точечные преобразования могут быть эффективно реализованы.
Вычисление 5-точечного DCT-IV выполняется при помощи DCT-II следующим образом:
T
Наконец, вычисление 5-точечного DCT-II для входного вектора x=[x0, x1, x2, x3, x4]
выполняется следующим образом:
DCT-II преобразование 802 может включать в себя промежуточные результаты, такие что:
где
Пример потокового графа для данного преобразования изображен на фиг.8.
Пример кодирования с использованием MDCT преобразования
Фиг.24 представляет собой блок-схему, иллюстрирующую устройство для вычисления значений преобразования. Устройство 2402 может включать в себя входной модуль 2406, модуль 2410 создания окна и/или модуль 2414 преобразования. Входной модуль 2406 может быть выполнен с возможностью приема аудиосигнала 2404 и обеспечения входных значений 2408 временной области, представляющих аудиосигнал. Модуль 2410 создания окна может получать функцию создания асимметричного окна, как показано на фиг.23.
Модуль 2414 преобразования может преобразовывать входные значения 2412, обработанные посредством окна, в спектральные коэффициенты 2416, используя, например, модифицированное дискретное косинусное преобразование (MDCT). MDCT может рекурсивно разбиваться на по меньшей мере одно из дискретного косинусного преобразования типа IV (DCT-IV), дискретного косинусного преобразования типа II (DCT-II) или как DCT-IV, так и DCT-II, причем каждое такое преобразование имеет меньшую размерность, чем MDCT. В одном примере DCT-II может представлять собой 5-точечное преобразование, которое реализует MDCT разных размеров. MDCT может реализовывать по меньшей мере два из 320-, 160-, 80-, 40-точечных преобразований, использующих одно и то же базовое DCT-II. Компоненты устройства 2402 могут быть реализованы в виде аппаратных средств, программных средств и/или их комбинации. Например, устройством 2402 может быть процессор и/или схема, которая реализует функции его компонентов или модулей.
Фиг.25 иллюстрирует пример способа кодирования сигнала, использующего преобразование MDCT, основываясь на 5-точечном базовом преобразовании. Могут приниматься 2502 входные значения временной области, представляющие аудиосигнал. Например, аналоговый аудиосигнал (например, речевой сигнал, музыка, видео и т.д.) может дискретизироваться для получения входных значений. В одном примере может создаваться модифицированная функция создания окна, которая применяет функцию асимметричного окна к входным значениям 2504. Входные значения (обработанные методом окна) затем могут преобразовываться в спектральные коэффициенты, используя модифицированное дискретное косинусное преобразование (MDCT), которое рекурсивно разбивается на множество 5-точечных преобразований. Например, может использоваться любое из 5-точечных преобразований, изображенных на фиг.5-22.
Пример декодирования с использованием преобразования IMDCT
Фиг.26 представляет собой блок-схему, иллюстрирующую устройство для вычисления значений преобразования. Устройство 2602 может включать в себя входной модуль 2606, модуль 2608 обратного преобразования и/или модуль 2621 окна. Модуль 2608 обратного преобразования может быть выполнен с возможностью преобразования спектральных коэффициентов 2604 в выходные значения 2610. Например, модуль обратного преобразования может преобразовывать спектральные коэффициенты в выходные значения 2610 временной области, используя обратное модифицированное дискретное косинусное преобразование (IMDCT), которое рекурсивно разбивается на по меньшей мере одно из обратного дискретного косинусного преобразования типа IV (IDCT-IV), обратного дискретного косинусного преобразования типа II (IDCT-II) или как на IDCT-IV, так и на IDCT-II, причем каждое такое обратное преобразование имеет меньшую размерность, чем IMDCT.
Модуль 2612 окна может создавать модифицированную функцию создания окна, которая реализует функцию асимметричного окна над выходными значениями 2610 для получения выходных значений 2614, обработанных методом окна. Компоненты устройства 2602 могут быть реализованы в виде аппаратных средств, программных средств и/или их комбинации. Например, устройством 2602 может быть процессор и/или схема, которая реализует функции его компонентов или модулей.
Фиг.27 иллюстрирует пример способа декодирования сигнала, использующего IMDCT преобразование, основываясь на базовом IDCT-II преобразовании. Принимаются или получаются 2702 спектральные коэффициенты, представляющие аудиосигнал. Спектральные коэффициенты могут преобразовываться в выходные значения временной области, используя обратное модифицированное дискретное косинусное преобразование (IMDCT), которое рекурсивно разбивается на множество 5-точечных обратных преобразований 2704. Каждое из множества 5-точечных обратных преобразований может быть реализовано с использованием одного и того же базового преобразования. IMDCT реализует по меньшей мере два из 320-, 160-, 80-, 40-точечных обратных преобразований, используя одно и то же базовое преобразование. В различных реализациях базовым преобразованием может быть любое одно из 5-точечных преобразований на фиг.5-22. Кроме того, может создаваться модифицированная функция создания окна, которая применяет функцию создания асимметричного окна к преобразуемым спектральным коэффициентам 2706.
В дополнение к примерам, представленным в данном документе, алгоритмы, описанные в данном документе, которые реализуют прореженные преобразования, могут использоваться для реализации любого другого преобразования, которое является кратным двух. Кроме того, необходимо отметить, что методы, описанные в данном документе, могут быть применены к различным типам сигналов, включающим в себя аудио, речь, видео, данные и т.д.
Должно быть понятно, что промежуточные результаты для преобразований, изображенных в данном документе, могут меняться, если выбирается другая точка на блок-схеме последовательности операций преобразования. Следовательно, предполагается большее или меньшее количество промежуточных результатов и/или разные промежуточные результаты (например, в разных точках на блок-схеме последовательности операций) и в пределах области действия блок-схем последовательности операций преобразования, описанных и заявленных в данном документе.
Информация и сигналы могут быть представлены с использованием любой из разнообразных различных технологий и методов. Например, данные, инструкции, команды, информация, сигналы и т.п., которые могут упоминаться в вышеупомянутом описании, могут быть представлены напряжениями, токами, электромагнитными волнами, магнитными полями или частицами, оптическими полями или частицами, или любой их комбинацией.
Различные иллюстративные логические блоки, модули и схемы и этапы алгоритма, описанные в данном документе, могут быть реализованы или выполнены в виде электронных аппаратных средств, программных средств или их комбинацией. Чтобы ясно проиллюстрировать эту взаимозаменяемость аппаратных и программных средств, различные иллюстративные компоненты, блоки, модули, схемы и этапы были описаны выше, в основном, в терминах их функциональных возможностей. Реализуется ли такая функциональная возможность в виде аппаратных средств или программных средств, зависит от конкретного применения и конструктивных ограничений, накладываемых на всю систему. Отмечается, что конфигурации могут описываться в качестве процесса, который описывается в виде блок-схемы последовательности операций, технологической схемы процесса, структурной схемы или блок-схемы. Хотя блок-схема последовательности операций может описывать операции в виде последовательного процесса, многие из операций могут выполняться параллельно или одновременно. Кроме того, может быть переупорядочен порядок операций. Процесс завершается, когда его операции заканчиваются. Процесс может соответствовать способу, функции, процедуре, рутинной подоперации, подпрограмме и т.д. Когда процесс соответствует функции, ее завершение соответствует возврату из функции к вызывающей функции или главной функции.
При реализации аппаратными средствами различные примеры могут применять процессор общего назначения, процессор цифровой обработки сигналов (DSP), специализированную интегральную схему (ASIC), программируемую вентильную матрицу (FPGA) или другое программируемое логическое устройство, дискретную вентильную или транзисторную логику, дискретные аппаратные компоненты или любую их комбинацию, предназначенную для выполнения функций, описанных в данном документе. Процессором общего назначения может быть микропроцессор, но, в альтернативе, процессором может быть любой обычный процессор, контроллер, микроконтроллер или конечный автомат. Процессор также может быть реализован в виде комбинации вычислительных устройств, например комбинации DSP и микропроцессора, множества микропроцессоров, одного или нескольких микропроцессоров вместе с ядром DSP, или любой другой такой конфигурации.
При реализации программными средствами различные примеры могут применять аппаратно-программное, микропрограммное обеспечение или микрокод. Программный код или кодовые сегменты для выполнения необходимых задач могут храниться на считываемой компьютером среде, такой как запоминающая среда или другое запоминающее устройство(а). Процессор может выполнять необходимые задачи. Кодовый сегмент может представлять процедуру, функцию, подпрограмму, программу, рутинную операцию, рутинную подоперацию, модуль, пакет программ, класс или любое объединение инструкций, структур данных или операторов программы. Кодовый сегмент может быть связан с другим кодовым сегментом или аппаратной схемой посредством пересылки и/или приема информации, данных, аргументов, параметров или содержимого памяти. Информация, аргументы, параметры, данные и т.д. могут пересылаться, направляться или передаваться при помощи любых подходящих средств, включая совместное использование памяти, пересылку сообщений, пересылку маркера, сетевую передачу и т.д.
Как используется в данной заявке, термины «компонент», «модуль», «система» и т.п., как предполагается, относятся к относящемуся к компьютеру объекту, или аппаратному средству, или аппаратно-программному средству, или комбинации аппаратных и программных средств, или программному средству, или программному средству в режиме исполнения. Например, компонентом может быть, но без ограничения, процесс, выполняющийся на процессоре, процессор, объект, исполняемый файл, поток управления, программа и/или компьютер. В качестве иллюстрации, компонентом может быть как приложение, выполняющееся на вычислительном устройстве, так и вычислительное устройство. Один или несколько компонентов могут находиться в процессе и/или потоке управления, и компонент может быть локализован на одном компьютере и/или распределен между двумя или более компьютерами. Кроме того, эти компоненты могут исполняться с различных считываемых компьютером сред, имеющих различные структуры данных, хранимые на них. Компоненты могут устанавливать связь посредством локальных и/или удаленных процессов, таких как в соответствии с сигналом, имеющим один или несколько пакетов данных (например, данные от одного компонента взаимодействуют с другим компонентом в локальной системе, распределенной системе и/или по сети, такой как Интернет, с другими системами посредством сигнала).
В одном или нескольких примерах в данном документе описанные функции могут быть реализованы аппаратными, программными, аппаратно-программными средствами или любой их комбинацией. Если они реализованы программными средствами, функции могут храниться или передаваться в виде одной или нескольких инструкций или кода на считываемой компьютером среде. Считываемая компьютером среда включает в себя как запоминающую среду компьютера, так и среду связи, включающую в себя любую среду, которая способствует пересылке компьютерной программы из одного места в другое. Запоминающая среда может представлять собой любую доступную среду, к которой может обращаться компьютер. В качестве примера, и не ограничения, такая считываемая компьютером среда может содержать оперативное запоминающее устройство (RAM), постоянное запоминающее устройство (ROM), электрически стираемое программируемое ROM (EEPROM), компакт-диск или другое запоминающее устройство на оптическом диске, запоминающее устройство на магнитных дисках или другие магнитные запоминающие устройства, или любую другую среду, которая может использоваться для переноса или хранения требуемого программного кода в виде инструкций или структур данных, и к которой может обращаться компьютер. Также любое соединение правильно называется считываемой компьютером средой. Например, если программные средства передаются с веб-сайта, сервера или другого удаленного источника, используя коаксиальный кабель, волоконно-оптический кабель, витую пару, цифровую абонентскую линию (DSL) или беспроводные технологии, такие как инфракрасные, радиочастотные или микроволновые, тогда коаксиальный кабель, волоконно-оптический кабель, витая пара, DSL или беспроводные технологии, такие как инфракрасные, радиочастотные и микроволновые, включаются в определение среды. Диск (disk) и диск (disc), как используется в данном документе, включает в себя компакт-диск (CD), лазерный диск, оптический диск, цифровой многофункциональный диск (DVD), дискету и диск Blu-ray, где диски (disk) обычно воспроизводят данные магнитным образом, тогда как диски (disc) воспроизводят данные оптическим образом при помощи лазеров. Комбинации вышеупомянутого также должны быть включены в объем считываемых компьютером сред. Программные средства могут содержать одну инструкцию, или много инструкций, и могут распределяться по нескольким разным кодовым сегментам, по разным программам и по многочисленным запоминающим средам. Примерная запоминающая среда может быть связана с процессором, так что процессор может считывать информацию с запоминающей среды и записывать информацию на нее. В альтернативе запоминающая среда может быть интегрирована в процессор.
Способы, описанные в данном документе, содержат один или несколько этапов или действий для достижения описанного способа. Этапы и/или действия способа могут обмениваться друг с другом без отступления от объема формулы изобретения. Другими словами, если не требуется конкретный порядок этапов или действий для надлежащей работы варианта осуществления, который описывается, то порядок и/или использование конкретных этапов и/или действий может модифицироваться без отступления от объема формулы изобретения.
Один или несколько компонентов, этапов и/или функций, изображенных на чертежах, могут быть переупорядочены и/или объединены в один компонент, этап или функцию или воплощены в нескольких компонентах, этапах или функциях. Также могут добавляться дополнительные элементы, компоненты, этапы и/или функции. Устройства, приборы и/или компоненты, изображенные на некоторых чертежах, могут конфигурироваться или адаптироваться для выполнения одного или нескольких способов, признаков или этапов, описанных на других чертежах. Алгоритмы, описанные в данном документе, могут эффективно реализовываться, например, посредством программных средств и/или встроенных аппаратных средств.
Необходимо отметить, что вышеприведенные конфигурации представляют собой просто примеры и не должны рассматриваться как ограничивающие формулу изобретения. Описание конфигураций, как предполагается, является иллюстративным и не ограничивает объем формулы изобретения. По существу, настоящие идеи могут быть легко применены к другим типам устройств, и многочисленные альтернативы, модификации и варианты очевидны для специалиста в данной области техники.