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

СОК) 3 СОВЕ Г СКИХ сг 1 иАпис тичс ских РЕПЦУПЛИк БО 18 6 снс 6 5/332 ГОСУДАРСТВЕН 1 ВЕДОМСТВО Сг (ГОСПАТЕНТ СС ПАТЕНТНОЕ САНИЕ ИЗОБРЕТЕНИЯ ВТОРСКОМУ СТВУ Е 18бюро лектроп оНестеренко. К,Ю ин. В.С,Харчен Воельст 5/33 ельст 15/3 ЛЯ О ИЯ ЦИ ДАМ оситс ике и НО- ИГис(54) УСТРОЙСТВО ДГО ПРЕОБРАЗОВАННАЛОВ ПО УОЛШУ - А(57) Изобретение отнвычислительной техн о СССР, 1980.о СССР2. 1984.ТОГОНАЛЬФРОВЫХ САРУк автоматикможет быть пользовано в аппаратуре обработки образцов. сжатия информации при передаче данных, для анализа и обработки звуковых и видеосигналов, для цифровой фильтрации и т.д. Целью изобретения является повышение производительности устройства за счет применения параллельного алгоритма реализации базовой операции преобразования Уолша-Адамара, Устройство для ортогонального преобразования цифровых сигналов по Уолшу - Адамару содержит генератор 1 тактовых импульсов, счетчик 2, первый 3 и второй 4 блоки сдвиговых регистров. сумматор 5, вычитатель 6, блоки 7, 822 элементов И, блоки 23, 24, 25, 26, 27, 28 элементов ИЛИ, блоки 20, 30, 31. 32. 33. 34 элементов И, блоки 35, 36, 37, 38 элементов ИЛИ, 3 ил.Изобретение относится к автоматике ивычислительной технике и может быть использовано в аппаратуре обработки образов, сжатия информации при передачеданных, для анализа и обработки звуковыхи видеосигналов, для цифровой фильтрациии т.д.Кель изобретения - повышение производительности,На фиг,1 изображена функциональнаясхема устройства для ортогонального преобразования цифровых сигналов по Уолшу-.Адамару; на фиг.2 - временные диаграммыфункционирования устройства; на фиг;3 -граф-схема алгоритма быстрого преобразования Уолша-Адамара,Устройство для ортогонального преобразования цифровых сигналов по УолшуАдамару (см, фиг.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. На фиг.З символами х 1,х 2х 8 обоэначенц входные отсчеты, символами у 1,у 2у 8 - выходные отсчеты Уолша. Адамара.Рассмотрим назначение основных элементов устройства.Генератор 1 тактовых импульсов служитдля формирования последовательности им.пульсов синхронизирующих работу устройства.Счетчик 2 служит для задания признакачетности такта, четности итерации, первойили второй половины итерации,Базовая операция алгоритма йреобразования заключается в вычислении по формулам:Ар + Вл г Со Ап - Вр = Оп1 , вгде Аи В - входные отсчеты для 1-й ите.рации ( = 1,2,й) при= 1, А и Вп1 1являются исходными отсчетами х,А =х 1,8 =х 2,А =хз,В 2 =х 4,АЗх 5: В = х 8; Аа - Х 7, Ва = Х 8.и = 2 - число вычисленных коэффициентовпреобразования;С и 0 результаты базовой операции1-й итераций, принимаемые как исходныеданные А+ и В 1 для базовых операцийследующей итерации согласно используемому графу алгоритма преобразования Уолша-Адамара (фиг.З).Таким образом для и = 2 = 8В 2 = С 4, А 2 = Сз В 4 = 04 , А 4 = Оз.После выполнения последней итерации1=ИУ 1 = С 1, У 2 = С 2, У 3 = Сз, У = С 4, У 5= 01, У 6=02, У 7=03, У 8=04Первый 3 блок сдвиговых регистров служит для последовательного приема по первому, второму, третьему и четвертому информационным входам, хранения и последовательной выдачи в порядке поступления отсчетов Ап, Вп Причем по первомувходу последовательно принимаются отсчеты А 1, А 2, по второму входу - В 1, В 2, ПОтретьему - Аз, Аа, по четвертому - Аз, Ва,Второй 4 блок сдвиговых регистров служит для последовательного приема по пер, вому, второму, третьему, четвертому 20 информационному входам, хранения и последовательной выдачи в порядке поступления отсчетов С 4, О, Причем по первомувходу последовательно принимаются отсчеты С 1, С, по второму - С 2, С 4 по третьему25 - 01, Оз по четвертому - 02, 04, Записьотсчетов с одновременным сдвигом уже записанных осуществляется по заднему фронту тактового импульса при разрешающем значении сигнала на соответствующем уп равляющем входе блок сдвиговых регистров.Сумматор 5 служит для выполнения операции,Вычитатель 5 служит для выполнения 35 операции.Рассмотрим порядок функционирования устройства для ортогонального преобразования цифровых сигналов по Уолшу-Адамару для случая 2" = 8. В исход ном состоянии счетчик 2 обнулен, в первом3 блоке сдвиговых. регистров по первому вход занесены отсчеты А 1 А 2, по второму - В 1, В 2 1 ЙО третьему - Аз, А 4, по пятому1 1- Вз, В 4, а второй 4 блок сдвиговцх регистров обнулен. (Цепи усановки исходного состояния не показаны). По нулевым сигналам на выходах 39, 40,41 счетчика 2 на первый и второй входы сумматора 5 и вычитателя 6 поступают от. счеты А 11 и В 1, сформированные отсчетыС 11 и 01 в конце первого такта по заднему фронту первого тактового импульса через 55 блок 8 и блок 12 соответственно занесутсяпо первому и второму информационным входам во второй 14 блок сдвиговых регистров, одновременно отсчеты записанные по первому и второму входам в первый 3 блок сдвиговых регистров сдвинутся и окажутся записанными по новым адресам, при этом на первом и втором, выходах блока будут5 10 15 20 25 30 40 45 50 55 присутствоватьг и Вг соответственно.Во втором такте на выходы сумматора 5 и вычитателя 6 в соответствии с управляющими сигналами (см, фиг.2) поступят отсчеты Аг и Вг соответственно. Результаты1 1базовой операции занесутся по соответствующему тактовому импульсу; Сг по второ 1му, Ог - по четвертому входам во второй 41блок сдвиговых регистров. Третья и четвертая базовые операции первой итерации реализуются аналогично, Отличие состоит лишь в том, что входные отсчеты поступают на входы сумматора 5 и вычитателя 6 с третьего и четвертого выходов первого 3 блока сдвиговых регистров, К концу первой итерации во втором 4 блоке сдвиговых регистров записаны: по первому входу последовательно отсчеты С 1 и Сз по второму - Сг,1С 4, по третьему - 01, Оз, по четвертому -1: Ог, О 4 . Вторая и третья итерации реализуются устройством аналогично первой, при этом лишь первый 3 и второй 4 блоки сдвиговых регистров меняются ролями: во второй итерации результаты базовых операций заносятся в первый блок сдвиговых регистров, в третьей - вновь во второй, В конце третьей итерации во втором 4 блоке сдвиговых регистров окажутся записанными выходные отсчеты - коэффициенты Уолша - Адамара. Устройство переходит в исходное состояние. Далее по соответствующим управляющим сигналам порядок функционирования устройства повторяется для очередной группы входных отсчетов.Формула изобретения Устройство для ортогонального преобразования цифровых сигналов по УолшуАдамару, содержащее шесть блоков элементов И, три блока элементов ИЛИ, первый и второй блоки сдвиговых регистров, генератор тактовых импульсов; счетчик, сумматор, шесть элементов. И, причем выход первого блока элементов. ИЛИ подключен к первому информационному входу сумматора, выход сумматора подключен к первым входам первого и второго блоков элементов И, выходы которых подключены к первым и вторым информационным входам соответственно первого и.второго блоков сдвиговых регистров, первый и второй выходы первого блока сдвиговых регистров подключены соответственно к . первым входам третьего и четвертого блоков элементов И, первый и второй выходы второго блока сдвиговых регистров подключены соответственно к первым входам пятого и шестого блоков элементов И, выход генератора тактовых импульсов подключен к синхровходам первого и второго блоков сдвиговых регистров и к счетному входу счетчика, о тличающее с я тем, что, с целью повышения производительности, оно дополнительно содержит десять блоков элементов И, три блока элементов ИЛИ, вычитатель и два элемента ИЛИ, причем выход первого разряда счетчика соединен с инверсным входом первого, первым входом второго, первым инверсным входом третьего и прямым входом четвертого элементов И, выход(й - 1)-го разряда счетчика где 2 - число вычисляемыхйкоэффициентов преобразования) соединен с первым инверсным входом пятого, инверсными входом шестого элементов И, первыми входами с седьмого по десятый и вторыми входами с третьего по шестой блоков элементов И, выход Й-го разряда счетчика соединен с вторыми инверсными входами третьего и пятого, прямыми входа-. ми первого и шестого, инверсным входом четвертого элементов И, первыми входами с одиннадцатого по шестнадцатый и вторыми входами первого и второго блоков элементов И, выход пятого элемента И соединен с первыми входами первого и второго элементов ИЛИ, вторые входы которых соединен с выходами соответственно первого и второго элементов И, выход первого элемента ИЛИ соединен с первым входом разрешения первого блока сдвиговых регистров, второй вход разрешения кото рого соединен с выходом второго элемента ИЛИ, выход шестого элемента И соединен с пер 35 выми входами третьего и четвертого элементов ИЛИ; вторые входыкоторых соединены с выходами соответственно третьего и четвертога элементов И, выходы третьего и четвертого элементов ИЛИ соединены соответственно с первым и вторым входами разрешения второго блока сдвиговых регистров, третий и четвертый выходы коърых соединены с вторыми входами соответственно девятого и десятого .блоков элементов И, выходы которых соединены с первыми входами соответственно второго и третьего блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно пятого и шестого блоков элементов И, третий и четвертый выходы первого блока сдвиговых регистров соединены с вторыми входами седьмого и восьмого блоков элементов И, выходы которых соединены с первыми входами четвертого и пятого блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно третьего и четвертого блоков элементов И, выходы четвертого и пятого блоков элементов ИЛИ соединены с вторыми входами соответственно одиннадцатого и тринадцатого блоков элементов И, выходы1815651 ца йа 2 У 7 Х 7 ХВ Фига Составитель Ю. Ланц Техред М.Моргентал Корректор Н. Ревска едактор Тираж Подписноесударственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва. Ж, Раушская наб., 4/5 Заказ 1637 ВНИИПИ роизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина. 1 О которых соединены с первыми входами соответственно первого и шестого блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно двенадцатого и четырнадцатого блоков элементов И, вторые входы которых соединены с выходами соответственно второго и третьего блоков элементов ИЛИ, выход первого блока элементов ИЛИ соединен с первым информационным входом вычитателя, второй информационный вход которого соединен с выходом шестого блока элементов ИЛИ и вторым информационным входом сумматора, выход вычитателя соединен с 5 вторыми входами пятнадцатого и шестнадцатого блоков элементов И, выходы которых соединены с третьими и четвертыми информационными входами соответственно первого и второго блоков сдвиговых регистров, 10 Ж 97 У 8