Устройство ортогонального преобразования по уолшу

 

Союз Советскнк

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

Реслублнк

К АВТОВСКОМУ СВИДЕТЕЛЬСТВУ (6l ) Дололнительное к авт. сеид-ву и 620974.(22)Заявлено 24. 06.80 (21) 2944133/18-24 с нрисоединениен заявки М (23)приоритетG 06 F 5/00

G 06 F 15/332

11теударстевнный камнтет

СССР до делам изобретений и еткрнтк»

Опубликовано 23.04 ° 82. Бюллетень М 15 (53) УДК681. 3 (088.8) Дата опубликования описания 23.04.82 (72) Авторы изобретения

А.А.Докучаев, В.А.Зенцов, С.Ф.Свиньин и

Ленинградский ордена Ленина электротехн институт им.В.И.Ульянова (Ленина) (71) Заявитель (54) УСТРОЙСТВО ОРТОГОНАЛЬНОГО ПРЕОБРАЗОВАНИЯ

ПО УОЛШУ

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

По основному авт.св, Ф 620974 известно устройство ортогональногопреобразованив по Уолшу, содержащее сумматоры-вычитатели и регистры сдвига, причем первый и второй входы

1-го (i=1,2 . ° ) сумматора-вычитателя подключены соответственно к выходу и входу t-го регистра сдвига, вход первого регистра сдвига является информационным входом устройства, выход суммы каждого из сумматороввь!читателей, имеющих номера с 2 по

2 -1 (и=1 2 . ° °, N-1, 2. - число коэффициентов преобразования), подключен к входу соот вет ст вующе го ре ги стра сдвига из группы регистров сдвига, и n-e имеющих номера с 2 по 3-2 -1, а выход разности - к входу соответст" вующего регистра сдвига из группы регистров сдвига, имеющих номера с

3 ° 2" " по 2" "1, .выходы суммы и тн1 выходы разности сумматоров-вычитате5 и- и 1 лей, имеющих номера с 2" по 2 представляют собой 2" информационных выходов устройства 712.

Недостатком известного устройства

10 являются ограниченные функциональные возможности, поскол ьку оно позволяет осуществлять преобразование только по функциям Уолша.

Цель изобретения - расширение

15, функциональных возможностей устройства ортогонального преобразования по Уолшу за счет преобразования по интегральным функциям Уолша.

Поставленная цель достигается

20 тем что устройство ортогонального преобразования по Уолшу содержит до. полнительный регистр сдвига и вычитатель, причем первый и второй входы вычитателя подключены соответстУ = -{9(х„. „)-9(х ))=2 (9(х„>1)-9(х))

Ю

Применим к полученным отсчетам у„. преобразование Уолша, которое обычно задается с помощью пары формул к

kg=2, г, у. W (x ° „)= Я(9 (х ° ).-g (x ) )

Я (3) WZ (x;), K. у„= Eс1р„(х.) ..

cl0

3 92272 венно к входу и выходу дополнитель ного регистра сдвига, выход вычитателя подключен к входу первого регистра сдвиra, вход дополнительного регистра сдвига является дополнительным информационным входом устройства.

На фиг.1 представлена функциональная схема устройства ортогонального преобразования по Уолшу; на фиг.2 - системы функций Уолша.

Устройство содержит регистр I сдвига, сумматоры-вычитатели 2, вычитатель 3, первый 4 и второй 5 информационные входы устройства.

8 предлагаемом устройстве производится ортогональное преобразование

Уолша-Адамара над первыми разностями значений цифрового сигнала. Полученные таким образом коэффициенты разложения исходного цифрового сигнала являются спектральными коэффи циентами в базисе кусочно-линейных функций (интегральных функций Уолша)

Рассмотрим систему кусочно-линейных треугольных Функций Мс (х), полученных интегрированием функций Уолша

И,1 хМoo(x) (1)

М (х)= $ W<(t)4t, Мс (х0)=О,х е 0;1).

Несколько первых функций Wg(x) и

Мс (х ) приведены на фиг. 2. В принятых обозначениях и - наивысший порядок данного семейства Функций, +=0, 1,...

k, М=2Й-1.

Функции, определенные в (1),обра-. 3> зуют полную систему линейно-независимых функций. в пространстве С(0; Ц непрерывных функций и являются в этом пространстве базисом.

Рассмотрим непрерывную на f0;1) функцию g(t), которая не имеет постоянную составляющую 9 (О) =О. Вычислим для этой функции-первые правые разности на множестве равноотстоящих значений аргумента x.=ih:

1=0 в 1е ° ° М h=2; g (x0)=01 (2) 4

Рассмотрим выражение для конечной суммы Ьк(х), образованной из произве. дений коэффициента ag преобразова- . ния Уолша (3) и кусочно-линейных функций

К

S„(x)= Р се, Мс (х) . сЬ-0

Для некоторой точки х на основа"

Ф ни и определения (1 ) и свой ст ва равномерной сходимости ряда Уолша имеем к " : . dl к

S„(x,.)= Z a<$WZ(t)at=) g, W<

cLX,0 0 АГРО

