Устройство для быстрого преобразования фурье

 

Изобретение относится к вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство содержит вычислительные модули 1, каждый из которых содержит блок синхронизации 2, коммутаторы 3-1-3-К, арифметический блок 4, блоки поС Тоянной памяти 5, блок па-: мяти 6-1-6-К, 7-1-7 К. 1 з.п. ф-лы, 7 ил. (Л оо о 4 О ОО 4

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

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

РЕСПУБЛИН (51)4 С 06 F

gfpgtlypr, -.

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

Н ABT0PCHQMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3946298/24-24 (22) 22,08,85 (46) 15.04.87. Бюл. Ф 14 (72) Г, В. Зайцев и Н. Е. Нагулин (53) 681.32(088.8) (56) Кухарев Г. А. и др, Процессор быстрого преобразования Фурье для обобщенного спектрального анализа сигналов. Л.: Изд-во ЛДНТП, 1982.

Авторское свидетельство СССР

Р 660057, кл, G 06 F 15/332, 1979. (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

„„SU„„1304034 А 1 (57} Изобретение относится к вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье. Цель изобретения— повышение быстродействия, Поставленная цель достигается за счет того, что устройство содержит вычислительные модули 1, каждый из которых содержит блок синхронизации 2, коммутаторы 3-1-3-К, арифметический блок 4, блоки постоянной памяти 5, блок памяти 6-1-6-К, 7-1-7 К. 1 з.п. ф-лы, 7 ил.

1304034

Изобретение относится к вычислительной технике и может быть использовано при построении устройств, реа.лизующих алгоритм быстрого преобразования Фурье (БПФ).

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

На фиг. 1 изображена функциональная схема устройства для быст- 10 рого преобразования Фурье; на фиг, 2 — функциональная схема вычислительного модуля; на фиr, 3 " функциональная схема арифметического блока; на фиг. 4 — функциональная 15 схема блока синхронизации;на фиг. 5— граф алгоритма БПФ с однородной структурой на всех итетрациях; на фиг. 6 — временная диаграмма выполнения базовых операций алгоритма БПФ; 20 на фиг, 7 — временная диаграмма работы блоков памяти.

Устройство {фиг. 1) содержит вычислительйые модули 1.1-1,К, Вычислительный модуль (фиг. 2) со- 25 держит блок 2 синхронизации, коммутаторы 3-1 — З-К, арифметический блок

4, блоки 5 постоянной памяти, блоки

6.1-6.К, 7,1-7К памяти.

Арифметический блок (фиг. 3) со- 30 держит регистры 8- 15, блоки 16-18 перемножения, блоки 19-22 суммирования, блок 23 перемножения, блоки 24-27 суммирования, регистры 28-35.

Блок 2 (фиг, .4) содержит элементы

И 36-1-36-k счетчик 37 адресов весовых коэффициентов, элементы И 38 и

39, элемент HE 40, элементы И 41 †1-41-К, элемент ИЛИ 42, элементы И 43- 1-43-(m-1), элементы И 44-1-44-К, 10 элементы И 45-1-45-К, элементы И 46-1-46-К, дешифратор 47, D-триггер

48, дешифратор 49, D-триггеры 50-1

-50-К, дешифратор 51, элемент НЕ 52, счетчик 53 отсчетов, счетчик 54 ите- 45 раций, сигналы 55-68 на выходах соответствующих блоков, Устройство быстрого преобразования Фурье работает следующим образом. 50

Перед началом вычислений отсчеты входного сигнала (9), 8=1,2,...,N-1, распределены последовательно группами по 11/К отсчетов в блоки 6-1-6-К памяти всех вычислительных модулей 55 так, что в i-M блоке памяти 6-i

j-ro вычислительного модуля 1-i наг ходятся N/К отсчетов входного сигнала с номерами

N . N

= -(— 1) + - (-1) +р, К К

i j=1р;р=L,N/К

Устройство реализует вычисление по алгоритму БПФ основания К с однородной структурой, у которого адресация записи и считывания обрабатываемой информации не зависит от номера итерации (см, на фиг. 5 граф алгоритма БПФ с однородной структурой для N=lá, К=4), Вследствие однородности графа алгоритма БПФ связи между вычислительными блоками остаются фиксированными в процессе вычислений. Если пронумеровать базовые операции у графа алгоритма БПФ сверху вниз (фиг, 5), то j-й вычислительный модуль 1 †{j=1,2, ° ., „...К) будет выполнять базовые опеN

Рации с номеРами (j — 1) -г + i, =1, N/Ê

На первой итерации алгоритма БПФ по управляющему сигналу считывания от блока 2 управления (сигнал 65 на фиг. 7) из блока 6-1-6-К памяти вычислительных модулей считываются операнды на выходн»е шины. В соответствии со связями между вычислительными модулями 1 — 14-1-К, приведенными на фиг. I, на входы j†- го вычислительного модуля 1-j (j =1,2,. ° .,К) при этом по К шинам поступают К операндов из блоков б-j памяти всех К вычислительных модулей, которые далее пропускаются через коммутаторы 3-14-3-К на входы арифметического блока

4 для выполнения базовой операции алгоритма БПФ, Арифметический 5лок 4, реализующий вычисления базовой операции алгоритма БПФ с основанием К, может строиться по любой из известных схем, Вариант построения арифметического блока 4 для К:=4 показан на фиг. 3.

Регистры 8-)5 арифметического блока 4 предназначены для приема и хранения входных операндов, поступающих из блоков памяти дпя выполнения базовых операций алгоритма БПФ. Группы регистров 8-11 и 12-15 находятся в зависимости от номера выполняемой базовой операции поочередно в режимах записи и хранения информации, Так, если для выполнения i-й базовой операции входные операции записываются в регистры 8-11 по управляющему сигналу записи от блока 2 (сигнал 55 на

3 13040 фиг ° 6), то на следующем такте считывания информации из блоков памяти вычислительных модулей группа входных операндов для выполнения (i+1,)-й операции запишется в регистры 12-15

5 (по управляющему сигналу 56 на фиг. 6), а в это время регистры 8-11 используются для формирования результата

i-й базовой операции. Затем для формирования результата (i+1)-й базовой 10 операции используется содержимое регистров 12-15, а очередная группа входных операндов для выполнения (i+2)-й базовой операции записывается в регистры 8-11 и т,д. 15

При выполнении базовой операции алгоритма БПФ умножение входных операндов на весовые коэффициенты вида (22

Ф

Я = ехр (-I — 1), где I = Х-l, производится йа олоках 16-18 перемножения. Соответствующие значения весовых коэффициентов поступают из постоянного запоминающего устройства, Блок 23 перемножения выполняет умножение на фиксированное значение ий

= -I и может быть реализован на н основе коммутаторов и инверторов.

Суммарно-разностные операции выполняются на блоках 19-22, 24-27 сумми- 30 рования.

Результаты базовых операций, формируемые на выходах блоков 24-27 суммирования, записываются поочередно в группы регистров 28 -31 (по управляющему сигналу 58 на фиг. 6) или в группы регистров 32-35 (соответственно по управляющему сигналу 59 на фиг. 6). Если результаты произвольной (i-1)-й базовой операции за- 40 писываются в регистры 28-31, то на следующем такте производится перезапись их содержимого в блоки памяти вычислительного модуля, а в это время результаты следующей i-й базовой 45 операции записываются в регистры 3235, Затем выполняется перезапись в блок памяти содержимого регистров 3235, а в регистры 28-31 записываются результаты (i+1)-й базовой операции 50 и т,д.

При выполнении перезаписи результатов базовых операций в блоки памяти из группы регистров 28-31 или 3235 по одной общей шине (фиг. 3) по- 55 очередно выход одного из регистров переводится иэ третьего состояния на момент записи его содержимого в блоки памяти. На фиг. 6 позициями 60-134 4

-60-4 обозначены управляющие сигналы последовательного перевода из третьего состояния выходов регистров

28-31, а позициями 61-1-61-4 — соответственно управляющие сигналы последовательного перевода из третьего состояния выходов регистров 32-35.

Согласно временной диаграмме выполнения базовых операций алгоритма

БПФ конвейерного режима обработки информации одновременно производится запись входных операндов в регистры 8- 11 или в регистры 12-15 для выполнения произвольной j-й базовой операции, вычисление (j-1)-й базовой операции с последующим запоминанием результатов вычислений в регистрах

28-31 или в регистрах 32-35 и запись в блоки памяти результатов (j 2)-й базовой операции. Поскольку за время выполнения произвольной базовой операции (на фиг. 61 позицией 57 обозначены временные интервалы, затрачиваемые арифметическим блоком 4 на формирование результатов базовой операции) в блоки 7-14-7-К памяти записывается К операндов, а из блоков 6-1-6-К памяти вычислительных модулей 1-1-1 — К считывается для выполнения следующей базовой операции лишь по одному операнду, то, следовательно, темп записи результатов вычислений, поступающих по одной шине в блоки 7-1-7-К памяти в К раз выше, чем темп считывания информации операндов в арифметический блок 4 из блоков 6-1-6 — К памяти. На фиг, 6 позициями 62 и 63 обозначены соответственно частота записи и частота считывания информации из блоков памяти вычислительных модулей. Из-за начальной задержки конвейерной обработки информации, реализуемой в вычислительных модулях, начало записи в блоки памяти результатов вычислений задержано относительно начала считывания в арифметический блок входных операндов на 2Т, где Т вЂ” гериод считывания информации из блоков памяти, что, в свою очередь, эквивалентно задержке 2К периодов записи информации в блоках памяти. По этой причине на фиг. 7 управляющие сигналы записи 66-1-66 в блок памяти 7-1-7-40К=4) сдвинуты на 8 периодов записи относительно управляющего сигнала 65 считывания из блоков 6-1-6-4 памяти. Результаты вычислений первой итерации алгоритма БПФ записываются

5 "13040 2 последовательно по И/К операндов в блоки 7-1-7-К памяти вычислительных блоков, первые N/К операндов записываются в блоки 7-1 памяти, следующие

N/K операндов — блоки 7-2 памяти и

5 т,д. При такой организации записи результатов вычислений в каждом блоке 7-i памяти j-го вычислительного модуля 1-j (i j=1,2...,К} запоминаются операнды, которые, как следует lð из приведенных на фиг. 1 связей между вычислительными модулями, будут использоваться на следующем этапе вычислений в 1-м вычислительном модуле 1- по j-й входной шине, Это позволяет при выполнении следующей итерации алгоритма БПФ реализовать одновременное поступление операндов по всем К входным шинам вычислительных модулей и снизить в К раз темп обмена информацией между вычислительными модулями по сравнению с темпом записи из арифметического блока 4 в блоки памяти, осуществляемой по одной шине внутри вычислительных модулей. 25

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

На второй итерации алгоритма БПФ производится считывания операндов щ из блоков 7-1-7-К памяти вычислительных модулей, а запись результатов вычислений — в блоки 6 — 1 — 6 — К памяти (на фиг, 7 позицией 67 обозначен управляющий сигнал считывания информации из вычислительных модулей 7-1-7-К, а позициями 68-1-68-4 — управляющие сигналы записи информации в блоки 68-1-68 — К памяти для К=4 ° Чередование режимов записи считывания блоков 6-1-6-К,7-1 — 7-К памяти выполняется и на последующих итерациях, Окончательный результат — 11 коэффициентов дискретного преобразования фурье входного сигнала записываются в блоки памяти вычислительных модулей после п/k итераций алгоритма БПФ.

Для выполнения вычислений по алгоритму БПФ в блок 5 постоянной па34 6 мяти каждого вычислительного модуля записывается матрипа весовых коэффи,е р 2Й циентов И, где W = ехр -I --.е) ° При н выполнении любой базовой операции из блока 5 постоянной памяти считывается строка матрицы 4 . Порядок адресов считывания строк матрицы в соответствии с алгоритмом БПФ формируется на выходах элементсв И 36-1-36-k u счетчика 37 адресов весовых коэффициентов. Из алгоритма БПФ основания

К с нормальным порядком входных отсчетов и двоично-инверсным порядком выходных отсчетов следует, что на произвольной i-й итерации базовые операции можно разбить на К групп так, что в каждой из групп базовые операции имеют одни и те же значения весовых множителей, Порядок следования весовых коэффициентов на любой итерации подчиняется правилу двоичной инверсии (см, фиг. 5 для N=16,К=4), Для формирования адресов строк матрицы весовых коэффициентов в соответствии с этим правилом используются сигналы разрядов счетчика 17 и сигналы с выходов элементов И 36-1 — 36-k при-.

1 чем сигнал i-го разряда счетчика 37 адресов весовых коэффициентов (i=1, 2...,,n-2k) используется в качестве (n-k+1-i)-го разряда адреса строки матрицы W, а и качестве j ro разряда адреса строки матрицы Я (j =1,2, ...,k) — сигнал с j-го элемента

В 36-j, Формирование адресов строк матрицы весовых коэффициентов W в зависимости от номера итерации алгоритма

БПФ управляется дешифратором 47, который вырабатывается на своем i-м выходе (i=1,2,,...,н) логический уровень "1" на время прохождения i-й итерации, Из алгоритма БПФ следует, что на (1,2,, ° .,m-1)-й итерации во всех вычислительных модулях одновременно выполняются базовы» операции с одинаковыми весовыми множителями, а на

m-й итерации в вычислительных модулях для выполнения базовых операций используются разные группы весовых множителей, Для реализации считывания íà m-й итерации в вычислительных модулях различных:"рупп весовых коэффициентов, зависящих от номера вычислительного моду.чя, используются элементы И 36-1-36-k, на первые вхо1304034 ды которых подается сигнал с m-го выхода дешифратора 47, а на второй вход i-го элемента И (i=1,2. .,m)

36-i подается (К+1-i)-й разряд двоичного хода, соответствующего номеру вычислительного модуля, Так, первому вычислительному модулю 11-12 соответствует двоичный код 000...00, второму вычислительному модулю 1-2 двоичный код 000...00 и т.д. На m-й 10 итерации сигнал с m-го выхода дешифратора 47 имеет логический уровень

"1", и на выходы элементов И 36-1—

-36-k пропускаются двоичные коды номеров вычислительных модулей. На ос- 15 тальных (1,2...,,m1)-х итерациях с

m-го выхода дешифратора 47 на первые входы элементов И 36-1-36 поступает логический уровень "0", При этом выходы элементов И 36-1-36-k 20 находятся в нулевом состоянии и во всех вычислительных модулях из блоков постоянной памяти считываются одинаковые значения весовых коэффи— циентов. Для считывания в необходи- 25 мом порядке в соответствии с алгоритмом БПФ строк матрицы W используются разряды счетчика 37. Перед началом вычислений каждой итерации алгоритма БПФ счетчик 37 адресов весо- 30 вых коэффициентов устанавливается в

1 нулевое состояние. На 1-й итерации алгоритма БПФ счетчик 37 адресов весовых коэффициентов не изменяет своего состояния, поскольку на его счет- 35 ном входе присутствует логический

"0", При этом для выполнения базовых операций во всех вычислительных модулей используется 1-я строка матрицы весовых коэффициентов W, Во время выпол-40 нения 2-й итерации алгоритма БПФ на счетный вход счетчика адресов весовых коэффициентов 37 через элемент

И 43-1 и элемент ИЛИ 42 пропускается сигнал с (и-2k+1)-го разряда счетчи- 45 ка 53 отсчетов. В результате на 2-й итерации счетчик 37 адресов весовых коэффициентов изменит свое состояние

К раз и сформируется К адресов строк весовых коэффициентов для выполнения 5р

К групп базовых операций.

Аналогично для считывания на i-й итерации (i=2 З,...,m-I) К строк матрицы Г на счетный вход счетчика адресов весовых коэффициентов 37 про- 55 пускается через элемент И (43-i- 1) и элемент ИЛИ 42 сигнала с (n-ik+I )-го разряда счетчика отсчетов.

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

БПФ в арифметическом блоке 4 (фиг. 6) и сигналы управления режимами записи-считывания блоком памяти (фиг. 7).

Считывание информации из блоков

6-1-6-К и 7-1-7-К памяти для выполнения базовых операций осуществляется соответственно по сигналам 65 и 67 (см. фиг ° 7). Поскольку частота считывания операндов в К раз меньше, чем частота записи, то для формирования импульсов записи в блоки памяти используется сигнал с 1-го разряда счетчика 53 отсчетов, а для формирования сигнала считывания — сигнал с (k+1)-го разряда счетчика 53 отсчетов, где k=log,К. При формировании управляющего сигнала считывания из блоков 7-1-7-К памяти сигнал (k+1)-го разряда счетчика 53 отсчетов селектируется на элементе И 38 сигналом

1-ro разряда счетчика 54 итераций, а для считывания из блоков 6-I-6-К памяти соответствующий управляющий сигнал образуется путем селекции на элементе И 39 сигнала (k+1)-ro разряда счетчика 53 отсчетов инверсным сигналом 1-ro разряда счетчика итераций, поступающим с выхода элемента

НЕ 40, Для формирования управляющих импульсов записи в блоки 6-1-6-К памяти входы элементов И 44-1-44-К подаются сигналы соответственно с (1-К)-го выхода дешифратора 49, а также сигнал с выхода 1-ro разряда счетчика 53 отсчетов и сигнал 1-го разряда счетчика 54 итераций. Выходные сигналы дешифратора 49 представляют собой последовательно сдвинутые импульсы 1-ro разряда счетчика отсчетов. Для их формирования на входы дешифратора 49 подаются сигналы (п-2k+ 1) — (n-k) — ro разряда счетчика отсчетов, На выходах элементов И44-1-44-К при этом формируются управляющие сигналы записи (на фиг. 7 для

К=4 — сигналы 66-1-66-4). Сдвиг начала записи в блоки 6- 1-6-K памяти относительно начала считывания информации из блоков 7-1-7-К памяти на задержку конвейера выполняется путем соответствующего сдвига сигналов с

9 13040 выхода дешифратора 49 íà D-триггерах 50-1"".50-К и сигнала 1-ro разряда счетчика итераций на. Ртриггере 48.

При этом в качестве сдвигающих импульсов подаваемых на С-входы DЭ триггеров 48,50-1-50-К, используется сигнал с (k+2)-го разряда счетчика

53 отсчетов, за счет чего обеспечивается задержка на два интервала считывания из блоков памяти. l0

Формирование управляющих импульсов записи в блоки 7-1-7-К памяти осуществляется аналогичным образом на элементах И 45-1-45-К, подаетоя сдинутый на начальную задержку конвейера инвертированный сигнал 1-го разряда счетчика 54 итераций с инверсного выхода D-триггера 48.

В качестве управляющего сигнала записи входных операндов в регистры 20

8-11 и сигнала записи результатов выполнения базовой операции алгоритма БПФ в регистры 28-31 (на фиг, 6 соответственно сигналы 55 и 58) используется сигнал с выхода элемента 25

И 46-К (K=4}„ на вход которого подается сигнал с К-ео выхода дешифратора 51 и проинвертированный сигнал (1:+1) -го разряда счетчика отсчетов, поступающий с выхода элемента 30

НЕ 52, Аналогично в качестве сигна-. лов записи информации в регистры 12-15 и 32-35 (на фиг. 6 соответственно сигналы 56 и 59) используют сигнал с выхода элемента И 41-К, на

I g входы которого подается сигнал с

К-ro выхода дешифратора 51 и непосредственно сигнал с выхода (k+1)-го разряда счетчика 53 отсчетов, Для управления последовательной перезаписью результатов базовой операции из регистров 28-31 блоки памяти (сигналы о0-1-60-4 на фиг. 6 для К--4) используются сигналы с выходов дешифратора 51, которые селек- д5 тируются проинвертированным на элементе HE 52 сигналом (К+1)-го разряда счетчика 53 отсчетов на элементах И 46- -46-К. При формировании управляющих сигналов перезаписи инфор- 50 мации из регистров 32-35 н блоки памяти (соответственно сигналы 6-1-61-4 на фиг, 6) сигналы с выходов дешифратора 51 селектируются сигналом с (k+1)-го разряда счетчика 53 отсче- >5 тов.

Наличие коммутаторов 3-1-3-К (фиг. 2) позволяет выполнять автономно каждому вычислительному модулю 1-i

34 10 (i=1 2.. °,,K) БПФ размером N/К, В режиме автономной работы в каждом вычислительном модупе 1-i (i=1 2, .. °,К) коммутаторы 3-1-3-К пропускают сигналы с выходов внутренних блоков памяти на входы арифметического блока 4, и отсутствует обмен информацией между вычислительными мэдулями 1 — 1-1-К. При этом описанное управление вычислительным процессом, рассчитанное на выполнение всем многопроцессорным устройством БПФ размером N, полностью соответствует выполнению каждым вычислительным модулем в режиме автономной работы БПФ размером М.

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

1. Устройство для быстрого преобразования Фурье, содержащее К-2

E (E — размер преобразования устройства) вычислительных модулей, каждый из которых содержит арифметический блок и четыре блока памяти, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в каждый вычислительный модуль введены К коммутаторов, 2К-4 б.псков памяти, блок синхронизации и блок постоянной памяти, причем информационные входы первой группы i-гэ (i=!,К) коммутатора являются вхоaàìè 1-й группы вычислительного модуля, а выходы группы i-го коммутатора подключены к соответствующим входам i-го операнда арифметического б.пока, управляющие входы коммутаторов объединены и подключены к выходам первой группы блока синхронизации, входы группы весовых коэффициентов арифметического блока подключены к соответствующим выходам группы блэка постоянной памяти„ адресные вхэды группы которого подключены к соответствующим выходам второй группы блока синхронизации, информационные входы группы 2К блоков памяти объединены и подключены к соответствующим информационным выходам группы арифметического блока, информационные выходы группы i-ro u (i+K)-го блоков памяти объединены и подключены к соответствующим информационным входам второй группы i-го коммутатора и являются выходами i-ой группы вычислительного модуля, управляющие входы груп:пы блоков памяти подключены к соответствующим выходам третьей группы блэка синхронизации, входы блоков синхронизации группы

11 13040 всех вычислительных модулей соответственно объединены и являются тактовыми входами группы устройства, выходы U-ой группы V-ro вычислительно го модуля (U,V=I,K) подключены к со5 ответствующим входам V-й группы U-го вычислительного модуля, 2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что блок син- 10 хронизации содержит (4K+m+k+ I ) элементов И, (1с=„1ов К, m=n/k, п=1оя М, N — размер преобразования вычислительного блока, элемент ИЛИ, два элемента НЕ, три дешифратора, К+1+П- 15 триггеров, счетчик отсчетов, счетчик итераций и счетчик адресов весовых коэффициентов, причем 3-й (i=,р, р=1од, т) вход первого дешифратора подключен к выходу 3-го разряда счет- 20 чика итераций, счетный вход которого подключен к выходу переполнения счетчика отсчетов, (S+1)-й выход первого дешифратора (S=l,m-l) подключен к первому входу S-Fo элемента И, вы- 25 ход которого подключен к S-му входу элемента ИЛИ, выход которого подключен к счетному входу счетчика адресов весовых коэффициентов, выходы разрядов которого являются соответ- 30 ствующими выходами первой группы блока, второй вход q-ro элемента И (q=

=I,in-2) подключен к входу (и-(q+1)К+

+1)-го разряда счетчика отсчетов, второй вход (m-1)-го элемента И подключен к входу k-го разряда счетчика отсчетов, первые входы (m+1-1)-х элементов И (1=1,k) объединены и подключены к ш-му выходу первого дешифратора, а выходы (m-I-1)-х элементов 40

И являются соответствующими выходами второй группы блока, второй вход (m+I-1)-го элемента И является так34 12 то вым входом блока, С-входы (К+1 ) Dтриггеров объединены и подключены к выходу (k+2)-ro разряда счетчика отсчетов, (t-A(t=l k) подключен к выходу (n-2k+t)-го разряда счетчика отсчетов, t-й выход второго дешифратора подключен к D-входу t-ro

D-триггера, выход которого подключен к вторым входам (m+k+t-1)-го и (m+K+

+k+t-1)-го элементов И, выходы которых являются соответственно выходами третьей группы блока, а третьи входы (m+k-1)-ro и (m+K+k+t- 1) — ro элементов И подключены к выходу первого разряда счетчика отсчетов, первые входы m+K+t-1 элементов И подключены к выходу (K+1)-ro D-триггера, первые входы (m+K+k+t-1)-х элементов

И подключены к инверсному выходу (К+1)-ro D-триггера, D-вход которого подключен к 1-му разряду счетчика итераций, выходы (m+k+2K) — ro и (m+k+

+2К+1)-го элементов И подключены к (k+1)-му разряду счетчика отсчетов, второй вход (m+k+2K+1)-го элемента

И подключен к выходу первого элемента НЕ, вход которого объединен с вторым входом (m+k+2K)-го элемента И и подключен к выходу первого разряда счетчика итераций, t-й вход третьего дешифратора подключен к выходу t-го разряда счетчика отсчетов, t-й выход третьего дешифратора подключен к вторым входам (m+k+2K+t+1)-го и (m+k+

+3K+t+I)-го элементов И, выходы которых являются выходами третьей группы блока, первые входы (m+k+2K+t+1)-х элементов И подключены к выходу второго элемента НЕ> вход которого объединен с первыми входами (m+k+3K+t+

+1)-х элементов И и подключен к выходу (К+1)-го разряда счетчика отсчетов.

1304034

Фиг 1

0m

0m аигг

1304034!

Р (О

2

4

6

В

17

72

Ц

74

Ьреиенная диаграмма быполнения Запись брегисгпрыЯ-)П)6годнык олерандо6 <-и бтобои олераиии

Sb ! 6ылолнение(-1)-ii базойй олерсч ии з1

JE

Запись 603Уизрегистро6(З2)-(J5) резульяатоб(-2)0 дозобои опероЮ1 +VV юг

ELM

Ю4

$1-1

6 1-2

Ю

6У-4

12 г

70 б

Й

У

Х

73

Л

11

75 оазобых операциц оягоритма БПЖ

Запись 6 регистры(!2)-(15) 8ходных аперандаЦЖ --и базобои опежг ии Вылалненце i-u бтабои операции

Запись 6 039из региппроф28)- (3И уезуяыпатЯИ)-и оозойй операции I

1304034

Составитель А, Баранов

Техред В.Кадар Корректор M. Пожо

Редактор Е, Копча

Заказ 1313/50 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r, Ужгород, ул, Проектная, 4