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

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

Иллюстрации

Показать все

Реферат

 

1. АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ , содержащее восемь входных и восемь вькодных регистров, семь выходных блоков элементов и,, i сумматрры-вычитатели по модулю Р{ 2 (j 1, 2, 3, 4 - номер сумматора-вычитателя , Р - целое положительное число), умножитель, причем информационные входы входных регистров являются входами отсчетов входного сигнала устройства, вход множителя умножителя является входом поворачивсшщегб множителя устройства , выход j -го ( j ) выходного регистра подключен ко входу (j+1)-го выходного регистра и к информационному входу -го выходного блока элементов И, выходы всех выходных блоков элементов И и восьмого выходного регистра являются информационными выходакш ус ройства, управляшций вход укоюжителя, а также . соединенные между собою управлякхцие входы выходных блоков элементов И «подключены к соответствующим тактовым входам устройства, отличающееся тем, что, с целью повышения быстродействия и повышения точности устройства, оно содержит преобразователь дбоичного кода в модулярный код, преобразователь модулярного кода в двоичный код, первый , второй и третий регистры, первый и второй блоки элементов И, блок (постоянной памяти, а также регистры и блоки элементов И, объединенные в четыре группы, каждая из которых состоит из девяти регистров и тринадцати блоков элементов И, причем, выход j -го (} 1-7) вход;ного регистра подключен к дополни тельному информационному входу (j+l)-ro входного регистра, выход первого регистра подключен к информационному входу первого блока элементов И, к первому входу преобразователя двоичного кода в моду (Л лярный код, выход знакового разряда восьмого входного регистра подс ключен ко второму; входу преобразо-; вателя двоичного кода в модулярный; код, выходы разрядов с bf nobg + I + Ье4,- 1 (е О, 1, 2j bo , bi., bj , 03 - натуральные числа такие , что Ьо+Ъ +Ь2 +b-j г + г-г + г,- - 1 Ъ-) 2) восьмого входного регистра, образующие его

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (д) 0 06 Р 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3365921/18-24 (22) 18.12.81 (46) 15.09.83. Бюл. В 34 (72) А,А.Коляда, Л.Н.Василевич, В.В.Ревинский и A.Ô.×åðíÿâñêèé (71) Научно-исследовательский институт прикладных физических проблем им. акад. A.Н.Севченко (53) 681.3(088.8) (56) 1. Патент Ctr!A 9 3920978, кл. G 06. F 15/34, опублик. 1975.

2. Ben-Dan Trang. G А. Jullian, member, 1ЕЕЕ and Willisn С. Miller.

1mp1ementation оГ FFT Structures

Using Sistern. 1ЕЕЕ, Trans Comprit, 1979, М 11, р. 29 (прототип). (54)(57) 1. АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЭОВАНИЯ ФУРЬЕ, содержащее восемь входных и восемь выходных регистров, семь выходных блоков элементов И,. в сумматоры-вычитатели по модулюР; г

= 2 (j= 1, 2, 3, 4 — номер сумматора-вычитателя, r — целое положительное число), умножитель, причем информационные входы входных регистров являются входами отсчетов входного сигнала устройства, вход множителя умножителя является входом поворачивакицего множителя устройства, выход j --,го () = 1-7) выходного регистра подключен ко входу () +1)-го выходного регистра и к информационному входу у -го выходного блока элементов И, выходы всех выходных блоков элементов И и восьмого выходного регистра являются информационными выхоцамн у*ройства, управляющий вход умножителя, а также соединенные между собою управляющие входы выходных блоков элементов И ,подключены к соответствующим тактовым входам устройства, о т л и ч аю щ е е с я тем, что, с целью повькаения быстродействия и повышения точности устройства, оно содержит

„„80„„.1 42 A преобразователь двоичного кода в модулярный код, преобразователь модулярного кода в двоичный код, первый, второй и третий регистры, первый и второй блоки элементов Й, блок (постоянной памяти, а также регистры и блоки элементов И, объединенные в четыре группы, каждая из которых состоит. из девяти регистров и тринадцати блоков элементов

И, причем выход j --го (j= 1-7) входноro регистра подключен к дополнительному информационному входу

-(+1)-го входного регистра, выход первого регистра подключен к информационному входу первого блока элементов И, к первому входу преобразователя двоичного кода в модулярный код, выход знакового разряда восьмого входного регистра подключен ко-второму. входу преобразо-: ! вателя двоичного кода в модулярный, код, выходы разрядов с bp поЬ +

+bc. 1(8= 0, 1, 2;b,,b,,b, bq — натуральные числа такие, что

Ь+Ъ„+be+Üú = Г + .tg + +Р4

1, 5> > 2) восьмого входного регистра, образующие его (0 + 1)-й параллельный выход, подключены к (+ 3)-му входу преобразователя двоичного кода в модулярный код, j-й (q = 1-4) выход преобразователя .двоичного кода в модулярный код подключен к информационным входам . первого и второго блоков элементов

И -й группы, выходы которых под.ключены соответственно ко входу первого и первому входу второго ре-. гистров -й группы, выход первого регистра j -й группы подключен к . первому входу третьего регистра 1 -й группы, выход которого, а также выход второго регистра 1 -й группы подключены ко входам соответствующего сумматора-вычитателя по модулю

Р; выход разности сумматора-вычи1042028 тателя по модулю Pj подключен к информационным входам третьего и четч; вертого блоков элементов И -й груйпы, а выход сумин сумматора-нычи4а теля по модулю - к информационным входам пятого, шестого и седьмого блоков элементов И -й группы, выходы четвертого и пятого блоков элементов И i --й группы подключены соответственно ко входу четвертого и первому входу пятого регистров

<-й группы, ныход седьмого блока элементов Й ) -й группы подключен .ко. второму входу второго регистра q --й группы, выход четвертого регистра у-й группы подключен к информационным входам восьмого и девятого блоков элементов И -й группы, выходы которых подключены соответст венно ко входу шестого и второму входу пятого регистров < --й группы, выход пятого регистра j -й группы подключен ко входу седьмого регистIpa i -й группы, выход шестого регистра i -й группы подключен к информационным входам десятого и одиннадцатого блоков элементов И f -й группы, выход седьмого регистра 1 -й группы подключен к информационным входам двенадцатого и тринадцатого блоков элементов И -й группы, выхо.-.. ды десятого и тринадцатого блоков

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

