Генератор функций уолша

 

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

СОЮЗ СО8ЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

4(51) G 06 F 15/31

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

Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ СССР

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГГИЙ (21) 3694502/24-24 .(22) 23.01.84 (46) 07.07.85. Бюл. Ф 25 (72) П.М. Чеголин, P.Õ. Садыхов, А.В. Шаренков и С.А. Золотой

/ (71) Институт технической кибернетики АН Белорусской ССР (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

У 890409, кл. С 06 F 7/26, 1974;

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

И 781819., кл. G 06 F 15/31, 1977.. (прототип). (54)(57) ГЕНЕРАТОР ФУНКЦИЙ УОЛША, содержащий распределитель импульсов, первый выход которого подключен к тактовому входу регистра сдвига и тактовому входу первого регистра, информационный вход регистра сдвига является информационным входом генератора, тактовым входом которого является вход распределителя импульсов, отличающийся тем, что, е целью повышения быстродействия, в него введены первый и второй счетчики адреса, элемент ИСКЛЮЧАЮЩЕЕ КПИ, первый и второй мультиплексоры, второй регистр, первая и вторая группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ,.сумматор и блок памяти, выход i-ro (i = 1, m; m — разрядность) разряда которого подключен к первым входам i-х элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соответственно первой и второй групп, выходы которых подключены к .i-му разряду соответственно первого информационного входа первого мультиплексора и первого

„„Я0„„) 1 4

1 входа сумматора, выход i-ro разряда: которого подключен к i-му разряду второго информационного входа первого мультиплексора, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого является информационным выходом генератора и подключен к информацион- . ным входам блока памяти и первого регистра, информационный выход которого подключен к второму входу сумматора, вход переноса которого соединен с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой и второй групп и подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы которого подключены к выходам m"го и (m-1)-го разрядов регистра сдвига, второй выход распределителя импульсов подключен к управляющему входу второго мультиплексора, тактовому входу второго регистра и счетным входам первого и второго счетчиков адреса, информационные входы которых подключены соответственно к первому и второму информационным входам второго мультиплексора, информационный выход которого подключен к адресному входу блока памяти, управляющий вход которого подключен к третьему выходу распределителя импульсов, а управляющий вход первого мультиплексора является входом задания режима генератора, первый выход распределителя импульсов подключен к входу сброса первого счетчика адреса.

t 166134!

О в-15 е20

30

40

55

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

Известен генератор интегральных функций, содержащий генератор функ-ций Уолша и и-аналоговых блоков взвешенного алгебраического суммирования, где (n +1) — порядок генерируемой системы интегральных функций

Уолша) (1) .

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

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

Недостатком известного устройства является низкое быстродействие, так как вычисление одной интегральной функции Уолша происходит за (n+1) N, а все матрицы за N (n+1)

2 тактов работы генератора.

Цель изобретения — повышение быстродействия путем уменьшения количества тактов на вычисление одной функции Уолша.

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

ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй мультиплексоры, второй регистр, пер щя и вторая группы элементов исключающее ИЛИ, сумматор и блок памяти, выход i-ro (i = 1, m, m — разрядность) разряда которого подключен к первым входам 1 х элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ соответственно первой и второй групп, выходы которых подключены к i-му разряду соответственно первого информационного входа первоro мультиплексора и первого входа сумматора, выход i-ro разряда которого. подключен к i-му разряду второго информационного входа первого мультиплексора, информационный выход которого подключен к информационному входу второго регистра, информационный выход которого является информационным выходом генератора и подключен к информационным входам блока памяти и первого регистра, информационный выход которого подключен к второму входу сумматора, вход переноса которого соединен с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первой и второй групп и подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы которого подключены к выходам m-ro и (ш-1)-ro разрядов регистра сдвига, второй выход распределителя импульсов подключен к управляющему входу второго мультиплексора, тактовому входу второго регистра и счетным входам первого и второго счетчиков адреса, информационные входы которых подключены соответственно к первому и второму информационным входам второго мультиплексора, информапионный выход . которого подключен к адресному входу блока памяти, управляющий вход которого подключен к третьему выходу распределителя импульсов, а управляющий вход первого мультиплексора является входом задания режима генератора, первый выход распреде- лителя импульсов подключен к входу сброса первого счетчика адреса.

