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

Авторы патента:

G06F9 - Устройства для программного управления, например блоки управления (программное управление для периферийных устройств G06F 13/10)

G06F17/14 - преобразования Фурье, Уолша или аналогичные преобразования

1. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СПЕКТРА ФУРЬЕ, содержащее первый блок памяти, информационный вьпсод которого соед1:1нен с первым входом коммутатора, элемент ИЛИ, выход .которого подключен к первому входу блока умножения, выход которого подключен к входу накапливающего сум-матора , блок управления, первый, второй и третий счетчики, селектор, первый выход которого подключен к установочному входу сдвигового регистра , выходы разрядов первой группы которого соединены с входами соответствующих младших разрядов адреса второго блока памяти, информационный выход первого счетчика соединен .с информаьшонным входом сдвигового регистра, блок сравнения и регистр, информационный вход которого является входом задания номера коэффициента устройства, отличающееся тем, что, с целью повышения быстродействия , в него введены переключатель , третий, четвертый и пятый блоки памяти, блок формирования знака и преобразователь прямого кода в дополнительный, выход которого подключен к установочному входу второго счетчика, информационный выход которого соединен с адресными входами третьего и четвертого блоков памяти, информационные выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, ин- . . формационный выход регистра соединен с первым входом селектора, второй выход которого соединён с первым входом блока формирования знака, первым входом блока управления и вторым входом коммутатора, первый и .второй выходы которого соединены с информационными входами соответственно третьего и четвертого блоков памяти, входы разрешения считыва (Л ния которых подключены соответственно к первому и второму выходам блока управления, третий выход которого соединен с первым управляющим входом блока умножения, второй вход . которого подключен к информационному выходу первого блока памятиj вход го разрешения считывания которого объединен с вторым управляющим входом блока умножения и соединен с четвер05 тым вькодом блока управления, пятый vj выход кот;орого соединен со счетным ое входом третьего счетчика, выходы раз-. рядов которого подключены к второму входу блока формирования знака, входам соответствуюпщх старщих разря-дов адреса первого блока памяти и управляющему входу сдвигового регистра , выходы разрядов второй группы которого соединены с третьим входом блока формирова.ния знака, выход которого подключен -К.третьему входу блока умножения, шестой выход блока управления подключен к входу обнуления

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

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

РЕСГВБЛИН

ЗШГ 06 F 15 332

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

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

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3573461/18-24 (22) 06.04.83 (46) 30. l0.84. Бюл. -40 (72) В.А.Зенцов и P.×óïèê (71) Ленинградский ордена Ленина электротехнический институт им. В.И.Ульянова (Ленина) (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

¹598085, кл. g 06 F 15/332, 1978.

2. Авторское свидетельство СССР №760115, кл. r 06 . 15/33?, 1980 (прототип) ° (54)(57) 1. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СПЕКТРА ФУРЬЕ, содержащее первый блок памяти, информационный вьгход которого соединен с первым входом коммутатора, элемент ИЛИ, выход .которого подключен к первому входу блока умножения, выход которого подключен к входу накапливающего сумматора, блок управления, первый, второй и третий счетчики, селектор, первый выход которого подключен к установочному входу сдвигового регистра, выходы разрядов первой гру пы которого соединены с входами соответствующих младших разрядов адреса второго блока памяти, информационный выход первого счетчика соединен с информационным входом сдвигового регистра, блок сравнения и регистр, информационный вход которого является входом задания номера коэффициента устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены переключатель, третий, четвертый и пятый блоки памяти, блок формирования знака и преобразователь прямого кода в дополнительный, выход которого,.SU„„1121678 А подключен к установочному входу второго счетчика, информационный выход которого соединен с адресными входами третьего и четвертого блоков памяти, информационные выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, информационный выход регистра соединен с первым входом селектора, второй выход которого соединен с первым входом блока формирования знака, первым входом блока управления и вторым входом коммутатора, первый и .второй выходы которого соединены с информационными входами соответственно третьего и четвертого блоков Е

И памяти, входы разрешения считывания которых подключены соответственно к первому и второму выходам блока управления, третий выход которого соединен с первым управляющим Я входом блока умножения, второй вход . которого подключеь к информационному выходу первого блока памяти, вход Immi разрешения считывания которого объе- (Я динен с вторым управляющим входом ва блока умножения и соединен с четвертым выходом блока управления, пятый выход которого соединен со счетным входом третьего счетчика, выходы раз-, рядов которого подключены к второму входу блока формирования знака, входам соответствующих старших разря-. дов адреса первого блока памяти и ф управляющему входу сдвигового регистра, выходы разрядов второй группы которого соединены с третьим входом блока формирования знака, выход кото- рого подключен к.третьему входу блока умножения, шестой выход блока управления подключен к входу обнуления торых подключены соответственно к первому и второму входам элемента И-НЕ, выход которого соединен с первым входом первого триггера, прямой и инверсный выходы которого подклюно первого и второго элементов И, выход которого подключен к счетному входу первого счетчика, информационный выход ко орого подключен к входу первого дешифратора, выход первоro элемента И подключен к входу второго триггера, первому входу третьего элемента И и первому входу генератора тактовых импульсов, первый и второй выходы которого подключены к счетному входу второго счетчика, информационный выход которого соеинформационный выход первого регистра соединен с вторым входом генератора тактовых импульсов, выход окончания входу первого триггера, первый вход четвертого элемента И объединен с подключен к второму входу четвертого элемента И, выход которого является двенадцатым выходом блока, вход вход первого узла сравнения объединены и являются первым входом блока, и второй вход второго узла сравнения объединены и "являются вторым входом блока, выходы первого и второго дешифраторов и выход. третьего. элемента

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

2. Устройство по п.1, о т л ивЂ” ч а ю щ е е с я тем, что блок формирования знака содержит шесть триггеров, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемент

И-НЕ и элемент ИЛИ, выходы первого, второго и третьего триггеров соединены с первыми входами соответственно первого, второго и третьего суммавходами соответственно первого и соединены соответственно с первым, второго узлов сравнения, выходы ко- вторым и. третьим входами первого

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

112 элемента И, выход которого соединен. с первым входом элемента И-НЕ и первым входом второго элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого соединен с первым входом третьего элемен:та И, выход которого является выходом блока, выходы четвертого, пятого и шестого триггеров соединены с первыми входами соответственно четвертого, пятого и шестого сумматоров по модулю два, выходы которых подключены соответственно к первому, второму и третьему входам четвертого элемента И, выход которого соединен с вторым, 1á78 входом элемента И-HF,, и первым входом пятого элемента И, выход которого подключен к второму входу элемента

ИЛИ, третий вход которого соединен с выходом элемента И-HF. второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока, второй вход третьего элемента

И является вторым входом блока, вторые входы первого, второго и третьего сумматоров по модулю два объединены с вторыми входами соответственно, четвертого, пятого и шестого сумматоров по.модулю два и являются третьим входом блока.!

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

Известно устройство для вычисления коэффициентов разложения времен- 15 ного процесса в ряд Фурье посредством

БПФ,содержащее регистры, блок умножения, сумматор и коммутаторы f1).

Недостаток известного уСтройствавЂ” невозможность получения спектральных характеристик Фурье непосредственно из спектральных характеристик Уолша.

Наиболее близким к предлагаемому является устройство для вычисления р5 спектра мощности Фурье, содержащее регистр, блок сравнения, первый, второй и третий счетчики, первый и второй блоки памяти, блок формирования адреса, первый и второй дешифра- ЗО торы, первый и второй шифраторы, блок умножения, сумматор, коммутатор, .блок управления, блок вычисления коэффициентов спектра мощности

Уолша, блок селекции, блок формирования кода Грея, первый и второй

2 элементы ИЛИ, причем выход первого шифратора подключен к установочному входу первого счетчика, выход которого подключен к входу первого дешифратора и первому входу блока формирования адреса, выход которого подключен к адресному входу первого блока памяти, выход первого блока памяти подключен к первому, а выход второго блока памяти вЂ” к второму входу коммутатора, выход которого подключен к входу блока умножения, выход блока умножения подключен к входу сумматора, выход второго счетчика подключен к адресному входу второго блока памяти, выход ре гистра вЂ” к первому, а выход третье- . го счетчика и второй выход блока. формирования адреса вЂ” к второму входу схемы сравнения, первый выход блока управления подключен к счетному входу первого счетчика, второй выход блока управленияк управляющим входам первого и второго счетчиков и сумматора и счет-; ному входу второго счетчика, первый выход блока управления подклю- . чен к выходу схемы сравнения, а второй выход вЂ” к переключающему входу коммутатора и управляющему входу блока умножения, установочный вход третьего счетчика,.вход регистра и первый вход второго блока памяти являются входами устройства, вход блока для вычисления спектра мощ- ности Уолша является дополнительным з 11216 входом устройства, а выход подключен к второму входу второго блока памяти, вход второго дешифратора подключен к выходу третьего счетчика, выход вЂ” к входу первого и первому входу второго шифратора, выход

5 которого подключен к установочному входу второго счетчика, выход которого подключен к второму входу второго шифратора, входу первого элемента ИЛИ и входу блока формирования кода Грея, выход которого подключен-к первому, а выход первого дешифратора вЂ” к второму входу блока селекции, выход которого подключен к третьему входу блока формирования адреса, выход первого счетчика подключен к входу второго элемента

ИЛИ, выходы первого и второго элементов ИЛИ вЂ” соответственно к третье20 му и второму входам блока управле- ния P2).

Однако с помощью известного устройства спектральные коэффициенты

Фурье из спектральных коэффициентов

Уолша анализируемого временного процесса вычисляют с низким быстродействием.

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

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

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

112 t

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

5 памяти, информационный выход которого является информационным выходом устройства и соединен с третьим входом коммутатора, четвертый вход которого объединен с вторым входом блока управления., первым входом блока сравнения и подключен к первому выходу селектора, третий выход которого соединен с установочным входом первого счетчика, вторым входом блока сравнения и входом преобразователя прямого кода в дополнительный, управляющий вход которого подключен к выходу блока сравнения, управляющий вход которого объединен с управляющим входом селек- о тора и подключен к седьмому выходу блока управления, восьмой выход которого соединен с входами обнуления первого и второго счетчиков, управляющие входы которых объединены с уп->5 равляющнм входом третьего счетчика и подключены к девятому выходу блока управления, десятый и одиннадцатый выходы которого соединены со счетными входами соответственно первого и второго счетчиков, двенадцатый и тринадцатый выходы блока управления соединены соответственно с первым и вторым управляющими в-..одами коммутатора, а информационный вход первого блока памяти соединен с выходом переключателя, вход которого является информационным входом устройства, второй выход блока управления подключен к входу обнуления накапливающего

40 сумматора и входу разрешения записи пятого блока памяти, адресный и информационный входы которого соединены соответственно с информационным выходом первого счетчика и выходом накапливающего сумматора, причем f

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

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

Блок формирования знака содержит шесть триггеров, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемент И-НЕ, и элемент

ИЛИ, выходы первого, второго и третьего триггеров соединены с первыми входами соответственно первого, второго н третьего сумматоров по модулю д.>а, выходы которых соединены соот7 11216 ветственно с первым, вторым и третьим входами первого элемента И, выход которого соединен с первым входом элемента И-НЕ и первым входом второго элемента И,, выход которо- 5 го.подключен к первому входу элемента ИЛИ, выход которого соединен с первым входом третьего элемента

И, выход которого является выходом блока, выходы четвертого, пятого и шестого триггеров соединены с первыми входами соответственно четвертого, питого и шестого сумматоров по модулю два, выходы которых подключены соответственно к первому, второму и третьему входам четвертого элемента И, выход которого соединен с вторым входом элемента И-HF. и первым входом пятого элемента И, выход которого подключен к второму входу элемента ИЛИ, третий вход которого соединен с выходом элемента И-НЕ, второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока, второй вход третьего элемента И является вторым входом блока, вторые входы первого, второго и третьего сумматоров по модулю два объединены с вторыми входами соответственно четвертого, пятого и шестого сумматоров но модулю два и являются третьим входом блока.

На фиг.1 приведена блок-схема устройства для вычисления спектра . Фурье, на фиг.2 вЂ” временная диаграмма блока управления; на фиг.3 вЂ” схема селектора; на фиг.4 вЂ” схема блока управления; на фиг.5 вЂ” схема переключателя; на фиг.б вЂ” схема блока форми40 рования знака.

Устройство содержит (фиг.1) вход

1 устройства, переключатель 2, блоки .3-7 памяти, блок 8 умножения, накапливающий сумматор 9, счетчики 10

45 и 11,регистр.12,счетчик 13,преобра-> зователь 14 прямого кода в дополнительный, блок 15 сравнения, коммутатор

16, селектор 17, сдвиговый регистр (блок формирования адреса) 18, блок

19 формирования знака, элемент ИЛИ 20, 50 блок 21 управления, вход 22 и выход 23 устройства.

Возможный вариант построения схемы селектора приведен на фиг.3, Селектор содержит регистр 24, сдвиговый регистр .25, элемент И 26, триггеры 27 и 28 с раздельными входами, счетчик 29, а также мультиплексор

78 8

30, управляющий вход 31 на запуск блока, вход 32 двоичного кода коэффициент Фурье %, выход 33 кода параметра р (признак четности или нечетности коэффициента Фурье, причем, если р=1, коэффициент косинусный, если р=0 - синусный), выход 34 кода (номер совокупности (блока), к которому относится коэффициент) и выход 35 кода 3 (номер коэффициента в r -м блоке).

Блок 21 управления предназначен для формирования на его 13 выходах в соответствии с заданными п,r,р требуемой последовательности управляющих импульсов (она изображена на фиг.2 для случая п=б, r=2) и содержит регистры 36 и 37, элементы 38 и 39 задержки, узлы 40 и 41 сравнения, генератор 42 тактовых импульсов, триггеры 43-45 с раздельными входа- . ми, элемент И-НЕ 46 элементы И 47-50, элементы ИЛИ 51-60, группы, дешифра- . торы 6 1 и 62, а также счетчики 63 .и 64. Вход тактовых импульсов обозначен буквами ТИ, Переключатель 2 предназначен для перетасовки вычисленных коэффициентов Уолша к виду, необходимому для их умножения на факторизованные матрицы.

На фиг.5 изображена схема коммутации входов 1С i j и выходов

1С ) переключателя 2 для 1 =16 в соответствии с табл.1.