3-й группы, выходы третьего и двенадцатого блоков элементов И 3 -й группы подключены ко входам восьмого регистра j -й группы, выход шестого блока элементов И -й группы подключен к первому входу девятого регистра i --й группы, выход восьмого и второй вход девятого регистров 4 -й группы поцключены соответственно ко входу i -го разряда множимого умножителя и. к выходу j --го разряда умножителя, выход .девятого регистра ч -й группы подключен к

1-му входу преобразователя модулярного кода в двоичный код, первый выход которого подключен ко входу второго регистра, а второй, третий и четвертый выходы - ко входам соответствующих групп разрядов первого выходного регистра, выходы второго и третьего регистров подключены к соотнетствующим группам адресных входов блока постоянной памяти выход;.которого подключен к информационному входу третьего регистра и через второй блок элементон И - к информационному входу первого регистра, установочные входы первого и,второго регистров являюТся устано+вочными входами устройства, выход первого блока элементов И является выходом порядка преобразуемых чисел устройства, управляющие входы пер- вого и второго блоков элементов И, а также объединенные управляющие входы одноименных блоков элементов

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

2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что преобразователь двоичного кода в модулярный код состоит из первого, второго и третьего блоков постоянной памяти и четырех суммирующих блоков, в каждом из которых содержится пять регистров и два сумматора, причем адресные входы k -го (k = 1, 2, 3) блока постоянной памяти. являются первым, вторым и (k + 2) -м входами. преобразователя двоичного кода в модулярный код, -я группа выходов

k-го блока постоянной памяти подключена ко входу k -го регистра в 1 -й суммирующем блоке, выходы первого и второго регистров.каждого сумми1рующего блока подключены ко входам соответствующего первого сумматора, выход которого подключен ко входу четвертого регистра этого суммирующего блока, выход третьего регистра в суммирующем блоке подключен ко входу пятого регистра, выход которого и выход четвертого регистра того же суммирующего блока подключены ко входам соответствующего. второго сумматора, ныходы вторых сумматоров суммирующих блоков являются выходами преобразователя дноич" ного кода в модулярный код.

3. Устройство по п. 1, о т л ич.а ю щ е е с я тем, что преобразователь.модулярного кода в двоичный код состоит из девяти сумматоров, двадцати одного элемента задержки и блока постоянной памяти, причем первые входы первого, второ.

ro и третьего сумматоров являются: соответственно первым, вторым и третьим входами преобразователя модулярного кода в двоичный код, объединенные вторые входы первого, второго и третьего сумматоров яв- ляются четвертым входом преобразователя модулярного кода в двоичный код, выход первого сумматора через .последовательно соединенные первый, второй, третий и четвертый элементы задержки подключен к первому входу четвертого сумматора, выход второго сумматора через последовательно соединенные пятый, шестой,,седьмой и восьмой элементы задержки под:ключен к первому входу пятого сумматора, выходы четвертого и пятого сумматоров соотнетственно через девятый и десятый элементы задержки поцключены к адресным входам блока

1042028

10

35 постоянной памяти, выход третьего сумматора через одиннадцатый элемент задержки подключен к первому входу шестого сумматора, второй вход шестого сумматора подключен к выходу шестого элемента задержки, а выход шестого сумматора через двенадцатый элемент задержки подключен к первому входу седьмого сумматора, второй вход которого и первый вход восьмого сумматора подключены к выходу второго элемента задержки, второй вход восьмого сумматора подключен к выходу седьмого элемента задержки, выходы седьмого и восьмого сумматоров через тринадцатый и четырнадцатый элементы задержки подключены ко входам девятого сумматора, выход которого через пятнадцатый элемент

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

Фурье с основанием "4", ориентированных на обработку сигналов невысокой разрядности (12-24 бит).

