Устройство для вычисления преобразования Уолша (его варианты) Советский патент 1984 года по МПК G06F17/14 

блока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров , информационные вхрда которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информа ционным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций, о тличающееся тем, что с целью расширения области применения птем обработки последовательностей произвольной длины, в него введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которого соединен с управлякяцим входсил второго KoiviMyTaTopa, выход Которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и подключен к первому входу.сумматора и адресному входу блока памяти, выход сумматора подключен к управляющему входу первого коммутатора, информационный вход которого объединен с информационными входами первого и второго регистров и подключен к информационному выходу блока памяти, второй информационный выход второго блока постоянной памяти соедивен с установочным входом счетчика адреса, второй вход сумматора подключен к информационному выходу регистра базы, информационный вход которого объединен с информационным входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого коммутатора является информационным вых1эяом устройства.

3. Устройство для вычисления преобразования Уолша, содержащее первый коммутатор, первый и второй ре.гистры, информационные выходы кото рых соединены соответственно С первьм и вторь 1 информационными входами арифметического блока, информационный выход которого соединен с инфор|мационньв4 входом блока памяти управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянн Л памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок .постоянной па14яти, счетчик итераций, о т. л и ч а ю щ е е с я тем, чтр, с целью расширения области применения путём обработки последовательностей произвольной длины, в него введен регистр длины выборки, информационный выход которого соединен с управляющим входом первого коммутатора , выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адреснсилу входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и адресным входом блока памяти, информационный выход которого соединен с информационными входами перв.ого и второго регистров и является информационным выходом устройства, второй информационный выход втоjporo блока постоянной памяти соединен с установочным входом счетчика адреса ,информационный вход регистра длины выборки объединен с информационными входами первого и второго регистров .

1. Устройство для вычисления преобразования Уолша, содержащее первый камяутатор, первый и второй i регист{ш, иифр|; ационные выхода t которых соединены соответственно с первым и вторым информационными входами арифметического блока, информационный выход которого соединен с информационным входом ока пгшяти, управляющий вход которого соединен с выходом первого разряда первого Ълока постоянной памяти, выход второго и третьего разрядов которого соедииеиы с тактовыми входами соот ветственно первого и второго регистipoB, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока- постоянной памяти соединен с тактовым входом счетчика ад- , реса, первого блока, постоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом, запуска устройства, второй блок постоянной памяти, счетчик итерации, о тличаюцееся тем, что, с .целью расширения области применения путем обработки последовательностей произвольной длины, в него введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которого соединен с управляющим входом второго коммутатора, выход соединен с входом обнуления счетчика адреса и тактовым входе) счетчика итераций, информационный выход которого объединен с информационньм выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входе счетчина адреса и подключен к первсмлу входу сумматора, выход которого соеданен с управляющим входом первого коммутатора, информационный вХод ко торого объелщнен с информационными выходс1ми первого и второго регистров и подключеи к информационному выходу блока пгмяТи, втрЕрй информационный, выход второго блока, постоянной памяти соединен с установочнью входом счетчика адреса, второй вход сумматора подключен к информационному выходу регистра базы, информационный вход сл ю которого объединен с информационным входом регистра длииы выборки и информационными входами первого и втол рого регистров, а выход первого ком- со мутатсфа является информационным выходом устройства. 2, Устройство для вычисления преобразователя Уолша, содержащее первый коммутатор, первый и второй реГИСТ1ИД, информационные выходы которых соединены соответственно с пер.вым и вторым информационн1лми входами арифметического блока, информационный выход которого соединен с информационным входом блока памяти, управляющий вход которого соединен с выходом первого разряда первого

