Устройство для вычисления коэффициентов обобщенных функций хаара

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Сомз Советских

Социалистических

Респубпии ()942036 (6l ) Дополнительное к авт. саид-ву— (22) Заявлено 28. 03. 79 (21) 2742162/18-24 (5l)M. Кл.

С 06 F 15/332 с присоединением заявки №вЂ”

РкУаарвтиллы11 комитет

СССР ло делам иэабрвтвник н открытки (23) П рнорнтет

Опубликовано 07. 07. 82. Бюллетень № 25

Дата опубликования описания 07.07.82 (53) УДК 681 14 (088.8) (72) Авторы изобретения

П.М. Чеголин, Н.В. Нечаев, P.Х. Садыхов и В.Х,. Кончак

} !

» ) » »; - » Д ор усск6и С бР ": Ji 4 g ; :;.,;

Институт технической кибернетики АН Бе (71) Заявитель (54 ) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ

ОБОБЩЕННЫХ ФУНКЦИЙ ХААРА

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

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

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

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

neöâîãî и последнего регистров сдвига t2).

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

m - произвольное число.

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

"елое число.

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

Хаара, содержащее блок управления, введены основной и дополнительный

3 9420 блоки памяти; арифметический блок, два элемента И, элемент задержки, адресный счетчик и блок формирования ядра обобщенных функций Хаара, содержащий счетчик весовых коэффи- З циентов, узел умножения, узел преобразования двоичного кода в код по модулю Р, узел памяти, причем выход счетчика весовых коэффициентов подключен к первому входу узла умножения, выход которого соединен с первым входом узла преобразования двоичного кода в код по модулю Р,, выход которого подключен ко входу узла памяти, выход которого со15 единен с первым входом арифметическо го блока, выход которого подключен к первому входу основного блока памяти, выход которого объединен с выходом дополнительного блока памяти и соединен со вторым входом арифметического блока и первым входом дополнительного блока памяти, второй вход которого объединен со вторым входом узла умножения блока формирования ядра обобщенных функций Хаара и подключен к первому выходу адресного счетчика, первый вход которых объединен с третьим входом дополнительного блока памяти и первого элемента И и является тактовым входом устройства, второй выход адресного счетчика объединен с выходом второго элемента И и подключен ко второму входу основного блока памяти, входу 3s элемента задержки и первому входу счетчика весовых коэффициентов блока формирования ядра обобщенных функций

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

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

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

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

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

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

И 5, тактовый вход 20 устройства, счетчик 21 по модулю Р, триггер 22, счетчик по модулю S 23, узел 24 умножения (на модуль Q) узел 25 умножения (на модуль R), сумматор 26, 942036 6

Осуществляя в (1) перестановку столбцов в обратном троичном поряд« ке получаем

5 узел 27 деления (узел вычисления модуля S), узел 28 возведения в степень (узел вычисления модуля О), узел 29 умножения (на модуль Р), группа входов 30 устройства (в двоичном коде подается модуль P), вход

31 устройства (значение модуля 1 =Р""л), Чо Чо Чо Чр о л " "р о 2. Чл Чо

Чо О О Ч4 О б о о ч, о о

Чо О 0 Ч2 0

0 O Ч

o o. ч, счетчик 32 весовых коэффициентов, узел 33 умножения, узел 34 преобразования двоичного кода в код по модулю Р, узел 35 памяти, узел 3б умножения комплексных чисел, сумматор

37 комплексных чисел.

Обобщенные функции Хаара, определяемые с помощью обобщенных функций

Радемахера X(r,t) на интервале (О, Р"") записываются как Н(о,т) 1

Н(о,t) 1

f/ е

Сх(1 1) 3

26 (ф) О в-г 1 м-г+л

Н = н.

diag W

dia gW

IH

dia ч

diag Ч

25.где 1 - единичная матрица размерностью 3 х 3, diagW - диагональная . матрица той же размерности, %=19., р" t=RP e р-- Rp""

k - номер обобщенной функции Хаара;Зв

6 весовые коэффициенты;

3)1

ent - целая часть.

Матрица обобщенного преобразования

Хаара размерностью 9 х 9 при Р = 3, m = 2 имеет вид 35

О 1 2 3 4 5 6 7 8 о р

Чо чл W2.

Чо Чд. Ч, - ядро обобщенных дискретных функций.

Коэффициенты М обобщенного преобразования Хаара входной последователь" ности х определяются иэ соотношения

М=Нх (3) Wo Wo Чр Чо о Чo

Wo Чo о

W, W. .Чл Ч2. Чач

Как видно иэ (2), матрицу можно факторизовать, т.е. представить в виде произведения двух слабозаполненных матриц

Чо Чо о л

Чр Wo o

0 О О О О О

Wî л я

Чр О

w o o

О

W„О0 Ч, Ч„ О О

О О Ч„ 0

Ч2 00 Ч4

0 WО 1