Большинство известных устройств для быстрого преобразования Фурье выполняют различные алгоритмы с основанием "2", которые характеризуются максимальным количеством последовательных шагов, а следовательно, и умножений чисел.

Использование алгоритмов быстрого преобразования Фурье с основанием

"4" позволяет существенно уменьшитьобщее число умножений. Кроме того, алгоритмы с основанием "4" отличаются более высокой точностью p)-.

Недостатком известных быстродействующих процессоров быстрого преобразования Фурье с основанием "4" является сложность их арифметияеских устройств.

Наиболее близким к изобретению является арифметическое устройство, реализующее алгоритм быстрого преоб раэования Фурье с основанием "4" в модулярных системах счисления и со.е держащее восемь входных и восемь выходных регистров, .семь выходных блоков элементов И, четыре сумматора-вычитателя по модулю Р = 2 (i =.

= 1, 2, 3, 4 — номер сумматора-вычитателя; — целое положительное число), умножитель f2) .

Недостатками известного устройст-: ва являются низкая точность, обусловленная большой погрешностью задержки подключен ко вторым входам четвертого и пятого сумматоров и входу шестнадцатого элемента задержки, вход семнадцатого элемента задержки подключен ко вторым входам первого, второго и третьего сумматоров, а выход семнадцатого элемента задержки через последовательно соединенные восемнадцатый, .девятнадцатый и двадцатый элементы задержки подключен ко входу двадцать первого элемента задержки, первый и второй выходы блока постоянной памяти, а также выходы шестнадцатого и двадцать первого элементов задержки являются соответственно первым, вторым, третьим и четвертым выходами преобразователя модулярного кода в двоичный код.

2 используемой процедуры масштабиро вания, и малое быстродействие.

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

Поставленная цель достигается тем, что арифметическое устройство для процессора быстрого преобразования Фурье, содержащее восемь вход,", ных и восемь выходных регистров, семь выходных блоков элементов И, четыре сумматора-вычитателя йо мо-.. дулю Р„= 2" (j= 1, 2, 3, 4 — номер сумматора-вычитателя; г — целое

15 положительное число), умножитель, причем информационные входы входных регистров являются входами отсчетов входного сигнала устройства, вход множителя умножителя является. входом поворачивающего множителя устройства, выход . j -го (j = 1-7} выходного регистра подключен ко входу (j + 1) -ro выходного регистра и к информационному входу -го выходного блока

25 элементов И, выходы всех выходных блоков элементов И и восьмого вы-, кодного регистра являются информационными выходами устройства, управляющий вход умножителя, а также соединенные между собою управляющие входы выходных блоков элементов И подключены к соответствующим тактовым входам устройства, содержит преобразователь двоичного кода в модулярнцй код, преобразователь модулярного кода в двоичный код, первый, второй и третий регистры, первый, второй блоки элементов И, блок постоянной памяти, а также, регистры и блоки элементов И, объе«

1042028 диненные в четыре группы,, каждая из которых состоит из девяти регистров и тринадцати блоков эле ментов И, причем выход j --ro(j =1-7) входного регистра подключен к дополнительному информационному входу (+ 1) -го входного регистра, выход первого регистра. подключен к информационному входу первого блока элементов И и к первому входу преобразователя двоичного кода 10 в модулярный код, выход знакового разряда восьмого входного регистра подключен ко второму входу преобразователя двоичного кода в модулярный код, выходы разрядов с bq по 15

