Устройство для ортогонального преобразования цифровых сигналов по Уолшу-Адамару Советский патент 1984 года по МПК G06F17/14 

кого узла, выход которого является выходом блока.

3.Устройство поп,1 о т л и ч аю щ е е с я тем, что блок преобразования по Уолшу-Адамару по основанию шесть содержит десять последовательно соединер1ных элементов задер ки первой группы, элементы задержки второй группы, .четыре коммутатора, три арифметических узла и сумматор, причем вход первого элемента задержки первой группы является информа - ционным входом блока, вход и выход первого элемента задержки первой группы, а также выходы третьего, четвертого, шестого седьмого, девятого и десятого элементов задержки первой группы подключены к информаИД1ОННЫМ входам первого коммутатора, выход которого подключен к входу первого арифметического узла, выходы второго, пятого и восьмого элементов .задержки первой группы подключены к информационным входам второго коммутатора, выход которого подключен к входу второго ариф1мети ческого узла, дополнительные выходы третьего, четвертого, шестого и седьмого элементов задержки первой группы подключены к информационным входам третьего коммутатора, выход которого подключен к входу третьего арифметического узла, выход которого подключен к первому инфopмaциoннo ry входу четвертого коммутатора и через элемент задержки второй группы к второму информационному входу четвертого коммутатора, выходы первого и второго арифметических узлов и выход четвертого коммутатора подключены к входам cy iмaтopa, выход которого является выходом блока, управляющий вход четвертого коммутатора является управляющим входом первой группы блока, управляющие входы первого, второго и третьего коммутаторов являются управляющими входами второй группы блока.

