Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования

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

 

По настоящей заявке на патент испрашивается приоритет по дате подачи предварительной заявки США №60/816697, поданной 26 июня 2006, предварительной заявки США №60/841362, поданной 30 августа 2006, предварительной заявки США №60/847194, поданной 25 сентября 2006, предварительной заявки США №60/829669, поданной 16 октября 2006, и предварительной заявки США №60/869530, поданной 11 декабря 2006, которые полностью включены в этот документ по ссылке.

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

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

Предшествующий уровень техники

Во многих существующих стандартах кодирования видео и изображения используются способы сжатия для обеспечения возможности сохранения или передачи видео и изображений с высоким разрешением как относительно компактных файлов или потоков данных. Такие стандарты кодирования включают в себя стандарт сжатия неподвижного изображения (JPEG), разработанный группой экспертов по видео, международный стандарт сжатия видео- и аудиоданных (MPEG)-1, MPEG-2, часть 2 MPEG-4, H.261, H.263 и другие стандарты кодирования видео или изображения.

Согласно многим из этих стандартов видеокадры сжимают с использованием "пространственного" кодирования. Эти кадры могут быть исходными кадрами (то есть i-кадрами) или могут быть остаточными кадрами, сформированными посредством временного кодирования, которое использует компенсацию движения. Во время пространственного кодирования кадры разбиваются на блоки пикселей равного размера. Например, несжатый кадр может быть разбит на ряд блоков пикселей 8×8. Для каждого блока пикселей компоненты пикселя разделяются на матрицы значений компонентов пикселя. Например, каждый блок пикселей может быть разделен на матрицу значений компонента пикселя Y, матрицу значений компонента пикселя U и матрицу значений компонента пикселя V. В этом примере, значения компонента пикселя Y указывают значения яркости, и значения компонентов пикселя U и V представляют значения информации о цвете.

Кроме того, во время пространственного кодирования к каждой матрице значений компонента пикселя в кодируемом кадре применяется прямое дискретное косинусное преобразование (FDCT). Идеальное одномерное FDCT определяется посредством

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное FDCT определяется формулой

где s - массив N исходных значений, t - массив N преобразованных значений и c(i,j) задается посредством c(i,j)=c(i)c(j), и причем c(k) определяется, как в одномерном случае.

Матрица коэффициентов формируется при преобразовании блока значений компонента пикселя с использованием FDCT. Далее эту матрицу коэффициентов можно квантовать и кодировать с использованием, например, кодов Хаффмана или арифметических кодов. Битовый поток видео представляет объединенный результат выполнения этого процесса для всех блоков значений компонентов пикселя в последовательности видеокадров в несжатой последовательности видеокадров.

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

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное IDCT определяется формулой

Далее получающиеся в результате матрицы значений компонента пикселя снова собираются в блоки пикселей, и эти блоки пикселей снова собираются для формирования декодированного кадра. Если декодированный кадр является i-кадром, то этот кадр теперь полностью декодирован. Однако если несжатый кадр является p- (прогнозным) или b- (бипрогнозным) кадром, то декодированный кадр является только декодированным остаточным кадром. Законченный кадр формируется посредством создания восстановленного кадра с использованием векторов движения, связанных с декодированным кадром, и последующего суммирования восстановленного кадра с декодированным остаточным кадром.

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

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

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

Описаны способы аппроксимации вычисления обратного дискретного косинусного преобразования с использованием вычислений с фиксированной запятой. Согласно этим способам матрицы масштабированных коэффициентов формируются посредством умножения коэффициентов в матрицах закодированных коэффициентов на масштабные множители. Затем формируются матрицы смещенных коэффициентов посредством добавления значений смещения центра и значений дополнительного смещения к коэффициентам DC матриц масштабированных коэффициентов. Далее используются арифметические операции с фиксированной запятой для применения преобразования к получающимся в результате матрицам смещенных коэффициентов. После этого значения в получающихся в результате матрицах сдвигаются вправо для получения матриц значений компонента пикселя. Матрицы значений компонента пикселя затем объединяются для создания матриц пикселей. Матрицы пикселей, сформированные этими способами, близко напоминают матрицы пикселей, восстановленные из сжатых данных с использованием идеального обратного дискретного косинусного преобразования ("IDCT").

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.6 - блок-схема, изображающая иллюстративные детали модуля обратного дискретного косинусного преобразования ("IDCT").

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

Фиг.8 - блок-схема, изображающая иллюстративные детали модуля прямого дискретного косинусного преобразования ("FDCT").

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

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

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

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

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

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

Устройство 2 может включать в себя источник 4 мультимедиа для формирования мультимедийных данных. Источник 4 мультимедиа может содержать цифровую видео- или фотокамеру для ввода данных изображения. Источник 4 мультимедиа может быть встроен в устройство 2 или может быть присоединен к устройству 2 как периферийное устройство. Источник 4 мультимедиа может также содержать микрофон для записи звуковых данных. Источник 4 мультимедиа может обеспечивать мультимедийные данные в процессор 6. Процессор 6 может содержать цифровой сигнальный процессор ("DSP"), микропроцессор или некоторый другой тип интегральной схемы.

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

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

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

Драйвер 13 воспроизведения в устройстве 2 вызывает воспроизведение блоком 14 воспроизведения мультимедиа мультимедийных данных, декодированных модулем 12 декодирования. Например, блок 14 воспроизведения мультимедиа может содержать компьютерный монитор, который воспроизводит мультимедийные данные видео или изображения. В другом примере блок 14 воспроизведения мультимедиа может содержать устройство вывода звука (например, динамик), которое воспроизводит звуковые мультимедийные данные. Блок 14 воспроизведения мультимедиа может быть встроен в устройство 2 или может быть связан с ним через проводную или беспроводную линию связи как периферийное устройство. Драйвер 13 воспроизведения может содержать драйвер устройства или другие программные средства, аппаратный или программно-аппаратный блок или некоторый другой механизм, который вызывает воспроизведение мультимедийных данных блоком 14 воспроизведения мультимедиа.

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

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

Когда модуль 8 кодирования кодирует последовательность видеокадров, модуль 8 кодирования может начинать с выбора тех видеокадров, которые должны быть "i-кадрами". Например, модуль 8 кодирования может выбирать каждый восьмой кадр как i-кадр. I-кадры являются кадрами, которые не ссылаются на другие кадры. После выбора i-кадров модуль 8 кодирования использует "пространственное кодирование" для кодирования i-кадров. Кроме того, модуль 8 кодирования может использовать "временное кодирование" для кодирования оставшихся кадров.

Для использования пространственного кодирования для кодирования кадра модуль 8 кодирования может разбивать данные кадра на блоки пикселей. Например, модуль 8 кодирования может разбивать данные кадра на блоки пикселей, восемь пикселей шириной и восемь пикселей высотой (то есть каждый блок пикселей содержит 64 пикселя). После этого модуль 8 кодирования может разделять значения компонентов пикселя пикселей в каждом блоке пикселей на отдельные матрицы значений компонента пикселя. Значения компонентов пикселя одного пикселя являются значениями, которые характеризуют вид пикселя. Например, каждый пиксель может специфицировать значение компонента пикселя Y, значение компонента пикселя Cr и значение компонента пикселя Cb. Значение компонента пикселя Y указывает яркость пикселя, значение компонента пикселя Cr указывает информацию о красном цвете пикселя, и значение компонента пикселя Cb указывает информацию о синем цвете пикселя. В этом примере, когда модуль 8 кодирования разделяет значения компонентов пикселя блока пикселей, модуль 8 кодирования может получать матрицу значений компонента пикселя Y, матрицу значений компонента пикселя Cr и матрицу значений компонента пикселя Cb.

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

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

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное FDCT определяется формулой

где s - массив N исходных значений, t - массив N преобразованных значений и c(i,j) задается посредством c(i,j)=c(i)c(j), и причем c(k) определяется, как в одномерном случае.

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

Для использования временного кодирования для кодирования кадра модуль 8 кодирования может разделять кадр на "макроблоки". В зависимости от используемого стандарта кодирования эти макроблоки могут иметь фиксированный или переменный размер и могут быть перекрывающимися или неперекрывающимися. Например, каждый макроблок может быть блоком пикселей 16×16. Для каждого макроблока в кадре модуль 8 кодирования 8 может пытаться идентифицировать исходный макроблок в одном или нескольких кадрах ссылки. В зависимости от стандарта кодирования кадры ссылки могут быть i-кадрами, p-кадрами или b-кадрами. Если модуль 8 кодирования может идентифицировать исходный макроблок в кадре ссылки, то модуль 8 кодирования записывает вектор движения для этого макроблока. Вектор движения включает в себя значение x, которое указывает горизонтальное перемещение макроблока относительно идентифицированного исходного макроблока, и значение y, которое указывает вертикальное перемещение макроблока относительно идентифицированного исходного макроблока. Если модуль 8 кодирования не может идентифицировать исходный макроблок для упомянутого макроблока, то может не потребоваться запись вектора движения модулем 8 кодирования для этого макроблока. Затем модуль 8 кодирования формирует "восстановленный" кадр. Восстановленный кадр содержит кадр, который получается в результате перемещения макроблоков из кадров ссылки согласно записанным векторам движения для текущего кадра. После формирования восстановленного кадра модуль 8 кодирования вычитает значения компонентов пикселя в каждом пикселе восстановленного кадра из соответствующих значений компонентов пикселя в соответствующих пикселях текущего кадра, в результате чего получается "остаточный" кадр. После этого модуль 8 кодирования может использовать схему энтропийного кодирования для сжатия векторов движения для макроблоков текущего кадра. Кроме того, модуль 8 кодирования использует описанный выше способ пространственного кодирования для сжатия остаточного кадра.

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

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

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

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

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

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

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

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

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

