Генератор функций Уолша Советский патент 1985 года по МПК G06F17/14 

Изобретение относится к автоматике и вычислительной технике и мо жет быть использовано, в частности в апгфоксимирующих устройствах кусочно-линейного типа. Известен генератор интегральных функций, содержащий генератор функ ций Уолша и п-аналоговых блоков взвешенного алгебраического суммир вания, где (п +1) - порядок генери руемой системы интегральных функци Уолша) l3 . Недостаток устройства - низкая точность, обусловленная большой ин струментальной погрешностью резист ной матрицы на входах аналоговых блоков взвешенного суммирования. Наиболее близким техническим решением к изобретению является ге ратор интегральных функций Уолша, содержащий кольцевой регистр сдвига номера функции, кольцевой регистр сдвига аргумента, регистр сдвига, два триггера, элементы И, блок формирования пачек импульсов и блок преобразования прямого кода в дополнительный, причем тактовый, вход регистра сдвига связан с тактовым входом первого регистра и первым выходом блока формирования пачек импульсов, второй выход которого соединен с тактовым входом второго регистра . Недостатком известного устройст ва является низкое быстродействие, так как вычисление одной интеграль ной функции Уолша происходит за (h+1) N, а все матрицы за N (п+1) тактов работы генератора. Цель изобретения - повьш1ение быстродействия путем уменьшения количества тактов на вычисление од ной функции Уолша. Поставленная цель достигается тек, что в генератор функций Уолша содержащий распределитель импульсов, первый выход которого подключен к тактовому входу регистра сдв га и тактовому входу первого регистра, информационный вход регист ра сдвига является информационньм входом генератора, тактовым входом которого является вход распределителя импульсов, введены первый и второй счетчики адреса, элемент ИСКШЧАЮЩЕЕ ИЛИ, первый и второй мультиплексоры, второй регистр, пе вая и вторая группы элементов исключающее ИЛИ, сумматор и блок памяти, выход i-ro (1 1 , га; m - разрядность) разряда которого подключен к первьм входам i-x элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соответственно первой и второй групп, выходы которых подключены к i-му разряду соответственно первого информащюнного входа первого мультиплексора и первого входа сумматора, выход i-ro разряда которого.подключен к i-му разряду второго информационного входа первого мультиплексора, информационньй выход котогрого подключен к информационному входу второго регистра , информационный выход которого является информационным выходом генератора и подключен к информационным входам блока памяти и парвого регистра, информационный выход которого подключен к второму входу сумматора, вход переноса которого соединен с вторыми.входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой и второй групп и подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый И второй входы которого подключены к выходам т-го и (m-l)-ro разрядов регистра сдвига, второй выход распределителя импульсов подключен к управляющему входу второго мультиплексора, тактовому входу второго регистра и счетным входам первого и второго счетчиков адреса, информационные входы которых подключены соответственно к первому и второму информационным входам второго мультиплексора, информаи ионный выход которого подключен к адресному вхоДУ блока памяти, управляющий вход которого подключен к третьему выходу распределитедя импульсов, а управляющий вход первого мультиплексора является входом задания режима генератора, первьй выход распределителя импульсов подключен к входу сброса первого счетчика адреса. Принцип действия генератора функций Уолша основан на использовании рекуррентных соотношений для кусочнопостоянных функций Уолша Wal ( oJ,x), Wai ( u), X ) (, x) при X (W, X + N/2) Wai (-1) Wai (60. x) .. -.. , где Lj означает целую часть; @ сложение по модулю два, w (.V... t),. 3 Для кусочно-линейных функций У ша, определяемых как К (i, t) Wai (i. x)dx, также справедливы следующие рекур рентные выражения: П t «г N(i, t) ( i/2, t), ( , t) KV (Г1/21, N/2-1) + (-l)-® , (1/21. t - N/2, , i („, ifl. ,...) . :(4) Генерирование кусочно-линейных функций Уодша осуществляется за п шагов :(п logj N). Алгоритм фо мирования кусочно-линейньпс функда Уолша можно сформулировать следую щим образом. В исходном состоянии (на нулевом шаге) имеем массив О 1 2 ... N-2 N-1 x(j) (1 О О ... О 0) На к-м шаге при j о, h, , где he , IK О, то Xj,(j) X,., (j); XK(J + Ь„) х,, (h., ) + XK-I J Если i., ф i 1, то x(j) хц., (j); x(j + h) x,tvi (h|c - 1) - X,., (j)( Для N 8 матрица кусочно-лине ных функций Уолша имеет вид 1234567-8 2343210 21 0-1-2-10 Рассмотрим формирование кусоч но-линейной функции Уолша для N 8, п 3, i (0111) 7. В исходном состоянии ХдСг) (10000000). На 1-м шаге h 1, j 0,0, iS) i, 1. Тогда x(o) Xo(o) 1, x,(1) Xg(o) - x(o) 0, т.е. x,(r-). ,( 1 0 0 0 0 0 ). Ha 2-M шаге , j 0,1, i, Ф ij 0, x(o) x,(o) i; xj(l) x,(iX o; 315(2) x,(1) + x,(0) 1; X2(3) x,(1) + x,(1) 0, 4.4 T.e.XjCr) (10100000). Наконец на 3-м шаге hf А, j (ЗТЗ, ii@ i, о; х,(0) х,г(0). /1) Xj(1); x,(2) X2(2)i x,(3) Xj(3)j x(3)+ Xj(0) x,(3)+ x,(1) x;(6) x,(3) + x,(2) U x,(7) X2(3) + x,(3) 0; Таким образом, x,(r) K (7, t) (10101010). Ha фиг. 1 представлена функциональная схема генератора функций Уолша} на фиг. 2 - первые восемь функций Уолша и соответствующие им кусочно-линейные функции Уолша; на фиг. 3 - временные диаграммы работы блока формирования пачек импульсов и таблицы состояния блоков устройства при формировании второй кусочно-линейной функции Уолша (код 0010) и пятой кусочнопостоянной функции Уолша (код 0101) в соответствии с тактами работы устройства на фиг. 4 и 5 - функциональные схемы распределителя импульсов и арифметического блока соответственно. Генератор функций Уолша содержит мультиплексор 1, группу элементов ИСКЛЮЧАЮЩЕЕ ШШ 2, регистр 3, арифметический блок 4, распределитель 5 импульсов, блок 6 памяти, мультиплексор 7, счетчики 8 и 9 адреса, регистр 10, регистр 11 сдвига, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 12, информационный выход 13 устройства, выходы 14-16 блока 5, информационный вход 17 устройства, вход 18 задания режима устройства, тактовый вход 19 устройства. Распределитель импульсов (фиг. 4) содержитциклический регистр 20 сдвига, двоичный счетчик 21, группу элементов ИСКПЮЧАЯЯЦЕЕ ИЛИ 22, элемент ИЛИ-НЕ 23, линию 24 задержки, элементы И 25 и 26, триггер 27. Схема 4-разряднрго арифметического блока содержит группу элементов ИСКЛЮЧАКЯЦЕЕ ИЛИ 28 и (полный) умматор 29. Распределитель импульсов работает следующим образом. Время задержки t на линии 24 задержки равно Т/4 (Т - период еле 5 дования та.стовых импульсов). Импул сы, поступающие с выхода линии 24 задержки, перемножаются с тактовыми импульсами элементом И 25, на выходе 14 которого формируется вре менная последовательность (фиг. 3) В исходном состоянии в кольцевом регистре 20 сдвига записан код 001 триггер 27 установлен в О, в дво ичном счетчике 21 установлен код 001. На группе элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 22 и элементе ШШ-НЕ 23 собрана схема совпадения кодов, вырабатывающая импульс на выходе 16 при совпадении кодов на вьрсодах двоичного счетчика 21 и кольцевого регистра 20 сдвига. По спаду первого тактового импульса 27 установится в 1 и элемент И 26 разрешит прохождение импульсов с вБгхода элемента Ш1И-НЕ 23 на тактовый вход кольцевого регистра 20 сдвига. Таким образом, на выходе 17 распределителя импульсов вырабатывается импульс и по второму такту, при этом проис ходит сброс в О двоичного счетчи ка 21 и сдвиг 1 в соседний старший разряд кольцевого регистра 20 сдвига. Следующие импульсы на выхо де 16 блока 5 появятся по 2 , 2, ..., 2 тактовым импульсам согласно временной диаграмме (фиг. 3). Арифметический блок 4 работает следующим образом. При О на управляющем входе в сумматоре происходит сложение прямых кодов, поступающих на его входы. При 1 на управляющем входе код, поступающий на входы труппы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 28, инвертируется, в младший разряд сумматора добавляется 1 и происходит сложение полученных кодов. В этом случае при отрицательном результате сложения он будет представлен в дополнительном коде. Генератор функций Уолша работает следующим образом. Мультиплексор 1 управляет формированием класса генерируемых фун ций. Если выходы элементов 2 через мульти1шексор 1 подсоединены к входу регистра 3, то на выходе 13 устройства формируются кусочно-пос . тоянные функции Уолша. В случае подключения выхода арифметического блока 4 к входу регистра 3 на выхо 4 де 13 будут сформированы кусочнолинечные функции Уолша. Кусочно-линейные функции Уолша формируются следующим образом. В исходном состоянии в регистре 3 записан код 001, а в остальных регистрах и счетчиках - нулевой код, тактовые импульсы поступают на тактовый вход распределителя 5 импульсов, на счетные входы счетчиков 8 и 9 адреса и на управляющий вход мультиплексора 7, причем высоким уровнем сигнала к адресной шине блока 6 памяти подключается выход счетчика 9 адреса, формирующий адрес записи, а низким - выход счетчика адреса 8, формирующий адрес считывания. Запись информации в блок 6 памяти происходит по импульсам, поступающим с выхода. 14 распределителя 5 импульсов на управляющий вход Чтение-запись блока 6 памяти, причем низкий уровень сигнала соответствует операции Чтение, во время которой происходит сложение (вычитание) кодов регистра 10 с кодом ячейки блока 6 памяти, адрес которой сформирован счетчиком 8 адреса, и запись результата в регистр 3 по тактовым импульсам, на выходе 16 распределителя 5 импульсов формируется последний импульс последовательности 2, 2 , ..., 2 (фиг. 3), по которому происходит запись информации в регистр 10, сброс счетчика 8 адреса в исходное состояние и сдвиг информации влево в регистре 11сдвига. Выходы двух старших разрядов регистра 11 сдвига, соединены с входами элемента ИСКЛЮЧАЮЩЕЕ ШШ 12, на выходе которого формируется сигнал управления арифметическим блоком 4 и группой элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 2 в соответствии с выражением -io. Причем 1 соответствует операщ1Я вычитания для арифмети{1еского блока 4 и инвертирования для группы элементов ИСКЛЮЧАННЦЕЕ ШШ 2, а О опера1Ц1Я сложения и передачи сигнала без инверсии соответственно. По первому импульсу с выхода 16 распределителя 5 импульсов в разряды i 2 ; 1„ регистра 11 сдвига (ij, - младший разряд) записьгаается двоичный код .номера генерируемой

функции, а в разряд ig - О, На

выходе элемента ИСКЛЮЧАЩЕЕ ИЛИ 12 I формируется сигнал ip@i, ив регистр 3 записывается результат арифметической операции над содержимьм регистра 10 и ячейки блока 6 памяти, адрес которой формируется в счетчике адреса 8. Затем этот результат переписывается в блок 6 памяти по адресу, содержащемуся в счетчике 9 адреса и, если данньй такт совпадает с импульсом на Ьыходе 16 распределителя 5 импульсов, происходит запись в регистр Юн. сдвиг информации в регистре 11 сдвига. В регистре 10 запоминается последнее значение предьщущего шага , алгоритма, которое далее суммируется (вычитается) последовательно с содержимым ячеек блока 6 памяти (адреса которых формируются в счетчике 8 адреса), записывается в регистр 3 и ячейки блока 6 памяти, адреса которых формируются счетчиком адреса 9.

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

формирования второй кусочно-линейной функции Уолша (код 0010) и пятой кусочно-постоянной функции Уолша (код 0101).

В случае формирования кусочнопостоянных функций Уолша выход блока 6 памяти через группу элементов ИСКЛЮЧАЮПЩЕ ИЛИ 2 и мультиплексор 1 подключается к входу регистра 3. Формирование функций Уолша происходит аналогично в соответствии с временнь&ш диаграммами (фиг. 3). Отрицательные значения ординат кусочнопостоянных функций Уолша представлены в обратном коде.

При формировании кусочно-линейных функщ1й Уолюа отрицательные значения ординат представлены в дополнительном коде.

По N + 1 такту происходит установка в исходное состояние всех регистров и счетчиков и процедура вычислений может быть повторена для следующей функции Уолша.

Таким образом, одна функция Уолша вычисляется за N тактов, а вся матрица Уолша размерностью N N за N тактов, т.е. предлагаемое устройство обладает в п 1 раз более высоким быстродействием по |Сравнению с известным.

ГЕНЕРАТОР. ФУНКЦИЙ УОЛША, содержащий распределитель импульсов, первьй выход которого подключен к тактовому входу регистра сдвига и тактовому входу первого регистра, информационный вход регистра сдвига являемся информационным входом генератора, тактовым входом которого является вход распределителя импульсов, отличающийся тем, что, с цепью повьпяения быстродёйстВИЯ, в него введены первый и второй счетчики адреса, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй мультиплексоры, второй регистр, первая и вторая группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ сумматор и блок памяти, выход 1-го (i 1, т; m - разряд йость) разряда которого подключен к первым входам i-x элементов ИСКЛЮЧАЩЕЕ или соответственно первой и второй групп, выходы которых подключены к ,1-му разряду соответственно первого информационного входа первого мультиплексора и первого входа сумматора, выход 1-го разряда которого подключен к i-му разряду второго информационного входа первого мультиплексора, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого является информационным выходом генератора и подключен к информационным входам блока памяти и первого регистра, информационный выход которого подключен к второму входу сумматора, вход переноса которого соединен с вторыми входами элемен- тов ИСКЛЮЧАЮЩЕЕ ИЛИ первой и второй групп и подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый (Л и второй входы которого подключены к выходам т-го и (m-l)-ro разрядов регистра сдвига, второй выход распределителя импульсов подключен к управляющему входу второго мультиплексора, тактовому входу второго регистра и счетным входам перОд вого и второго счетчиков адреса, 0д информационные входы которых подключены соответственно к первому 00 4i и второму информационным входам второго мультиплексора, информационный выход которого подключен тс адресному входу блока памяти, управляющий вход которого подключен ,к третьему выходу распределителя , импульсов, а управляющий вход первого мультиплексора является входом задания режима генератора, первый выход распределителя импульсов подключен к входу сброса первого счетчика адреса.

L

Wae.f

I.

Щ 1

О

/А f/2 5А

Кп f

Wf 1

Ki / О

W 1

щ /

W4 / О

Щ / О

Wg /

. о

Щ 1

к i о

Фиг.г

« nS

C

Г

Фиг4

BL ..Ai

SL

f

Фиг.5