4.Устройстпо по п. 1, отличающееся тем, что блок преобразования по Уолшу-Адамару по основанию десять содержит восемнадцать последовательно соединенных элементов задержки первой группы, элемент задержки второй группы, четыре коммутатора, три арифметических узла и сумматор, причем вход первог элемента задержки первой группы является информацион11ым входом блока, вход и выход первого элемента задержки первой группы, а также выходы второго, третьего, пятого, шестого, седьмого, восьмого, десятого, одиннадцатогб, двенадцатого, тринадцатог пятнадцатого, шестнадцатого,, семнадцатого и восемнадцатого элементов задержки первой группы подключены к информащшнным входам первого коммутатора, выход которого подршючен к входу первого арифметического узла, выход которого подключен к первому информа1.(ионному входу второго коммутатора и через элемент задержки вто рой группы к второму информащюнном входу второго комь:утатора 5 дополнительные выходы пятого, десятого и пятнадцатого э.пементов задержки первой группы подключены к информацион ным входам третьего коммутатора, выход которого подключен к входу второго арифметического узла, дополнительные выходы шестого, седьмого, восьмого, девятого, одиннадцатого, двенадцатого, тринадцатого к четырнадцатого .элементов задержки первой группы подключены к информационным входам четвертого коммутатора; выход которого подключен к входу третьего арифметического узла, выходь: второго и третьего арифметических узлов, а также выход второго кo мyтaтopa подключены к входя..: сумматора, выход которого .является выходом блока, управляю1ций вход, второго коммутатора я.пяется управ.пя;о1шм входом первой группы блока, управляющие входы первго, третьего и четвертого коммутаторов являются управляющит-ш входами второй группы блока.

5, Устройство по п,. 1, о т л и ч а ю щ е е с я теМ; что блок управления содер:1кит задаю дий генератор hi последовател.ьно соедиггенных делителей часготы

два,

последовательно соединенных делителей частоты на шесть, k -1 последовательно соединенных де лителей частоты на десять и h-f 1 формирователей импульсов, причем вькод задающего генератора подключен к входу первого делителя частоты на. два,, выход iV-го делителя частоты на два подключен к входу первого делителя частоты на шесть, выход h-го делителя частоты на шесть подключен к, входу первого депитепя частоты на десять выход m-го делителя частоты на два подключен к входу

первого формирователя импульсов, выход L. -го делителя частоты на шесть подключен к вхопу i+1 -го Лормирователя импульсов, выход -го ( В 1,..., ) делителя частоты на десять подключен к входу п+1+ -го формирователя импульсов, выход задающего генератора и выходы делителей частоты на два, кроме m-го делителя частоты на два, образуют первую группу выходов блока, выходы « -го (f 1, . . ., п k ) формирователя иьшульсов являются выходами (,+ 1)-й группы блока.

1. УСТРОЙСТВО ДЛЯ ОРТОГОНАЛЬНОГО ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ СИГНАЛОВ ПО УОЛШУ АДАМАРУ, содержащее последовательно соединенные блоки преобразования по Уолшу-Адамару по основанию два и блок управления, причем информационный вход первого блока преобразования по Уолшу-Адамару по основанию два является входом устройства, выходы первой группы блока управления подключены к управляюц№1м входам соответствукнцих блоков преобразования по Уолшу-Адамару по основанию два, отличающееся тем, что, с целью расширения функциональных возможностей устройства, состоящего в преобразовании по Уолшу-Адамару при объеме выборки N 10 где m,n,1 неотрицательные целые числа, оно содержит п последовательно соединенных блоков преобразования по Уол-шу-Адамару по основанию шесть и k последовательно соединенных блоков преобразования по Уолшу-Адамару по основанию десять, причем выход т-го блока преобразования по Уолшу-Адамару по основанию два подключен к ни- формационному входу первого блока преобразования по Уолшу-Адамару по основанию шесть, выход блока преобразования по Уолшу-Адамару по основанию шесть подключен к информационному входу первого блока преобразования по Уолшу-Адамару по основанию десять, выход k -го блока преобразования по Уолшу-Адамару по основанию десять является выходом устройства, первый выход первой группы блока управления подключен к управляющему входу первой группы каждого из блоков преобразования по. Уолшу-Адамару по основанию шесть и десять,выходы (т+О-й группы блока § управления ( i 1, .. ., п ) подключены (Л к соответствуюш 1м управляющим входам второй группы i-ro блока преобразования по Уолшу-Адамару по основанию шесть, выходы п- -1+ й группы блока управления ( j 1, . .., fc. ) подключены к соответствующим управляющим входам второй группы j-ro блока преобразования по Уолшу-Адамару по основанию со десять. 00 2. Устройство по п. 1, отличающееся тем, что блок преобразования по Уолшу-Адамару по осел нованию два состоит из двух последовательно соединенных элементов задержки, коммутатора и арифметического узла, причем вход первого зле мента задержки и управлякнций вход коммутатора являются информационным и управляющим входами блока соответственно, входы и выходы элементов задержки подключены к информационным входам коммутатора, выход кото рого подключен к входу арифметичес

Изобретение относится к автоматике и вычислительной технике и может быть использовано для построения устройств цифровой фильтрации, обработки и передачи изображений, распознавания образов,, основанных на алгоритме быстрого преобразования Уолша-Адамара, когда объем входной выборки N ро , где рр 2,4, 8, 12, 16, 20,..., 100, а п и V - любые натуральные числа.

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

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

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

Целью изобретения является расширение функциональных возможностей устройства, состоящее в преобразовании по Уолшу-Адамару при объеме

m

1 10

2

где

m , п

неотрицательные целые числа.

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

тем, что устройство для ортогонального преобразования цифровьпс сигналов по Уолшу-Адамару, содержащее последо.вательно соединенные блоки преобразования по Уолшу-Адамару по основанию два и блок управления, причем информационньй вход первого блока преобразования по Уолшу-Адамару по осно ванию два является входом устройства выходы первой группы блока управлени подключены к управляющим входам соотBeTCTByroutfix блоков преобразования по Уолгау-Адамару по основанию два, содержит п последовательно соединенных блоков преобразования по УолшуУдамару по основанию шесть и К последовательно соединенных блоков преобразования по Уолшу-Адамару по основанию десять, причем выход m-го блока преобразования по Уолшу-Адамару по основанию два подключен к информационному входу первого блока преобразования по Уолшу-Адгмару по основанию шесть, выход п -го блока преобразрвания по Уолшу-Адамару по основанию шесть подключен к информационному входу первого блока преобразования по Уолшу-Адамару по основанию десять, выход блока преобразования по Уолшу-Адамару по основанию десять является выходом устройства, первый выход первой группы блока управления подключен к управлякицему входу первой группы каждого из блоков преобразования по УолшуАдамару по основанию шесть и десять , выходы (1+1)-й группы блока управления ( 1 1,. . ., п) подключены к соответствукицим управляющим входам второй группы i-го блока преобразования по Уолшу-Адамару по основанию шесть, выходы ( п+1+ j )-й группы блока управления ( j 1,..., 1) подключены к соотве.тствующим управляющим входам второй группы j-ro блока преобразования по Уолшу-Адамару по основанию десять. Блок преобразования по Уолшу-Адамару по основанию два состоит из дву последовательно соединенных элементов задержки, коммутатора и арифметического узла, причем вход первого элемента задержки и управляющий вход коммутатора являются информационным и управляющим входами блока соответственно, входы и выходы элементов за держки подключены к информационным входам коммутатора, выход которого подключен ко входу арифметического узла, выход которого является выходо блока, Блок преобразования по Уолшу-Адамару по основанию шесть содержит десять последовательно соединенных элементов задержки первой группы, элементы задержки второй группы, четьфе коммутатора, три арифметических узла и сумматор, причем вход первого элемента задержки первой группы является информационным входом блока, вход и выход первого элемента задерж ки первой группы, а также выходы третьего, четвертого, шестого, седьмого, девятого и десятого элементов задержки первой группы подключены к информационным входам первого коммут тора, выход которого подключен к входу первого арифметического узла, выходы второго, пятого и восьмого элементов задержки первой группы под ключены к информационным входам втор го коммутатора, выход которого подкл чен ко входу второго арифметического узла, дополнительные выходы третьего четвертого, шестого и седьмого элементов задержки первой группы подключены к информационным входам трет его коммутатора, выход которого подключен ко входу третьего арифметического узла, выход которого подключен к первому информационному входу четвертого коммутатора и через элемент задержки второй группы - ко вто рому информационному входу четвертого Koi-fMyTaTopa, выхода первого и второго арифметических узлов и выход четвертого коммутатора подключены ко входам сумматора, выход которого является выходом блока, управляющий вход четвертого коммутатора является управляющим входом первой группы блока, управлякнцие входы первого, второго и третьего коммутаторов являются управляющими входами второй группы блока. Блок преобразования по УолшуАдамару по основанию десять содержит восемнадцать последовательно соединенных элементов задержки первой группы, элемент задержки второй группы, четыре коммутатора, три арифметических узла и сумматор, причем вход первого элемента задержки первой группы является информационным входом блока, вход и выход первого элемента задержки первой группы, а также выходы второго, третьего, пятого, шестого, седьмого восьмого, десятого, одиннадцатого, двенадцатого, тринадцатого, пятнадцатого, шестнадцатого, семнадцатого и восемнадцатого элементов задержки первой группы подключены к информационным входам первого коммутатора, выход которого подключен ко входу первого арифметического узла, выход которого подключен к первому информационному входу второго коммутатора и через элемент задержки второй группы - ко второму информационному входу второго коммутатора, дополнительные выходы пятого, десятого и пятнадцатого элементов задержки первой группы подключены к информационным входам третьего коммутатора, выход которого подключен ко входу второго арифметического узла, дополнительные выходы шестого, седьмого, восьмого, девятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов задержки первой группы подключены к информационным входам четвертого коммутатора, выход которого подключен ко входу третьего арифметического узла, выходы второго и третьего арифметических узлов, а также выход второго коммутатора подключены ко входам сумматора, выход которого является выходом блока, управляющий вход второго коммутатора является управляющим входом первой группы блока, управляющие входы первого, третьего и четвертого коммутаторов являются управляющими входами второй группы блока. Блок управления содержит задающий генератор, m последовательно соединенных делителей частоты на два, п последовательно соединенных делителей частоты на шесть, последовательно соединенных делителей частоты на десять и n+lc формирователей импульсов, причем выход задающего генератора подключен ко входу первого делителя частоты на два, выход m -го делителя частоты на два подключен ко входу первого делителя частоты на шесть, выход И-го делителя частоты на шесть подключен ко входу первого делителя частоты на десять, выход т-го делителя частоты на два подключен ко входу первого формирователя импульсов, выход i-ro делителя час тоты на шесть подключен ко входу 1+1 -го формирователя импульсов, выход е-го ( Р 1,..., k-1) делителя частоты на десять подключен ко входу n + t+t -го формирователя импульсов, выход задающего генератора и выходы делителей частоты на два, кроме m-го делителя частоты на два, образуют первую группу выходов блока выходы (q, 1,...,b+k) формирователя импульсов являются выходами (с},+ 1)-й группы блока управления. На фиг. 1 представлена функционал ная схема устройства ортогонального преобразования цифровых сигналов по Уолшу-АдамарУ4 на фиг.2-4 - функциональные схемы блоков преобразования по Уолшу-Адамару над основанием шесть, десять и два соответственно; на фиг. 5 - функциональная схема блока управления для случая , п 2, 1с 2; на фиг. 6 - временная диаграмма для входного и трех выходных сигналов формирователя импульсов на фиг. 7 - график последовательности вычислений для порядка N 2-6 . Устройство содержит m последовательно соединенных блоков 1 преобраз вания по Уолшу-Адамару по основанию два, п последовательно соединенных блоков 2 преобразования по УолшуАдамару по основанию шесть, k последовательно соединенньк блоков 3 пр образования по Уолшу-Адамару по основанию десять, блок управления 4 информационные входы 5 и выходы 6 блоков преобразования по Уолшу-Адама ру, вход 7 и выход 8 устройства. Влок преобразования по УолшуАдамару по основанию шесть содержит элементы задержки 9-,- 9 10, коммутаторы 11-, - 11д, арифметические узлы 12з, сумматор 13, информационный вход 14, управляющие входы 15, выход 16. Блок преобразования по Уолшу-Адамару по основанию десять содержит элементб задержки 17,- 17,g, 18, ком19 , арифметические мутаторы 20j, сумматор) 21, инфорузлымационньй вход 22, управляющие вхо23, выход 24 . Блок преобразования по Уолшу-Адамару по основанию два содержит элементы задержки 25,- 25, коммутатор 26, арифметический узел 27, иг формационньй вход 28, управляющий вход 29 и выход 3 О. Блок управления содержит задаю- , щий генератор 31, дапитель частоты на два 32, делителя частоты на шесть 33 и 34, делитель частоты на десять 35, формирователи импульсов 36-39, группы выходов 40-52. Задающий генератор 31 и делители частоты 32-35 задают частоту переключений в блоках преобразования 1-3, воздействуя на их управляющие входы. Частота переключений в последующих блоках преобразования должна уменьшаться в число раз, равное основанию предьиущего канала. Так, для случая, соответствующего фиг. 5, выход 40 блока 4 управления подключается ко входу 29 блока преобразования по основанию 2, группа выходов 41 - 43 в порядке убывания частоты подключается ко входам 15,, 15, 15j первого блока преобразования по основанию шесть, и т.д., группа выходов 50-52 в порядке убывания, частоты - ко входам 23,, 232, 23з второго блока преобразования по основанию десять. Кроме того, при всяких значениях m , п , 1 выход задающего генератора 31 подключается к управлянмдим входам 15 всех блоков преобразования по основанию шесть и к управляющим входам 23х j всех блоков преобразования по основанию десять. Задержка сигналов на элементах задержки должна быть пропорциональной частоте переключений в соответствующих блоках преобразования. В качестве элементов задержки можно использовать регистры сдвига соответствующей разрядности. В этом случае основным выходом элемента задержки служит выход последнего разряда, а в качестве дополнительного выхода используется выход предпоследнего разряда егистра сдвига. Арифметические узлы в блоках преобразования выполняют операции сложения или вьмитания пар операндов,

поступающих на их суммирующие или вычитающие входы.

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

В соответствии с использованием алгоритмом над входной выборкой данных, представляемой вектором размера N, производится следующее преобразование

F

(1)

F - полученное преобразование , А - N-N матрица Адамара. Построение БПА (быстрого преобразования Адамара) над входными ма сивами размера N р основано на разработанном авторами рекурентном методе построения матриц Адамара порядков N Р(, ( Ро 2,4,8,12,16,20100), в частности pQ 2) , Пусть X и Y - матрицы, которые д преобразований по основаниям р 6 и р 10 будут иметь следующий вид +1 О 0+1 -1 -1 0+1 +1 -1 о 0+1-1 -1 +1 +1 -1 -1-1 00 -1 +1 -1 0-1 о -1 -1+1 00 -1

(2)

Yi.

1 -1 +1

О

о о о

о 1 -1

0+10 1 -1

о о +1

-1 -1 -1 +1-100

о +1

-1 -1-1-1+1 о о о о +1

+1 с о о 0-1+1+1+1+1

о 0+1 о 0+1+1-1 +1 +1

0+1 о о 0+1-1+1 +1 +1

о о 0+1 0+1+1+1 -1 +1

о 00 0+1+1 +1 +1 +1 -1

Y

10

Определим понятие -у-оператора, переводящего строки а, а,

4

ag , . . .а j матрицы А J на матрицу j А 15 следующим образом

-а

Ч ®V; .

является матрицей Адамара порядка т Здесь О - прямое (кронекеровское произведение матриц

Р порядок матрицы Адамара;

р - основание преобразовав ния, равное 6 или 10; матрица Н„, -j- Н,. Для практической реализации устройства БПА преобразование

tF3 «ЪЗГА

для построенных матриц Адамара на i-том этапе преобразования будет иметь вид (для основания р 6)

(6)

fi X,f ,. + Y.

f

1-1

гпе

f3i Xfe f..;.(xi+x) f ..xi, f.,+xf f.., (7) г д т е yi J У в блоке преобразования по основанию шесть (фиг. 2) оператор f реализуется с помощью элемента задержки 10 на два такта и коммутатор 114. Числа, поступакяцие на второй вход коммутатора, появляются на его выходе с измененным знаком. Аналогичную роль в блоке преобразования по основанию десять (фиг. 3) вьшолняют элемент задержки 18 и коммутатор 194В соответствии с (4)

v-l f,

fc -i

Матрица Xg представлена в виде

+ 1 0 0 -H 00 0+1 0 0+1 0

Xg Xj,+ X,0 0+1 0 0+1 +1 00-1 00 0+1 0 0-1 0 0 0+1 0 0-1 Для основания преобразование Адамара(1)на i-том этапе будет иметь вид

X-iof i-i-

L+ 1 О О О 0+10 00 о 0+10000+1000 00+1 0000+1 00 000+10000+10 0000+10000+1

+ 1 0000-1 0000 0+1 0000-1 000 00+1 0000-1 00

-о о о +1 о о о о -1 о 0-0 о 0+1 о о о 0-1

Используя (12), получаем для

,

.f(l

l( f Uz.)

f.((bl

(8,9,10

f(4l1(Ы

О О и 0-1о О 0-1 0о о 0-1-1 0-1-1 о о -1 0-1 00 .-t -1 000 Остается в силе также Матрицы Х и Х для вид

1-1-1 о о о о о

1-1-1 00 о о о

0-1-100000

10-100000

1-1000000

(121

00 0+1+1+1+1

о о 0+1 0+1+1+1

о о 0+1+1 0+1+1

о о 0+1+1+1 0+1

о о 0+1 +1+1 -и о

- (13, 14)

K9I 1(101 ) l((lQ) l((lOI 1(91

(15)

f((4).jl(5)

)

)

flOl+f 1(5)

KM+ 1(41

в этом спуча.е устройство ссдсрsiif /ШГь блоков преобразования; оди;: блек хфеобразовання по основаiiiiia два,, два блока гфеобразоаания по основацкк; шесть н два блока ирес;6раз)занн51 по основанию десять,

;;; nspcoii блоке преобразования

siJTopoe должны задерживать аларжки,, оозрлстает в два - 2, поэтому каждый -эпе;;т:-;-; ;ки два разряда третьем блоке (по

о..;Б :дв:,1га ъ) калчдьш элемент за .: нию деся

J.. i 6 }2 разрядов ре-1;В чсПвертом -Sjiotce

У ОБ с/:(йига , В ) калудьй элемент :;:к;;{ОисИг1;-1ю тест 10 - 120 разрядо У::;Л-;КИ v;;--esT 1i

зад

Piii. :.i

oc;- o;j::LH

задержк

;эе.;м.iOTyio.-j ;;д..

:1;;.Г:ТС---ЭЙ чаКгОЗЬК ИМПульСО)

дискрет и ore сигна71а пог:лс;д поступают на иход первого обо,зозгния , Здесь произ-

водится д,1 у::точ2чиое преобразование

. лйЯчЭг-ия сутчкы и разности пос-у

лают на второй блок преобразования, где производится Г|реобразование по основанию шесть (шеститочкое преобразование) в соответствии с формулой (б), где f и выходные вектра соответственно первого и второго блоков преобразонания, а f , -jj-fg .

В третьем блоке преобразования :прО 13Бодится преобразование по основанию десять (десятиточечное преобразование) в соответствии с формует ой

f - ч Г V f

L 2 .. 10 1-.|.,- .j,,| 1 ,| .

6 четвертом и пятом блоках производятся преобразования соответственно по основаниям шесть и десять по формулам:

f.U

f-,

f

2 6 fl

f, -; Y

3

(С

f4 те г

г.

и

выходные

1S

-2- 3

зсктора соответственно второго, треего, четвертого и пятого блоков преобразования.

Преимуществом предлагаемого уст эойства является ЕОЗМОЛШОСТЬ выполнения преобра;

5ования со смешанным о. для N 10 нозанием,, т е

Рас;1С1Ложение блоков с различными ocHoaaHMHiiH можно комбинироват 13 любом порядке.

Для вьтолн:ениЕ обратного БПА используется то же устройство без I-.f-.ieneHUH,

19

- S

-. --; : пз1йГ-.:..-rrrE-C: ; аа2;;

28

Z5,

зг

л

31

5

TV

4/424J

mmПППГ.

27

30

Фиг.

Jtf

5У

J

гФ Ф

W5t52

7i.