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

 

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

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

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

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

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

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

Б . Е ь l30bhA)i

И где С = (С,3 вектор коэффициентов преобразования; квадратные матрицы преобразования размерностью И 11: (i)

Vgэ W

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4341620/24-24 (22) 11.12.87 (46) 23.09.89. Вюл. М- 35 (72) Г.Е. Галич, В. А. Зенцов и Г-.А, Кухарев (53) 681. 32 (088. 8) (56) Авторское свидетельство СССР

Р 922721, кл. G 06 F 15/332, 1980.

Авторское свидетельство СССР

N - 555404, кл. G 06 F. 15/332, 1975 ° (543 УСТРОЙСТВО ДПЯ ОРТОГОНАЛЪНОГО

ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ СИГНАЛОВ IIO

У ОЛШУ-АДАМАРУ

t (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в качестве. специализированного устройства спектрального анализа и имитации случайИзобретение относится к автоматике и вычислительной технике и может быть использовано в качестве специализированного устройства спектрального анализа и имитации случайных процессов, для обработки и распознавания изображений, в аппаратуре сжатия информации при передаче данных, в цифровых системах управления и так далее и для, выполнения усеченных и полного быстрых ортогональных преобразо- ваний цифровых сигналов в базисе функций Уолша над отсчетами дискретного сигнала.

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

„„SU„„3669936 А1

2 ных процессов, для обработки и распознавания изображений, в аппаратуре сжатия информации при передаче данных, цифровых системах управления и т.д. Цель изобретения — расширение функциональных возможностей устройства за счет выполнения как неусеченных, так и усеченных ортогональных преобразований. В состав устройства входят элементы задержки, арифметические блоки и элементы И, объединенные в канал единичного преобразования, счетчик,два регистра, группа элементов задержки, группа блоков сравнения, группа элементов ИЛИ и четыре группы элементов И, объединенные в блок настройки, а также блок синхронизации. 9 ил., 2 табл. ва за счет выполнения как неусеченных, так и усеченных дискретных ортогональных. преобразований цифровых сигналов. l

Усеченные ортогональные преобразования последовательности обрабатыва-: емых данных Х (Х -1. определяются

1 11 следующим образом:

<1 (М (-s)

С VgVя Uк МКХ (1) W„-E,е I г" < 1

1 и Ш (kll 1Е пРи Il у 1 е

В, -1(" (Т„при k g

Е1 1 ) . 10

Т - единичная квадратная матриМ ца порядка Б;

® - знак кронекеровского перемножения матриц;

® — знак кронекеровского сложения, Введение в рассмотрение усеченных преобразований в базисе функций Виленкина (частным случаем которых является преобразование Уолша) было вызвано необходимостью учета различной физической природы обрабатываемых сигналов, их статических и спектральных свойств, класса задач обработки, т.е. адаптации ортогонального преобразования к классу обрабатываемых сигналов. Усеченные преобразо" вания, определяемые выражением (I) позволяют, меняя значения параметров

g П-1 заполнить широкий спектр

30 возможных ортогонапьных преобразований между преобразованиями Уолша (при всех k e = 1) и Хаара (n9zfke$<., 1, (kдf ; =, О) и тем самым подобрать необходимую степень рассредото- 35 ченности и локализации энергии базисных функций на различных временных участках.

На фиг.1 изображена функциональная схема устройства для случая И=8; 40 на фиг.2 — гриф полного БПУ для N 8 закодированный ««; на фиг.3-8 - графы усеченных дискретных ортогональных преобразований для 11=8, закодированные следующим образом: 0«, 1+,00, 45

01, 10, 11 соответственно; на фиг.9схема арифметического блока.

Блок-схема устройства (фиг.1) содержит элементы I и 2 задержки, арифметические блоки 3, элементы И 50

4 и 5, образующие три канала единич.1509930 4 ного преобразования, блок 6 синхрониs ации, совокупность элементов, обра" зующих блок настройки, выход 7 блока 6 синхронизации, регистры 8 и 9, счетчик 10, блоки 11 и 12 сравнения, элементы ИЛИ 13 и 14, элементы

15 и 16 задержки, четыре группы иэ, двух элементов И 17 и 18, 19 и 20, 21 и 22, 23 и 24, информационные вход

25 и выход 26.

Арифметический блок (фиг.9) содержит сумматор 27, вычитатель 28, элементы И 29 и 30, элемент НЕ 31, элемент ИЛИ 32 и преобразователь 33 прямого кода в дополнительный.

Устройство работает след ющим образом.

Рассмотрим работу устройства при выполнении вычислений в соответствии с графом полного БПУ на фиг.2 (работа операционной части предлагаемого устройства).

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

С частотой тактовых импульсов значения дискретного сигнапа Х 1), q 1, 2,...,N последовательно поступают на вход первого канала. Арифметический блок 3 производит поочередное суммирование значений сигналов с выхода и входа первого элемента 1 задержки и вычитание значений сигналов с выхода и входа второго элемента 2 задержки. Значения. суммы и разности поступают на второй канал единичного преобразования, где производятся аналогичные вычисления, но задержки каждого элемента возрастают вдвое.

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

: Работа устройства проиплюстрирова. на табл,1 для 118.!

509930

° -х

Хх(+ 1 г- г-Х

Х К I

+ + ч

° «Х хк+ + I л ллй х х

+ + +.ч ч ч кхх

+ I I

ЕЪ Ег Гг кхх

+ + 1

° 4 г н ххк

+ I +! Ххк а ч г ч хх

+ 1 г. гкх

1 1 ч хк

1 I

lC к х

+ 1 ч хх

+ + ю и х х

1 +

4 °" к х

I + ххх

+ + I ххх

I + 1

° ч ° кхк

+ 1 +

l хкх

I 1 ч ч ч ххх

1 1 + ч ххх

+ 1 I

Cl C Ч ххх

1 + I ххк !

O( о

1 1 1 ххфх

66а

I я o(a x ръхох — — Ъ

uuuuIaoa4aIa !

4Е чХ "; °

xxxx+ x!Кх

+ 1 1 + ° 1 1 +

CC Л CC 4 гх l ххкх+ к кк

++ I I «+1 ег гг 4 clx e v ч

КХК К ККК

+ I + 1 + I + I

Э 4Е CC Л

1 I ХХХХХХХХ

111111

Ч гг ххх

+ i I ь у. к х

+ 1

° 4 4ег ххх

+ 1 +

I ХКХ

Е Ю ч 44 Ч ххххх

+ + 1 1 +

4C t. ° Г Г хххкк

1 + + 1 I

° 4 × × × « хкxхx

1 1 I + 1 ь ь л

ХХХХХ

i I 11 е- чч ххххкххх

+ 1 1 + + I 1 +

Л CC CC Г 4 ° Iх х х х у. х х х

+ + 1 1 + + 1 1

44 Е4 Ге Ч ххху;ххху;

+ 1 + 1 + 1 +

l I! xxxxxxxx !

1 1 1

I I о х сс ххах

1 4(OI È а

1 — — 4 сохох гг

1 1 1 1 I 1

u u aI co u u (a oo !

1 с 4 ! ЯБ

O g Х Х еЪ !

1ф1хф

1 СО «Х сЭ Х

4 ° Ч « ° .Г е ххххххх

+ I + 1 + 1 + е л г л

1 ХХХХХХХ I

1 1 1

° 4 ег Ч Ч ° .е е, ХХХХХХХХ

+!+!+1+

Л 4 Г ! ХХХХХХХХ!!

1

1 I 1

1 I

4Ъ ° 1 о с(ххххх !

KIIoIaa a !

1а lO«4 Х Q Х 1

1 1 I 1 !! эф! — — — ц ЧИ-!

О ХХХХчЪ

Ф х х ф

С41 Х ОХ

44ч«Л«гее

1 ХХХХХХХХ 1 I C 1 1

1

I с 4

I o IC! х ю ч ч л ч ч

I ХХХХХХХХ I !11111

1 — — — — -! ф Ц Ф е ч л е 4 ° г э

ХХХХХХХХ I I 1 1 I 1 1 1 (О ф

4 СО О

СЧ 4Ъ о- СЧ 4 Ъ Э Ъ О Г а В».( ф ч н Т

1 с( о а ! ! !с

I 1 !

4Ъ ег !

1 о х з х

С4 С4 Ч Ч « .4 Ч

ХХХХХХХХ

+ 1 + 1 + 1 + и е л г- г

ХХХХХХХХ!

0(О0(О0(О0(О !

1

1 1

1 1

1 1!

1 Ю,)3

1 ! в х! !, 5

1! 0! e!

3х! х ф! х,! х 1509930

Т аблица2

Номер такта, на котором должен быть подан единичный сигнал на

Код на регистре

Конфигур ация графа на фиг.

Г (41 4 5 5

4

6

8

00 00

01 00

10 00

11 00

ОХ 01

IX 01

XX 10

2 3

4 5

6 7

8 9

2,4 3,5

6, 8 7,9

6,8 7,9

4,5

4,5

8,9

8,9

4,5

8,9

4,5, 8,9

6,7

6,7

10,11

10,11

6,7

10, 11

6,7, 10,11

П р и м е ч а н и е. Х - безразлично "О" ипи "1", Теперь рассмотрим работу блока .настройки — управляющей части устрой1

;ства.

Каждый граф усеченного преобразо5 .;вания закодирован с помощью двух кодов, размещаемых в регистрах 8 и 9.

В регистре 8 размещается (n-1) -разряный код, который определяет положение участвующих в. обработке номеров отсчетов среди имеющихся. Причем . младшие и-i разрядов определяют положение (номер 1 в (1), начиная с "О") ,,соответствующей бабочки в i-й итера:ции. В регистре 9 код имеет только

1 одну "1", остальные "О". Положение этой единицы (номер разряда) опреде-, ляет порядковый номер той итерации, 1где прекращается увеличение числа . 20 участвующих в обработке отсчетов

Задача блока настройки — выработка управляющих сигналов в соответ ствии с табл.2. При установке кодов в регистры 8 и 9 с выхода 7 поступа- 45 ют импульсы на счетчик 10. До тех пор, пока значение n-i младших раз1 рядов счетчика 10 не равно значению младших разрядов регистра 8, на вы--. ходе всех блоков 11 и 12 сравнения

50 имеется нулевой сигнал. При совпадении этих значений на выходе опреде-, ленного j-ro блока сравнения появляется единичный сигнал, который пропускает очередной импульс с выхода 7 на элемент ИЛИ через открытый элемент И,. Затем этот импульс "разделяется нужным образом" элементами И 2124, управляемыми значениями (j-1)-ro (начиная с этой итерации число отсчетов становится равным N) .

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

Соответствие между конфигурацией графа ортогонального преобразования,. соответствующими кодами в регистрах и номерами тактов, на которых необходимо подавать единичные управляющие сигналы на соответствующие элементы И, задается табл.2. разряда счетчика 10, и задерживается на определенное число тактов в элементах 15 и 16 задержки.

Описанное функционирование блока настройки имеет место в случае, когда в регистре 9 записан нулевой код.

Если же там имеется "1" в некотором

К-м разряде, то она поступает на

К-й элемент И второй группы 19 и 20, открывая его. Тем самым все импульсы, которые относятся к (K+1)-му разряду ((п-К-1)-й итерации графа) поступают в ту часть блока настройки, где вырабатываются. управляющие сигФ налы, относящиеся к работе устройст:ва на,(п-K)-й итерации.

Рассмотрим, например работу устройства при реапизации усеченного

1509930 ортогонального преобразования для графа (фиг. 8) . В начальном состоянии на счетчике 10 находится код 11...1, При этом на регистре 8 записан код

1О (а может быть записан код 11), на регистре 9 код 01 (табл.2) . Импульсы с выхода 7 заполняют счетчик

10, на первом такте его содержимое ст анрвится 00...О. Блок 12 ср авнения фиксирует равенство кодов на пятом такте, затем на седьмом, а блок 11 сравнения — на пятом-восьмом тактах. Таким образом, на выходе элемента ИЛИ-13 импульсы появляются также на пятом-восьмом тактах. Так как элемент И 15 открыт единичным сигналом с первого разряда регистра

9, то на выходе элемента ИЛИ 14, кроме импульсов с элемента И 18, на пятом и седьмом тактах появляются еще импульсы с элемента И 20 на пестом и восьмом такт.ах. С учетом задержек на третий и первый такт в элементах

15 и 16 задержки соответственно на

1 выходе элемента И 21 импульсы появляются на восьмом и девятом тактах, на выходе И 23 — на десятом и одиннадцатом тактах, на выходе И 22 на шестом и восьмом тактах, на выходе И 24 — на седьмом и девятом тактах. Это означает, что в первом канале единичного преобразования выполнены только операции Х +Х

Х +Х, Х -Х, Х -Х (табл.1), Во втором канале — только операции Х +X +

+Х7+Х,+Х,, Х,+ Х, Х; Х „Х,— К,+ Х,Х, Х вЂ” К - Х7+ Ха °

В третьем канале выполнены все операции, соответствующие третьей последней итерации БПУ. Таким образом, реализовано усеченное ортогональное преобразование, которое может быть записано следующим образом:

С7 = Х + Х5. + Х + Х7 + Х8, С7. = Х + Xz — Х + Х7 — Х э с,-х,+ х, + х,-х,-х,;

Сз Х4+ Х Х вЂ” Х7 + Х, С4 = Х + Х5 - Х + Х7 — Х, С Х Х Х Х Х е

С Х1 — Х + Х6 Х7 + Х8

С7 = Х вЂ” X5 — К + Х7 + Xst

Cs = Х4 X5+ Х + X7 xij что соответствует графу на фиг.8.

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

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

55 шу-Адамару, содержащее и (N=2"— размер преобразования) каналов еди" ничного преобразования и блок синхрониз ации, причем выход i-ro (i

1, и-1) канала единичного преобразования подключен к информационному входу (i+1)-го канала единичного преобразования, выход n-ro канала единичного преобразования является. информационным выходом устройства, информационным входом которого является информационный вход первого ка| нала единичного преобразования, j é (j = 1,n) выход блока синхронизации подключен к тактовому входу

j-ro канала единичного преобразования, причем j-й канал единичного преобразования содержит первый и второй элементы задержки и арифметический блок, тактовый вход которого является тактовым входом канопа единичного преобразования, информацион-. ным входом которого является вход первого элемента задержки, выход которого подключен к входу второго элемента задержки и первому информационному входу арифметического блока, выход которого является выходом канала единичного преобразования, при этом в и-м канале единичного преобразования второй и третий информационные входы арифметического блока подключены соответственно к информационному входу канала единичного преобразования и выходу второго элемента задержки, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения как неусеченных, так и усеченных преобразований, в него введены счетчик, два регистра, и-1 блоков сравнения, группа элементов ИЛИ, группа элементов задержки и четыре группы элементов И по и-1 элементу в каждой группе, а в i-й канал единичного преобразования введены два элемента И, при этом (и+1)-й выход блока синхронизации подключен к счетному входу счетчика, первым входам элементов И первой группы и первому входу (n-1)-ro элемента И вто-, рой группы, и- входов первой группы

i-ro блока сравнения подключены соответственно к выходам и-7. старших разрядов счетчика, n-i входов второй группы i-ro блока сравнения под- . ключены соответс-венно к выходам

1509930

12 старших разрядов первого регист ра, выход i-ro блока сравнения под ключен к второму входу i-ro элемента И первой группы, выход которого подключен к входу i-го элемента ИЛИ группы, выход х-ro разряда второго регистра подключен к первому входу т-го впвмвитв И второй гРуппы, второй вход m-ro (m 2 и- I ) элемента И второй группы. подключены к выходу

;(а+1)-го элемента ИЛИ группы, выход

i-ro элемента И второй группы подключен к второму входу i-ro элемента

ИЛИ группы, выход которого подключен к входу i-ro элемента з,адержки группы, выход которого подключен к пер" вым входам i-х элементов И третьей и четвертой групп, выходы которых ! подключены соответственно к первому и и второму входам синхронизации i"ro канала единичного преобразования, вторые входы i-x элементов И третьей и четвертой групп подключены соответственно к инверсному и прямому выходам (i-1)-ro разряда счетчика, причем в i-м канале единичного преобразования второй и третий информационные входы арифметического блока подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены соответственно к информационному входу канала единичного преобразования и выходу второго элемента задержки,, второй вход первого элемента И является первым входом синхронизации канала единичного преобр аз ов ания, вторым входом синхронизации которого являются соединенные между собой второй вход второго элемента И и вход синхронизации арифметического блока, причем арифметический .-блок содержит два элемента И, элемент НЕ, сумматор, 10 вычитатель, элемент ИЛИ.и преобразователь прямого кода в дополнительный выход которого подключен к первым входам сумматора и вычитателя, выходы которых подключены соответствен15 но к первому и второму входам элемента ИЛИ, выход которого является выходом арифметического блока, первым, вторым и третьим предынформационными входами которого являются

20, соответственно информационный вход преобразователя прямого кода в дополнительный и первые входы первого и второго элементов И, выходы которых подключены к вторым входам соответственно сумматора и. вычитателя, второй вход первого элемента И соединен с входом элемента НЕ, входом, синхронизации сумматора и является тактовым входом арифметического бло-;

ЗО ка, входом синхронизации. которого является вход синхронизации преобразователя прямого кода в дополнительный, а выход элемента НЕ подключен к вто рому входу второго элемента И и входам синхронизации вычитателя.

1509930

1509930

1509930

Фиг. 7

1509930

Тираж 668

Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Редактор N. Бланар Заказ 5815/48

Составитель А. Баранов .

Техред Л. Олийнык,. Корректор С. Лекмар