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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 3 бв О "6 Р 15/332 ОПИСАНИЕ ИЗОБРЕТЕНИЯ 3И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЪЮ(46) 15 .Об .84. Бюл . В 22 (72) С.С.Агаян и А.В.Мелкумян (71) Ереванский политехнический институт им. К.Маркса(56) 1. Патент США В 3742201, кл. С Об Р 15/34, 1973.2. Авторское свидетельство СССР У 555404, кл. С 06 Р 15/20, 1975 (прототип).(54)(57) 1. УСТРОЙСТВО ДЛЯ ОРТОГОНАЛЬНОГО ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХСИГНАЛОВ ПО УОЛШУ АДАМАРУ, содержащее последовательно соединенные блокипреобразования по Уолшу-Адамару пооснованию два и блок управления,причем информационный вход первогоблока преобразования по Уолшу-Адамару по основанию два является входомустройства, выходы первой группыблока управления подключены к управляющим входам соответствующихблоков преобразования по Уолшу-Адамару по основанию два, о т л и ч аю щ е е с я тем, что, с целью расширения функциональных возможностей.устройства, состоящего в преобразовании по Уолшу-Адамару при объемевыборки М = 2 6" 1 О, где в, п,%неотрицательные целые числа, оносодержит и последовательно соединенных блоков преобразования по Уол"шу-Адамару по основанию шесть ипоследовательно соединенных блоковпреобразования по Уолшу-Адамару пооснованию десять, причем выход 1 о-гоблока преобразования по Уолшу-Адама=ру по основанию два подключен к ин 801098005 А формационному входу первого блокапреобразования по Уолшу-Адамару пооснованию шесть, выход ь -го блокапреобразования по Уолшу-Адамару пооснованию шесть подключен к информационному входу первого блока преобразования по Уолшу-Адамару пооснованию десять, выход % -го блокапреобразования по Уолшу-Адамару пооснованию десять является выходомустройства, первый выход первойгруппы блока управления подключенк упоавляющему входу первой группыкаждого из блоков преобразованияпо Уолшу-Адамару по основанию шестьи десять, выходы (1+1)-й группы блокауправления ( 1 = 1 п ) подключенык соответствующим управляющим входамвторой группы 1-го блока преобразо -вания по Уолшу в Адама по основаниюшесть, выходы(о+1+ 1)й группы блокауправления ( ) = 1 1) подключенык соответствующим управляющим входамвторой группы 1-го блока преобразования по Уолшу-Адамару по основаниюдесять,2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок преобразования по Уолшу-Адамару по основанию два состоит из двух последовательно соединенных элементов задержки, коммутатора и арифметического узла, причем вход первого элемента задержки и управляющий вход коммутатора являются информационным и управляющим входами блока соответственно, входы и выходы элементов задержки подключены к информационным входам коммутатора, выход кото рого подключен к входу арифметичес овзсокого узла, выход которого являетсявыходом блока,3, Устройство по п.1 о т л и ч а ю щ е е с я тем, что блок преобразования па Уолшу-Адамару по основанию шесть содержит десять последовательно соединенных элементов задержки первой группы, элементы задержкивторой группычетыре коммутатора,три арифметических узла и сумматор,гричем вход первого элемента задержки первой группы является информа -ционным входом блока, вход и выходпервого элемента задержки первойгруппы, а также выходы третьего,четвертого, шестого, седьмого, девятого и десятого элементов задержкипервой группы подключены к информационным входам первого коммутатора,выход которого подключен к входупервого арифметического узла, выходь 1 второго, пятого и восьмогоэлементов задержки первой группыподключены к информационным входамвторого коммутатора, выход которогоподключен к входу второго арифмети-.ческого узла, дополнительные выходытретьего, четвертого, шестого иседьмого элементов задержки первойгруппы подключены к информационнымвходам третьего коммутатора, зыхсдкоторого подключен к входу третьегоарифметического узла, выход которогоподключен к первому информационномувходу четвертого коммутатора ичерез элемент задержки второй группык второму информационному входучетвертого коммутатора, выходы пергзого и второго арифметических узлов ивыход четвертого коммутатора подключены к входам сумматора, выход которого является выходом блока, управляющий вход четвертога коммутатораявляется управляющим входом первойгруппы блока, управляющие входы первого, второго и третьего коммутаторов являются управляющими входамивторой группы блока,4. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок преобразования па Уолшу-Адамару по Основанию десять содержит восемнадцать последовательно соединенных элементов задержки первой группы, элемент задержки второй группы, четыре коммутатора, три арифметических узла и сумматор, причем вход первого элемента задержки первой группы является информационным зхадом блока, вход и выход первого элемента задержки первой группы, а также выходы второго, третьего, пятого, шестого, седьмого, васьмага, десятога, один- надцатогЬ, дзенадцатого, тринадцатого пятнадцатога, шестнадцатого семнадцатого и восемнадцатого элементовзадержки первой группы подключены к информационным входам первого камму - татара, выход которого подключен к гзхаду первого арифметического узла, выход которого подключен к первому информационному входу второго комму - татара и через элемент задержки вто = рай группы к второму инфармапноннаму вхадч вто 1 ога коммутатора, дополни тельные выхацы пятого, десятого и пятнадцатого элементов задержки первой грунпь подключены к информацианным входам третьего коммутатора, выход которого подключен к входу вто - рого арифметического узна, даполнительнь:е выходы шестога, седьмого, васьмагацевятога, одиннадцатого, двенадцатого, тринадцатого,; четырнадцатога элементов задержки первойГруппы подключены к инлаэмацианньмвходам четвертого коммутатора, выходкоторого подключен к входу третьегоарифметического узла, выходы второгои третьего арифметических узлов, атакже выход второго коммутатора падключены к входам сумматора, вьгхад которого являегся выходом блока, управляющий вход второго коммутатора является управляюигим входом первой группы блоха, управляющие входы первого, третьего и зетзертага ксммутатороз являют я управляюзгНтт входами второй группы блока,5. Устройства па и,. 1, а т л и ч а ю ш е е с я тем чта блок управления содержит задающий генератор и 1 последоватс;ьно соединенных делителей час гат":ни два и наследовав теяьно соеди енных делителей частоты на шесть, 1 -1 последовательна соединенных делителей частоты на десять и и+ % формирователей импульсов, причем вьгхад задающего генератораподключен к входу первого делителячастоты на два выход н -го делителячастоты на два подключен к входупервого делителгг частоты на шесть,выход я -го делителя частоты на шестьподключен к входу первого делителя Очастоты на десять выход ги -го делителя частоты на два подключен к входу109800первого формирователя импульсов, выход 1;го делителя частоты на шесть подключен к входу+ 1 -го формирователя импульсов, выход 1 "го (=1 3 с) делителя частоты на десять подключен к входу и+1+ 1 -го формирователя импульсов, выход задаю 5щего генератора и выходы делителей частоты на два, кроме в -го делителя частоты на два, образуют первую группу выходов блока, выходы с -го (с =1 и + 1) формирователя импульсов являются выходами +1) - й группы блока.Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для построенияустройств цифровой фильтрации, обработки и передачи изображений,5распознавания образов основанныхна алгоритме быстрого преобразования Уолша-Адамара, когда объем входной выборки И = Ро 6 10 , где ро =с2,4, 8, 12, 16, 20, , 100, а 10н и % - любые натуральные числа,Известно устройство выполняющееортогональное преобразование УолшаАдамара для выборок объемом И=2,содержащее три канала единичного преобразования, которые соединены последовательно и обеспечивают на выходетретьего канала получение коэффициентов преобразования по Уолшу-Адамаруот последовательности, составленной 20из восьми значений 1 1.Наиболее близким к предлагаемомуявляется устройство для ортогонального преобразования цифровых сигналовна Уолшу-Адамару, содержащее последовательно соединенные блоки преобразования по Уолшу-Адамару по основанию два и блок управления 21,Однако известные устройства невозможно применить для решения за- ЗОдач обработки информации в тех случаях, когда объем входной выборкиотличен от 2.Целью изобретения является расширение функциональных возможностейустройства, состоящее в преобразовании по Уолшу-Адамару при объемевыборки 26 " 10 , где пз,п, % -%неотрицательные целые числаПоставленная цель достигаетсятем, что устройство для ортогонального преобразования цифровых сигналовпо Уолшу-Адамару, содержащее последо,вательно соединенные блоки преобразования по Уолшу-Адамару по основанию два и блок управления, причем информационный вход первого блока преобразования по Уолшу-Адамару по осно - ванию два является входом устройства, вьжоды первой группы блока управления подключены к управляющим входам соответствующих блоков преобразования по Уолшу-Адамару по основанию два, содержит д последовательно соединен - ных блоков преобразования по Уолшу - Удамару по основанию шесть ипоследовательно соединенных блоков преобразования по Уолшу-Адамару пооснованию десять, причем выход в -го блока преобразования по Уолшу-Адамару по основанию два подключен к информационному входу первого блока преобразования по Уолшу-Адамару по основанию шесть, выход и -го блока преобразования по Уолшу-Адамару по основанию шесть подключен к информа - ционному входу первого блока преоб - разования по Уолшу-Адамару по основанию десять, выход 1 с-го блока пре= образования по Уолшу-Адамару по ос - нованию десять является выходом устройства, первый выход первой группы блока управления подключен к управляющему входу первой группы каждого из блоков преобразования по УолшуАдамару по основанию шесть и десять, выходы (1+1)-й группы блока управления (= 1 и ) подключены к соответствующим управляющим входам второй группы 1-го блока преобразо - вания по Уолшу-Адамару по основанию шесть, выходы ( п +1+ 1 )-й группы блока управления ( 1 1 %) подключены к соответствующим управляющим входам второй группы 1-го блока преобразования по Уолшу-Адамару по основанию десять.1 О 98 ООЗ -4Блок преобразования по УолшуАдамару по основанию десять содержитвосемнадцать последовательно соединенных элементов задержки первойгруппы, элемент задержки второй группы, четыэе коммутатора, три арифметических узла и сумматор, причемвход первого элемента задержки первой группы является информацион 10 ным входом блока, вход и выходпервого элемента задержки первойгруппы, а также выходы второго,третьего, пятого, шестого, седьмоговосьмого, десятого, одиннадцатого,двенадцатого, тринадцатого, пятнадцатого, шестнадцатого, семнадцатогои восемнадцатого элементов задержкипервой группы подключены к информационным входам первого коммутатора,выход которого подключен ко входупервого арифметического узла, выходкоторого подключен к первому информационному входу второго коммутатораи через элемент задержки второйгруппы - ко второму информационномувходу второго коммутатора, дополнительные выходы пятого, десятого ипятнадцатого элементов задержкипервой группы подключены к информационным входам третьего коммутатора,выход которого подключен ко входувторого арифметического узла, дополнительные выходы шестого, седьмого,восьмого, девятого, одиннадцатого,двенадцатого, тринадцатого и четырнадцатого элементов задержки первойгруппы подключены к информационнымвходам четвертого коммутатора, выходкоторого подключен ко входу третьегоарифметического узла, выходы второгои третьего арифметических узлов, атакже выход второго коммутатора подключены ко входам сумматора, выходкоторого является выходом блока, управляющий вход второго коммутатора является управляющим входом первойгруппы блока, управляюище входы первого, третьего и четвертого коммутаторов являются управляющими входами второй группы блока. Блок преобразования по Уолшу-Адамару по основанию два состоит из двух последовательно соединенных элементов задержки, коммутатора и арифметического узла, причем вход первого элемента задержки и управляющий вход коммутатора являются информационным и управляющим входами блока соответственно, входы и выходы элементов задержки подключены к информационным входам коммутатора, выход которого подключен ко входу арифметического узла, выход которого является выходом блока. Блок преобразования по Уолшу-Адамару по основанию шесть содержит десять последовательно соединенных элементов задержки первой группы, элементы задержки второй группы, че тыре коммутатора, три арифметических узла и сумматор, причем вход первого элемента задержки первой группы является информационным входом блока, вход и выход первого элемента задерж ки первой группы, а также выходы третьего, четвертого, шестого, седьмого, девятого и десятого элементов задержки первой группы подключены к информационным входам первого коммута З 0 тора, выход которого подключен к входу первого арифметического узла, выходы второго, пятго и восьмого элементов задержки первой группы подключены к информационным входам второго коммутатора, выход которого подклю чен ко входу второго арифметического узла, дополнительные выходы третьего, четвертого, шестого и седьмого элементов задержки первой группы подключены к информационным входам треть40 его коммутатора, выход которого подключен ко входу третьего арифметического узла, выход которого подключен к первому информационному входу четвертого коммутатора и через эле 45 мент задержки второй группы " ко второму информационному входу четвертого коммутатора, выходы первого и второго арифметических узлов и выход четвертого коммутатора подключены ко50 входам сумматора, выход которого является выходом блока, управляющий вход четвертого коммутатора является управляющим входом первой группы блока, управляющие входы первого, второго и третьего коммутаторов являются управляющими входами второйгруппы блока. Блок управления содержит задающий генератор,последовательно соединенных делителей частоты на два,последовательно соединенных делителей частоты на шесть % -1 последовательно соединенных делителей час- о таты на десять и л % формирователей импульсов, прйчем выход задающего ге 1098005нератора подключен ко входу первогоделителя частоты на два, выход-годелителя частоты на два подключен ковходу первого делителя частоты нашесть, выход П -го делителя частотына шесть подключен ко входу первогоделителя частоты на десять, выходю-го делителя частоты на два подключен ко входу первого формирователяимпульсов, выход -го делителя час Отаты на шесть подключен ко входу1+1 -го формирователя импульсов,выход В-го ( Р = 1 1 с) делителя частоты на десять подключен ковходу 0+1+ 7 -го формирователя импульсов, выход задающего генератораи выходы делителей частоты на два,кроме о-го делителя частоты на два,образуют первую группу выходов блока,выходы с-го ( = 1 ь+ 1 с ) Формирователя импульсов являются выхо- .дами с+1)-й группы блока управления.На Фиг. 1 представлена функциональ.ная схема устройства ортогонального 25преобразования цифровых сигналов поУолшу-Адамару; на Фиг.2-4 - функциональные схемы блоков преобразованияпо Уолшу-Адамару над основаниемшесть, десять и два соответственно;на фиг. 5 - Функциональная схемаблока управления для случая п 1 =1п = 2, Ъ= 2; на Фиг. б - временнаядиаграмма для входного и трех выходных сигналов формирователя импульсов;на Фиг. 7 - график последовательности вычислений для порядка М = 2 6 .Устройство содержит щ последовательно соединенных блоков 1 преобразования по Уолшу-Адамару по основанию 4 Одва, 1 последовательно соединенныхблокоч, 2 преобразования по УолшуАдамару по основанию шесть, 1 последовательно соединенных блоков 3 преобразования по Уолшу-Адамару пооснованию десять, блок управления 4,информационные входы 5 и выходы 6блоков преобразования по Уолшу-Адамару, вход 7 и выход 8 устройства.Влок преобразования по УолшуАдамару по основанию шесть содержитэлементы задержки 9- 9, 10, коммутаторы 11 - 11 , арифметическиеузлы 12, - 12 з, сумматор 13, информационный вход 14, управляющие входы15- 15 выход 16,55Блок щеобразования по Уолшу-Адамару по основанию десять содержитэлементы задержки 17 - 1718, 18, коммутаторы 19. - 19, арифметическиеУузлы 201- 20, сумматор 21, информационный вход 22, управляющие входы 23 - 23, выход 24.Блок преобразования по Уолшу-Адамару по основанию два содержит элементы задержки 251 - 25, коммутатор 26, арифметический узел 27, иформационный вход 28, управляющий вход 29 и выход 30,Блок управления содержит задающий генератор 31, делитель частотына два 32, делителя частоты нашесть 33 и 34, делитель частоты надесять 35, формирователи импульсов36-39, группы выходов 40-52.Задающий генератор 31 и делителичастоты 32-35 задают частоту переключений в блоках преобразования1 - 3, воздействуя на их управляющие входы. Частота переключений впоследующих блоках преобразованиядолжна уменьшаться в число раз,равное основанию предыдущего канала,Так, для случая, соответствующегофиг5, выход 40 блока 4 управленияподключается ко входу 29 блока преобразования по основанию 2, группавыходов 4 1 - 43 в порядке убываниячастоты подключается ко входам 1515 , 15 первого блока преобразования по основанию шесть, и т.д группа выходов 50 - 52 в порядке убывания,частоты - ко входам 23 231 ф 2233 второго блока преобразованияпо основанию десять, Кроме того,при всяких значениях ю , и , % выходзадающего генератора 31 подключаетсяк. Управлякицим входам 154 всех блоковпреобразования по основанию шестьи к управляющим входам 23 всех бло 4ков преобразования по основаниюдесять,Задержка сигналов на элементахзадержки должна быть пропорциональнойчастоте переключений в соответствующих блоках преобразования, В качестве элементов задержки можно использовать регистры сдвига соответствующей разрядности. В этом случае основным выходом элемента задержки служитвыход последнего разряда, а в качестве дополнительного выхода используется выход предпоследнего разрядарегистра сдвига,Арифметические узлы в блоках преобразования выполняют операции сложения или вычитания пар операндов,1098005 поступающих на их суммирующие или вычитающие входы.Устройство рассчитано на естественный порядок входных данных, результаты вычислений также получаются в естественном порядке, удобном для обратного преобразования.В соответствии с использованием алгоритмом над входной выборкой данных, представляемой векторомК 3 размера М, производится следующее преобразование 0 0 0 0 0 О 0 0 О 10 Ойределим понятие у -оператора, переводящего строки а , а , а 5, А,а ,аматрицы А 3 на матрицу т А 15 следующйм образом Г 3 = Г 3 А 3Г- полученное преобразованиеА - Б Я матриЦа Адамара,а 1 а 2 а а а аПостроение БПА (быстрого преобразования Адамара) над входными массивами размера К = ро 6"10 основано на разработанном авторами рекурентном методе построения матриц Адамара порядков М = ро 6 10 ( Ро =(4) В блоке преобразования по основанию шесть (фиг, %) оператор 1 реализуется с помощью элемента задержки 10 на два такта и коммутатор 11,. Числа, поступающие на второй вход коммутатора, появляются на его выходе с измененным знаком. Аналогичную роль в блоке преобразования по основанию десять (Фиг. 3) выполняют элемент задержки 18 и коммутатор 9.В соответствии с (4) Пусть Х и У - матрицы, которые для преобразований по основаниям р = 6 и р = 10 будут иметь следующий вид, является матрицей Адамара порядка в.Здесь- прямое (кронекеровское) произведение матрицщ-, р - порядок матрицы Адамара;(%) 0 - 1 -1 0- 1 0 - 1 0- 1 - 1 0 О 0 0 0 0 0 0 0 - 1 0 0 0-1 0 О 0 0 0 О -1 - 1 О -1 -1 О р - основание преобразования, равное 6 или 10;матрица Н, =НВ 1 и Для практической реализации устройства БПА преобразование для построенных матриц Адамара на1-том этапе преобразования будетиметь вид (для основания р = 6) гпеДля основания р=10 преобразование Адамара(1) на (-том этапе будет иметь вид Остается в силе такие выражение (7)Матрицы Х и Хдля р = 1 О имеютвид.1 Ой 1 Ц )-- ,О,3 3 У 1 г, гС - . ;.-,Р"л О э- .: У УРР Р О"и с Т 4 а ДЛ 5оото","н:3 ь 070 преобоазования пор,:,.Б 1." -:, ".,5= . 1. з - , о;,: с; 1 1 ае устрбиство сод ср- К.;, 5 Ь ;гКОБ пгвоб ЗазОБания ,.Ба;: Ба б. - .окз поеоооазова 5 Н 5: по з:",:;"р 5 кки . 1 еет Один рд зряд регист 3 0131 а,;яВ 0 1;Ова ниш шесть) ч осло так " 3-Пт;, .=;разрядов ре Гаю На второй блок преобразования, где производится преобразование по зс 110 вани 10 шесть ,шеститочное преобразование) в соответствии с формулой 6), где Г и Г - Выходные вектфо Б,:а: оответственно первого и Второго блокОБ преобразованиЯ а Е = 1 Гб3 треть:м блоке прсобразования Яро 1 зводится преобразование по осно Баниш десять 1,десятиточечное преоб:аздван 1 е,; Б сООт ВетстВии . форму 8 :етвертОм и нятОМ ОЛОках проНзвоДятся пр(:Образования соответст Бенно О зсновани 51 м шесть и десять по(13 О-Гф,;л Где Й.1, Г ., т и, Гд - Выходные23 ктОра соответстВен 110 ВторОГО треть Го, нетвертого и ПЯТОГО блокОз и езооазования,11 реимуществом гредлагаемого устрй(тва 51 вл 5 ется Возможность Выпол - .НГ 11 Я реобра зовеБия со смешанным Ос ,-о. аниемт.е. для И= 2 6" 101,1:1 С 1 оложение блоков с разлинными основаниями можно комбинировать Б лшбо 1,1 норс пкеДля вылОлнени 5 Обратного 13 ПА используется то же устройство безэн нчи