Устройство для вычисления коэффициентов обобщенных функций Хаара Советский патент 1982 года по МПК G06F17/14 

1

Изобретение относится к цифровой вычислительной технике и может быть использовано в составе автоматизированного комплекса обработки данных экспериментальных исследований.

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

Недостатком этого устройства является низкое быстродействие.

Из известных устройств наиболее: ,5 близким к предлагаемому по технической сущности является устройство для вычисления коэффициентов ФурьеХаара, содержащее преобразователь аналог-цифра, (2 + 1) последователь-го но соединенных регистров сдвига, первый из которых соединен информационным входом с выходом преобразователя, а управляющие входы каждого регистра

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

Недостатком подобного устройства является то, что оно позволяет вычислять коэффициенты Хаара с интервалом задания аргумента о, 2, где m - произвольное число.

Цель изобретения - расширение функциональных возможностей, а имен но вычисление коэффициента обобщенных функций Хаара с интервалом задания аргумента to, Р, где Р - простое елое число. .

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

блоки памятиj арифметический блок, два элемента И, элемент задержки, адресный счетчик и блок формирования ядра обобщенных функций Хаара, содержащий счетчик весовых коэффициентов, узел умножения, узел преобразования двоичного кода в код по модулю Р, узел памяти, причем выход счетчика весовых коэффициентов подключен к первому входу узла умножения, выход которого соединен с первым входом узла преобразования двоичного кода в код по модулю Р выход которого подключен ко входу узла памяти, выход которого соединен с первым входом арифметического блока, выход которого подключен к первому входу основного блока памяти, выход которого объединен с выходом дополнительного блока памяти и соединен со вторым входом арифметического блока и первым входом дополнительного блока памяти, второй вход которого объединен со вторым входом узла умножения блока формирования ядра обобщенных функций Хаара и подключен к первому выходу адресного счетчика, первый вход которых объединен с третьим входом дополнительного блока памяти и первого элемента И и является тактовым входом устройства, второй выход адресного счетчика объединен с выходом второго элемента И и подключен ко второму входу основного блока памяти, входу элемента задержки и первому входу счетчика весовых коэффициентов блока формирования ядра обобщенных функций Хаара, причем блок управления, содержащий счетчик по модулю Р, триггер, счетчик по модулю S, узел деления, узел возведения в степень, три узла умножения и сумматор, при этом первый вход счетчика по модулю Р объединен с первым входом второго элемента .И и соединен с выходом элемента задержки и выходом первого элемента И, первый вход счетчика по модулю Р подключен ко входу триггера, инверсный выход которого соединен с третьим входом основного блока памяти и первым входом счетчика по модулю S, первый выход которого подключен к первому входу узла делен я и первому входу узла возведения в степень, выход которого подключен к первому входу первого узла умножения, второму входу узла деления и

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

соединен со вторым входом сумматора, второй выход счетчика по модулю S соединен со вторым входом третьего узла умножения, выход узла деления соединен со вторым входом счетчика

по модулю S, прямой выход триггера подключен ко вторым входам первого и второго элементов И и четвертому входу дополнительного блока памяти, при этом второй вход счетчикапо модулю Р, второй вход узла возведения в степень, .второй вход второго узла умножения блока управления, второй вход счетчика весовых коэффициентов второй вход узла преобразования двоичного кода в код по модулю Р блока формирования ядра обобщенных функций Хаара и второй вход адресного счетчика образуют группу входов устройства, а третий вход узла деления

блока управления является входом устройства.

На фиг. 1 представлена блок-схема устройства; на фиг. 2 - быстрая итерационная процедура вычисления коэффициентов обобщенных функций Хаара для на фиг. 3 - графсхема .

Устройство содержит блок 1 управления, основной блок 2 памяти, дополнительный блок 3 памяти, арифметический блок k, первый и второй элементы И 5 и 6, элемент 7 задержки, адресный счетчик 8, блок 9 формирования ядра обобщенных функций Хаара,

информационный : выход 10 блока управления, выход 11 основного блока 2 памяти, выход 12 блока , второй вход 13 узла умножения блока 9, выход Т узла блока памяти 9 выхода

15 блока I, первый вход 1б счетчика весовых коэффициентов блока 9, второй вход 17 элемента И 6, третий вход 18 блока 2, выход 19 элемента И 5, тактовый вход 20 устройства,