Принцип действия генератора функций Уолша основан на использовании

C рекуррентных соотношений для кусочнопостоянных функций Уолша WaI (с,х), WaI (01, х ) = WaI" (L >/2), х) при х N/2 (1)

WaI (О < х + N/2) а,6и, — (1) WaI (Са х) > (2) где t-"t означает целую часть;

9 сложение по модулю два, (4 « < -< ° ° ° < ) 20

1 2 3 4 5 6 7 8

1 2 3 4 3 2 1 О

2 1 О -1 -2 -1 . О

К „=

1210 1210

1 0-1 О 0-1 О

1 О -1 О -1 О 1 О

1 О 1 О -1 О -1 О

1 О 1 О, 1 О 1 О рим формирование кусо

Рассмот чно-линейной функции Уолша для

N 8,n 3, i= (0111)г =7 .

В исходном состоянии Х (г) (10000000). На 1-м шаге h„= 1, 00, iQ i = 1.

Тогда х1(о) = х (о) = !, х, (1) = х,(о) .— х

На 2-м шаге h „= 2, j = 0,1, i 9 i = О, :х (о) = х1(о) = 1; х (1) = х,(1), = 0; х (2) = х (1) + х,(О) = 1; х (3) = х (1) + х,(1) = О, 40

3 11661

Для кусочно-линейных функций Уолша, определяемых как

К„„ (i, t) .= f WaE (i, x)dx, о также справедливы следующие рекуррентные выражения:

К» (1, t) = К»% (с1/2) t)

N/г (3)

