SU1645966A1 - Устройство дл вычислени преобразовани Фурье - Галуа - Google Patents

Abstract

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

Description

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

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

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

Устройство содержит первую группу из Р регистров 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) новой последовательности .

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

Claims (1)

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-го регистра первой

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

   11

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

   tz