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

СО 1 ОЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 5940 06 Р 15 332 САНИЕ ИЗОБРЕТЕНИЯ 7 СУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИИ И ОТНРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Кировский политехнический институт(56) Ярославский Л.П. Усеченные алгоритмы быстрых преобразований ФурьеУолша. - Радиотехника, 1977, У 1 О.Авторское свидетельство СССР У 922763, кл. С 06 Р 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА УСЕЧЕННОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к радиотехнике и вычислительной технике и может быть использовано в устройствах цифровой обработки сигналовЦель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство содержит два регистра сдвига, два счетчика, блок управления, два сумматора, два блока сдвига, элемент И, два блока сравнения, блок счетчиков, два блока элементов И, элемент ИЛИ, блок регистров. Причем блок управления содержит шесть элементов НЕ, шестнадцать элементов И, три ВЯ-триггера, десять элементов ИЛИ, дешифратор и генератор тактовых импульсов. Устройство формирует на каждом шаге алгоритма тОлько те адреса которые нужны для вычисления искомых отсчетов 1 дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужными отсчетами. 7 ил.где 1 =0,2 -1. Изобретение относится к радиотехнике и вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов.Целью изобретения является повышение быстродейс вия.Для пояснения сущности изобретения сравним обычный и усеченный алгоритмы БПФ. В случае, когда число отсчетов сигнала равно степени двух, т.е. Б 2 , дискретный спектр сигнала может быть вычислен за Р шагов по рекуррентным формулам.х;(р) х; (р)+х (р+2 ) ЪТ% х, (р+2 ) =х,(р) -х,(р+2 ) И где 1 - номер шагаМ;,Х, - входные и выходные данныедля 1-го шага;11,Рф 2 - номера отсчетов в массивахвходных и выходных данных;Ю - тригонометрический коэффициент, причемехр (27-1/Б) В приведенных формулах1р=ш+Х.2 и Е=ш.2,Так как периодическая дискретная функция Е с периодом Б, достаточно сформировать массив тригонометрических коэффициентов и отсчетов. Прихэтом И соответствует Е-му отсчету в массиве,На фиг.приведен пример направленной граф-схемы алгоритма БПФ для случая Б2 . На этой схеме вершины графа (точки) соответствуют отсчетам данных. На каждом шаге алгоритма линии без стрелок соответствуют простой передаче данных, линии со стрелками соответствуют передаче с предварительным умножением на тригонометрический коэффициент, Знак +" или "-" возле вершины графа указывает ва операцию, с помощью которой получен соответствующий отсчет, Ниже граф-схемы алгоритма БПФ указаны для каждого шагазначения, которые принимают переменные ш и 1. В рассматриваемом примере для определения дискретного спектра сигнала требуется выполнить 12 операций комплексного умножения. 5 О 15 20 25 30 35.40 45 50 55 В усеченном алгоритме БПФ требуется найти М (М (с И) отсчетов диск .ретного спектра сигнала с номерами5 Ь ,1 , где 5 - целые числаиз интервала (О, 11-1). При этом достаточно на каждом шаге преобразования определить только те отсчеты,которые требуются на следующем шаге.На фиг, 1 зачернены вершины графсхемы алгоритма ЕПФ, соответствующиеотсчетам данных, которые необходимоопределить на каждом шаге для вычисления отсчетов дискретного спектрасигнала с номерами 3 и 7, Таким образом, зачерненные вершины графа образуют граф-схему усеченного алгоритма БПФ для случая, когда М = 2, о,3,= 7.Прй использовании алгоритма усеченного БПФ вычисление ведется потем же формулам, но переменная шпринимает значениеш = (1;)тпо 2",где= 1, 2М.В рассматриваемом примере длявычисления искомых отсчетов спектратребуется выполнить 8 операций комплексного умножения, т.е, на однутреть меньше, чем при использованииобычного алгоритма БПФ, Выигрышдостигается тем, что данное устройство для формирования адресов процессора усеченного БПФ формирует накаждом шаге алгоритма только те адреса, которые нужны для вычисления искомых отсчетов дискретного спектрасигнала. Благодаря этому процессорне выполняет операции с ненужнымиотсчетами.На. фиг. 1 представлен алгоритмусеченного БПФ; на фиг. 2 - блок-схема устройства; на фиг. 3 - блок-схема блока регистров, блока элементовИ, блока счетчиков и блока фиксациинуля; на фиг. 4 - алгоритмы работыустройства; на фиг. 5 - временныедиаграммы; на фиг, 6 - схема блокауправления; на фиг. 7 - схема логического узла.Устройство (фиг. 2) содержит регистры 1 и 2 сдвига, счетчики 3 и 4,сдвигатели 5 и 6, элемент И 7, сумматоры 8 и 9 блоки 10 и 11 сравнения,блок 12 регистров, блок 13 элементов И, блок 14 счетчиков, блок 15фиксации нуля и блок 16 управления,выходы 17-22 блока управления, входы23-26 блока управления, выход 27=2, Ь= 3, Ь = 7. На диаграмме приведены сигналы СС, формируемые внутри блока 16 управления (БУ), сигналы Р 1, Р 2, РЗ и Р 4 на его входахи сигналы У 1, У 2, УЗ, У 4, У 5, УЬ наего выходах, Приведены также сигналы на прямых выходах разрядов Рг 1,Рг 2, Сч 1, Сч 2. В соответствии срассматриваемым примером Рг 1 и Рг 210 трехразрядные, а Сч 1 и Сч 2 - двухразрядные.Устройство для формирования адресов процессора усеченного БПФ работает следующим образом,5 После запуска БУ он формируетсигнал У 1, который устанавливает Рги Рг 2 в режим параллельной записиинформации, и сигнал У 5, который записывает в Рг и Рг 2 код 001. При20 поступлении следующего импульса сигнала СС БУ формирует сигналы У 2, УЗи У 5. Первый из них устанавливаетСч 2 и Сч 1, а также счетчики 31 врежим параллельной записи информации,Сигнал УЗ обнуляет Сч 1 и записываетв каждый счетчик 31 код, которыйполучается в результате поразрядногологического умножения кода, записанного в одном из регистров блока 3030 на код, записанный в старших г разрядах Рг 2, При этом в счетчиках31 записываются коды(Ь)той 235 где Ь - коды записанные в регистУрах 30.В рассматриваемом примере в счетчики 31 при этом записывается код00. Сигнал У 4 обнуляет Сч 2. Так как40 в счетчиках 31 записан О, на выходе блока 15 фиксации нуля появляется логическая единица (Р 4 = 1). Приэтом в алгоритме выполняется переход от вершины 4 к вершине 7, что ф45 соответствует формированию Уб припоступлении следующего импульса сигцииСч Я - означает записьразряд Сч;11(Рг) - означает сдвиг содержимого Рг влево на один разряд;Р 1, Р 2, РЗ, Р 4 - сигналы на входах 23-26 блока 16 управления.У 1, У 2, УЗ, У 4, У 5, Уб - сигналы на выходах.17-22 блока 16 управления.Для пояснения работы устройства для формирования адресов процессора усеченного БПФ воспользуемая также временными диаграммами, приведенными на фиг. 4. Временные диаграммы построены для случая, когда М =8 , М= Ю 5 адреса коэффициента, выходы 28 и 29 адреса соответственно первого и второго операндов.На фиг. 3 приведены схемы блока 12 регистров, блока 13 элементов И, блока 14 счетчиков и блока 15 фиксации нуля. Блок 2 регистров содержит регистры 30, число которых не меньше числа искомых отсчетов дискретного спектра сигнала М. Блок 14 счетчиков содержит соответствующее число счетчиков 31. Блок 13 элементов И содержит М групп элементов И, причем число элементов И 32 в каждой группе равно разрядности регистров 30. Блок фиксации нуля включает блок элементов И, состоящий из элементов И 33, число которых равно числу счетчиков 31, и элемент ИЛИ 34.Блок управления (Фиг. 6) содержит дешифратор 35, триггеры 36-38, элементы И 39-46, элементы ИЛИ 47-52, элементы НЕ 53-55, резистор 56, конденсатор 57, логический узел 58, генератор 59 тактовых импульсов,Логический узел (фиг, 7) содержит элементы НЕ 60-62, элементы И 63-65 с выходом 66, элементы И 67-71, элементы ИЛИ 72-75.Для пояснения работы устройства на фиг. 4 приведена блок-схема алгоритма его работы. На блок-схеме алгоритма использованы следующие обозначения:Рг 1 - первый регистр 1 сдвига;Рг 2 - второй регистр 2 сдвига;Сч 1 - первый счетчик 3;Сч 2 - второй счетчик 4;БлСч - блок 14 счетчиков;См 1 - первый сумматор 8;См 2 - второй сумматор 9;СхСд - второй сдвигатель 6;обозначает запись информанала СС. Этот сигнал информируетпроцессор о том, что на выходе См 2находится адрес А 1 (первого операнда, на выходах См 1 - адрес А 2 второго операнда и на выходах СхСд - адрес АЗ тригонометрического коэффи-. циента).В рассматриваемом примере в этом случае А 1 = 000, А 2 = 00 и АЗ =000. Так как в Сч 2 и записан О, а на инверсных выходах всех разрядов Сч 2,кроме младшего, находится код 11, на выходе блока 11 сравнения находится логический нуль (РЗ = О). Поэтому н алгоритме выполняется переход от вершины 8 к вершине 9, Так как сигнал У 2 при этом не вырабатывается, сигнал У 4 добавляет к содержимому Сч 2 единицу. После этого по сигналу Уб на выходах См, См 2 и СхСд считываются адреса А 1 =010, А 2=011 и АЗ= =000. В следующем цикле считываются коды 00, 101, 000 и наконец, коды 110, 111 и 000. При этом на выходе .блока 11 сраннения появляется логическая единица, так как с Сч 2 записан код 11. Поскольку на выходе блока 1 О сравнения также установлена логическая елиница (Р 21), выполняется переход к вершине 10 блок-схемы алгоритма. Формируемый при этом сигнал У 5 сдвигает содержимое Рг 1 и Рг 2 влево на один разряд, В младший разряд Рг 1 записывается логический нуль, а Рг 2 - логическая единица. Так как в Рг 1 записан не нуль, сигнал Рг=0. Поэтому выполняется переход к верши не 3 алгоритма. Производится новая запись кодов в счетчики 31. В рассматриваемом примере записывается код 01, При этом на выходе блока 15 фиксации нуля появляется логический нуль (Р 4 О). Так как на выходе блока 1 О сравнения тоже нуль (02=0), формируется сигнал УЗ, который добавляет 1 к содержимому Сч 1 и вычитает 1 из содержимого счетчиков 31; В результате счетчики 31 обнуляются и появляется сигнал Р 4 - 1, Поэтому выполняется переход к вершине 7 алгоритма и считывается адрес А 1 = 001, А 2 = 011 и АЗ = 010. В следующем цикле содержимое Сч 2 увеличива, ется на единицу и считываются адреса,А 101, А 2 = 111 и АЗ = 010. Затем проходит очередной сдвиг кодов в Рг 1 и Рг 2 и новая запись всчетчик 31, На этот раз в них записывается код 11, Так как Р 4=0 происходит обращение к вершине б алгоритма. После трех обращений счетчик31 обнуляется, а н Сч 1 появляется код 11При появлении следующего импульса сигнала СС БУ формирует Уб, и с выходов СИ 1, См 2,- СхСд считьва -ются коды 101, 111, 011. Затем происходит очередной сдвиг кодов и Рг 1и Рг 2, Так как Рг при этом обнуляется, БУ по сигналу Р 4 с выхода элемента И 7 прекращает работу устрой 78883 6стна для формирования адресов процессора усеченного БПФ,Формула изобретения5Устройство для формирования адресов процессора усеченного быстрогопреобразования Фурье, содержащее первый регистр сдвига, первый и второйсчетчики, блок управления, первыйвыход которого подключен к установочным входам первого и второго счетчиков, счетные входы которых подключены соответственно к второму итрет ему выходам блока управления, четвертый и пятый выходы которогоподключены соответственно к тактовому входу и входу управления направлением сдвига первого регистра сдвига,о т л и ч а ю щ е е с я тем, что, сцелью повышения быстродействия, в него введены первый и нторой сумматоры,второй регистр сдвига, первый и второй сдвигатели, элемент И, первый ивторой блоки сравнения, блок счетчиков, первый и второй блоки элементов И, элемент ИЛИ и блок регистров,1,-й выход(1.=1,г, г- разрядность) которого подключен к -му входу первого блока элементов И, 1.-й выход которого подключен к 1.-му, информационному входу блока счетчиков, д-й информационный выход которого подключен к 1-му входу второго блока эле ментов И, -й выход которого подключен к -му входу элемента ИЛИ, вы"ход которого подключен к первому входу блока управления , первый, второй, четвертый и пятый выходы кото рого подключены соответственно кустановочному и счетному входам блока счетчиков и тактовому и установочному входам нторого регистра сдвига,,)-й ( =2,г) разряд прямого выхода 45 которого подключен к (+г)-му вхо"ду первого блока элементов И и(1-1)-му входу первого блока сравнения, выход которого подключен квторому входу блока управления, тре тий вход которого подключен к выходу второго блока сравнения.-1)-йвход которого подключен к )-муразряду инверсного выхода второгорегистра сдвига, -й разряд прямоговыхода первого регистра сдвига подключен к -му входу первого сум матора, -му входу управления сдвигом первого сднигателя, х-й выход12788 которого подключен к д-му входу второго сумматора, -й выход которого является -м адресным выходом первого операнда устройства и подключен к (+г)-му входу первого сумма тора, 1-й выход которого является -м адресным выходом второго операнда устройства, выходом адреса коэффициента которого является -й выход второго сдвигателя -1)-й вход управления сдвигом которого подключен к -1)-му разряду прямого выхода первого регистра сдвига, 1"й разряд инверсного выхода которого подключен к -му входу элемента И,15 выход которого подключен к четвертому входу блока управления, (-1)-й разряд выхода первого счетчика подключен к +г)-му входу первого блока сравнения, (-1)-му информационному входу второго сдвигателя и (+г)-му входу второго суиматора, (1-1)-й разряд выхода второго счетчика подключен к (+г)-му вхо 25 ду второго блока сравнения и (1-1)- му информационному входу первого сдвигател шестой выход блока управ" ления является выходом синхронизации устройства, блок управления со-держит десять элементов ИЛИ, шесть элементов НЕ, шестнадцать элементов И, три ВБ-триггера, дешифратор и генератор тактовых импульсов, выход которого подключен к первым входам элементов И с первого по шестой, к входу первого элемента НЕ, выход которого подключен к входам синхронизации первого, второго и третьего ВЯ-триггеров, выходы которых подключены Соответственно к первому, второму и третьему входам дешифратора, первый и второй выходы которого подключены соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к первым входам второго и третьего элементов ИЛИ, выходы которых подключены соответственно к В-входу первого ВЯ-триггера и первому входу седьмого элемента И, выход которого подключен к Я- входу второго ВБ-триггера, третий выход дешифратора подключен к второму входу первого элемента И,первому входучетвертого элемента ИЛИ и первому входу пятого элемента ИЛИ, выход которого подключен к Я-входу первого ВЯ-триггера, четвертый выход дешифратора подключен к второму входу эле 83 8мента И, первым входам шестого и седьмого элементов ИЛИ, первым входом восьмого и десятого элементов И, выходы которых подключены соответственно к Я-входу третьего ВБ-триггера, второму входу второго элемента ИЛИ и первому входу восьмого элемента ИЛИ, выход которого подключен к первому входу девятого элементаИЛИ, выход которого подключен к Ввходу второго ВЯ-триггера, пятыйвыход дешифратора подключен к второму входу третьего элемента И и первым входам одиннадцатого, двенадцатого и тринадцатого элементов И, выходы которых подключены соответственно к второму и третьему входам восьмого элемента ИЛИ и второму входупятого элемента ИЛИ, шестой выходдешифратора подключен к второму входу седьмого элемента ИЛИ и первымвходам четырнадцатого и пятнадцатогоэлементов И, выходы которых подключены соответственно к.третьему входувторого элемента ИЛИ и четвертомувходу восьмого элемента ИЛИ, седьмойвыход дешифратора подключен к второму входу четвертого элемента ИЛИ,первому входу десятого элемента ИЛИи первому входу шестнадцатого элемента И, выход которого подключен квторому входу третьего элемента ИЛИ,третий вход которого объединен с вторым входом шестого элемента ИЛИ иподключен к восьмому выходу дешифратора, вторые входы седьмого и восьмого элементов И объединены и подключены к выходу второго элементаНЕ, вход которого объединен с вторыми входами девятого и десятого элементов ИЛИ и подключен к выходутретьего элемента НЕ, вход которогоявляется входом задания логическойединицы устройства, выходы первого,второго и третьего элементов И являются соответственно пятым, первыми шестым выходами блока, четвертым,третьим и вторым выходами которогоявляются выходы соответственно четвертого, пятого и шестого элементовИ, вторые входы которых подключенык Выходам соответственно четвертогошестого и седьмого элементов ИЛИ,второй вход шестнадцатого элементаИ подключен к выходу четвертого элемента НЕ, вход которого является четвертым входом блока, второй вход которого подключен к вторым входамодиннадцатого и пятнадцатого элементов И, второй вход двенадцатого элемента И подключен к выходу пятогоэлемента НЕ, вход которого объединенс вторым входом тринадцатого элемента И и является третьим входом бло 278883 ока, первый вход которого подключенк вторым входам девятого и четырнадцатого элементов И и входу шестогоэлемента НЕ, выход которого подключен к второму входу десятого и треть.ему входу пятнадцатого элементов И.1278883 ставитель А. Барановхред А.Кравчук Тираж 671Государственногоо делам изобретений и035, Москва, Ж, Ра Подписн д. 4/ Производств олиграфическо едприяти едактор В. Иванова Заказ 6841/49ВНИИПИ 7 7 2345 б омитета открытийушская на Корректор А, Обруча город, ул, Проектная, 4