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

. СОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 И 9 51) 4 О 06 Р 15/33 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ,56) Авторское свидетельство СССРВ 744555, кл, Г 06 Р 15/332, 1980,Юаг 3.агапка В Негякеу 1.Е. АгсМ 1 есЫге оГ т,Ье 1 авт, Ма 1 вЬ-НаГашагапй 1 ав 1, Гопгег 1 гапв 1 огшв ю.ЛЬсЬаге 1 гапв 1.ег бетсев. - 1 п 1.Ю.ес 1 гоп 1.ся, 1981, . 51, В 5,Ре 677 Г 1 р, 2(54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗ ОВАНИЯ УО ЛБА-АЦАМАРА(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа случайных процессов, цифровой обработкисигналов, цифровой фильтрации, сжатияинформации и в технике связи, Цельизобретения - повышение быстродействия. Поставленная цель достигается засчет того, что в состав устройствавходят коммутаторы 1-4, регистры сдви-.га 5-8, коммутаторы 9-14, сумматорвычитатель 15, коммутаторы 16-19,регистры сдвига 20-23, коммутатор 24,блок синхронизации 25, входы устройства 26-29, 4 ил.Изобретение относится к антоматике и вычислительной технике и можетбыть использовано для спектрапьногои корреляционного анализа случайныхпроцессов, цифровдй обработки сигналов, цифровой фильтрации, сжатия информации, в технике связи и тд,Цель изобретения - повьппение бь 1 стродействия устройства за счет параллельного занесения промежуточных да 1"ных в регистры сдвига и оргавнзаии.".регистров сдвига путем их разбивкина четыре регистра сдвига в каждойгруппе, позволяющей исключить одно " ,ктактные задержки входных и промежуточных данных,На фиг. 1 представлена фун:;.циональная схема устройства быстрого преоб"разования Уолва-Адамара; на ф т,2 - 20схема блока синхронизации на фиг,Зсхема формирователя импульсов, нафиг. 4 - временная диаграмма заботыустройства для И=8Устройство (фиг, 1) содерж 1 дт коммутаторы 1-4, регистры 5-8 сдвига,коммутаторы 9-14 (две группы), сумматор-вычитатель 15, коммутаторы 1619, регистры 20-23 сдвига, коммутато,24, блок 25 синхронизации, входы 3 О26-29 устройства.Блок 25 синхронизации (фиг, 2) содержит счетчик 30, формирователь 31импульсов, элемент И 32, элементы НЕ33-36 элементы И 37-46, элем:.нты ИЛИ 3547 и 48, элементы И 49 и 50, влемен=ты ИЛИ 51, элемент НЕ 52, эле;";.ент ИБ,53, элементы И 54-58,. элемент ИЛИ 59.элемент И 60-62, элемент ИЛИ 63, элемент И 64, элементы ИЛИ 65-72, щФормирователь 31 импульсов (фиг,З)содержит .регистр 73 сдвига, вычитающий счетчик 74, элемент И-НЕ 5 и элмент НЕ 76,Устройство работает следуюцим об" разом.Последовательность хх, .,х; тсчеов ходного иала с частотой тактовых импульсов через коммутатор50 1, управляемый с второго выхо;а формирователя 31 импульсов блока 25 уп" равления сигналом "4" (Фиг. 4 , поступает на вход коммутатора ,", При этом коммутатор 1 включен наремя поступления отсчетов х -хд, в одного сигнала.В четные такты (,1=0 - (И, где- номер тактового импульса) черн выходы коммутаторов 2 и 3 значения первой полонины четных отсчетов входного сигнала хх х заносятся в регистр 5 сдвига, а значе-. ния второй половины четных отсчетов входного сигнала хрх 11Х к рез выход коммутатора 2 и выход коммутатора 3 в четные такты заносятся в регистр 6 сдвига. Аналогично в нечетные такты =1-(К) значения второй половины нечетных отсчетов Входного сигнала хх . ,х 1 ,через выход коммутатора 2 и выход коммутатора 4 заносятся в регистр 7 сдвига, а втооая половина нечетных отсчетоввходнОго сигнала хх,.в рх че рез выход коммутаторов 2 и 4 - в регистр 8 сдвига. При этом коммутатор 2 управляет/ ся сигналом с выхода первого младшего)разряда счетчика 30 блока 25 синхронизации, а коммутаторы 3 и 4 сигналом с выхода (и)-го разряда счетчика 30. Регистры 5-8 сдвига уп. равляются соответственно сигналами "7-10" (фиг. 4) с выходсв элементов ИЛИ 65-68 блока 25 синхронизации (фиг, 2),На протяжении И/2 тактов 1,от И до 3/2 И) выполняется первая итерация преобразования, При этом в четные такты, начиная с Б-го такта, происходит синхронно сдвиг информации в регистрах 5 и 6 сдвига, а в нечетные такты - сдвиг информации в регистрах 7 и 8 сдвига.В четные такты из регистров 5 и 6 сдвига на входь сумматора-вычитателя 15 через первые входы коммутаторов 9, 10, 13 и 14 поступают эначещщ четных отсчетов сигнала. В нечетные такты на Входы сумматора-Вычитателя 15 через входы коммутаторо и 12 и входы коммутаторов 13 и , ступают значения нечетных отс етов сигнала, которые содержатся В регистрах 7 и 8 сдвига, Коммутаторы 9-12 управляются сигналом "6" (фиг, 4) с выхода элемента ИЛИ 63 блока 25 син,;: ронизации, а коммутаторь 3 я сигналом с выхода первого (младиегс разряда счетчика 30 блока 25 синхрс низации. В каждом такте на выходе сумматора-Вычитателя 1 В соответст вии с графом преобразования формируются суммы х +х ч 1 л, 1 в -0,1,2,Ь/2 - 1ч л . 5 3первая ноловйна кот рых через :хс коммутаторов 16 и 18 з,.носится в регистр 20 сдвига, а вторая половина сумм через выходы коммутаторов 16 и 18 заносится в регистр 21 сдвига, Одновременно с этим в каждом такте на втором выходе сумматора-вычитятеля 15 Формируются разности х, -х),щ/, которые аналогично суммам через выходы коммутаторов 17 и 19 заносятся сначала в регистр 22 сдвига, а затем че рез выход коммутатора 19 в регистр 23 сдвига.При этом управление коммутаторами 16 и 17 осуществляется сигналом с выхода п-го (старшего) разряда счетчи ка 30 блока 25 синхронизации, а управление коммутаторами 18 и 19 - сигналом с выхода (п)-го разряда счетчика 30. Управление регистрами 20- 23 сдвига осуществляется соответст венно сигналами "11-14" (фиг, 4) с выходов элементов ИЛИ 69-72 блока 25 синхронизации.В течение следующих И/2 тактов (от 3/2 И до 2 И) выполняется вторая 25 итерация прео бра зов ания, При э том на входы сумматора-вычитателя 15 в четные такты (начиная с 3/2 И-го такта) через входы коймутаторов 9 и 10 и входы коммутаторов 13 и 14 поступа ют данные регистров 20 и 21 сдвига, а в нечетные такты через входы коммутаторов 11-14 на входы сумматора-вычитателя 15 поступают данные из регистров 22 и 23 сдвига. На вь 1 ход ком мутатора 16 в каждом такте выводятся суммы х (+х +И/2), где )=0-(И/ /2-1), сформированные на выходе сумматора-вычитателя 15, первая половина которых через выход коммутатора 3 40 заносится в регистр 5 сдвига, а вторая половина сумм через выход коммутатора 3 - в регистр 6 сдвига. Одновременно с этим в каждом такте на выход коммутатора 17 выводятся раэ ности х (-м+И/2), сформированныейЙа выходе сумматора-вычитателя 15, первая половина которых через выход коммутатора 4 заносится в регистр 7 сдвига, а вторая половина разностей через выход коммутатора 4 - в регистр 8 сдвига.В течение следующих И/2 тактов (от 2 И до 5/2 И) данные из регистров5-8 сдвига поступают на входы сумматора-вычитателя 15, а результаты (сум; ма и разность), полученные в каждом такте на выходах сумматора-внчитателя 15; заносятся в регистры 20-23 сдвига и т,д., пока не выполняется п итераций преобразования, На последнейи-й итерации преобразования в течениеИ/2 тактов, начиная с И+(и) И/2 -готакта, на выходах сумматора-вычитателя 15 Формируются коэффициенты х(0)х(И) преобразования Уолша-Адамара,которые в зависимости от числа и итераций преобразования попарно заносятсл в соответствующие регистры сдвига,В случае, если и - четное число, токоэффициенты преобразования заносятсяв регистры 5-8 сдвига, а если и - нечетное, то в регистры 20-23 сдвига,Таким образом, последняя пара коэффициентов х(И), х(И) преобразования в зависимости от четности числаи заносится соответственно в регистры 6 и 8 сдвига или в регистры 21 и23 сдвига на (И+пИ/2-1)-м такте.Последовательное считывание коэфФициентов преобразования из регистров сдвига производится через коммутаторы 9-14 и 24 во время занесениязначений отсчетов сигнала из последу-.ющей выборки. Считывание коэффициентов преобразования из регистров 5-8или 20-23 сдвига производится передними фронтами импульсов сигналов"7-10" или "11-14" (Фиг. 4),а занесение значений отсчетов сигнала врегистры 5-8 сдвига - задними фронтами импульсов этих сигналов, При этомпервый коэффициент х(0) преобразования получается на (И+пИ/2)-м тактена выходе коммутатора 24, управляемого сигналом "5" (Фиг. 4) с выхода элемента И 35 блока 25 синхронизации, а последний коэффициентх(И) преобразования - на (2 И+пИ/2-1)-м такте,Блок 25 синхронизации работает следующим образом,Запуск блока 25 управления производится потенциалом логического"0", который подается на вход 28 блока 25 синхронизации и запускает формирователь 31 импульсов. При этом на втором выходе формирователя 31. импульсов формируется положительюай им"пульс сигнала "4" (фиг. 4), который по переднему фронту сбрасывает счетчик 30 в нулевое состояние. По приходу тактовых импульсов Г (фиг. 4)на счетныи вход 27 счетчика 30 на .выходах первого (младшего), (и)-ии-го разрядов счетчика 30 Формируются5 14430 сигналы управления 1-3". По приходу сигнала Т с выхода (и)-го разряда счетчика 30 на первый вход формирова" теля 31 импульсов на втором выходе формирователя 31 импульсов Формируется сигнал "4" (Фиг, 4). Сигнал "4" через элемент И 32 Формирует сигнал "5" (Фиг. 4), Сигнал "6" Формируется в зависимости от четности числя и, п В случае, если и -. нечетное число, т. на первом выходе Формирователя 31, импульсов, на выходе О, первогс(мла,.- шего) разряда вычитающего счетчика 74 (Фиг. 3), находится потенциал логикческой 1, который разрешает прохождение через элемент И 62 сигнала "6" Формируемого на выходе элемента И 46 с помощью инверсных сигналов "4и 113 , В случае , если и - четное число , 20 то на первом выходе Фо рмирова те.тя 3 1 импульсов находится потенциал ло гиче ско го " 0", ко то рый через элемент НЕ 5 2 разрешает прохождение чер езэлемент И 64 сигнала " 6 "Формируемо. Б го с помощью сигнала " 4" , и си гнала6 " ( для случая , когда и - нечетное число) на выходе эл емента ИЛИ 5 3, При э том для четкого числа и на интервале считывания коэффициенто в прео бр;,.зов а- ЗО ния сигнал " 6 " имеет по тенциал ,г. огич еской " 1 " , который и ереключает коммутаторы 9- 1 2 для считывания ко зффициентов преобразования с регистров 5 -8сдвига , так к ак при четном и ко эффициен ты по ео браз о ванин находятся в р егистрах 5 -8 сдвига . Остальные сигналы7- 1 4 Формируются на выходах элемен товИЛИ 65- 72 с помощью прямых и инв е рсных сигналов "1-4".Формирователь 31 импульсов работает следующим образом.Перед запуском Формирователя:-,а инФормационных входах В, -0 вычитазщего счетчика 74 устанавливается двоичный код числа и итераций преобразования. Запуск Формирователя, 31 имп;гльсов осуществляется потенциалом логического "О", который подается на первый вход 28 элемента И-НЕ 75, та: как цб в исходном состоянии на выход Р обратного переноса вычитающего сче.чика74 находится потенциал логическойкоторый поступает на второи входэлемента И-НЕ 75. При этом на выходе элемента И-НЕ 75 устанавливается по. тенциал логической "1", который поступает на управляющий вход 7 параллельного занесения регистра 73 сдвига. Р исходном. состоянии на информационныхвходах О, -Э регистра 73 сдвига устанавливается код 100 для Формированияимпульсов длительностью 2 ТО, которая.получается по приходу третьего импульса сигнала Т, а на входе 7 последовательного занесения регистра 73 сдвига постоянно присутствует высокий потенциал (логическая "1"),По приходу сигнала с периодом Т =:.Ч/2 из выхода (и)-го разряда счет.ика 30 блока 25 синхронизации насчетный вход С параллельного занесения регистра 73 сдвига по заднемуфронту первого импульса сигнала Т няовыходах 1-4 регистра 73 сдвига устанавливается код 1100, Потенциалом ло-,гического "0" с выхода четвертого(старшего) разряда регистра 73 сдвигав вычитающий счетчик 74 параллельнозаносится двоичный код числа и итераций преобразования, который .установлен на инФормационных входах В -1).:ычитающего счетчика 74. Прн этом на-,1 ходе элемента НЕ 76 устянавливаетс 1 тенциал л огическойТак как на управляющем входе Ч:.;егистра 73 сдвига устанавлнвяетсянизкий потенциал (логической 0) ина выходе постоянно присутствует высокий потенциал, то по приходу второго импульса сигнала Т на счетныйовход С регистра 73 сдвига (по заднему Фронту импульса сигнала Т,) на.-.го выходах происходит сдвиг вправоранее занесенного параллельного кода1100. На выходах регистра 73 сдвигаполучается код 1110, т.е, состояниестаршего разряда ня выходе не изменилось и равно логическому "О", чтоне разрешает запускать вычитающий: четчик 74,С приходом очередног . ретье - оимпульса сигнала Т, по заднему .".роь. на выходе четвертого (старшего) разяда регистра 73 сдвига после очередного сдвига вправо устанавливается потенциал логической "1", который запускает вычитающий счетчик 74,.При этом счетчик 74 начинает вычи. ять, а на выходе элемента НЕ 76 ус.;анавливается потенциал логическо 103оПосле прихода и-го импульса сигнала Т на счетный вход С регистра2 .3 сдвига на выходе Р,. братного педеноса вычитающего счетчика 74 Ферми .жется отрицательный импульс которыйУстройство для быстрого преобразования Уолша-Адамара, содержащее шесть коммутаторов, первый, второй и трегий, регистры сдвига, блок синхронизации и сумматор-вычитатель, выход первого коммутатора подключен к информационному входу второго коммутатора, выходы суммы и разности сумма тора-нычитателя подключены к информационным входам соответственно третье" го и четвертого коммутаторов, первый выход четвертого коммутатора подключен к информационному входу пятого 25 .ммутатора, первый выход которого"дключен к информационному входу первого регистра сдвига, выход шестого коммутатора является информационным, выходом устройства, информацион- ЗО ным входом которого является информационный вход первого коммутатора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены четвертый, пятый, шестой, седьмой и восьмой регистры сдвига, с седьмого по пятнадцатый коыгутаторы, причем первый выход второГо коммутатора и второй вход третьего коммутатора подключены к информацион ному входу седьмого коммутатора, первый выход которого подключен к инфор" мационному входу второго регистра ;двига, выход которого подключен к .;-:рвому информационному входу восьмо го коммутатора, выход которого подключен к первому информационному входу девятого коммутатора, выход которого подключен к первому входу сумматор -вычитателя и первому информационному входу шестого коммутатора, первый вход третьего коммутатора подключен к информационному входу десятого коммутатора, первый и второй выходы которого подключены к информационным входам соответственно третьего и четвертого регистров сдвига, выэды которых подключены соотнеТстненно к второму информационному входу 50 через элемент И-НЕ 75 потенциалом логической "1", поступающим на вход Ч регистра 73 сдвига, устанавливает на его выходах параллельный код 1100, При этом низкий потенциал на выходе четвертого разряда регистра 73 сдвига устанавливает на выходе элемента НЕ 76 высокий потенциал,10Формула из о бре тения восьмого коммутатора и второму информационному нходу одиннадцатого коммутатора, выход которого подключен кпервому информационному входу двенадцатого коммутатора, выход котороГоподключен к второму входу сумматоравычитателя и второму информационномувходу шестого коммутатора, вторые выходы второго и четвертого коммутаторов подключены к информационному вхо-;ду тринадцатого коммутатора, первыйи второй выходы которого подключенык информационным входам соответственно пятого и шестого регистров сдвига,выходы которых подключены к первыминформационным входам соответственночетырнадцатого и пятнадцатого коммутаторов, выходы которых подключены квторым информационным входам соответственно девятого и двенадцатогокоммутаторов, второй выход седьмогокоммутатора подключен к информационному входу седьмого регистра сдвига,выход которого подключен к первомуинформационному входу одиннадцатогокоммутатора, выходы первого и восьмого регистров сдвига подключены к вторым информационным входам соответственно четырнадцатого и пятнадцатогокоммутаторов, второй выход пятогокоммутатора подключен к информационному входу восьмого регистра сдвига,первый выход блока синхронизации подключен к управляющим входам второго,девятого и двенадцатого коммутаторов,второй выход блока синхронизации под"ключен к управляющим входам пятого,седьмого, десятого и тринадцатогокоммутаторов, третий выход блока син,хронизации подключен к управляющимвходам третьего и четвертого коммутаторов, четвертый и пятый выходыблока синхронизации подключены к управляющим входам соответственно первого и шестого коммутаторов, шестойвыход блока синхронизации подключенк управляющим входам восьмого, одиннадцатого, четырнадцатого и пятнадцатого коммутаторов, седьмой, восьмой,девятый и десятый выходы блока синхронизации подключены к тактовым входам соответственно второго, седьмого,пятого и шестого регистров сднига,одиннадцатый, двенадцатый, тринадцатый и четырнадцатый выходы блока сии"хронизации подключены к тактовым входам соответственно третьего, четвертого,.первого и восьмого регистровсдвига, а тактовый вход, вход запуска и вход задания размера преобразования блока синхронизации являются соответственно тактовым входом, входом запуска и входом задания раэмерапреобразования устройства,1443002 Составитель А,БарановТехред И.Ходанич ктор В,Петраш Корректор В.Ромаиеик ка город, ул. Проектная, 4 6 Тир ВНИИПИ Госуд по делам 113035, Москвааж 704рственного комизобретений и оЖ, Раушская водственно-полиграфическое предприятие Подписноета СССРытийб д, 4/5