.Изобретение относится к вычислительной технике предназначено для аппаратной реализации алгоритма быстрого преобразования Уолша (БПУ), который используется при цифровой обработке сигналов. . Известно устройство для реализации быстрого преобразования Фурье содержащее два коммутатора, регистр итерации,, счетчик адреса, постоянное эапс линающее устройство (ПЗУ;, сулматор Си. Недостаток данного рЫенйя заключается в том, что это устройство жестко привязано к длине выборки, при изменении длины выбррки тре буется внесение изменений в схему устройства.. Наиболее близким по технической сущности к изобретению является уст.ройство для выполнения быстрого преобразования Фурье, содержгидее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с пер вьвм и вторым информационньми входами арифметического блока, инфо ялационный выход которого подключен к информационнс(у входу блока памяти, управляющий вход которого подключен к выходу первого разряда первого Яблока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых . являются информационньш входом устройства, тактовый вход счетчика адреса соединен с выходом четвертого разряда.первого блока постоянной пам ти, адресньй вход которого подключен к информационному выходу счетчика , тактовый вход которого соединен с выходом генератора тактовых ик.пуль сов, вход запуска которого является входом запуска устройства, второй блок постоянной Пс1мяти, счетчик итераций С2. Однако известное устройство аппаратно ориентировано к конкретной длине выборки, которое является след ствием использования в качестве ОЗУ памяти с последовательным доступом , Л- ЖЛ « l 4/V « iiiAV t J J (сдвиговых регистров ). В том случае когда длина выборки не совпадает с емкостью памяти, эффективность ycTpottV ства резко ухудшается, причем ухудшение зависит от отношения , где V - емкость памяти, 2 - длина выбррки и приблизительно равна

Целью изобретения является расширение области применения устройства путем преобразования последователь- 55 ностей произвольной длины.

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

ва.

Поставленная цель достигается тем, что по второму варианту устройство, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вто(шм информационными входами ,тического блока, информационный выхо которого соединен с информационным входом блока памяти,управляющий вход которого соединен с выходом первого разряда первого блока гпостоянноа памяти, выходы второго и третьего разрядов которого соединеныс такто-. блока памяти, управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адрес1Шй вход первого блока постоянной памяти соединен с информационнъам выходом счетчика, тактовый вход которого подключен .к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций, введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которого соединен с управл)аощим входом второго коммутатора, выход которого соединен с входсм обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и, подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и подключен к первому входу cytvwaTopa, выход которого соединен с управлякяцим входом первого коммутатора, информационный вход которого объединен с информационными выходом первого и второго регистров и подключен к информационному выходу блока памяти, второй информа-г ционный выход второго блока постоянной памяти соединен с установочшлм входом,счетчика адреса, второй вход сумматора подключен к информационному выходу регистра базы, ин.V b V K-4i«. m f л ЧП«|Г.П fm-,mm формационный вход которого объединен с информационным входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого коммутатора является инфорг4ационньаи выходом устройствыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четве того разряда первого блока постоянно памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соедине с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов вход запуска которого является входом запуска устройства, второй блок .постоянной памяти, счетчикi итераций введены регистр базы, второй коммута тор, сумматор и регистр длины выборки, информационный выход которого соединен с управлякяцим входом второг коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовьм входом счетчика итераций, информационный выход которого объеди нен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и лодключен к адресному входу второго блока достоянной памяти, первый информационный выход которого -соединен c информационным входом счетчика адреса -и подключен к первому входу сум матора и адресному входу блока памяти, выход cyivwaTopa подключен к управлякицему входу первого коммутатора информационный вход которого объединен с информационными входами первого и второго регистров и подключен к информационному выходу блока , второй информационный выход второго, блока постоянной памяти соединен с установочным входом счетчика адреса, второй вход сумматора подключен к информационному выходу регистра базы, информационный вход которого объединен с информационным входом регистра длины выборки и информацион ными входами первого и второго регистров , а выход первого коммутатора является информационным выходом устройства. Поставленная цель достигается тем что по третьему варианту устройство, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответствен но с первым и вторым информационными входами арифметического блока памяти управляющий вход.которого соединен с выходом первого разряда первого бло ка постоянной памяти, выходы второго и третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций, введен регистр длины выборки, информационный выход которого соединен с управляющим входом первого коммутатора, вы-. ход которого соединен с входом обнуления счетчика адреса и тактовьм входом счетчика итераций, информаци-. онный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый ин.формацион.ный выход которого соединен с информационным входом счетчика адреса и адресным входом блЬка памяти, информационнйй выход .которого соединен с информационными входами первого и второго регистров и является информационным выходом устройства,, второй информационный выход второго блока постоянной памяти соединен с установочный .входом счетчика адре- са, информационный вход регистра дли-i ны выборки объединен с информационными входами первого и второго регистров. Наличие в схеме коммутатора при конкретной технической реализации определяется особенностью организации какала или магистрали сателлитной ЭВМ. Например, для магистрали, в которой подшины данных и .адреса разделены на две подшины, нет необходимости передачи данных адресов по одной общей шине, следовательно, нет необходимости и в этом коммутаторе, а если гщреса -и данные передаются по одной магистрали, то коммутатор необходим. Второй информационный вход этого коммутатора соединен с выходом автономного блока памяти, причегл выход блока- ОЗУ должен быть либо с тремя состояниями, либо с открытой коллекторной нагрузкой, потому что этот выход образует совместно с входом устройства микроканал устройства, к которому подсоединены информационные входы процессора, регистра выборки и регистра базы. В решении устройства в целом возможны варианты. При втором варианте емкость блока памяти может быть , значительно уменьшена в зависимости от пределов длин выборок. Sторой вариант может иметь упрсяценное решение. Устройство по третьему варианту ,т.еряет возможность использования блока памяти сателлитной ЭВМ в качестве рабочей памяти и способно работать только со своим блоком памяти. На фиг.1 приведена функциондльная блок-схема устройства; на фиг.2функциональная блок-схема второго варианта; на фиг.З - функциональная блок-схема третьего варианта модуля/ на фиг.4 - граф алгоритма быстрого преобразования Уолша-Адамара с замещением; на фиг.5 - блок-схема процес сора, на фиг,б - временная диагра1 1ма работы процессора j на фиг.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% При начальном обращении к модулю осуществляется настройка модуля к рабочему полю памяти и к длине выборки (массива). Для этого начсшьный адрес К загружается в регистр базы б, а длина выборки Е - в регистр управ ление передается процессору 9. С это го момента устройство становится активным и осуществляет обмен данных с ОЗУ в режиме прямого доступа к памяти. Цикл состоит из двух тактов. На первом такте устройство выставляет в магистраль адрес ячейки ОЗУ, на втором такте осуществляется передача (или приём J данных. Устройство выставляет гщрес в магистраль с выхо да сумматора 7 через первый вход коммутатора 10, а данные выставляютс в общем случае с выхода блока 8. суть быстрого преобразования Уолша заключается в том, что циклически выполняется базовая операция, причем результат суммирования засылается по адресу операнда А, который будем называть верхним операнде а результат вычитания засылается по.адресу операнда В (нижний операнд). .Адреса операндов формируются согласно графа алгоритма (фиг.41. Сначала покажем работу устройства на одной базовой операции, а затем покажем как в устройстве осуществляется переход на следующую операцию внутри итерации, а также переход с итерации на итерацию. Выполнение одной базовой операции состоит из трех тактов работы устройства. На-первом такте формируется цикл обращения к ОЗУ ЭВМ для выбора верхнего адреса А. Для этого процессор 9 устанавливает для блока 5 признак верхнего адре- j са, по которому блок 5 на вход сумматора 7 пропускает текущее значение счетчика 1, например i . Адрес этот представляет собой абсолютный адрес, во втором и четвертом вариантах он непосредственно подается на адресную шину автономного блока 8, а в тех вариантах, которые работают С памятью ЭВМ, арифметически суммируется с адрессЛл базы на регистре 6 и с выхода сумматора 7 через коммутатор 10 подается в магистраль. Выбираются данные по этому адресу с ОЗУ ЭВМ и по входу 11 заносятся во внутренний регистр 9.1 процессора 9. На этом завершштся первый такт. На втором такте выбирается нижний операнд. Но в этом случае блок 5 по признаку процессора 9 формирует абсолютный адрес в виде суммы по trios 2 текущего значения счетчика 1 (адрес верхнего операнда) -и унитарного кода номера итерации, т.е. на j итерации нижнир операнд представляется как i ® 2 . Нижний операнд заносится в регистр 9.1 процессора 9. Но такт этот завершается, засылкой результата вычитания по адресу нижнего операнда, т.е. в этом такте ОЗУ работает в режиме Ввод-Пауза-Вывод. На третьем такте процессор .9 восстанавливает признак верхнего операнда, по которому производится запись суммы операндов. По концу выполнения базовой операции процессор 9 наращивает значение счетчика 1 на единицу и. осуществляется переход на следующую операцию. Из-за того, что верхний и нижний операнды являются элементами одного массива и эти элементы на итерации должны только один раз участвовать в базовой операции, нарушается линейный порядок выбора операндрв из массива, причем длина группы верхних (соответственно и нижних/) операндов, расположенных в последовательных ячейках памяти, зависит от номера итерации. Эта особенность расположения операндов хорошо прбсматривается на графе алгоритма . (фиг.4), поэтому возникает необходи.мость переустановки счетчика 1, суть которого заключается в том, что в счетчик 1 заносится адрес нижнего оп ранда базовой операции, после которой возникает ситуация для переуст ановки счетчика 1, только после этого счетчик 1 наращивается на единицу. Теперь покажем как осячествляется переход с итерации на итерацию, хак как решение этого момента является одним из существенных отличительных признаков предлагаемого решения. В прототипе переход на следую щую итерацию осуществляется при появ лении сигнала переполнения счетчика 1, по которому счетчик итераций 4 изменяет свое состояние. Но для того, чтобы управлять моментом переноса, который зависит от длины выборки, введены регистр длины выборки 2 и коммутатор 3. При этом сигнал пере носа из счетчика 1 в счетчик 4 про-... ходит через коммутатор 3. А так как информационные входы коммутатора 3 соединены с выходами разрядов счетФаг.}

/2 чика 1 номера которых соответствуют длине выборки, открыв соответствующий канал коммутатора 3, с выхода которого сигнал переполняется не только Hapauj iaaeT значение счетчика «i но и очищает сам счетчик 1, можно контролировать моменты переноса а, следовательно, эффективно испол зовать устройство на преобразованиях массивов с различньв4 числом элементов (но кратньол степени 2. Выбор канала коммутатора 3 осуществляется значением регистра 2, в котором и-располагается длина выборки. В предлагаемом случае при зиачении счетчика 1, равном 2, на выходе коммутатора З появляется сигнал, по .которому счетчик итерации 4 наращивается на 1, а счетчик очищается. Таким образом, введение указанных блоков и связей позволит расширить функциональные возможности устройства за счет отработки массива разной длины.

//

11

П

ftit

Т2

..J

иг.У

Гактовые О f 23 5 В 7

С2

fj-

Фиъ.7