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

 

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

ае 01) МЮ . и 06 F 15 3.3

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОУО40МУ СЮМЗЮИЗЪСФВМ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ 000Р

Д В ЭЭФ Ю Ю (21 ) 3520311/18-24 (22) 03.12.82 (46) 23.02.84 ° Бюл. 9 7 (72) A.Т.Клышбаев (71) Конструкторское бюро вычислительной техники при Дальневосточном орде-, на Трудового Красного Знамени поли .-, техническом институте нм.В.В.Куйбышева (53 ) 881.32(088.8) (56.) 1, Авторское свидетельство СССР

В 809198р кл. 6 06 F 15/332, 1981.

2. Авторское свидетельство СССР

Э 723582, кл. Я 06 F 14/332, 1980 (прототип). (54) УСТРОИСТВО ДЛЯ ВЫЧИСЛЕНИЯ ИРЕ»

ОБРАЗОВАНИЯ УОЛША (BAPHAHTbl), (57) 1. Устройство для вычисления преобразования Уолша, содержавшее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторьэи информационными входамн арифметического блока, информационный выход которого соединен с информационным входом Ипока памяти, управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти,:выход второго и третьего разрядов которого соединены с тактовыми входами соот1. ветствеино.первого и второго регист- . ров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока-постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока по- стоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов, вход запуска которого является входом..за" пуска устройства, второй блок постоянной памяти, счетчик итерации, о т-. л и ч а в ш е е с я тем, что, с