счетчик 21 по модулю Р, триггер 22, счетчик по модулю S 23, узел 2 умножения (на модуль Q), узел 25 умножения (на модуль R), сумматор 26, узел 27 деления (узел вычисления модуля S), узел 28 возведения в степень (узел вычисления модуля 0.), узел 29 умножения (на модуль Р), группа входов 30 устройства (в двоичном коде подается модуль Р), вход 31 устройства (значение модуля , счетчик 32 весовых коэффициентов, узел 33 умножения, узел З преобразования двоичного кода в код по модулю Р, узел 35 памяти, узел Зб умножения комплексных чисел, сумматор 37 комплексных чисел. Обобщенные функции Хаара, определяемые с помощью обобщенных функций Радемахера X(r,t) на интервале (О, Р) записываются как H(0,t) 1 .x..., 1 Cr/n в lti-r+1 и/яс-ь t(.B-i)p ,ер в остальных случаях, l---e,vitUO pK Hi е-1,2,...,Р Ы.,..., 1.Р°- аР-- е-у„Р Л 9 42036 сто ке где нос мат б существляя в (1) перестановку бцов в обратном троичном порядолучаем1 - единичная матрица размерью 3x3, dtagV/ - диагональная ица той же размерности, Представляя ( в (3), получим быструю итерационную процедуру вычисления коэффициентов обобщенного преобразования Хаара, которая поясняется фиг. 2. Граф-схема вычисления коэффициентов обобщенного преобразо вания Хаара приведена на фиг. 3. Устройство работает следующим об разом. Предварительно задаются все начал ные условия, а именно: на входы 30 всех устройств, выполняющих операции по модулю Р, подается в двоичном коде значение модуля Р; через информационный вход в узел 35 блока 9 формирования ядра обобщенных функций Хаара заносятся все значения йамплитуд, представленные в двоичном коде которые могут принимать обобщенные функции Хаара при данном Р, причем номера ячеек узла 35 памяти совпадают с номерами занесенных в них значений амплитуд fдля Р 3 в ячейку с адресом 00 - W, в ячейку с адресом 01 - W, в ячейку с адресом 10 - W2). На вход 31 подается значение модуля L . В основной блок 2 памяти заносятся ординаты реализации исследуемого процесса, причем адреса ячеек совпадают с номерами занесенных в них ординат реализации. Для пояснения работы устройства рассмотрим случай, когда Р 3--и m 2. Граф-схема для этого случая приведена на фиг. 3. В исходном состоянии все счетчики устройства установлены в нуль. Тактовые импульсы со входа 20 поступают через первый элемент И 5 на выход 19 счетчика 21 по модулю Р блока 1 управления. При этом на входе 18 выбора операции основного блока 2 пакяти присутствует логическая единица, что соответствует операции Чтение, а на выходе выбора опера9 420368

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

функций Хаара модуль Q Р 3° 1/

рУЧ--) Q

