Устройство для преобразования по функциям хаара

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 G 06 F )5 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

4 f1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 4031045/24-24 (22) 27.02.86 (46) 30.07,87, Бюл. У 28 (71) Институт технической кибернети ки АН БССР (72) P.Х.Садыхов, С.А.Золотой, А.В.Шаренков и Н.Н.Легонин (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 1061150, кл. G 06 F 15/332, 1983.

Патент США У 3792355, кл. С 06 F 15/332, 1974. (54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ

ПО ФУНКЦИЯМ ХААРА (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в цифровых

„„SU„„1327119 А1 системах связи для построения устройств цифровой фильтрации, сжатия изображений и выделения контуров,оскованных на алгоритме быстрого преобразования Хаара. Цель изобретения— расширение функциональных возможностей устройства за счет преобразования по интегральным функциям Хаара. Устройство содержит блоки 1 задержки, сумматоры-вычитатели 2, блоки 3 задержки, коммутатор 4, блок 5 постоянной памяти, счетчик 6, регистр 7 сдвига, вычитатель 8. Введение регистра, вычитателя, счетчика, блока постоянной памяти и коммутатора nos-. воляет вычислять коэффициенты преобразования по интегральным функциям

Хаара. 2 ил.

l327ll! 0 0 0 1 0 0 0

О 1 О 0 0 1 О 0

О О l О О 0 1 О

0 0 G 1 0 0 0 1

1 О О 0-1 О О О

0 1 О О 0-1 О О

О О I О 0 0-1 О

000 j 000-! т

Н

6 (3) 0101

1 О-! О

0 0-1

1-1

1-ll

1

1-1

1-1

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

Хаара.

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

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

Хаара при N 8 (N 2" — размерность

- преобразования) °

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

7 сдвига, вьтчитатель 8. Блоки устройства сгруппированы в п ярусов. В 25 !

1-1010100

11-100010

1-1 О"1 0001.

1 1 1 0-1 О О О

1-! О 1 0-1 О О

1 }-1 О О 0-1 О

1-.1 0-1 О О 0-1

1010

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

9 2 блоке I задержки i-rc (i I,...,n) информация задерживается íà N/2t тактов, а в блоке 3 задержки — на

К/21 1 тактов, Работа устройства основывается на следующем положении.

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

Х=CHI (1) где С вЂ” вектор-строка коэффициентов;

Н вЂ” матрица преобразования Хаара; I — - оператор интегрирования.

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

С = Хт-"Н"= ХТ Н", (2) где Т вЂ” транспортирование.

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

7119

4.5

10 х,х,х,х,1г = (5) 15

2-й шаг

l-й шаг

d +d ++d й,C а,+d,-а,-d, С, 0 2 С д — й. С

de+d

d„+d

do 12 и -й (6) 20

000 =001 O l О

Адрес 011

Код ПЗУ 00 01 10 10

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

Аналогично работают коммутатор 4, 45

ПЗУ 5 и счетчик 6 для размерности N: по (Я+1)-му и (N+2)-му тактам к выходу устройства подключаются выход суммы сумматора-вычитателя 2 и выход блока 3 задержки соответственно пос- В0 леднего яруса, а далее последовательно подключаются выходы блоков 3 задержки (i-1)"ro, (i-2)-го и т.д, яру-, сов, причем число тактов, на которое подключается выход блока 3 задержки

i-го яруса, равно N/2 .

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

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

Отсчеты fX;) поступают на первый вход вычитателя 8 и регистра 7. В регистре 7 отсчеты (X;) задерживаются на 1 один такт, в результате этого на выходе вычитателя 8 формируется выражение (5). Далее информация задерживается блоком 1 задержки (i l) на

N/2 тактов, в результате чего на выходе суммы (+) сумматора-вычитателя

2 первого яруса формируются суммы первого шага (6), При этом разности (6) поступают в блок 3 задержки длиной Н. В последующих ярусах блоки

1 и 3 задержки и сумматоры-вычитатели 2 работают аналогично первому ярусу, причем длина блока задержки

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

Управление коммутаторов 4 осуществляется от блока 5 постоянной памяти (ПЗУ), адресуемого счетчиком 6.

Для N 8. прошивка ПЗУ 5 представлена в таблице °

100 101 110 111

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

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

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

l,...,n) блока задержки подключены к входам i-ro сумматора-вычитателя, выход разности i-ro сумматора-вычитателя подключен к входу 2 -го блока задержки, о т л и ч а ю щ е е с я тем, что,. с целью расширения функциональных воэможностей устройства за счет преобразования по интегральным функциям Хаара, оно содержит ре1327119 х, г

Диа,2

Составитель В.Байков

Редактор Л.Веселовская Техрец И.Попович

Корректор М.Пожо

Заказ 3391/46 Тираж 672

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

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

Подписное

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

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

С gf х1+Хг з

С х, õ хг

С х,Су