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

 

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

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

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

РЕСПУБЛИН (5ц 4 G 06 F 15/332

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ г

Фиг, /

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3959634! 24-24 (22) 01.10.85 (46) 07.03.87. Вюл. Ф 9 (71) Физико-механический институт им. Г.В.Карпенко (72) Л.В.Вариченко, M.ß.Äåäèøèí, М.А.Раков и Г.С.Сварчевский (53) 681.32(088.8) (56) Авторское свидетельство СССР

Р 800995, кл. G 06 Г 15/332, 1980.

Патент Франции Р 2384303, кл. G 06 Р 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА И СВЕРТКИ

Л0 1295415 А 1 (57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов. Цель изобретения — .повьппение быстродействия. Поставленная цель достигается за счет того, что устройство для вычисления преобразования Фурье-Галуа и свертки содержит вычислительный блок 1, блок 2 умножения, вычислительный блок 3, блок накапливающих сумматоров 4, блок 5 памяти и блок.6 управления. 18 ил.

1295415 2

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

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

На фиг. 1 представлена функциональ- 10 ная схема устройства для вычисления преобразования Фурье-Галуа (ПФГ) и свертки; на фиг. 2 — схема вычислительного блока; на фиг.3 — схема узла накапливающих сумматоров по модулю М; на фиг.4 — схема блока умножения," на фиг.5 — схема блока соединений; на фиг. 6 — схема блока памяти; на фиг. 7— схема блока накапливающих сумматоров; на фиг.8 — функциональная схема блока управления; на фиг.9 — схема узла выбора режима; на фиг.10 — схема синхронизатора вычислительного блока; на фиг.11 — схема синхронизатора

25 умножителей; на фиг.12 — схема узла памяти адресов; на фиг.13 — схема синхронизатора накапливающих сумматоров; на фиг.14 — общая временная диаграмма работы устройства для вычисления ПФГ и свертки; на фиг.15 — 17—

Временнме диаграммы работы блоков устройства для вычисления ПФГ и свертки соответственно на первом и втором, третьем и четвертом, пятом и шестом этапах работы устройства; на фиг.18 — схемы умножителей на степе-, и ни двойки по модулю M = 2 — 1 в случае Р = 7.

Функциональная схема устройства 40 для вычисления ПФГ и свертки (фиг. 1) содержат вычислительный блок 1 ПФГ, блок 2 умножения, вычислительный блок 3, блок 4 накапливающих сумматоров, блок 5 памяти, блок б управле- 45 ния, информационные входы 7 и 8, вход 9 управления, информационный выход 10 устройства.

Вычислительный блок (фиг.2) содержит группу из F Р-разрядных вход- 50 йых регистров 11, узел 12 накапливающих сумматоров по модулю М, группу из P Р-разрядных выходных регистров

13, информационные выходы 14, входы управления 15 — 18. 55

Узел накапливающих сумматоров по модулю М (фиг.3) содержит группу из

Р P-разрядных регистров 19 промежуточной памяти, группу из Р Р-разряд-, ных сумматоров 20, группу из Р умножителей 21 на степени двойки, информационные входы 22, выходы 23, входы 24 и 25 управления.

Схема блока умножения (фиг.4) содэржит информационные входы 26 блока, группу из P P — разрядных входных регистров 27, узел 28 накапливающих сумматоров по модулю M (выполненный по схеме блока накапливающих сумматоров по модулю М, содержацимися в блоке 1 ПФГ), узел 29 соединений, группу из P P-разрядных выходных регистров 30, выход 31 блока умножения, Р управляющих входов 32, управляющие входы 33 — 37.

Блок соединений (фиг.5) содержит

Р P-разрядных информационных входов

38 и Р Р-разрядных выходов 39, причем младшие разряды первого, второго,..., Р-го входов 38 соединены соответственно с первым, вторым,..., Р-м разрядом первого выхода 39, вторые разряды первого, второго,..., Р-ro входов 38 и соединены соответственно с первым, вторым,..., P — м разрядом второго выхода 39, аналогично старшие (P-е) разряды первогО, Второго, ° ° ° у Р-гО ВХОДОВ 38 соединены соответственно с первым, вторым,..., Р-м разрядом P-го входа 39.

Блок памяти (фиг.б) содержит группу из P P-разрядных регистров 40, выходы 32, Р управляющих входов 41, управляющий:вход 42, Блок накапливающих сумматоров (фиг.?) содержит информационные входы 43,группу из Р 3 Р-разрядных входных сдвиговых регистров 44, группу из Р 3 P-разрядных регистров 45 промежуточной памяти, группу из P 3 Pразрядных сумматоров 46, выходы 47, управляющие входы 48 - 52.

Блок управления (фиг.8) содержит входы 9 управления, узел 53 выбора режима, выходы 54 — 59, элементы ИЛИ

60 — 62, входы 63 — 65, синхронизатор

66 вычислительного блока, узел 67 памяти адресов, синхронизатор 68 умножителей, синхронизатор 69 вычислительного блока, синхронизатор 70 накапливающих сумматоров, выходы 71-74.

Узел выбора режима (фиг.9) содержит RS-триггеры 75, элемент НЕ 76, элементы ИЛИ 7?, элемент И 78, шестиразрядный сдвиговый регистр 79 (Р +

+ 1)-разрядный сдвиговый регистр 80, группу (из шести двухвходовых) элементов И 81.

2, 2, 2 ...,,2 о р-1 1

2,2,2,...,2 х(0), X(0) х(1), X(1)

Х(2)

) 25

Ф Р-П Р-4 2

2,2,2,...,2 х(2) у(п) = h(n) W x(n) 5) О 1 2 P2, 2, 2,...,2