0 О Ч

О .О

W Ч О О О

Ч0

0 Wo

О О

Wg. Чл

О О

w ч w

Ч 0

О Ч1

О О

О О О

Н = о 2.

О О 0 о о о о о о ч ч ч

Причем каждый элемент Ч, матрицы Н определяется соотношением (2R j

%<=Exp(е g), тле 1 =-д, w„о

О Ч в остальных случаях, =Ь+т.ЕОР)+, Е,а,.-, P

О О 0 О О О Ч

Ч О О

0 Ч О

О

Ч О О

О Ч О о о ч, Ч О О

О W О

О О

Чо Чо ЧФр W

Ч1. 1

0 w 00 о о чо

Ч1 О О Ч2 о ч„о,о

О О W 0

Ч О ОЧ„

9420 о

W W W о !

Ы W W О О !

WÎ W2. М l

Г

0 Ч !

О

W (! И

О О !

I Ч

Представляя (4) в (3Р, получим быструю итерационную процедуру вычисления коэффициентов обобщенногопреобразования Хаара, которая поясняется фиг. 2. Граф-схема вычисления коэффициентов обобщенного преобразования Хаара приведена на фиг. 3.

Устройство работает следующим образом.

Предварительно задаются все начальные условия, а именно: на входы 30 всех устройств, выполняющих операции

rio модулю Р, подается в двоичном коде значение модуля Р; через информационный вход в узел 35 блока 9 формирования ядра обобщенных функций

Хаара заносятся все значения 5амплитуд, представленные в двоичном коде, которые могут принимать обобщенные функции Хаара при данном Р, причем номера ячеек узла 35 памяти совпадают с номерами занесенных в них значений амплитуд (для Р = 3 в ячейку с адресом 00 - 14, в ячейку с адресом 01 — И, в ячейку с адресом t 0 — Wg) . На вход 31 подается значение модуля (= 2в - . В основной блок 2 памяти заносятся ординаты реализации исследуемого процесса, причем адреса ячеек совпадают с номерами занесенных в них ординат реализации. Для пояснения работы устройства рассмотрим случай, когда P = 3-и

m = 2. Граф-схема для этого случая приведена на фиг. 3.

В исходном состоянии все счетчи50 ки устройства установлены в нуль.

Тактовые импульсы со входа 20 поступают через первый элемент И 5 на выход 19 счетчика 21 по модулю Р блока 1 управления. При этом на входе 18 выбора операции основного бло55 ка 2 памяти присутствует логическая единица, что соответствует операции

"Чтение", а на выходе выбора опера36 8 ции дополнительного блока 3 памяти логический ноль, что соответствует операции "Запись". На первом шаге вычисления коэффициентов обобщенных функций Хаара модуль Q = Р = 3 = 1,:

Р " 9 модуль 9 — = 9 модуль

О 1

R = QxP. = 1. 3 = 3. При поступлении первых P-1 тактовых их импульсов на информационном выходе счетчика 21 по модулю Р формируется цифровая последовательность вида 00, 01, 10, которая подается на один из входов узла 24 умножения на модуль Q, на второй вход которой в этот момент с выхода узла 28 подается .в двоичном коде значения модуля Q = 01. Тогда в результате перемножения этих значений на выходе 10 блока управления формируется цифровая последовательность вида 00, 01, 10 и происходит выборка значений ординат реализации из О-й, 1-й и 2-й ячеек основного блока памяти, которые последовательно перемножаются в узле 36 умножения комплексных чисел с нулевой строкой ядра обобщенных функций Хаара, значения которой выбаратывает блок 9 формирования ядра обобщенных функций

Хаара, и результаты перемножения суммируются в сумматоре 37. В это же время значения ординат О,й, 1-й и

2-й ячеек основного блока 2 памяти записываются соответственно в О,1 и 2-ю ячейки памяти дополнительного блока 3 памяти, адреса выборки которых вырабатывает счетчик 8 адреса.Следующий P-ый импульс устанавливает счетчик 21 по модулю Р в ноль,а сигнал переполнения с его хода перебрасывает триггер 22 в противоположное состояние, в результате чего на выходе выбора операции основного блока 2 памяти устанавливается уровень записи, а на входе выбора операции дополнительного блока 3 памяти устанавливается уровень чтения. В этот момент времени на выходе 10 блока 1 управления сформирован адрес выборки 00 и по сигналу выборки, который поступает на вход разрешения выборки основного блока

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

3 памяти происходит считывание ординаты Х,. При поступлении следующих

Р- 1 тактовых импульсов счетчик 8

Формула изобретения

Устройство для вычисления коэффициентов обобщенных функций Хаара, содержащее блок управления, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет вычисления обобщен ных функций Хаара с интервалом зада ния аргумента (О, P ), где P - npoill стое число, в него введены основной и дополнительный блоки памяти, арифметический блок, два элемента

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

9 94203 адреса вырабатывает адреса 01 и 10 и происходит операция чтения ординат

Х и X из 1-й и 2-й ячеек дополни 2 тельного блока 3 памяти. Одновременно происходит перемножение этих ординат 5 (Х, Х, Х )с 1-й строкой ядра обобщенных функций Хаара, которую сформировал блок 9 формирования ядра, так как импульс переполнения с выхода счетчика 8 адреса записал s счетчик

32 весовых коэффициентов единицу.

При этом тактовые импульсы со входа, 20 на выход 19 счетчика 21 по модулю

P не проходят, так как на втором входе схемы совпадения присутствует высокий уровень, сформированный триггером 22, который дает запрет на прохождение импульсов. При поступлении следующего тактового импульса на вход 20 устройства счетчик 8 адреса 2о устанавливается в ноль и сигнал переполнения с его выхода поступает на счетный вход счетчика 2 1 по модулю

P и записывает в него единицу и одновременно этот сигнал, поступающий на вход разрешения выборки основного блока 2 памяти, записывает результат перемножения ординат Х, Х, Х на 1-ю строку ядра обобщенных функций Хаара и суммирования в 1-ю ячей- зо ку основного блока 2 памяти. Аналогично происходит перемножение ординат Хо, Х, Х на 2-ю стРокУ ядРа обобщенных функций Хаара, их суммирование и запись во вторую ячейку ос- З5 новного блока 2 памяти. При этом импульс переполнения с выхода счетчика 8 адреса поступает на вход счетчика 21 по модулю Р, в котором ранее было записано двоичное число 10 и 4О устанавливает его s. нулевое состояние. Импульс переполнения счетчика 21 по модулю Р, в свою очередь, перебрасывает триггер 22 в противоположное состояние и записывает в счетчик по модулю S единицу, в Результате чего аналогичным образом происходит перемножение ординат Хз, Х Х на ядро обобщенных функций

Хаара, суммирование их и занесение результатов вычислений соответственно в З-ю, 4-ю и 5-ю ячейки основного блока 2 памяти. Аналогично производятся операции и для оРдинат Х, Х7, Х после чего оканчивается первый ь 55 шаг преобразования, по окончании которого счетчик 23 по модулю S вырабатывает сигнал переполнения, который поступает на узел 27 и на .

6 10 вход узла 28, в результате чего мо- дуль 0 становится равным Q = P

Р" 9

= 3" = 3, а модуль

При этом модуль R = Q P = 3 3 = 9.

Последующая работа вычислителя на

2-м шаге преобразования происходит аналогичным образом.

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

m = 5 выигрыш в быстродействии состав вит Р,2(„„) 160

11 9420 вход адресного счетчика объединен с выходом второго элемента И и подключен к второму входу основного блока памяти, входу элемента задержки и первому входу счетчика весовых коэффициентов блока формирования ядра обобщенных функций Хаара, причем блок управления, содержащий счетчик по модулю Р, триггер, счетчик по модулю 5, узел деления, узел возве- 10 дения в степень, три узла умножения и сумматор, при этом первый вход счетчика по модулю Р объединен с первым входом второго элемента И и соединен с выходом элемента за- 15 держки и выходом первого элемента И, первый выход счетчика по модулю P подключен к входу триггера, инверсный выход которого соединен с третьим входом основного блока памяти и пер- 2о вым входом счетчика по модулю S, пер вый выход которого подключен к первому входу узла деления и первому входу узла возведения в степень, выход которого подключен к первому 25 входу первого узла умножения, второму входу узла деления и первому входу второго узла умножения, выход которого соединен с первым входом третьего узла умножения, выход которого зо подключен к первому входу сумматора, выход которого соединен с четвертым входом основного блока памяти, вто-

36 12 рой выход счетчика по модулю P соединен с вторым входом первого узла умножения, выход которого соединен с вторым входом сумматора, второй выход счетчика. по модулю S соединен с вторым входом третьего узла умножения, выход узла деления соединен с вторым входом счетчика по модулю S, прямой выход триггера подключен к вторым входам первого .и второго элементов И и четвертому входу дополнительного блока памяти, при этом второй вход счетчика по модулю

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР и 484523, кл. G 06 F 15/3", 1975.

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

М 579623, кл. G 06 F 15/34, 1977 (прототип).

942036

I urus î х, х, 4 хс

Ku u+ +xi ix х к х к,+х +х х, вх, и х, х в,х,. х, х в,х +и,х х, в,х,вх, хз и гх ю ху хе > wqA к (хю+х хд+Яр+х +ц+ х +х +х (хф ху х )+идху х + хуф+ щ 4 хр хр +ху (х,+х, +х )+,+х +@+и,р,+х,+х

Яаав942036

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

Редактор А. Власенко Техред Т. Маточка

Корректор Г. Огар

Подписное

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

Заказ 4842/40 Тираж 731

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

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