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

(51)4 С 06 Р 15 3 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ЗОБРЕТЕН ЕЛЬСТВУ ВТОРСКОМУ С 8 бернетиой о СССР2, 1983(54) УСТРОЙСТВО ДЛЯ ПРЕОБРАПО ФУНКЦИЯМ ХААРА(57) Изобретение относитсяавтоматики и вычислительнойи может быть использовано в областитехникицифровых ПИСАНИЕ И(71) Институт техническойки АН БССР(56) Авторское свидетельстУ 1061150, кл. С 06 Р 15/3Патент США У 3792355,кл, С 06 Р 15/332, 1974. системах связи для построения устройств цифровой фильтрации, сжатияизображений и выделения контуров,основанных на алгоритме быстрого преобразования Хаара. Цель изобретения -расширение функциональных возможностей устройства за счет преобразованияпо интегральным функциям Хаара, Устройство содержит блоки 1 задержки,сумматоры-вычитатели 2, блоки 3 задержки, коммутатор 4, блок 5 постоянной памяти, счетчик 6, регистр 7сдвига, вычитатель 8, Введение регистра, вычитателя, счетчика, блокапостоянной памяти и коммутатора позволяет вычислять коэффициенты преобразования по интегральным функциямХаара. 2 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах связи дпя построения устройств цифровой Фильтрации, сжатия изображе "Б ний и выделения контуров, основанных на алгоритме быстрого преобразования Хаара.Цель изобретения - расширение функциональных возможностей устройства эа счет преобразования по интегральным функциям Хаара.На фиг. представлена Функциональ" ная схема устройства; на Фиг,2- 15 граф быстрого алгоритма преобразования в базисе интегральных Функций Хаара при Я8 (Ю щ 2" - размерность преобразования)Устройство содержит блоки 1 задержки, сумматоры-вычитатели 2,бло" . ки 3 задержки, коммутатор 4, блок 5 постоянной памяти, счетчик 6, регистр 7 сдвига, вычитатель 8. Блоки устройства сгруппированы в п ярусов. В 2511101000 1-1010100 11-100010 1 "1 0"1 0001.1 1 1 0-1 О 0 О 1-1 0 3 0-1 0 0 .1 3-1 О 0 0-1 0 1-.1 0-1 О 0 0-1 1010 1Оператор 1для Н 8 имеет внд 9 2блоке 1 задержки ."го ( 1 п) информация задерживается на Н/2 тактов, а в блоке 3 задержки - на ЯД" такто-,Работа устройства основывается на следуюшем положении.При спектральном анализе в базисе интегральных функций Хаара произвольный вектор Х представляется линейной комбинацией базисных функцийХ=СН 1 (1) где С - вектор-строка коэффициентов;Н - матрица преобразования Хаара;1 - оператор интегрирования.Тогда процедура вычисления коэфФициентов С имеет видС = Х 1-" Н "= Х 1" Н", (2) где Т - транспортирование.Матрица Н факторизуется, что позволяет построить быструю вычислительную процедуру, которая для В8 имеет вид(5) 2-й шаг 1-й шаг 10 1 2 3 а,+1,-а,-а, С,о - 12 С 2 1, - а, С,1 ф+дтд+йО 12а,-1,(6) 20 25 30 ООО =001 010 Адрес 011 Код ПЗУ 00 01 10 1 О Таким образом, коммутатор 4 подключает к выходу устройства на (И+1)-м, такте выход сумматора-вычитателя 2 третьего яруса, на (0+2)-м такте - выход блока 3 задержки третьего яру са, на (0+3)-м и (И+4)-и тактах - выход блока 3 задержки второго яруса, на (0+5) - (0+8)-х тактах - выход блока 3 задержки первого яруса.Аналогично работают коммутатор 4, 45 ПЗУ 5 и счетчик 6 для размерности Н: по (Я+1)-му и (0+2)-му тактам к выходу устройства подключаются выход суммы сумматора-вычитателя 2 и выход блока 3 задержки соответственно пос- В 0 леднего яруса, а далее последовательно подключаются выходы блоков 3 задержки (-1)"го, (1-2)-го и т.д, яру-, сов, причем число тактов, на которое подключается выход блока 3 задержки д-го яруса, равно Б/2 .Таким образом, через М тактов на выходе коммутатора 4 последовательно формируются коэффициенты раэложез. 132Согласно (2) к массиву из Н отсчетов сначала применяют оператор 1 , а затем оператор 1 . Результат дей,8ствия оператора 1 может быть представлен в следующем виде: юй ВВоспользовавшись факторизацией (3),для Н = 4 имеем следующую процедурувычисления С: Отсчеты 1 Х;1 поступают на первый вход вычитателя 8 и регистра 7, В регистре 7 отсчеты Х;)задерживаются на 1 один такт, в результате этого на выходе вычитателя 8 формируется выражение (5). Далее информация задерживается блоком 1 задержки (1 1) на И/2 тактов, в результате чего на выходе суммы (+) сумматора-вычитателя2 первого яруса формируются суммыпервого шага (6), При этом разности(6) поступают в блок 3 задержки длиной Н. В последующих ярусах блоки1 и 3 задержки и сумматоры-вычитатели 2 работают аналогично первомуярусу, причем длина блока задержкид-го яруса равна Н/2, а блока 3 задержки К/2 , Суммы (б) 1-го ярусапоступают на вход блока 1 задержки,согласно графу фиг.2. Через 0 тактов на выходе суммы (+) сумматора-вычитателя 2 последнего яруса формируется первый коэффициент С разложения в базисе интегральных функций Хаара, который через коммутатор 4 поступает на выход, а коэффициент С 1, формируемый на выходе разности (-), поступает в блок 3 задержки и через тактна выход коммутатора 4.Управление коммутаторов 4 осуществляется от блока 5 постоянной памяти (ПЗУ), адресуемого счетчиком 6.Для К8. прошивка ПЗУ 5 представлена в таблице100 101 110 11 11 , 11 11 11 ния С; по интегральным функциям Хаара. В случае, когда последовательность Х, поступает непосредственно на вход блока 1 задержки первогояруса, на выходе коммутатора 4 формируются коэффициенты разложения Спо кусочно"постоянным функциям Хаара. формула изобретения Устройство для преобразования по функциям Хаара, содержащее п сумматоров-вычитателей и 2 п блоков задерж" ки (2 - размерность преобразования),ипричем вход и выход (2 ь)-го (1п) блока задержки подключены к входам ь-го сумматора-вычитателя, выход разности -го сумматора-вычитателя подключен к входу 2-го блока задержки, о т л и ч а ю щ е е с я тем, что,. с целью расширения функциональных воэможностей устройства за счет преобразования по интегральным функциям Хаара, оно содержит реХ -х х Составитель В.Ба Техред И,Попович Редактор Л.ВеселовскЗаказ 3391/46 Коррект ож 672 Тир арствен зобрете ва, Ж-З1 одписно НИИПИ Гос по делам 13035, Иого комитета СССР и открытаушская б., д.4/ оизводственио-полиграфическое предприятие, г.ужгород оектиая, 4 гистр сдвига, вычитатель, счетчик,блок постоянной памяти и коммутатор,причем вход регистра сдвига является информационным входом устройстваи подключен к входу уменьшаемого вычитателя, выход регистра сдвига подключен к входу вычитаемого вычита.теля, выход вычитателя подключен квходу первого блока задержки, выходсуммы -го кроме п"го) сумматоравычитателя подключен к входу (2-1)-гоблока задержки, выход суммы п-го сумматора-вычитателя подключен к первому информационному входу коммутатора,выход 21.-го блока задержки подключенк 1.+1)-му информационному входу коммутатора, вход счетчика является тактовым входом устройства, выход счетчика подключен к адресному входу блока постоянной памяти, выход блокапостоянной памяти подключен к управляющему входу коммутатора, выход коммутатора является выходом устройства.