Устройство для вычисления спектра Фурье Советский патент 1984 года по МПК G06F17/14 G06F9/00 

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

2, Устройство ПОП.1, отличающееся тем, что блок формирования шака содержит шесть триггеpdB, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемен И-НЕ и элемент ШЖ, выходы первого, второго и третьего триггеров соединны с первыми входами соответственно первого, второго и третьего сумматоров по модулю два, выходы которых соединены соответственно с первым, вторым и третьим входами первого

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

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

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

. Изобретение относится к вычислительной и информационно-измерительной технике и может быть использован в качестве специализированного вычис лительного устройства для спектрального анализа временных процессов и имитации случайных процессов с заданными спектральными характеристиками в вычислительных комплексах для испытания изделий новой техники на вибрационные воздействия а также в навигационных и радиолокационных системах слежения и обнаружения. Известно устройство для вычисления коэффициентов разложения временного процесса в ряд Фурье посредство БПФ,содержащее регистры, блок умножения, сумматор и коммутаторы 13. Недостаток известного устройства невозможность получения спектральных характеристик Фурье непосредственно из спектральных характеристик Уолша. Наиболее близким к предлагаемому является устройство для вычисления спектра мощности Фурье, содержащее регистр, блок сравнения, первый, второй и третий счетчики, первый и второй блоки памяти, блок формирования адреса, первый и второй дешифраторы, первый и второй шифраторы, блок умножения, сумматор, коммутатор .блок управления, блок вычисления коэффициентовспектра мощности Уолша, блок селекции, блок формирования кода Грея, первый и второй элементы ИЖ, причем выход первого шифратора подключен к установочному входу первого счетчика, вькод которого подключен к входу первого дешифратора и первому входу блока формирования адреса, выход которого подключен к адресному входу первого блока памяти, выход первого блока памяти подключен к первому, а выход второго блока памяти - к второму входу коммутатора, выход которого подключен к входу блока умножения, выход блока умножения подключен к входу сумматора, выход второго счетчика подключен к адресному входу второго .блока памяти, выход ре-у гистра - к первому, а выход третьего снетчика и второй выход блока. формирования адреса - к второму входу схемы сравнения, первый выход блока управления подключен к счетному входу первого счетчика, второй выход блока управления к управляюшрм входам первого и второго счетчиков и сумматора и счет- ; ному входу второго счетчика, первый выход блока управления подключен к выходу схемы сравнения, а второй выход - к переключающему входу : коммутатора и упЬавляющему входу блока умножения, установочный вход третьего счетчика, вход регистра и первый вход второго блока памяти являются входами устройства, вход блока для вычисл ения спектра мощности Уолша является дополнительным ВХОДОМ устройства, а выход подключен к второму входу второго блока памяти, вход второго дешифратора подключен к выходу третьего счетчик выход - к входу первого и первому входу второго шифратора, выход которого подключен к установочному входу второго счетчика, выход которого подключен к второму входу второго шифратора, входу первого элемента ИЛИ и входу блока фор Ф1рования кода Грея, выход которого под ключен -к первому, а выход первого дешифратора - к второму входу блока селекции, выход которого подключен к третьему входу блока формирования адреса, выход первого счетчика подключен к входу второго элемента ИЛИ, выходы первого и второго элементов ИЛИ - соответственно к треть му и второму входам блока управления fZ.. Однако с помощью известного устройства спектральные коэффициенты Фурье из спектральных коэффициентов Уолша анализируемого временного процесса вычисляют с низким быстродействием. Цель изобретения - повьш1ение быс родействия устройства путем уменьше ния числа операций умножения и сложения при вычислении нескольких коэ фициентов Фурье, имеющих номера которые относятся к одной и той же. совокупности номеров. Сущность изобретения заключается в цифровой обработке кода номера вычисляемого коэффициента Фурье, а также кодов вектора-столбца коэффициентов Уолша анализируемого дискретного вре: генного процесса с целью его преобразования в значение коэффициента Фурье путем последо эательного умножения на несколько так называемых факторизованных матриц спектрального образования Уолша-Фурье, в которых число ненулевых элементов примерно в Nf, меньше чем в самой матрице спектрального преобразования. Г, Таким образом, реализуется быстрый алгоритм спектрального преобразования коэффи1щент разложения временного процесса из базиса Уолша в базис Фурье. Поставленная цель достигается те что устройство, содержащее первый блок памяти, информационный выход которого соединен с первым входом коммутатора, элемент ИЛИ, выход ко784 . торого подключен к первому входу блока умножения, выход которого подключен к входу накапливающего сумматора, блок управления, первый, второй, и третий счетчики, селектор, первый выход которого подключен к установочному входу сдвигового регистра, выходы разрядов первой группы которого соединены с входами соответствующих младших разрядов адреса второго блока памяти, информатщонный выход первого счетчика соединен с информационным входом сдвигового регистра, блок сравнения и регистр, информационный вход которого .является входом задания номера коэффициента устройства, введены переключатель, третий, четвертый и пятый блоки памяти, блок формирования знака и преобразователь прямого кода в дополнительный, выход которого подключен к установочному входу второго счетчика, информациониьш выход которого соединен с адресньми входами третьего и четвертого блоков памяти, информа1щон- ные выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, информационный выход регистра соединен с первым входом селектора, второй выход которого соединен с первым входом блока формирования знака, первьм вхрдом блока управления и вторым входом коммутатора, первый и второй выходы которого соединены с информационными входами соответственно третьего и четвертого блоков памяти, входы разрешения считывания которых подключены соответственно к первому и второму выходам блока управления, третий выход которого соединен с первым управляющим входом блока умножения, второй вход которого подключен к информационному выходу первого .блока памяти, вход разрешения считывания которого объединен с вторым управляющим входом блока умножения и соединен с четвертым выходом блока управления, пятый выход которого соединен со счетным входом третьего счетчика, выходы разрядов которого подютючен к второму входу блока формирования знака, входам соответствующих старших разрядов адреса первого блока памяти и управляющему входу сдвигового регистра, выходы разрядов второй группы которого соединены с третьим входом блока формирования знака, выход которого подключен к третьему входу блока умножения, шестой выход блока управления подклю чен к входу обнуления третьего счетчика и входу обнуления пятого блока памяти, информационный выход которог является информационным выходом, устройства и соединен с третьим входом коммутатора, четвертый вход которого объединен с вторым входом блока управления., первым входом блока сравнения и подключен к первому выходу селекто ра, третий вькод которого соединен с установочным входом первого счетчи ка, вторым входом блока сравнения и входом преобразователя прямого кода в дополнительный, управляющийвход которого подключен к выходу блока сравнения, управляющий вход которого объединен с управляющим входом селек тора и подключен к седьмому выходу блока управления, восьмой выход кото рого соединен с входами обнуления первого и второго счетчиков, управляющие входы которых объединены с уп равляющим входом третьего счетчика и подключены к девятому выходу блока управления, десятый и одиннадцатый выходы которого соединены со счетными входами соответственно первого и второго счетчиков, двенадцатый , и тринадцатый выходы блока управления соединены соответственно с первы и вторым управляющими входамикоммутатора, а информационный вход первого блока памяти соединен с выходом переключателя, вход которого является информационным входом устройства, второй выход бпока управления подклю чен к входу обнуления накапливающего сумматора и входу разрешения записи пятого блока памяти, адресный и информационный входы которого соединены соответственно с информационным выходом первого счетчика и выходом накапливающего сумматора, причем f блок управления содержчт первый и второй регистры, первый и второй эле менты задержки, первый и второй узлы сравнения, генератор тактовых импульсов, первый и второй дешифраторы первый и второй счетчики, первый, второй и третий триггеры, первьй, второй третий и четвертый элементы И, группу элементов ИЛ1, элемент И-Н причем выходы первого и второго элементрв задержки соединены с инфор мационными входами соответственно первого и второго регистров, информационные выходы которых соединены с первыми входами соответственно первого и второго узлов сравнения, выходы которых подключены соответственно к первому и второму входам элемента И-НЕ, выход которого соединен с первым входом первого триггера, прямой и инверсный выходы которого подключены к первым входам соответственно первого,и второго элементов И, выход которого подключен к счетному входу первого счетчика, информационный выход которого подключен к входу первого дешифратора, выход первого элемента И подключен к входу второго триггера, первому входу третьего элемента И и.первому входу генератора тактовых импульсов, первый и второй выходы которого подключены к счетному входу второго счетчика, информационный выход которого соединен с входом второго дешифратора, информационный выход первого регистра соединен с вторым входом генератора тактовых импульсов, выход окончания работы которого подключен к второму входу первого триггера, первый вход четвертого элемента К объединен с входом третьего триггера и вторыми входами пе первого и второго элементов И и является тактовым входом блока, инверсный выход третьего триггера подключен к второму входу четвертого элемента И, выход которого является двенадцатым выходом блока, вход пзрвого элемента задержки и второй вход первого узла сравнения объединены и являются первым входом блока, а вход второго элемента задержки и второй вход второго узла сравнения объединены и являются вторым входом блока 5 выходы первого и второго дешифраторов и выход третьего элемента И соединены с входами соответствующих элементов ШШ группы, выходы которых являются первым, вторым, третьим, четвертым, пятым, шестым, восьмым, девятым, десятым, одиннадцатым и тринадцатым выходами блока. Блок формирования знака содержит шесть триггеров, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемент И-НЕ, и элемент ИЛИ, выходы первого, второго и третьего триггеров соединены с первыми входами соответственно первого, второго и третьего сумматоров по модулю , выходы которых соединены соот7ветственно с первым, вторым и третьим входами первого элемента И, выход которого соединён с первым входом элемента И-НЕ и первым входом второго элемента И, выход котор го подключен к первому входу элемента ИЛИ, выход которого соединен с первым входом третьего элемента И, выход которого является выходом блока, выходы четвертого, пятого и шестого триггеров соединены с пер выми входами соответственно четвертого, питого и шестого сумматоров по модулю два, выходы которых подключены соответственно к первому, второму и третьему входам четвертого эле.мента И, выход которого соеди нен с вторым входом элемента Й-НЕ и nepBbiM входом пятого элемента И, выход которого подключен к второму входу элемента ИЛИ, третий вход которого соединен с вь1ходоМ элемента И-НЕ, второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока второй вход третьего элемента И является вторым входом блока, вторые входы первого, второго и третьего сумматоров по модулю два объединены с вторыми входами соответственно четвертого, пятого и шестого сумматоров по модулю два и являются третьим входом блока. На фйг,1 приведена блок-схема устройства для вычисления спектра Фурьер на фиг.2 - временная диаграм блока управления; на фиг.З - схема селектора; на фиг.4 - схема блока управления; на фиг.З - схема перекл чателя; на фиг.6 - схема блока форм рования знака. Устройство содержит (фиг.1) вход 1 устройства, переключатель 2, блок .3-7 памяти, блок 8 умножения, накап ливающий сумматор 9, счетчики 10 и 11 ,регистр. 12, счетчик 13,пр.еобразователь 14 прямого кода в дополнительный, блок I5 сравнения,коммутато 16, селектор 17, сдвиговьй регистр (блок формирования адреса) 18, блок 19 формирования знака,элемент ИЛИ 2 блок 21 управления, вход 22 и выход 23 устройства. Возможный вариант построения схе мы селектора приведен на фиг.З, Селектор содержит регистр 24, сдвиговый регистр .25, элемент И 26, тригг ры 27 и 28 с раздельными входами, счетчик 29, а также мультиплексор 88 30, управляющий вход 31 на запуск блока, вход 32 двоичного кода коэффициент Фурье 1, выход 33 кода параметра р (признак четности или нечетности коэффициента Фурье, причем, если , коэффициент косинусный, если - синусный), выход 34 кода г (номер совокупности (блока), к которому относится коэффигшент) и выход 35 кода И (номер коэффициента в г-м блоке). Блок 21 управления предназначен для формирования на его 13 выходах в соответствии с заданными п,г,р требуемой последовательности управляющих импульсов (она изображена на фиг.2 для случая , ) и содержит регистры 36 и 37, элементы 38 и 39 задержки, узлы 40 и 41 сравнения, генератор 42 тактовых импульсов, триггеры 43-45 с раздельными входами, элемент И-НЕ 46 элементы И 47-50, элементы ИЛИ 51-60, группы, деимфра- . торы 61 и 62, ,ч также счетчики 63 -И 64. Вход тактовых импульсов обозначен буквами ТИ, Переключатель 2 предназначен для перетасовки вычисленных коэффициентов Уолша к виду, необходимому для их умножения на факторизованные матрицы. На фиг.5 изображена схема коммутации входов СС j/J и выходов {с. переключателя2 для в соответствии с табл.1. Блок 19 формирования знака предназначен для формирования знака, элемента факторизованных матриц спектрального преобразования для четных (косинусных) коэффициентов в зависимости от положения элемента в матрице и ее номера и содержит триггеры 65-70, сумматоры по модулю геры 65-70, сумматоры 71-76 по модулю два, элементы И 77-81, элемент НЕ 82, элемент И-НЕ 83 и элемент ИЛИ 84. Входы кода номера факторизованной матрицы i обозначены позицией 85, входы кода номера элементов Ев 1 -и факторизованной матрице - 86, вход параметра р-87, выход блока р- 88. Блок 8 умножения имеет три входа сомножителей х,у,р, участвуюищх в умножении и может работать в двух режимах. Если задействован один управляющий вход, то производится умножение сомножителей в соответствии с выражениемX V I если р 0 X , если Если задействован другой управляющий вход, то независимо от того, что поступает на остальные входы, умножения не происходит, а код сомножителя с входа поступает на выход блока 2 X . Алгоритм функционирования устрой ва можно описать следующим об15азом, Все соответствующие элементы матриц спектрального преобразования (табл.1 и 2) равны по модулю КеНПз -(|-) У половины из общего числа элементов Г и Г знаки одинаковы, а у остал1гной половины противополож ны. При перестановке строк и столбцо матриц Г по описанному нкихе алгоритму удается привести их к так называемому блочно-диагональному виду. При этом отдельные спектральные составляющие как в базисе Фурье, так и в базисе Уолша, объединяются в п совокупностей (блоков) . Спектральные составляющие Фурье, относящиеся в любой г-сово купности (их число составляет зависят только от спектральных составляющих в базисе Уолша относящихся к этой же совокупности Благодаря этому свойству можно вычи лять отдельные спектральные составляющие, принадлежащие разным совокупностям, независимо друг от друга Все без исключения элементы в ме щих блоках с номерами имеются в самом большом блоке с номером г ОГ / 45 %t ,2 S ,5 1,2 Ь 2, Матрицы и имею блочно-диагональный вид, для N 32 изображены в табл.3 и 4. Таким образом, все основные стр турные свойства матрицы Г полност определяются свойствами их основного блока ( -г 1). Введем следующие обозначения: -совокупность элеD4/iir,M ментов h-ro блока вектора Б ; , -совокупность элементов блока вектора Ег с Т VJ -совокупность sineГ Ju, ментов блока матрицы Г- j, г L f I Г ir (O.vtf -совокупность элеI о I U v l V J ментов r-ro квадратного блока матn-f-i рицы Г ; -совокупность элементов г-го блока вектора А, -совокупность эле-К Гг. ментов г-го блока вектора В. Исследования показали, что у каждого блока матриц г .h. имеется свойство пропорционального соотношения между элементами различных столбцов. Используя это свойство, можно представить любой блок матриц Г,Г размернрстью 2 2 в виде произведения n-t-- сильно разреженных нулевыми элементами матриц. г г г Если Г.тг (а)( -совокупI 1 И ,1 ность елементов г-го квадратного блока f-и факторизованной матрицы г г-г о .п-г-25г 5, 5, Г г„ г Здесь число ненулевых элементов в исходной матрице Г уг 1 число ненулевых и неединичных элементов в матрицах Г..., 2 , а в матрице Г . Общее число ненулевых и неединичных элементов в матрицах Г0 I-( составляет таким образом (п-г)-2 2 VeHbше, чем в самой Матрицы ,г;/, для представлены в табл.5-7. Таким образом, для умножения в и вестном устройстве для г-го блока необходимо 2. операций, в то вре мя как умножение на правую часть . тождества (3),которое может совершаться по итерационному алгоритму (А) за n-r-l итераций, требует в общей сложности лишь (п-г)-2 ум ножений, т.е. в 2 1Д меньше, чем в прототипе: 1 1, п-г-2 , где).|(. (e)|g - совокупность эл ментов г-го блока вектора коэффициентов D после i -и. итерац .h-r-l. ; - совокупность элементов I -го блока вектора коэффициентов Е после 1-й итерации. Обозначим элементы факторизован ных матриц следующим образом: 0.2 , 1, W risJM Я-( i 1,n-3-, Свойство (2) позволяет исполь-. зовать элементы первого блока матр Q для выполнения умножений в блока 2,3,...h (} {гГ} . i ,n-3 i т п--1 (5 r Че).,Г( Лишь матрицу Q 2 ребуется. хранить в полном объеме - N/2 коэффициенто из них в первом блоке N/8, во вт ром N/16 в третьем и т.д. (4 812 Для вычисления четных (косинусных) спектральньк составляющих можно воспользоваться значениями для нечетных элементов матриц составляющих. Неединичные элементы матриц Гр |Г I iЗ,n-3 равны по модулю. Чтб касается знаков, то для матриц Г.... , Г.а эти знаки всегда противоположны. Г, (с)-у.Че), r -f,n-i ; ,2 Если Е 2 , то у элементов йц-чпо сравнению сQ.;, знаки менять нужно, а yQn-2 нужно. Если же g . то у элементов S р. знаки менять не нужно, а У S.j нужно. В результате спектрального преобразования по (4) вектор-столбцы А,В будут двоично перетасованы. Поэтому чтобы ползтаить коэффициенты Фурье в естественном порядке следования, необходимо массивы коэффициентов перетасовать по закону двоичной ид версии. Быстрый алгоритм преобразования коэффициентов Уолша в коэффициенты Фурье, который используется в данном устройстве.записывается следующим образом. 1. Разделение (N-1) спектральных коэффициентов Уолша С;Д на две N i N части четных и -j- нечетных коэффициентов, а внутри каждой части - разделение на i блоков в соответствии с номером первой справа единицы в двоичном представлении номера j Для упорядочения функций Уолша по Пэли эти операции могут производиться следующим образом. Пусть Т - двоичный эквивалент (код) номера j . В процессе поразрядной логической обработки производится вычисление параметров Р , номера первой единицы в коде, считая со стороны старших разрядов, и логической переменной Если , то функций нечетная, если 8 0, то четная. В соответствии со значениями f формируются блоков коэффициентов и п-1 блоков четньос. Зйтем производится 13. перестановка коэффициентов в каждо группе в соответствии с алгоритмом двоичной инверсии их номеров С в этом блоке (нумерация начинается с 0) . Например, для N 16 приведена табл.8 для перетасован-, ного массива коэффициентов Уолша c.,V L 3) . 2. Непосредственное вычисление k-ro коэффициента Фурье. Вначале в ходе логической обработки кода 1 определяются значения параметров р,г,1 по следующему алгоритму. Значение :амо го младшего разряда в коде k определяет значение р. Если обозначить через k, ((1-1)-разрядный код, образованный отсечением у кода х самого младшего разряда то номер первой по счету единицы в этом коде, считая справа, определяет значение параметра - . Если обозначить через (пч н}-разрядный код, образованный из кода k отсечением первой справа единицы и всех нулей (если они есть), следую 1ЦИХ после этой единицы справа, то значение определяется двоично-инверсным кодом 2 Например, если , а 1 011101, то Р 1 коэффициент косинусньй (четный); 1,0it10; - номер блока; - номер коэффициента в 2-м бло ке; е 110. Тогда значение кoэффиц ieнтa {oj или Ь определяется из значений только четных (при ) или нечетн (при ) коэффициентов г-го блока и может быть вычислено с пом щью следующих выражений (см.конфигурацию матрицГ ,r в табл. 5-7); (е)ч:(П,(т)е;.), г-2„., е;(е)(е)..Д.2 -|,, , 1 C i,n-r-2 .-., .г - -Чч-е, p.2 - 814в случае нечетных коэффихи ентов.и ciiU)n)() .иЬя;(е).д.)..Г), ; i l,n-r-2 C., ..() в случае четных коэффициентов. Значения (2) могут быть получены из значений коэффициентов (С) (т.е. относящихся к первому блоку) в соответствии с выражениями (5), (6). Таким образом, для вычисления всех коэффицициентов Фурье, относящихся к г-му блоку, требуется (п-г) 2 умножений и сложений. Для вычисления одного коэффициента Фурье с заданным номером k требуется (п-г-2) 2 умножений и сложений для выполнения вычислений по (7) и два умножения и одно сложение для выполнения (8). Всего, таким образом, необходимо (п-г-2)х 2П-г-1 2 умножений и сложений. Устройство для случая г 6, , работает следующим образом. В начальный момент времени в блоке 3 памяти записаны 2 -1 коэффициентов Уолша 2 коэффициентов и Ср, которые поступают с информационного входа устройства и перетасовываются с помощью переключателя 2 по описанному выше алгоритму. В блок 6 памяти записаны элементы первых блоков матрицЙ,...|й и все п блоков матрицы Q,.. Все счетчики и сумматор 9 обнулены. На регистре 12 установленоочередное значение номера коэффициента Фурье к, подлежащего вычислению. Номера коэффициентов могут устанавливаться на регистр либо сл айным образом, либо в определенном порядке. Наилучшее использование устройства достигается, если коэффициенты устанавливарстся в порядке, соответствующем двоично-инверсным кодам от номеров, расположенных в натуральном порядке: ,6,1,5,3,7 (при ). Тактовые импульсы начинают поступать на вход, блока 21 управления. Блок 21 управления (фиг.4) работает следующим образом. В исходном 15 состоянии все триггеры и счетчики находятся в нулевом состоянии. Первы тактовый импульс проходит через откр ть1й элемент И 47 на выход блока и затем устанавливает в единичное положение-триггер 43, тем самым запира элемент И 47для дальнейшего пропуск тактовых импульсов. По сигналу блока управления селек тор 1 7 производит логическую обработк двоичного кода 1 по описанному вьше алгоритму. В начальном состояни (фиг.З) счетчик и оба триггера находятся в нулевом состоянии. По сигналу на зупуск устройства на регистр 24поступает код iT Значение самого младшего -(n-D-ro .разряда поступает на триггер 28 и устанавливает его в определенное положение, соответст вующее значению параметра р, код tt на регистр 25. Управляющий сигнал поступаюидай на вход 31, .устанавливае триггер 27 в единичное положение, благодаря чему открывается элемент И 26. Тактовые импульсы начинают поступать на сдвиговый вход регистра 25, а счетчик 29 ведет подсчет этих импульсов. До тех пор, пока на вход триггера 27 поступают нули, элемент и 26 открыт и сдвиг регистра продолжается. Первая же единица, поступившая на вход триггера 27, устанавливает его в нулевое состояние, элемен И 26 закрывается сдвиг регистра 25прекращается. На счетчике 29 будет находиться значение кода г, а значение кода и может быть считано с выхода регистра 25 с после дующим его двоичным инвертированием что обеспечивается соответствующей настройкой С1.лзей входов и выходов в мультиплексоре 30. Значения параметров г, р поступают на входы блока 21 управления и сравниваются (фиг.4) со значением этих же параметров, которые обрабатывались на предьщущем цикле работы устройства при старом значении 1, В зависимости от результата сравнения триггер 44 устанавливается либо в единичное положение (если хотя,бы одно значение.параметров г или р не совпадае.т) или остае ся в нулевом положении . (если оба значения параметров совпадают), После этого новые значения г, р задержавшись в элементах 38 и 39 за держки устанавливаются в регистрах 36 и 37. 816 Если старые и новые значения параметров совпадают, то это означает, что в блоках 4 и 5 памяти (фиг.1) содержатся необходимые для вычисления коэффициента Фурье с текущим значением номера V- значения векторов Df,.(. п-г-2 блок 21 управления вьщает в дальнейшем такую последовательность управляющих импульсов, которая на фиг.2 соответствует моменту времени 1У и далее. Рассмотрим случай, когда текущие значения | р не совпадают с предьщущими, что означает, что триггер 44 (фиг.4) находится в единич- . ном состоянии, т.е, на выходах блока управления появляется последовательность импульсов, полностью соответствующая фиг,2. В этом случае тактовые импульсы (фиг.4) начинают поступать на генератор 42 тактовых импульсов, элемент И 50 и триггер 45, Импульс пройдет через открытый элемент И 50 и выйдет на соответствующие выходы. Этот же импульс переведет в единичное состояние триггер 45 и элемент И 50 в дальнейшем будет закрыт. Генератор 42 предназначен для выдачи (n-t-2)2 +1 тактовых импульсов по первому своему выходу и (h-r--2) импульсов по второму выходу (через каждые выдаваемых по первому выходу) для сброса счетчика 64 в нулевое состояние.Благодаря этому на выходах дешифратора 62 будет появляться последовательность импульсов, соответствующая временному интервалу 1-Ш на фиг,2, и эта последовательность импульсов будет повторена (h-p-2) раз. Имеющаяся на фиг.2 картина на выходах блока управления получается благодаря соответствующему соединению выходов дешифратора 62 с входами элементов ИЛИ 51-60 группы. На вькодах дешифратора в момент прихода очередного импульса на тактовый вход генератора будет возбуждаться только одна из его выходных шин. На фиг..4 показаны соединения только первых его четырех шин и последняя 17-я, в то время, как для случая , у дешифратора должны быть задействованы выходы всех первых 17 шин, которые соединены с входами элементов ИЛИ 51-6Q группы. После выдачи последнего ( п-г-2) )-го импульса генератор выда17ет сигнал конца своей работы, который перебрасывает триггера 44 в нул вое положение. Этому моменту времени соответствует точка 1У на фиг.2. Как уже отмечалось, триггер 44 може находиться в нулевом состоянии и по ле прихода первого тактового импуль са на вход блока из-за несовпадения старых и новых -начений г, р. По сигналу блока управления в блоке 15 сравнения производится сра нение кодов и устанавливается соответствующее значение на выходе преобразователя 14 прямого кода в допо нительный в соответствии с (1). По сигналу блока управления с помощью коммутатора 16 производится перезапись Z значений четных (при. ) или нечетных (при ) коэффициентов Уолша г-го блока из блока памяти в блоки памяти 4 и 5 таким образом, что первые значений подряд заносятся в блок 4 памяти а оставшиеся 2 значений - в блок 5 памяти. По сигналу блока управления прои водится суммирование единицы в счет чик 11 матриц . его содержимое становится равным 1. По импульсам из блока управления к содержимым счетчиков 10 (параметр tn) и 13 (параметр 2 ) добавляется по единице, они становятся равными 1. По сигналу блока управления из блока 4 памяти выбирается значение адрес которого соответствует содержимому счетчика 10, которое че рез элемент ИЛИ 20 поступает на вход блока 8 умножения. По сигналу с блока управления производится выборка значения (i из блока 6 памяти. Его адрес слагается из двух кодов -номера факторизованной матрицы 1 определяемого содержимым сче-i -{ика 11, и кода номера в I-м блоке 1-1 матрицы, определяем го содержимым счетчика 13. Сдвиговый регистр 18 производит формирование физического адреса для работы блока 19 и блока 5 памяти. Его работу можно описать следующим образом. Если поступаюищй на третий вход блока код номера факторизованной матрицы 1 не равен п-2, то код номера в факторизованной матрице, поступившей на вход сдвигового регистра i8. сдвигается в соответст ВИИ с (5) на г-1 разрядов влево 8 . 18 и вьщается на первый и второй выходы. Значение /-. поступает на вход блока 8 умножения. В случае вычисления четных коэффициентов Фурье блок 19 формнрования знака формирует значение логической переменной f , Блок 19 работает следующим образом. В начальном состоянии (фиг.6) в триггеры 65-67 записан код 101 (соответствующий ), а в триггеры 68-70 - код 100 (соответст , вуютций ). с помощью сумматоров по модулю два осущес- вляется определение признаков О , Го, if п-2 Pi . -а 1 I U , i п-2 Старший разряд кода Г о ределяет логическую переменную О, 1 , 2 Остальные элементы сх-омы реализуют логическую функцию р в соответствии с табл.9, которая, в свою очередь, следует из описания алгоритма формирования знаков матриц Q9 , П-1 описанного выше. При всех остальных комбинациях РЗ Р должно быть равнь м 0. Значение j устанавливается на входе блока 8 умножения (фиг.1). Поскольку задействован другой вход блока умножения, то производится умножение O H/i), Р-0 (1(. Р--1 , Значение Z поступает на вход сумматора.9-и суммируется с его содержанием (т.е. с нулевым кодом). По приходу управляющих импульсов с выходов блока управ:1ения производится выборка значений Qj-i+ii из блока 5 памяти с тем же адресом, определяемым счетчиком 10, Это. значение -из-за того, что у блока умножения задействован соответствующий вход, передается на выход умножителя и поступает на вход сумматора, где происходит суммзгрование по (9) . Сфор№рованная сумма d (1) передается на вход блока 7 памяти и записывает ся по адресу, определяемому содержимым счетчика 13. Сумматор обнуляется В дальнейшем на выходах блока управления появляются управляющие импульсы. При этом производятся действия, аналогичные описанным, с той разницей, что содержимое счетчика 10() не изменяется, и на вход блока умножения поступают те же значения ) и (Зд (5), а из блока 6 выбирается новое значение ск (з) по адресу,- определяемому новым (равным 2) содержимым счетчика 13. По адресу 2 в блек 7 памяти будет за:писано новое значение cJ (гЬ Тем самым к моменту времени П реа лизовано умножение элементов вектора D о на первые две строки матрицы ui( е 1,2). В дальнейшем на последующих такта вплоть до момента времени III (фиг.2) производятся аналогичные действия, В результате к моменту времени Ш в блоке 7 памяти будут сформированы восемь значений первого промежуточного вектора И . По приходу управляющих импульсов из блока управления содержимое блока 7 -памяти переписывается через коммутатор 16 в блоки 4 и 5 памяти, перва половина (первых четыре элемента) в блок 4, а остальные четыре элемента - в блок 5. К содержимому счетчи 11прибавляется 1 и оно становится равным , Счетчики 10 и 13 обнуляются. В дальнейшем производится умножение вектора 2 на матрицу, номер которой соответствует содержимому счетчика 11. Описанные ранее действия повторяются без всяких изменени и в результате к моменту времени 1У в блоке 7 памяти будут сформированы восемь значений второго промежуточного вектора К этому моменту времени триггер 44 в блоке 21 управления (фиг.4) находится в нулевом состоянии. Поэтому открывается элемент И 48 и тактовые импульсы начинают поступать на счетчик 10 и дешифратор 61. Благодаря сделанным соединениям выходов дешифратора 61 с входами эл ментов РШИ 51-60 группы на выходах блока управления появятся упраъпяющие импульсы (фиг.2) после момента времени .1у. По импульсу блока управления в счетчик 11 номеров факторизованных матриц заносится код, десятичный эквивалент которого равен что соответствует подготовке- к умножению на матрицу Q -г счетчик 13 заносится значение Р соответствующее строке матрицы Qп-2 на которую необходимо умножать вектор Б В счетчик 10 заносится значение m по (2), которое было получено на выходе преобразователя прямого кода в дополнительный, управляемого блоком сравнения. По импульсам, поступающим с выходов блока управления, производится выборка соответствующего значения которое через элемент ИЛИ 20 поступает на соответствующий вход блока умножения. В соответствии со значениями р и содержимым счётчиков 11 и 13 на соответствующие входы блока умножения поступают значения g..p. При этом следует отметить, что благодаря особенности матрицы Q г,2 работа сдвигового регистра 18 при 1 п-2 происходит особым образом. На выход сдвигового регистра 18 так же, как и при i п-2, поступает сдвинутьш на г-1 разряд влево код . На другой выход сдвигового регистра 18 поступает составной -разрядный код адреса в матрице Q п-г. Старшие j o 2 разрядов этого кода составляет код номера блока г в матрице, а млад;шие n-jfog-jrf- разрядов - код не сдвинутый на разрядов.Такое строение кода адреса позволяет адресовать N/2 элементов матрицы разделенной на п блоков размерностями соответственно N/4, N/8,.. В блоке 8 -умножения задействован соответствующий вход, поэтому производится умножение 2 S . Р ° я./(1 , р- . результат 2 поступает на вход сумматора. По импульсам с выходов блока управления к содержимому счетчика 11 матриц добавляется 1 и оно становится равным П -1. Производится выборка (. - значения вектораЛ из блока 5 памяти, которое через 21 элемент ИЛИ поступает на соответствуюгций вход блока умножения. На выходах блока 19 и блока 6 памяти появляются соответствующие значения р,|(Р)-Так как у блока 8 умножения задействован соответствующий вход, то производится умножение сомножит телей Г . So d:lmH)o {{)) . р 0 2 2 -с/„ (т-«-4)с, 2 и значение z поступает - на вход су тора, где реализуется вычисление значения в соответствии с (10). Сф мированное значение записывается по адресу в блок 7 памяти. Это значение представляет собой значени коэффициента Фурье с номером fc. По сигналам из блока управления производится выборка, по адресу определяемому содержимым счетчика 13 из блока 7 памяти значения коэфф циента Фурье, и передача его на выход 23 устройства. Производится обнуление счетчиков 11,13 и 10. Уст ройство готово к следующему циклу работы по вычислению нового значени 8 коэффициента Фурье с новым номером к При этом сохраняются значения вектора D, находящиеся в блоках 4 и 5. памяти. Затраты времени на вычисление коэффИ1щента Фурье по-заданным коэффициентам Уолша с помощью предлагаемого и известного устройств приведены в табл.10. Таким образом, при вычислении подряд с помощью предлагаемого устройства коэффициентов Фурье, ОТНОСЯ1ЦИХСЯ к одному I-му блоку, требуется в меньще операций умножения и сложения по сравнению с устройством-прототипом, что и определяет его преимущества.по быстродействию. Например, при п 10 2, это преимущество составляет 16 раз. С помощью предлагаемого устройства можно вычислять спектральные коэффициенты Фурье и по заданным коэффициентам разложения временного процесса в базисе интегральные кусочно-линейные функции Уолша, образованные интегрированием функций Уолша.

гО

Ь о

0

m о

о

ъ

СУ

Ю

S сг

CVI

сг

О

с5

cvj lO

О I

D

CTV

ii

ч о CM

oT

I

Cvi

o

-T О

3 rj

3

т о

p

9 cr

rv CS

cf

o

I

.э

lO

rn S

rt cx 0

CT

I

o о

J

o

«o

g

CJ

HI rO

СГ

o

or

СГ

1

чЛ fO

во

t

o

«o c

CVJ

Xo

O

I

r

o

tC v Ю O

C4

о

О

04

cr«

vj

о

.jr

5 D

s

rO

o

O

oч5

CM

Ю

r

s

и

0

cs

о

CO

о

ос

vA

j: J5 о

OJ о cf

о

CM

K)

c- CM «чг М Ю .qr О чО t 00 «У О Ij; CJJ

о

о

Сч

см

О О

о

J

o

Г2

Ю O

O O

CN Ю

C5

ci

S C3

M

E

Й

Й

f Cf

Oc:5«« CJ

«ХЭ

О О

S

ч«X

Cvl

Cf

o

сГ

CJ

t- CM

S

to

о о

с ;

О

О kl

о

ОС }

vj

o

C3

о

or

vj

Ю

ем o

o

I

OJ

oЮ vo jr -jf , .

« rO

tr к

4 Ю Ю «

H .

s

JO

См

О

су

о ем «г.

IО

о

и

сг

сУ

см

и «

и

О

CJ

ъП

р - ю м cf

см

о

р.

Я о

eg

ю

V

rj

;5

«

см

м

р

м

«

о

s

cr

t S

о

CM no Ю Ю

Рч

о or

«о о

Kl

О

о

I

о о

о

%

vO

Ci

)

47

o

-гг t

«N Ст.

tr. vB

Ю

S

Cvj

cS

oо

or

oo

1

v3

o

- я

акз

ГМ fM lO СГ

«KJ СЭ

t о оr)

..

э Ю

o

O

о

О

о

О

kO

;Я

«г

о о

.аSс rv

S

о о

ГМ

О

оГ

О

о

CJ

ю «

С5

о

«

Ю4О

о

vi

о

S

и

J

VA

CJ

о о

С4

«

о

cf

о о

I

OJ

г г

;.

CV

CSJ чл

vO X;; -1

i; е

ч9 О О

Ч) кч о

О CSi

С е;У

от

cr

СГ

сг

I

I

p

CN

t4J

fj

V

tC4CN oS-O

O

«

lo

vj(

«v

5

oCS

«3O

O

tr

-.T

§ 1

cw

о сэ cv cr

aСГ

cr O

t

fO

с

чЛ S

|0

о

Тч

о

ю с-1

f I

O cu

.

jn

Ю eV

0

bCM

o

о

vf

о-

О

s

Jсм о о

o

чО

сг

о

J3

-s:;:

CSJ

CNJ « о

о 1Л

о

vD

PJ ю ш см

см

б

to

00

ю о

rw

о

со

vj)

fO

t I 10

см о

04

чй

(ч.

-3CNJ

см о 1Г

С5

СМ

и

S

о

га

Cs(

Sjl CM CJ vO ЧГ-СУ Л:2Ю;р J4. О

Otf «

о

vB

o о

О

«ю

eo

oIсъ

t- o o

:

О

CM

CM

I

4J

o

«э сэ

t o

ro O

OT

O

0

I

1

ХЭ

о

vS

о

e

CM

r- 3 o

о о

« h«о tn 4}

fcj

«о

S О

см о ro

va o

О

о

cjO

С)

I

I

чО

5;з

O cr о

о

1 о сг

u- c

CM

io

Kl гО

IT)

c

cT

o

-TI

i5

«ю

о

vD

iC

Q О

cv

jr

«о ю

CM О

о a

ем о

СЗ

o

o

о

Cvj

oo Ю

eo

и

S «o

S

lO

О

t «о

To

t- o

ev O

о о

о

00.

V.O

СМ

%r

5 t о

CVJ

in

К1

.

чО О

: о «3

S ОО Оч

CT rf)

о

О

сз

во

ю

CM

оо

ХЗ

vj см tj«

CW

D

ii

ОО

V

гО

«Э

О

О

XJ

:

JчЗ

KJ

00

о т-Jи-

S «ч;

LO

См

Of

« 3

и

,: e

c« H

« NJ

55:

:

ЧО «M

SJ

O

в

s

«rw

СГ

o

jr

Ч

«A

oCM

ii o

cr

h ev Ю

«M

о

g

CV

«V

.Jf

o

fr00СЧ1

CM

sO

s e ем e

o о СЧ

o c

M

cf

o о

Pi os

b.

о о

cf

о

o

so

О

о ем

o

&

s 3

СЭ

cr

cr

о

2C « J

er «r sp

vo

1 lO

a. s

0

Ю,

rt H

.

O CM

co«arCicMSoSI Qr OC3O2:C i 2

vJ

,

ol r

- O

«41

CM

jr

ЧCJ

«M

еч

CxJ

« HS

tf is

IO|

Ч H

i

«n

CM

o

CNJ CW

CM

CJ

r

jr

V

. O

r.

)ipio5:

CM vD

cr

iC

«Г

«v

2

N e cr

v49

JT

r

«r

&

Й

CM

.7 o

t-- iO

2{n- -tJ

n-r-l

(n-r)2

Таблица 8

Таблица 10

(n-r-2)2 - -+2

16

ft W f 3

«

8JV2f

Ipg

i

f5

I ;, 5

tfr

3

I I I IT

H

23

2ik 2

3

2/

lnii

19

11

2 ifv

J

ZZ

иг. /

л

ж

Фиг.г

ти

-

26 УЧ

ZV

ъг

27

29

3

25

3ff

35

Z8

33

fue,3