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

Изобретение ОТНОСИТСЯ к автоматике и вычислительной технике и может быть использовано в качестве специализированного устройства спектрального анализа и имитации случайных процессов, для обработки и распознавания изображений, в аппаратуре сжатия информации при передаче даннь:х, в цифровых системах управления и так далее и для. выполнения усеченных и полного быстрых ортогональных преобразо- ваний цифровых сигналов в базисе функций Уолша над отсчетами дискретного сигнала.

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

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

Усеченные ортогональные преобразования последовательности обрабатываемых данных X {Х ; i определяются- следующим образом:

СП

о со со со

С где С

.

, )

.

(О

СП VN , W

с )

lC,3,-c,- вектор коэффициен- :

тов преобразования; - квадратные матрицы преобразования размерностью

г , С

N ш

(k,)

()

i ® (..--К i.tn - 1;

fEj, при k е ij, при k {

V Ч11 - ij

),

1;

О;

%25

единичная квадратная матрица порядка NJ

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

S - знак кронекеровского сложения.

Введение в рассмотрение усеченных преобразований в базисе функций Ви- ленкина (частным случаем которых является преобразование Уолша) бьто вызвано необходимостью учета различной физической природы обрабатываемых сигналов, их статических и спектральных свойств, класса задач обработки, т.е. адаптации ортогонального преобразования к классу обрабатываемых сигналов. Усеченные преобразования, определяемые выражением (1), позволяют, меняя значения параметров (,, заполнить широкий спектр возможных ортогональных преобразований между преобразованиями Уолша , (при всех k е О и Хаара (npH{ke j, 1, (k е . О) и тем самым подобрать необходимую степень рассредото- 35 ченности и локализации энергии базисных функций на различных временных участках.

; На фиг.1 изображена функциональная схема устройства для случая на фиг.2 - гриф полного БПУ для , закодированный ; на фиг.3-8 - графы усеченных дискретных ортогональных преобразований для , закодирован9 ные следующим образом: О, J,00, 01, 10, 11 соответственно; на фиг схема арифметического блока.

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

ного преобразования, блок 6 синхрони : зации, совокупность элементов, образующих блок настройки, выход 7 бло- г ка 6 синхронизации, регистры 8 и 9, счетчик 10, блоки И и 12 сравнения, элементы ИЛИ 13 и 14, элементы ) 15 и 16 задержки, четыре группы из f& Byx элементов И 17 и 18, 19 и 20, i 10 21 и 22, 23 и 24, информационные вход 25 и выход 26.

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

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

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

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

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

50 Работа устройства прошшюстрирова на дпя .

30

n-l-1

40

C tJC i X t

X x: I X X X X M

.+ + I 1 1 4. I

-f x x x x x

..,

,

X X x x X X + I I + + I I +

xxxxxxxx . «.- xxxxxxxx + I + I + I + I

I I I I I I I x x x x x x x x till

I I I I I I luuuuiaieiataii i i

, , , - xxxx + XI Kx

+ I I + I- I M +

tn M n «nX t-

.

«s/ rl H r4 Ч U

X X X X XXX I 1

I I I I I I I I I I I x x x x x X C x

4-rl

xxxxxxxx « V „ b ,. V V

XXXXXXXX

+ 1 I I + + I I X X X X X x x X

+ I + 1 I I + I

.W 1 1|«1л(А

IIIIIIIXXXXXXXX III

., , .

xxxxxxxx + I t + + 1 I +

xxxx xxx x

+ + 1 1 + + I I

X X X X X X X ; + 14-1 + 1 + 1

I I x x x x x x x x I I I I I I I I

Теперь рассмотрим работу блока .настройки - управляющей части устрой- ;ства.

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

(начиная с этой итерации число от- счетов становится равным N).

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

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

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

Примечание. Х- безразлично О или

Задача блока настройки - выработ- ;ка управляющих сигналов в соответ- |ствии с табл.2. При установке кодов в регистры 8 и 9 с выхода 7 поступают импульсы на счетчик 10. До тех пор, пока значение n-i мдадщих разрядов счетчика 10 не равно значению младших разрядов регистра 8, на вы-, ходе всех блоков 11 и 12 сравнения имеется нулевой сигнал. При совпаде- :Нии этих значений на выходе опреде-, ленного j-ro блока сравнения появляется единичный сигнал, который пропускает очередной импульс с выхода 7 на элемент ИЛИ через открытый элемент И. Затем этот импульс разделя- ;ется нужным образом элементами И 21- i24, управляемыми значениями (j-l)-ro

ii II

разряда счетчика 10, и задерживается на определенное число тактов в элементах 15 и 16 задержки.

5Описанное функционирование блока

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

-где вырабатываются, управляющие сигналы, относящиеся к работе устр ойст- ;, |ва на ,(п-К)-и итерации.

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

10

ортогонального преобразования для графа (фиг.8). В начальном состоянии на счетчике 10 находится код 11...1. При этом на регистре 8 записан код 10 (а может быть записан код 11), на регистре 9 код 01 (табл.2). Импульсы с выхода 7 заполняют счетчик 10, на первом такте его содержимое станрвкгся 00...0.. Блок 12 сравнения фиксирует равенство кодов на пятом такте, затем на седьмом, а блок 11 -сравнения - на пятом-восьмом тактах. Таким образом, на выходе элемента ИЛИ-13 импульсы появляются также на пятом-восьмом тактах. Так как элемент И 15 открыт единичным сигналом с первого разряда регистра 9, то на выходе элемента ИЛИ 14, кроме импульсов с элемента И 18, на пятом и седьмом тактах появляются еще импульсы с элемента И 20 на шестом и восьмом тактах. С учетом задержек на третий и первьш такт в элементах .15 и 16 задержки соответственно на выходе элемента И 21 импульсы появляются на восьмом и девятом тактах, / на выходе И 23 - на десятом и одиннадцатом тактах, на выходе И 22 - на шестом и восьмом тактах, на выходе И 24 - на седьмом и девятом тактах. Это означает, что в первом канале единичного преобразования выполнены только опер ации ,

шу-Адамару, содержащее п ( - размер преобразования) каналов единичного преобразования и блок синхронизации причем выход i-ro (i 1, n-1) канала единичного преобразования подключен к информационному входу (i-t-l)-ro канала единичного преобразования, выход п-го канала единичного преобразования являетс я. информационным выходом устройства, информационным входом которого является информационный вход первого ка- I нала единичного преобразования,

j-й (J 1,п) выход блока синхронизации подключен к тактовому входу j-ro канала единичного преобразования, причем j-й канал единичного преобразования содержит первый и второй элементы задержки и арифметический блок, тактовый вход которого является тактовым входом канала единичного преобразования, информационным входом которого является вход первого элемента задержки, выход которого подключен к входу второго элемента задержки и первому информационному входу арифметического блока, выход которого является выходом канала единичного преобразования, при этом в п-м канале единичного преобразования второй и третий информационные входы арифметического блока подключены соответственно к информа20

30

, , (табл. 1). Во вто- 35 ционному входу канала единичного пре- ром канале - только операции Х -+Х +образования и выходу второго элемен+Х-,+Х-,+Х, Xj+ ,- X g, X 5.- Xj+ Х,- та задержки, отличающееся

тем, что у с целью расширения функциональных возможностей за счет вы- 40

5- 6

X,

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

полнения как неусеченных , так и усеченных преобразований, в него введены счетчик, два регистра, п-1 блоков сравнения, группа элементов ИЛИ, группа элементов задержки и четыре

что соответствует графу на фиг.8, Формула изобретения

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

шу-Адамару, содержащее п ( - размер преобразования) каналов единичного преобразования и блок синхронизации причем выход i-ro (i 1, n-1) канала единичного преобразования подключен к информационному входу (i-t-l)-ro канала единичного преобразования, выход п-го канала единичного преобразования являетс я. информационным выходом устройства, информационным входом которого является информационный вход первого ка- I нала единичного преобразования,

j-й (J 1,п) выход блока синхронизации подключен к тактовому входу j-ro канала единичного преобразования, причем j-й канал единичного преобразования содержит первый и второй элементы задержки и арифметический блок, тактовый вход которого является тактовым входом канала единичного преобразования, информационным входом которого является вход первого элемента задержки, выход которого подключен к входу второго элемента задержки и первому информационному входу арифметического блока, выход которого является выходом канала единичного преобразования, при этом в п-м канале единичного преобразования второй и третий информационные входы арифметического блока подключены соответственно к информа0

0

тем, что у с целью расширения функциональных возможностей за счет вы- 40

полнения как неусеченных , так и усеченных преобразований, в него введены счетчик, два регистра, п-1 блоков сравнения, группа элементов ИЛИ группа элементов задержки и четыре

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

50

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

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

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

.1

Vzf

Фие. 2

ФигЛ

Фиг.

Фиг. 8

.З

Редактор М, Бланар

Составитель А. Баранов Техред Л. Олийнык к Заказ 5815/48

Тираж 6F8

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Корректор С. Шекмар

Подписное