Арифметическое устройство для процессора быстрого преобразования фурье
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> 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
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 = / х) (О) — х ) (2)/р - 541; (53з) = / х (О) + x ) (2)/р. 55i л 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 = / х" (О) — х) (2)/р -т53i /хх/(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з. 1042028 Продолжение табл. 4 16 20 Цэ табл. 4 и фиг, 1 видно, что модулярный код, сформированный на выходах преобразователя 30, на (2F +1) -м такте через блоки элементов И 33.1-33.4 передается в регист ры 49.1-49.4, а на (2 Г + 2) -м такте через блоки элементов И 34.1-34.4 в регистры 51.1-51.4 для всех Г 1-4. Кроме, того, на (21 + 2) -м такте (Й = 1-4} содержимое регистра 49 пересылается в регистр 50;. ((= 1-4) . В результате на 4, б, 8 и 10-м тактах во входные регистры 50; и 51, сумматора-вычитателя по модулю Р, 62 соответственно подаются 1 -е цифры модулярных кодов пар чисел x I(0), х (2),; х«(0), х I(2); х (1), х (3) и х "(1) х" (3) .(i = 1- 4). На модульных тактах с номерами 4О 5-9 арифметическое устройство выполняет действия, указанные в соответствующих строках табл. 4, и на 10-м такте сумматоры-вычитатели 62..1-62.4 в соответствии с (1) за- 45 вершают вычисление действительных чаотей х (0) и х (2) отсчетов х(0) и х(2) выходного сигнала четырехточечного преобразования Фурье. Модулярный код числа х (2) с пер- 5ð вых выходов сумматоров-вычитателей 62.1-62.4 поступает в регистры 56.1-56.4, а на 11-м модульном такте - в умножитель 63 комплексных чисел, где начииается операция умножения комплексного числа х(2) на .соответствукщий поворачивакщий мно житель. Отсчету х(0) соответствует поворачивающий множитель, равный единице, поэтому модулярный код числа х(0) со вторых выходов сумматоров-вычитателей 62.1-62.4 поступает в регистры 57.1-57,4 через вторые их входы (см. фиг.. 1 и табл. 4) и, начиная с 11-го такта преобразователь 64 начинает выполнение, как это 65 C55i) = (x (1)/р, 56i (5 3 i) / x (1 )/ð; - 5 5 а. (55 i) = j x«(1 )/>, 56 i 1 описано в ll операции перевода числа х (О) из модулярной системя счисления в двоичную. На 11 и 12-м модульных тактах устройство, работая в соответствии с табл. 4 -и формулой (2), находит модулярные коды чисел х (0) и х"(2), которые со второго и первого выходов сумматоров-вычитателей 62 .162.4 поступают соответственно в регистры 57.1-57.4 и 56.1-56.4 ° Модулярные коды пар чисел х"(1),,х" (3) и x (3), х (1). сумматорами-вычитателямн 62.1-62.4 формируются соответственно на 13 и 14-м модульных, тактах. Число х (3) через блоки элементов И 35.1-35.4 передается в регистры 54.1-54.4 через первые их входы на 14-м модульном такте, а числа х" {3), х (1), х <(1) через блоки элементов . И 44.1-44.4 поступают в регистры 56.1-56.4 через вторые их входы соответственно на 16, 18 и 20-м модульных тактах (табл. 4) . На выходах умножителя 63 комплекс ных чисел полученные им произведения появляются в следующем порядке у (2), у" (2), у (3), у (3), у (1), у (1) . В таком же порядке через регистры 57.1-57.4 они поступают в преобразователь 64. Учитывая, что числа х (0) = у (0) и x" (0) у" (0) в преобразователь 64 поступают ранее в соответствии с Д заключаем,g что двоичные коды действительных и мнимых частей отсчетов выходных сигналов предлагаемого арифметического устройства со второго, третьего и четвертого выходов преобразователя 64 поступают в выходной регистр устройства 58 в следука ем порядке: у (0), у" (0), у (2), у«{2) ., у. (3), у" (3), у (1}, у «(1) . Перед записью в регистр 58 F -го из укаэанных чисел (6 = 2, 3. .., 8) парал лельно осуществляются пересылки: 1042028 Таблица 5 ) ")" I ) Содержимое у"(1) у.(1) yt3) у (3) Формируемая преобразователем 64 для каждого входного числа конс-, танта сдвига (см. Jt) с первого вы-хода преобразователя 64 передается в двухраэрядный регистр 29, откуда вместе с содержимым регистра 28 она !5 поступает на адресные входы блока 48 памяти,.;. Большая из входных величин с выхода блока 48 памяти передается в регистр 28 через первый его вход. По окончании текущего шага алгорит- 2p ма М -точечного преобразования Фурье, реализуемого процессором на выходе блока 48 постоянной памяти, получают константу сдвига h, общую для всех входных сигналов арифме. тического устройства, которые обра- батываются на следующем такте алгоритма. Поэтому константа h через блок элементов И 32 передается в регистр 27 через первый его вход для участия в работе на очередном шаге алгоритма И-точечного преобразования Фурье. Действительная и мнимая части выходного сигнала. у.(x) ()а =. 0,1,2,3) в требуемый момент времени через блоки35 элементов И 46-47, управляемые по шине 22, передаются из регистров 58-61 на выходные шины устройства 23.- На этом обработка входного сигнала у(п) (n = 0,1,2,3) sasepuia- 40 ется. Таким образом, производительнесть предлагаемого арифметического устройства в основном зависит от быстродействия и пропускной способности 4 умножителя комплексных чисел. Для определенности предполагают, что используется умножитель, быстродействие которого составляет 10 модульных тактов при пропускной способности - одно умножение комплексных чисел за четыре модульных так» та. Тогда быстродействие устройст-,,ва составляет 35 модульных тактов, 10 двоичного кода в ьюдулярный; имеющих максимально возможную пропускную способность. Кроме того, точность предлагаемого устройства выше, чем у прототипа, так как в первом реализуется адаптивная процедура масшта" бирования чисел, в то время как в другом масштабы выбираются априорно. 58> - 59, (59) °......, (60)- 61. В.результате по окойчанни обработки входных сигналов у (n) (n = 0,1,2,3) »««» 9 регистра 58 59 °,. в регистрах 58-61 выходная информация записывается по правилу, укаэанному в табл. 5. y" (2) у (2) у (o) у (o) 1 а пропускная способность - одно четырехточечное преобразование Фурье, за 13 модульных тактов. Для выполнения Б-точечного преобразования Фурье (N = 4 ) потребуется 13IR 4 тактов, что при N= 1024 и длительности модульного такта 100 нс составляет время 416 мкс, а при N = --1024 и длительности такта 150 нс время выполнения N-точечного преобразования Фурье — 624 мкс.. Для технической реализации предлагаемого арифметического устройства в случае, когда используется модулярная система счисления с основаниями Р = 11, Р2 = 13, Р9 = 15 и Р4 = 16, обеспечивающая возмож-. ность работы с числами, мантиссы которых изменяются в диапазоне f-2 2 }. Кроме умножителя комплексных чисел необходимы 39 постоянных запоминающих устройств емкостью 256 четырехразрядных слов, постоян- ное запоминающее устройство емкостью 256 двухраэрядных слов (табл. 1j, три двухразрядных, 76 четырехразрядных и 16 шестнадцатиразрядных регистров и 326 двухвходовых элементов И. Сравнение Скоростных характерйсг тик предлагаемого устройства и прототипа показывает, что при использовании однотипных умножителей комплексных чисел пропускная способность первого иэ сравниваемых устройств существенно выше за счет использования преобразователей модулярного кода в двоичный код и 1042028 1042028 1042028 Составитель B. Байков Техред у. Тепер Корректор o ° ™гор Редактор М. Келемеш Тираж 706 Подписное ВНИИПИ Государствени62"о комитета СССР по делам иэобретейий и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Закаэ 7129/49 Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4