ЬЕ+ЬЕ||- 1(8= О, 1, 2; Ъо Ъ| bi

Ь вЂ” натуральные числа такие, что

tb+b1+ Ь7+ Ъ1 = r1 + "г + r5 +Г4

Ъ = 1, Ь |>21 восьмого входного регистра, образующие его (9 + 1) -й парал- лельный выход, подключены к (0 +3)-.му входу преобразователя двоичного кода в модулярный код, t -й (i = 1-4) выход преобразователя двоичного ко- да в модулярный код подключен к 2S информационным входам первого и второго блоков элементов И -й группы, выходы которых подключены соответственно ко входу первого и и первому входу второго регистров (-й группы, выход первого регистра

i †. и группы подключен к первому входу третьего регистра | -й группы, выход. которого, а также выход второго ре- гистра | -й группы подключены ко входам соответственно сумматора-вычитателя по модулюР;, выход разности сумматора-вычитателя по модулю

Р! подключен к информационным входам третьего и четвертого блоков элементов И -й группы, а выход 4О суммы сумматора-вычитателя по модулю Р; — к информационным входам пятого, шестого и седьмого блоков элементов И -й группы, выходы четвертого и пятого блоков элементов 45

И j --й группы подключены соответствен но ко входу четвертого и первому

-, входу пятого регистров 1 -.й группы, выход седьмого блока элементов И

1-й группы подключен ко второму входу второго регистра « -й группы, выход четвертого регистра N -й группы подключен к информационным входам восььюго и девятого блоков элементов И 1 -й группы, выходы которых подключены соответственно ко входу шестого и второму входу пятого регистров у -й группы, выход пятого регистра t --й группы подключен ко входу седьмого регистра

i-й группы, выход-шестого регистра Я)

t"й группы подключен к информационным входам десятого и одиннадцатого блоков элементов И 1 -й группы, выход седьмого регистра -й группы подключен к информационным входам двенадцатого и тринадцатого блоков элементов И j --й группы, выходы десятого и тринадцатого блоков элементов И -й группы подключены соответственно ко второму и третьему входам третьего регистра it -й группы, выход одиннадцатого блока элементов И | -й группы подключен, к третьему входу пятого регистра || -N;rpynmf, выходы третьего и двенадцатого блоков элементов И -й группы подключены ко входам восьмого регистра | -й группы, выход шестого блока элементов Й у -й группы подключен к первому входу девятого регистра i --й группы, выход восьмого и второй вход девятого регистров | -й группы подключены соответственно ко входу -го разряда множимого умножителя и к выходу j «ro разряда умножителя, выход девятого регистра t -й группы подключен к 1 -му входу преобоазователя модулярного кода в двоичный код, первый. выход которого подключен ко входу второго регистра, а второй, . третий и четвертый выходы — ко входам соответствующих групп разрядов первого выходного регистра, выходы второго и третьего регйстров подключены к соответствующим группам адресных входов блока постоянной памяти, выход которого подключен к информационному входу третьего регистра и через. второй блок элементов И вЂ” к информационному входу первого регистра, установочные входы первого и второго регистров являются установочными входами устройства, выход первого блока элементов И является выходом порядка преобразуе мых чисел устройства, управляющие входы первого и второго блоков эле, Ментов И, а также соединенные управляющие входы одноименных блоков элементов И четырех групп подключены к соответствующим тактовым входам устройства.

Кроме того, преобразователь двоич- ного кода в модулярный код состоит из первого, второго и третьего блоков постоянной памяти и четырех .суммирующих блоков, в каждом из которых содержится пять регистров и два сумматора, причем адресные входы k-ro (k = 1,2,3) блока постоянной памяти являются первым, вторым .и (k + 2)-м входами преобразователя двоичного кода в модулярный код, |-я группа выходов k-го блока пос-. тоянной памяти подключена ко входу.

k-ro регистра в t -м суммирующем» блоке, выходы первого и второго регистров каждого суммирующего блока подключены ко входам соответствующего первого сумматора, выход которого подключен ко входу четвертого регистра в этом суммирующе| | бл|пке, 1042028 . выходы вторых сумматоров суммирующих блоков являются выходами пре" обраэователя двоичного кода в модулярный код. При этом преобразователь модулярного кода в двоичный код сос о-. ит. из девяти сумматоров, двадцати одного элемента задержки и блока постоянной памяти, причем первые входы первого, второго и третьего сумматоров являются соответственно первым, вторым и третьим входами преобразователя модулярного кода в двоичный код, соединенные вторые входы первого, второго и третьего сумматоров являются четвертым входом в в преобразователя модулярного код а двоичный код, выход первого сумматора через последовательно соединенные первый, второй, третий и четвертый элементы задержки подключен к первому входу четвертого сумматора, выход второго сумматора через последовательно соединенные пятый, шестой, седьмой и восьмой элементы задержки подключен к первому входу пятого сумматора, выходы четвертого и пятого сумматоров соответственно через девятый и десятый элементы задержки подключены к адресным входам блока постоянной памяти, выход третьего сумматора через одиннадцатый элемент задержки подключен к первому входу шестого сумматора, второй вход шестого сумматора подключен к выходу шестого элемента задержки, а выход шестого сумматора через двенадцатый элемент задержки. подключен к первому входу седьмого сумматора, второй вход которого вместе с первым входом восьмого сумматора подключен к выходу второго элемента задержки, второй вход восьмого сумматора подключен к выходу седьмогЬ элемента задержки, выходы седьмого и восьмого сумматоров через тринадцатый и четырнадцатый элементы задержки подключены к входам девятого сумматора, выход которого через пятнадцатый элемент задержки подключен ко вторым входам четвертого и пятого сумматоров и входу шестнадцатого элемента задержки, вход семнадцатого элемента задержки подключен ко вторым входам первого, второго и третьего сумматоров, а выход семнадцатого элемента . 60 задержки через последовательно соединенные восемнадцатый, девятнадцатый и двадцатый элементы задержки подключен ко входу двадцать первого элемента задержки, первый и второй выход третьего регистра в суммирующем блоке подключен ко входу пятого регистра, выход которого и выход четвертого регистра в том же суммирующем блоке подключены ко входам соответствующего второго сумматора, выходы блока постоянной памяти, а также выходы шестнадцатого и двадцать первого элементов задержки являются соответственно первым, вторым, третьим и четвертым выхо" дами преобразователя модулярного кода в двоичный код.

На фиг. 1 представлена структурная схема предлагаемого арифметического устрОйства для процессора быстрого преобразования Фурье; на фиг. 2 и 3 — соответственно структурные схеьы преобразователя двоичного кода в модулярный код и пре-! образователя модулярного кода в

15 двоичный код.

На фиг. 1, 2 и 3 приняты обозна" чения: информационные входы 1, установочный вход 2, тактовый вход 3,,.выход 4 порядка преобразуемых чисел, тактовые входы 5-17, информа:ционные входы 18 поворачивающего ! множителя, тактовый вход 19, уста новочный вход 20, тактовые входы

21 и 22, информационные выходы 23, входные регистры 24-26, предназна:,ченные для хранения мантисс отсче тов входного сигнала, двухразрядные регистр 27 константы сдвига, регистр 28 текущего значения константы сдвига н регистр 29, преобразователь 30 двоичного кода в модулярный код, блоки двухвходовых элементов

И 31, 32, 33 - 45, (»= 1-4 и 46-47 блок 48 постоянной памяти, регист35 ры 49 -57». (i = 1-4) выходные реI гистры 58-61 устройства, предназначенные для хранения мантисс отсчетов.выходного сигнала, сумматор-вы- > читатель 62; по » -му модулю Р» используемой непозиционной системы

4О счисления (» = 1-4), умножитель 63 комплексных чисел в непозиционном коде и преобразователь 64 модулярного кода в двоичный код.

Преобразователь 30 двоичного

45 кода в модулярный код включает блоки

65-67 постоянной памяти для хранения констант в модулярном коде и суммирующие блоки 68.1-68.4 (для суммирования вычетов по модулям система счисления), » -й из которых (i = 1-4) состоит из пяти регистров

69; и двух сумматоров 70 по модулю

P.

Преобразователь 64 модулярного кода в двоичный код включает сумма торы 71.1-.71. 3, 72-75, 76.1 и 76.2 вычетов с весом, блок 77 постоянной памяти, хранящий таблицу старших разрядов двоичного кода, элементы

78, (» = 1-4), 79-81 и 82 (» = 1, 2 и 3 задержки.

Разрядность регистров, номера которых снабжены индексом(» = 1-4), составляет » « 1о Р; бит, где через « X(обозначается наименьшее

5 целое число, не меньшее действи1042028

Таблица 1 бьем памяти Разрядность Число входов Число выходов

2 4 2

Блок, Р

48

2гч.

62„(=1,2,3 и 4) 2

2г

2гч

2г .4

, г . j--5

Qrj чч.{Ь;чз)

+ 3

64+i(i=1 2 и 3) 70j,(i=1,2,3 и 4 ) 2

2г< гj

Z" j ч. 4

71j (i= 1,2 и 3)

76j (i= 1 и 2) r + r4 ч

r/lч г3

72 г,+г.

2/ ч+ ч э

74 г»+ r

2 чч д

73 г+г г4

/ ч ч>4 3 Г4

Г4

r -2r4+ 2

r-2г» + 2

77 г(+ re

Таблица 2

» 1

Входные параметры Адрес Содержимое ячейки ячейки

Стро- Блок, М ка| 9

L х х; х,1<(0.1.2,33

48. max (X Х

4х + х

62; -(i=1,2, 3 4) rj х 2 +у (/x - x/ ., /х + x/2>7

»> 2

+S2+Вч

>/в, 2 P;7, если

f//2> <>, 2>е>и />>>если

8=1

h, Б, В4, hc(o, 1,2|3 ; ЯЕ(0,1 ; в а (0,1,..., 2 >>ч 1

65 тельного числа X. Разрядность входных и выходных регистров устрсфства равна г = ) 1og Рч»»t, Р< » =,Ц Рч, 1=2,3и4, г ° Ц, Все функциональные узлы предлагаемого устройства, за исключением регистров и групп элементов И, 8 реализуются на основе постоянных запоминающих устройств небольшой емкости. В табл. 1 для каждого из функциональных узлов указаны параметры соответствующих постоянных запоминающих устройств, а в табл.2правила формирования содержимого их памяти.

1042028 г

2 г В 2 з /р1), если

b r bbр >

+ S 2. + В S=O; i = 1,2,3,4 (/-В - 2 э /р; f, если

S= 1 ь, s, в не о,1, 2,3 ; se (О,Ц;

В 6 (0 1, ° ° °, 2 -11

66 л. г + (((sе г )/p, j, если

+ 8и2 + В S=O, i = 1,2,3,4; ()(-луг "1/ . 3, если

8=1

67.70( (i l, 2,3э4) /К + т/р.

Х .2 + Y рэ эвв ю юЮюювв

71; (i 1

2,3)

Хэ Тэ

Г

Хе (0913 рч l 4 ар г

Т((оэ1э эР4 -1)

1 72

/Y !К.Р /р, ( Ухи х т

XC(0 э 1 ° е ° ° ° Рве, -1)

le(o,1;., Р,- .-:

X2 э+ т р х, т, X@$0,1„... Р -ф

ТЕ (0,1...,э.Р 1 Ь/Рг л//рэ:+

4, + Р pj т/pi/.73

Х>2 +

/х zip,/ ю ю в ю

° вв юювв ю

X + Y

Xt

Ф " " * -3 г

ТЕ;(0 э1 э ° ° ° ° Рф

10 ю ю

/х +

75, Р4 -1

Рэ 1

Х.2 З+ если

/х + если 76) (i--1 л2) 12 х - х(4 Р

-1 i х 24+.т

-1 ю

-1) Ке2 + (гр э (ао 1 а„-т,4-. ),3 ь s, в, aefO 1

2,2 SS (0, 3Р

Вф0,1,...,2

Хэ Y

Хэ Т6(оэ1 э е ° ° э

Рg - lf

Т

Х©(0,1,..., ХЕ 0,1...,, ююввю ю ю ююю ю ююю ююввююю юююююевЮ х т (э э э {г

Т6(о э 1 °..., Р4 ю ю ю юв ююю юю вию

Хэ Тэ

Xt(0эl ° ° ° е ° Р4

YS(0„l„,, „Р

Ирли.;.в грие табл. 2

РР) т/ . х а t )

Р (т Р®)fz<, (2/ хг (-гх) 1042028

В изобретении используются следующие предположения и обозначения

Модули Р4, Р, Р и Р4 — попарно взаимно просты, причем Р4

2 "4> 2(q + 1), q ) 4 2 — фиксированное натура>льное число;

IXI - наименьший неотрицательный вычет, сравнимый с величиной

X по модулю Р;

LXJ - целая часть действительного числа Х, причем

$x), если О.< XI(X) +

x„

)Х(, если fx)+ — < Х «gXt

Двоичные числа, поступающие на вход предлагаемого арифметического устройства, а также формируемые на, его выходе, принадлежат диапазону (— qP, Р ) и представляются в дополнительном . коде (P = Р< 1 1,:

bp,Ь1, Ь, Ъ -натуральные числа такие, что g b>» =, r Ъо = 1

b > 2; =О (M4 г М,..., М вЂ” множество j состоящее из элементов м4, м м (м; д „К= (м, Mq,..., м>,);

0 1 = (Alp„.

3), где A — некоторое целое число, ! °

P = Р

W = W - 3 W — точное значение

I некоторого поворачивающего множитеJfH

Л Л .Л» W ДУ

»> - gW = — - — — прибли °

qP qP женное значение поворачивающего мно. жителя W, где W = pqPW 1

» (рч»)

>> — произвольный элемент множестаа (W, Символ ()g используется для указания того, что число,заключенное в скобки, является двоичным; (ah а.>...а„ „.,), — дополнительный код целого числа;

А Аоi если 0 A а L2 j о

Аа Р если д сАО < Р по модулю 2 - 2 ., где A

Р 1р

Х6>0,1,..., Р> — 1j; YF(0,1, ° ° °,Р>

- 13 а - )ling Р °

Ь6 = r - d — t, Где t — MRKcHмальное,число следующих подряд друг за другом, начиная.с аб, иуде

ВЫХ цнфр В ЧИСЛЕ (аО а>... а d 4 4 если аб - "0 и максимальное число следующйх подряд друг за другом, начиная с а, единичных цифр в числе (aa a< .. . a < < ), если аа 1;

CR)- содержимое регистра R I,„ I. 1,. It> ")I,,I, ., если 5-0;

1>I ) )Р+IB,. "I> |(в,2"и,; .„ если 5=) 35»(..

1-4.

40 Заметим, что благодаря конвейерной стРуктуре преобразователя 30 сразу после выполнения первого такта описанной процедуры может быть на» чато преобразование нового двоично.45 ro числа; При таком режиме работы рассмотренная операция превращается в однотактную.

П. Преобразователь 64 модулярного кода в двоичный код осуществляет перевод числа A =(» >,>>(д,gq,»(4) < находящегося в регистрах 57.1-57,4, иэ модулярной системы счисления с основаниями Р, PZ, Р, Р4 в двоичную систему счисления, проверяет принадлежность числа А к интервалу

3-2", 2 ) и в случае, когда A P-2", 2 ) определяет минимальное число двоичных разрядов, на которое необходимо сдвинуть вправо число A с тем, чтобы результат сдвига при4>9 надлежал рассматриваемому интервалу.

14

Так как Р4 — — 2, то r4 младших двоичных разрядов дополнительного кода А> числа A ñoâïàäàþò с а 4;.

Поэтому цифраЫ4 через цепочку элеХ-ъН - величина Х пересылается в регистр R.

Арифметическое устройство работает следующим образом.

1. Преобразователь 30 двоичного кода B модулярный код выполняет перевод числа A = (В 2 ") в модулярную систему счисления с.основаниями

Р, Р, Р>, Р4, где В -двоичное

> число, дополнительный код В кото10 рого находится в регистре 26, а

h - содержимое регистра 27.

На первом такте работы преобразователя 30 с выхода регистра 27, первого выхода регистра 26 и (3 + -

15 + 1)-го выхода регистра 26 констан та сдвига h, знак S числа В н со-. держимое BI> -м выходе преобразователя формируется значение 1.-й цифры>».; часла A определяемое соотношением

1042028

l ментов 78,4 задержки, обеспечивающих поточный режим работы, с выхода регистра 57.4 передается на четвертый выход преобразователя (см. фиг. 3). Для получения старших r - r äâoè÷íûõ цифр кода A цифра о „ (» = 1, 2, 3) числа A с выхода регистра 57, подается на первый вход сумматора вычетов с ве сами 71(,, а на второй его вход с выхода регистра 57.4 подается C.I» . . 10

В результате на выходах блоков

71.1, 71.2 .и 71.3 формируется модулярный код(И,g >, ((". числа А,= — (см. 7-ю строку табл. 2)), который 5 передается в элементы 78.1, 78.2 и 78.3 задержки. На этом заканчи- вается первый этап. работы преобразователя.

ПифраiLg(i= 1, 2), пройдя цепоч- ® ку элементов 787 задержки, на пятом модульном такте поступает на первый вход сумматора 76 вычетовф с весами. Параллельно с этим сумматоры 72 и 74 вычетов с весами в течение второго и. третьего модульных

25 тактов определят вычет

+ 3(A, } Р I модулярного кода числа А по осно- . 40

Ванию Р4 (см, 9-ю и 11-ю строки табл. 2),: Г Ъ )

J(A< ),если 7(А ) (У(л, ) -р,есле () и;i(((()

Вычето(. 4, совпадающий с очередными о) двоичными разрядами дополнительного кода A исходного числа А с выхода сумматора 75 вычетов с веса.ми через цепочку элементов 82.3 задержки передается на третий выход преобразователя 64.

На пятом тактЕ работы преобразо" ватель вычет кф с выхода первого элемента 82.3 задержки. подается на второй вход сумматора 76< вычетов с весами, а на первый его вход ,с выхода последнего элемента 78 задержки, как уже отмечалось, посту« пает вычет (= 1, 2). В результате на выходах блоков 76,1 и 76.2 форми- 60 руется модулярный код (р(,, Ы:<) по

c»() о:

ГАД . основаниям Р» и Р числа Аэ = (43 который передается в элементы 82.1 и 82.2 задержки.

Выполняемое устройством четырехтояечное преобразование Фурье опре- деляется следунщими соотношениями

X(O) = х(0) + х(1) + х(2) + х(3):.

X(1) = x(0) - Дх(1) — х(2) +

+ )х(3)

Х(2) = х(0) - х(1) + х(2) — х(3), X(3) = х(0) + Дх(1) — (((2) -Дх(3;

l(, ю.,"Ip,) (7 " " l

Э(А, = ( (р (см. 8-ю и 10-ю строки табл. 2), а сумматоры вычетов с весами 73 и 75 . на третьем и четвертом модульных .тактах опрецеляют цифру „" -il,Ê

r — 2r4 двоичных разрядов дополнительного кода А числа А (см. 13-ю строку табл. 2).

Как и в 1 заметим, что благодаря поточной структуре преобразователя 64 рассмотренная операция преобразования модулярного кода в двоичный код при соответствующем режиме работы устройства является однотактной.

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

DI Устройство реализует дискретное четырехточечное преобразование Фурье последовательности х (n) = х" (и ) + Jx" (n) (n =0,1,2,3) формируемой преобразователем 30 двоичного кода в модулярный код по правилу х((и) = (у (и} 2 ) х" (и) (у" (n) 2 ) где у(и) = у"(и) + Ду (и) (и

0,1,2, 3) - входная последовател) ность арифметического устройства;

2 " масштабный множитель, умножающий выходную последовательность

X(k) = Х (k) + ДХ (k) (k =0 1 2 3) преобразования Фурье на соответствующие поворачивающие множители

Mg.,(k 0+2>

X(k) Ф (k =0,1,2,3 ) из модулярной систеьы счисления в двоичную.

При этом осуществляется контроль выхода элементов этой последовательности из диапазона (-2(; 2 ),как описано в.II

Разделив действительную и мнимую части, получим

Х (0) = х (0) + х»(1} + х (2). +

+ х (3)

Х((1),= х f(0) + х" (1) — х (2) х (3)

X (2) = х (0) - х (1) + х (2) х»(3), Х" (3) .; — x»(0) - х" (1) — х (2) +: + х"(3) 16

1042028

Таблица 3

}i регистра 24

° ° ° ° ° °

25 ... (26

Содержимое у (3) у (1) у -,3) у (1) у (2) у (О) у (2) у (0) Таблица 4

Такт, Входные Величины, опре9 шины деляемые блоком

Пересылки х (0 )(- 4 9 i

Р5

5,8,9 /x (О) - х 4 (2)/Р

/х (О) + х (2)/Р, и X))(0) = х "(3) + х" (1) + x" (2) +

+ x)((3), Х "(1) = х "(О) — х (1) - х "(2) +

+ x((3), Х (2) = х "(О) - xl (1) + х" (2) х )(3), Х (3) = х "(О) + х (1) — х" (2) х) (3).

В начале первого шага, реалиэуе- мого процессором алгоритма и-точечного (п=4 ) быстрого преобразования

Фурье, в регистр 27, а в начале каждого иэ m шагов в регистр 28 через установочные входы устройства

2 и 20 соответственно передаются нулевые значения. Содержимое регистра 28 корректируется блоком 48 постоянной памяти по правилу, укаэанному в 1-й строке табл. 2, после каждого четырехточечного преобразования Фурье, выполняемого арифметическим устройством. По истечеНа первом такте работы устройства величина у)(0) иэ регистра 26 поступает s преобразователь 30 двоичного кода в модулярный код, где, как было описано в I, начинается формирование модулярного кода числа х (0).В то же время содержимое

i-ro входного регистра передается в (i+ 1)-й регистр через второй его вход для всех 1 = 1, 2,... 7.

На втором модулярном такте преобразователем 30 начинается формирование модулярного .кода величины х (2), а содержимое -ro входного регистра передается в (+ 1) -й регистр для всех = 2,...,7. Описанная последовательность действий повторяется до тех пор, пока величина у"(3), находившаяся перед наннн каждого шаца р1-точечного преобразования Фурье блок 48 постоянной памяти выдает новое значение константы сдвига h которая, пройдя через блок элементов И 32, управляемый по шине 21, поступает на первый вход регистра 27. Величина

h иэ регистра 27 может быть передана через блок элементов И 31, управляемый по шине 3, на выходную !

О шину устройства 4. Это производится в момент коррекции процессором быстрого преобразования Фурье. порядка обрабатываеьых чисел.

Мантиссы действительных и мнимых

15 частей отсчетов у(п) (и = Д, 1, 2, и 3 ), входного сигнала арифметического устройства через входные шины устройства 1 поступают соответственно во входные регистры

24-26 устройства s порядке, задаваемым табл. 3. чалом первого такта в регистре 24, не поступит иэ регистра 26 в преобра эователь 3P.. Это происходит на, восьмом модулярном такте.

Начиная с третьего такта, модуляр ные коды чисел x (О), х (2),...x (3) последовательно такт за тактом начинают появляться на выходах йреобразователя .30. В табл. 4 для каждого иэ модульных тактов работы арифметического устройства, имеющих номера 3-20, указаны те из тактовых шин устройства, по которым в

4О данном такте подаются единичные сиг- налы, а также перечень пересылок, обусловленных появлением этих снгналов, и операции, выполняемые модульными сумматорами-вычитателями

45 621 ((= 1-4).

4244> = ))x ((5)! 501, )x((2)) w514

Р Р

/ х " (О ) /Р.-5 4 9 i, /х > (О ) — х < (2 )/Р, 52 з.;

/х5(0) + х((2)(-5 53

F4

1О42О28

17 (49з> = / х «(0)/р -т 50i, /х " (2 /р 51i;

<52i7 >

6, 12

/х ) (1)/ w49i, /х (О) - х (2)/. 521

/х« (О) + х (2)/ . -+53i

Р; (49i) = /х) (1)/р 50i, /х (3)/ -+51i

/х" (1) /р -+74з,(55i) = / х (О) +

+ х (2 /р;- 50i, (53i) = / x «(0) + х "(2)/p," 551, þ

<52i7 >

/хх/(1) + х (3)/р 51i, Ix (1) — х «(3)/р. 52i! »«(0)/рл. - 57 i /х) (2)/р. 561;, (49i) = /х (1)/р 50i)

/х«)(3)/р. --«51i 1

6,7,9 /xl (2)/p (х" (О) + х (2)/р; 50i;

/ x « ) (О ) - х)) (2 )/р-, ъ 5 5 i;.

/х (О) — х (2)/р -53з

/ х (1) - х (3)gp. 541

+ х))(3)/р -л 51 у

- - х (3)/р; P52i

<7,10, t x «(2)/р.

12,14, 17.

/x" (О)/р 571, (54i) = /х (1) (55i) = /х) (0) (52i7 = /х) (1) (531) = / х (0) jx (О)/р, /х (1)/р. 521/ /х (3) /р; - 53Хр

<54i) = /x4«(1) - х« (3)/p„. — л 51Х (55з7 = /xI (О) — х (2)/р. 50i ч

7,9, /х (3)«р.

12

«

/x«(1)/,, (52i) = /х (1)/р, л 54i > (53i7 = /x) (3)/р . 55

/х > (1)/р. -ь53з /x (3)/р — ъ 56 i (55 = !х "(3)/р. - 56 (53i7 = /х ) (1)/рл 55з, (54i> = / х (1)/p, - 53 з

15,16

5,8,9 . /») (0) - »Р(2)/р"

/х)Р(0) + х (2)/р.

5,8,11, /х (1) - х! Э)/р„.

13,17 /х«(1) + х«(3)/р.

8« 11 « )«х (1 ) - «<(3)/р

12,15, / II

8,9, /õ «(1 )/р

14, 17

/» (3)/р; (551

<53 1) (54i7 (52 i7

/ x (1()/х (1) Продолжение табл. 4

/x (2)/р,, - 56 i, х (3))рл 51i;

- хн(2)/р, 50 х "(3)/р 541; х (2 )/р„55з.