° целью расШирения области применения путем обработки последовательностей произвольной длины, в него введены регистр базы, второй коммутатор, сум- матор и регистр длины выборки, информационный выход которого соединен с управляющим входом второго коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационньм выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счет- Я чика адреса и подключен к первому .входу сумматора, выход которого соединен с управляюцим входом первого коммутатора, информационный вход ко торого объединен с информационными выходами первого и второго регистров и подключен к информационному выходу блока памяти, .BTopogf информационный, выход второго блока постоянной памяти соединен с установочньм входом счетчика адреса, второй вход сумматора (,",) подключен к информационному выходу регистра базы, информационный вход которого объединен с информационным (Д входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого ком- ©) мутатора является информационным выходом устройства.

2. Устройство для вычисления преобразователя Уолша, содержацее первый коммутатор, первый и второй ре- фю гистры, информационные выходы которых соединены соответственно с пер.вым и вторым информационными входами арифметического блока, информационный выход которого соединен с

Информационнюе входом блока памяти, управляющий вход которого соединен с выходом первого разряда первого

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

Изобретение относится к вычис-.

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

ы подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и адресным входом блока памяти, информационный выход которого соединен с информационными входами первого и второго регистров и является информационным выходом устройства, второй информационный выход вто-! рого блока постоянной памяти соединен с установочным входом счетчика адреса, информационный вход регистра длины выборки объединен с информационными входами первого и второго регистров . ма быстрого преобразования Уолша (БПУ), который используется при цифровой обработке сигналов. блока памяти, управляющий вход которого соединен с выходом первого разряда первого блока постоянной памяти, выходы второго g третьего разрядов которого соединены с тактовыми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвертого разряда первого блока постоянной памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационньаи выходом счетчика, тактовый вход которого подключен .к выходу генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постояниой памяти, счетчик итераций, введены регистр базы, второй коммутатор, сумматор и регистр длины выборки, информационный выход которого соединен с управляющим входом второго коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и.подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса и подключен к первому входу. сумматора, выход которого соединен с управляющим входом первого коммутатора, информационный вход которого объединен с информационными выходом первого и второго регистров и подключен к информационному выходу блока памяти, второй информа-. ционный выход второго блока постоянной памяти соединен с установочным входом, счетчика адреса, второй .вход сумматора подключен к информационному выходу регистра базы, информационный вход которого объединен с информационным входом регистра длины выборки и информационными входами первого и второго регистров, а выход первого коммутатора является информационным выходом устройства.

11оставленная цель достигается тем, что по второму варианту устройство, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторьви информационными входами арифме тического блока, информационный выход которого соединен с информационным входом блока памяти, управляющий вход которого соедйнен с выходом первого разряда первого блока .постоянной памяти, выходы второго и третьего разрядов которого соединены с такто-, 3

10752

Известно устройство для реализации быстрого преобразования Фурье, содержащее два коммутатора, регистр йтерации,, счетчик адреса, постоян-, .ное запоминающее устройство (ПЗУ1, сумматор 1>. 5

Недостаток данного решения заключается в том, что это устройство жестко привязано к длине выборки, при изменении длины выборки требуется внесение изменений в схему устройства.

Наиболее близким по технической сущности к изобретению является устройство для.выполнения быстрого преобразования Фурье, содержащее первый коммутатор, первый и второй регистры, информационные выходы которых соединены соответственно с первым и вторым информационными входами арифметического блока, информационный выход которого подключен к информационному входу блока памяти, управляющий вход которого подключен к выходу первого разряда первого блока постоянной памяти, выходы второго и третьего разрядов которого соединены с актовыми входами соответственно первого и второго регистров, информационные входы которых . являются информационным входом устройства, тактовый вход счетчика ад- 3О реса соединен.с выходом четвертого разряда .первого блока постоянной памяти, адресный вход которого подключен к информационному выходу.счетчика, тактовый вход которого соединен З5 с выходом генератора тактовых импульсов, вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций (2 ).

4Ь

Однако известное устройство аппаратно ориентировано к конкретной длине выборки, которое является следствием использования в качестве ОЗУ памяти с последовательным доступом 45 (сдвиговых регистров ). В том случае когда длина выборки не совпадает с ем-, костью памяти, эффективность устрой 1 ства резко ухудшается, причем ухудшение зависит от отношения 2/2

v e где V - -емкость памяти, 2 — дли- 5О

3 на выборки и приблиэительйо равна

2 -5

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

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

1075 выми входами соответственно первого и второго регистров, информационные входы которых являются информационными входами устройства, выход четвер- того разряда первого блока постояниой памяти соединен с тактовым входом счетчика адреса, адресный вход первого блока постоянной памяти соединен с информационным выходом счетчика, тактовый вход которого подключен к выходу генератора тактовых импульсов 10 вход запуска которого является входом запуска устройства, второй блок постоянной памяти, счетчик итераций, введены регистр базы, второй коммутатор, сумматор и регистр длины выбор- 15 .ки, информационный выход которого соединен с управляющим входом второго коммутатора, выход которого соединен с входом обнуления счетчика адреса и тактовым входом счетчика итераций, информационный выход которого объединен с информационным выходом счетчика адреса и выходом пятого разряда первого блока постоянной памяти и подключен к адресному входу второго блока постоянной памяти, первый информационный выход которого соединен с информационным входом счетчика адреса-и подключен к первому входу сумматора и адресному входу блока памяти, выход сумматора подключен к управляющему входу первого коммутатора, информационный вход которого объединен с информационными входами первого и второго регистров и подключен к информационному выходу блока памяти, 35 второй информационный выход второго. блока постоянной памяти соединен с установочным входом счетчика адреса, второй вход сумматора подключен к информационному выходу регистра ба- 40 зы, информационный вход которого объединен с информационным входом регистра длины выборки и информационными входами первого и второго регистров, а выход пеРвого коммутато- 45 ра является информационным выходом устройства.

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

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

Наличие в схеме коммутатора при конкретной технической реализации определяется особенностью организации канала или магистрали сателлитной

ЭВИ. Например, для магистрали, в которой подшины данных и адреса разделены на две подшины, нет необходимости передачи данных адресов но одной общей шине, следовательно, нет необходимости и в этом коммутаторе, а если адреса -и данные передаются по одной магистрали, то коммутатор необходим. Второй информационный вход этого коммутатора соединен с выходом автономного блока памяти, причем выход блока. ОЗУ должен быть либо с тремя состояниями, либо с открытой коллекторной нагрузкой, потому что этот выход образует совместно с входом устройства микроканал устройства, к которому подсоединены информационные входы процессора, регистра выборки и регистра базы.

В решении устройства в целом возможны варианты. При втором варианте емкость блока памяти может быть, значительно уменьшена в зависимости от пределов длин выборск. Второй вариант может иметь упрощенное решение.

Устройство по третьему варианту ,теряет возможность использования блока памяти сателлитной ЭВИ в качестве рабочей памяти и способно работать только со своим блоком памяти.

1075269

На фиг.1 приведена функциональная блок-схема устройства, на фиг.2функциональная блок-схема второго варианта; на фиг.3 — функциональная блок-схема третьего варианта модуля на фиг.4 — граф алгоритма быстрого 5 преобразования Уолша-Адамара с замещением; на фиг.5 — блок-схема процессора, на фиг.б — временная диаграмма работы процессора) на фиг.7 — блоксхема устройства в комплексе е ЭВМ. )9

Устройство для вычисления преобразования Уолша содержит счетчик адреса 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 ориентирован на выполнении базовой операции,и состоит из умножителя и сумматора.

Рассмотрим работу устройства на примере работы первого варианта как наиболее общего случая. Работа частных вариантов не отличается от рабо- 30 ты первого варианта в соответствующих режимах. Сначала рассмотрим режимы работы устройства с внешней памятью, в качестве которого используется память сателлитной 3BN. Пусть для опре- 35 деленности необходимо произвести преобразование Уолша над массивом 2, который размещен в ОЗУ ЭВМ, начиная с адреса К на адрес К + 2. При начальном обращении к модулю осуществ- gg ляется настройка модуля к рабочему полю памяти и к длине выборки (массива). Для этого начальный адрес К загружается в регистр базы 6, а длина выборки 6 - в регистр Т и управ-45 ление передается процессору 9. С этого момента устройство становится активным и осуществляет обмен данных с ОЗУ в режиме прямого доступа к памяти. Цикл состоит иэ двух тактов °

