Устройство для вычисления преобразования уолша (его варианты)

ае оо МЮ й 06 Г 15 З.З БРЕТЕНИНЬСВУ П С ИЕ(71) Конструкторское бюро вычислительной техники при Дальневосточном орна Трудового Красного Знамени политехническом институте им,В.В.Куйбыше(56.) 1, Авторское свидетельство СССВ 809198, кл. 9 0615/332, 19812. Авторское свидетельство СССР9 723582, кл. Я 06 Р 14/332, 1980(54) УСТРОИСТВО ДЛЯ ВЫЧИСЛЕННАЯ НРЕ ОБРАЗОВАНИЯ УОЛША (ВАРИАНТЫ). (57) 1. Устройство .для вычисления преобразования Уолша, содержавшее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторьэа информационными входамн арифметического блока, информационный выход которого соединен сформационным входом бпока памяти, управлякарюй вход которого соединен с выходом первого разряда первого блока постоянной памятивыход второго и третьего разрядов которого соединены с тактовыми входами соответствеино.нервого и второго регист- . ров, инФормационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока п стоянной памяти соединен с информац онным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входомза" пуска устройства, второй блок постоянной памяти, счетчик итерации, о тл и ч а ю ц е е с я тем, что, с .целью расширения области применения ин о- нГОСУДАРСТВЕННЫЙ КОМИТЕТ ОССРпвидш ииввееенбавпа путем обработки последовательностей произвольной длины, в него введещг регистр базы, второй коммутатор, сум-матор и регистр длины выборки, информационный выход которого соединен с управляющим входом второго коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационньм выходом счетчика адреса и выходом пятого разряда первого блокапостоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счет-чика адреса и подключен к первому ,входу сумматора, выход которого соединен с управляюцим входом первого коммутатора, информационный вход ко- торого объединен с информационными выходами первого и второго регистров и подключен к информационному выходублока памяти, .второЯ инФормационный, выход второго блока постоянной памяти соединен с установочньаж входом счетчика адреса, второй вход сумматора (,",) подключен к информационному выходу регистра базы, информационный вход которого объединен с информационным ( Д входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого ком- ) мутатора является информационным выходом устройства.2Устройство для вычисления преобразователя Уолша, содержащее первый коммутатор, первый и второй ре- фю гистры, информационные выходы которых соединены соответственно с пер.вым и вторым информационными входами арифметического блока, информационный выход которого соединен с Информационньщ входом блока памяти, управляющий вход которого соединен с выходом первого разряда первого1075269 блока постоянной памяти, выходывторого и третьего разрядов которогосоединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами уст"ройства, выход четвертого разрядапервого блока постоянной памятисоединен с тактовым входом счетчикаадреса, адресный вход первого блокапостоянной памяти соединен с информа,ционным выходом счетчика, тактовыйвход которого подключен к выходу генератора тактовых импульсов, входзапуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций, о тл и ч а ю щ е е с я тем, что с целью расширения области применения путем обработки последовательностейпроизвольной длины, в него введенырегистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которого соеди-нен с управлякяцим входом второгокоммутатора, выход которого соединен с входом обнуления счетчикаадреса и тактовым входом счетчикаитераций, информационный выход которого объединен с информационнымвыходом счетчика адреса и выходомпятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационныйвыход которого соединен с информационным входом счетчика адреса иподключен к первому входу,сумматора и адресному входу блока памяти,выход сумматора подключен к управляющему входу первого коммутатора,информационный вход которого объединен с информационными входами перво-,го и второго регистров и подключенк информационному выходу блока памяти, второй иыформациоыный выходвторого блока постоянной памяти сое-,динен с установочным входом счетчика адреса, второй вход сумматораподключен к информационному выходурегистра базы, инФормационный входкоторого объединен с информационнымвходом регистра длины выборки и информационными входами первого ивторого регистров, а выход первого коммутатора является информационным выходом устройства. 1Изобретение относится к вйчислительыой технике и предназначено для аппаратной реализации алгорит 3. Устройство для вычисления преобразования Уолша, содержащее пер вый коммутатор, первый и второй ре,гистры, информационные выходы которых соединены соответственно с первьм и вторым информационными входами арифметического блока, информационный выход которого соединен с иыформационыым входом блока памяти, управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых иьвульсов, вход запуска которого является входом запуска устройства, второй блок ,постоянной памяти, счетчик итераций, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения путем обработки последовательностей произвоЛьной длины, в него введен регистр длины выборки, информационный выход которого соединен с управляющим входом первого коммутатора, выход которого соединен с входом обыумения счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационньм выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соеди" нен с информационным входом счетчика адреса и адресным входом блока памяти, информационный выход которого соединен с информационными входами первого и второго регистров и является информационным выходом устройства, второй информационный выход второго блока постоянной памяти соединен с установочным входом счетчика адреса, информационный вход регистра длины выборки объединен с информационными входами первого и второгорегистров. ма быстрого преобразования Уолша(БПУ), который используется прицифровой обработке сигналов.блока памяти, управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационныч выходом счетчика, тактовый вход которого подключен .к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постояниой памяти, счетчик итераций, введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, инФормационныйвыход которого соединен с управляющим входом второго коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной .памяти и.подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и подключен к первому входу. сумматора, выход которого соединен с управляющим входом первого коммутатора, информационный вход которого объединен с информационными выходом первого и второго регистров и подключен к информационному выходу блока памяти, второй информа-. ционный выход второго блока постоянной памяти соединен с установочным входом, счетчика адреса, второй ,вход сумматора подключен к информа" ционному выходу регистра базы, информационный вход которого объединен с информационным входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого коммутатора является информационным выходом устройства.11 оставленная цель достигается тем, что по второму варианту устройство, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторыа информационными входами арифметического блока, информационный выход которого соединен с информационным входом блока памяти, управляющий вход которого соедйнен с выходом первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединеныс такто-,3 107521Известно устройство для реализации быстрого преобразования фурье, содержащее два коммутатора, регистр йтерации счетчик адреса, постоян.ное запоминающее устройство ПЗУ 1, сумматор 1.13. 5Недостаток данного решения заключается в том, что это устройство жестко привязано к длине выборки, при изменении длины выборки требуется внесение изменений в схему 10 устройства.Наиболее близким по технической сущности к изобретению является устройство для.выполнения быстрого преобразования фурье, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторым информационными входами арифметического блока, информационный выход которого подключен к информационному входу блока памяти, управляющий вход которого подключен к выходу первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с актовыми входами соответственно первого и второго регистров, информационные входы которых . являются информационным входом устройства, тактовый вход счетчика ад реса соединен с выходом четвертого разряда.первого блока постоянной памяти, адресный вход которого подключен к информационному выходу счетчика, тактовый вход которого соединен 35 с выходом генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций 12 3.40Однако известное устройство аппаратно ориентировано к конкретной длине выборки, которое является следствием использования в качестве ОЗУ памяти с последовательным достуцом сдвиговых регистров ). В том случае когда длина выборки не совпадает с ем-, костью памяти, эФфективность устро 61 ства резко ухудшается, причем ухудшение зависит от отношения 2/2ч е где У - емкость памяти, 2 - длиФ на выборки и приблиэительйо равна 2-Целью изобретения является расширение области применения устройства путем.преобразования последовательностей произвольной длины.Поставленная цель достигается тем, что по первому варианту устройство, содержащее первый коммутатор, первый и второй регистры, информаци онные выходы которых соединены соответственно с первым и вторым .информационными входами арифметического блока, информационный выход которо.го соединен с информационным входом 651075 выми входами соответственно первогои второго регистров, информационныевходы которых являются информационными входами устройства, выход четвер-того разряда первого блока постояниойпамяти соединен с тактовым входомсчетчика адреса, адресный входпервого блока постоянной памяти соединенс информационным выходом счетчика,тактовый вход которого подключен квыходу генератора тактовых импульсов 10вход запуска которого является входом запуска устройства, второй блокпостоянной памяти, счетчик итераций,введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которогосоединен с управляющим входом второгокоммутатора, выход которого соединенс входом обнуления счетчика адресаи тактовым входом счетчика итераций,информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разрядапервого блока постоянной памяти иподключен к адресному входу второгоблока постоянной памяти, первый информационный выход которого соединенс информационным входом счетчика адреса и подключен к первому входу сумматора и адресному входу блока памяти, выход сумматора подключен к управляющему входу первого коммутатора,информационный вход которого объединен с информационными входами первого и второго регистров и подключен кинформационному выходу блока памяти, 35второй информационный выход второго.блока постоянной памяти соединен сустановочным входом счетчика адреса,второй вход сумматора подключен кинформационному выходу регистра базы, информационный вход которогообъединен с информационным входомрегистра длины выборки и информационными входами первого и второго регистров, а выход первого коммутатора является информационным выходомустройства.Поставленная цель достигается тем,что по третьему варианту устройство,содержащее первый коммутатор, первыйи второй регистры, информационныевыходы которых соединены соответствен.но с первым и вторым информационнымивходами арифметического блока памяти,управляющий вход которого соединенс выходом первого разряда первого бло 55ка постоянной памяти, выходы второгои третьего разрядов которого соединены с тактовыми входами соответственнопервого и второго регистров, инфор"мационные входы которых являются 60информационными входами устройства,выход четвертого разряда первогоблока постоянной памяти соединен стактовым входом счетчика адреса,адресный вход первого блока постоян 269ной памяти соединен с информационным выходом счетчика, тактовый входкоторого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом запускаустройства, второй блок постояннойпамяти, счетчик итераций, введен регистр длины выборки, информационныйвыход которого соединен с управляю"щим входом первого коммутатора, вы-.,ход которого соединен с входом обнуления счетчика адреса и тактовьвчвходом счетчика итераций, информаци".онный выход которого объединен с инФормационным выходом счетчика адре"са и выходом пятого разряда первогоблока постоянной памяти и подключенк адресному входу второго блока постоянной памяти, первый информацион,ный выход которого соединен с информационным входом счетчика адресаи адресным входом блока памяти, информационный выход .которого соединенс информационными входами первогои второго регистров и является информационным выходом устройства, второй инФормационный выход второгоблока постоянной памяти соединен сустановочным, входом счетчика адреса, информационный вход регистра дли-ны выборки объединен с информационными входами первого и второго регистров,Наличие в схеме коммутатора приконкретной технической реализации определяется особенностью организацииканала или магистрали сателлитнойЭВИ. Например, для магистрали, в которой подшины данных и адреса разделены на две подшины, нет необходимости передачи данных адресов но одной общей шине, следовательно, нетнеобходимости и в этом коммутаторе,а если адреса .и данные передаютсяпо одной магистрали, то коммутаторнеобходим. Второй информационныйвход этого коммутатора соединен свыходом автономного блока памяти,причем выход блока. ОЗУ должен бытьлибо с тремя состояниями, либо с открытой коллекторной нагрузкой, потому что этот выход образует совместнос входом устройства микроканал устройства, к которому подсоединены инФормационные входы процессора, регистра выборки и регистра базы.В решении устройства в целомвозможны варианты, При втором варианте емкость блока памяти может быть,значительно уменьшена в зависимостиот пределов длин выборск. Второйвариант может иметь упрощенное решение.Устройство по третьему варианту,теряет возможность использования блока памяти сателлитной ЭВИ в качестве рабочей памяти и способно работать только со своим блоком памяти.На фиг.1 приведена функциональная блок-схема устройства, на фиг.2 функциональная блок-схема второго варианта; на Фиг,3 - Функциональная блок-схема третьего варианта модуля на фиг.4 - граф алгоритма быстрого 5 преобразования Уолша-Адамара с замещением; на фиг.5 - блок-схема процессора, на фиг,б - временная диаграмма работы процессора) на Фиг,7 - блоксхема устройства в комплексе с ЭВМ. )ОУстройство для вычисления преобразования Уолша содержит счетчик адреса 1, регистр длины выборки 2, коммутатор 3, счетчик 4 итераций, блок 5 постоянной памяти, регистр б базы, сумматор 7, блок памяти (ОЗУ)8, процессор 9, который состоит из регистров 9.1 и 9.2, арифметического блока 9.3, генератора тактовых импульсов 9.4, счетчика 9.5 и блока постоянной памяти 9.6, коммутатор 10, информационный вход 11 и информационный выход 12 устройства.Арифметический блок 9.3 процессора 9 ориентирован на выполнении базовой операции,и состоит из умно- жителя и сумматора.Рассмотрим работу устройства на примере работы первого варианта как наиболее общего случая, Работа частных вариантов не отличается от рабо- ЗО ты первого варианта в соответствующих режимах. Сначала рассмотрим режимы работы устройства с внешней памятью, в качестве которого используется память сателлитной ЭВМ. Пусть для опре деленности необходимо произвести преобразование Уолша над массивом 2, который размещен в ОЗУ ЭВ, начиная с адреса К на адрес К + 2, При начальном обращении к модулю осуществ- що ляется настройка модуля к рабочему полю памяти и к длине выборки (массива), Для этого начальный адрес К загружается в регистр базы , а длина выборки- в РегистР Йи управ"45 ление передается процессору 9. С этого момента устройство становится активным и осуществляет обмен данных с ОЗУ в режиме прямого доступа к па" мяти. цикл состоит иэ двух тактовНа первом такте устройство выставля О ет в магистраль адрес ячейки ОЗУ, на втором такте осуществляется передача или прием ) данных, Устройство выставляет адрес в магистраль с выхода сумматора 7 через первый вход 55 коммутатора 10, а данные выставляются в общем случае с выхода блока 8.Суть быстрого преобразования Уолша заключается в том, что цикличес" ки выполняется базовая операция, Я) причем результат суммирования засылается по адресу операнда А, который будем называть верхним операндом, а результат вычитания засылается по- адресу операнда В нижний операнд ). б 5 Адреса операндов Формируются согласно графа алгоритма Фиг.4). Сначала покажем работу устройства на одной базовой операции,.а затем покажем как в устройстве осуществляется переход на следующую операцию внутри итерации, а также переход с итерации на итерацию.Выполнение одной базовой операции состоит из трех тактов работы устройства. На .первом такте формируется цикл обращения к ОЗУ ЭВМ для выбора верхнего адреса А. Для этого процессор 9 устанавливает для блока 5 признак верхнего адреса, по которому блок 5 на вход сумматора 7 пропускает текущее значение счетчика 1, например 1, Адрес этот представляет собой абсолютный адрес, во втором и четвертом вариантах он непосредственно подается на адресную шину автономного блока 8, а в тех вариантах, которые работают с памятью ЭВМ, арифметически суммируется с адресоМ базы на регистре б и с выхода сумматора 7 через ком; мутатор 10 подается в магистраль. Выбираются данные по этому адресу с ОЗУ ЭВМ и по входу 11 заносятся во внутренний. регистр 9.1 процессора 9. На этом завершится первый тактНа втором такте выбирается нижний операнд. Но в этом случае блок 5 по признаку процессора 9 Формирует абсолютный адрес в виде суммы по вод 2 текущего значения счетчика 1 адрес верхнего операнда ) и унитарного кода номера итерации, т.е. на ) итерации нижний операнд. представляется как 1 9 2) . Нижний операнд заносится в регистр 9.1 процессора 9. Но такт этот завершается.засылкой результата вычитания по адресу нижнего операнда, т.е. в этом такте ОЗУ работает в режиме фВвод-Пауза-Выводф. На третьем такте процессор .9 восстанавливает признак верхнего операнда, по которому производится занись суммы операндов, По концу выполнения базовой операции процессор 9 наращивает значение счетчика 1 на единицу и.осуществляется переход на следующую операцию. Из-эа того, что верхний и нижний операнды являются элементами одного массива и эти элементы на итерации должны только один раз участвовать в базовой операции, нарушается линейный порядок выбора операндов иэ массива, причем длина группы верхних соответственно и нижних ) операндов, расположенных в последовательных ячейках памяти, зависит от номера итерации. Эта особенность расположения операндов хорошо прбсматривается на графе алгоритма Ииг.4), поэтому возникает необходимость переустановки счетчика 1, сутькоторого заключается в том, что в счетчик 1 заносится адрес нижнего операнда базовой операции, после которой возникает ситуаций для переустановки счетчика 1, только после этого счетчик 1 наращивается на еди-" 5 ницу.Теперь покажем как осуществляется переход с итерации на итерацию, хак как решение этого момента является одним из существенных отличи ф тельных признаков предлагаемого решения. В прототипе переход на следующую итерацию осуществляется при появлении сигнала переполнения счетчика 1, по которому счетчик итерации 4 изменяет свое состояние, Но для того, чтобы управлять моментом переноса, который зависит от длины выборки, введены регистр длины выборки 2 и коммутатор 3. При этом сигнал переноса из счетчика 1 в счетчик 4 про-., ходит через коммутатор 3. А так как информационные входы коммутатора 3 соединены с выходами разрядов счетчика 1 номера которых соответствуют длине выборки, открыв соответствующий канал коммутатора 3, с выхода ,которого сигнал переполняется не только наращивает значение счетчика 4 фно и очищает сам счетчик 1, можно контролировать моменты переноса а. следовательно, эффективно использовать устройство на преобразованиях массивов с различным числом элементов но кратным степени 2). Выбор канала коммутатора 3 осуществляется значением регистра 2, в котором и располагается длина выборки. В предлагаемом случае при значении счетчика 1, равном 2, на выходе коммутатора 3 появляется сигнал, по которому счетчик итерации 4 наращивается на "1", а счетчик очищается еТаким образом, введение указанных блоков и связей позволит расширить функциональные возможности устройства за счет отработки массива разной длины.Э1075269 ТактоВые 0 Р 2 Я Ф Х Ю 7 имиь 41 ъ 1 41 %фцоз 1 ф ф 1Фае. Ю Фае итель А.бауД,Коцвбняк. ов Корре СостТехре О.Била тор Н.Пушненков ПП фПатен фил Тирам ВНИИПИ Государс по делам иэобре 113035, Москва,699венного комиений и откЖ, Рауш Подпистета СССРрытийская наб., д згород, ул. Проектная,