Способы, описанные в этом раскрытии, могут обеспечить несколько преимуществ. Например, уменьшение ошибок округления во время вычисления дискретного косинусного преобразования и обратного дискретного косинусного преобразования может уменьшить видимые ошибки в данных изображения и может уменьшить слышимые ошибки в звуковых данных. Кроме того, так как эти способы можно применять к вычислениям с фиксированной запятой, то эти способы могут быть применены в меньших, менее сложных устройствах, например мобильных телефонах, персональных цифровых секретарях и личных медиаплеерах. В частности, упомянутые способы могут быть применены с использованием чисел с фиксированной запятой, части мантиссы которых имеют очень ограниченное количество битов (например, три бита), при этом выполняются требования по точности, специфицированные стандартом 1180 Института инженеров по электротехнике и радиоэлектроники (IEEE), все содержимое которого включено в этот документ по ссылке. Кроме того, эти способы могут быть применены к форматам, которые включают в себя рекомендации H.261, H.263, H.264, T.81 (JPEG) сектора стандартизации (электросвязи) Международного союза электросвязи (ITU-T), а также форматы мультимедиа Международной организации по стандартизации (ISO)/MEC Группы экспертов по видео (MPEG)-1, MPEG-2 и Части 2 MPEG-4.

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

Как изображено в примере фиг.2, модуль 8 кодирования включает в себя модуль 20 управления кадром, который управляет тем, обрабатывает ли модуль 8 кодирования видеокадр как i-кадр, p-кадр или b-кадр. Например, когда модуль 8 кодирования принимает видеокадр, модуль 20 управления кадром может устанавливать флажок битового потока, связанный с этим видеокадром, указывает, что кадр является i-кадром, p-кадром или b-кадром. Если модуль 20 управления кадром устанавливает, что флажок битового потока указывает, что кадр является i-кадром, то модуль 20 управления кадром может вызвать обработку видеокадра набором модулей, которые непосредственно выполняют пространственное кодирование видеокадра. С другой стороны, если модуль 20 управления кадром устанавливает, что кадр является p-кадром или b-кадром, то модуль 20 управления кадром может вызвать обработку видеокадра набором модулей, которые выполняют временное кодирование.

Модуль 8 кодирования включает в себя последовательность модулей для применения пространственного кодирования к видеокадрам. Эти модули включают в себя модуль 22 разделителя на блоки, модуль 24 выделения компонента, модуль 26 прямого преобразования, модуль 28 квантования и модуль 30 энтропийного кодирования. Модуль 22 разделителя на блоки может принимать незакодированные видеокадры из источника 4 мультимедиа, сетевого интерфейса 16 или другого источника. Когда модуль 22 разделителя на блоки принимает незакодированный видеокадр, модуль 22 разделителя на блоки может разделять кадр на блоки пикселей. Модуль 22 разделителя на блоки может обеспечивать блоки пикселей в модуль 24 выделения компонента.

Модуль 24 выделения компонента принимает блок пикселей, модуль 24 выделения компонента может преобразовывать значения компонента пикселя каждого пикселя в различные цветовые форматы. Например, модуль 24 выделения компонента может преобразовывать каждый пиксель из цветового формата "красный-зеленый-синий" (RGB) в цветовой формат YCrCb. После преобразования пикселей в блоке в другой цветовой формат модуль 24 выделения компонента может разделять значения компонентов пикселя пикселей в блоке на матрицы значений компонента пикселя. Например, модуль 24 выделения компонента может выделять матрицу значений Y, матрицу значений Cr и матрицу значений Cb из одного блока пикселей. Значения Y специфицируют яркость пикселей, значения Cr специфицируют информацию о красном цвете пикселей и значения Cb специфицируют информацию о синем цвете пикселей. После выделения матриц значений компонента пикселя модулем 24 выделения компонента модуль 24 выделения компонента может обеспечивать каждую из матриц отдельно в модуль 26 прямого преобразования.

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

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

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

Когда модуль 28 квантования принимает матрицу коэффициентов из модуля 26 прямого преобразования, модуль 28 квантования может квантовать масштабированные коэффициенты. Модуль 28 квантования может квантовать масштабированные коэффициенты множеством способов, в зависимости от используемого стандарта кодирования. Например, согласно части 2 стандарта MPEG-4 модуль 28 квантования может использовать следующую матрицу квантования для квантования коэффициентов в матрице масштабированных коэффициентов для i-кадра:

Кроме того, в этом примере модуль 28 квантования может использовать следующую матрицу квантования для квантования коэффициентов в матрице масштабированных коэффициентов для p- или b-кадра:

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

Модуль 8 кодирования также включает в себя один или несколько модулей для выполнения временного кодирования видеокадров. Как изображено в примере фиг.2, модуль 8 кодирования включает в себя модуль 32 оценки движения, модуль 34 формирования восстановленного кадра и модуль 36 формирования остаточного кадра. Модуль 32 оценки движения пытается идентифицировать исходный макроблок в изображении ссылки для каждого макроблока в текущем видеокадре. Модуль 32 оценки движения может пытаться идентифицировать исходный макроблок для макроблока в текущем кадре посредством поиска макроблоков в изображении ссылки, которые содержат пиксели, аналогичные пикселям этого макроблока. Модуль 32 оценки движения может вести поиск в областях различных размеров согласно различным стандартам кодирования для идентификации исходного макроблока для макроблока в текущем кадре. Например, модуль 32 оценки движения может вести поиск исходного макроблока в области, которая является пикселями (размером) 32 пикселя шириной 32 пикселя высотой, с текущим макроблоком в центре области поиска. Когда модуль 32 оценки движения идентифицирует исходный макроблок для макроблока в текущем кадре, модуль 32 оценки движения вычисляет вектор движения для этого макроблока в текущем кадре. Вектор движения для макроблока в текущем кадре специфицирует значение x, которое указывает различие в горизонтальной позиции между идентифицированным исходным макроблоком и макроблоком текущего кадра. После того как модуль 32 оценки движения или вычислил вектор движения, или не смог идентифицировать исходный макроблок для каждого макроблока в текущем кадре, модуль 32 оценки движения может обеспечивать вычисленные векторы движения для текущего кадра в модуль 34 формирования восстановленного кадра.

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

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

Фиг.3 является блок-схемой, изображающей иллюстративные детали модуля 12 декодирования. Модуль 12 декодирования может содержать модуль 44 энтропийного декодирования, модуль 46 деквантования, модуль 48 обратного преобразования, модуль 50 восстановления пикселя, буфер 51 кадра, модуль 52 объединителя блоков, модуль 53 управления кадром, модуль 54 хранения кадра ссылки, модуль 56 формирования восстановленного кадра и модуль 58 формирования p-кадра. Некоторые или все эти модули могут содержать подмножества программных команд модуля 12 декодирования. В качестве альтернативы некоторые или все эти модули могут содержать специализированные аппаратные средства или программно-аппаратные средства. В другом варианте эти модули могут содержать программные команды и специализированные аппаратные средства или программно-аппаратные средства.

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

После применения модулем 44 энтропийного декодирования схемы энтропийного декодирования к матрицам квантованных коэффициентов в видеофайле модуль 46 деквантования может деквантовать коэффициенты в каждой из матриц квантованных коэффициентов. В зависимости от стандарта кодирования модуль 46 деквантования может деквантовать коэффициенты множеством способов. Например, согласно части 2 стандарта MPEG-4 модуль 46 деквантования может использовать две вышеупомянутые матрицы квантования двумя различными способами. Во-первых, модуль 46 деквантования может использовать эти матрицы квантования для выполнения деквантования в стиле H.263. В деквантовании в стиле H.263 модуль 46 деквантования получает восстановленные коэффициенты F"[v][u] из квантованных значений QF[v][u] следующим образом:

что включает в себя только одно умножение на quantiser_scale, и

во-вторых, модуль 46 деквантования может использовать эти матрицы квантования для выполнения деквантования в стиле MPEG-l/2. В деквантовании в стиле MPEG-1/2 модуль 46 деквантования использует дополнительные весовые матрицы W[w][v][u], где w указывает, какая весовая матрица используется:

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

После вывода модулем 48 обратного преобразования матрицы значений компонента пикселя модуль 50 восстановления пикселя может формировать матрицу пикселей посредством объединения матрицы значений компонента пикселя с матрицами значений компонента пикселя, связанными с эквивалентными позициями в видеокадре. Например, модуль 50 восстановления пикселя может принимать матрицу значений компонента пикселя Y, матрицу значений компонента пикселя Cb и матрицу значений компонента пикселя Cr из модуля 48 обратного преобразования. Каждая из этих трех матриц может включать в себя компоненты пикселя для одного блока пикселей, 8×8. Каждый из пикселей может включить в себя значение компонента пикселя Y, значение компонента пикселя Cb и значение компонента пикселя Cr. После формирования матрицы пикселей модуль 50 восстановления пикселя может обеспечивать блок пикселей в модуль 52 объединителя блоков.

Когда модуль 52 объединителя блоков принимает блок пикселей, модуль 52 объединителя блоков может помещать в буфер блок пикселей, пока модуль 52 объединителя блоков не примет некоторые или все блоки пикселей в видеокадре. После приема одного или нескольких блоков пикселей модуль 52 объединителя блоков может объединять блоки пикселей в видеокадр и может выводить видеокадр в буфер 51 кадра. Видеокадр может быть сохранен в буфере 51 кадра, пока он не будет отображен блоком 51 воспроизведения мультимедиа. Кроме того, модуль 52 объединителя блоков может выводить видеокадр в модуль 54 хранения кадра. Видеокадры в модуле 54 хранения кадра могут использоваться как кадры ссылки для восстановления p- и b-кадрв. Кроме того, видеокадры в модуле 54 хранения кадра могут быть остаточными кадрами, которые используются при восстановлении p- и b-кадров.

