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

(51)5 С 06 Р 15/332 ПИСАНИЕ ИЗОБРЕТЕНИ ВТОРСХОМУ СВИ ЕЛЬСТВ(2 (2 (4 (7 ом счет того, что в сос" входят коммутаторы сдвига, сумматор-выистры 5, 6 сдвига, лок 8 синхронизации, га, 5 ил. достигается з тав устройств 1,2, регистр читатель 4, р коммутатор 7, регистр 1 с дви СЛ 4 ь г ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ "ННТ СССР 1) 4452770/24-242) 07,07.886) 07.11.90,Бюл. У 411) Институт кибернетикиим. В.М.Глушкова(56) Авторское свидетельство СССРВ 951320, кл, С 06 У 15/332,1982.К.Лаг 1 а 8 аИа, 1.Е.НегсЬеу. АгсЬ1 есйиге оЮ йЬе газй 11 а 1 зЬ - Найащагй. апй тазг. Роигдег гапзГогшз,дхСЬ сЬапде йгапзЙег бечь.сез.1 п. Л,Е 1 есггопсз, 1981, чо 1.51,У 5, р.677, Ня.2. (прототип),(54) УСТРОЙСТВО -ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША-АДАМАРА(57) Изобретение относится к авт атике и вычислительной технике и может быть использовано для цифровойобработки сигналов на основе дискретных ортогональных преобразованийв базисе функций Уолша, для цифровойфильтрации, сжатия информации, дляцифрового спектрально-корреляционного анализа случайных процессов, втехнике связи и т.д. Цель изобретения - повышение быстродействия, ЦельИзобретение относится к автоматике н вычислительной технике и можетбыть использовано для цифровой обработки сигналов на основе дискретных5ортогональных преобразований в базисе функций Уолша, для цифровойфильтрации, сжатия информации, дляцифрового спектрально-корреляционного анализа случайных процессов, в 10технике связи и т.д.Цель изобретения - повышение быстродействия устройства за счет параллельного считывания из регистровсдвига данных, поступающих на входысумматора"вычитателя, что позволяетисключить однотактные задержки промежуточных данных.На Фиг представлена Функциональная схема устройства; на Фиг 2 - граФик быстрого преобразования УолшаАдамара; на фиг. 3 - схема блокасинхронизации; на фиг, 4 - схема .Формирователя импульсов; на фиг, 5временная диаграмма работы устройства для Н = 8 (Б2 ),Устройство содержит коммутаторы1 и 2, регистр 3 сдвига, сумматор-вычитатель 4, регистры 5 и б сдвига,коммутатор 7, блок 8 синхронизации,информационный вход 9, тактовыйвход 10, регистр 11 сдвига, вход 12запуска и вход 13 задания размерапреобразователя,БлОк 8 синхронизации (фитеЭ) содержит счетчик 14, Формирователь 15импульсов, счетчик 16, элементы И 17и 18, счетчик 19, элементы И 20 и21, элемент НЕ 22, элемент И 23,элемент НЕ 24, элемент И 25 элементНЕ 2 б, элементы И 27 и 28, элементыИЛИ 29 и 30.Формирователь 15 импульсов (Фиг,4)содержит четырехразрядный регистр 31сдвига, вычитающий счетчик Э 2 и элент И-НЕ 33.Устройство работает следующим об"разом.Последовательность Х(1), Х(2),Х(Б) отсчетов входного сигналас частотой тактовых импульсов черезпервый информационный вход коммутатора 1, управляемого с выхода 1 блока8 синхронизации сигналом 1 (фиг,5),поступает на вход коммутатора 2,кото 55рый управляется сигналом 2 с выхода2 блока 8 синхронизации. При этомкоммутатор 1 подключен к информацион"ному входу 9 устройства на время поступления отсчетов Х(1) - Х(Н) входного сигнала, В нечетные такты Ц1 - Н, где- номер тактового импульса) ,через первый выход коммутатора 2 значения нечетных отсчетов входного сигнала Х(1), Х(3)Х(Н- -1) заносятся в регистр 3, .а в четные такты ( = 2 - Б) значения четных отсчетов входного сигнала Х(2), Х(4)Х(Н) через второй выход коммутатора 2 заносятся в регистр 11. При этом регистры 3 и 11 управляются задними фронтами тактовых импульсов сигналов соответственно 5 и б (фиг.5) с выходов 5 и 6 блока 8 синхронизации. На протяжении Б/2 тактов,начиная с (Б+1)-го такта, выполняется первая итерация преобразования, При этом с тактовой частотой происходит считывание одновременно с регистров 3 и 11 сдвига данных, поступающих на входы сумматора-вычитателя 4, В каждом такте на выходах сумматоравычитателя 4 в соответствии с графом (Фиг,2) преобразования Формируются суммы и разности Х,(1/2) = Х(1 - 1) + хХ,(Н/2) + З(2) =- Х(1-1) - ХЦ), 1 = 2,4,6,Н,которые одновременно заносятся в регистры 5 и б (суммы заносятся в регистр 5, а разности - в регистр 6), При этом регистр 5 управляется тактовым сигналом Кт (фиг,5) с выхода 10 блока 8 синхронизации (эта связь на схема не показана), а регистр б - сигналом 4 (фиг,5) с выхода 4 блока 8 синхронизации. В.течение следующих Н/2 тактов, начиная с (3/2 Н + 1)-го такта происходит считывание данных (сумм) иэ регистра 5. При этом данные из регистра 5 через коммутаторы 7, и 2 в нечетные такты заносятся в регистр 3, а в четные такты - в регистр 1. Коммутатор 7 управляется - сигналом 3 (Фиг,5) с выхода 5 блока 8 синхронизации, После этого, начиная с (2 Я+1)-го такта, в течение следующих Н/2 тактов происходит аналогично считывание данных (разностей) из регистра 6 через коммутаторы 7, 1 и 2 в регистры 3 и 1, При этом в нечетные такты данные заносятся в регистр 3, а в четные такты - в регистр 11, 5 16После этого, начиная с (52 И+1)-го т акт а, происходит аналогично первой вторая итерация преобразования и т.д пока не выполнится и итераций преобразования, На последней и-й итерации преобразования в течение Б/2 тактов, начиная с (Зп"1)Б /2+1-го такта, на выходах сумматора-вычитйтеля 4 формируются коэффициенты Х(1)- " Х(Б) преобразования Уолша-Адамара, первая половина которых заносится в регистр 5, а вторая половина коэффициентов преобразования одновременно заносится в регистр 6. В течение Б/2 тактов, начиная с (Эп Б/2 + + 1)"го такта, происходит считывание с регистра 5 первой половины коэффициентов Х(1) - Х(Б/2) преобразования, а в течение следующих Б/2 тактов считывается с регистра 6 вторая половина коэффициентов Х(Б/2+1)-Х(Б) преобразования, которые выводятся на выход коммутатора 7. Прн этом первый коэффициент Х(1) преобразования выводится на выход коммутатора 7 на (ЗпБ/2 + 1)-м такте, а последний коэффициент Х(Б) преобразования - на (Зп+2) Б/2-м такте. На время считывания коэффициентов преобразования коммутатор 1 подключается к информацион.ному входу 9 устройства и одновремен-. но со считыванием коэффициентов происходит занесение в регистры 3 и 11 значений отсчетов, сигнала из следующей выборки.Блок 8 синхронизации работает следующим образом, Запуск блока 8 синхронизации производится потенциалом логического "0", который подается на вход 12 блока 8 синхронизации и запускает формирователь 15 импульсов. При этом на выходе формирователя 15 импульсов формируется отрицательный импульс сигнала управления 1 (фиг.5). По приходу тактовых импульсов Е, (фиг,5) на счетный вход 10 счетчика 14 на выходе 1 первого (младшего) разряда его формируется сигнал управления 2 (фиг,5), а на( выходе (и)-го разряда счетчика 14 формируется сигнал Ткоторый посту. пает на первый вход формирователя 15 импульсов и на счетные входы счетчиков 16 и 19, По приходу сигнала Т на выходе формирователя 15 импульсов формируется сигнал управления, который по переднему фронту сбрасывает счетчик 19 в нулевое состояние05254 5 1 О 15 20 2 30 35 40 а 5 50 55 Сигналы с выходов первого и второго разрядов счетчика 16 поступают на входы элемента И 17, на выходе которого формируется сигнал управления 4 (фиг,5), С помощью тактового сигнала Г и сигнала управления 4 кормитруется на выходе элемента И 18 сигнал управления Э, Сигналы с выходов первого и второго разрядов счетчика 19 поступают на входы элемента И 20, на выходе которого формируется сигнал, который поступает на первые входы элементов И 21 и 27 и через элемент НЕ 24 поступает на первый вход элемента И 25 С помощью прямого и инверсного сигналов управления 1,которые поступают на входь 1 элементов И 21, 23, 25, 27 и 28, прямого и инверсного сигналов управления 2, которые поступают на входы элементов И 21, 23, 27. и 28, а также с помощью тактового сигнала Г , который поступает на вход элемента И 25, на выходах элементов ИЛИ 29 и 30 Формируются сигналы управления соответственно 5 и 6.Формирователь 15 импульсов работает следующим образом. Перед запуском формирователя импульсов на информационных входах Р, - Р вычитаишего счетчика 32 устанавливается двоичный код числа ш(ш = Зп) тактов преобразования, Запуск формирователя 15 импульсов осуществляется потенциалом логического "0", который подается на вход 12 элемента И-НЕ 33, так как в исходном состоянии на выходе Р обратного переноса вычитаюшего счетчика 32 находится потенциал логической "1", который поступает на второй вход элемента И-НЕ 33, При этом на выходе элемента И-НЕ 33 устанавливается потенциал логическойкоторый поступает на управляющий вход Ч параллельного занесения регистра 31 сдвига. В исходном сос-, тоянии на информационных входах В 1 - П регистра 31 сдвига устанавливается код 1100 для формирования импульсов с длительностью 2 Т , которая получается по приходу третьего импульса сигнала Т , а на входе Ч 1 последовательного занесения регистра 31 сдвига постоянно присутствует высокий потенциал (логическая "1"),По приходу сигнала с периодом ТБ/2 из выхода (и)-го разряда счетчика 14 блока 8 синхронизациина счетный вход С параллельногозанесения регистра 31 сдвига по заднему фронту первого импульса сигналаТ на выходах 1 - 4 регистра 310сдвига устанавливается код 1100.Потенциаломлогического "О" с выходачетвертого (старшего) разряда регистра 31 сдвига в вычитающий счетчик 32параллельно заносится двоичный кодчисла ш, который установлен на информационных входах 0 - П , вычитающего счетчика 32, При этом на выходечетвертого разряда регистра 3 сдви"га устанавливается потенциал логического "0",Так как на управляющем входе 7регистра 31 сдвига устанавливаетсянизкий потенциал (логический "О") ина входе 71 постоянно присутствуетвысокий потенциал, то по приходу второго импульса сигнала Т на счетныйвход С регистра 31 сдвига (по заднему фронту импульса сигнала Т ) наего выходах происходит сдвиг вйраворанее занесенного параллельного кода1100. На выходах регистра 31 сдвигаполучается код 1110, т.е. состояниечетвертого разряда на выходе не изменилось и равно логическому "О",чтоне разрешает запускать вычитающийсчетчик 32. С приходом очередноготретьего импульса сигнала То по заднему фронту на выходе четвертогоразряда регистра 31 сдвига после очередного сдвига вправо устанавливает"ся потенциал логической "1",которыйзапускает вычитающий счетчик 32.Приэтом вычитающий счетчик 32 начинаетвычитать, После прихода (Зп)-гоимпульса сигнала Т на счетный входС регистра 31 сдвига на выходе Робратного переноса вычитающего счет. чика 32 формируется отрицательныйимпульс, который через элемент .И-НЕ 33 потенциалом логической "1",поступающим на вход регистра 31 сдвига, устанавливает на его выходах параллельный код 1100, При этом на выходе четвертого разряда регистра 31сдвига устанавливается низкий потен"циал,1 О 1 э 20 25 ЗО 35 4 О 45 Ю формула изобретенияУстройство для выполнения быстрого преобразования Уолша-Адамара,содержащее первый, второй и третий коммутаторы, первый, второй и третийрегистры, сумматор-вычитатель и блоксинхронизации, первый выход которогоподключен к управляющему входу первого коммутатора и тактовому входувторого регистра, выход которого подключен к первому информационномувходу второго коммутатора, выход которого является инФормационным выходом устройства и подключен к первомуинформационному входу первого коммутатора, второй информационный входкоторого является информационнымвходом устройства, тактовым входоми входом запуска которого являютсясоответственно тактовый вход и входзапуска блока синхронизации, второйи третий выходы которого подключенык управляющим входам соответственнотретьего и второго коммутаторов,выход первого регистра подключен кпервому входу сумматора-вычитателя,выход третьего регистра подключен квторому информационному входу второго коммутатора, о т л и ч а ю щ е е-.с я тем, что, с целью повышениябыстродействия, в него введен четвертый регистр, причем выход первого коммутатора подключен к инФормационному входу третьего коммутатора, первый и второй выходы которогоподключены к информационным входамсоответственно первого и четвертогорегистров, выход четвертого регистра подключен к второму входу сумматора-вычитателя, выходы суммы и разности которого подключены к информационным входам соответственно второго и третьего регистров, четвертый,пятый и шестой выходы блока синхронизации подключены к тактовым входам соответственно третьего, первого и четвертого регистров, а входзадания размера преобразования блокасинхронизации является входом зада"ния размера преобразования устройства,1605254 Фв ФЬЮФ а юч ъеею аЯфэФюэ Сю Ьз чу ФМЪВ ЕЕВФзъ- ФСЬмщф ът ъ ъв фч фафмфч Ффм меам Эъ фэйс)йф фъФФ ФФф и/т Рлч)Ф Сост авит ель А, Баранов едактор Н,Тупица Техред М,Дидык Корректор Т,Палий. е еей е еоизводственно"издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 аказ 3455НИИПИ Государст Тираж 569нного комитета по изобрет 3035, Москва, Ж, Раушс. Подписноеям и открытиям при ГКНТ СССнаб., д. 4/5