"(") = . QÊ(")с " где Я (tf является частичной суммой ряда Уолша.

Разобъем интервал интегрирования (О; .y,.) на 1 равных частей. На каждом таком интервале (x, х. „1, где

j=0,1,...,i-1, значение частичной суммы Уолша Q (t) является постоянj ным числом, равным у . Поэтому х.

;-1 J ê 1-1 Х5Ф1

S„(>.,)= Z, ) g a<, (е)й = Z ) у

3=0 К ° 0 J=0 y.

1-1 . 51

4 хс)йЬ 2, y =h-(g(x.) -g(x )+ g(x. „)g(xg) -g(х )+9(х )=9(x) ) °

Таким образом, конечйая сумма

S„(x) ряда по функциям (l)a произвольной узловой точке х. совпадает

i со значением исходной функции g (x) в этой точке. Другими словами,частичная сумма интерполирует исходную функцию 9 (х) на системе равноотстоящих .двоично- рациональных узлов.

Следовательно, для. получения коэффициентов интерполяционного при-. ближения заданной функции g (x) в Gaзисе функций (1) на системе точек.

Х„=i -h, п=2, i=-- 0,1,...,k достаточно произвести ортогональное преобразование Уолша над правыми первыми разностями исходной функции у. =g(x ) -9(х„) .

Заметим, что для получения интерполяционного приближения произвольной функции Ф (х)6С при r (0)P О необходимо наряду с 2" коэффициентами, получаемыми применением преобразования Уолша, вычислить коэффициент а0с=У(0) при "внесистемной" функции

М 00(x)=-1, так как операция (2) вычисления разностей автоматически исключает постоянную составляющую функции.

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

2721 6 узлов с помощью частичной суммы Уолша g„(x) при К=2 -1 равна

E<=max)f (х) -0.„(х) <; 2 max) f (х) t, 2 х e(0;11 X6j0 1) а погрешность кусочно-линейной интерполяции при тех же условиях с помощью частичной суммы кусочно-линейных функций S (х) равна

Е„= пах1Г(x)-S<(x)! < - 2 . maxI f" (x)j .

xeТ0р1) хф;1)

Таким образом, выигрыш в точности, получаемой при использовании аппрок15 симации ку сочно-линейными функциями, оценивается выражением

Em „2й axtf х )

Е" max Р х 1;

К

20 За счет незначительного количественного усложнения схемы известного устройства без нарушения ее однородности (вместо 2 - 1 регистров сдвига

И и стольких же сумматоров-вычитателей

25 в предлагаЕмом устройстве используются 2 регистров сдвига и столько же сумматоров- вычитателей) удалось . расширить область применения предлагаемого. устройства. Этому расширению

З0 сопутствует либо увеличение точности представления анализируемого сигнала, либо при фиксированной точностиувеличение быстродействия за счет применения предлагаемого изобретения.

5 92

Значения f (x ), f (x„),..., f (x < )цифрового сигнала последовательно с заданной частотой поступают на вход

4 устройства. В дополнительном регистре сдвига сигнал т(х0), поступивший в первом такте, задерживается на один такт. На входы вычитателя 3 во втором такте поступают значения f (xo) и 1(х„), а на его выходе формируется значение у0=1(х,) -f (xp) . 8 третьем такте на выходе вычитателя 3 появляется значение у„=1(х )-f(x„), в четвертом такте - значение у = f (x g -f x (х ), и так далее. Таким образом, начйная с второго такта, на вход регистра сдвига с порядковым номером один последовательно поступают значеyO t y y yfl 4 ° ° ° y Y,.

Дальнейшая обработка этих значений - ортогональное преобразование

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

В регистре 1 первого яруса (п=1) сигнал у, поступивший во втором

0 такте, задерживается на один такт, и на входы сумматора-вычитателя 2 первого яруса поступают значения у и у„, а на его выходе формируются зйачения уо+у и уо .у

В четвертом такте на выходах сумматора-вычитателя 2 первого яруса появляются значения у +у и у„-у, в пятом такте - у +у и у -у>, и так

1далее. Аналогично работают блоки в ! последующих ярусах с той лишь разницей, что каждый регистр сдвига и--го яруса задерживает поступивший на его вход цифровой код на 2" " тактов., 35 формула изобретения

В результате через 2"+I тактов после поступления на вход устройства первого отсчета f (x0) на параллельных выходах устройства сформируются 2" коэффициентов преобразования в базисе И функций. Девятым коэффициентом преобразования, как указывалось, является а =1(0) .

Если поступающйе отсчеты цифрового сигнала подавать не на вход 4, а на. вход 5, то .в этом случае на вы" ходах у стройст ва вычи сляют ся 2 коК эффициентов ортогонального преобразования Уолша.

55 можно показать, что погрешность кусочно-постоянной интерполяций произ вол ьной т (х) е С (О; 11 на множестве ра вноот стоящих двои чно- рационал ьных

Устройство ортогонального преобразования по Уолшу по .авт.св.

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

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

1. Авторское свидетельство СССР и 620974, кл. G 06 F 5/00, 1976 (про- тотип) °