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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН ЗШ 60615 332 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙОПИСАНИЕ ИЗОбРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Ленинградский ордена Ленина электротехнический институт им. В,И.Ульянова (Ленина)(56) 1. Авторское свидетельство СССР 9598085, кл. Ц 06 Р 15/332, 1978,2. Авторское свидетельство СССР 9760115, кл. 6 06 Г 15/332, 1980 (прототип)(54)(57) 1. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СПЕКТРА ФУРЬЕ, содержащее первый блок памяти, информационный вьгходкоторого соединен с первым входом коммутатора, элемент ИЛИ, выход ,которого подключен к первому входу блока умножения, выход которого подключен к входу накапливающего сум-. матора, блок управления, первый, второй и третий счетчики, селектор, первый выход которого подключен к установочному входу сдвигового регистра, выходы разрядов первой гру. пы которого соединены с входами соответствующих младших разрядов адреса второго блока памяти, информационный выход первого счетчика соединен с информационным входом сдвигового регистра, блок сравнения и регистр, информационный вход которого является входом задания номера коэффициента устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены переключатель, третий, четвертый и пятый блоки памяти, блок формирования знака и преобразователь прямого кода в дополнительный, выход которого,.801121678 А подключен к установочному входу второго счетчика, информационный выходкоторого соединен с адресными входами третьего и четвертого блоковпамяти, информационные выходы которыхподключены соответственно к первомуи второму входам элемента ИЛИ, информационный выход регистра соединенс первым входом селектора, второйвыход которого соединен с первымвходом блока формирования знака,первым входом блока управления и вторым входом коммутатора, первый и.второй выходы которого соединеныс информационными входами соответственно третьего и четвертого блоков Ейпамяти, входы разрешения считывания которых подключены соответственно к первому и второму выходам бло- Сффка управления, третий выход которого соединен с первым управляющим Явходом блока умножения, второй вход .которого подключеь к информационному фвыходу первого блока памяти, вход йразрешения считывания которого объединен с вторым управляющим входом мыблока умножения и соединен с четвертым выходом блока управления, пятыйвыход которого соединен со счетнымвходом третьего счетчика, выходы раз-,рядов которого подключены к второмувходу блока формирования знака,входам соответствующих старших разря-.дов адреса первого блока памяти и ф,управляющему входу сдвигового регистра, выходы разрядов второй группы которого соединены с третьим входомблока формирования знака, выход кото-рого подключен к.третьему входу блокаумножения, шестой выход блока управления подключен к входу обнуления678 16 1121 15состоянии все триггеры и счетчики находятся в нулевом состоянии. Первый тактовый импульс проходит через открытый элемент И 47 на выход блока и затем устанавливает в единичное по 5 ложение триггер 43, тем самым запирая элемент И 47 для дальнейшего пропуска тактовых импульсоь.По сигналу блока управления селектор7 производит логическую обработку1 О двоичного кода 1 по описанному выше алгоритму. В начальном состоянии (фиг.3) счетчик и оба триггера находятся в нулевом состоянии. По сигна-. лу на зупуск устройства на регистр 24 поступает код К Значение самого младшего (и)-го .разряда поступает на триггер 28 и устанавливает его в определенное положение, соответствующее значению параметРа Р код М - 2 О на регистр 25, Управляющий сигнал поступающий на вход 31, .устанавливает триггер 27 в единичное положение, благодаря чему открывается элемент И 26. Тактовые импульсы начинают25 поступать на сдвиговый вход регистра 25, а счетчик 29 ведет подсчет этих импульсов. До тех пор, пока. на вход триггера 27 поступают нули, элемент И 26 открыт и сдвиг регистра продолжается. Первая же единица, поступившая на вход триггера 27, устанавливает его в нулевое состояние, элемент И 26 закрывается сдвиг регистра 25 прекращается, На счетчике 29 будет находиться значение кода г, а значение кода 1 может быть считано с выхода регистра 25 с последующим его двоичным инвеРтированием, что обеспечивается соответствующей настройкой связей входов и выходов в мультиплексоре 30.Значения параметров г,р поступают на входы блока 21 управления и сравниваются (фиг.4) со значением этих жепараметров, которые45 обрабатывались на предыдущем цикле работы устройства при старом значении Ъ, В зависимости от результата сравнения триггер 44 устанавливается либо в единичное положение (если хотя,бы одно значение,параметров г или р не совпадает) или остается в нулевом положении (если оба значения параметров совпадают). После этого новые значения г,р задержавшись в элементах 38 и 39 за держки устанавливаются в регистрах 36 и 37. Если старые и новые значения параметров совпадают, то это означает,что в блоках 4 и 5 памяти (фиг.1)содержатся необходимые для вычислениякоэффициента Фурье с текушим значением номера Ъ значения векторовЭ2 или Ег 2.Поэтому блок 21 управ.ления выдает в дальнейшем такую последовательность управляющих импульсов,которая на Фиг.2 соответствует моменту времени 1 У и далее.Рассмотрим случай, когда текущие значения г р не совпадают спредыдущими, что означает, что триггер 44 (фиг.4) находится в единичном состоянии, т.е. на выходах блокауправления появляется последовательность импульсов, полностью соответствующая фиг.2,В этом случае тактовые импульсы(Фиг.4) начинают поступать на генератор 42 тактовых импульсов, элементИ 50 и триггер 45. Импульс пройдетчерез открытый элемент И 50 и выйдетна. соответствующие выходы. Этот жеимпульс переведет в единичное состояние триггер 45 и элемент И 50 вдальнейшем будет закрыт.Генератор 42 предназначен длявыдачи (и-г) 2 + 1 тактовыхимпульсов по первому своему выходуи (п - г) импульсов по второмувыходу (через каждые 2 "выдаваемыхпо первому выходу) для сброса счетчика 64 в нулевое состояние. Благодаряэтому на выходах дешифратора 62будет появляться последовательностьимпульсов, соответствующая временному интервалу 1-И на фиг,2, и этапоследовательность импульсов будетповторена (ь-г) раз. Имеющаясяна фиг.2 картина на выходах блокауправления получается благодарясоответствующему соединению выходовдешифратора 62 с входами элементовИЛИ 51-60 группы. На выходах дешифратора в момент прихода очередного импульса на тактовый вход генератора будет возбуждаться толькоодна из его выходных шин.На фиг,4 показаны соединения только первых его четырех шин и последняя 17-я, в то время, как для случая п =6, г =2 у дешифратора должныбыть задействованы выходы всех первых17 шин, которые соединены с входамиэлементов ИЛИ 51-60 группы.После выдачи последнего ( и-г)х 2" + 1)-го импульса генератор выда121678 22коэффициента Фурье с новым номером кПри этом сохраняются значения векторами, находящиеся в блоках 4 и 5.памяти.5 Затраты времени на вычисление коэффициента фурье по -заданным коэффициентам Уолша с помощью предлагаемогои известного устройств приведеныв табл.10,1 О Таким образом, при вычисленииподряд с помощью предлагаемого устройства 2"коэффициентов Фурье,телей 2 О р,р О 2и значение г поступает на вход сумматора, где реализуется вычисление значения"в соответствии с (10) . Сфор мированное значение записывается .по адресув блок 7 памяти. Это значение представляет. собой значение коэффициента фурье с номером к.По сигналам иэ блока управления 20 производится выборка, по адресу определяемому содержимым счетчика 13 из блока 7 памяти значения коэффициента фурье, и передача его на выход 23 устройства. Производится 25 обнуление счетчиков 11, 13 и 10. Устройство готово к следующему циклу работы по вычислению нового значения 21 1 элемент ИЛИ поступает на соответствующий вход блока умножения. На выходах блока 19 и блока 6 памяти появляются соответствующие значения р, (Д.Так как у блока 8 умножения задействован соответствующий вход, то производится умножение сомножи-. относящихся к одному г-му блоку,и-Г требуется в2.меньше операцийи-г умножения и сложения по сравнениюс устройством-прототипом, что и определяет его преимущества по быстродействию. Например, при и =О,2,это преимущество составляет 16 раз.С помощью предлагаемого устройстваможно вычислять спектральные коэффициенты Фурье и по заданным коэффициентам разложения временного процессав базисе интегральные кусочно-линейные функции Уолша, образованныеинтегрированием функций Уолша,30 1121678 29 ВВ О с О 4 р ь ьС;В1О Э с ОО о ь1 ь1 93 с ФМ МЪ о сО Тф СЧ СЪ тЗф ЛВ Ч ЮД о СМ О О Ч Вф) С) Ф ВВВ СЯ С) О То ВФ ь О СВВ В 3 Эф СВ 4 оООВ фъ ь 1 нъ С) о ОВ ОО Ъ Ю 1Ъ ;В Ю С) 1 о ОВ ВЛ о"ВВ У ОВ ч СЪ УВ о о 1 С,.В ОО ю о ь СМ о 1 ОО НЪ М С С:) ОО 3 Ъ фВ- ь О) ВВЮВ T Ю сОо ОВ ю о ОЯ Ъ В.О ь 1 ОО ВВВ СЪ В ь 1 О 4В; Н) 1 1 ВВЯ о сч М 3 о 1 о Ь(р ИЪ :В,Д ЯЪ Ю УУ В/В Д В ОСВД Сч ф 4 ВВ С Б С Ю Вм :) Сч О.3 х ъВ Сз ВВД СЪ Вфс,9 О 3 Сэ бВВго 4 Г ф ЮВ Ъ Г3 (У о3" РВ ВВЯ С.) МС:ВВ ОС 4 ь с.Д Съ о ООВВ ВВЪ ь 1 ВВВ ВСЭ1 У -4 ВВ С с ч ВВ -В. ь сОЯЮторых подключены соответственно к первому и второму входам элемента И-НЕ,выход которого соединен с первымвходом первого триггера, прямойи инверсный выходы которого подклюно первого и второго элементов И,выход которого подключен к счетномувходу первого счетчика, информационный выход которого подключен к входу первого дешифратора, выход первого элемента И подключен к входу второго триггера, первому входу третьего элемента И и первому входу генератора тактовых импульсов, первый и второй выходы которого подключены к счетному входу второго счетчика, информационный выход которого соеинформационный выход первого регистра соединен с вторым входом генератора тактовых импульсов, выход окончания входу первого триггера, первый входчетвертого элемента И объединен с подклЮчен к второму входу четвертогоэлемента И, выход которого являетсядвенадцатым выходом блока, вход вход первого узла сравнения объединены и являются первым входом блока,и второй вход второго узла сравненияобъединены и "являются вторым входомблока, выходы первого и второго дешифраторов и выход. третьего. элемента И соединены с входами соответствующих элементов ИЛИ группывыходы которых являются первым, вторым, третьим, четвертым, пятым, шестым,.восьмым, девятым, десятым, одиннадцатым и тринадцатым выходами блоха. 2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок формирования знака содержит шесть триггеров, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемент И-НЕ и элемент ИЛИ, выходы первого,второго и третьего триггеров соединены с первыми входами соответственно первого, второго и третьего суммавходами соответственно первого и соединены соответственно с первым,второго узлов сравнения, выходы ко- вторым и. третьим входами первого 1121678третьего счетчика и входу обнуленияпятого блока памяти, информационныйвыход которого является информационным выходом устройства и соединен стретьим входом коммутатора, четвертый.вход которого объединен с вторым чены к первым входам соответствен"входом блока управления, первым входом блока сравнения и подключен к первому выходу селектора, третий выходкоторого соединен с установочным входом первого счетчика, вторым входомблока сравнения и входом преобразователя прямого кода в дополнительный,управляющий вход которого подключенк выходу блока сравнения, управляющийвход которого объединен с управляющим входом селектора и подключен кседьмому выходу блока управления,восьмой выход которого соединен с вхо" динен с входом второго дешифратора,дами обнуления первого и второгосчетчиков, управляющие входы которыхобъединены с управляющим входом третьего счетчика и подключены к девято- работы которого подключен к второмуму выходу блока управления, десятыйи одиннадцатый выходы которого соединены со счетными входами соответственно первого и второго счетчиков,двенадцатый и тринадцатый выходы блока управления соединены соответствен- инверсный выход третьего триггерано с первым и вторым управляющимивходами коммутатора, а информационный вход первого блока памяти соединен с выходом переключателя, вход первого элемента задержки и второйкоторого является информационнымвходом устройства, второй выход блокауправления подключен к входу обнуле- а вход второго элемента задержкиния накапливающего сумматора и входуразрешения записи пятого блока памяти, адресный и информационный входыкоторого соединены соответственнос информацион:.ым. выходом первогосчетчика и выходом накапливающегосумматора, причем блок управлениясодержит первый и второй регистры,первый и второй элементы задержки,первый и второй узлы сравнения, генератор тактовых импульсов, первыйи второй дешифраторы, первый и второй счетчики, первый, второй и третий триггеры, первый, второй, третийи четвертый элементы И, группу элементов ИЛИ, элемент И-НЕ, причем вы"ходы первого и второго элементов за".держки соединены с информационнымивходами соответственно первого ивторого регистров, информационныевыходы которых соединены с первыми торов по модулю два, выходы которых38 Таблица 8 1121678 37 3 .1 32 1 З З,1 2 М 3 0001 .1 1 0 9 3 0011 О. 1 0 0 4 13 14 0 1Таблица 9 Р Р Р 2 Рз У О 0 0 Таблица 10 Вычисление всех 2 " " коэффициентов число операций Ь Вычисление одного коэффициента число операций Прототип Прототип Предлагаемое устройство Предлагаемое устройство 2 2(ь - -131121678 Си Срр Филиал ППП "Патент",г. Уигород, ул. Проектная, 4 ВН КИПИТирак 69 Заказ 876 Подписное112 элемента И, выход которого соединен. с первым входом элемента И-НЕ и первым входом второго элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого соединен с первым входом третьего элемента И, выход которого является выходом блока, выходы четвертого, пятого и шестого триггеров соединены с первыми входами соответственно четвертого, пятого и шестого сумматоров по модулю два, выходы которых подключены соответственно к первому, второму и третьему входам четвертого элемента И, выход которого соединен с вторым,1 б 78входом элемента И-НЕ, и первым входом пятого элемента И, выход которого подключен к второму входу элемента ИЛИ, третий вход которого соединен с выходом элемента И-НЕ, второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока, второй вход третьего элемента И является вторым входом блока, вторые входы первого, второго и третьего сумматоров по модулю два объединены с вторыми входами соответственно, четвертого, пятого и шестого сумматоров по.модулю два и являются третьим входом блока.О 1Изобретение относится к вычислительной и информационно-измерительной технике и может быть использованов качестве специализированного вычислительного устройства для спектраль 5ного анализа временных процессови имитации случайных процессов с заданными спектральными характеристиками в вычислительных комплексахдля испытания изделий новой техникина вибрационные воздействия а такжев навигационных и радиолокационныхсистемах слежения и обнаружения,Известно устройство для вычисления коэффициентов разложения временного процесса в ряд Фурье посредствомБПФ,содержащее регистры, блок умножения, сумматор и коммутаторы 11.Недостаток известного уСтройства -невозможность получения спектральных характеристик Фурье непосредственно из спектральных характеристик Уолша,Наиболее близким к предлагаемомуявляется устройство для вычисления 25спектра мощности Фурье, содержащеерегистр, блок сравнения, первый,второй и третий счетчики, первый ивторой блоки памяти, блок формирования адреса, первый и второй дешифра- ЗОторы, первый и второй шифраторы,блок умножения, сумматор, коммутатор,.блок управления, блок вычислениякоэффициентовспектра мощностиУолша, блок селекции, блок формирования кода Грея, первый и второй 2элементы ИЛИ, причем выход первого шифратора подключен к установочному входу первого счетчика, выход которого подключен к входу первого дешифратора и первому входу блока формирования адреса, выход которого подключен к адресному входу первого блока памяти, выход первого блока памяти подключен к первому, а выход второго блока памяти - к второму входу коммутатора, выход которого подключен к входу блока умножения, выход блока умножения подключен к входу сумматора, выход второго счетчика подключен к адресному входу второго .блока памяти, выход ре гистра - к первому, а выход третье- . го счетчика и второй выход блока. формирования адреса - к второму входу схемы сравнения, первый выход блока управления подключен к счетному входу первого счетчика, второй выход блока управленияк управляющим входам первого и второго счетчиков и сумматора и счет- . ному входу второго счетчика, первый выход блока управления подклю- . чен к выходу схемы сравнения, а второй выход - к переключающему входу коммутатора и упр 1 авляющему входу блока умножения, установочный вход третьего счетчика,.вход регистра и первый вход второго блока памяти. являются входами устройства, вход блока для вычисления спектра мощ-ности Уолша является дополнительнымз 11216входом устройства, а выход подключен к второму входу второго блокапамяти, вход второго дешифратораподключен к выходу третьего счетчика,выход - к входу первого и первомувходу второго шифратора, выход5которого подключен к установочномувходу второго счетчика, выход которого подключен к второму входувторого шифратора, входу первогоэлемента ИЛИ и входу блока формирования кода Грея, выход которого подключен к первому, а выход первогодешифратора - к второму входу блокаселекции, выход которого подключенк третьему входу блока формированияадреса, выход первого счетчика подключен к входу второго элементаИЛИ, выходы первого и второго элементов ИЛИ - соответственно к третье 20му и второму входам блока управле-ния 2.Однако с помощью известного устройства спектральные коэффициентыФурье из спектральных коэффициентовУолша анализируемого временногопроцесса вычисляют с низким быстродействием.Цель изобретения - повышение быстродействия устройства путем уменьшеЗОноя числа операций умножения и сложения при вычислении нескольких коэффициентов Фурье, имеющих номеракоторые относятся к одной и той же,совокупности номеров,Сущность изобретения заключаетсяв цифровой обработке кода номеравычисляемого коэффициента Фурье,а также кодов вектора"столбца коэффициентов Уолша анализируемого дискретного вреенного процесса сцелью его преобразования в значениекоэффициента Фурье путем последовательного умножения на несколькотак называемых факторизованных матриц спектрального образования Уолша-Фурье, в которых число ненулевых элементов примерно в М меньше,чем в самой матрице спектральногопреобразования Г. Таким образом,реализуется быстрый алгоритм спектрального преобразования коэффициентовразложения временного процесса избазиса Уолша в базис Фурье.Поставленная цель достигается тем,что устройство, содержащее первый 55блок памяти, информационный выходкоторого еоединен с первым входомкоммутатора, элемент ИЛИ, выход которого подключен к первому входублока умножения, выход которогоподключен к входу накапливающегосумматора, блок управления, первый,второй, и третий счетчики, селектор,первый выход которого подключенк установочному входу сдвиговогорегистра, выходы разрядов первойгруппы которого соединены с входамисоответствующих младших разрядовадреса второго блока памяти, информационный выход первого счетчикасоединен с информационным входомсдвигового регистра, блок сравненияи регистр, информационный вход которого.является входом задания номера коэффициента устройства, введены переключатель, третий, четвертый и пятый блоки памяти, блок формирования знака и преобразовательпрямого кода в дополнительный, выход которого подключен к установочному входу второго счетчика информационный выход которого соединен с адресными входами третьего и четвертого блоков памяти, информационные выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, информационный выход регистра соединен с первымвходом селектора, второй выход которого соединен с первым входом блока формирования знака, первым входом блока управления и вторым входом коммутатора, первый и второй выходы которого соединены с информационными входами соответственно третьего и четвертого блоков памяти, входы разрешения считывания которых подключены соответственно к первому и второму выходам блока управления, третий выход которого соединен с первым управляющим входом блока умножения, второй вход которого подключен к информационному выходу первого .блока памяти, вход разрешения считывания которого объединен с вторым управляющим входом блока умножения и соединен с четвертым выходом блока управления, пятый выход которого соедииен со счетным входом третьего счетчика, выходы разрядов которого подключен к второму входу блока формирования знака, входам соответствующих старших разрядов адреса первого блока памяти и управляющему входу сдвигового регистра, выходы разрядов второй группы которого соединены с третьим входом блока формирования.5знака, выход которого подключен к третьему входу блока умножения, шестой выход блока управления подклю- чен к входу обнуления третьего счетчика и входу обнуления пятого блока5 памяти, информационный выход которого является информационным выходом устройства и соединен с третьим входом коммутатора, четвертый вход которого объединен с вторым входом блока управления первым входом блока сравнения и подключен к первому выходу селектора, третий выход которого соединен с установочным входом первого счетчика, вторым входом блока сравнения и входом преобразователя прямого кода в дополнительный, управляющий вход которого подключен к выходу блока сравнения, управляющий вход которого объединен с управляющим входом селек тора и подключен к седьмому выходу блока управления, восьмой выход кото-рого соединен с входами обнуления первого и второго счетчиков, управляющие входы которых объединены с управляющнм входом третьего счетчика и подключены к девятому выходу блока управления, десятый и одиннадцатый выходы которого соединены со счетными входами соответственно первого и второго счетчиков, двенадцатый и тринадцатый выходы блока управления соединены соответственно с первым и вторым управляющими входами коммутатора, а информационный вход первого блока памяти соединен с выходом переключателя, вход которого является информационным входом устройства, второй выход блока управления подключен к входу обнуления накапливающего40 сумматора и входу разрешения записи пятого блока памяти, адресный и информационный входы которого соединены соответственно с информационным выходом первого счетчика и выходом накапливающего сумматора, причем с45 блок управления содерж т первый и второй регистры, первый и второй элементы задержки, первый ивторой узлы сравнения, генератор тактовых импульсов, первый и второй дешифраторы, первый и второй счетчики, первый, второй и третий триггеры, первый, второй третий и четвертый элементы И, группу элементов ИЛИ, элемент И-НЕ, причем выходы первого и второго элементрв задержки соединены с информационными входами соответственно первого и второго регистров, инфор 678 ьмационные выходы которых соединены с первыми входами соответственно первого и второго узлов сравнения, выходы которых подключены соответственно к первому и второму входам элемента И-НЕ, выход которого соединен с первым вкодом первого триггера, прямой и инверсный выходы которого подключены к первым входам соответственно первого и второго элементов И, выход которого подключен к счетному входу первого счетчика, информационный выход которого подключен к входу первого дешифратора, выкод первого элемента И псдключенк входу второго триггера, первому входу третьего элемента И и первому входу генератора тактовых импульсов, первый и второй выходы которого подключены к счетному входу второго счетчика, информационный выход которого соединен с входом второго дешифратора, информационный выход первого регистра соединен с вторым входом генератора тактовых импульсов, выход окончания работы которо" го подключен к второму входу первого триггера, первый вход четвертого элемента И объединен с входом третьего триггера и вторыми входами пепервого и второго элементов И и является тактовым входом блока, инверсный выход третьего триггера подключен к второму входу четвертого элемента И, выход которого является двенадцатым выходом блока, вход первого элемента задержки и второй вход первого узла сравнения объединеныи являются первым входом блока, а вход второго элемента задержки и второй вход второго узла сравнения объединены и являются вторым входом блока, выкоды первого и второго дешифраторов и выход третьего элемента И соединены с входами соответствующих элементов ИЛИ группы, выходы которых являются первым, вторым, третьим, четвертым, пятым, шестым, восьмым, девятым, десятым, одиннадцатым и тринадцатым выходами блока,Блок формирования знака содержит шесть триггеров, шесть сумматоров по модулю два, пять элементов И, элемент НЕ, элемент И-НЕ, и элементИЛИ, выходы первого, второго и третьего триггеров соединены с первыми входами соответственно первого, второго н третьего сумматоров по модулю д.а, выходы которых соединены соот 71216ветственно с первым, вторым и третьим входами первого элемента И,выход которого соединен с первымвходом элемента И-НЕ и первым входом вТорого элемента И выход которого.подключен к первому входу элемента ИЛИ, выход которого соединенс первым входом третьего элементаИ, выход которого является выходомблока, выходы четвертого, пятогои шестого триггеров соединены с первыми входами соответственно четвертого, питого и шестого сумматоровпо модулю два, выходы которых подключены соответственно к первому,второму и третьему входам четвертого элемента И, выход которого соединен с вторым входом элемента И-НЕи первым входом пятого элемента И,выход которого подключен к второмувходу элемента ИЛИ, третий входкоторого соединен с выходом элемента И-НЕ, второй вход пятого элемента И и вход элемента НЕ объединены и являются первым входом блока,второй вход третьего элемента И является вторым входом блока, вторыевходы первого, второго и третьегосумматоров по модулю два объединеныс вторыми входами соответственночетвертого пятого и шестого сумматоров но модулю два и являются третьим входом блока.На Фиг.1 приведена блок-схемаустройства для вычисления спектра. Фурье, на фиг.2 - временная диаграммаблока управления; на фиг.З - схемаселектора; на фиг.4 - схема блокауправления; на фиг,5 - схема переключателя; на Фиг.6 - схема блока форми 40рования знака,Устройство содержит (фиг.1) вход1 устройства, переключатель 2, блоки(блок Формирования адреса) 18, блок9 Формирования знака, элемент ИЛИ 20,50блок 21 управления, вход 22 и выход 23 устройства.Возможный вариант построения схемы селектора приведен на Фиг.З, Селектор содержит регистр 24, сдвиговый регистр .25, элемент И 26, триггеры 27 и 28 с раздельными входами,счетчик 29, а также мультиплексор 78 830, управляющий вход 31 на запускблока, вход 32 двоичного кода коэффициент Фурье %, выход 33 кода параметра р (признак четности или нечетности коэффициента Фурье, причем,если р=1, коэффициент косинусный,если р=0 - синусный), выход 34 кода(номер совокупности (блока), ккоторому относится коэффициент) ивыход 35 кода 1 (номер коэффициентав г -м блоке).Блок 21 управления предназначендля формирования на его 13 выходах всоответствии с заданными п,г,р требуемой последовательности управляющихимпульсов (она изображена на Фиг.2для случая п=6, г=2) и содержит регистры 36 и 37, элементы 38 и 39задержки, узлы 40 и 41 сравнения,генератор 42 тактовых импульсов,триггеры 43-45 с раздельными входа- .ми, элемент И-НЕ 46 элементы И 47-50,элементы ИЛИ 51-60, группы, дешифра- .торы 61 и 62, я. также счетчики 63,и 64. Вход тактовых импульсов обозначен буквами ТИ,Переключатель 2 предназначендля перетасовки вычисленных коэффициентов Уолша к виду, необходимомудля их умножения на факторизованные матрицы.На фиг.5 изображена схема коммутации входов 1 Си выходов1 Спереключателя 2 для М =16в соответствии с табл.1.Блок 19 Формирования знака предназначен для Формирования знака.элемента Факторизованных матрицспектрального преобразования длячетных (косинусных) коэффициентовв зависимости от положения элементав.матрице и ее номера и содержит триггеры 65-70, сумматоры по модулюгеры 65-70, сумматоры 71-76 по модулю два, элементы И 77-81, элементНЕ 82, элемент И-НЕ 83 и элементИЛИ 84. Входы кода номера факторизованной матрицы 1 обозначены позицией 85, входы кода номера элементов 1 в 1 -й факторизованнойматрице - 86, вход параметра р -87,выход блока Р - 88. Блок 8 умножения имеет три входа сомножителей х,у,р, участвующих в умножении и может работать в двух режимах.Если задействован один управляющий вход 1 то производится умножение-Х У, если р =1, 2 п-г Г: г "(О,ч)О,Ч:1 У половины иэ общего числа элементов Г и Г знаки одинаковы,са у ОсталЬной половины противоположны.При перестановке строк и столбцовматриц Г , Г по описанному ни,е 25с 5алгоритму удается привести их ктак называемому блочно-диагональному виду. При этом отдельные спектральные составляющие как в базисеФурье, так и в базисе Уолша, объе- ЗОдиняются в и совокупностей (блоков). Спектральные составляющиефурье, относящиеся в любой г-совокупности (их число составляет 2" "+"зависят только от. 2 " " " спект 35ральных составляющих в базисе Уолша,относящихся к этой же совокупности,Благодаря этому свойству можно вычислять отдельныс спектральные составляющие, принадлежащие разным совокупностям, независимо друг от друга.Все без исключения элементы в меньших блоках с номерами г 2 имеютсяв самом большом блоке с номером г=1,45С С И%з:1,2 -1 =1 р 2 %е 2 С СсС 5 г еЗдесь число ненулевых элементов висходной матрице Г " =Я"г Р числоЭг50ненулевых и неединичных элементовв матрицах Г, Гпо 2 ега в матрице Г" =2 е 1-г . Общее числоненулевых и неединичных элементовгВ МатрИцаХГО Е - .еГ,. б СОСтаВЛяЕт 55 таким Образом и-г 1 2 " г 1 в 2 е Г меньше, чем в самой Г г5Матрицы Г, еГ , Г 5 для 8=326 5 5представлены в табл.5-7.(2гсгп "гфзсг 9сомножителей в соответствии с выра- жением Если задействован другой управляющий вход, то независимо от того, что поступает на остальные входы, умножения не происходит, а код сомножителя с входа поступает на выход блока 2= х .Алгоритм функционирования устройства можно описать следующим Образом.Все соответствующие элементы матриц спектрального преобразования (табл.1 и 2) равны по модулю 5 5иу =у 1 с,5=1(25 Л,ь Матрицы Г с(Ен Г (Ео имеющие с с 5 5блочно-диагональный вид, для И =32 изображены в табл.3 и ее.Таким образом, все основные структурные свойства матрицы Г полностью 78 1 Оопределяются свойствами нх основного блока ( г =1),Введем следующие обозначения:Р-Г: - совокупность элен(б (Ц, ментов т-го блокаЕв 1вектора 3);ее-г Г Ъ- совокупность эле 3 Е=1ментов-го блокавектора Е совокупность зпементов г-го блокаматрицы Гс;,Ее-Г 5 г 5 2Г = у (О,ч)-совокупность элеО,Ч:1ментов г-го квадратного блока матрицы Г-совокупность элементов г-го блокавектора В. Исследования показали, что у кадого г-го блока матриц г,гР. имеется свойство пропорционального соотношения между элементами различных столбцов. Используя это свойство, можно представить любой блок матриц Гсег 5 размерностью 2 е- - 2 п-гв виде произведения и -г -1 сильно разреженных нулевыми элементами матриц. П-Г г 1 гЕСЛИ Г,: , (ее Чф -СОВОКУП 1ность елементов г-го квадратного блока е -и факторизованной.матрицы11 1121678 12Таким образом для умножения в из- Для вычисления четных (косинус 1вестном устройстве для г-го блока не- ных) спектральных составляющихо ходимобходимо 2"," " о операций в то вре- можно воспользоваться значениямиЭбьмя как умножение на правую часть элементов матриц Я ." для нечетныхтождества (Э) которое может соверсоставляющих. Неединичные элементыГ Гсшаться по итерационному алгоритму матриц , Г;, 1"-О,ь-З равны по мо(4) за и- г -1 итераций, требует дулю. Что касается знаков, то дляв общей сложности лишь(п-г) 2 ум- матриц Г , Г З эти знаки всегданожений, т.е. в 2 " меньше, чем противоположны.и-г10С СД; (с)=-, И), г:1,0-1-12" "-"в прототипе: С А=Г Э), Ц=)г Е,ч)1 ) =1,о; у,"и,е), есг"е)флг 2- -Е Е Е 2-г 40 45 Свойство (2) позволяет исполь-; зовать элементы первого блока матриц Й для выполнения умножений в блоках2,3, ь" О+если е г=1, то функций нечетнаЯ,если Ег =О, то четная. В соответствии со значениями о-формируютсяь блоков коэффициентов и п -1 блоков четных. Затем производится ЬэО ментов г-го блока вектора коэффициентов 1) после 1 -й итерации,Г 125 Е,=Е. (ц), - совокупность эле 3 е:1ментов г -го блока вектора коэффициентов Е после 1-й итерации,Обозначим элементы факторизованных матриц следующим образом: и- -2Если 8 4 2, то у элементов Йп по сравнению сй знаки менять нужно, а у Й 2 не нужно. Если же5Е 3 2" г , то у элементов Я знаки менять не нужно, а у Ййужно.5В результате спектрального преобразования по (4) вектор-столбцы А,В будут двоично перетасованы. Поэтому чтобы получить коэффициенты фурье в естественном порядке следования, необходимо массивы коэффициентов перетасовать по закону двоичной инверсии.Быстрый алгоритм преобразования коэффициентов Уолша в коэффициенты Фурье, который используется в данном устройстве записывается следующим образом.1. Разделение (й) спектральных коэффициентов Уолша СД на двеН М части - -1 четных и - нечет 2 г ных коэффициентов, а внутри каждой части - разделение на п блоков в соответствии с номером первой справа единицы в двоичном представлении номераДля упорядочения функций Уолша по Пэли эти операции могут производиться .следующим образом.Пусть- двоичный эквивалент (код) номера. В процессе поразрядной логической обработки производится вычисление параметров номера первой единицы в коде, считая со стороны старших разрядов, и ло13 11216 перестановка коэффициентов в каждой группе в соответствии с алгоритмом двоичной инверсии их номеров в этом блоке (нумерация 1 начинается с О) . Например, для М =16 приведено табл,8 для перетасованного массива коэфАициентов Уолша"(Р: "б, (т(+Е., (т 2 ), Ь 2 СИ=сЦе,. С(М г(м 2 , 0=250- о-г Со=1,2;=1, о-ггде,1 ц, дяСт:и-ги-с -22 +С-О, Р 2 СО2. Непосредственное вычисление М-го коэфАициента Фурье. Вначале в ходе логической обработки кода % определяются значения параметров р,г,Р по следующему алгоритму. Зна 15 чение самого младшего разряда в коде М определяет значение р. Еслигетеобозначить через %, (и)-разрядный код, образованный отсечениемЛlу кода % самого младшего разряда,20 то номер первой по счету единицы в этом коде, считая справа, определяет значение параметра г . Если обозначить через 1(г-г"1)-разрядный код, образованный из кода % от 25 сечением первой справа единицы и всех нулей (если они есть), следующих после этой единицы справа, то значение 1 определяется двоич(Ъно-инверсным кодом 12 . Например, если и =6, а Сщ =01;101, то Р =1 коэффициент косинусный (четный); %,=01110, г =2 - номер блока; М =011 1=7 - номер коэАфициента в 2-м блоке, Е =110.Тогда значение коэфАициента ( йли 1 ЬДопределяется из значений только четных (при р=1) или нечетных (при р=О) коэффициентов г-го блока и может быть вычислено с помо- щью следующих выражений (см.конфи 40 гурацию матрицГ 5,Г ,Г,бв табл.5-7);зб 1478в случае нечетных коэфАициентов,иСЫ Л(=, (Ю, (т)с( (т+2 ), ( (т.1 б,.(ЦУщ,(Цб,. (т(.б, (т.К"),(:гтПс: С,2 ; =1 р-г-гп-г.Сщ:с( (с(б (т(то (Е(1) (т 2 ) (91в случае четных коэффициентов,Значения , (Р ) могут быть получены из значений коэффициентов 5(Р(т.е. относящихся к перенну блокув соответствии с выражениями-г Лля вычисления одного коэффициентаФурье с заданным номером % требуется (и-г) 2(1 " " умноженийи сложений для выполнения вычислений по (7) и два умножения и односложение для выполнения (Я) . Всего,таким образом, необходимо (и-г)х2 " " +2 умножений и сложений,Устройство для случая С 1 =6, г=2,р=1 работает следующим образом.В начальный момент времени в блоке 3 памяти записаны 2 " " -1 коэАфициентов Уолша с 5 2 " коэффициентов 15 и С , которые поступают с информационного входа устройства и перетасовываются с помощью переключателя 2 по описанному выше алгоритму, В блок б памяти записаныэлементы первых блоков матриц 0,.,8и все и блоков матрицы Я . Всесчетчики и сумматор 9 обнулены.На регистре 12 установлено очередное значение номера коэффициента Фурьек, подлежащего вычислению. НомеракоэАфициентов могут устанавливатьсяна регистр либо случайным образом,либо в определенном порядке. Наилучшее использование устройства достигается, если коэфйициенты устанавливаются в порядке, соответствующемдвоично-инверсным кодам от номеров,расположенных в натуральном порядке;82,бу 1 у 5,3,7 (при СЧ =Я).Тактовые импульсы начинают поступать на вход блока 21 управления.Блок 21 управления (фиг.4) работает следующим образом. В исходном