На первом такте устройство выставля- 5О ет в магистраль адрес ячейки ОЗУ, на втором такте осуществляется передача (или прием ) данных. Устройство выставляет адрес в магистраль с выхода сумматора 7 через первый вход 55 коммутатора 10, а данные выставляются в общем случае с выхода блока 8.

Суть быстрого преобразования Уолша заключается в том, что циклически выполняется базовая операция, Я) причем результат суммирования засылается по адресу операнда А, который будем называть верхним операндом, а результат вычитания засылается поадресу операнда В(нижний операнд ). б5

Адреса операндов формируются согласно графа алгоритма (фиг.4). Сначала покажем работу устройства на одной базовой операции,.а затем покажем как в устройстве осуществляется переход на следующую операцию внутри итерации, а также переход с итерации на итерацию.

Выполнение одной базовой операции состоит из трех тактов работы устройства. На -первом такте формируется цикл обращения к ОЗУ ЭВМ для выбора верхнего адреса A. Для этого процессор 9 устанавливает для блока 5 признак верхнего адреса, по которому блок 5 на вход сумматора 7 пропускает текущее значение счетчика 1, например i . Адрес этот представляет собой абсолютный адрес, во втором и четвертом вариантах он непосредственно подается на адресную шину автономного блока 8, а в тех вариантах, которые работают с памятью ЭВМ, арифметически суммируется с адресоМ базы на регистре б и с выхода сумматора 7 через ком; мутатор 10 подается в магистраль.

Выбираются данные по этому адресу с ОЗУ ЭВМ и по входу 11 заносятся во внутренний. регистр 9.1 процессора 9. На этом завершится первый такт ° На втором такте выбирается нижний операнд. Но в этом случае блок 5 по признаку процессора 9 формирует абсолютный адрес в виде суммы по rood 2 текущего значения счетчика 1 (адрес верхнего операнда ) -и унитарного кода номера итерации, т.е. на j итерации нижний операнд. представляется как i 9 g> . Нижний операнд заносится в регистр 9.1 процессора 9. Но такт этот завершается.засылкой результата вычитания по адресу нижнего операнда, т.е. в этом такте ОЗУ работает в режиме "Ввод-Пауза-Вывод". На третьем такте процессор .9 восстанавливает признак верхнего операнда, по которому производится запись суммы операндов, По концу выполнения базовой операции процессор 9 наращивает значение счетчика 1 на единицу и.осуществляется переход на следующую операцию. Из-эа того, что верхний и нижний операнды являются элементами одного массива и эти элементы на итерации должны только один раз участвовать в базовой операции, нарушается линейный порядок выбора операндов иэ массива, причем длина группы верхних (соответственно и нижних ) операндов, расположенных в последовательных ячейках памяти, зависит от номера итерации. Эта особенность расположения операндов хорошо прбсматривается на графе алгоритма (фиг.4), поэтому возникает необходимость переустановки счетчика 1, суть

1075269

10 которого заключается в том, что в счетчик 1 заносится адрес нижнего операнда базовой операции, после которой возникает ситуация для переустановки счетчика 1, только после этого счетчик 1 наращивается на еди-" 5 ницу.

Теперь покажем как осуществляется переход с итерации на итерацию, хак как решение этого момента является одним из существенных отличи- )Q тельных признаков предлагаемого решения. В прототипе переход на следующую итерацию осуществляется при появлении сигнала переполнения счетчика 1, по которому счетчик итерации 4 изменяет свое состояние. Но для того, чтобы управлять моментом переноса, который зависит от длины выборки, введены регистр длины выборки 2 и коммутатор 3. При этом сигнал переноса из счетчика 1 в счетчик 4 про-... ходит через коммутатор 3. A так как информационные входы коммутатора 3 соединены с выходами разрядов счет чика 1 номера которых соответствуют длине выборки, открыв соответствующий канал коммутатора 3, с выхода ,которого сигнал переполняется не только наращивает значение счетчика 4

" íî и очищает сам счетчик 1, можно контролировать моменты переноса а. следовательно, эффективно использовать устройство на преобразованиях массивов с различным числом элементов (но кратным степени 2). Выбор канала коммутатора 3 осуществляется значением регистра 2, в котором и -располагается длина выборки.

В предлагаемом случае при значении счетчика 1, равном 2, на выходе коммутатора 3 появляется сигнал, по которому счетчик итерации 4 наращивается на "1", а счетчик очищается.

Таким образом, введение указанных блоков и связей позволит расширить функциональные возможности устройства за счет отработки массива разной длины.

1075269

1075269

Фие. Х г

1075269

ТактоВые 2 S Ф Х Ю 7 ими ъ =>1») 4!

1 % (ф Фа } фф1

Фае. Ю

Составитель А. бауанов .

Техред Л.Коцвбняк. Корректор О,Билак

Редактор Н.Пушненкова

Тираа 699 Подписное

ВНИИПИ Государственного комитета СССР по делам иэобретений и -открытий

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Закаэ 1087

Филиал ППП "Патент", г. Умгород, ул. Проектная, 4