модуль S J 9, модуль R , QxP 1-3 3. При поступлении первых Prl тактовь1х х импульсов на информационном выходе счетчика 21 по модулю Р формируется цифровая последовательность вида 00, 01, 10, которая подается на один из входов узла 2k умножения на модуль Q, на второй вход которой в этот момент с выхода узла 28 подается.в двоичном коде значения модуля Q 01. Тогда в результате перемножения этих значений на выходе 10 блока управления формируется цифровая последовательность вида00, 01, 10 и происходит выборка значений ординат реализации из 0-й, 1-й и 2-й ячеек основного блока памяти, которые последовательно перемножаются в узле Зб умножения комплексных чисел с нулевой строкой ядра обобщенных функций Хаара, значения которой выбаратывает блок 9 формирования ядра обобщенных функций Хаара, и результаты перемножения суммируются в сумматоре 37. В это же время значения ординат О,и, 1-й и 2-й ячеек основного блока 2 памяти записываются соответственно в 0,1 и 2-ю ячейки памяти дополнительного блока 3 памяти, адреса выборки KOJOрых вырабатывает счетчик 8 адреса.Следующий Р-ый импульс устанавливает счетчик 21 по модулюР в ноль,а сигнал переполнения с его хода перебрасывает триггер 22 в противоположное состояние, в результате чего на выходе выбора операции основного блока 2 памяти устанавливается уровень записи, а на входе выбора операции дополнительного блока 3 памяти устанавливается уровень чтения. В этот момент времени на выходе 10 блока 1 управления сформирован адрес выборки 00 и по сигналу выборки, который поступает на вход разрешения выборки основного блока 2памяти, происходит запись результатов перемножения и суммирования в ячейку с адресом 00, а из ячейки с адресом 00 дополнительного блока 3памяти происходит считывание ординаты Xjj. При поступлении следующих Р-1 тактовых импульсов счетчик 8 адреса вырабатывает адреса 01 и 10 и происходит операция чтения ординат Х и /2 из 1-й и 2-й ячеек дополнительного блока 3 памяти. Одновременн происходит перемножение этих ординат (Хр, Х , Х)с 1-й строкой ядра обобщенных- функций Хаара, которую сформировал блок 9 формирования ядра, так как импульс переполнения с выход счетчика 8 адреса записал в счетчик 32 весовых коэффициентов единицу. При этом тактовые импульсы со входа 20. на выход 19 счетчика 21 по модулю Р не проходят, так как на втором входе схемы совпадения присутствует высокий уровень, сформированный триг гером 22, который дает запрет на про хождение импульсов. При поступлении следующего тактового импульса на вход 20 устройства счетчик 8 адреса устанавливается в ноль и сигнал переполнения с его выхода поступает на счетный вход счетчика 21 по модулю Р и записывает в него единицу и одно временно этот сигнал, поступающий на вход разрешения выборки основного блока 2 памяти, записывает результат перемножения ординат Х, Х, Х на 1-ю строку ядра обобщенных функций Хаара и суммирования в 1-ю ячейку основного блока 2 памяти. Аналогично происходит перемножение ординат Х, X., Х на 2-ю.строку ядра обобщенных функций Хаара, их суммирование и запись во вторую ячейку ос новного блока 2 памяти. При этом импульс переполнения с выхода счетчика 8 адреса поступает на вход счет чика 21 по модулю Р, в котором ранее было записано двоичное число 10 и устанавливает его в, нулевое состояние. Импульс переполнения счетчика 21 по модулю Р, в свою очередь перебрасывает триггер 22 в противоположное состояние и записывает в счетчик по модулю S единицу, в результате чего аналогичным образом происходит перемножение ординат X Х,- на ядро обобщенных функций Хаара, суммирование их и занесение результатов вычислений соответствен но в 3-ю, 4-ю и 5-ю ячейки основного блока 2 памяти. Аналогично производятся операции и для ординат Xg, Х Хд, после чего оканчивается первый шаг преобразования, по окончании которого счетчик 23 по модулю S вырабатывает сигнал переполнения, который поступает на узел 27 и на . 610 вход узла 28, в результате чего мо0. Р, о становится равным с- S-Q- 3 31 модуль При этом модуль R QP ЗЗ 9. Последующая работа вычислителя на 2-м шаге преобразования происходит аналогичным образом. Предлагаемое устройство позволяет значительно повысить быстродействие вычисления коэффициентов обобщенных функций Хаара. При р « 3 и m 5 выигрыш в быстродействии соста) Формула изобретения Устройство для вычисления коэффициентов обобщенных функций Хаара, содержащее блок управления, отличающееся тем, что, с целью расширения функциональных возможностей за счет вычисления обобщен ных функций Хаара с интервалом задания аргумента (О, Р) , где Р - простое число, в него введены основной и дополнительный блоки памяти, арифметический блок, два элемента И, элемент задержки, адресный счетчик и блок формирования- ядра обобщенных функций Хаара, содержащий счетчик весовых коэффициентов, узел умножения, узел преобразования двоичного кода и код по модулю Р, узел памяти, причем выход счетчика весовых коэффициентов подключен к первому входу узла умножения, выход которого соединен с первым входом узла преобразозания двоичного кода в . код по модулю Р, выход которого подключен к входу узла памяти, выход которого соединен с первым входом арифметического блока, выход которого подключен к первому входу основного блока памяти, выход которого объединен с выходом дополнительного блока памяти и соединен с вторым входом арифметического блока и первым входом дополнительного блока Пс1мяти, второй вход которого объединен с вторым входом узла умножения блока формирования-ядра обобщенных функций Хаара и подключен к первому выходу адресного счетчика, первый вход которых объединен с третьим входом дополнительного блока памяти и первого элемента И и является тактовым входом устройства, второй вход адресного счетчика объединен с выходом второго элемента И и подключен к второму входу основного блока памяти, входу элемента задержки и первому входу счетчика весовых коэффициентов блока формирования ядра обобщенных функций Хаара, приче блок управления, содержащий счетчик по модулю Р, триггер, счетчик по модулю S, узел деления, узел возведения в степень, три узла умножения и сумматор, при этом первый вход счетчика по модулю Р объединен с первым входом второго элемента И и соединен с выходом элемента задержки и выходом первого элемента И первый выход счетчика по модулю Р подключен к входу триггера, инверсный выход которого соединен с третьи входом основного блока памяти и первым входом счетчика по модулю S, пер вый выход которого подключен к первому входу узла деления и первому входу узла возведения в степень, выход которого подключен к первому входу первого узла умножения, втором входу узла деления и первому входу второго узла умножения, выход которо го соединен с первым входом третьего узла умножения, выход которого подключен к первому входу cy 4 aтopa выход которого соединен с четвертым входом основного блока памяти, вто6 рой выход счетчика по модулю Р соединен с вторым входом первого узлэ умножения, выход которого соединен с вторым входом сумматора, второй выход счетчика по модулю S соединен с вторым входом третьего узла умножения , выход узла деления соединен с вторым входом счетчика по модулю S, прямой выход триггера подключен к вторым входам первого .и второго элементов И и четвертому входу дополнительного блока памяти, при этом второй вход счетчика по модулю Р, второй вход узла возведения в степень, второй вход второго узла умножения блока управления, второй вход счетчика весовых коэффициентов, второй вход узла преобразования двоичного кода в код по модулю Р. блока формирования ядра обобщенных функций Хаара и второй вход адресного счетчика образуют группу входов устройства, а третий вход узла деления блока управления является входом устройства. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР tf I 8k523, кл. G Об F 15/34, 1975. 2.Авторское свидетельство СССР № 579623, кл. G Об F 15/3, 1977 (прототип).

,/

We X, Xi)/)f5 ,)()(t Л, Jf,J (, Гг){(ДГ, ,,/Jf, Xr Xt} ,

(X,X,}(f)- Wt{Xj X)(W,) ,

., ,Xt ,W,Xt , I шаг

M,

MI

H, Нз Siuatw

M,M, H, Mf

Фиг:2