K ù (i, t) = К w ((1/2j, N/2-1) +

+ (-1) К (fi/21 ю t — N/2, 1О

1Щ

t - 1/2; = (ln-1 ° ° ° 1 ) (4)

Генерирование кусочно-линейных функций Уолша осуществляется за n шагов (и = Tog2 М). Алгоритм фор- 15 мирования кусочно-линейных функций

Уолша можно сформулировать следующим образом.

В исходном состоянии (на нулевом шаге) имеем массив

О 2 ... N-2 N-1 х (j)=(1 О О ... О О).

На к-м шаге при j = о, h к-1 где Ьк =. 2 если i . (+7 i О, то х„(j) = 25

= х к1 (j), (5) х„(3 + h„) — х„, (h„, )

+ x„, (j) (6)

Если 13- Я 15 = 1, то хк(1) хк- () < (7) 30 хк(З + 1 к1 = хк- 1 (1 к — х „„(j) (8)

Для N =. 8 матрица кусочно-линейных функций Уолша имеет вид

34 4 т.е х,(г) = (1 О 1 О О О О 0).

Наконец на 3-м шаге

h, =4, j =0,3, i<О э=О, х,(0) = х (О), х (1) =х (1); х, (2) = х (2); х (3) =х (3); х (4) = х (3) + ха(0) 1 х (5) = х (3) + х (1) = 0; х,(6) = х (3) + х (2) = 1, z (7) =х (3) +х (3) 0 °

Таким образом, 9(r) . чч ( (1 0 0 1 0 1 0).

На фиг. 1 представлена функциональная схема генератора функций

Уолша, на фиг. 2 — первые восемь функций Уолша и соответствующие им кусочно-линейные функции Уолша; на фиг. 3 — временные диаграммы работы блока формирования пачек импульсов и таблицы состояния блоков устройства при формировании второй кусочно-линейной функции

Уолша (код 0010) и пятой кусочнопостоянной функции Уолша (код 0101) в соответствии с тактами работы с устройства, на фиг. 4 и 5 — функциональные схемы распределителя импуль-, сов и арифметического блока соответственно.

Генератор функций Уолша содержит мультиплексор 1, группу элементов

ИСКЛЮЧАЮЩЕЕ И3% 2, регистр 3, арифметический блок 4, распределитель

5 импульсов, блок 6 памяти, мультиплексор 7, счетчики 8 и 9 адреса, регистр 10, регистр 1 1 сдвига, эле мент ИСКЛЮЧАЮЩЕЕ ИЛИ 12, информационный выход 13 устройства, выходы

14-16 блока 5, информационный вход

17 устройства, вход 18 задания режима устройства, тактовый вход 19 устройства.

Распределитель импульсов (фиг. 4) содержит циклический регистр 20 сдвига, двоичный счетчик 21, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 22, элемент ИЛИ-НЕ 23, линию 24 задержки, элементы И 25 и 26, триггер 27 °

Схема 4-разрядного арифметического блока содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 28 и (полный) сумматор 29.

Распределитель импульсов работает следующим образом.

Время задержки t9 на линии 24 задержки равно Т/4 (Т вЂ” период сле1166134 дования та;товых импульсов), Импульсы, поступающие с выхода линии 24 задержки, перемножаются с тактовыми импульсами элементом И 25, на выходе .14 которого формируется временная последовательность (фиг, 3).

В исходном состоянии в кольцевом регистре 20 сдвига записан код 001, триггер 27 установлен в "0", в двоичном счетчике 21 установлен код

"001". На группе элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 22 и элементе ИЛИ-НЕ 23 собрана схема совпадения кодов, вырабатывающая импульс иа выходе

16 при совпадении кодов на выходах двоичного счетчика 21 и кольцевого регистра 20 сдвига.

По спаду первого тактового импульса триг ер 27 установится в "1" и элемент И 26 разрешит прохождение импульсов с выхода элемента

ИЛИ-НЕ 23 на тактовый вход кольцевого регистра 20 сдвига. Таким образом, на выходе 17 распределителя импульсов вырабатывается импульс и по второму такту, при этом происходит сброс,в "0" двоичного счетчика 21 и сдвиг "1" в соседний старший разряд кольцевого регистра 20 сдвига. Следующие импульсы на выходе 16 блока 5 появятся по 2, 2, .. °, 2 тактовым импульсам соглас-

П но временной диаграмме (фиг. 3) .

Арифметический блок 4 работает следующим образом.

При "0" на управляющем входе в сумматоре происходит сложение прямых кодов, поступающих на его входы. При "1" на управляющем входе код, поступающий на входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 28, инвертируется, в младший разряд сумматора добавляется "1" и происходит сложение полученных кодов.

В этом случае при отрицательном результате сложения он будет представлен в дополнительном коде.

Генератор функций Уолша работает следующим образом.

Мультиплексор 1 управляет формированием класса генерируемых функций. Если выходы элементов 2 через мультиплексор 1 подсоединены к входу регистра 3, то на выходе 13 .устройства формируются кусочно-пос.тоянные функции Уолша. В случае . подключения выхода арифметического блока 4 к входу регистра 3 на выхоS

1О

1S

ÇS

40 де 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 в соответствии с выражением

1n-i + и 0

Причем "1" соответствует операция вычитания для арифметщ1еского блока

4 и инвертирования для группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 2, а "0"— операция сложения и передачи сигнала без инверсии соответственно. По первому импульсу с выхода 16 распределителя 5 импульсов в разряды з., ..., п регистра 11 сдвига (i — младший разряд) записывается двоичный код номера генерируемой

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

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

S В случае формирования кусочнопостоянных функций Уолша выход блока 6 памяти через группу элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ 2 и мультиплексор

1 подключается к входу регистра 3.

1© Формирование функций Уолша происходит аналогично в соответствии с временными диаграммами (фиг. 3). Отрицательные значения ординат кусочнопостоянных функций Уолша представ1З лены в обратном коде.

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

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

И

Хаким образом, одна функция Уолша вычисляется за N тактов, а вся матрица Уолша размерностью Ы ° N—

2 за N тактов, т.е. предлагаемое

3ф устройство обладает в n + 1 раэ более высоким быстродействием по сравнению с известным.

1166134 к, r

Kf f

Ку

К

О

Cf /

О

К 1

К7 о

1166134

) )66)34

Составитель А. Баранов

Техред М.Гергель Корректор М. Пожо

Редактор А. Козориз

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

Заказ 4312/45 Тираж 710 Подписное

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

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