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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов .. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство для вычисления преобразования Фурье-Галуа и свертки содержит вычислительный блок 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 и за:исываются на место старших разрядов, сдвинутых на один разряд влево.

Таким образом, производится ц