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

(51) С 06 Г 15/3 ИСАНИЕ ИЗОБРЕТЕНИ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМПРИ ГКНТ СССР К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Ленинградский механический институт им. Маршала Советского Союза Устинова Д.Ф.(56) Авторское свидетельство СССР1211752, кл, С 06 Р 15/332, 1984,Авторское свидетельство СССР1141420, кл, С 06 Р 15/332, 1983. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано при построении процессоровцифровой обработки сигналов. Цельизобретения - расширение функциональных возможностей за счет выполненияодномерных и двумерных преобразований Фурье и Хартли. Это достигаетсяза счет того, что в состав устройствавходят блоки памяти 1, 2, блоки постоянной памяти 3, 4, коммутаторы5-9, регистры 10-13, сдвиговый регистр14, регистры 15, 16, сумматор-вычитатель 17, умножитель 18, генератортактовых импульсов 9, счетчик 20,триггер 21, блоки элементов ИЛИ 22,23, элементы ИЛИ 24. 25, регистр 26.3 ил.Изобретение относится к вычислительной технике и может быть использовано при построении процессоров цифровой обработки сигналов, в том числе в составе типовых персональных,управляющих,и специализированных бортовых ЗВИ.Цель изобретения - расширениефункциональных возможностей за счетвыполнения одномерных и,двумерныхпреобразований Фурье и Картли и дискретного косинусного преобразования,На Фиг. 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 Формирует адреспервой микрокоманды из микропрограммыг 5соответствующей заданному быстромуалгоритму, Код первой микрокомандызакладывается на первом такте в регистр 10 микрокоманды. Формат мнкрокоманды выбран таким, что в нем присут-,ствует поле адреса первого блока памяти (разряды а,1),поле адреса второгоблока памяти (разряды а), после сигналов управления первого и второгоблоков памяти - разряды а и ае Поле55ат соответствует адресу второго блокапостоянной памяти, где хранятся весовые коэффициенты, Разряд а о черезодин из входов коммутатора 9 управляет коммутацией операндов, размещенныхв регистрах 11-13, на входы сумматоравычитателя 17. Разрядами а осуществляется управление сумматором-вычитателем 17 и коммутатором 9. Разрядома з осуществляется управление сдвигами в случае вычисления коэффициентовобратного преобразования,Рассмотрим сначала работу устройства в случае реализации в нем гнездовых алгоритмов дискретного преобразования Фурье для комплексных входных данных с длиной преобразованияИ=12, Граф гнездового алгоритма БПФприведен на фиг, 2,Код нулевой микрокоманды в регистре 10 соответствет одному ненулевомузначению а, с помощью которого черезтриггер 21 на вход счетчика 20 подается сигнал "Запрет счета". Прн этомс внешнего устройства., например с ЭВИ,ь один (любой) из блоков памяти устройства заносятся исходные данные, аиз другого блока памяти считываютсявычисленные на предыдущем цикле работы устройства коэффициенты преобразования. После этого внешнее устройство сигналом Разрешеи.:е счета,Формируемым на входе 27, переводитсчетчик 20 в состояние счета н с еговыхода в течение цикла Формируетсяпоследовательность адресов микрокоманд, соответствующих быстрому алгоритму Фиг. 2, Число микрокоманд накаждой итерации на три больше, чемэто следует из графа. Объясняетсяэто временной задержкой обработкипервой пары операндов в арифметическом блоке ( регистры 11 -16, 26 сумматор-вычитатель 17, умножитель 18 нкоммутатор 9), Лля рассматриваемогогнездового алгоритма БПФ с длинойИблок постоянной памяти являетсяодноадресным, т,е. в чем хранится одно число 1 3/2, являющееся весовым множителем в данном алгоритме БПФ. Поэтому и умножитель может быть выполнен, например на ПЗУ по табличному принципу. Работу арифметического блока достаточно рассмотреть на одной паре комплегссньпс отсчетов, Еа гервом такте из блока 1 памяти считываетсявещественная часть первого отсчета 1 се 1 х н записывается в регистр 11. На втором такте из блока 1 памяти считывается вещественная часть второго отсчета Кех 1. 11 ри этом гсехд переписывается в регистр 12, По перед"из последовательности микрокоманд,являющихся микропрограммой, соответствующей реализуемому быстрому алго"ритму ЕЕП. Работа арифметическогоблока устройства при реализации тойчасти быстрого алгоритма, где вершинам графа соответствуют бинарные операции начиная с третьей итерации),является аналогичной его работе приреализации гнездовых алгоритмов Хартли или Фурье. В случае реализацииунарных операций, соответствующихвершинам графа, операнд, считанныйиз одного блока памяти через регистры 1 и 12, сумматор-вычитатель 17,на второй вход которого коммутатор9 коммутирует нуль-операнд, черезреги"тры 14 и 26 и через коммутатор 20 25 6 поступает на вход данных другогобпока памяти, Характерно, что при переходе от унарных к бинарным операциям над операндами конвейерный принцип их обработки не нарушается,Формула изобретения Устройство для выполнения быстрых ортогональных преобразований, содержащее первы," блок памяти, первый блок постоянной памяти, сумматор-вычитатель, два коммутатора, четыре регистра счетчик и генератор тактовых импульсов, выход которого подключен к счетному входу счетчика, информационный вьход которого подключен к первому адресному входу первого блока постоянной памяти, выход которого подключен к информационному входу первого регистра, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональьых возможностей за счет выполнения одномерных и двумерных преобразований Фурье и Хартли и дискретного косинусногс преобразования, в него введены второй блок памяти, второй блок постоянной памяти, умно- житель, третий, четвертый и пятый коммутаторы, пятый, шестой и седьмой регистрь 1, сдвиговый регистр, триггер, два элемента ИЛИ и два, блока элементов ИЛИ, причем выход триггера подключен к входу запрещения счета счетчика, первому унравляющему входу первого коммутатора, управляющему входу второго коммутатора и является вы,одом начала вычислении устройства, информационным входом которого является пеопый ивформал.о 1 нн,и";, выл пер 51606977нему фронту третьего такта коммутатор 9 коммутирует выход регистра 11на один из входов сумматора-вычитателя, на второй вход которого поступаетсодержимое регистра 12, Таким образом, на третьем такте в регистр 14будет занесена сумма Ке х +Кех .На третьем такте в регистр 11 заносится также Ешхо . При этом в регист ры 12 и 13 заносятся соответственноКех, и Кех . По переднему фронтучетвертого синхроимпульса в регистр14 заносится разность Кехо -Ке 1 х 11 .Одновременно сумма Кех, +Кех, переписывается в регистр 26 и в регистр11 заносится из блока 1 памятиЕшх, . Так, последовательно чередуясь, сумма и разность вещественных,а затем сумма и разность мнимых частей первого и второго комплексныхотсчетов записываются с выхода регистра 26 через коммутатор 6 данных всоответствующие ячейки блока 2 памяти, Если на соответствующем шаге вграфе алгоритма БПФ предусматривается умножение разностей на весовоймножитель, то с помощью коммутатора6 на вход данных блока 2 памяти коммутируется выход регистра 6. При переходе с одной итерации на другуюрежимы блоков 1 и 2 памяти изменяютсяна-противоположные. Так, на второйитерации в рассмотренном примере за-пись осуществляется в блок 1, а блок2 работаег на чтение, Аналогичнореализуются быстрые гнездовые алгоритмы дискретного преобразования ХартЛИ еБыстрые алгоритмы преобразования 40Уолша реализуются подобно гнездовымалгоритмам БПФ с тем лишь отличием,что не используется умножитель 18.Быстрые алгоритмы двумерных преобразований Фурье, Хартли и Уолша реализуются как обобщенные гнездовые алгоритмы одномерных преобразований,Рассмотрим работу устройства вслучае реализации быстрого алгоритмаДКП в соответствии с графом фиг. Э. 50Предполагается, что исходные отсчеты занесены в блокпамяти в той последовательности, которая была указана для случая реализации гнездовогоалгоритма БПФ, 55После прихода на вход 27 сигнала"Разрешение счетана каждом тактес выхода блока 3 постоянной памятисчитывается очередная микрокомандавого коммутатора, выход которого подключен к информационным входам первого и второго блоков памяти, выходыкоторых подключены к информационномувходу второго комМутатора, первыйвыход которого подключен к информационному входу второго регистра, выходкоторого подключен к первому информационному входу гретьего коммутатораи инФормационному входу третьего регистра, выход которого подключен кпервому информационному входу сумматора-вычитателя и информационномувходу четвертого регистра, выход которого подключен к второму информационному входу третьего коммутатора,выход которого подключен к второмуинформационному входу сумг.атора-вычитателя, выход которого подключен 2 Ок информационному входу сдвиговогорегистра, выход которого подключен кинформационному входу пятого регистра и первому входу умножителя, выходкоторого подключен к информационному 25входу шестого регистра, выход которого подключен к второму информационному входу первого коммутатора, третий информационный вход которого подключен к выходу пятого регистра, первый и второй выходы первого регистраподключены к первым входам соответственно первого и второго элементовИЛИ, выходы которых подключены к входам управления записью - считываниемсоответственно первого и второго блоков памяти, адресчые входы которыхподключены к выходам соответственнопервого и второго блоков элементовИЛИ, первые входы которых подключены ц)соответственно к третьему и четвертому выходам первого регистра, пятый выход которого подключен к первому установочному входу триггера, второй установочный вход которого является входом запуска устройства, входом выбора режима и информационным выходом которого являются соответственно второй адресный вход первого блока постоянной памяти и второй выход второго коммутатора, шестой, седьмой, восьмой, девятый и десятый выходы первого регистра подключены соответственно к второму управляющему входу первого коммутатора, адресному входу второго блока постоянной памяти управляющему входу сумматора-вычитателя, входу управления сдвигом сдзигового регистра и управляющему входу третьего коммутатора, выход второго блока постоянной памяти подключен к информационному входу седьмого регистра, выход которого подключен к второму входу умножителя, вторые входы первого и второго блоков элементов ИЛИ подключены соответственно кпервому и второму выходам четвертого коммутатора, информационньй вход которого является входом задания адреса устройства, первым входом синхронизации которого является информационный вход пятого коммутатора, первый и второй выходы которого подключены к вторым входам соответственно первого и второго элементов ИЛИ, а управляющие входы четвертого и пятого коммутаторов соединены между собой и являются вторым входом синхронизации устройства, выход генератора тактовых импульсов подключен к тактовым входам сдвигового регистра и регистров с первого по седьмой.б Ф 1 И 7) Составитель Ь.гарановТекред Л.Олийнык Корректор и опча дак о 550Госуда Тираж 56 аказНБИП 11 одписно е 1 ого комитета35, Москва, Ж о изо 35, Р рои х 10)9 д) Ч О ХЫ х 13) Х(2) Х 7) етениям и открь 1 тиял при ГКНТ СССР нская н,чб., и. /5 нно-издательский комбинат Патент", г. Ужг,род, ул. Гагарина, 10