Устройство для вычисления преобразования фурье-галуа Советский патент 1986 года по МПК G06F17/14 

I

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

Цель изобретения - повышение быстродействия устройства.

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

Функциональная схема устройства , для вычисления преобразования Фурье- Галуа содержит р регистров 1 (проме- жуточного хранения данн ых), р .блоков элементов ИЛИ 2, регистров 3 (хранен данных), р умножителей 4 на коэффициент, сумматор 5 по модулю М (М 2 - р - разрядность чисел), синхрони.- затор 6, состоящий из сдвигового регистра 7, р элементов ИЛИ 8, RS-триг гера 9 и элемента И 10, информационный 11 и тактовый входы 12. Да- лее с приходом 2-го отсчета регистр 7 переключается в состояние, когда уровень логической 1 появляется на втором выходе, т.е. на выходе второй ячейки регистра 7, и второй отсчет входных данных аналогично первому записывается во второй регистр 3. Точно так же записываются остальные отсчеты входных данных. 11оследш1й Р -и отсчет записывается в Р-и регистр 3. С выходов р регистров отсчеты входных даннь1Х поступают на Р умножителей 4. Первый блок 4 производит умножени на 2 , второй блок 4 - на третий блок 4 - . ..., р-й блок 4 производит умножение на 2 . Пос- кольку при преобразовании Фурье-Галуа вычисления производятся по модулю целого числа, в данном случае по модулю числа М , где f - простое число, то умножения на коэф- фициент представляют собой циклические сдвиги кодового слова. Реализовать умножение на коэффициент по модулю М 2 можно простой коммутацией проводов. С выходов Р бло- ков 4 значения отсчетов х{0),..., х(р- ) умноженные соответственно на 2 , 2,..., 2- , поступают на Р регистров 1 соответственно, где запоминаются. Кроме тог о, данные с выходов Р блоков 4 поступают на входы сумматора 5 Р-разрядных чисел

по модулю М

p-t

. в результате

Q

o 5 0 5

0

5

3962

суммирования получаем спектральныГ коэффициент (P--I). Сумматор 5Р -раз РЯДШ11Х чисел по модулю М состоит из обычного Сумматора р-разрядных чисел и р-разрядного сумматора, служащего для коррекции результата суммирования по модулю М. Разряды, вьпиедшие за пределы р-разрядной сетки, суммируются с младшими. Возможный перенос Р в ( разряд суммируется с младшими разрядами. С выходов Р регистров 1 данные через Р блоков 2 поступают и запоминаются в Р регистрах 3 и снова умножаются на коэффициенты последней строки матрицы преобразования. В результате суммирования умноженных вторично отсчетов входных данных получаем значение спектрального коэффициента S(P-2). Такой процесс повторяется Р раз, пока не получится спектральный коэффициент S (О).

Управление этим процессом осуществляется следующим образом.

Регистр 7 переключается в положение Р+1 (при записи последнего отсчета входных данных регистр 7 находится в состоянии, когда напряжение логической 1 присутствует на выходе р - положение р). Импульс с выхода (р+1)-го регистра 7 устанавливает RS- триггер в положение . Сигнал открывает прохождение тактовой частоты через элемент И 10. Импульс с выхода этого элемента поступает на тактовые входы р регистров 1. Тот же импульс с выхода элемента И 10 поступает на входы элементов ИЛИ 8, с выходов которых он уже в качестве Р импульсов поступает на тактовые входы Р регистров 3. С появлением сигнала логической 1 на выходе регистра 7 RS-триггер устанавливается 13 состояние , закрывая элемент И 10, но за счет задержки включения RS-триггера импульс тактовой частоты успевает пройти на тактовые входы р регистров 1 и 3, и в результате вычисляется коэффициент S(0). С приходом следующего импульса тактовой частоты регистр 7 устанавливается в нулевое положение и тем самым схема готова к приему следующих бтсчетов входных данных .

Формула и 3 о R р е т е н и

Устройство До1я вычисления преобразования Фурье-Галуа, содержащее первую и вторую группы регистров по р регистров , причем выход i-ro ( р) регистра второй группы подключен к входу i-ro умножителя на коэффициент, выход которого подключен к i-му входу сумматора по модулю М (М 2, выход которого является информационным выходом устройства, отли чающееся тем, что, с целью повьшения быстродействия, в него введены Р блоков элементов,ИЛИ, RS-триггер, элемент И, р элементов ИЛИ и сдв иговый регистр, выход i-ro разряда которого подключен к первому входу i-ro элемента ИЛИ, выход которого подключен к тактовому входу i-ro регистра второй группы, информационный вход

18396

которого подключен к выходу i-ro блока элементов ИЛИ, первый вход которого подключен к выходу i-ro регистра первой группы, информаци- 5 онный вход которого подключен к выходу i-ro умножителя на коэффициент, выход (р+1)-го разряда сдвигового регистра подключен к S-входу RS-триг- гера, выход которого подключен к

10 первому входу элемента И, выход которого подключен к второму входу i-ro элемента ИЛИ и тактовому входу i-ro регистра первой группы, вторые входы блоков элементов ИЛИ являются

15 информационными входами устройства, тактовым входом устройства нвляет- |ся тактовый вход сдвигового регистра, соединенный с вторым входом элемента И, а выход { 2р-1)-гс

20 разряда сдвигового регистра подключен к R - входу RS - триггера.

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