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

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

Цель изобретения - повышение производительности.,; , ; .

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

Устройство для ортогонального преобразования цифровых сигналов по Уолшу- Адамару (см. фиг. 1) содержит генератор 1 тактовых импульсов, счетчик 2, первый 3 и второй 4 блок сдвиговых регистров, сумматор 5, вычитатель 6; блоки 7-22 элементов И, блоки 23, 24, 25, 26,. 27. 28 элементов ИЛИ, блоки 29, 30. 31, 32, 33, 34 элементов И, блоки 35, 36, 37, 38 элементов ИЛИ, выходы 39-41 счетчика.

На фиг.2 использованы обозначения, принятые на фиг. 1. На фиг.З символами xi, Х2..-Х8 обозначены входные отсчеты, символами У1,у2,...,у8 - выходные отсчеты Уолша- Адамара.

Рассмотрим назначение основных элементов устройства.

Генератор 1 тактовых импульсов служит для формирования последовательности импульсов синхронизирующих работу устройства.- . : . .... : - . . ...;

Счетчик 2 служит для задания признака четности такта, четности итерации, первой или второй половины итерации.

Базовая операция алгоритма преобразования заключается в вычислении по формулам:

An + Cn , An -Bn1 Dn1 где An и Вп - входные отсчеты для f-й итерации (I 1,2.,....N) при 1 1. An1 и Вп1 являются исходными отсчетами хп:

At1 xi, Bi - Х2. Аз1 хз, Вз1 Х4, Аз1 Xs; Вз Х6, А4 X, В4 Х8;

n - 2 j- число вычисленных коэффициентов преобразования;

Сп1 и On результаты базовой операции 1-й итерации, принимаемые как исходные данные Anl+1 и для базовых операций следующей итерации согласно используемому графу алгоритма преобразования Уолша-Адамара (фиг.З).

Таким образом для n 2N 8

Biw-C/-.Ai,+1 Ci ,

С4 ,

Аз1

1+1

А41

1+1

01 , Оз1.

После выполнения последней итерации I N

11 C1N- Y,2 C2N, Уз C3N, Y4 - C4N, Ys DiN, Y6 D2N, Y D3 , Y8 04 .

Первый З блок сдвиговых регистров служит для последовательного приема по первому, второму, третьему и четвертому информационным входам, хранения и последовательной выдачи в порядке поступления отсчетов An1, Bn1; Причем по первому входу последовательно принимаются отсчеты Ai, A2, по второму входу - Bi1, 82, по третьему - Аз, А4, по четвертому - Аз, В41. Второй 4 блок сдвиговых регистров служит для последовательного приема по пер- вому, второму, третьему, четвертому

информационному входам, хранения и последовательной выдачи в порядке поступления отсчетов С41, Dn Причем по первому входу последовательно принимаются отсчеты Ci, Сз, по второму Cz, C4 по третьему

- DI , Оз по четвертому - Da , D41. Запись отсчетов с одновременным сдвигом уже записанных осуществляется по заднему фронту тактового импульса при разрешающем значении сигнала на соответствующем управляющем входе блок сдвиговых регист.ров. ... .. -.- .. V .

Сумматор 5 служит для выполнения операции.

Вычитатель 5 служит для выполнения

операции.

Рассмотрим порядок функционирования устройства для ортогонального преобразования цифровых сигналов по Уолшу-Адамару для случая 2м 8. В исходном состоянии счетчик 2 обнулен, в первом 3 блоке сдвиговых регистров по первому входу занесены отсчеты At1. Аа1, по второму - Bi , 82 , по третьему - Аз , А41, по пятому

- Вз1, В4 , а второй 4 блок сдвиговых регистрое обнулен. (Цепи установки исходного состояния не показаны).

По нулевым сигналам на выходах 39,40, 41 счетчика 2 на первый и второй входы сумматора 5 и вычйтателя 6 поступают отсчеты Ai1 и Bi1, сформированные отсчеты ..Ci1 и Di в конце первого такта по заднему фронту первого тактового импульса через

блок 8 и блок 12 соответственно занесутся по первому и второму информационным входам во второй 1.4 блок сдвиговых регистров, одновременно отсчеты записанные по первому и второму входам в первый 3 блок сдвиговых регистров сдвинутся и окажутся записанными по новым адресам, при этом

на первом и втором, выходах блока будут

присутствовать отсчеты А21 и В21 соответственно.

