Устройство для выполнения быстрых ортогональных преобразований

 

Изобретение относится к вычислительной технике и может быть использовано при построении процессоров цифровой обработки сигналов. Цель изобретения - расширение функциональных возможностей за счет выполнения одномерных и двумерных преобразований Фурье и Хартли. Это достигается за счет того, что в состав устройства входят блоки памяти 1, 2, блоки постоянной памяти 3, 4, коммутаторы 5 - 9, регистры 10 - 13, сдвиговый регистр 14, регистры 15, 16, сумматор-вычитатель 17, умножитель 18, генератор тактовых импульсов 19, счетчик 20, триггер 21, блоки элементов ИЛИ 22, 23, элементы ИЛИ 24, 25, регистр 26. 3 ил.

СОЮЗ СОВЕТС2НИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИК (192 (112 (1) С 06 Г 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

flO ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГКНТ СССР (21) 4615337/24-24

1 (22) 02 ° 12.88 (46) 15.11.90. Бюл. № 42 (71) Ленинградский механический институт им. Маршала Советского Союза

Устинова Д.Ф. (72) Ю.И.Гагарин и К,IÎ.Ãàãàðèí (53) 681,32(088,8) (56) Авторское свидетельство СССР № 1211752, кл. G 06 F 15/332, 1984.

Авторское свидетельство СССР № 1141420, кл, G 06 F 15/332, 1983. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано при построении процессоров цифровой обработки сигналов. Цель изобретения — расширение функциональных возможностей за счет выполнения одномерных и двумерных преобразований Фурье и Хартли. Это достигается за счет того, что в состав устройства входят блоки памяти 1, 2, блоки постоянной памяти 3, 4, коммутаторы

5-9, регистры 10-13, сдвиговый регистр

14, регистры 15, 16, сумматор-вычитатель 17, умножитель 18 генератор тактовых импульсов 19, счетчик 20, триггер 21 блоки элементов ИЛИ 22, 23, элементы ИЛИ 24. 25, регистр 26.

3 ил.

1606977

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

Цель изобретения — расширение функциональных возможностей за счет выполнения одномерных и.двумерных преобразований Фурье и Картли и дискретного косинусного преобразования, На фиг. 1 изображена функциональная схема устройства; на фиг, 2 и 3 — 15 соответственно сигнальные графы быстрых алгоритмов Фурье и косинусного преобразований.

Устройство состоит из блоков 1 и

2 памяти, блоков 3 и 4 постоянной памяти, коммутаторов 5-9, регистров

10-13, сдвигового регистра 14, регистров 15 и 16, сумматора-вычитателя 17, умножителя 18, генератора 19 тактовых импульсов,, счетчика 20, триггера 21, 25 блоков элементов ИЛИ 22 и 23, элементов ИЛИ 24 и 25, регистра 26, входов

27 и 28, выхода 29, входов 30-33, выхода 34.

Устройство работает следующим образом., Начальной установке триггера 21 соответствует состояние, определяемое состоянием его выхода„ запрещающее счет для счетчика 20, который установлен в нулевое состояние, код длины и типа преобразований по входам 33 устанавливается на заданную длину и тип преобразования, для каждого из которых в блоке 3 постоянной памяти хранятся микрокоманды.По приходу с входа

27 сигнала "Разрешение счета", триггер 21 изменяет свое начальное состояние и счетчик 20 формирует адрес первой микрокоманды из микропрограммы»дсоответствующей заданному быстрому алгоритму. Код IIepBoH микрокоманды закладывается на первом такте в регистр 10 микрокоманды. Формат мнкрокомандь1 выбран таким, что в нем присут-, ствует поле адреса первого блока памяти (разряды а.1),поле адреса второго блока памяти (разряды а )» после сигналов управления первого и второго блоков памяти — разряды а< и or, Hoëå

55 ат соответствует адресу второго блока постоянной памяти, где хранятся весовые коэффициенты. Разряд ад через один из входов коммутатора 9 управляет коммутацией операндов, размещенных в регистрах 11-13, на входы сумматоравычитателя 17. Разрядами а осуществляется управление сумматором-вычитателем 17 и коммутатором 9. Разрядом а осуществляется управление сдвигами в случае вычисления коэффициентов обратного преобразования, Рассмотрим сначала работу устройства в случае реализации в нем гнездовых алгоритмов дискретного преобразования Фурье для комплексных входных данных с длиной преобразования

N=12. Граф гнездового алгоритма БПФ приведен на фиг. 2.

Код нулевой микрокоманды в регистре 10 соответствет одному ненулевому значению а, с помощью которого через триггер 21 на вход счетчика 20 подается сигнал "Запрет счета". Прн этом с внешнего устройства., например с 3НМ, в один (любой) из блоков памяти устройства заносятся исходные данные, а из другого блока памяти считываются вычисленные на предыдущем цикле работы устройства коэффициенты преобразования. Послe этого внешнее устройство сигналом Разреше и- .е счета" » формируемым на входе 27, переводит счетчик 20 в состояние счета н с его выхода в течение цикла формируется последовательность адресов микрокоманд, соответствующих быстрому алгоритму фиг. 2. Число микрокоманд на каждой итерации на три больше, чем это следует из графа. Объясняется это временной задержкой обработки первой пары операндов в арифметическом блоке (регистры 11 -16, 26., сумматор-вычитатель 17» умножитель 18 н коммутатор 9). Лля рассматриваемого гнездового алгоритма БПФ с длиной

И=-12 блок постоянной памяти является одноадресным, т,е. в чем хранится одно число ГЗ/2, являющееся весовым множителем в данном алгоритме БПФ. Поэтому и умножнтель может быть вь|полнен, например на ПЗУ по табличному принципу. Работу арифметического блока достаточно рассмотреть на одной паре комплекснык отсчетов, Еа первом такте из блока 1 памяти считывается вещественная часть первого отсчета

Re(x f н записывается в регистр 11 °

На втором -..àêте из блока 1 памяти считывается вещественная часть второго отсчета Re õi1 . При этом Re 1õ » переписывается в регистр 12. По передиз последовательности микрокоманд, являющихся микропрограммой, соответствующей реализуемому быстрому алгоритму DIG. Работа арифметического блока устройства при реализации той части быстрого алгоритма, где вершинам графа соответствуют бинарные операции (начиная с третьей итерации), является аналогичной его работе при реализации гнездовых алгоритмов Хартли или Фурье. В случае реализации унарных операций, соответствующих вершинам графа, операнд, считанный из одного блока памяти через регистры !1 и 12, сумма" îð-вычитатель 17, на второй вход которого коммутатор

9 коммутирует нуль-операнд, через реги"тры 14 и 26 и через коммутатор

6 поступает на вход данных другого бпока памяти. Характерно, что при переходе от унарных к бинарным операциям над операндами конвейерный принцип их обработки не нарушается.

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

Устройство для выполнения быстрых ортогональных преобразований, содержащее первьй блок памяти, первый блок постоянной памяти, сумматор-вычитатель, два коммутатора, четыре регистра„ счетчик и генератор тактовых импульсов, выход которого подключен к счетному входу счетчика, информационный выход которого подключен к первому адресному входу первого блока постоянной памяти, выход которого подключен к информационному входу первого регистра, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей за счет выполнения одномерных и двумерных преобразований Фурье и Хартли и дискретного косинусногс преобразования, в не-.о введены второй блок памяти, второй блок постоянной памяти, умножитель, третий, четвертый и пять,й коммутаторы, пятый, шестой и седьмой регистры, сдвиговый регистр, триггер, два элемента ИЛИ и два, блока элементов ИЛИ, причем выход триггера подключен к входу запрещения счета счстика, первому унравляющему входу перного коммутатора, управляющему входу второго коммутатора и является выходом начала вычислений ус-.тройства, информанион1пл". входе которого является nennIхй ивфорь1агио1нн10, вх< д ер5

1606977 нему фронту третьего такта коммутатор 9 коммутирует выход регистра 11 на один из входов сумматора-вычитателя, на второй вход которого поступает содержимое регистра 12. Таким образом, на третьем такте в регистр 14 будет занесена сумма Re(xI) +Re(x ) .

На третьем такте в регистр 11 заносится также Em(xII(. При этом в регист-!о ры 12 и 13 заносятся соответственно

Re(xI) и Re(xone . По переднему фронту четвертого синхроимпульса в регистр

14 заносится разность Re(xII(-Re (х1 .

Одновременно сумма Re(xI) +Re(x,) пе- 15 реписывается в регис-,р 26 и в регистр

11 заносится из блока 1 памяти

Im(x,) . Так, последовательно чередуясь, сумма и разность вещественных, а затем сумма и разность мнимых частей первого и второго комплексных отсчетов записываются с выхода регистра 26 через коммутатор 6 данных в соответствующие ячейки блока 2 памяти. Если на соответствующем шаге в графе алгоритма БПФ предусматривается умножение разностей на весовой множитель, то с помощью коммутатора

6 на вход данных блока 2 памяти коммутируется выход регистра !6. При пе- 30 реходе с одной итерации на другую режимы блоков и 2 памяти изменяются на-противоположные. Так, на второй итерации в рассмотренном примере за- пись осуществляется в блок 1 а блок

2 работаег на чтение, Аналогично реализуются быстрые гнездовые алгоритмы дискретного преобразования ХартЛие

Быстрые алгоритмы преобразования 40

Уолша реализуются подобно гнездовым алгоритмам БПФ с тем лишь отличием, что не используется умножитель )8.

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

Рассмотрим работу устройства в случае реализации быстрого алгоритма

ДКП в соответствии с графом фиг. Э. 50

Предполагается, что исходные отсчеты занесены в блок памяти в той последовательности, которая была указана для случая реализации гнездового алгоритма БПФ, 55

После прихода на вход 27 сигнала

"Разрешение счета на каждом такте с выхода блока 3 постоянной памяти считывается очередная микрокоманда

1606977 вого коммутатора, выход которого подключен к информационным входам первого и второго блоков памяти, выходы которых подключены к информационному входу второго комМутатора, первый выход которого подключен к информационному входу второго регистра, выход которого подключен к первому информационному входу гретьего коммутатора и информационному входу третьего регистра, выход которого. подключен к первому информационному входу сумматора-вычитателя и информационному входу четвертого регистра, выход которого подключен к второму информационному входу третьего коммутатора, выход которого подключен к второму информационному входу сумг..атора-вычитателя, выход которого подключен 2О к информационному входу сдвигового регистра, выход которого подключен к информационному входу пятого регистра и первому входу умножителя, выход которого подключен к информационному 25 входу шестого регистра, выход которого подключен к второму информационному входу первого коммутатора, третий информационный вход которого подключен к выходу пятого регистра, пер- 30 вый и второй выходы первого регистра подключены к первым входам соответственно первого и второго элементов

ИЛИ, выходы которых подключены к входам управления записью — считыванием соответственно первого и второго бло— ков памяти, адресчые входы которых подключены к выходам соответственно первого и второго блоков элементов

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

1606977

Х(0) 9

17 г

Составитель А.Баранов

Текред Л.Олийнык

Редактор Е. Копча

Корректор О.ципл»

Заказ 3550 Тираж 567 Подписное

BHHMIIH Государственного комитета l10 изобретениям и còêðütòèÿë при ГКНТ СССР

113035, Москва, iK-35, Раушская наб., jl 6/5

Производственнс-издательский комбинат Патент", г. Ужг;род, ул. Гагарина, 101 ф

5

Х(д) х®

Х(2) х(б)

ХК х®

x(3 х(7) x(O)

Х(7У

Х(З)

Х(2)

Х(7) х®

Х(М х(5)