Для восстановления p- или b-кадра модуль 12 декодирования включает в себя модуль 56 формирования восстановленного кадра. Модуль 56 формирования восстановленного кадра принимает декодированные векторы движения из модуля 44 энтропийного декодирования. Кроме того, модуль 56 формирования восстановленного кадра извлекает кадры ссылки текущего кадра из модуля 54 хранения кадра. После этого модуль 56 формирования восстановленного кадра "перемещает" макроблоки из их позиций в кадрах ссылки в позиции, указанные векторами движения. Восстановленный кадр получается в результате перемещения макроблоков этим способом. После формирования восстановленного кадра модулем 56 формирования восстановленного кадра модуль 56 формирования восстановленного кадра обеспечивает восстановленный кадр в модуль 58 формирования p-кадра.

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

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

Вначале, модуль 8 кодирования принимает последовательность незакодированных видеокадров (60). Например, модуль 8 кодирования может принимать последовательность незакодированных кадров в виде наборов пикселей из источника 4 мультимедиа. Когда модуль 8 кодирования принимает последовательность незакодированных кадров, модуль 20 управления кадром в модуле 8 кодирования может устанавливать, должен ли текущий кадр в последовательности незакодированных кадров быть закодирован как i-кадр, или как p-, или b-кадр (62).

Если модуль 20 управления кадром устанавливает, что текущий кадр должен быть закодирован как i-кадр, то модуль 22 разделителя на блоки в модуле 8 кодирования может разделять текущий кадр на блоки пикселей (64). Например, модуль 8 кодирования может разделять текущий кадр на блоки пикселей, 2×2, 4×4 или 8×8.

После разделения текущего кадра на блоки пикселей модуль 24 выделения компонента может разделять значения компонентов пикселя в каждом из блоков пикселей (66). В результате может быть три блока значений компонента пикселя для каждого блока пикселей: блок значений Y, представляющих яркость пикселей, блок значений Cb, представляющих информацию о синем цвете пикселей, и блок значений Cr, представляющих информацию о красном цвете пикселей.

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

После формирования модулем 26 прямого преобразования матриц масштабированных коэффициентов для каждой из матриц компонентов пикселя модуль 28 квантования в модуле 8 кодирования может квантовать коэффициенты в каждой из матриц масштабированных коэффициентов (70). После квантования модулем 28 квантования коэффициентов в каждой матрице масштабированных коэффициентов модуль 30 энтропийного кодирования может выполнять процесс энтропийного кодирования каждой из матриц квантованных коэффициентов (72). Например, модуль 8 кодирования может применять схему кодирования методом Хаффмана или схему арифметического кодирования к каждой матрице квантованных коэффициентов. Процесс энтропийного кодирования также сжимает данные. Однако процессы энтропийного кодирования в результате не приводят к потере информации. После выполнения процесса энтропийного кодирования каждой матрицы квантованных коэффициентов модуль 38 вывода потока в модуле 8 кодирования может добавлять закодированные матрицы квантованных коэффициентов в битовый поток для последовательности видеокадров (74). После добавления модулем 38 вывода потока закодированных матриц в битовый поток модуль 20 управления кадром может устанавливать, был ли текущий кадр последним видеокадром последовательности кадров (76). Если текущий кадр является последним кадром последовательности кадров ("ДА" 76), то модуль 8 кодирования завершает кодирование последовательности кадров (78). С другой стороны, если текущий кадр не является последним кадром последовательности кадров ("НЕТ" 76), то модуль 8 кодирования может возвращаться к началу цикла и устанавливать, должен ли новый текущий кадр быть закодирован как i-кадр (62).

Если текущий кадр не должен быть закодирован как i-кадр ("НЕТ" 62), то модуль 32 оценки движения в модуле 8 кодирования может разделять текущий кадр на ряд макроблоков (80). Затем модуль 32 оценки движения может пытаться идентифицировать исходный макроблок в одном или нескольких кадрах ссылки для каждого из макроблоков в текущем кадре (82). Модуль 32 оценки движения может далее вычислять вектор движения для каждого из макроблоков в текущем кадре, для которых модуль 32 оценки движения смог идентифицировать исходный макроблок (84). После вычисления векторов движения модулем 32 оценки движения модуль 34 формирования восстановленного кадра использует векторы движения для формирования восстановленного кадра посредством "перемещения" идентифицированных макроблоков в кадрах ссылки в позиции, обозначенные векторами движения (86). Модуль 36 формирования остаточного кадра может далее формировать остаточный кадр для текущего кадра посредством вычитания значений компонента пикселя в восстановленном кадре из соответствующих значений компонента пикселя в текущем кадре (88). После формирования остаточного кадра модулем 36 формирования остаточного кадра модуль 30 энтропийного кодирования может использовать схему энтропийного кодирования для кодирования векторов движения для текущего кадра (90). Кроме того, к остаточному кадру может быть применено пространственное кодирование посредством применения этапов с (66) по (74) к остаточному кадру.

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

Вначале модуль 12 декодирования принимает закодированный видеокадр (100). После приема закодированного видеокадра модуль 44 энтропийного декодирования в модуле 12 декодирования может выполнять процесс энтропийного декодирования блоков данных в закодированном кадре (102). Модуль 44 энтропийного декодирования может выполнять процесс энтропийного декодирования, который эквивалентен процессу энтропийного кодирования, используемому для кодирования кадра. Например, если модуль 8 кодирования использует кодирование методом Хаффмана для кодирования кадра, то модуль 44 энтропийного декодирования использует декодирование методом Хаффмана для декодирования кадра. В результате применения процесса энтропийного декодирования к каждому блоку данных в кадре модуль 44 энтропийного декодирования формирует набор матриц квантованных коэффициентов.

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

После вычисления модулем 48 обратного преобразования матрицы значений компонента пикселя для каждой из матриц коэффициентов модуль 50 восстановления пикселя в модуле 12 декодирования может объединять соответствующие матрицы значений компонента пикселя для создания блоков пикселей (108). Например, модуль 12 декодирования может объединять блок значений Y со связанным блоком значений Cr и связанным блоком значений Cb для создания блока пикселей YCrCb. После создания блоков пикселей модулем 50 восстановления пикселя модуль 52 объединителя блоков может повторно объединять блоки пикселей в видеокадр (110).

Затем модуль 53 управления кадром в модуле 12 декодирования может устанавливать, является ли текущий кадр i-кадром (114). Если текущий кадр является i-кадром ("ДА" 114), то модуль 52 объединителя блоков может выводить видеокадр в буфер 51 кадра (114). С другой стороны, если текущий кадр не является i-кадром (то есть текущий кадр является p- или b-кадром) ("НЕТ" 114), то модуль 44 энтропийного декодирования использует схему энтропийного декодирования для декодирования векторов движения текущего кадра (116). Затем модуль 56 формирования восстановленного кадра использует декодированные векторы движения и один или несколько кадров ссылки в модуле 54 хранения кадра для формирования восстановленного кадра (118). После этого модуль 58 формирования p-кадра может использовать восстановленный кадр и кадр, сформированный модулем 52 объединителя блоков, для формирования восстановленного кадра (120).

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

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

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

Значение дополнительного смещения является значением, которое делает положительные ошибки и отрицательные ошибки, в среднем, равными по величине и, в среднем, симметричными относительно нуля. Например, значение дополнительного смещения может (быть) значением знакоадаптивного смещения, которое равно нулю, когда коэффициент DC является неотрицательным, и равно отрицательному значению, когда коэффициент DC является отрицательным. Для добавления значения знакоадаптивного смещения к коэффициенту DC в 16-разрядном процессоре модуль 144 смещения коэффициента может использовать следующую формулу:

DC_coefficient=DC_coefficient+(1<<(P+2))+ (DC_coefficient>>15)

(1)

В формуле (1) терм (1<<(P+2)) добавлен для обеспечения смещения центра. P - константа, относящаяся к количеству битов мантиссы с фиксированной запятой (то есть битов справа от символа, отделяющего целую часть числа от дробной), используемая в преобразовании, выполняемом модулем 146 обратного преобразования вектора. К P прибавляется число 2, потому что модуль 148 сдвига вправо может сдвигать вправо все коэффициенты на (P+3), где число '3' получается из битов точности, добавляемых выполнением обратного дискретного косинусного преобразования. Для детального рассмотрения этого момента, если число x сформировано посредством сдвига влево 1 на (P+2) и число z сформировано посредством сдвига вправо x на (P+3), то z=1/2. (То есть 2^P+2/2^P+3=2⁰/2¹=1/2). Соответственно, добавление (1<<(P+2)) к коэффициенту DC эквивалентно добавлению (1<<(P+3))/2 к коэффициенту DC.

В формуле (1) терм (Dc_coefficient>>15) сдвигает вправо 16-разрядный коэффициент DC на 15 позиций. Оставшийся один бит указывает знак коэффициента DC. Например, предположим, что коэффициентом DC является 0b1111 1100 0011 0101. В этом примере, с расширением знака, сдвиг коэффициента DC вправо на 15 позиций в результате приводит к значению 0b1111 1111 1111 1111 (десятичное число, -1). Аналогично, если коэффициентом DC является 0b0111 1111 1111 1111, то сдвиг коэффициента DC вправо на 15 позиций в результате приводит к значению 0b0000 0000 0000 0000 (десятичное число, 0).

В другом примере значение дополнительного смещения может быть значением смещения дизеринга. Значение смещения дизеринга является значением, которое равно -1 или 0. Для добавления значения знакодизерингового смещения к коэффициенту DC в 16-разрядном процессоре модуль 34 IDCT может использовать следующую формулу:

DC_coefficient=DC_coefficient+(1<<(P+2))+ dither(-1|0)

(2)

В формуле (2) P указывает количество битов мантиссы в DC _coefficient. Терм (1<<(P+2)) добавляет смещение центра. Терм dither(-1|0) указывает, что модуль 34 IDCT выбирает -1 или 0 на псевдослучайной основе.

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

После формирования матрицы смещенных коэффициентов модулем 144 смещения коэффициента модуль 146 обратного преобразования вектора формирует матрицу преобразованных коэффициентов с использованием арифметических операций с фиксированной запятой для неоднократного применения одномерного преобразования к матрице смещенных коэффициентов. Например, модуль 146 обратного преобразования вектора может сформировать матрицу промежуточных значений с использованием арифметических операций с фиксированной запятой для применения одномерного преобразования к каждой вектор-строке коэффициентов в матрице смещенных коэффициентов. Затем модуль 146 обратного преобразования вектора может вычислять матрицу преобразованных коэффициентов с использованием арифметических операций с фиксированной запятой для применения одномерного преобразования к каждому вектор-столбцу в матрице промежуточных значений. Иллюстративные одномерные преобразования изображены на фиг.10 и фиг.11 ниже.

После формирования матрицы преобразованных коэффициентов модулем 146 обратного преобразования вектора модуль 148 сдвига вправо может формировать матрицу скорректированных коэффициентов посредством сдвига вправо каждого из коэффициентов в матрице преобразованных коэффициентов на количество позиций, равное количеству битов, добавленных во время применения преобразования и во время масштабирования. Например, если применение преобразования в результате приводит к дополнительным трем битам и масштабирование коэффициентов добавляет дополнительные три бита, то модуль 148 сдвига вправо может сдвигать вправо каждый из коэффициентов на шесть (3+3) позиций.

Модуль 148 сдвига вправо может выполнять этот сдвиг вправо вместо деления каждого из коэффициентов на 2^b, где b равно количеству дополнительных битов, добавленных модулем 146 обратного преобразования вектора, плюс количество битов, добавленных к части мантиссы коэффициентов модулем 142 масштабирования во время масштабирования. Могут иметь место различия между данными исходного изображения и данными изображения результата из-за различия между x_n/2^b и x_n>>b, где x_n - коэффициент в матрице в позиции n. Некоторые из этих различий могут иметь место из-за ошибок округления, относящихся к факту, что при ограниченной точности арифметических операций с фиксированной запятой (x_n>>b) не равно (x_n/2^b) для всех значений x_n. Например, модуль 8 кодирования может использовать шестнадцатибитовые числа с фиксированной запятой и x_n=63 (0000 0000 0011 1111 в двоичном представлении) и b=6. В этом примере сдвиг 0000 0000 0011 1111 вправо на шесть позиций в результате приводит к двоичному значению 0000 0000 0000 0000. Следовательно, 63>>6=0. При этом 63/2⁶=31/64=0,984375. Разность между 0 и 0,984 может в результате привести к визуальному различию между исходным изображением и изображением результата.

Добавление значений смещения к коэффициенту DC уменьшает различия из-за ошибок округления. Например, модуль 144 смещения коэффициента может добавлять значение смещения центра c к x_n. Значение смещения центра c может равняться 2^b/2=2^(b-1). Например, если b=6, то c=2⁶/2=64/2=32. В этом примере если x_n=63, то 63+32=95 (0b0000 0000 0101 1111). 95, сдвинутое вправо на 6 позиций=1 (0b0000 0000 0000 0001 в двоичном представлении). Значение 1, полученное после добавления значения смещения центра ближе к правильному значению 0,984375, чем значение 0, полученное без добавления значения смещения центра.

В дополнение к добавлению значения смещения центра c модуль 144 смещения коэффициента также может добавлять значение дополнительного смещения к коэффициенту DC. Например, модуль 144 смещения коэффициента может добавлять значение знакоадаптивного смещения d(x_n). Значение знакоадаптивного смещения d(x_n) может равняться -1, когда x_n является отрицательным и может равняться 0 в противном случае. Добавление значения знакоадаптивного смещения d(x_n) может в результате привести к значениям, которые являются лучшими аппроксимациями, чем значения без значения знакоадаптивного смещения d(x_n). Например, без значения знакоадаптивного смещения d(x_n) функция (x_n+c)>>b не является симметричной относительно 0. Например, если x_n=32, b=6 и c=32, то (x_n+c)>>b=1. Однако если x_n=-32, b=6 и c=32, то (x_n+c)>>b=0. Это отсутствие симметрии относительно нуля может в результате привести к постепенному накоплению ошибок при вычислении последовательных видео p-кадров. Кроме того, разности между x_n>>b и x_n/2^b больше при x_n больше нуля, чем при x_n меньше нуля. Это также может приводить к ошибкам.

Значение знакоадаптивного смещения d(x_n) может исправить эти проблемы. Например, предположим, что x_n=32, b=6, c=32, тогда d(x_n)=0. Следовательно, (x_n+c+d(x_n))>>b=1. Теперь предположим, что x_n=-32, b=6, c=32, тогда d(x_n)=-1. Следовательно, (x_n+c+d(x_n))>>b=-1. Этот пример иллюстрирует, что функция (x_n+c+d(x_n))>>b теперь симметрична относительно 0, и не получается разностей, которые больше при x_n больше нуля, чем при (x_n) меньше нуля.

В альтернативной реализации модуль 144 смещения коэффициента может добавлять значение смещения дизеринга e вместо добавления значения знакоадаптивного смещения d. Когда модуль 144 смещения коэффициента добавляет значение смещения дизеринга e к коэффициенту DC, модуль 144 смещения коэффициента может выбирать или значение 0, или значение -1 в качестве значения e на псевдослучайной основе. Для выбора значения смещения дизеринга e модуль 144 смещения коэффициента может включить в себя следующие команды:

#define IBl 1

#define IB2 2

#define IB5 16

#define IBl8 131072

#define MASK (IB1+IB2+IB5)

static unsigned long iseed=OxAAAAAAAA;

int ditherBit() {

if (iseed & IB18) {

iseed=((iseed ^Λ MASK)<<1) | IBl;

return 1;

} else {

iseed<<=1;

return 0;

}

}

Многие стандарты кодирования видео используют то, что известно как группа изображений ("GOP"). GOP содержит i-кадр и набор p-кадров и/или b-кадров, которые ссылаются на i-кадр и/или другие p- или b-кадры в GOP. Например, файл мультимедиа может включать в себя i-кадр, который закодирован с использованием набора матриц коэффициентов. Для формирования последовательности видео модуль 12 декодирования может формировать p-кадры на основе этого i-кадра. Ошибки, вызываемые декодированием i-кадра, отражаются в p-кадре, основанном на i-кадре. Кроме того, ошибки, вызываемые декодированием p-кадра, включаются в следующий p-кадр. Если ошибки, вызываемые декодированием кадров, не симметричны относительно нуля или имеют тенденцию к большему положительному или отрицательному значению, то эти ошибки могут быстро увеличивать или уменьшать значения компонента пикселя в последовательных p-кадрах. Например, если ошибки имеют тенденцию к большей положительной ошибке, то эти ошибки могут суммироваться в последовательных p-кадрах, что в результате приводит к большим значениям компонента пикселя, чем правильные значения компонента пикселя. В результате пиксели в последовательных p-кадрах в GOP могут ошибочно изменить цвет или яркость. Это известно как ошибка дрейфа. Во избежание слишком серьезной ошибки дрейфа из i-кадра может быть сформировано только ограниченное количество кадров. Из-за округления ошибки могут быть большими по величине при выполнении преобразования с использованием чисел с фиксированной запятой, у которых количество битов мантиссы ограничено (например, три бита мантиссы), чем при выполнении преобразования с использованием чисел с большей точностью. Следовательно, ошибка дрейфа может быть особенно проблематичной при выполнении преобразования с использованием чисел с фиксированной запятой, у которых количество битов мантиссы ограничено.

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

После сдвига вправо коэффициентов модулем 148 сдвига вправо модуль 150 ограничения может "ограничивать" коэффициенты для ограничения их максимальным допустимым диапазоном значений компонента пикселя. Например, в типичном изображении JPEG значение цветового компонента может находиться в пределах от -256 до 255. Если матрица коэффициентов должна включать в себя коэффициент, равный 270, то модуль 150 ограничения ограничивает этот коэффициент максимальным допустимым диапазоном с уменьшением этого коэффициента до 255. После окончания ограничения коэффициентов модулем 150 ограничения эти коэффициенты могут представлять значения компонента пикселя. Когда модуль 150 ограничения заканчивает ограничение коэффициентов в матрице, модуль 150 ограничения может обеспечивать матрицу ограниченных коэффициентов в модуль 152 вывода.

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

Фиг.7 является блок-схемой последовательности операций, изображающей иллюстративную работу модуля 34 обратного преобразования. Вначале модуль 140 ввода принимает матрицу деквантованных коэффициентов (170). Когда модуль 140 ввода принимает матрицу деквантованных коэффициентов, модуль 142 масштабирования может масштабировать каждое значение в матрице деквантованных коэффициентов, тем самым формируя матрицу масштабированных коэффициентов (172). Например, модуль 142 масштабирования может выполнять операции, в которых умножают каждый коэффициент в матрице деквантованных коэффициентов на значения в матрице масштабных множителей, которые находятся в эквивалентных позициях.

