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

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

Иллюстрации

Показать все

Реферат

 

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. второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока, второй вход третьего элемента

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

1

Изобретение относится к вычислительной и информационно-измерительной технике и может быть использовано в качестве специализированного вычислительного устройства для спектраль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, Р Я

14

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 устанавливается либо в единичное положение (если хотя,бы одно значение,параметров г или р не совпадает) или остается в нулевом п