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

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

Устройство для вычисления дискретного косинусного преобразования, состоящее из первого блока быстрого преобразования Фурье, отличающееся тем, что оно содержит новые элементы: демультиплексор, первый и второй скалярные умножители, генератор действительных коэффициентов, второй блок быстрого преобразования Фурье, генератор мнимых коэффициентов, первый и второй комплексные умножители, мультиплексор и компаратор, вход демультиплексора является входом устройства, выход четных отсчетов демультиплексора соединен с действительной частью входа первого блока быстрого преобразования Фурье и с первым входом второго скалярного умножителя, выход которого соединен с действительной частью входа второго блока быстрого преобразования Фурье, выход нечетных отсчетов демультиплексора соединен с мнимой частью входа первого блока быстрого преобразования Фурье и с первым входом первого скалярного умножителя, выход которого соединен с мнимой частью входа второго блока быстрого преобразования Фурье, действительная часть выхода первого блока быстрого преобразования Фурье соединена с действительной, а мнимая часть - с мнимой частью первого входа первого комплексного умножителя, действительная часть выхода второго блока быстрого преобразования Фурье соединена с действительной, а мнимая - с мнимой частью первого входа второго комплексного умножителя, первый выход генератора действительных коэффициентов соединен с действительной частью второго входа первого комплексного умножителя, второй выход генератора действительных коэффициентов соединен с действительной частью второго входа второго комплексного умножителя, первый выход генератора мнимых коэффициентов соединен с мнимой частью второго входа первого комплексного умножителя, второй выход генератора мнимых коэффициентов соединен с мнимой частью второго входа второго комплексного умножителя, действительная часть выхода первого комплексного умножителя соединена с первым, а действительная часть выхода второго комплексного умножителя - со вторым входом данных мультиплексора, выход которого является выходом устройства, а вход адреса мультиплексора соединен с выходом компаратора, сигнальный вход которого соединен с источником сигнала, являющегося индексом выходного отсчета, а опорный вход - с источником постоянной величины N/2-1, где N - длина исходной последовательности, вторые входы первого и второго скалярных умножителей подсоединены к источнику сигнала (-1)^m, демультиплексор является разделяющим входные отсчеты на отсчеты с четными и нечетными индексами, генератор действительных коэффициентов (4) является источником величин cos[ l/(2N)] и cos[ l/(2N)+ /4], а генератор мнимых коэффициентов (5) является источником величин (-cos[ l/(2N)] и sin[3 l/(2N)+ /4], m, l=0, 1, , N/2-1, a быстрое преобразование Фурье в первом (5) и втором (6) одноименных блоках имеет размерность N/2.

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

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

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

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

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

Известно устройство «Вычислитель дискретного косинусного преобразования с раздельным основанием» (Split-Radix Discrete Cosine Transform), патент США № 5408425 от 18.04.1995 г, того же назначения, что и предлагаемое изобретение, но не имеющее с ним общих признаков и состоящее из банка сумматоров (Adder Bank), вход которого является входом устройства, блока дискретного косинусного преобразования по основанию N/2 (N/2 DCT), выход которого является первым выходом устройства, банка сумматоров и двухвходовых скалярных умножителей (Adder Bank and 2-Scalar Multipliers), первого и второго перемежителей (Permutation), первого и второго блоков вычисления обратного дискретного косинусного преобразования по основанию N/4 (N/4 IDCT), постоянного запоминающего устройства (ROM) и банка вычислителей операции «бабочка» (Butterfly Bank), выход которого является вторым выходом устройства, первый выход банка сумматоров подсоединен к первому входу блока дискретного косинусного преобразования по основанию N/2, ко второму входу которого подсоединен первый выход постоянного запоминающего устройства, второй выход банка сумматоров подсоединен ко входу банка сумматоров и двухвходовых скалярных умножителей, выход которого соединен со входом первого перемежителя, первый выход которого соединен со входом первого, а второй - со входом второго блоков вычисления обратного дискретного косинусного преобразования по основанию N/4, выход первого блока вычисления обратного дискретного косинусного преобразования по основанию N/4 соединен с первым входом банка вычислителей операции «бабочка», выход второго блока вычисления обратного дискретного косинусного преобразования по основанию N/4 подсоединен ко входу второго перемежителя, выход которого подсоединен ко второму входу банка вычислителей операции «бабочка», третий вход которого соединен со вторым выходом постоянного запоминающего устройства.

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

Известно устройство «Вычислитель прямого и обратного дискретного косинусного преобразования» (DCT/IDCT Processor), патент США № 6308193 В1 от 23.10.2001 г., того же назначение, что и предлагаемое изобретение, но не имеющее с ним общих признаков и состоящее из первого мультиплексора (First Multiplexer), первый вход которого является входом устройства, последовательно соединенных первого масштабирующего устройства (First Pre/Post Scaler), второго мультиплексора (Second Multiplexer), матричного умножителя (Matrix Multiplier), второго масштабирующего устройства (Second Pre/Post Scaler), блока декодирования выходных путей (Output Path Decoding Part), блока оконечной стандартизации и округления (Final Standardization and Round-off Part) и блочного буфера (Block Buffer), выход которого является выходом устройства, последовательно соединенных блока стандартизации и округления (Standardization and Round-off Part) и транспонирующего буфера (Transpose Buffer), выход которого подсоединен ко второму входу первого мультиплексора, вход блока стандартизации и округления подключен к выходу блока декодирования выходных путей.

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

Известна схема, реализующая «эффективный алгоритм дискретного косинусного преобразования», описанная в [1] и состоящая из последовательно соединенных блоков: формирования вспомогательного сигнала, выделения из вспомогательного сигнала отсчетов с четными индексами, вычисления дискретного преобразования Фурье длины N, получения косинусного спектра. По функциональному назначению и схожести признаков данная схема принята за прототип.

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

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

Сопоставимый анализ с прототипом показывает, что предлагаемое устройство отличается от прототипа наличием новых элементов: демультиплексора, первого и второго скалярных умножителей генератора действительных коэффициентов, второго блока быстрого преобразования Фурье, генератора мнимых коэффициентов, первого и второго комплексных умножителей, мультиплексора и компаратора, причем вход демультиплексора является входом устройства, выход четных отсчетов демультиплексора соединен с действительной частью входа первого блока быстрого преобразования Фурье и с первым входом второго скалярного умножителя, выход которого соединен с действительной частью входа второго блока быстрого преобразования Фурье, выход нечетных отсчетов демультиплексора соединен с мнимой частью входа первого блока быстрого преобразования Фурье и с первым входом первого скалярного умножителя, выход которого соединен с мнимой частью входа второго блока быстрого преобразования Фурье, действительная часть выхода первого блока быстрого преобразования Фурье соединена с действительной, а мнимая часть - с мнимой частью первого входа первого комплексного умножителя, действительная часть выхода второго блока быстрого преобразования Фурье соединена с действительной, а мнимая - с мнимой частью первого входа второго комплексного умножителя, первый выход генератора действительных коэффициентов соединен с действительной частью второго входа первого комплексного умножителя, второй выход генератора действительных коэффициентов соединен с действительной частью второго входа второго комплексного умножителя, первый выход генератора мнимых коэффициентов соединен с мнимой частью второго входа первого комплексного умножителя, второй выход генератора мнимых коэффициентов соединен с мнимой частью второго входа второго комплексного умножителя, действительная часть выхода первого комплексного умножителя соединена с первым, а действительная часть выхода второго комплексного умножителя - со вторым входом данных мультиплексора, выход которого является выходом устройства, а вход адреса мультиплексора соединен с выходом компаратора, сигнальный вход которого соединен с источником сигнала, являющегося индексом выходного отсчета, а опорный вход - с источником постоянной величины N/2-1, где N - длина входного/выходного вектора, вторые входы первого и второго скалярных умножителей подсоединены к источнику сигнала (-1)^m, демультиплексор является разделяющим входные отсчеты на отсчеты с четными и нечетными индексами, генератор действительных коэффициентов является источником величин cos[ l/(2N)] и cos[ l/(2N)+ /4], а генератор мнимых коэффициентов является источником величин (-cos[ l/(2N)]) и sin[3 l/(2N)+ /4], l, m=0, 1, ,N/2-1, а быстрое преобразование Фурье в первом и втором одноименных блоках имеет размерность N/2.

Следовательно, устройство удовлетворяет критерию «новизна».

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

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

Изобретение поясняется чертежом,

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

Устройство для вычисления дискретного косинусного преобразования состоит из демультиплексора 1, первого скалярного умножителя 2, второго скалярного умножителя 3, генератора действительных коэффициентов 4, первого блока быстрого преобразования Фурье 5, второго блока быстрого преобразования Фурье 6, генератора мнимых коэффициентов 7, первого комплексного умножителя 8, второго комплексного умножителя 9, мультиплексора 10 и компаратора 11, вход демультиплексора 1 является входом устройства, выход четных отсчетов демультиплексора 1 соединен с действительной частью входа первого блока быстрого преобразования Фурье 5 и с первым входом второго скалярного умножителя 3, выход которого соединен с действительной частью входа второго блока быстрого преобразования Фурье 6, выход нечетных отсчетов демультиплексора 1 соединен с мнимой частью входа первого блока быстрого преобразования Фурье 5 и с первым входом первого скалярного умножителя 2, выход которого соединен с мнимой частью входа второго блока быстрого преобразования Фурье 6, действительная часть выхода первого блока быстрого преобразования Фурье 5 соединена с действительной, а мнимая часть - с мнимой частью первого входа первого комплексного умножителя 8, действительная часть выхода второго блока быстрого преобразования Фурье 6 соединена с действительной, а мнимая - с мнимой частью первого входа второго комплексного умножителя 9, первый выход генератора действительных коэффициентов 4 соединен с действительной частью второго входа первого комплексного умножителя 8, второй выход генератора действительных коэффициентов 4 соединен с действительной частью второго входа второго комплексного умножителя 9, первый выход генератора мнимых коэффициентов 7 соединен с мнимой частью второго входа первого комплексного умножителя 8, второй выход генератора мнимых коэффициентов 7 соединен с мнимой частью второго входа второго комплексного умножителя 9, действительная часть выхода первого комплексного умножителя 8 соединена с первым, а действительная часть выхода второго комплексного умножителя 9 - со вторым входом данных мультиплексора 10, выход которого является выходом устройства, а вход адреса мультиплексора соединен с выходом компаратора 11, сигнальный вход которого соединен с источником сигнала, являющегося индексом выходного отсчета, а опорный вход - с источником постоянной величины N/2-1, N - длина входного/выходного вектора, вторые входы первого 2 и второго 3 скалярных умножителей подсоединены к источнику сигнала (-1)^m, демультиплексор 1 является разделяющим входные отсчеты на отсчеты с четными и нечетными индексами, генератор действительных коэффициентов 4 является источником величин cos[ l/(2N)] и cos[ l/(2N)+ /4], а генератор мнимых коэффициентов 5 является источником величин (-cos[ l/(2N)]) и sin[3 l/(2N)+ /4], m, l=0, 1, ,N/2-1, а быстрое преобразование Фурье в первом 5 и втором 6 одноименных блоках имеет размерность N/2.

Дискретное косинусное преобразование может быть вычислено с использованием формулы

где x[n], n=0, 1, ,N-1 - исходная информационная последовательность; DCT[k] - последовательность отсчетов дискретного косинусного преобразования последовательности х[n]; N - размерность преобразования (последовательности).

Обозначим W_N=exp(-j2 /N). Тогда из выражения (1) следует

где - последовательность отсчетов дискретного преобразования Фурье исходной последовательности х[n].

Разделим исходную последовательность х[n] на две подпоследовательности: с четными p[m]=x[2m] и нечетными индексами q[m]=х[2m+1] соответственно, m=0, 1, , N/2-1. Тогда последовательность X[k] может быть вычислена как

где - последовательности, содержащие отсчеты преобразования Фурье по основанию N/2 от подпоследовательностей p[m] и q[m] соответственно.

Сформируем комплексную последовательность

Определим последовательность Z[k], являющуюся результатом преобразования Фурье от последовательности z[m] (4). С учетом (3) и (4):

Поделим последовательность Z[k] на старшую и младшую части, в зависимости от индекса k, таким образом, что

Младшая часть Z₁[l]=Z[l], l=0, 1, , N/2-1.

Старшая часть

Из (3) и (5)получим

Так же поделим последовательность X[k]:

Из (2) и (7) получим выражения для младшей и старшей подпоследовательностей последовательности, являющейся результатом дискретного косинусного преобразования DCT[k]:

где - постоянные коэффициенты, зависящие от индекса l и размерности дискретного косинусного преобразования N.

Из (6) и (8) получим окончательные выражения для вычисления дискретного косинусного преобразования исходной последовательности:

где R₁[l]=Re{Z₁ [l]}, I₁[l]=Im{Z₁[l]}, R₂[l]=Re{Z ₂[l]}, I₂[l]=Im{Z₂[l]}, l=0, 1, , N/2-1.

Устройство для вычисления дискретного косинусного преобразования работает следующим образом. Исходная информационная последовательность х[n] подается на вход демультиплексора 7, где разделяется на две подпоследовательности: р[m] - с четными индексами и q[m] - с нечетными индексами, которые формируют комплексную последовательность z[m] (4).

Далее последовательность z[m] подается на вход первого блока быстрого преобразования Фурье 5, где вычисляется ее комплексный спектр Z₁[l] в соответствии с (5) и (6). Первый 2 и второй 3 скалярные умножители служат для формирования последовательности z[m](-1)^m, которая подается на вход второго блока быстрого преобразования Фурье 6, где вычисляется комплексный спектр Z₂[l] согласно формуле (6).

Первый комплексный умножитель 8 производит вычисление младших DCT₁[l], а второй комплексный умножитель 9 - старших DCT₂[l] компонент последовательности отсчетов дискретного косинусного преобразования в соответствии с выражением (9). С выхода первого комплексного умножителя 8 снимается действительная часть произведения комплексных величин Z₁[l] и ₁[l], а с выхода второго комплексного умножителя 9 - действительная часть произведения комплексных величин Z ₂[l] и ₂[l]. Величины ₁[l] и ₂[l] вырабатываются генераторами действительных 4 и мнимых 7 коэффициентов.

С выходов первого 8 и второго 9 комплексных умножителей младшая и старшая подпоследовательности, DCT₁[l] и DCT₂[l], соответственно подаются на первый и второй входы мультиплексора 10, который при помощи компаратора 11 формирует отсчеты выходной последовательности согласно правилу (10).

Таким образом, на выход устройства сначала выдаются N/2 элементов последовательности DCT₁[l], затем N/1 элементов последовательности DCT ₂[l] (N - размерность дискретного косинусного преобразования).

Демультиплексор 1 может быть реализован в виде известного цифрового одноименного устройства, содержащего вход данных, вход адреса, первый и второй выходы данных, и источника сигнала (1-(-1) ⁿ)/2, подключенного ко входу адреса демультиплексора, где n=0, 1, , N-1 - индекс входного отсчета, причем при лог. «0» на входе адреса входной сигнал данных передается на первый, а при лог. «1» - на второй выход демультиплексора.

Первый 2 и второй 3 скалярные умножители являются известными цифровыми устройствами.

Первый 5 и второй 6 блоки быстрого преобразования Фурье являются известными цифровыми устройствами, должны обладать размерностью N/2, равной половине размерности входного вектора информационной последовательности х[n] и реализуются, как, например, предложено в [2], стр.401.

Генератор действительных коэффициентов 4 является источником величин, снимаемых с первого и второго входов соответственно cos[ l/(2N)] и cos[ l/(2N)+ /4]. Генератор мнимых коэффициентов 5 является источником величин, снимаемых с первого и второго входов соответственно (-cos[ l/(2N)]) и sin[3 l/(2N)+ /4], где l=0, 1, , N/2-1. При цифровой реализации устройства от генераторов требуется высокое быстродействие.

Генераторы могут быть реализованы, например, в виде цифровых устройств вычисления синуса и косинуса аргумента, функционирующих на основе общеизвестного алгоритма CORDIC в режиме «поворот» и построенных по конвейерному принципу, как описано в [3], Figure 4 - Развернутый CORDIC-процессор (Unrolled CORDIC processor) или [4], стр.33 - Цифровой CORDIC-алгоритм, работающий в реальном масштабе времени (On-line Implementation Of The DCORDIC Algorithm).

Первый 8 и второй 9 комплексные умножители являются общеизвестными цифровыми устройствами.

Мультиплексор 10 может быть реализован в виде известного цифрового мультиплексора, содержащего первый и второй входы данных, вход адреса и выход. При лог. «0» на входе адреса входной сигнал с первого входа данных, а при лог. «1» - со второго входа данных передается на выход мультиплексора.

Компаратор 11 является известным цифровым устройством, содержащим входы: сигнальный и опорный, и выход, причем на выход выдается лог. «1» при величине на сигнальном входе, превышающей величину на опорном входе, и лог. «0» - в остальных случаях.

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

Источники информации

1. Чичева М.А. Эффективный алгоритм дискретного косинусного преобразования четной длины. // Компьютерная оптика, № 18, 1998. - с.147-149.

2. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. Пер. с англ. М.: Мир, 1978.

3. R. Andraka, "A survey of CORDIC algorithms for FPGA based computers," in Proceedings of the 1998 ACM/SIGDA 6th international symposium on Field programmable gate arrays (Monterey, CA), pp.191-200, Feb. 1998.

4. Chang Yong Kang. CORDIC-Based High-Speed Direct Digital Frequency Synthesis. DISSERTATION Presented to the Faculty of the Graduate School of The University of Texas at Austin in Partial Fulfillment of the Requirements for the Degree of Doctor Of Philosophy The University Of Texas At Austin, May 2003.