После формирования матрицы масштабированных коэффициентов модулем 142 масштабирования модуль 144 смещения коэффициента может добавлять значение смещения центра и значение дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов, тем самым формируя матрицу смещенных коэффициентов (174). После добавления значения смещения к коэффициенту DC матрицы модулем 144 смещения коэффициента модуль 146 обратного преобразования вектора может устанавливать, меньше ли счетчик строки, чем максимум счетчика строки (176). Вначале счетчик строки может быть установлен в ноль. Максимум счетчика строки может быть статическим значением, которое равно количеству строк в матрице коэффициентов. Например, если матрица коэффициентов включает в себя восемь строк, то максимум счетчика строки равен восьми.

Если счетчик строки меньше, чем максимум счетчика строки ("ДА" 176), то модуль 146 обратного преобразования вектора может (использовать) арифметические операции с фиксированной запятой для применения одномерного преобразования вектор-строки матрицы коэффициентов, указываемой счетчиком строки (178). Когда модуль 146 обратного преобразования вектора применяет преобразование вектор-строки матрицы коэффициентов, модуль 146 обратного преобразования вектора может заменять исходные коэффициенты в этой вектор-строке коэффициентов вектором промежуточных коэффициентов. После применения преобразования вектор-строки матрицы коэффициентов модулем 146 обратного преобразования вектора модуль 146 обратного преобразования вектора может увеличить счетчик строки (180). После этого модуль 146 обратного преобразования вектора может возвращаться к началу цикла и снова устанавливать, меньше ли счетчик строки, чем максимум счетчика строки (176).

Если счетчик строки не меньше (то есть больше или равен), чем максимум счетчика строки ("НЕТ" 176), то модуль 146 обратного преобразования вектора может устанавливать, меньше ли счетчик столбца, чем максимум счетчика столбца (182). Вначале счетчик столбца может быть установлен в ноль. Максимум счетчика столбца может быть статическим значением, которое равно количеству столбцов в матрице коэффициентов. Например, если матрица коэффициентов включает в себя восемь столбцов, то максимум счетчика столбца равен восьми.

Если счетчик столбца меньше, чем максимум счетчика столбца ("ДА" 182), то модуль 146 обратного преобразования вектора может применять одномерное преобразование вектор-столбца матрицы промежуточных коэффициентов, указываемого счетчиком столбца (184). Когда модуль 34 обратного преобразования применяет преобразование вектор-столбца промежуточных коэффициентов, модуль 34 обратного преобразования заменяет промежуточные коэффициенты в вектор-столбце вектором преобразованных коэффициентов.

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

Если счетчик столбца не меньше (то есть больше или равен), чем максимум счетчика столбца ("НЕТ" 182), то модуль 148 сдвига вправо может сдвигать вправо каждый из преобразованных коэффициентов в матрице (188). Когда модуль 148 сдвига вправо сдвигает вправо коэффициент, модуль 148 сдвига вправо может сдвигать этот коэффициент вправо на определенное количество позиций. Результатом сдвига вправо каждого из вторых промежуточных коэффициентов в матрице является матрица скорректированных значений. После сдвига вправо каждого из преобразованных коэффициентов модулем 148 сдвига вправо модуль 150 ограничения может ограничивать скорректированные коэффициенты для обеспечения того, что скорректированные коэффициенты находятся в пределах соответствующего диапазона для значений компонента пикселя (190). Например, модуль 150 ограничения может ограничивать скорректированные коэффициенты для обеспечения того, что скорректированные коэффициенты находятся в пределах диапазона от -256 до 255. Когда модуль 150 ограничения закончит ограничение скорректированных коэффициентов, модуль 152 вывода может выводить получающуюся в результате матрицу значений компонента пикселя (192).

Фиг.8 является блок-схемой последовательности операций, изображающей иллюстративные детали модуля 26 прямого преобразования. Как изображено в примере фиг.8, модуль 26 прямого преобразования содержит модуль 210 ввода, который принимает матрицу значений компонента пикселя из модуля 24 выделения компонента. Когда модуль 210 ввода принимает матрицу значений компонента пикселя, модуль 210 ввода может обеспечивать матрицу значений компонента пикселя в модуль 212 сдвига влево. Модуль 212 сдвига влево может сдвигать все значения компонента пикселя в матрице значений компонента пикселя влево на количество битов мантиссы, используемых в значениях, которые модуль 214 прямого преобразования вектора использует при выполнении прямого преобразования, минус количество битов мантиссы, удаленных при выполнении прямого преобразования. Например, если в значениях при выполнении прямого преобразования используются десять битов мантиссы и при выполнении прямого дискретного косинусного преобразования три бита мантиссы удаляются, то модуль 212 сдвига влево может сдвигать значения компонента пикселя влево на семь позиций. В другом примере если в значениях при выполнении прямого преобразования используются три бита мантиссы и при выполнении прямого преобразования три бита мантиссы удаляются, то модуль 212 сдвига влево может сдвигать значения компонента пикселя влево на ноль позиций.

После сдвига значений компонента пикселя модулем 212 сдвига влево модуль 214 прямого преобразования вектора может применять прямое преобразование к каждому вектор-столбцу в матрице значений компонента пикселя для формирования матрицы промежуточных значений. Затем модуль 214 прямого преобразования вектора может применять прямое преобразование к каждой вектор-строке в матрице промежуточных значений для формирования матрицы преобразованных коэффициентов. Когда модуль 214 прямого преобразования вектора применяет прямое преобразование к вектору, модуль 214 прямого преобразования вектора может применять прямое преобразование, описанное в фиг.12, ниже. Отметим, что преобразование, описанное в фиг.12, ниже, является преобразованием, описанным в фиг.11, выполняемым в обратном порядке.

После формирования матрицы преобразованных коэффициентов модулем 214 прямого преобразования вектора модуль 216 масштабирования может применять масштабные множители к каждому преобразованному коэффициенту в матрице преобразованных коэффициентов. Модуль 216 масштабирования может применять обратные величины масштабных множителей, используемых модулем 142 масштабирования в модуле 48 обратного преобразования. Например, если одно или несколько значений были вынесены за скобки преобразования для улучшения эффективности преобразования, то эти значения могут стать базисом матрицы масштабных множителей. Коэффициенты в матрице преобразованных коэффициентов могут быть скорректированы посредством умножения коэффициентов на эти значения.

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

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

Следующее уравнение суммирует влияния модуля 216 масштабирования, модуля 218 смещения коэффициента и модуля 220 сдвига вправо на матрицу преобразованных коэффициентов, когда модуль 218 смещения коэффициента добавляет значение знакоадаптивного смещения:

F[v][u]=(F'[v][u]*S[v][u]+(1<<(P+Q)-((F'[v][u]>=0)?0:1))>>(P+Q)

где v=0..7, u=0..7, где S[v][u] - элемент в матрице масштабных множителей, F - матрица масштабированных коэффициентов, F' - матрица преобразованных коэффициентов, P указывает количество битов мантиссы в коэффициентах в матрице преобразованных коэффициентов и Q указывает количество битов, добавленных к коэффициентам в матрице преобразованных коэффициентов применением преобразования.

Следующее уравнение суммирует влияния модуля 216 масштабирования, модуля 218 смещения коэффициента и модуля 220 сдвига вправо на матрицу преобразованных коэффициентов, когда модуль 218 смещения коэффициента добавляет значение смещения дизеринга:

F[v][u]=(F'[v][u]*S[v][u]+(1<<19)-(dither(0:1))>>20

где v=0..7, u=0..7, где S[v][u] - элемент в матрице масштабных множителей, F - матрица масштабированных коэффициентов и F' - матрица преобразованных коэффициентов.

После формирования матрицы масштабированных коэффициентов модулем 216 масштабирования модуль 222 вывода может выводить матрицу коэффициентов в модуль 28 квантования.

Фиг.9 является блок-схемой последовательности операций, изображающей иллюстративную работу модуля 26 прямого преобразования. Вначале модуль 210 ввода принимает матрицу значений компонента пикселя (230). Когда модуль 140 ввода принимает матрицу значений компонента пикселя, модуль 212 сдвига влево может формировать матрицу скорректированных коэффициентов посредством сдвига влево каждого значения в матрице значений компонента пикселя (232). Например, модуль 212 сдвига влево может сдвигать все коэффициенты влево на десять позиций. В этом примере модуль 212 сдвига влево может сдвигать все коэффициенты вправо на десять позиций, потому что модуль 214 прямого преобразования вектора может использовать арифметические операции с фиксированной запятой, в которых числа закодированы с использованием десяти битов в дробной части. Соответственно, посредством сдвига коэффициентов влево на десять позиций модуль 212 сдвига влево фактически преобразует значения компонента пикселя в числа с фиксированной запятой с десятью битами мантиссы.

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

Если счетчик столбца меньше, чем максимум счетчика столбца ("ДА" 234), то модуль 214 прямого преобразования вектора может вычислять одномерное прямое преобразование вектор-столбца, указываемого счетчиком столбца (236). Когда модуль 214 прямого преобразования вектора вычисляет прямое преобразование вектор-столбца матрицы скорректированных коэффициентов, модуль 214 прямого преобразования вектора заменяет исходные скорректированные коэффициенты в вектор-столбце промежуточными коэффициентами. После вычисления прямого преобразования вектор-столбца матрицы скорректированных коэффициентов модулем 214 прямого преобразования вектора модуль 214 прямого преобразования вектора может увеличить счетчик столбца (238). После этого модуль 214 прямого преобразования вектора может возвращаться к началу цикла и снова устанавливать, меньше ли счетчик столбца, чем максимум счетчика столбца (234).

Если счетчик столбца не меньше (то есть больше или равен), чем максимум счетчика столбца ("НЕТ" 234), то модуль 214 прямого преобразования вектора может устанавливать, меньше ли счетчик строки, чем максимум счетчика строки (240). Вначале счетчик строки может быть установлен в ноль. Максимум счетчика строки может быть статическим значением, которое равно количеству вектор-строк в матрице коэффициентов. Например, если матрица коэффициентов включает в себя восемь строк, то максимум счетчика строки равен восьми.

Если счетчик строки меньше, чем максимум счетчика строки ("ДА" 240), то модуль 214 прямого преобразования вектора может вычислять одномерное дискретное косинусное преобразование вектор-строки, указываемой счетчиком строки (242). Поскольку модуль 214 прямого преобразования вектора уже вычислил прямое преобразование вектор-строк матрицы, то матрица коэффициентов теперь содержит промежуточные коэффициенты. Когда модуль 214 прямого преобразования вектора вычисляет прямое преобразование вектор-строки промежуточных коэффициентов, модуль 214 прямого преобразования вектора заменяет промежуточные коэффициенты в вектор-столбце преобразованными коэффициентами.

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

Если счетчик строки не меньше (то есть больше или равен), чем максимум счетчика строки ("НЕТ" 240), то модуль 216 масштабирования может масштабировать каждый преобразованный коэффициент в матрице преобразованных коэффициентов (246). После формирования матрицы масштабированных коэффициентов модулем 216 масштабирования модуль 218 смещения коэффициента может формировать матрицу смещенных коэффициентов посредством добавления одного или нескольких значений смещения к коэффициентам в матрице масштабированных коэффициентов (248). Например, модуль 218 смещения коэффициента может добавлять значение смещения центра и значение дополнительного смещения дизеринга или знакоадаптивного смещения к каждому коэффициенту в матрице масштабированных коэффициентов. Затем модуль 220 сдвига вправо может сдвигать вправо каждый коэффициент в матрице смещенных коэффициентов (250). Модуль 220 сдвига вправо может формировать матрицу скорректированных коэффициентов посредством сдвига вправо каждого коэффициента на количество битов мантиссы в каждом из коэффициентов плюс количество битов, добавляемых к коэффициенту применением преобразования. После формирования матрицы скорректированных коэффициентов модулем 220 сдвига вправо модуль 222 вывода может выводить получающуюся в результате матрицу скорректированных коэффициентов (252).

Фиг.10 является блок-схемой, изображающей первое иллюстративное одномерное преобразование 260. Как изображено в примере фиг.10, преобразование 260 может взять в качестве входных значений X₀ по X₇. Значения X₀ по X₇ могут представлять коэффициенты одной строки или столбца матрицы входных коэффициентов. Преобразование 260 может выводить значения x₀ по x₇. Когда значения X₀ по X₇ являются значениями в строке коэффициентов в матрице входных коэффициентов, значения x₀ по x₇ могут представлять строку промежуточных значений. Когда значения X₀ по X₇ являются значениями в столбце коэффициентов, значения x₀ по x₇ могут представлять столбец сдвинутых значений компонента пикселя. Как изображено в примере фиг.10, кружками с символами "+" внутри обозначены операции суммирования, и кружками с символами "X" внутри обозначены операции умножения. Комбинации буква/число обозначают значения, на которые умножается значение. Например, в строке x2 символ "A1" помещен над кружком с символом "X" внутри. Это указывает, что значение в строке X₂ умножается на значение A1.

Преобразование 260 включает в себя набор "операций структуры бабочки". "Операция структуры бабочки" может быть программной или аппаратной структурой, в которой первое выходное значение u вычисляется умножением первого входного значения x на первый множитель C для создания первого промежуточного значения, умножением второго входного значения y на второй множитель S для создания второго промежуточного значения и затем суммированием первого промежуточного значения и второго промежуточного значения. В этой более сложной "операции структуры бабочки" второе выходное значение v может быть вычислено посредством умножения второго входного значения y на первый множитель для создания третьего промежуточного значения, умножения первого входного значения x на второй множитель S для создания четвертого промежуточного значения и затем вычитанием третьего промежуточного значения из четвертого промежуточного значения. В следующих формулах суммируется математический результат "операции структуры бабочки":

u=x*C+y*S;

v=x*S-y*C.

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

Как используется в преобразовании 260, первый множитель C и второй множитель S могут быть иррациональными числами. Например, C может быть равным и S может быть равным

Поскольку модуль 146 обратного преобразования вектора может использовать арифметические операции с фиксированной запятой в 16-разрядных регистрах и поскольку C и S часто являются иррациональными значениями, то умножение входных значений x и y на C и S может быть трудным в вычислительном отношении. Поэтому модуль 146 обратного преобразования вектора может использовать аппроксимации рациональным числом для C и S. Эти целочисленные аппроксимации могут быть в виде (C'/2^j) и (S'/2^k), где C' и S' являются "преобразованными к целому числу" версиями C и S и j и k являются целыми числами. Например, пусть C=.

В этом примере модуль 146 обратного преобразования вектора может использовать целочисленные значения C=2217 и j=12 для аппроксимации , потому что 2217/2¹²=0,541259766 и ≈0,5411961…. В этом примере ясно, что 0,5411961 приблизительно равно 0,541259766. Соответственно, вычисления вида

u=x*C+y*S;

v=x*S-y*C

могут быть заменены вычислениями вида

u'=x*(C'/2^j)+y*(S'/2^k);

v'=x*(S'/2^k)-y*(C'/2^j).

Для дальнейшего упрощения этих вычислений операции деления на 2^j и 2^k могут быть заменены поразрядными операциями сдвига вправо на j и k позиций, обозначенных с использованием символа ">>":

u''=((x*C')>>j)+((y*S')>>k);

v''=((x*S')>>k)-((y*C')>>j).

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

u'''=(x*C'+(1<<(j-1))>>j)+(y*S'+(l<<(k-1))>>k);

v'''=(x*S'+(1<<(k-1))>>k)-(y*C'+(1<<(j-1))>>j).

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

Средняя разность между v=x*S-y*C и v''=((x*S')>>k)-((y*C')>>j) приблизительно равна нулю. Другими словами, среднее значение всех значений (v''-v) для всех значений x и y приблизительно равны нулю. Кроме того, средняя разность между v=x*S-y*C и v'''=((x*S'+(1<<(k-1))>>k)-((y*C'+(l<<(j-1))>>j) также приблизительно равна нулю. Это потому, что v'' и v''' всегда приблизительно равны. v'' и v''' всегда приблизительно равны, потому что, когда j равно k, значение смещения центра взаимно сокращается при вычитании:

v'''=((x*C'+m)>>j)-((y*S'+m)>>k)≈

(x*C'+m)/2^j-(y*S'+m)/2^k=

(x*C')/2^j+(m/2^j)-(y*S')/2^k-(m/ 2^k)=

(x*C')/2^j-(y*S')/2^k≈

v''=((x*C')>>j)-((y*S')>>k)

где m представляет значение смещения центра. Как иллюстрируется в этом примере, при вычитании (m/2^k) из (m/2^j), когда j равно k, значение смещения центра m взаимно сокращается. Поскольку средняя разность между v и v'' приблизительно равна нулю, то модуль 146 обратного преобразования вектора не вносит систематического положительного или отрицательного смещения в значения, сформированные вычислением v'' вместо v''', и поскольку v'' и v''' приблизительно равны, то модуль 146 обратного преобразования вектора может использовать v'' вместо v'''.

Средняя разность между u=x*C+y*S и u'''=((x*C'+(1<<(j-1))>>j)+((y*S'+(l<<(k-1))>>k) также приблизительно равна нулю. Вместе с тем разность между u=x*C+y*S и u''=((x*C')>>j)+((y*S')>>k) не находится вблизи нуля. Скорее, средняя разность между u и u'' приблизительно равна -1/2. Соответственно, u'' и u''' не равны приблизительно. u'' и u''' не равны приблизительно, потому что значения смещения центра взаимно не сокращаются, даже когда j равно k:

u'''=((x*C'+m)>>k)+((y*S'+m)>>k)≈

((x*C'+m)/2^j)+((y*S'+m)/2^k)=

((x*C')/2^j)+(m/2^j)+((y*S')/2^k)+(m/2^k)=

((x*C')/2^j)+((y*S')/2^k)+(m/2^j)+(m/2^k)≠

u''=((x*C')>>j)+((y*S')>>k).

Поскольку u'' не равно u''' приблизительно, u'' нельзя использовать вместо u'''. Попытка использовать u'' вместо u''' может в результате привести к существенным различиям с u.

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

u''''=((x*C')>>j)-((y*-S')>>k).

u'''' равно u'', за исключением того, что в u'''' используется версия S' со знаком минус, и вычитается ((y*-S)>>k). Подобно u''', u'''' не добавляет значений смещения центра. Однако в отличие от u''' разности между u'''' и u сосредоточены вокруг 0. Поскольку разности между u'''' и u сосредоточены вокруг нуля, то ошибки округления не увеличиваются при применении последующих операций структуры бабочки. Поэтому модуль 146 обратного преобразования вектора может использовать u'''' для вычисления u в операции структуры бабочки. Поэтому, когда j равно k, операции структур бабочки, используемые модулем 146 обратного преобразования вектора для применения преобразования 260, могут иметь следующий вид:

u''''=((x*C')>>j)-((y*-S')>>k);

v'''=((x*S')>>k)-((y*C')>>j).

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

В качестве альтернативы, при j, равном k, модуль 146 обратного преобразования вектора может использовать операции структуры бабочки, в которых сдвиги вправо отложены до конца операции структуры бабочки:

u'=x*(C'/2^k)+y*(S'/2^k);

((x*C')/2^k)+((y*S')/2^k)=

((x*C')+(y*S'))/2^k≈

u*=(((x*C')+(y*S')+(1<<(k-1)))>>k;

v'=x*(S'/2^k)-y*(C'/2^j)=

((x*S')/2^k)-((y*C')/2^k)=

((x*S')/2^k)+((-l)(y*C')/2^k)=

((x*S')/2^k)+((y*-C')/2^k)=

((x*S')+(y*-C'))/2^k≈

v*=((x*S')+(y*-C')+(1<<(k-1)))>>k.

Перенос сдвигов вправо на конец операции структуры бабочки может уменьшить общее количество операций сдвига, необходимых для выполнения операции структуры бабочки, и может улучшить точность. Кроме того, четырехэлементные команды умножения-накопления, доступные на самом современном 16-разрядном процессоре с одним потоком команд и многими потоками данных ("SIMD") и цифровых сигнальных процессорах, могут эффективно использоваться для вычисления u* и v*.

Операции умножения могут требовать больших вычислительных затрат по сравнению с операциями поразрядного сдвига, вычитания и сложения. Поэтому может оказаться проще использовать последовательность операций поразрядного сдвига, вычитания и сложения, которые дают результат, идентичный результату операции умножения. Например, предположим, что C'=2217. В этом примере r=x*C' может быть заменено следующими этапами:

x2=(x<<3)-x;

x3=x+(x2<<6);

x4=x3-x2;

r=x3+(x4<<2).

В этом примере x2, x3 и x4 являются промежуточными значениями. Для иллюстрации этого рассмотрим пример, где x=1:

7=(1<<3)-1;

449=1+(7<<6);

442=449-7;

2217=449+(442<<2).

2217=(1*2217)=(x*2217, где x=1).

В этом примере 1*2217=2217 и значение, сформированное этими последовательными операциями, при x=1 равно 2217.

В следующей таблице суммирован иллюстративный набор аппроксимаций целочисленным значением, который модуль 146 обратного преобразования вектора может использовать для постоянных множителей A1, A2, B1, B2, C1, C2, D1 и D2.

Таблица 1

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

В таблице 1 значения в столбце "Целочисленное значение" аппроксимируют значения в столбце "исходное значение", когда разделены на 2¹²=4096. Например, 2217/4096=0,541259766 и ≈0,5411961. Аналогично, 5352/4096=1,30664062 и ≈1,30656296. Формулы в столбце "Алгоритм для вычисления произведений" суммируют способы, которые модуль 146 обратного преобразования вектора может использовать вместо операций умножения на соответствующие целочисленные значения.

Фиг.11 является схемой, иллюстрирующей второй иллюстративный алгоритм 270. Как и в фиг.10, значения X₀, X₁, X₂, X₃, X₄, X₅, X₆ и X₇ представляют входные коэффициенты, и значения x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇ представляют выходные значения. Значение, связанное с линией после кружка с символом "+" внутри, является результатом добавления значений, связанных со стрелками, которые указывают в этот кружок. Значение, связанное с линией после кружка с символом "x" внутри, является результатом умножения коэффициента, помещенного рядом с кружком, и значений, связанных с линиями, которые проходят через кружки. Символ "-" рядом со стрелкой представляет взятие со знаком минус значения, связанного со стрелкой. Например, если значение "10" связано со стрелкой перед символом "-", то со стрелкой после символа "-" связано значение "-10". Кроме того, следует отметить, что описанные выше способы уменьшения ошибки округления, использующие коэффициенты, взятые со знаком минус, и вычитание могут использоваться в алгоритме 190.

В преобразовании 270 значения α=β= γ= δ=, ε= и ζ= могут быть аппроксимированы с использованием рациональных дробей. Например, значения α, β, γ, δ, ε и ζ могут быть аппроксимированы с использованием целочисленных аппроксимаций, перечисленных в таблице 2 ниже.

Таблица 2

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

В таблице 2 значения в столбце "Целочисленная аппроксимация" представляют преобразованную к целому числу версию значений в столбце "Исходное значение". Например, ≈0,5411961 и 8867/16384=0,54119873046875. Уравнения в столбце "Алгоритм для вычисления произведений" таблицы 2 представляют алгоритмы, посредством которых модуль 146 обратного преобразования вектора может использовать вместо операций умножения на значения в столбце "целочисленная аппроксимация".

Фиг.12 является блок-схемой, изображающей иллюстративное преобразование 200, которое может использоваться модулем 214 прямого преобразования вектора. На фиг.12 значения X₀, X₁, X₂, X₃, X₄, X₅, X₆ и X₇ представляют выходные коэффициенты и значения x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇ представляют входные значения. Кроме того, следует отметить, что описанные выше способы уменьшения ошибки округления, использующие коэффициенты, взятые со знаком минус, и вычитание могут использоваться в преобразовании 270.

В примере фиг.12 значение α=

β= γ= δ=, ε= и ζ= могут быть аппроксимированы с использованием рациональных дробей. Например, значения α, β, γ, δ, ε и ζ могут быть аппроксимированы с использованием целочисленных аппроксимаций, перечисленных в таблице 2.

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

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

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

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

2. Способ по п.1, в котором формирование матрицы смещенных коэффициентов содержит добавление значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов, и
в котором значение смещения центра равно 2^(P+T-l), где Р равно первому значению, и Т является количеством битов, добавляемых выполнением преобразования.

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

4. Способ по п.3, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.

5. Способ по п.3, причем этот способ также содержит выбор на псевдослучайной основе значения, которое равно или -1 или 0, и
в котором добавление значения дополнительного смещения содержит добавление выбранного значения.

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

7. Способ по п.6, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.

8. Способ по п.7, в котором вторым значением является три, и в котором с учетом матрицы входных коэффициентов значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).

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

10. Способ по п.1, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.

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

12. Устройство по п.11, в котором модуль смещения коэффициента добавляет значение смещения центра к коэффициенту DC матрицы масштабированных коэффициентов,
причем значение смещения центра равно 2^(P+T-1), где Р равно первому значению, и Т является количеством битов, добавляемых выполнением преобразования.

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

14. Устройство по п.13, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.

15. Устройство по п.13, в котором модуль смещения коэффициента выбирает на псевдослучайной основе значение, которое равно или -1 или 0, и
в котором модуль смещения коэффициента добавляет выбранное значение как значение дополнительного смещения.

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

17. Устройство по п.16, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.

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

19. Устройство по п.18, в котором средство для формирования матрицы смещенных коэффициентов содержит средство для добавления значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов,
причем значение смещения центра равно 2^(P+T-1), где Р равно первому значению, и Т является количеством битов, добавляемых выполнением преобразования.

20. Устройство по п.18, в котором средство для формирования матрицы смещенных коэффициентов содержит средство для добавления значения дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
в котором добавление значений дополнительного смещения к коэффициенту DC делает положительные ошибки и отрицательные ошибки, в среднем равными по величине и в среднем симметричными относительно нуля, и
в котором ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2^P, где Р равно первой величине, без учета точности.

21. Устройство по п.20, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.

22. Устройство по п.20, причем устройство также содержит средство для выбора на псевдослучайной основе значения, которое равно или -1 или 0, и
причем средство для добавления значения дополнительного смещения добавляет выбранное значение как значение дополнительного смещения.

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

24. Устройство по п.23, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.

25. Устройство по п.24, в котором вторым значением является три, и в котором с учетом матрицы входных коэффициентов значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).

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

27. Устройство по п.18, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.

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

29. Машиночитаемый носитель информации по п.28, в котором команды, которые вызывают формирование процессором матрицы смещенных коэффициентов, вызывают добавление процессором значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов, и
в котором значение смещения центра равно 2^(P+T-l), где Р равно первому значению, и Т является количеством битов, добавляемых выполнением преобразования.

30. Машиночитаемый носитель информации по п.28, в котором команды, которые вызывают формирование процессором матрицы смещенных коэффициентов, вызывают добавление процессором значения дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
причем добавление значения дополнительного смещения к коэффициенту DC вызывает положительные ошибки и отрицательные ошибки, в среднем равными по величине и в среднем симметричными относительно нуля, и
причем упомянутые ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2^P, где Р равно первой величине, без учета точности.

31. Машиночитаемый носитель информации по п.30, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.

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

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

34. Машиночитаемый носитель информации по п.33, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.

35. Машиночитаемый носитель информации по п.34, в котором вторым значением является три, и
в котором с учетом матрицы входных коэффициентов значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).

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

37. Машиночитаемый носитель информации по п.28, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.

38. Способ вычисления обратного дискретного косинусного преобразования, содержащий:
выполнение последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования, и
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля,
причем использование последовательности операций структуры бабочки содержит выполнение операции структуры бабочки вида:
u=((x*C)>>k)-((y*-S)>>k');
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате числа с фиксированной запятой,
С, S, k и k' - постоянные целые числа,
х и у - переменные с фиксированной запятой, и
C/2^k и S/2^k - аппроксимации рациональным числом иррациональных констант.

39. Способ по п.38, в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z₀, z₁, z₂, z₃, z₄, z₅, z₆ и z₇, и
причем выполнение любой из операций структуры бабочки содержит:
выполнение первой операции структуры бабочки, в которой x=x₀, y=x₄, C=1, S=1, u=x₀' и v=x₄',
выполнение второй операции структуры бабочки, в которой x=x₂, y=x₆, C=α, S=β, u=x₆', v=x₂',
выполнение третьей операции структуры бабочки, в которой x=x₇, y=x₁, C=1, S=1, u=x₇' и v=x₁',
выполнение четвертой операции структуры бабочки, в которой x=*x₁', y=x₅, C=1, S=1, u=x₁'' и v=x₅',
выполнение пятой операции структуры бабочки, в которой x=*x₇', y=x₃, C=1, S=1, u=x₇'' и v=x₃',
выполнение шестой операции структуры бабочки, в которой x=x₀', y=x₆', C=1, S=1, u=x₀'' и v=x₆'',
выполнение седьмой операции структуры бабочки, в которой x=x₄', y=x₂', C=1, S=1, u=x₄'' и v=x₂'',
выполнение восьмой операции структуры бабочки, в которой x=x₁'', y=x₇'', C=ζ, S=ε, u=x₁''' и v=x₇''',
выполнение девятой операции структуры бабочки, в которой x=x₃', y=x₅', C=δ, S=γ, u=x₅'' и v=x₃'',
выполнение десятой операции структуры бабочки, в которой x=x₀'', y=x₇''', C=1, S=1, u=z₀ и v=z₇,
выполнение одиннадцатой операции структуры бабочки, в которой x=x₄'', y=x₅'', C=1, S=1, u=z₁ и v=z₆,
выполнение двенадцатой операции структуры бабочки, в которой x=x₂'', y=x₃'', C=1, S=1, u=z₂ и v=z₅, и
выполнение тринадцатой операции структуры бабочки, в которой x=x₆'', y=x₁''', C=1, S=1, u=z₃ и v=z₄.

40. Способ по п.39, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений и соответственно.

41. Способ по п.40, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.

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

43. Устройство для вычисления обратного дискретного косинусного преобразования, содержащее:
модуль обратного преобразования, который использует последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования,
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля,
причем одна из операций структуры бабочки, выполненная модулем обратного преобразования, имеет вид:
u=((x*C)>>k)-((y*-S)>>k'),
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате значения с фиксированной запятой,
С, S, k и k' - постоянные целые числа,
х и y - переменные с фиксированной запятой, и
C/2^k и S/2^k - аппроксимации рациональным числом иррациональных констант.

44. Устройство по п.43, в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z₀, z₁, z₂, z₃, z₄, z₅, z₆ и z₇, и
в котором модуль обратного преобразования выполняет операции структуры бабочки посредством:
выполнения первой операции структуры бабочки, в которой x=x₀, y=x₄, C=1, S=1, u=x₀', v=x₄',
выполнение второй операции структуры бабочки, в которой x=x₂, y=x₆, C=α, S=β, u=x₆'и v=x₂',
выполнение третьей операции структуры бабочки, в которой x=x₇, y=x₁, C=1, S=1, u=x₇' и v=x₁',
выполнение четвертой операции структуры бабочки, в которой x=*x₁', y=x₅, C=1, S=1, u=x₁'' и v=x₅',
выполнение пятой операции структуры бабочки, в которой x=*x₇', y=x₃, C=1, S=1, u=x₇'' и v=x₃',
выполнение шестой операции структуры бабочки, в которой x=x₀', y=x₆', C=1, S=1, u=x₀'' и v=x₆'',
выполнение седьмой операции структуры бабочки, в которой x=x₄', y=x₂', C=1, S=1, u=x₄'' и v=x₂'',
выполнение восьмой операции структуры бабочки, в которой x=x₁'', y=x₇'', C=ζ, S=ε, u=x₁''' и v=x₇''',
выполнение девятой операции структуры бабочки, в которой x=x₃', y=x₅', C=δ, S=γ, u=x₅'' и v=x₃'',
выполнение десятой операции структуры бабочки, в которой x=x₀'', y=x₇''', C=1, S=1, u=z₀ и v=z₇,
выполнение одиннадцатой операции структуры бабочки, в которой x=x₄'', y=x₅'', C=1, S=1, u=z₁ и v=z₆,
выполнение двенадцатой операции структуры бабочки, в которой x=x₂'', y=x₃'', C=1, S=1, u=z₂ и v=z₅, и
выполнение тринадцатой операции структуры бабочки, в которой x=x₆'', y=x₁''', C=1, S=1, u=z₃ и v=z₄.

45. Устройство по п.44, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений и соответственно.

46. Устройство по п.45, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.

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

48. Устройство для вычисления обратного дискретного косинусного преобразования, содержащее:
средство для выполнения последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для вычисления вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования,
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля,
причем средство для использования последовательности операций структуры бабочки содержит набор средств для выполнения последовательности операций структуры бабочки,
причем каждое из средств для выполнения последовательности операций структуры бабочки содержит средство для выполнения последовательности операций структуры бабочки в виде:
u=((x*C)>>k)-((y*-S)>>k),
v=((x*S)>>k)-((y*C)>>k),
где u, v, x и у - числа с фиксированной запятой,
х и у - входные значения, и u и v - выходные значения, и
С, S и k - целые числа.

49. Устройство по п.48, в котором вектор исходных коэффициентов
состоит из висьми коэффициентов: x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z₀, z₁, z₂, z₃, z₄, z₅, z₆ и z₇, и
в котором набор средств для выполнения операций структуры бабочки содержит:
средство для выполнения первой операции структуры бабочки, в которой x=x₀, y=x₄, C=1, S=1, u=x₀' и v=x₄',
средство для выполнения второй операции структуры бабочки, в которой x=x₂, y=x₆, C=α, S=β, u=x₆'и v=x₂',
средство для выполнения третьей операции структуры бабочки, в которой x=x₇, y=x₁, C=1, S=1, u=x₇' и v=x₁',
средство для выполнения четвертой операции структуры бабочки, в которой x=*x₁', y=x₅, C=1, S=1, u=x₁'' и v=x₅',
средство для выполнения пятой операции структуры бабочки, в которой x=*x₇', y=x₃, C=1, S=1, u=x₇'' и v=x₃',
средство для выполнения шестой операции структуры бабочки, в которой x=x₀', y=x₆', C=1, S=1, u=x₀'' и v=x₆'',
средство для выполнения седьмой операции структуры бабочки, в которой x=x₄', y=x₂', C=1, S=1, u=x₄'' и v=x₂'',
средство для выполнения восьмой операции структуры бабочки, в которой x=x₁'', y=x₇'', C=ζ, S=ε, u=x₁''' и v=x₇''',
средство для выполнения девятой операции структуры бабочки, в которой x=x₃', y=x₅', C=δ, S=γ, u=x₅'' и v=x₃'',
средство для выполнения десятой операции структуры бабочки, в которой x=x₀'', y=x₇''', C=1, S=1, u=z₀ и v=z₇,
средство для выполнения одиннадцатой операции структуры бабочки, в которой x=x₄'', y=x₅'', C=1, S=1, u=z₁ и v=z₆,
средство для выполнения двенадцатой операции структуры бабочки, в которой x=x₂'', y=x₃'', C=1, S=1, u=z₂ и v=z₅, и
средство для выполнения тринадцатой операции структуры бабочки, в которой x=x₆'', y=x₁''', C=1, S=1, u=z₃ и v=z₄.

50. Устройство по п.49, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений и и соответственно.

51. Устройство по п.50, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.

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

53. Машиночитаемый носитель информации, содержащий команды вычисления обратного дискретного косинусного преобразования, которые при исполнении вызывают в процессоре:
выполнение последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования, и
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля,
в котором команды, которые вызывают выполнение процессором операций структуры бабочки, вызывают выполнение процессором операции структуры бабочки вида:
u=((x*C)>>k)-((y*-S)>>k'),
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате числа с фиксированной запятой,
С, S, k и k' - постоянные целые числа,
х и y - переменные с фиксированной запятой, и
C/2^k и S/2^k - аппроксимации рациональным числом иррациональных констант.

54. Машиночитаемый носитель информации по п.53, в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x₀, x₁, x₂, x₃, x₄, x₅, x₆ и x₇,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z₀, z₁, z₂, z₃, z₄, z₅, z₆ и z₇,
в котором команды, которые вызывают использование процессором последовательности операций структуры бабочки, вызывают в программируемом процессоре:
выполнение первой операции структуры бабочки, в которой x=x₀, y=x₄, C=1, S=1, u=x₀', v=x₄',
выполнение второй операции структуры бабочки, в которой x=x₂, y=x₆, C=α, S=β, u=x₆'и v=x₂',
выполнение третьей операции структуры бабочки, в которой x=x₇, y=x₁, C=1, S=1, u=x₇' и v=x₁',
выполнение четвертой операции структуры бабочки, в которой x=*x₁', y=x₅, C=1, S=1, u=x₁'' и v=x₅',
выполнение пятой операции структуры бабочки, в которой x=*x₇', y=x₃, C=1, S=1, u=x₇'' и v=x₃',
выполнение шестой операции структуры бабочки, в которой x=x₀', y=x₆', C=1, S=1, u=x₀'' и v=x₆'',
выполнение седьмой операции структуры бабочки, в которой x=x₄', y=x₂', C=1, S=1, u=x₄'' и v=x₂'',
выполнение восьмой операции структуры бабочки, в которой x=x₁'', y=x₇'', C=ζ, S=ε, u=x₁''' и v=x₇''',
выполнение девятой операции структуры бабочки, в которой x=x₃', y=x₅', C=δ, S=γ, u=x₅'' и v=x₃'',
выполнение десятой операции структуры бабочки, в которой x=x₀'', y=x₇''', C=1, S=1, u=z₀ и v=z₇,
выполнение одиннадцатой операции структуры бабочки, в которой x=x₄'', y=x₅'', C=1, S=1, u=z₁ и v=z₆,
выполнение двенадцатой операции структуры бабочки, в которой x=x₂'', y=x₃'', C=1, S=1, u=z₂ и v=z₅, и
выполнение тринадцатой операции структуры бабочки, в которой x=x₆'', y=x₁''', C=1, S=1, u=z₃ и v=z₄.

55. Машиночитаемый носитель информации по п.54, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений и соответственно.

56. Машиночитаемый носитель информации по п.55, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.

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