Устройство для преобразования по функциям Хаара Советский патент 1987 года по МПК G06F17/14 

5

10

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

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

На фиг. представлена функциональная схема устройства; на фиг,2 - граф быстрого алгоритма преобразования в базисе интегральных функций Хаара при N -8 (N 2 - размерность преобразования).

Устройство содержит блоки 1 за- 20 держки, сумматоры-вычитатели 2,блоки 3 задержки, коммутатор 4, блок 5 постоянной памяти, счетчик 6, регистр 7 сдвига, вьгчитатель 8. Блоки устрой15

25

Н,

тва сгруппированы в п ярусов. В

Г 1 1 О 1 О о О 1-1 01 О 100 1 1-100010 1--1 0-1 000 1. 1110-1000 1-1 010-100 1 1-1 О О 0-1 О 1-1 0-1 о о 0-1

Оператор для имеет вид

,-t

блоке I задержки i-ro (i 1,...,n) ин4нэрмация задерживается на N/2 тактов, а в блоке 3 задержки - на тактов.

Работа устройства основьгоается на следукяцем положении,

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

X CHI,(1)

где С - вектор-строка коэффициентов;

Н - матрица преобразования Хаара;

I - оператор интегрирования. Тогда процедура вычисления коэффициентов С имеет вид

б ХГ H- XI (2)

0

где Т - транспортирование.

Матрица Н факторизуется, что позволяет построить быструю вычислительную процедуру, которая для N « 8 25 имеет вид

10001000

01000100 00500010 00010001 1000-1000 0100 0-1 о о 001000-10 0001000-1

(4)

313271

Согласно (2) к массиву из N отсчетов сначала применяют оператор I , а затем оператор Н . Результат действия оператора Г может быть представлен в следующем виде:

{x.x/x,Xjii-

Х XQ у Х2 Х у X J X

о «1 QI 3

Воспользовавшись факторизацией (3), для N 4 имеем следующую процедуру вычисления С:

1-й шаг

2-й щаг

(6)

do+d

d,-d,

Отсчеты {Xj поступают на первый вход вычитателя 8 и регистра 7. В регистре 7 отсчеты {Xj задерживаются на I один такт, в результате зтого на выходе вычитателя 8 формируется выражение (5). Далее информация задерживается блоком 1 задержки () на N/2 тактов, в результате чего на вы-

- Адрес I 000 I 001 1 010 011 100 101 110 1И

Код ПЗУ 00

01

10

Таким образом,коммутатор4 подключает к выходу устройства на (N+1)-M. такте выход сумматора-вычитателя 2 третьего яруса, на ()-M такте - выход блока 3 задержки третьего яруса, на (N+3)-M и (N+4)-M тактах - выход блока 3 задержки второго яруса, на (N+5) - (N+8)-x тактах - выход блока 3 задержки первого яруса.

Аналогично работают коммутатор 4, ПЗУ 5 и счетчик 6 для размерности N: по (Ы4-1)-му и (N-«-2)-My тактам к выходу устройства подключаются выход суммы сумматора-вычитателя 2 и выход блока 3 задержки соответственно последнего яруса, а далее последовательно подключаются выходы блоков 3 задержки (i-l)-ro, (i-2)-ro и т.д. ярусов , причем число тактов, на которое подключается выход бпока 3 задержки i-ro яруса, равно N/2 .

Таким образом, через N тактов на выходе коммутатора 4 последовательно формируются коэффициенты разложе71

10

15

20

25 30

194

ходе суммы (+) сумматора-вычитателя 2 первого яруса формируются суммы первого шага (6), При этом разности (6) поступают в блок 3 задержки длиной N. В последующих ярусах блоки 1 и 3 задержки и сумматоры-вычитате- ли 2 работают аналогично первому ярусу, причем длина блока задержки i-ro яруса равна N/2 , а блока 3 задержки , Суммы (6) i-ro яруса поступают на вход блока 1 задержки (i+l)-ro яруса, а разности (6) - в блоки 3 задержки i-ro яруса. Таким 1 образом, реализуется быстрый алгоритм согласно графу фиг,2. Через N тактов на выходе суммы (+) сумматора-вычитателя 2 последнего яруса формируется первый коэффициент С разложения в базисе интегральных функций Хаара, который через коммутатор 4 поступает на выход, а коэффициент С, формируемый на выходе разности (-) , поступает в блок 3 задержки и через такт - на выход коммутатора 4.

Управление коммутаторов 4 осзпцест- вляется от блока 5 постоянной памяти (ПЗУ), адресуемого счетчиком 6, Для N 8 прошивка ПЗУ 5 представлена в таблице.

11

II

11

11

ния С; по интегральным функциям Хаа- ра. В случае, когда последовательность {ХЛ поступает непосредственно на вход блока 1 задержки первого яруса, на выходе коммутатора 4 формируются коэффициенты разложения С. по кусочно-постоянным функциям Хаара.

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

Устройство для преобразования по функциям Хаара, содержащее п сумма- торов-вычитателей и 2п блоков задержки (2 - размерность преобразования),

причем вход и выход (2i-l)-ro (i 1,... ,n) блока задержки подключены к входам i-ro сумматора-вычитателя, выход разности i-ro сумматора-вычитателя подключен к входу 2i-ro блока

задержки,отличающееся

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

гистр сдвига, вьгчитатель, счетчик, блок постоянной памяти и коммутатор причем вход регистра сдвига является информационным входом устройства и подключен к входу уменьшаемого вы- 5 читателя, выход регистра сдвига подключен к входу вычитаемого вычита- .теля., выход вычитателя подключен к входу первого блока задержки, выход суммы i-ro кроме п-го) сумматора- Ш вычитателя подключен к входу (21-1 )-го блока задержки, выход суммы п-го сум

матора-вычитателя подключен к первому информационному входу коммутатора, выход 2i-ro блока задержки подключен к (i-H)-My информационному входу коммутатора, вход счетчика является тактовым входом устройства, выход счетчика подключен к адресному входу блока постоянной памяти, выход блока постоянной памяти подключен к управляющему входу коммутатора, выход коммутатора является выходом устройства.

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в цифровых системах связи для построения устройств цифровой фильтрации, сжатия изображений и вьщеления контуров,основанных на алгоритме быстрого преобразования Хаара. Цель изобретения - расширение функциональных возможностей устройства за счет преобразования по интегральным функциям Хаара. Устройство содержит блоки 1 задержки, сумматоры-вычитатели 2, блоки 3 задержки, коммутатор 4, блок 5 постоянной памяти, счетчик 6, регистр 7 сдвига, вычитатель 8. Введение регистра, В1 1читателя, счетчика, блока постоянной памяти и коммутатора поз- воляет вычислять коэффициенты преобразования по интегральным функциям Хаара. 2 ил. (/) i П СО Ю vl СО фие.г

л,-лг

С8

Фиг, 2