Во втором такте на выходы сумматора 5 и вычитателя 6 в соответствии с управляющими сигналами (см. фиг.2) поступят отсчеты А21 и В21 соответственно. Результаты базовой операции занесутся по соответствующему тактовому импульсу; Са1 по второму, Da по четвертому входам во второй 4 блок сдвиговых регистров. Третья и четвертая базовые операции первой итерации реализуются аналогично. Отличие состоит лишь в том, что входные отсчеты поступают на входы сумматора 5 и вычитателя б с третьего и четвертого выходов первого 3 блока сдвиговых регистров. К концу первой итерации во втором 4 блоке сдвиговых регистров записаны: по первому входу последовательно отсчеты Ci1 и Сз1, по второму - Сг1,. С41, по третьему - Di1, Оз , по четвертому - Da1, D41. Вторая и третья итерации реализуются устройством аналогично первой, при этом лишь первый 3 и второй 4 блоки сдвиговых регистров меняются ролями: во второй итерации результаты базовых операций заносятся в первый блок сдвиговых регистров, в третьей - вновь во второй. В конце третьей итерации во втором 4 блоке сдвиговых регистров окажутся записанными выходные отсчеты - коэффициенты Уолша-Адамара. Устройство переходит в исходное состояние. Далее по соответствующим управляющим сигналам порядок функционирования устройства повторяется для очередной группы входных отсчетов.

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

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

оков сдвиговых регистров, первый и второй выходы первого блока сдвиговых регистров подключены соответственно к первым входам третьего и четвертого блоков элементов И, первый и второй выходы второго блока сдвиговых регистров подключены соответственно к первым входам пятого и шестого блоков элементов И, выход генератора тактовых импульсов подключен к синхровхо- дам первого и второго блоков сдвиговых

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

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

четвертого элементов И, выход (N-1)-ro разряда счетчика (где 2N - число вычисляемых коэффициентов преобразования) соединен с первым инверсным входом пятого, инверсными входом шестого элементов И, первыми входами с седьмого по десятый и вторыми входами с третьего по шестой блоков элементов И, выход N-ro разряда счетчика соединен с вторыми инверсными

0

0

5

входами третьего и пятого, прямыми входами первого и шестого, инверсным входом четвертого элементов И, первыми входами с одиннадцатого по шестнадцатый и вторыми входами первого и второго блоков эле5 ментов И, выход пятого элемента И соединен с первыми входами первого и второго элементов ИЛИ, вторые входы которых соединен с выходами соответственно первого и второго элементов И, выход первого

0 элемента ИЛИ соединен с первым входом разрешения первого блока сдвиговых регистров, второй вход разрешения которого соединен с выходом второго элемента ИЛИ, выход шестого элемента И соединен с пер5 выми входами третьего и четвертого элементов ИЛИ, вторые входыкоторых соединены с выходами соответственно третьего и четвертого элементов И, выходы третьего и четвертого элементов ИЛИ сое0 динены соответственно с первым и вторым входами разрешения второго блока сдвиговых регистров, третий и четвертый выходы которых соединены с вторыми входами соответственно девятого и десятого блоков

5 элементов И, выходы которых соединены с первыми входами соответственно второго и третьего блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно пятого и шестого блоков элементов И, третий и четвертый выходы первого блока сдвиговых регистров соединены с вторыми входами седьмого и восьмого блоков элементов И, выходы которых соединены с первыми входами четвертого и пятого блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно третьего и четвертого блоков элементов И, выходы четвертого и пятого блоков элементов ИЛИ соединены с вторыми входами соответственно одиннадцатого и тринадцатого блоков элементов И, выходы

которых соединены с первыми входами соответственно первого и шестого блоков элементов ИЛИ. вторые входы которых соединены с выходами соответственно двенадцатого и четырнадцатого блоков элементов И, вторые входы которых соединены с выходами соответственно второго и третьего блоков элементов ИЛИ, выход первого блока элементов ИЛИ соединен с первым информационным входом вычитателя, вто

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в аппаратуре обработки образцов, сжатия информации при передаче данных, для анализа и обработки звуковых и видеосигналов, для цифровой фильтрации и т.д. Целью изобретения является повышение производительности устройства за счет применения параллельного алгоритма реализации базовой операции преобразования Уолша-Адамара. Устройство для ортогонального преобразования цифровых сигналов по Уолшу-Адамару содержит генератор 1 тактовых импульсов, счетчик 2. первый 3 и второй 4 блоки сдвиговых регистров, сумматор 5. вычитатель 6. блоки 7. 8...22 элементов И. блоки 23. 24. 25. 26, 27, 28 элементов ИЛИ, блоки 20, 30, 31. 32. 33. 34 элементов И. блоки 35, 36, 37, 38 элементов ИЛИ. 3 ил.