Генератор функций уолша
Изобретение относится к области автоматики и вычислительной техники и может быть использовано в аппроксимирующих устройствах кусочно-линейного типа, для спектрального анализа случайных процессов,в устройствах сжатия информации. Цель изобретения - повьшение быстродействия генератора. В состав блока генератора входят три регистра сдвига, четыре регистра, блок памяти, два сумматора, сумматорвычитатель , сумматор по модулю два, два коммутатора, схе.мй сравнения, блок элементов И, три элемента И. Предлагаемая конструкция позволяет реализовать алгоритм вычислений обобщенных интегральных функций Уолша с числом шагов, существенно меньшим, Q чем в известном генераторе. 2 нл.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
„.SU„„1262470
ag 4 С 06 F 1/02
OIlHCAHHE ИЗОБРЕТЕНИЯ
К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (2 1) 3868933/24;24 (22) 19.03.85 (46) 07.10.86. Бюл. У 37 (71) Институт технической кибернетики
АН БССР (72) П.М.Чеголин, Р.Х.Садыхов, А.В.Шаренков и С.А.Золотой (53) 681.3(088.8) (56) Авторское свидетельство СССР
У 864274, кл. С 06 F 1/02, 1979.
Авторское свидетельство СССР
И 1156089, кл. G 06 F 1/02, 1983; (54) ГЕНЕРАТОР ФУНКЦИЙ УОЛША (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в аппроксимирующих устройствах кусочно-линейного типа, для спектрального анализа случайных процессов,в устройствах сжатия информации. Цель изобретения— повышение быстродействия генератора.
В состав блока генератора входят три регистра сдвига, четыре регистра, блок памяти, два сумматора, сумматорвычитатель, сумматор по модулю два, два коммутатора, схема сравнения, блок элементов И, три элемента И.
Предлагаемая конструкция позволяет реализовать алгоритм вычислений обобщенных интегральных функций Уолша с числом шагов, существенно меньшим, чем в известном генераторе. 2 ил.
12 (2) (4) где К = О, 2" ;
S = 2
1 (s) Изобретение относится к автоматике и вычислительной технике и может быть использовано в аппроксимирующих устройствах кусочно-линейного типа, для спектрального анализа случайных процессов, в устройствах сжатия информации.
Целью изобретения является повышение быстродействия генератора.
На фиг.1 представлена функциональная схема генератора функций Уолша, на фиг,2 — граф. алгоритма вычислений фукций К (2, 7, х).
Генератор функций Уолша содержит регистр 1 сдвига, сумматор 2, коммутатор 3, сумматор 4, регистр 5, регистр 6 сдвига, схему 7 сравнения, элемент И. 8, двухразрядный счетчик 9, выходную шину 10, блок 11 памяти, элемент И 12, коммутатор 13, элемент
И 14, регистр 15, сумматор-вычитатель 16, регистр 17, блок 18 элементов И, регистры 19 и 20 сдвига, сумматор 21 по модулю два. Группа блоков
1-9 образует адресную часть схемы генератора, группа блокев 14-21 — арифметическую часть, Система обобщенных интегральных .функций Уолша определяется следующим образом (- t
К(р, В, t) = t waf(p, x) .
62470 2 (о) при начальных условиях К, = 1, (о)
К. о О.
Преобразования на j-м шаге описываются рекурентными соотношениями (j +)) (J (J) Р„(j ) К, = (-1) К + (-1) К 1
RS Si2 RS
Яз 5(3) 10
ОприХ. +р, 1 (Já1)
Я «)
2К при f + р. 0, йз J р . — значения 3-го разряда в двоичных (— разрядных кодах 5, р (нумерация со стороны младших разрядов).
После выполнения шага с номером п-1 получаем (h)
K1,K(p К 1 дх/T).
В качестве примера рассмотрим вычисления при N = 8, р = 2, 1 = 7.
Для наглядности на фиг.2.показан граф вычислений функции К(2, 7, х), .стрелками отмечены операнды выражений (3) и (4) на каждом шаге преобразований:
1-й шаг (j = О):
waf(C, х + t) dx, где waf(r, х) — функция Уолша с номером r.
В зависимости от упорядочения сис- 40 темы функций Уолша возможны различные способы упорядочения обобщенных интегральных функций: по Адамару, по
Пэли и по Качмажу. При переходе из одной системы в другую номера р, 4 па- 45 ры функций Уолша, используемых в выражении (1), изменяются, В системе Уолша-Пэли значения
K(p ° f 14х/T) 1 = 0; N
50 дискретной обобщенной интегральной
h функции Уолша К(р, f., х), где И 2 число отсчетов за период Т, могут быть получены в результате и шагов преобразования массива чисел (.) )
К, i = О; N j = О; и-1 (K ) = (1оооооооо), R=0;0, S=8, $/2=4, (.=1, р -О.
2-й шаг (j = 1): (K, j = (0000-10000), R 0; 1, S 4, $/2=2, 1,р 1, 1 () (1) (1)
К вЂ” К вЂ” К 4 8+ 2 аа 4Яб 4 (2) (1)
К4Я = 2КЯ
3-й шаг (j = 2): — (0010-20100), 3,$=2,S/2=1, = о.
R = --0
Э
P 2 (1) (2) (3)
-K + К Й
2R+1 2R 2Я+2 2Я (1) (О)
BR+4 8R ЯР Я 8Я е
1262470
Таким обр4зом, функция К (2, 7, х) представляется отсчетами (К(2,7,ihx/T)s = (0,1,0,-3,0,3, Устройство работает следующим образом. (э l
Массив чисел К хранится в блоке
1! памяти по адресам i. Перед началом вычислений содержимое блока 11 памяти определяется, выражением (2). Цикл обращений к блоку 11 памяти для чтения и записи операндов при однократном . выполнении операций (3) и (4) (при фиксированном значении R, S) регламентируется 2-разрядным счетчиком 9 и состочт из четырех тактов. Окончание каждого цикла соответствует состоянию "11" счетчика 9 и индицируется выходным сигналом элемента И 8, стробируемым тактовым импульсом. Значение S хранится в регистре 1 сдвига.
Перед началом вычислений в регистр 1 заносится 2, что соответствует зна(чению S npu j = О.
Сигнал "1" на выходе п-го разряда регистра 1 сдвига указывает на начало работы генератора. В регистре 5 формируется значение RS, а на комбинационном сумматоре 4 — сумма RS+S содержимого регистров 1 и 5. Регистр
5 перед началом вычислений обнуляется, что соответствует начальному условию R = О. Совместно с комбинационным сумматором 4 регистр 5 функцио-З нирует как накапливающий сумматор с входом операнда S от регистра 1 сдвига. Схемой 7 сравнения вырабатывается сигнал окончания шага преобразований для перехода от j к j+1 по условию 4о
RS+S = 2 (адрес достигает наибольшего значения). Значение 2 постоянно хранится в регистре 6. Появление сигнала на выходе схемы 7 сравнения син- . хронизируется выходным импульсом эле-,5 мента И 8 и обуславливает сдвиг в сторону младших разрядов в регистре
1 сдвига (т,е. уменьшает S вдвое) и обнуление регистра 5 (R = 0).
На комбинационном сумматоре 2 фор-50 мируется сумма RS+S/2, причем слагаемое S/2 получается благодаря подключению выхода регистра 1 сдвига к входу сумматора 2 со сдвигом в сторону младших разрядов. При выполнении опе-55 раций (3) и (4) операнды К
К,, извлеченные из блока 11 памятй, хранятся в регистрах 17 и 15 соОперанд
Такт Состояние Режим счетчика 9 блока
11 паАдрес
1 яти (()
Чтение RS К
Йз
01
КЯ+Б К (J 41)
RS Кя (J i()
R S+S / 2 К
Запись
Источниками адресов являются регистр .5 и сумматоры 2 и 4, подключаемые к адресному входу блока 11 памяти через коммутатор 3 в зависимости от состояния счетчика 9. В 1-м и 2-м тактах ("О" в старшем разряде счетчика 9) тактовые импульсы проходят через элемент И 14 на управляющие входы регистров 15 и 17, разрешая прием операндов. При этом операнд
Кд проходит в регистр 17 (2-й такт через регистр 15 (1-и тахт). В режиме "Запись" ("1" в старшем разряде счетчика 9 — 3-й и 4-й такты) блок 11 памяти управляется тактовыми импуль:ми, проходящими через элемент И 12, Отбор результатов операций (3) и (4) с выходов сумматора 16 и блока 18 элементов И для записи в бла . 11 паответственно! На последовательных выходах регистров 19 и 20 сдвига, в которые перед началом вычислений заносятся значения р, 1, присутствуют сдвинутые разряды р., 1 . Сдвиги в
J J регистрах 19 и 20 синхронизируются сигналами окончания выполнения шагов от схемы 7 сравнения. Результат операции (3) формируется на сумматоре
16, причем знаки (f,,р ) слагаемых ь задаются с его управляющих входов.
Результат операции (4) формируется на выходе блока 18 элементов И по управляющему признаку „+ р., вырабатываемому сумматором 21 по модулю два. При этом умножение на два обеспечивается благодаря подключению выхода блока 18 элементов И к входу коммутатора 13 со сдвигом в сторону старших разрядов.
Четырехтактный цикл выполнения операций (3) и (4) имеет структуру, приведенную в таблице.
12624
% мяти (3-й и ч-й такты) осуществляется коммутатором 13, который управляется младшим разрядом счетчика 9.
На шаге с номером и-1 результаты (5) вь|числений могут быть последовательно считаны с выхода 10 генераторра. Признаком работы íà (n-1) шаге является сигнал "i" на выходе первого разряда регистра 1 сдвига (S = 2 ).
Для перехода к системе функций 1О
Уолша-Качмажа достаточно записать разряды двоичных кодов р, е в регистрах 19 и 20 в обратной последовательности, Переход к системе функций Уолша- 15
Адамара требует преобразования двоичных кодов р, 1 в коды Грея по правилу р. р + Р+, f.— f„+ f и может быть реализован, например, при помощи двух дополнительных сумматоров по модулю два, подключенных к выходам нулевого и первого разрядов соответствующего регистра 19 и 20, 25
Формула изобретения ответственно к выходам первого сумматора и второго регистра, выход схеГенератор функций Уолша, содержа. щий первый регистр сдвига, счетчик, два коммутатора, первый и второй элементы И, причем счетный вход счетчика и первый вход первого элемента И подключены к тактовому входу генератора, выходы нулевого и первого млад-З ших разрядов счетчика подключены соответственно ко второму и третьему входам первого элемента И, о т л и— ч а ю шийся тем, что, с целью повышения его быстродействия, он со- go держит второй и третий регистры сдвига, четыре регистра, блок памяти, два сумматора, сумматор-вычитатель, сумматор по модулю два, схему сравнения, блок элементов И, третий элемент И, причем разрядный выход первого регистра сдвига подключен к первому входу первого сумматора и со сдвигом на один разряд в сторону младших разрядов к первому входу второго сумматора, выход первого сумматора подключен к информационному входу первого регистра, выход которого подключен к вторым входам первого и второго сумматопервый и ВТороА информационные входы схемы сравнения подключены сомы сравнения подключен к управляющим входам сдвига всех регистров сдвига и к входу установки в "0",первого регистра, стробирующий вход схемы сравнения и управляющий вход записи первого регистра подключены к выходу первого элемента И, выходы первого и второго сумматоров, а также выход первого регистра подключены соответственно к первому, второму и третьему информационным входам первого коммутатора, первый и второй управляющие входы первого коммутатора подключены соответственно к выходам нулевого и первого разряда счетчика, выход первого коммутатора подключен к адресному входу блока памяти, выход блокапамяти подключен к информационному входу третьего регистра, выход третьего регистра подключен к информационному входу четвертого регистра и к входу первoro операнда сумматоравычитателя, выход четвертого регистра подключен к входу второго операнда сумматора-вычитателя и к информационному входу блока элементов И, последовательный выход второго регистра сдвига подключен к входу знакового разряда первого операнда сумматоравычитателя и к первому входу сумматора по модулю два, последовательный выход третьего регистра сдвига подключен к входу знакового разряда второго операнда сумматора-вычитателя и к второму входу сумматора по модулю два, инверсный выход которого подключен к управляющему входу блока элементов И,. выход сумматора-вычитателя подключен к первому информационному входу второго коммутатора, выход блока элементов И со сдвигом на один разряд в сторону старших разрядов подключен к второму информационному входу вторorо коммутаторà, управляющий вход второго коммутатора подключен к выходу нулевого разряда счетчика, выход второго коммутатора является выходом генератора и подключен к информационному входу блока памяти, выход первого разряда счетчика подключен к первому входу второго элемента И и к инверсному входу третьего элемента И, второй вход второго элемента И и прямой вход третьего элемента И подключены к тактовому входу генератора, выход второго элемента И подключен к управляющему входу записи (считывания блока памяти, 1262470 выход третьего элемента И подключен к управляющим входам записи третьего и четвертого регистров выходы и3
1 го (2 — число отсчетов функции) и первого разрядов первого регистра сдвига являются соответственно выходом начала и окончания вычислений генератора.
Составитель В.Байков
Техред Л.Олейник Корректор Е.Рошко
Редактор Г..Волкова
Заказ 5427/45 . Тираж 67.1 . . Подписное
ВНИИПИ Гасударственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
П роизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
