Устройство для вычисления преобразования Фурье - Галуа Советский патент 1991 года по МПК G06F15/332 

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

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

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

Устройство содержит первую группу из Р регистров 1, вторую группу из Р регистров 2, Р коммутаторов 3, Р умножителей 4 на коэЛбициент, сумматор 5 по модулю М (И 2р-1, где Р - разрядность чисел), RS-триггер 6, элемент ИЛИ 7, сдвиговый регистр

8, установочный вход 9, тактовый вход 10, информационный вход 11 и информационный выход 12.

Устройство работает следующим образом.

Импульсом на входе 9 обнуляются все регистры 1, 2 и 8 устройства и включается PS-триггер 6 (), устанавливая уровень 1 на информационном входе сдвигового регистра 8 и соединяя первые информационные входы Р коммутаторов 3 с их выходами.

Первый тактовый импульс, поступающий на тактовый вход 10 устройства, приводит к появлению уровня 1 на первом выходе сдвигового регистра 8, который выключает RS-триггер 6 (), устанавливает уровень О на информационном входе сдвигового регистра 8, соединяет вторые информационные входы Р коммутаторов 3 с их выходами и

ш

tf

С

05

4ь СЛ

Ј О5 55

31

записывает первый отсчет входной последовательности в первый регистр первой группы регистров 1. Второй тактовый импульс приводит к сдвигу 1 на второй выход сдвигового регистра 8 и записи второго отсчета входной последовательности во второй регистр первой группы регистров 1 и ТсДс Р-й тактовый импульс сдвигает 1 на Р-й выход сдвигового регистра 8, что приводит к записи Р-го отсчет входной последовательности в Р-й регистр первой группы регистров 1, включению RS-триггера 6, появлению уровня 1 на информационном входе сдвигового регистра 8 и соединению первых информационных входов Р ком- яутаторов 3 с их выходами. С выходов первой группы регистров 1 отсчеты входной последовательности поступают через Р коммутаторов 3 на Р умножителей 4 с Первый умножитель 4 производи умножение на 2, второй - на 2Р , третий - на 2 тель производит

Поскольку при преобразовании Фурье- Галуа вычисления производятся по модулю целого числа, в данном случае по модулю числа -1, где Р - простое число, то умножения на коэффициент представляют собой циклические сдвиги кодового слова о- Реализовать умножения на коэффициент можно простой коммутацией входов и выходов умножителей 4„ С выходов Р умножителей

4значения отсчетов Х(0),.е„,Х(Р-1), умноженные соответственно на 2 ,

,с„.,2, поступают на информационные входы второй группы регистров 2 соответственно и на входы сумматора

5Р-разрядных чисел по модулю М

2р-1„ Сумматор 5 Р-разрядных чисел

и

т„дс Р-й умножи- умножение на 2 .

р по модулю -1 состоит из обычного

сумматора Р-разрядных чисел и Р- разрядного сумматора, служащего для коррекции результата суммирования по модулю Ко В результате суммирования получаем спектральный коэффициент S(P-1)0 Следующий (Р-1)-й или снова первый тактовый импульс приводит к появлению уровня 1 на первом выход сдвигового регистра 8, включению RS- триггера 6, соединению вторых информационных входов коммутаторов 3 с их выходами, записи первого отсчета новой входной последовательности в первый регистр первой группы регистров 1 и записи результатов умножения

0

Q 5

5

5

0

0

5

0

5

предыдущего такта во вторую группу регистров 2. С выходов второй группы регистров 2 через коммутаторы 3 результаты первого умножения снова поступают на Р умножителей 4 на коэффициент, с выходов которых результаты второго умножения поступают на информационные входы второй группы регистров 2 и на информационные входы сумр

матора 5 по модулю -1„ В результате суммирования получается спектральный коэффициент S(P-2).

Следующий (Р+2)-й или второй, тактовый импульс приводит к записи второго отсчета новой входной последовательности во второй регистр первой группы регистров 1 и вычислению сле- эующего спектрального коэффициента S(P-3).

Во время следующих тактов происходит запись остальных отсчетов новой последовательности в остальные регистры первой группы регистров 1 и вычисления следующих спектральных коэффициентов S(P-4), S(P-5) и т.д„ аналогично описанному.

(Р-1)-й или (2Р-1)-й тактовый импульс приводит к записи предпоследнего отсчета новой последовательности в (Р-1)-й регистр первой группы регистров 1 и вычислению последнего спектрального коэффициента 8(0)„

Р-й или 2Р-й тактовый импульс приведет к включению RS-триггера 6, уровню лог„ 1 на информационном входе сдвигового регистра 6, соединению первых информационных входов коммутаторов 3 с их выходами, записи результатов последнего умножения во вторую группу регистров 2 и последнего отсчета новой последовательности в Рй регистр первой группы регистров 1„ С выходов первой группы регистров 1 данные через коммутаторы 3 поступают на умножители 4 на коэффициент, затем на информационные входы второй группы регистров 2 и на сумматор 5 по модулю -1, где происходит вычисление первого спектрального коэффициента S(P-1) новой последовательности.

В дальнейшем работа устройства происходит аналогично

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

Устройство для вычисления преобразования Фурье-Галуа, содержащее

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

входу PS-триггера, выход которого под- 20 товому входу 1-го регистра первой

1645966

и Р-го разрядов которого подключены гоответственно к Г8-триггепа и первому входу элемента ИЛИ, второ вход которого подключен к установочному входу устройства, информацион- ным входом которого являются соединенные между собой информационные входы регистров первой группы, выход

1-го регистра которой подключен к первому информационному входу 1-го коммутатора, выход которого подключен к входу 1-го умножителя на коэффициент, выход которого подключен к

информационному входу i-ro регистра второй группы, выход которого подключен к второму информационному входу 1-го коммутатора, выход 1-го разряда1 сдвигового регистра подключен к тактовому входу 1-го регистра первой

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки изображений. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что -в состав устройства входят две группы из Р (Р - размер преобразования) регистров 1, 2, Р коммутаторов 3, Р умножителей 4 на коэффициент, сумматор 5, RS-триггер 6, элемент ИЛИ 7 и сдвиговый регистр 8. 1 ил.

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

11

группы, а тактовые входы всех регистров второй группы подключены к тактовому входу устройства.

tz