Х(Р-1

Х(Р-1

x(0) X(0) 2 Р-1

2,...,2

2, 2 х(1) Х(1) 2, 2 х(2) Х(2) Nh (6) х(Р-1) X(P-1?

3 12954

Синхронизатор вычислительного блока (фиг.10) содержит (P + 1)-разрядный сдвиговый регистр 82., RS-триггеры 83, элемент НЕ 84, элементы И 85.

Синхронизатор умножителей (фиг.11) содержит (P + 1)-разрядный сдвиговый регистр 86, RS-триггеры 87, элемент

НЕ 88, элементы И 89, элемент ИЛИ 90.

Узел 67 памяти адресов (фиг.12) содержит RS-триггеры 91, элементы 1О

НЕ 92., P-разрядный сдвиговый регистр

93, элементы И 94,(Р + 1)-разрядный сдвиговый регистр 95, P элементов

ИЛИ 96.

Синхронизатор накапливающих сум- 15 маторов (фиг.13) содержит RS-триггеры 97, элементы И 98, элемент 99 задержки и элементы ИПИ 100.

Конечная цифровая свертка представляет собой числовую процедуру, 20 определяемую следующим образом: й-1

y(n) = h(n-m) x(m), и = 0,1,2,.. ° (1)

))ФО и символически обозначается как где x(n) п(п) и y(n) — последовательности 30 чисел.

Вычисление свертки можно проводить с помощью прямого и обратного преобразований Фурье-Галуа (ППФГ и ОПФГ):

35 у(п) = ППФГ (ПФГ (п).ПФГ (х)), (2) где ПНФГ н ОПФГ. вычисляются по .формулам йt, 40

ППФГ (х ) = X(k) = Q x (n) „(и), ФО

k=0, N 1; (3), 1п 1

ОПФГ t x g =,-x(n) = N QX(k)< < (n) Ф

КпО

n = -1, (4) 15 4 где х(п) — цифровой сигнал заданный на интервале N т.е. в точках 0,1,...,N — i и принимающий значения в множестве (0,1,...,N — 1j

X(k) — спектр Фурье-Галуа сигнала;

X (n) — элемент матрицы ПФГ, который находится на пересечении k-й строки и n-ro столбца этой матрицы.

Операции в выражениях (3) и (4) выполняются по модулю М, где М вЂ” порядок поля Галуса GF(M), на которым определяются ПФГ. Если в качестве первообразного корня из единицы N-й степени "))1 E. GF(M), принадлежащего полю Галуа, выбрать 2, то выражение (3) записывается в матричном виде р (M = 2 — 1, где M - число простое) В случае N = P. Обратное преобразование вычисляется по выражению, аналогичному выражению (5), с той лишь разницей, что матрица X „ (n) заменяется матрицей (.„ (и), учитывается нормирующий множитель и векторстолбцы Х(п) и X(k) меняются местами, т.е. вычисление ОПФГ проводится по тому же алгоритму, чуо и вычисление прямого преобразования:

5 l2954i5 6

При вычислении ППФГ после пере столбец х(п) выражение (5) записымножения матрицы Х,„, (n) на векторвается

2 х(0) + 2 х(1) + 2 x(2P + ... + 2 х(Р-1)

2 х(0) +2 х(1) + 2 х(2)+ ... + 2 х(Р-1)

2 х(0) +2 . х(1) + 2 х(2)+ ... + 2 х(Р-1) X(0) Х(1) (7) Х(2) 2 х(0) + 2 х(1) + 2 х(2) + ... + 2 х(Р-1) Х(Р-1).

2 (х(Р-1)+2 (х(Р-2)+2 (х(Р-3)+...+2 (х(1)+2 (х(0))))...) 2 (х(Р-1)+2 (х(Р-2)+ 2 (х(Р-3)+...+2 (х(1)+2 х(0)))...) 2 (х(Р-1)+2 (x(P-2)+2 (x(P-3)+...+2 (х(1)+2 х(0)))...) 2 (х(Р-1)+2 (х(Р-2)+2 (х(Р-3)+...+2 (x(1)*2 х(0)))...) ю P-2 у=ХН=X.(h> 2 +h,,г +

+e ° ° + hq2 + hî 2 ) = Xh>12 +

Р-Я

+Х h „2 +...+ Х h, 2 +

В матрице-столбце (8), полученной из матрицы (7), слагаемые каждого спектрального коэффициента X(k) перегруппированы так, что структура выражений для каждого X(k) получена одинаковой, причем умножение в выражениях (8) для каждого ХЦс) производится на один и тот же мно- ц житель, равный двойке в степени, соответствующей номеру k спектрального коэффициента X(k) .

Вычисление Х() состоит в умножении первого отсчета входной последовательности х(0) на 2, суммировании полученного результата со следующим (вторым) отсчетом входной последова" тельности х(1) и умножении полученной суммы на 2 ; суммировании резуль" 50 тата последнего умножения со следующим (третьим) отсчетом входной последовательности х(2) и умножении к, полученной суммы на 2 ;...; суммировании результата последнего умно- 55 жения с последним P-м отсчетом входной последовательности х(Р-1) и умнок жении полученной суммы на 2 (выражение (8), 0 % k P-1). Поэтому в алгоритме вычисления Х(1,) можно выделить цикл, состоящий в суммировании результата предыдущего цикла со значением слецующего отсчета входной последовательности и умножении полуК чейной суммы на 2 . Цикл для первого отсчета входной последовательности х(0) может быть представлен суммированием нуля с первым отсчетом входной последовательности х(0) и умножением полученной суммы, т.е. первого отсчета,на 2". Таким образом алгоритм вычисления X(k) состоит в последовательном выполнении P циклов.

При вычислении свертки двух последовательностей выполняется операция поточечного перемножения значений спектральных коэффициентов этих последовательностей. Операция умножения двух P-разрядных чисел Х и Н может быть записана как

1295415

Х Ьо 2 = 2 (Х h

P-!

+2 1(Х Ь + 2 (Х Ьрз+ °

+2 (X h +2 (Х h + О)))

P-1 Р-1

Р-f

Н = 1,. 2 °

i--о

° ° +

Полученное выр аже ние (9) соотв етствует структуре выражения (8) для вычисления P-ro спектрального коэф-. фициента Х(Р-1), в котором входные отсчеты представляют последовательность из одинаковых чисел Х (первый сомножитель), каждое из которых ум- 15 ножается на значение соответственно первого h, второго h;,...,P-го

hp», разряда второго сомножителя Н (при умножении входного отсчета (первого сомножителя Х) на значение ло- 20 гической единицы входной отсчет остается неизменным, при умножении на значение логического нуля — входной отсчет становится нулевым). Поэтому вычисление значений спектральных коэффициентов и умножение двух чисел можно производить по одним и тем же алгоритмам.

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

+ х (п)»h„(n)) 2 +

+ х (и)«. h (n).

Устройство производит свертку двух числовых последовательностей (по Р отсчетов, каждый отсчет представляет собой целое число, не превышающее М = 2 — 1, т.е. представ2Р ляемое в двоичной системе счисления

2Р-разрядным двоичным числом). С целью сокращения длины разрядной сетки в устройстве применяется разбиение входных 2Р-разрядных слов на части, состоящие из двух P-разрядных слов (в соответствии с выражением (10)). При этом выходная свертка onх(п)=х;(и) 2 +х. (и); 1х (п)1(2

2 35

h(n)=h (n) 2 +h (n); (h (n) 2 ; (10)

Свертка в этом случае определяется следующим образом:

y(n) = x(n) » h(n) = (x:(n) + Ь (п))х

Q.Р

Ф2 + („(п)»- ?} (n) .+ (11) ределяется как сумма четырех частичнык сверток согласно равенству (11).

Р результате можно избежать применения псевдопреобразования Мерсенна и, следовательно, упростить устройство, а с другой стороны добиться сокращения разрядной сетки в 2 раза как и при использовании этого преобразования.

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

= x(n) » h(n) вычисляются в следующей последовательности (слева направо):

y(n) = (х,(n) » h (n)) ° 2 +

+ (х„(n)» h„(n))- 2 + (12)

+ (х (n) «h (n)) 2 +

+ (х2 (n)» h, (n)) 2

Кроме того, ПФГ выполняется только для первой входной последовательности x(n),a значение спектральных коэффициентов второй входной последовательности H(k), умноженные на нормирующий множитель N, ñðàçó заносится с управляющей ЭВМ в блок памяти устройства. Это обусловлено тем, что при выполнении большинства задач цифровой обработки сигналов изменяется только первая входная последовательность, а вторая входная последовательность при выполнении конкретной задачи цифровой обработки сигналов остается неизменной и представляет собой импульсную реакцию.

При изменении задачи обработки в блок памяти устройства вводятся новые значения спектральных коэффициЭ ентов.

Устройство работает следующим образом (фиг. 1) .

Входные данные, представляющие собой отсчеты первой входной последовательности x(n), где 0 с и < P-1, подаются по входной шине 7 на вход блока 1. Причем числовая последовательность подается двумя частями

x „(n) и х (и) (х,(n), х (n) — числовые последовательности йз P Р-разрядных отсчетов соответственно Рстарших и P-младших разрядов P вход ных 2Р-разрядных отсчетов x(n)). От9 12954 счеты числовых последовательностей

x„(n) и х (n) поступают на вход блока 1 последовательно во времени, причем подача последовательностей х,(n) или х (n) начинается по управляющему сигналу с блока 6 управления, Отсчеты второй входной последовательности H(k) подаются по входной шине 8 на вход блока 5 памяти ,также последовательно во времени. 1О

Управляющая 3ВМ связана с блоком б управления с помощью шины 9. Управляющая ЗВМ обеспечивает подачу первой и второй входной последовательности соответственно по шине 7 и шине 8, а также управление устройством в целом. Для синхронизации работы всех блоков устройства и выработки управляющих сигналов на вход блока 6 управления по шине 9 подаются сигналы начальной установки, пуска и тактовой частоты. Процесс вычисления свертки делится на шесть этапов (фиг.14 — 17), в пределах каждого из которых работают те или иные бло25 ки устройства в соответствии с управляющими сигналами, поступающими с блока 6 управления.

Устройство начинает работать пос- 30 ле поступления на входы 9, и 9 блока 6 управления (фиг.8) импульса начальной установки и запускающего импульса от управляющей ЭВМ, которые устанавливают все блоки устройства в начальное состояние и запускают блок 6 управления. При этом на первом этапе работают блок 1 и блок 5 памяти, а на, их входы по шинам 7 и

8 соответствено поступают отсчеты 4Q первой части первой входной последовательности х,(п) и отсчеты второй входной последовательности H(k).

Блок 1 производит ППФГ входной последовательности х,(n). После завершения первого этапа работы на выходе блока 1 ПФГ появляются значения спектральных коэффициентов X r„(k) входной последовательности х „(и).

В блок 5 памяти на первом этапе ра- gg боты устройства записываются 2Р-разрядные значения отсчетов второй входной последовательности H(k).

На втором этапе работают блок 5 памяти и блок 2 умножения. Входные данные в блок 2 умножения поступают с блока 1 (X„{k)) и с блока 5 памяти. Причем с последнего поступают отсчеты второй части Н (k) второй

15 10 входной последовательности H(k), которые являются последовательностью из Р Р-разрядных отсчетов (Р разрядов младшей группы 2Р-разрядных значений спектральных коэффициентов H(k))„ Блок 2 умножения производит по гочечное умножение значений спектральных коэффициентов двух последовательностей Х,(k) и . Н (k) . !

На третьем этапе работают блок

1, блок 5 памяти, блок 2 умножения, блок 3 и блок 4 накапливающих сумматоров. На вход блока 1 поступают отсчеты второй части первой входной последовательности х (n). С выхода блока 5 памяти на первый вход блока

2 умножения поступают отсчеты первой части второй входной последовательности Н,(k). На второй вход блока

2 умножения подаются вычисленные в блоке 1 на первом этапе отсчеты спектральных коэффициентов Х (1с) первой части первой входной последовательности х (n). На вход блока

3 подаются отсчеты последовательности перемноженных спектральных коэффициентов Х1„(К) Н () с выхода блока 2 умножения. Блок 1 производит ППФГ входной последовательности х (n). Блок 2 умножения производит поточечное умножение значений спектральных коэффициентов двух последовательностей Х,(k) и H„ (k) . Блок

3 производит ОПФГ последовательности Х „(k)" Н (k), поступающей на его вход. Р. конце третьего этапа работы на выходе блока 1 ПФГ появляются вычисленные значения спектральных коэффициентов Х,(), в блоке 2 умножения записываются значения отсчетов последовательности перемноженных спектральных коэффициентов

Х,(k) Н,(k), на выходе блока 3 появляются вычисленные значения свертки х,{п) -ъ Ь (п),которые записываются в блок 4 накапливающих сумматоров. С помощью последнего производится умножение частичных значений

2Р Р о сверток на множители 2, 2 и 2 и суммирование результатов умножения в соответствии с выражением (12).

На четвертом этапе работают блок

5 памяти, блок 2 умножения, блок 3 и блок 4 накапливающих сумматоров.

С выхода блока 5 памяти на первый вход блока 2 умножения поступают отсчеты второй части второй входной

11 12954 последовательности H (k). На другой вход блока 2 умножения подаются вычисленные с помощью блока 1 на третьем этапе отсчеты спектральных коэффициентов Х (k) второй части первой входной последовательности х (и).

На вход блока 3 подаются отсчеты последовательности перемноженных спектральных коэффициентов Х,(k) H„(k), вычисленные на третьем этапе с помо- 10 щью блока 2 умножения. Последний производит поточечное умножение значений спектральных коэффициентов двух последовательностей Х (k) и

Н (k). Блок 3 производит ОПФГ последовательности X „(k) . H„ (k), поступающей на его вход. Блок 4 накапливающих сумматоров производит умножение вычисленных на третьем этапе значений свертки x (n) » h (и) на р

1 2 множитель 2 . В конце четвертого этапа работы в блоке 2 умножения за1писываются значения отсчетов последовательности перемноженных спектральных коэффициентов Х (1 ) " H2(k) на выходе блока 3 появляются вычисленные значения свертки х,(n) + h„(n), которые записываются в блок 4 накапливающих сумматоров.

На пятом этапе работают блок 5 памяти, блок 2 умножения, блок 3 и блок

4 накапливающих сумматоров. С выхода блока 5 памяти на первый вход блока умножения 2 поступают отсчеты первой 35 части второй входной последовательности Н,(k). На другой вход блока 2 умножения подаются вычисленные с помощью блока 1 на третьем этапе отсчеты спектральных коэффициентов Х (k), 40 второй части первой входной последовательности х (n). На вход блока 3 подаются отсчеты последовательности перемноженных спектральных коэффициентов X (k) ° H (k),âû÷èñëåííûå на 45 четвертом этапе в блоке 2 умножения.

Последний производит поточечное умножение значении спектральных коэффициентов двух последовательностей

Xg(k) Н .(k). Блок 3 производит ОПФГ 50 последовательности Х (k) H (k).

Блок 4 накапливающих сумматоров производит умножение вычисленных на четвертом этапе значений свертки

2Р х (а).» h, (n) на множитель 2 и сум- 55 мирование с предыдущим значением свертки т.e. (x,(n) + h (и)) 2

+ (х,(п) + h,(n)) 2 ). В конце пято"п этапа работы в блоке 2 умножения

15 12 записываются значения отсчетов перемноженных спектральных коэффициентов

Н,(k) -Х (k),.на выходе блока 3 появляются вычисленные значения свертки х (n) + h (n) которые записываются в блок 4 накапливающих сумматоров.

На шестом этапе работают блок 3 и блок 4 накапливающих сумматоров.

На вход блока 3 подаются отсчеты последовательности перемноженных спектральных коэффициентов X (k) H,(k)

Блок 4 накапливающих сумматоров производит умножение вычисленных на пятом этапе значений свертки х (n) ?j(n, на множитель 2 и суммированйе с предыдущими значениями свертки, т.е. (х,(n) h (и)) ° 2 + (х, (n) a h,(n)) 2

+ (х (n) м h (n) ) 2 . В конце шестого этапа работы на выходе блока 3 появляются вычисленные значения свертки х (n)» h, (n), которые записываются в блок 4 накапливающих сумматоров, умножаются с помощью этого блока на

P множитель 2 и суммируются с предыдущими значениями свертки, т.е. на выходе блока 4 накапливающих суммато1ров появляются значения отсчетов вы,ходной свертки, соответствующей вы,ражению (12). После завершения шестого этапа работы устройство готово к обработке следующей последовательности входных данных.

Блок 1 работает следующим образом.

Входные данные, представляющие собой отсчеты числовой последовательности х,(n) или х (n) (Р отсчетов по Р разрядов каждый), подаются по шине 7 последовательного ввода на входы регистров 11, — 11р группы входных регистров 11 (фиг.2, 15).

Вход 15 объединяет входы тактовой частоты входных регистров 11„, — 11.р (P регистров представляют собой группу Р-разрядных регистров хранения данных с записью по переднему фронту импульса). В момент йоступления первого отсчета входной последовательности (например, х„(0)) х,(n) на вход 15 с блока б управления поступает первый импульс тактовой частоты. С постунлением этого импульса первый отсчет записываеч ся во все входные регистры 11 и с их выходов поступает на вторые входы (входы В) сумматоров 20 блока 12 накапливающих сумматоров по модулю

И (фиг.3). Импульсом, поступающим

13 12954 на вход 17 (вход 25 на фиг.3) синхронно с первым импульсом тактовой частоты, производится обнуление ре-. гистров 19 промежуточной памяти бло— ка 12 накапливающих сумматоров по модулю М. На вход 16 (вход 24,фиг.З) объединяющий входы тактовой частоты регистров 19 промежуточной памяти, поступают импульсы тактовой частоты, сдвинутые во времени на полови- 10 ну периода тактовых импульсов. До момента поступления первого импульса тактовой частоты на вход 16 значение первого отсчета х (0) входной последовательности, поданное на вторые входы сумматоров 20, суммируется с данными, поступившими на первые входы (входы А) сумматоров 20 с выходов регистров 19 промежуточной памяти (нулевые значения), и полученная сумма поступает на входы умножителей 21 на степени двойки. Первый умножитель 21 на степени двой 1 о ки производит умножение на 2, второй умножитель 21 — на 2,...,Р-й

25 умножитель 21 — на 2 .

Полученные в результате умножения произведения х;,(О) 2 (где Š— номер вычисляемого спектрального коэффициента Х „(k), 0 k « P-1) поступают на входы регистров 19 промежуточ- ной памяти и с приходом первого импульса тактовой частоты, поступающего на вход 16, записываются в эти регистры промежуточной памяти. One- 35 рация суммирования выполняется по модулю М = 2 — 1, что реализуется г путем суммирования возможного переноса в (Р + 1)-й разряд с младшим разрядом в каждом сумматоре 20. Для

40 этого выход переноса сумматора 20 соединен. с его же входом переноса.

Операция умножения на степени двойки. реализуемая умножителями 21- — 21

P на степени двойки, произволится по модулю целого числа М = 2 — 1, где.

P — - простое число. Поэтому умножения на степени двойки представляют собой циклические сдвиги кодового слова.

Реализовать умножение на степени двойки по модулю M = 2 — 1 можно

Р простой коммутацией проводов. Симво" лически операция умножения на степени цвойки изображена в виде P блоков 21 (для случая Р 7 реализация этих блоков показана на фиг.18).

В момент поступления второго отсчета входных данных на вход 15 по"

15 14 ступает второй импульс тактовой частоты и второй отсчет входной последовательности х (1) записывается во все входные регистры 11 и с их выходов поступает на вторые входы сумматоров 20. На выходах последних формируются суммы поступивших на вторые входы (входы В) данных с входных регистров 11 (х1(1)) и данных, поступивших с выходов регистров 12 промежуточной памяти, записанных в них на к предыдущем цикле (х „(О) ° 2 ), т.е. формируется сумма х;(1) + х„(0) 2

Значения суммы с выходов сумматоров

20 поступают на блоки 21 умножителей на степени двойки и с их выходов подаются на входы регистров 19 про-— межуточной памяти. Второй импульс, поступающий на вход 16, разрешает запись в регистры 19 данных, поданных на их входы, т.е.

2 (х,(1) + 2 х (01).

В момент поступления третьего от— счета входных данных х, (2) цикл работы блока 1 повторяется и в регистры 19 записываются накопленные за три цикла в каждом сумматоре 20 значения частичных сумм соответствующих спектральных коэффициентов. Такой процесс повторяется Р раэ. На Р-и цикле в момент поступления P-ro отсчета входных данных ыа вход 15 поступает

Р-й имцульс тактовой частоты и P-й отсчет входной последовательности х (Р-1) записывается во все входные регистры 11 и с. их выходов поступают на вгорые входы сумматоров 20. На выходах последних формируются суммы ,поступивших на вторые входы (входы В) анных с выходов входных регистров 11

1 (P-1) и данных, поступивших с выхоцов регистров 19 промежуточной памяти, записанных в них на предыдущем цикле: (2 (х (Р-2) + 2"(х,(Р-З) +

+ + 2ê"((1) + 2кх,(0)))...) ..

Суммы х„(Р-1) + 2 (х (Р-2) +

+ 2 "(х, (Р-3)+...+ 2" (х„(1) +

+ 2 х,(0)))...), 0 «k «Р-1 с выходов сумматоров 20 поступают на блоки 21 умножителей на степени двойки и с выходов этих блоков подаются на входы регистров 19 промежуточной памяти. Р-й импульс, поступающий на вход 16, разрешает запись в регистры 19 данных, поступивших на. их входы в соответствии с выражением

12954 15

1б (13) 25

2 (х, (Р-1) + 2" (х, (Р-2) +

+ 2 (х (Р-3)+... +

+ 2" (х,(1) + 2 х,(0))) ° ..).

Это выражение полностью совпадает с выражением (8) для спектральных коэффициентов, в котором каждому спектральному коэффициенту Х,(1 )

10 соответствует выражение (13) (О c k P-1) . Значения P спектральных коэффициентов Х,(k) с выходов регистров 19 поступают на входы выходных регистров 13 блока 1 ПФГ и при поступлении на вход 18 разрешающего импульса, совпадающего по времени с (Р+1)-м импульсом тактовой частоты (фиг. 15), записываются в регистры 13. Таким образом в конце действия (Р+1)-ro импульса тактовой частоты блок 1 заканчивает вычисление ПФГ, а на Р Р-разрядных выходах блока 1 появляются значения спектральных коэффициентов X Ä(k) и блок

1 готов к обработке следующей последовательности входных данных.

Блок 3 устройства производит ОПФГ последовательности значений спектральных коэффициентов, например, Х, (k) Н,(k) .

Номирующий множитель N, который вводится при вычислении ОПФГ по равенству (4), учитывается в последовательности H(k), отсчеты кото35 рой поступают с управляющей ЭВМ уже умноженные на И ". Замена (5) матрицы степеней двоек,К (и) на матк

Рину (6) X„ (n), которая отличается только расположением строк, учитывается в блоке 3 путем перестановки умножителей 21„ — 21 на степени двойки в соответствии с перестановкой строк матрицы X„ (n)

При этом сохраняется порядок йомеров выходов блока 3 и, фактически, "он ничем не отличается от блока 1.

Схема блока 3 совпадает со схемой блока 1 (фиг.2 и 3) с той лишь разницей, что умножители 21, — 21 на степени двойки построены следующим образом: умножитель 21„ осуществляет умножение на 2, умножитель 21 — на 2, умножитель 21 — на 2 умножитель 21 — на 2 з,..., умноД житель 21р — на 2 . Временная диаграмма работы блока 3 приведена на фиг.16 и 17 (в блоке 3 с целью удобства описания устройства номера управляющих выводов даются в скобках).

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

Входные данные, представляющие собой отсчеты двух числовых последовательностей X (k) или Х <(k) первых сомножителей и H, (k) или Н (k) вторых сомножителей, например X„ (k) и

Н (k), подаются соответственно на входы 26 входных регистров 27 и входы

32 установки логического нуля этих же входных регистров. Причем значения первого, второго,..., P-ro спектральных коэффициентов первых сомножителей X,(k) или Х (k) поступают в параллельном коде соответственно на P — разрядные входы 26 первого, второго, ..., Р-го входных P-разрядных регистров 27, а значения,первого, второго,..., P-го спектральных коэффициентов вторых сомножителей Н,(k) или Н (k) поступают в последовательном коде (поразрядно,начиная с младших разрядов) на одноразрядные входы 32 установки логического нуля соответственно первого

32,, второго — 32,..., P-ro — 32 р входных регистров 27. Импульсы тактовой частоты с блока 6 управления поступают на вход 33 блока 2 умножения. Вход 33 объединяет входы тактовой частоты группы входных регистров 27. С поступлением первого импульса тактовой частоты значения первых сомножителей (например,Х (k)) записываются во входные регистры 27 и с их выходов поступают на вторые входы сумматоров 20 блока 28 накапливающих сумматоров по модулю И (фиг. 3), Первым импульсом тактовой .частоты, поступающим на вход 35, производится также обнуление регистров 19 промежуточной памяти блока 28 накапливающих сумматоров по модулю M (номера управляющих входов 34 и 35 блока 28, используемого в блоке 2 умножения, указаны в скобках,фиг.3).

Такая нумерация введена для удобства описания блока 6 управления.,3 это же время на входы 32 установки ! логического нуля входных регистров

27 поступают значения первых (младших) разрядов вторых сомножителей (например, Н (k)), которые корректи17 129541 руют выходные данные входных регистров 27 следующим образом: при поступлении на вход 32 n-ro входного регистра 27 (1 iи < P), в котором saписано значение первого сомножителя

Х,(k), значения первого (младшего) разряда h (k) второго сомножителя ао

Н (К), соответствующего логическои единице, выходные данные и-го регистра 27 остаются неизменными, а при поступлении на вход 32 значения, соответствующего логическому нулю, выходные данные и-ro регистра 27 становятся равными нулю, т.е. про-" исходит умножение значения k-ro первого сомножителя Х,(k) на значение первого разряда k-го второго сомножителя h gk) .

5 18 .Р-м цикле работы блока 2 умножения ,с поступлением P-ro импульса такто,вой частоты на вход 33 во входные регистры 27 записываются значения первых сомножителей X Ä(k). В то же время на входы 32 — 32 поступают значения,P-х разрядов вторых сомножителей h,} (k), которые корректируют выходные данные входных регистров 27. Скорректированные выходные данные X,(k) Ь <р,} (k) входных регистров 27 поступают на первые входы сумматоров 20 блока 28, где они суммируются с данными, которые поступили на вторые входы сумматоров 20 с. выходов регистра 19 промежуточной памяти и на выходе сумматоров 20 формируется сумма

Скорректированные выходные дан- 20 ные X„(k) . h (k) входных регистров 27 поступают на вторые входы (входы В) сумматоров 20 блока 28 (фиг.3), где они суммируются с данными, поступившими на первые вхо- 25 ды (входы А) этих же сумматоров с выходов регистров 19 промежуточной памяти (нулевые значения) и на выходе сумматоров 20 формируется сумма (Х, (k) h о (k) + О) . Выходные 30 данные сумматоров 20 поступают на входы умножителей 21 на степени двойки, причем во всех умножителях

21 блока 28 накапливающих сумматоров по модулю M используемого в блоке 2 умножения, производится умножение на 2 " . Выходные данные с блоков 21,поступают на входы регистров 19 промежуточной памяти. На вход 34, объединяющий входы такто- })0 вой частоты регистров 19 промежуточной памяти блока 28„поступают импульсы тактовой частоты, сдвинутые во времени на половину периода тактового импульса. Первый импульс, поступивший на вход 34, разрешает запись в регистры 19 промежуточной памяти сумм полученных на выходах

У

P-1 сумматоров 20 и умноженных на 2 с помощью умножителей 21, т.е. 50

2 "-Т X, (}-) . h„(k)

С поступлеййем третьего импульса тактовой частоты на вход 33 цикл работы блока 2 умножения повторяется и в регистры 19 промежуточной памяти записываются накопленные за три цикла s сумматорах 20 частичные значения произведения Х (k) Н (К)

Такой процесс повторяется Р раз. На (Х,(k) } м,,) (k) +

+ 2 (Х, (k). },<„» (k) +

+...+2 (X;(k)- h $k) +

+ 2 х,(k) h (k).

Выходные данные сумматоров 20 поступают на умножители 21, где умножаются на 2 и подаются затем на г входы регистров 19 промежуточной памяти, Р-й импульс тактовой частоты, который поступает на вход 34, разрешает запись в регистры 19 промежуточной памяти данных, которые поступили на его входы . (Х (}) }„,„(k) +

+2 (Х,(k) h,(} (k) +

+...+2 (x,(k) h Ä(k) +

+2 Х,(k) ° h„(k)) ° ° ° ) (14) Выражение (14) полностью совпадает с выражением (9) для произведения двух

P-разрядных чисел X и Н. Р значений произведений спектральных коэффициентов Х (k) ° Н (k) 0 k < Р-1 с выходов

1 2

23 регистров 19 промежуточной памяти поступают одновременно íà P P-разрядных входов 38 блока 29 соединений (фиг. 5) . Блок 29 соединений и группа из Р P-разрядных выходных сдвиговых регистров 30 служат для реализации последовательного вывода Р значений произведений X<(k).Н (1) из блока 2 умножения в блок 3 на . том этапе вы10

Для получения P значений произведения Х,(1) Н (1) необходимо произвести (P-1) сдвигов влево содержимого сдвиговых регистров 30. Импуль-. сы сдвига поступают на входы 36 и

37 при работе блока 3 (обеспечивают последовательный ввод значений про— изведений Х „(k) Н (k) в блок 3) . 5

Блок памяти работает следующим образом.

Входные данные, представляющие собой отсчеты числовой последова!

9 числений, когда работает блок 3.

1". помощью блока 29 соединений на вход первого сдвигового регистра 30 постуl дают P первых (младших) разрядов первого, второго,..., Р-го произведения спектральных коэффициентов, на вход второго сдвигового регистра 30 поступают P вторых разрядов первого, второго, ..., P-го произведения спектральных коэффициентов, на вход Р-го сдвигового регистра

30 поступают P P-x разрядов первого, второго,..., Р-го произведения спектральных коэффициентов. Запись данных, поступивших на входы сдвиговых регистров 30, производится подачей на вход 36 разрешающего импульса, совпадающего по времени с (Р+1)-м импульсом тактовой частоты. Выходы младших разрядов каждого из Р выход- 20 ных сдвиговых регистров 30 объединены в одну P-разрядную шину 31.При этом после записи в сдвиговые регистры

30 данных на первом выходе P-разряд25 ной шины 31 появляется значение первого разряда первого произведения

Х „(О) - Н (О), на втором выходе— значение второго разряда произведения Х,(0) Н (О),..., на Р-м выходе — значение P-ro разряда произведе30 ния Х,(0) Н (О). Для получения на выходе шины 31 значения второго произведения Х, (1) " Н (1) необходимо произвести сдвиг влево содержимого

P сдвиговых регистров 30 путем подачи управляющих импульсов на входы

36 и 37. При этом на выходах младших разрядов появляются значения второго произведения Х„(1) Н,(i): на первом выводе P-разрядной шины

31 — значение первого разряда

Х,(1) Н (1), на втором. выводе— значение второго разряда произведе. ния Н (1) Х,(1),..., на P-м выводе — значение Р-го разряда произведения Х„(1) Н (1).

15 20 тельности (P отсчетов по 2Р разрядов каждый, О k < P-1), подаются по шине

8 последовательного ввода на входы каждого сдвигового регистра 40 (фиг.б, 14 и 15). В момент поступления первого отсчета входной последовательности H(0) на вход 41 тактовой частоты первого сдвигового регистра 40 с выхода блока 6 управления поступает первый импульс такто1 вой частоты. С поступлением этого импульса первый отсчет записывается в первый сдвиговый регистр 40. В момент поступления второго отсчета входной последовательности Н(1) на вход

41 тактовой частоты второго сдвигового регистра 40 поступает второй импульс тактовой частоты и второй отсчет записывается во второй сдвиговый регистр 40. Таким же образом записываются остальные отсчеты входной последовательности H(k) в соответствующие сдвиговые регистры 40. После записи последнего P — го отсчета входной последовательности Н(Р-1) в Р-й сдвиговый регистр 40 процесс записи входной последовательности Н®) заканчивает— ся (это соответствует работе блока 5 памяти на первом этапе вычисления, фиг.15). Данные, записанные в сдвиговых регистра 40, поступают на выход блока 5 памяти с выходов младших разрядов регистров 40, начиная с младших разрядов. При записанных данных в регистрах 40 на выходах 32, — 32„ младших разрядов регистров 40 находятся значения первых (младших) разрядов

Р отсчетов входной последовательности

H(k). Для получения на выходах

32„ — 32 р значений вторых разрядов отсчетов H(k) производится сдвиг влево содержимого регистров 40 путем подачи управляющих импульсов на входы

41 и вход 42.

При этом з начения первых раз рядов с выходов 32 подаются на входы последовательного ввода при сдвиге влево

D соответствующих регистров 40 и за:исываются на место старших разрядов, сдвинутых на один разряд влево.

Таким образом, производится циклический сдвиг данных, записанных в регистрах 40. Повторяя сдвиг данньц; в регистрах 40 (P-1) раз, получают на выходах 32 значений младших разрядов отсчетов 2Р— разрядной числовой последовательности Н(к). Младшие Р разрядов -отсчетов последовательности

1295415

H(k) соответствуют второй части числовой последовательности Н (k).Äëÿ получения на выходах 32 Р старших отсчетов 2Р-разрядной последовательности H(k) соответствующих первой части числовой последовательности

Н (k) необходимо произвести Р циклических сдвигов содержимого регистров 40. При следующих Р сдвигах содержимого регистров 40 на выходах

32 последовательно появляются значения Р разрядов отсчетов второй части числовой последовательности Н (k}. Таким же образом получают значения следующих P разрядов отсчетов первой части числовой последовательности

Н,(k) при осуществлении Р сдвигов содержимого регистров 40. Работа блока 5 памяти в режиме циклического сдвига соответствует работе этого блока на втором — пятом этапах вычисления (фиг.14 — 17).

В блоке 4 накапливающих сумматоров (фиг.7, 14 — 17) производится вы- 25 числение выходной свертки путем умножения частичных значений сверток, поступающих íà его входы 43 на множители 2, 2 и 2, и суммироQP P а ванне полученных произведений в со- 30 ответствии с выражением (12). Перед началом работы блока 4 производится обнуление регистров 45 промежуточной памяти импульсом, который поступает синхронно с запускающим импульсом от управляющей 3ВМ на вход 52. Входные Р-разрядные отсчеты вычисленных частичных значений свертки поступают на входы 43 ЗР-разрядных входных сдвиговых регистров 44, причем пер- 10 вые (младшие) разряды Р входных отсчетов поступают на входы (Р+1)-х разрядов соответствующих входных регистров 44, вторые разряды входных отсчетов поступают на входы (P+2)-х разрядов соответствующих входных регистров 44, ..., Р-е разряды P входных отсчетов поступают на вхоцы

2Р-х разрядов соответствующих входных регистров 44. При поступлении импульса тактовой частоты на вход

48, который объединяет входы тактовой частоты группы входных сдвиговых регистров 44, производится запись данных, поступивших на P вхо- 55 дов регистров 44, начиная с входов (Р+1)-го разряда и кончая входами

2Р-ro разряда ЗР-разрядных входных регистров 44, т.е. входные данные сразу сдвинуты на Р разряд вправо, что соответствует умножению на 2

Поэтому нет необходимости умножать на 2 частичные значения свертки

xÄ(n) А- h (n) и х (и) + h (n), поступающие на входы 43 блока 4 накапливающих сумматоров на третьем и шестом этапах вычислений.

Частичные значения свертки х,(п) + h (n) в конце третьего этапа вычислений поступают на входы регистров 44. Вход 48 объединяет входы тактовой частоты группы входных регистров 44.

С поступлением на вход 48 на третьем этапе вычислений (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса (фиг.16), частичные значения свертки х,(п} - h (n) записываются во входные регистры 44. С выходов последних частичные значения свертки, умноженные на 2, т.е. (х Ä(n) < h (n). 2, поступают на вторые входы (входы В) сумматоров 46.

На первые входы (входы A) сумматоров

46 поступают данные с выходов регистров 45 промежуточной памяти (нулевые значения). Полученная сумма поступает на входы регистров 45 промежуточной памяти и с поступлением перного импульса. тактовой частоты на четвертом этапе вычислений (фиг.16) записываются в регистры 45. Частичные значения свертки х Ä(n) + h„ (n) в конце четвертого этапа вычислений поступают на входы регистров 44 и с поступлением на вход 48 на четвертом этапе вычислений (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса, записываются во входные регистры 44. Частичные значения свертки, записанные в регистрах 44 (х,(n) < h„(n}}- 2, необходимо умножить на 2 " в соответствии с выражением (12). Для этого на пятом этапе вычислений производится сдвиг вправо содержимого регистров 44 путем подачи Р управляющих импульсов на входы

48 и 49 (фиг. 17). Полученные на входах регистров 44 значения частичной свертки (х(п) «- h,>(n)) 2 подаются на вторые входы сумматоров 46, где они суммируются с данными, хранящимися в регистрах промежуточной памяти 45.

Полученная сумма ((х, (n) «(h <(n) ) 2 +

+ (х (n) «h, (n)) 2") с приходом

1295415

24 (Р+1)-ro импульса тактовой частоты на пятом этапе вычислений на вход 51 записывается в регистры промежуточной памяти.

Частичные значения свертки х (и) » h (n) в конце пятого этапа вычислений поступают на входы регистров 44 и с поступлением на вход

48 (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса, записываются во входные регистры 44.

Частичные значения свертки, записанные в регистрах 44 ((х (n) « h (n)) 2 р 2 необходимо умножить на 2 в соответствии с выражением (12), т.е. значение, определяемое выражением ((х (n) » h (n)) 2, сдвигается на Р разрядов влево, что соответствует умножению х (n) « h (n) на 2 . Для этого на шестом этапе вычислений (фиг.17) производится сдвиг влево содержимого регистров 44 путем подачи P управляющих импульсов на входы 48 и 50. Полученные на выходах регистров 44 значения частичной свертки ((х (n) »- h (и)) 2 подаются на и вторые входы сумматоров 46, где они 30 суммируются с данными, хранящимися в регистрах 45 промежуточной памяти..

Полученная сумма ((х <(n) » h (n)) 2 +

+ (х,(n) »- h,(n) 2 + (х (n) »- h (n)) 2, с приходом (Р+1) — го импульса тактовЬй частоты на шестом этапе вычислений на вход 51 записывается в регистрах 45 промежуточной памяти. Частичные значения свертки х (n? + h,(n) в конце шестого этапа вычислений по- 4р ступают на входы регистров 44 и с поступлением на вход 48 (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса, записываются во 45 входные регистры 44. С выходов регистров 44 значения частичной свертки ((х (и) »- h,(n)) 2 подаются на первые входы сумматоров 46, где они суммируются с данными, хранящимися в ре-50 гистрах 45 промежуточной памяти. Полученная на выходах сумматоров

46 сумма (х,(п) -» h (и) ) 2 +

+ (x „() ° Ь, (n)) 2 "+ (x () h (n)).2 +

+ (х (n)» h, (n)). 2 соответствует. выражению (12) для результирующей свертки. Данные с выводов сумматоров 46 подаются на выходы 47 блока 4 накапливающих сумматоров.

Блок 6 управления служит для выдачи управляющих импульсов на все блоки. устройства и работает следующим образом (Лиг.8, фиг.9 — 17).

На вход 9 блока 6 управления поступает импульс начальной установки от управляющей ЭВМ. На вход 9„ поступает запускающий импульс от управляющей ЭВМ. На вход 9 поступают импульсы тактовой частоты. Вся работа устройства делится на шесть этапов длительностью (Р+1) периодов тактовых импульсов каждый. На каждом этапе работы с блока 6 управления подаются управляющие импульсы в различные блоки устройства. Перед началом работы блока управления произво дится начальная установка узла 53 выбора режима импульсом, поступающим на вход 9, узла 53. С приходом запускающего импульса начинает работать узел 53 и на его выходе 54 появляется импульс, который запускает синхронизатор 66 и узел 67 памяти адреса, которые управляют работой бло ка 1 и блока 5 памяти на первом эта пе вычислений (Лиг. 14). Кроме того, синхронно с запускающим импульсом от управляющей ЭВМ на выход 52 управле.ния накапливающими сумматорами подается импульс для обнуления регистров

45 промежуточной памяти блока накапливающих сумматоров (фиг.7). По окончании первого этапа работы блока

6 управления на выходе 55 узла 53 появляется импульс, который изменяет режим работы узла 67 памяти адреса и запускает синхронизатор 68 умножителей. Эти узлы управляют работой блока 5 памяти на протяжении второго— пятого этапов вычислений и блока 2 умножителя .на втором этапе вычислений.

По окончании второго этапа работы блока 6 управления на выходе 56 узла

53 появляется импульс, который запускает синхронизатор 66, синхронизатор

68 умножителей, синхронизатор 69 и синхронизатор 70 накапливающих сумматоров. Эти синхронизаторы управляют работой блоков 1 — 4 на третьем этапе вычислений. По окончании третьего этапа работы блока 6 управйения на выходе 57 узла 53 появляется импульс, который запускает синхронизатор 68 умножителей, синхронизатор

69, синхронизатор 70 накапливающих сумматоров. Эти синхронизаторы управ25 ляют работой блоков 2, 1 и 4 на четвертом этапе вычислений. По окончании четвертого этапа работы блока 6 угфавления на выходе 58 узла 53 появляется импульс, который запускает синхронизатор 68 умножителей, синхронизатор 69, синхронизатор 70 накапливающих сумматоров. Эти синхронизаторы управляют работой блоков 2 — 4 на пятом этапе вычислений. По окончании 10 пятого этапа работы блока 6 управления на выходе 59 узла 53 появляется импульс, который останавливает работу формирователя 67 адреса и запускает синхронизатор 68 умножителей, син- 15 хронизатор 70 накапливающих сумматоров. Синхронизаторы 69 и 70 управляют работой блока 3 и блока 4 накапливающих сумматоров на шестом этапе вычислений. 20

Узел 53 выбора режима блока 6 управления работает следующим образом (фиг. 9, 14 — 17) .

12954

На первый вход 9 узла 53 поступает импульс начальной установки от управляющей 3BN, на второй вход 9, запускающий импульс от управляющей

ЭВМ, на третий вход 9 поступают им- 30 пульсы тактовой частоты. Импульсом начальной установки производится обнуление шестираэрядного 79 и (Р+1)разрядного 80 сдвиговых регистров и первого RS-триггера 75. С приходом запускающего импульса на выходе второго RS-триггера 75 устанавливается уровень "Лог.1". Этот же запускающий . импульс через элемент НЕ 76 устанавливает уровень "Лог.0" на входах 10 управления шестиразрядного 79 и (Р+1)-разрядного 80 сдвиговых реги.стров, на первые входы которых постоянно подается уровень "Лог.i".

При поступлении на входы тактовой частоты регистров 79 и 80 уровня

"Лог.1" с выхода второго RS-триггера 75 через элементы ИЛИ 77 в первых (младших) разрядах регистров 79 и 80 записывается значение "Лог.1 .

Уровень "Лог.1" с первого выхода регистра 80 поступает на R-вход второго RS-триггера 75 и íà S-вход первого RS-триггера 75. При этом на вы-. ходе второго RS-триггера 75 устанавливается уровень "Лог.О", а на выходе первого RS-триггера уровень ,"Лог.1", который разрешает прохождение через элемент И 78 импульсов

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

Импульсы тактовой частоты с выхода элемента И 78 через второй эле-. мент ИПИ 77 поступают на вход тактовоч частоты регистра 80. Уровень

"Лог.1" с первого выхода регистра 80 поступает также на вход элемента И

81 группы из шести элементов И, на другой вход которой поступает уровень "Лог.1" с выхода регистра 79.

При этом на выходе первого элемента

И 81 группы находится уровень "Лог.1" до тех пор, пока значение "Лог. 1", записанное в первом разряде регистра 80, не сдвинется во второй разряд при поступлении импульса тактовой частоты на тактовый вход регистра 80. Следующим импульсом тактовой частоты производится сдвиг содержимого регистра 80 еще на один разряд вправо и так далее до тех пор, пока на (Р+1)-м выходе регистра 80 не появляется уровень "Лог.1". При этом уровень "Лог.1" поступает через элемент ИЛИ 77 на вход тактовой частоты регистра 79 и содержимое этого регистра сдвигается на один разряд вправо, т.е. на втором выходе регистра 79 появляется уровень

"Jlor.1" который подается на первый вход второго элемента И 81 группы.

На этом заканчивается первый этап работы узла 53, который равен длительности запускающего импульса от управляющей ЭВИ плюс дительность P периодов тактовой частоты.

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

Поэтому первый этап работы блока уп.равления режимами длится (Р+1)-пе1 риодов тактовой частоты. (Р+1)-й выход регистра 80 соединей также с входом последовательного ввода при сдвиге вправо этого же регистра и при поступлении следующего импульса тактовой частоты значение "Лог.1" записывается в первом разряде регистра 80.

Таким образом с поступлением (Р+1)-ro импульса тактовой частоты или первого импульса тактовой частоты второго этапа работы узла 53 на первом выходе регистра 80 появляется уровень

"Лог.1", который разрешает прохождение через второй элемент И 81 уровня

"Лог.1" с второго выхода регистра 79, < на выходе 55 узла 53 находится уро27 129541 вень "Лог.1" в течение одного периода .тактовой частоты. Через каждые следуюшие (Р+1) такта работы узла 53 на его выходах 56 — 59 поочередно появляются уровни "Лог.1" в течение первого периода тактовой частоты каждо,го этапа работы узла 53. B конце ше стого этапа работы на (Р+1)-м выходе регистра 80 появляется уровень

"Лог.1", который через элемент ИЛИ 77 10 поступает на вход тактовой частоты .регистра 79 и содержимое этого регистра сдвигается на один разряд вправо, т.е. на всех выходах регистра 79 находятся уровни "Лог.О" и узел 53 заканчивает свою работу до поступления следующих управляющих импульсов на его входы. В результате в процессе работы узла 53 Hà его выходах 54-59 формируются импульсы, которые управля 2О ют работой синхронизаторов 66 — 70 рлока 6 управления (фиг.8 и 14).

Синхронизатор 66 (блок 69 аналогичен блоку 66) работает следующим образом (йиг.10. 14 — 17).

На вход 63 синхронизатора 66 поступают запускающие импульсы с узла

53. На тактовый вход 9 поступают импульсы тактовой частоты. На вход управления (Р+1)-разрядного сдвиго- 30 вого регистра 82 постоянно подается уровень "Лог. 1". С приходом запускающего импульса на входе последовательного ввода при сдвиге вправо (Р+1)-разрядного сдвигового регистра 82, $-входе первого RS-триггера

83 и выходе 17 устанавливается значение "Лог. 1 . При этом на выход первого RS-триггера 83 появляется уровень "Лог.1", который разрешает 40 прохождение тактовых импульсов через элемент И 85 на выход 15. Тактовые импульсы поступают также на вход тактовой частоты регистра 82 и вход элемента НЕ 84. С приходом 45 первого тактового импульса в первом (младшем) разряде регистра 82 записывается значение "Лог.1" и на его первом выходе появляется уровень

"Лог.1", который поступает на 8вход второго RS-триггера 83. При этом на выходе этого RS-триггера появляется уровень "Лог. 1", который разрешает прохождение инвертированных тактовых импульсов через второй элемент 60 на выход 16.

С приходом второго тактового импульса содержимое регистра 82 сдвигается на один разряд вправо и на втором выходе этого регистра появляется уровень "Лог.1". Каждым следующим тактовым импульсом производится сдвиг содержимого регистра 82 на один разряд вправо. При этом импульсы тактовой частоты проходят на выход 15, а инвертированные импульсы тактовой частоты прцходят на выход 16 синхронизатора бб. С поступлением P-го импульса тактовой частоты на P-м выходе регистра

82 появляется уровень "Лог.1", который поступает на S-вход третьего

RS-триггера 83 и на его выходе устанавливается уровень "Лог.1".

При этом разрешается прохождение через элемент И 85 инвертированного

P-го импульса тактовой частоты, который поступает на Е-вход первого RS — триггера 83 и устанавливает на его выходе значение "JIor.О", чем запрещает дальнейшее прохождение тактовых импульсов через элемент И 85 на выход 15 ° С поступлением (Р+1)-ro импульса тактовой частоты на (Р+1)-м выходе регистра 82 появляется уровень "Лог.1", который поступает на К-входы второго и третьего RS-триггеров 83 и на их выходах устанавливаются уровни "Лог.О".

Пр. этом запрещается прохождение инвертированных импульсов тактовой частоты с выхода элемента НЕ 84 через элементы 60. Уровень "Лог.1" с (Р+1)-го выхода регистра 82 поступает на выход 18. С .приходом следующего импульса тактовой частоты содержимое регистра 82 сдвигается на один разряд вправо и на всех выходах регистра 82 устанавливаются уровни "Лог.О". В результате в процессе работы синхронизатора 66 на его выходах 15 — 18 Формируются импульсы, которые управляют работой блока 1.

Синхронизатор умножителей 68 работает следующим образом (фиг.11,14-17)

На вход 64 поступают запускающие импульсы с узла 53. На тактовый вход

9 поступают импульсы тактовой час2 тоты. На вход 72 синхронизатора 68 умножителей поступают управляющие импульсы выхода 72 синхронизатора 69 (фиг.8). Эти импульсы поступают на выход 37 и через элемент ИЛИ 90 также на выход 36 синхронизатора 68.

В остальном работа синхронизатора

68 умножателей полностью соответствует работе синхронизатора 66.

29 12954

Узел 67 памяти адресов работает следующим образом (фиг. 12, 14-17) .

На входы 54, 55 и 59 узла 67 поступают запускающие импульсы с узла

53. На тактовый вход 9 поступают импульсы тактовой частоты. На вход управления режимом Р-разрядного сдвигового регистра 93 и первый вход (Р+1) -разрядного сдвигового регистра

95 постоянно подается уровень "Лог. 1" Ю

С приходом запускающего импульса на вход 54 на входе последовательного ввода при сдвиге вправо P-разрядного сдвигового регистра. 93 появляется уровень "Лог.1" и с приходом первого импульса тактовой частоты, который поступает на вход тактовой частоты регистра 93, в первом (младшем) разряде регистра 93 записывается значение "Лог.1" и íà его первом выходе 2О появляется уровень "Лог.1", который через первый элемент ИЛИ 96 группы поступает на выход 41, узла 67.

С приходом второго импульса тактовой частоты на втором выходе регистра 93

25 появляется уровень "Лог.1, который через второй элемент ИЛИ 96 группы поступает на выход 41 узла 67,..., с приходом P-го импульса тактовой частоты на P-м выхода регистра 93 по- 30 является уровень "Лог.1", который через Р-й элемент ИЛИ 96 группы поступает на выход 41 р, На этом узел 67 памяти заканчивает работу, соответствующую первому этапу работы устройства.

С приходом запускающего импульса на вход 55, который соединен с входом схемы 92 и S-входом первого RS-триггера 91, на входе управления режимом (Р+1)-разрядного сдвигового регистра 95 устанавливается уровень "Лог.О", а на выходе первого RS-триггера уровень "Лог.1", который разрешает прохождение тактовых импульсов через элемент И 94 на вход тактовой частоты регистра 95. Первым импульсом такТоВоН частоты, поступивижм на вход тактовой частоты регистра 95, производится запись уровня "Лог.1" в первом (младшем) разряде регистра 95 и на первом выходе этого регистра появляется уровень "Лог.1", который подается на Б-вход второго RS-триггера

91. При этом на выходе второго RSтриггера появляется уровень "Лог.1" который разрешает прохождение инвертированных импульсов тактовой часто15 30 ты на выход элемента И 94. С выхода последнего инвертированные импульсы тактовой частоты поступают на выход

42 и через Р элементов ИЛИ 96 группы на выходы 41 — 41, узла 67.

По экончании запускающего импульса, поступившего на вход 55, на входе управления режимом регистра 95 появляется уровень "Лог.i" и при поступлении следующего импульса тактовой частоты происходит сдвиг содержимого регистра 95 на один разряд вправо.

При этом на втором выходе регистра 95 появляется уровень "Лог.1".

С поступлением каждого следующего импульса тактовой частоты происходит сдвиг содержимого регистра 95 на один разряд вправо и при поступлении (Р+1)-го импульса тактовой частоты второго этапа работы устройства на (P+1)-м выходе регистра

95 появляется уровень "Лог. 1", который поступает на R-вход второго RS-триггера и на его выходе устанавливается уровень "Лог.О", который запрещает прохождение (Р+1)-го инвертированного импульса, тактовой частоты на выходы 42 и 4 1, — 41 .узла 67.

Уровень "Лог.1" с (Р+1)-ro выхода регистра 95 поступает также на вход последовательного ввода при сдвиге вправо этого же регистра и при поступлении первого импульса тактовой частоты на третьем этапе работы в первом разряде регистра 95 записывается значение "Лог.1". В остальном работа узла 67 на этапе работы блока 6 управления полностью совпадает с работой этого блока на втором этапе работы. На следующих четвертом и пятом этапах работы узла 67 цикл повторяется. С приходом в начале шестого этапа работы узла 67 запускающего импульса на вход 59 на выходе первого RS-триггера появляется уровень "Лог.О", который запрещает прохождение импульсов тактовой частоты через элемент И 94. Этим же запускающим импульсом производится обнуление содержимого регистра 95.:B результате в процессе работы узла 67 на его выходах 42 и 41 — 41> формируются импульсы, которые управляют работой блока 5 памяти устройства.

Синхронизатор 70 накапливаллцих сумматоров работает следующим образом (фиг.13 — 17).

31 12954

На входи 57 — 59 пост лают запускающие импульсы с узла 53. На первый и второй входы блока 70 поступают управляющие импульсы соответственно с четвертого 74 и второго 72 выходов синхронизатора 69. Управляющие ,импульсы, поступающие на вход 74 через элемент 99 задержки и элемент

ИЛИ 100, поступают на выход 48 с задержкой на половину периода так- 10 товой частоты. С выхода схемы задержки эти же импульсы поступают на Rвходы первого и второго RS-триггеров

97 и на BbIxopax H RS-триггеров устанавливается уровень "Лог.0". За— пускающий импульс с входа 57 через элемент ИЛИ 100 проходит на выход

51. Запускающий импульс, который поступает на вход 58 синхронно с первым импульсом тактовой частоты, на пятом этапе вычислений подается на

S-вход первого RS-триггера 97 и на его выходе появляется уровень "Лог.1", который разрешает прохождение импульсов с входа 72 через элемент И 98

25 на выход 49 и далее через элемент

ИЛИ 100 на выход 48, а также импуль— са с входа 74 через элемент И 98 и элемент ИЛИ 100 на выход 51 на пятом этапе вычислений. Запускающий импульс, поступающий на вход 59 синхронно с первым импульсом тактовой частоты, на шестом этапе вычислений подается на S âõîä второго RS òðèã-гера 97 и на его выходе появляется 35 уровень "Лог. 1", который разрешает прохождение импульсов с входа 72 через элемент И 98 на выход 50 и далее через элемент ИЛИ 100 на выход

48, а также импульса с входа 74 че- 40 рез элемент И 98, элемент ИЛИ 100 на выход 51 на шестом этапе вычислений. Импульсом, задержанным на половину периода тактовой частоты, с входа 74 производится установка в нулевое состояние первого и второго

RS-триггеров 97. B результате, в процессе работы синхронизатора 70 накапливающих сумматоров на его выходах 48 — 51 формируются импульсы, которые управляют работой блока 4 накапливающих сумматоров.

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

Устройство для вычисления преобразования Фурье-Галуа и свертки, содержащее блок умножения и блок памяти, выход которого подключен к пер32 ному входу блока умножения, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены первый и второй вычислительные блоки, блок накапливающих сумматоров и блок управления, информационный вход первого вычислительного блока является первым информационным входом устройства, выход первого вычислительного блока подключен к второму входу блока умножения, выход которого подключен к информационному входу второго вычислительного блока, выход которого подключен к информационному входу блока накапливающих сумматоров, выход которого является информационным выходом устройства, причем первый, второй третий, четвертый и пятый выходы блока управления подключены соответственно к управляющему входу первого вычислительного блока, адресному входу блока памяти, к синхровходу блока умножения, управляющему входу второго вычислительного блока и к синхровходу блока накапливающих сумматоров, причем информационный вход блока памяти является вторым информационным входом устройства, при этом блок управления содержит узел выбора режима, два синхронизатора вычислительных блоков, узел памяти адресов, синхронизатор умножителей, синхронизатор накапливающих суммато-. ров и три элемента ИЛИ, причем первый, второй и третий входы узла выбора режима являются соответственно входом начальной установки, входом запуска и тактовым входом устройства, первый и третий выходы узла выбора режима подключены соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к входу первого синхронизатора вычислительного блока, первый, второй и шестой выходы узла выбора режима подключены соответственно к первому, второму и третьему адресным входам узла памяти адресов, второй, третий, четвертый и пятый выходы узла выбора режима подключены соответственно к первому, второму,третьему и четвертому входам второго элемента ИЛИ, выход которого подключен к входу запуска синхронизатора умножителей, третий, четвертый и пятый выходы узла выбора режима подключены соответственно к первому, второму, третьему и четвертому вхо12954

З3 дам третьего элемента ИЛИ, выход которого подключен к входу запуска второго синхронизатора вычислительного блока, четвертый, пятый и шестой выходы узла выбора режима подключены соответственно к установочному входу, входу запуска и входу останова синхронизатора накапливающих сумматоров, второй выход второго синхронизатора вычислительного блока под- 10 ключен к входу останова синхронизатора умножителей и входу запуска синхронизатора накапливающих сумматоров, четвертый выход второго синхронизатора вычислительного блока подключен к установочному входу синхронизатора накапливающих сумматоров, тактовый вход узла выбора режима объединен с установочными входами первого и второго синхронизаторов вычислительных блоков, управляющим входом узла памяти адресов и установочным входом синхронизатора умножителей, первый, второй, третий и четвертый выходы первого синхрониза25 тора вычислительного блока объединены и являются первым выходом блока управления, первый и второй выходы узла памяти адресов объединены и являются вторым выходом блока. управле30 ния, первый, второй, третий, четвертый и пятый выходы синхронизатора умножителей объединены и являются б третьим выходом блока управления,пер11ый, второй, третий и четвертый вы- 35 ходы второго синхронизатора вычислительного блока объединены и являются четвертым выходом блока управления, первый, второй, третий и четвертый выходы синхронизатора накапливающих сумматоров и второй вход узла выбора режимов объединены и являются пятым выходом блока управленкя, при этом узел выбора режима содержит два RSтриггера, элемент НЕ, два элемента

ИЛИ, элемент И, два сдвиговых регистра и группу элементов И, причем входы установки нуля первого и второго сдвиговых регистров и R-вход первого RS-триггеров объединены и являют- >0 ся первым входом узла выбора режима. третьим входом которого является первый вход элемента И, вход элемента НЕ и 8-вход второго КБ-триггера

15 34 объединены и являются вторым входом узла выбора режима, выход первого

RS-триггера подключен к второму входу элемента И, выход которого подключен к первому входу второго элемента ИЛИ, выход элемента НЕ подключен к входам управления сдвигом первого и второго сдвиговых регистров, выход второго RS-триггера подключен к вторым входам первого и второго элементов ИЛИ, выход второго элемента ИЛИ подключен к тактовому входу второго сдвигового регистра, выход младшего разряда которого подключен к S-входу первого RS-триггера,К-входу второго RS-триггера и первым входам элементов И группы, выход старшего разряда второго сдвигового регистра подключен к входу последо- . вательного занесения информации второго сдвигового регистра и первым входам первого элемента ИЛИ, выход которого подключен к тактовому входу первого сдвигового регистра, входы младших разряцов первого и второго сдвиговых регистров соединены и являются входом логической единицы узла выбора режимов, выходы разрядов пер,вого сдвигового регистра подключены к вторым входам соответствующих элементов И группы, выходы которых являются выходами с первого по шестой узла выбора режима, при этом вычислительный блок содержит группу из

P входных регистров, узел накапливающих сумматоров по модулю М (M =

Р

2 — 1) и группу из Р выходных регистров, причем информационные входы входных регистров объедине ны и являются информационным входом вычислительного блока, выход -го (I. = 1,Р) входного регистра подключен к i-му информационному входу узла накапливающих сумматоров по модулю М, i-й выход которого подключен к информационному входу

I.-го выходного регистра, выходы выходных регистров объединены и являются выходом:вычислительного блока, тактовые входы входных регистров, узла накапливающих сумматоров по модулю М и вьиодных регистров объединены и являются управляющим входом вычислительного блока.

1295/4 15

8 гс г гор

1295415

44

/р

1р г

7Г

7Z

74 фф

4Р

У/

58

Фиг.9

1295415

1295415 гр

РиюЛЭ

1295415 d5

Ю

44 м с

47

У

7г

73

74

48

4g

5d

Фа/г. В

78

74

44м 17

1295415

На 2

На 2

//а,г2

На 23 д) е) ж) Составитель А.Баранов

Редактор Н.Бобкова Техред И.Попович Корректор Г.Решетник

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

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

113035, Москва, Ж-35, Раушская наб., д.4/5 предприятие, г.Ужгород, ул.Проектная,4

Производственно-полиграфическое

2о

2f

22

2s

24

2î

2к г

2s

24

2ю

2"

2r

2г

2s

24

2о

2к

22

2s

24

2

22

2s

24

2

26

2о

22

23

Zs

24

26

22

22

2з

2 х

26

2î

2î

22

2з

24

2î

2к

22

23

24

2к

22

2s

24

26

2о

22

2У

24

g5

24

2Х

26

2о

2r

22

22

2s

24

2х

26

2î