Блок 19 формирования знака предназначен для формирования знака. элемента факторизованных матриц спектрального преобразования для четных (косинусных) коэффициентов в зависимости от положения элемента в.матрице и ее номера и содержит триггеры 65-70, сумматоры по модулю геры 65-70, сумматоры 71-76 по модулю два, элементы И 77-81, элемент

НЕ 82, элемент И-НЕ 83 и элемент

ИЛИ 84. Входы кода номера факторизованной матрицы i обозначены позицией 85, входы кода номера элементов 1 в -й факторизованной матрице вЂ” 86, вход параметра р -87, выход блока p вЂ” - 88.

Блок 8 умножения имеет три входа сомножителей х,v,р, участвующих в умножении и может работать в двух режимах.

Если задействован один управляющий вход то производится умножение

11216 (Х, если р=О (х у, если р =1, 2 и- -1

Г = " (0,vj

U,v=1

7 = 75,1 5=1, У половины иэ общего числа эле- 20 ментов Г и Г знаки одинаковы, с 5 а у ОсталЬной половины противоположны.

При перестановке строк и столбцов матриц Г, Г по описанному ни»,е с алгоритму удается привести их к так называемому блочно-диагональному виду. При этом отдельные спектральные составляющие как в базисе

Фурье, так и в базисе Уолша, объе- Зо диняются в и совокупностей (блоков). Спектральные составляющие

Фурье, относящиеся в любой г-совокупности (их число составляет 2" "+" зависят только от. 2 " " " спект35 ральных составляющих в базисе Уолша, относящихся к этой же совокупности.

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

Все без исключения элементы в меньших блоках с номерами r 2 имеются в самом большом блоке с номером г=1..

С С И-1 „ у = у ks =1,2 -1 =1,h-1

%5 21с2з

С, С„с„с„

Здесь число ненулевых элементов в исходной матрице Г " =Я & число

Эп

50 ненулевых и неединичных элементов в матрицах Г ..., Г„„по 2 " ", r а в матрице Г" =2" . Общее число ненулевых и неединичных элементов

Р в матрицах Го -- Г „,. б составляет

55 таким Образом (n- r1 2 в " 1 в 2" " "меньше, чем в самой Г .

Матрицы ГО,Г Г 5 для И=32

5 S 5 представлены в табл.5-7. (2)

yak 2

2es<2

9 сомножителей в соответствии с выражением

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

Алгоритм функционирования устройства можно описать следующим Образом.

Все соответствующие элементы матриц спектрального преобразования (табл.1 и 2) равны по модулю

Матрицы Г =(y » н Г () о„» имеюцие с с 5 5 блочно-диагональный вид, для N =32 изображены в табл.3 и 4.

Таким образом, все основные структурные свойства матрицы Г полностью

78 10 определяются свойствами нх основного блока (г =1) .

Введем следующие обозначения:

r-Г-1 : вЂ” совокупность элеII=(/ jIjl ментов т-го блока

° Е=1 вектора 3;

II- --

- е {е{ вЂ” совокупность эле3 Е=1 ментов г-го блока вектора Е

I совокупность weментов г.-го блока матрицы Гс;, В-Г-1

S 5 2

Г = 1" (0,v} -совокупность элеО,v=1 ментов r-ro квадратного блока матрицы Г

-совокупность элементов r-ro блока вектора А, -совокупность элементов r-ro блока вектора В.

Исследования показали, что у каждого г-го блока матриц г, имеется свойство пропорционального соотношения между элементами различных столбцов. Исгользуя это свойство, можно представить любой блок матриц Гс, Гзразмерностью 2"-"-12 -"-" в виде произведения и -и -1 сильно разреженных нулевыми элементами матриц. п-г-1 и 1 r

Если p, = ., (О ф -совокуп,О,Ч=1 ность елементов r-го квадратного блока l -и факторизованной матрицы

1 1 1121678 12

Таким образом для умножения в из- Для вычисления четных (косинусе вестном устройстве для r-ro блока не- ных) спектральных составляющих о ходимо бходимо 2, " " " операций в то вре- можно воспользоваться значениями

Э бе! мя как умножение на правую часть элементов матриц Q ." для нечетных тождества (Э) которое может совер- 5 составляющих. Неединичные элементы

)S Гс

ШатЬСя ПО ИтЕрацИОННОМу аЛГОрИтМу Ма Рнц 1 еГ; е1"-Ое11-3 раВНЫ ПО МО(4) за п- г -1 итераций, требует дулю. Чте .» касается знаков, то для в общей сложности .пишь(е1-г) 2" г ум- матРиЦ Г1..., Гп З эти знаки всегДа ножений, т.е. в 2 и г меньше, чем противоположны.

l1- l

С С (с)=" ° И), г=1,h-1; 1=1,2 (g) в прототипе:

A=f 3

5 г г! 1 1 1 г

В ГО Е„г2 (4) 15

30 Э

Eî=E

1=1! n-l 2

1-г-2

20 где j). =(д. Щ) „вЂ” совокупность эле1 1

2п-г-1 г

@ () . ) г

q,",(<)=yr (<,1); 1=1,п-З;,г(е ) и-г-2 (щ О е !

1-2 г - г- < „n-r-2

Я-г-2 l1-r-2

fZ (1++2,)l/, 0(2

1",(ее " е-ее), е.2" „1®=

Свойство (2) позволяет исполь--; зовать элементы первого блока матриц

Й для выполнения умножений в блоках

2,3,... h

,."c),)= s;." (г-г" )

; 1И и-3; 1=я-1 (5)

1, ЕЦ=1,."(е-2 )

Лишь матРицУ Я „г.2тРебУетсЯ хРанить в полном объеме вЂ” Й/2 коэффициентов, из них в первом блоке Й/8, во втором М /16 в третьем и т.д. гической переменной

l1-1

Рг= j (i!1), " 0+

Если 3 г=1, то функций нечетная, если 1г =0, то четная. В соответствии со значениями 11- < формируются е! блоков коэффициентов и и --1 блоков четных. Затем производится

th""-0 ментов r-ro блока вектора коэффициентов Я после 1 -й итерации, h-1--1 25

Е,= 0.()l)), вЂ” совокупность элене=

1 ментов ) -ro блока вектора коэффициентов Е после 1-й итерации, Обозначим элементы факторизованных матриц следующим образом: е1- -2

Если 1 -4 2, то у элементов

Q>1ÏO СРаВНЕНИЮ СЕеЕ „„ЗяаКИ МЕНЯТЬ нужно, а у 6„2 не нужно. Если же

0 3 2" г 2, то у элементов Я „„знаки менять не нужно, а у ее(„йужно.

В результате спектрального преобразования по (4) вектор-столбцы А,В будут двоично перетасованы. Поэтому чтобы получить коэффициенты Фурье в естественном порядке следования, необходимо массивы коэффициентов перетасовать по закону двоичной инверсии.

Быстрый алгоритм преобразования коэффициентов Уолша в коэффициенты

Фурье, который используется в данном устройстве записывается следующим образом.

1. Разделение (й-1) спектральных коэффициентов Уолша fC>. „на две

Н N части вЂ” -1 четных и вЂ” нечет2 2 ных коэффициентов, а внутри каждой части вЂ” разделение на 11 блоков в соответствии с номером первой справа единицы в двоичном представлении номера

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

Пусть j вЂ” двоичный эквивалент (код) номера j . В процессе поразрядной логической обработки производится вычисление параметров номера первой единицы в коде, считая со стороны старших разрядов, и ло13 11216 перестановка коэффициентов в каждой группе в соответствии с алгоритмом двоичной инверсии их номеров в этом блоке (нумерация 1 начинается с О) . Например, для М =16 приведена табл.8 для перетасованного массива коэффициентов Уолша (15

j -jг=1

2. Непосредственное вычисление к-го коэффициента Фурье. Вначале в ходе логической обработки кода % определяются значения параметров р,r,Р по следующему алгоритму. Зна15 чение самого младшего разряда в коде 1(, определяет значение р. Если

I обозначить через %, (h-1)-разрядный код, образованный отсечением / у кода % самого младшего разряда, 20 то номер первой по счету единицы в этом коде, считая справа, определяет значение параметра- г . Если обозначить через k„(o-г-1)-разрядный код, образованный из кода 1 „ от25 сечением первой справа единицы и всех нулей (если они есть), следующих после этой единицы справа, то значение 1 определяется двоич( но-инверсным кодом 1 2 . Например, если и =6, à 1щ =01 . 101, то р =1 коэффициент косинусный (четный);

%, =01110, г =2 вЂ” номер блока; М =011

1=7 вЂ” номер коэАфициента в 2-м блоке; Г =110.

Тогда значение коэфАициента е)(„« йли (ЬДопределяется из значений только четных (при р=1) или нечетных (при р=О) коэффициентов г-го блока и может быть вычислено с помощью следующих выражений (см. конфи40 гурацию матрицГ,Г,Г, в табл.5-7); з5

30 г

ЕО=Е 0= . 45

", (е)=("lele,. „(ml.е"., „(m e 1, )=г, „

7 (P)=q), (Це. (m1+e „, „()+2 }, ()=2

50 вЂ” e)-) -2 его=.1) 2; 1 =1, и-)=2

Й) 55

rp.е, 1Р ) -2 (е(=

e)- r -1 n -)--2

2 +1 0, Р Я

78 в случае нечетных коэфАициентов,и

С„

d (г)=,"(Щ, „lm)+a. „(м+г }, (=em-1

d;(el=9, (e)d; „(m) d. (m+e"" J,Е=гм

"=1,)г-г-2 и-г-2 .

С„ (е) г„„г()щ) „(e)am„(e ) (и) в случае четных коэффициентов.

Значения (g,(0j« могут быть получены из значений коэффициентов (Я; (Р1« (т.е. относящихся х пеРвому бпоху) в соответствии с выражениями (5), (6).

Таким образом, для вычисления всех 2" г " коэффицициентов Фурье, относящихся к г -му блоку, требуется (n-г) 2 умножений и сложений.

))-г-1

Для вычисления одного коэффициента

Фурье с заданным номером k требуется (и-e- -2) 2" " " умножений и сложений для выполнения вычислений по (7) и два умножения и одно сложение для выполнения (8) . Всего, таким образом, необходимо (h-г-2))(«2 " " +2 умножений и сложений.

Устройство для случая h =6, г=2, р=1 работает следующим образом.

В начальный момент времени в блоке 3 памяти записаны 2 " " -1 коэАфициентов Уолша )edeЗ «2 " коэффициентов Р5« и C которые постуI пают с-информационного входа устройства и перетасовываются с помощью переключателя 2 по описанному выше алгоритму. В блок 6 памяти записаны элементы первых блоков матрицй„)...,8„ 1 и в е и блоков матрицы Я„„. Все счетчики и сумматор 9 обнулены.

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

8,)y2,6, 1,5,3,7 (при N =Я).

Тактовые импульсы начинают поступать на вход блока 21 управления.

Блок 21 управления (фиг.4) pz6oтает. следующим образом. В исходном

678 16

1121

15 состоянии все триггеры и счетчики находятся в нулевом состоянии. Первый тактовый импульс проходит через открытый элемент И 47 на выход блока и затем устанавливает в единичное по5 ложение триггер 43, тем самым запирая элемент И 47 для дальнейшего пропуска тактовых импульсоь.

По сигналу блока управления селектор 7 производит логическую обработку 1О двоичного кода 1 по описанному выше алгоритму. В начальном состоянии (фиг.3) счетчик и оба триггера находятся в нулевом состоянии. По сигна-. лу на зупуск устройства на регистр

24 поступает код k Значение самого младшего (и-1)-ro .разряда поступает на триггер 28 и устанавливает его в определенное положение, соответствующее значе ию параметра р код 4 вЂ” 20 на регистр 25 . Управляющий сигнал поступающий на вход 31, .устанавливает триггер 27 в единичное положение, благодаря чему открывается элемент

И 26. Тактовые импульсы начинают

25 поступать на сдвиговый вход регистра

25, а счетчик 29 ведет подсчет этих импульсов. До тех пор, пока. на вход триггера 27 поступают нули, элемент

И 26 открыт и сдвиг регистра продолжается. Первая же единица, поступившая на вход триггера 27, устанавливает его в нулевое состояние, элемент

И 26 закрывается сдвиг регистра

25 прекращается. На счетчике 29 будет находиться значение кода r а значение кода 1 может быть считано с выхода регистра 25 с последующим его двоичным инве тированием, что обеспечивается соответствующей настройкой связей входов и выходов в мультиплексоре 30.

Значения параметров r,Р поступают на входы блока 21 управления и сравниваются (фиг.4) со значением этих же параметров, которые

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

После этого новые значения г,р задержавшись в элементах 38 и 39 за держки устанавливаются в регистрах

36 и 37.

Если старые и новые значения параметров совпадают, то это означает, что в блоках 4 и 5 памяти (фиг.1) содержатся необходимые для вычисления коэффициента Фурье с текушим значением номера Ъ значения векторов

Э „„g или Е „„g .Поэтому блок 21 управления выдает в дальнейшем такую последовательность управляющих импульсов, которая на фиг.2 соответствует моменту времени 1У и далее.

Рассмотрим случай, когда текущие значения r р не совпадают с предыдущими, что означает, что триггер 44 (фиг.4) находится в единичном состоянии, т.е. на выходах блока управления появляется последовательность импульсов, полностью соответствующая фиг.2.

В этом случае тактовые импульсы (фиг.4) начинают поступать на генератор 42 тактовых импульсов, элемент

И 50 и триггер 45. Импульс пройдет через открытый элемент И 50 и выйдет на. соответствующие выходы. Этот же импульс переведет в единичное состояние триггер 45 и элемент И 50 в дальнейшем будет закрыт.

Генератор 42 предназначен для ь- выдачи (n-г-2) . 2 +1 тактовых импульсов по первому своему выходу и (п вЂ” r 2) импульсов по второму выходу (через каждые 2" выдаваемых по первому выходу) для сброса счетчика 64 в нулевое состояние. Благодаря этому на выходах дешифратора 62 будет появляться последовательность импульсов, соответствующая временному интервалу 1-1 1 на фиг.2, и эта последовательность импульсов будет повторена (h-r -2) раз. Имеющаяся на фиг.2 картина на выходах блока управления получается благодаря соответствующему соединению выходов дешифратора 62 с входами элементов

ИЛИ 51-60 группы. На выходах дешифратора в момент прихода очередного импульса на тактовый вход генератора будет возбуждаться только одна из его выходных шин.

На фиг,4 показаны соединения только первых его четырех шин и последняя 17-я, в то время, как для случая п =6, г =2 у дешифратора должны быть задействованы выходы всех первых

17 шин, которые соединены с входами элементов ИЛИ 51-60 группы.

После выдачи последнего (n-r-2)» 2 +1)-го импульса генератор выда20 Старший разряд кода Г О 7ределяет логическую переменную

0, Га2

Р 2

По приходу управляющих импульсов с выходов блока управю ения произво50 дится выборка значений 1„ „, 1 из бло2 ка 5 памяти с тем же адресом, опре.деляемым счетчиком 10, Это значение из-за того, что у блока умножения задействован соответствующий вход, передается на выход умножителя и поступает на вход сумма-.ора, где происходит сумм.рование по (9) . Сфори ю рованная сумма д„(1) передается

17 11216 ет сигнал конца своей работы, который перебрасывает триггера 44 в нулевое положение. Этому моменту времени соответствует точка 1У на фиг.2.

Как уже отмечалось, триггер 44 может находиться в нулевом состоянии и после прихода первого тактового импульса на вход блока из-за несовпадения старых и новых .начений г,р.

По сигналу блока управления в блоке 15 сравнения производится сравнение кодов и устанавливается соответствующее значение на выходе преобразователя 14 прямого кода в дополнительный в соответствии с (1). По сигналу блока управления с помощью коммутатора 16 производится перезапись 2 " значений четных (при. р=1) или нечетных (при p=0) коэффициентов Уолша r --го блока из блока памяти в блоки памяти 4 и 5 таким образом, что первые 2 " " значений подряд заносятся в блок 4 памяти, а оставшиеся 2 " " 2 значений вЂ” в блок 5 памяти.

По сигналу блока управления производится суммирование единицы в счетчик 11 матриц Э„. его содержимое становится равным 1.

По импульсам из блока управления к содержимым счетчиков 10 (параметр

1п) и 13 (параметр 0 ) добавляется по единице, они становятся равными

1. По сигналу блока управления из блока 4 памяти выбирается значение (о21"1 адрес которого соответствует содержимому счетчика 10, которое чевЂ” рез элемент ИЛИ 20 поступает на вход блока 8 умножения. По сигналу с блока управления производится выборка значения „;11 из блока 6

2, памяти. Его адрес слагается из двух кодов - номера факторизованной матрицы 1 определяемого содержимым сче; ика 11, и кода номера F в

Г-м блоке 1 вЂ” 1 матицы, определяемого содержимым счетчика 13. Сдвиговый регистр 18 производит формирование физического адреса для работы блока 19 и блока 5 памяти.

Его работу можно описать следующим образом.

Если поступающий на третий вход блока код номера факторизованной матрицы 1 не равен и -2, то коц номера в факторизованной матрице, поступившей на вход сдвигового регистра i8. сдвигается в соответствии с (5) Hà r вЂ” 1 разрядов влево

78 18 и выдается на первый и второй выходы, Значение 1 поступает

1 (21 на вход блока 8 умножения.

В случае вычисления четных коэффициентов Фурье р =1 блок 19 форми рования знака формирует значение логической переменной p . Блок 19 работает следующим образом.

В начальном состоянии (фиг.6) в триггеры 65-67 записан код 101 (соответствующий и -1=5), а в триггеры 68-70 вЂ” код 100 (соответст», вующий ь -2=4). С помощью сумматоров по модулю два осущес вляется определение признаков

О, i4n 4 0 14п-2

Р21, 1= п-1 1=- я-2

Остальные элементы схемы реализуют логическую функцию р в соответствии с табл.9, которая, в свою очередь, следует из описания алгоритма формирования знаков матриц Йс 1=1

1 Э

h-1 описанного выше.

При всех остальных комбинациях

p,р„,р2, p p ДОлжнО быть равным 0 °

Значениp р +ñòÿ÷éÐëèBéeòñÿ на входе блока 8 умножения (фиг,1).

Поскольку задействован другой вход блока умножения, то производится умножение

Значение z поступает на вход сумматора . 9. и суммируется с его содержанием (т.е. с нулевым кодом) .

19 1121 на вход блока 7 памяти и записывается по адресу, определяемому содержи-. мым счетчика 13. Сумматор обнуляется.

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

10 (т=1) не изменяется, и на вход блока умножения поступают те же значения о1 (1) и d (5), а из блока 6 выбирается новое значение а „ (5) по адресу,. определяемому новым (равным

2) содержимым счетчика 13. По адресу 2 в блек 7 памяти будет записано новое значение d„(pl

Тем самым к моменту времени П реализовано умножение элементов вектора Э о на первые две строки матрицы г

G„(m=1; 6 =1, 2), 20

В дальнейшем на последующих тактах вплоть до момента времени Ш (фиг.2) производятся аналогичные действия.

В результате к моменту времени И в блоке ? памяти будут сформированы восемь значений первого промежуточного вектора 3 „

По приходу управляющих импульсов из блока управления содержимое блока

7 памяти переписывается через коммутатор 16 в. блоки 4 и 5 памяти, первая половина (первых четыре элемента) в блок 4, а остальные четыре элемента вЂ” в блок 5. К содержимому счетчика

11 прибавляется l и оно становится равным 1=2. Счетчики 10 и 13 обну35 ляются.

В дальнейшем производится умножение вектора 2 на матрицу, номер которой соответствует содержимому

40 счетчика 11. Зписанные ранее действия повторяются без всяких изменений, и в результате к моменту времени

1У в блоке 7 памяти будут сформированы восемь значений второго проме,45 жуточного Вектора 3 2

678 20

По импульсу блока управления в счетчик 11 номеров факторизованных матриц заносится код, десятичный эквивалент которого равен h -2=4> что соответствует подготовке к умножению на матрицу Ц д 2 В счетчик

13 заносится значение 1 соответствующее строке матрицы 6 q-g на которую необходимо умножать вектор 3 2 В

2 счетчик 10 заносится значение rn no (2), которое было получено на выходе преобразователя прямого кода в дополнительный, управляемого блоком сравнения.

По импульсам, поступающим с выходов блока управления, производится выборка соответствующего значения d2(rnl которое через элемент

ИЛИ 20 поступает на соответствующий вход блока умножения. B соответствии со значениями р и содержимым счетчиков 11 и 13 на соответствующие входы блока умножения поступают значения (el; р.

При этом следует отметить, что благодаря особенности матрицы Q „ 2 работа сдвигового регистра 18 при

i =n-2 происходит особым образом.

На выход сдвигового регистра 18 так же, как и при 1 п-2, поступает сдвинутый на г -1 разряд влево код

На другой выход сдвигового регистра

18 поступает составной -разрядный код адреса в матрице Q 2. Старшие

)(og vI+1 разрядов этого кода состав2 ляет код номера блока r в матрице, а младшие п-)Гор.(- разрядов вЂ” код не сдвинутый на г -1 разрядов,Такое строение кода адреса позволяет адресовать N/2 элементов матрицы разделенной на и блоков размерностями соответственно N/4, N /8...

В блоке 8 умножения задействован соответствующий вход, поэтому производится умножение

К этому моменту времени триггер

44 в блоке 21 управления (фиг.4) находится в нулевом состоянии. Поэтому открывается элемент И 48 50 и тактовые импульсы начинают поступать на счетчик 10 и дешифратор 61.

Благодаря сделанным соединениям выходов дешифратора 6 1 с входами элементов ИЛИ 51-60 группь. на выходах 55 блока управления появятся управляющие импульсы (фиг.2) после момента времени Q". результат 2 поступает на вход сумматора.

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

11 матриц добавляется 1 и оно становится равным и -1. Производится выборка g2 („1 вЂ” значения вектора Э

2 из блока 5 памяти, которое через

121678 22 коэффициента Фурье с новым номером к

При этом сохраняются значения векторами<, находящиеся в блоках 4 и 5. т. памяти.

5 Затраты времени на вычисление коэффициента Фурье по -заданным коэффициентам Уолша с помощью предлагаемого и известного устройств приведены в табл.10.

t0 Таким образом, при вычислении подряд с помощью предлагаемого устройства 2 " " коэффициентов Фурье, телей и значение z поступает на вход сумматора, где реализуется вычисление значения"в соответствии с (10). Сфор- 15 мированное значение записывается .по адресу g в блок 7 памяти. Это значение представляет. собой значение коэффициента Фурье с номером k.

По сигналам иэ блока управления 20 производится выборка, по адресу определяемому содержимым счетчика

13 из блока 7 памяти значения коэффициента Фурье, и передача его на выход 23 устройства. Производится 25 обнуление счетчиков 11,13 и 10. Устройство готово к следующему циклу работы по вычислению нового значения

21 1 элемент ИЛИ поступает на соответствующий вход блока умножения. На выходах блока 19 и блока 6 памяти появляются соответствующие значения р, (P}.Так как у блока 8 умножения задействован соответствующий вход, то производится умножение сомножи-. относящихся к одному г-му блоку, и- Г-1 требуется в

-меньше операций и-г умножения и сложения по сравнению с устройством-прототипом, что и определяет его преимущества по быстродействию. Например, при п =10 2, это преимущество составляет 16 раз.

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

С»

С44

СР"

4 4

С» .Ь

4«»

4»

«4 в

Ю4

4 Г

СЭ

DQ 4 о