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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа случайньк процессов, цифровой обработки сигналов, цифровой фильтрации, сжатия информации и в технике связи. Цель изобретения - повышение быстродействия . Поставленная цель достигается за счет того, что в состав устройства входят коммутаторы 1-4, регистры сдвн-- га 5-8, коммутаторы 9-14, сумматорвычитатель 15, коммутаторы ,16-19, регистры сдвига 20-23, коммутатор 24, S блок синхронизации 25, входы устройства 26-29. 4 ил. (Л

СОЮЗ СОВЕТСНИХ . СОЦИАЛИСТИЧЕСНИХ РЕСПУБЛИК

А1 (!9! S0 и! (51) 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H АВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

PO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4259535/24-24 (22) 04.05.87 (46) 07.12,88. Бвл. ¹ 45 (71) Институт кибернетики им. В.М. Глушкова (72) Л,А .Гнатив, Я.Е,Визор, Г.Я.Ширмовский и M.A. Гнатив (53) 681.32(088,8)

,56) Авторское свидетельство СССР № 744555, кл, Г 06 F 15/332, 1980, Jar3 agama R,, Herskey I.Е. Architecture of t,he fast Malsh-Hafamar

and fast, Fourier transforms vith

charge transfer devices. — Int .

Electronics, 1981, v 51, ¹ 5, р, 677, t ig., 2. (54 ) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗ ОВАНИЯ УО ЛБА-АЦАМАРА (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для спектрального и корреляционного анализа случайных процессов, цифровой обработки сигналов, цифровой фильтрации, сжатия информации и в технике связи. Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят коммутаторы 1-4, регистры сдви-. га 5-8, коммутаторы 9-14, сумматорвычитатель 15, коммутаторы 16-19, регистры сдвига 20-23, коммутатор 24, Я блок синхронизации 25, входы устройства 26-29. 4 ил.

1443002

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

Цель изобретения — повышение быстродействия устройства за счет парал- лельного занесения промежуточных да1- ". ных в регистры сдвига и оргавнзаии. :". регистров сдвига путем их разбивки на четыре регистра сдвига в каждой группее) позволяющей исключить Одно-: i"ê тактные задержки входных и проме .— точных данных.

На фиг. 1 представлена фун:;.циональная схема устройства быстрого преобразования Уолша-Адамара; на фаг.,2 — 20 схема блока синхронизации„ на фиг.3схема формирователя импульсов; на фиг. 4 — временная диаграмма заботы устройства для N--8,.

Устройство (фиг. 1) содерж.!! Ком- 2 мутаторы 1-4, регистры 5-8 сдвига, коммутаторы 9-14 (две группы), сумматор-вычитатель 15, коммутаторы 1619, регистры 20-23 сдвига, ко1. мутят ;: .24, блок 25 синхронизации, входы 30

26-29 устройства.

Блок 25 синхронизации (фиг, 2) содержит счетчик 30, формироват::ьль 31 импульсов, элемент И 32, элем :.нты НЕ

33- 36,, элементы И 37-46, элем .нты ИЛИ 35

47 и 48, элементы И 49 и 50, влемен= ты ИЗИ 51, элемент HE 52, эле;";.ент K!11!

53, элементы И 54-58,. элемент ИЛИ II9. элемент И 60-62, элемен" ИЛИ 63, эле мент И 64, элементы ИЛИ 65-72, yg

Формирователь 31 импульсов (фиг.3) содержит .регистр 73 сдвига, вычитающий счетчик 74, элемент И-НЕ 5 и эл:-= мент НЕ 76, ДЧ

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

Последовательность х,,х,.. .,x!I отсчетов BxopHG I cHIHGJIB c !I< стотой тактовых импульсов через коммутатор

Я)

1, управляемый с второгo выхо";а Вор= мирователя 31 импульсов блока 25 уп: равления сигналом "4" (фиг, 4 . поступает на вход коммута-.îðà,"., При этом коммутатор 1 включен на ремя поступления отсчетов х -х, в>одного сигнала.

В четные такты (1=0 — (N-2, где — номер тактового импульса) черн:: выходы коммутаторов 2 и 3 значения первой полонины четных отсчетов входного сигнала х,,х,...,х„1 заносятся в регистр 5 сдвига, а значе-. ния второй половины четных отсчетов сигнала х .х„,...,хд че рез выход коммутатора 2 и выход коммутатора 3 в четные такты заносятся в регистр 6 сдвига. Аналогично в нечетные такты =1-(N-1) значения з орой половины нечетных отсчетов входного сигнала х,,„х . ..,х„1,через выход коммутатора 2 и выход коммутатора 4 заносятся в регистр 7 сдвига, а втооая половина нечетных отсчетов вхОднОго сигнала х1 г ух !i е ° в g х ц че ! И рез выход коммутаторов 2 и 4 — в реги с тр 8 сдвиг а, 1

При этом коммутатор 2 управляет/ ся сигналом с выхода первого младшего) разряда счетчика 30 блока 25 синхронизации, а коммутаторы 3 и 4 сигналом с выхода (и-1)-гc разряда счетчика 30. Регистры 5-8 сдвига уп равляются соответственно сигналами

"77-10" (фиг. 4) с выходсв элементо=ИЛИ 65-68 блока 25 синхронизации (фиг. 2).На протяжении N/2 тактов

1,от N,öo 3/2 N) выполняется первая итерация преобразования. При этом в четные такты, начиная с N-го такта, происходит синхронно сдвиг информации в регистрах 5 и 6 сдвига, а в нечетные такты — сдвиг информации в регистрах 7 и 8 сдвига.

В четные такты из регистров 5 и

6 сдвига на входы сумматора-вычитателя 15 через первые входы коммутаторов 9, 10, 13 и 14 поступают =.íà÷åьжя четных отсчетов сигнала. 8 нечетные такты на входы сумматора-вычитателя 15 через входы коммутаторс::- 11 I»

12 и входы коммутаторов !3 и !-: ступают значения нечетных Ото eTQB сигнала, которые содержатся ь ре истрах 7 и 8 сдвига, Коммутаторы 9-12 управляются сигналом "6" (фиг. 4) с выхода элемента ИЛИ 63 блока 25 син,-; ронизации, а коммутаторы .3 я сигналом с выхода первого (младл;ег;. разряда счетчика 30 блока 5 синхрс низации. В каждом ";àê" å на выходе сумматора-вычитателя 15 - ссответст . вии с графом преобразования формируются суммы х +х „ ()=0,1, 2....,N/2 — 1 i л, . 6 Ю первая ноловйна кот рых через . Кс коммутаторов 16 и 18 з носится в ре144 3002 гистр 20 сдвига, а вторая половина сумм через выходы коммутаторов 16 и

18 заносится н регистр 21 сдвига. Одновременно с этим в каждом такте на втором выходе сумматора-вычитятеля

15 формируются разности х -х;,„, которые аналогично суммам через выходы коммутаторов 17 и 19 заносятся сначала в регистр 22 сдвига, а затем че- 10 рез выход коммутатора 19 в регистр 23 сдвига.

При этом управление коммутаторами

16 и 17 осуществляется сигналом с выхода n-ro (старшего) разряда счетчи- 15 ка 30 блока 25 синхронизации, а управление коммутаторами 18 и 19 — сигналом с выхода (n-1)-ro разряда счетчика 30. Управление регистрами 2023 сдвига осуществляется соотнетст- 20 венно сигналами "11-14" (фиг. 4) с выходов элементов ИЛИ 69-72 блока 25 синхронизации.

В течение следующих N/2 тактов (от 3/2 N до 2 И) выполняется вторая 25 итерация прео бра зов ания. При э том на входы сумматора-вычитателя 15 н четные такты (начиная с 3/2 И-го такта). через входы коймутаторон 9 и 10 и входы коммутаторов 13 и 14 поступа- 30 ют данные регистров 20 и 21 сдвига, а в нечетные такты через входы коммутаторов 11-14 на входы сумматора-нычитателя 15 поступают данные из регистров 22 и 23 сдвига. На вь1ход ком- 3 мутатора 16 в каждом такте выводятся суммы x<() )+x ()+N/2), где =0-(N/

/2-1), сформированные на выходе сумматора-вычитателя 15, первая половина которых через выход коммутатора 3 40 заносится в регистр 5 сдвига, а вторая половина сумм через выход коммутатора 3 — в регистр 6 сдвига. Одновременно с этим в каждом такте на выход коммутатора 17 выводятся раэ- 45 ности х (g)-м ()+N/2), сформированные

I и

Йа выходе сумматора-вычитателя 15, первая половина которых через выход коммутатора 4 заносится в регистр 7. сдвига, а вторая половина разностей через выход коммутатора 4 — в регистр

8 сдвига.

В течение следующих И/2 тактов (от 2 N до 5/2 И) данные из регистров

5-8 сдвига поступают на входы сумматора-вычитателя 15, а результаты (сум-. ма и разность), полученные в каждом такте на выходах сумматора-внчитателя

15; заносятся в регистры 20-23 сдвига и т.д., пока Ie выполняется и итераций преобразования. На последней и-й итерации преобразования в течение

И/2 тактов, начиная с И+(и-1) N/2 -го такта, на выходах сумматора-нычитателя 15 формируются коэффициенты х(0)х(И-1) преобразования Уолша-Адамара, которые н зависимости от числа и итераций преобразования попарно заносятсл в nîòâåòñòíóþùèå регистры сдвига

В случае, если и — четное число, то

Koэффициенты преобразования заносятся в регистры 5-8 сдвига, а если n — - нечетное, то н регистры 20-23 сдвига, Таким образом, последняя пара коэффициентов x(N-2), x(N-1) преобразования н зависимости от четности числа и заносится соответственно в регистры 6 и 8 сдвига или в регистры 21 и

23 сдвига íà (N+nN/2-l)-м такте.

Последовательное считывание коэффициентов преобразования из регистров сдвига производится через коммутаторы 9-14 и 24 но время занесения значений отсчетов сигнала из последующей выборки. Считывание коэффициентов преобразования из регистров 5-8 или 20-23 сдвига производится передними фронтами импульсов сигналов

"7-10" или "11-14" (фиг. 4),а занесение значений отсчетов сигнала в регистры 5-8 сдвига — задними фронтами импульсов этих сигналов. При этом первый коэффициент х(0) преобразования получается íà (N+nN/2)-м такте на выходе коммутатора 24, управляемого сигналом "5" (фиг. 4) с выхода элемента И 35 блока 25 синхронизации, а последний коэффициент х(И-1) преобразования — íà (2N+nN/

12-1)-м такте.

Блок 25 синхронизации работает следующим образом.

Запуск блока 25 управления производится потенциалом логического

"0", который подается на вход 28 блока 25 синхронизации и запускает формирователь 31 импульсов. При этом на втором выходе формирователя 31. импульсов формируется положительюай им" пульс сигнала "4" (фиг. 4), который по переднему фронту сбрасывает счет-. чик 30 в нулевое состояние. По приходу тактовых импульсов f (фиг. 4) на счетный вход 27 счетчика 30 на . выходах первого (младшего), (n-1)-и и-го разрядов счетчика 30 формируются

5 14430 сигналы управления 1-3". По приходу сигнала Т„с выхода (n-I )-го разряда счетчика 30 на первый вход формирова" теля 31 импульсов на втором выходе

Ф; формирователя 31 импульсов формируется сигнал "4" (фиг. 4). Сигнал " 4" через элемент И 32 формирует сигнал

"5" (фиг. 4). Сигнал "6" формируется

s зависимости от четности числя n, q

В случае, если п -. нечетное число, т-. на первом выходе формирователя 31 импульсов, на выходе D, первогс (мла,.meго) разряда вычитающего счетчика 74 (фиг. 3), находится потенциал логик ческой I, который разрешает прохождение через элемент И 62 сигналя "6" „ формируемого на выходе элемента И 46 с помощью инверсных сигналов "4 и

I l I I

3, В случае, если и — четное число, 20 то на первом выходе формировате. тя 31 импульсов находится потенциал ло -ического "0", который через элам-гнт

HE 52 разрешает прохождение через элемент И 64 сигнала "6"q формируемо- .5 го с помощью сигнала "4", и сигнала

6" (для случая, когда n — нечетное число) на выходе элемента ИЛИ 53. При

=-том для четкого числа и на интервале считывания коэффициентов преобрязова- З0 ния сигнал "6" имеет потенциал .г.огической "1", который переключает коммутаторы 9-12 для считывания коэффициентов преобразования с регистров 5-8 сдвига, так как при четном и коэффициенты поеобразования находятся в perzexpaz 5-8 сдвига. Остальные сигналы

7-14 формируются на выходах элементов

ИЛИ 65-72 с помощью прямых и инверсных сигналов "1-4".

Формирователь 31 импульсов работает следующим образом.

Перед запуском формирователя 1-.а информационных входах D, -D„âû÷èòà:çùåro счетчика 74 устанавливается двоичный код числа и итераций преобразования. Запуск формирователя, 31 имп;льсов осуществляется потенциалом логического "0", который подается на первый вход 28 элемента И-НЕ 75, тя : как цб в исходном состоянии на выход Р обратного переноса вычитающего сче.чика

74 находится потенциал логической

1 KOTopbIA поступает на второй вход элемента И-НЕ 75. При этом на выходе элемента И-НЕ 75 устанавливается по. тенциал логической "I" который поступает на управляющий вход V< параллель:"-ого занесения регистра 73 сдвига. Р исходном. состоянии на информационных входах D, -D„ ðåãèñòðà 73 сдвига устанавливается код 1100 для формирования импульсов длительностью 2ТО, которая. получается по приходу третьего импульса сигнала Т, а на входе V последовательного занесения регистра 73 сдвига постоянно присутствует высокий потенциал (логическая "1").

По приходу сигнала с периодом Т =

-Ч/2 из выхода (n-1)-ro разряда счет .нка 30 блока 25 синхронизации ня .четный вход С< параллельного занесения регистра 73 сдвига по заднему фронту первого импульса сигнала Т на о выходах 1-4 регистра 73 сдвига устанавливается код 1100, Потенциалом ло-, гическо го "0" с выхода четверто го (старшего) разряда регистра 73 сдвига в вычитающий счетчик 74 параллельно заносится двоичный код числа п итераций преобразования, который -установлен на информационных входах D --D

1 .-ычитающего счетчика 74. Прн этом на .-,1ходе элемента НЕ 76 уст: Hявливяетс1тенциал л гической

Так как на управляющем входе V

:;егистра 73 сдвига устанавлнвается низкий потенциал (логической "0 ) и ня выходе постоянно присутствуе- высокий потенциал, -о по приходу второго импульса сигнала Т ня счетный о вход С регистра .73 сдвига (по заднему фронту импульса сигнала Т, ) на .-."o выходах происходит сдвиг вправо ранее занесенного параллельного кода

1100. На выходах регистра 73 сдвига

;получается код 1110, т.е, состояние старшего разряда ня выходе не изменилось и равно логическому "0", что не разрешает запускать вычитающий

:.четчик 74.

С приходом очередног третье -.о импульса сигналя Т, по заднему ".роь.; ня выходе четвертого (старшего) ряз.:яда регистра 73 сдвига после очередного сдвига вправо устанавливается потенциал логической "1, который

=-апускает вычитающий счетчик 74,. ри этом счетчик 74 начинает вычи..ять, а ня выходе элемента HE 76 ус,-анавливяется потенциал логическоtt tt о о

После прихода и-го имч,:льса сигналя Т на счетный вход С регистра . 3 сдвига на выходе Р. :бгятно;:.,.те:эеноса вычитающего счетчика 74 фсрми7ется отрицятельньФ импульс,,который

1443002

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

".ммутатора, первый выход которого эдключен к информационному входу

::-ервого регистра сдвига, выход шестос коммутатора является информационным, выходом устройства, информацион- ЗО ным входом которого является информационный вход первого коммутатора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены четвертый, пятый, шестой, седьмой и восьмой регистры сдвига, с седьмого по пятнадцатый кожгутаторы, причем первый выход второго коммутатора и второй вход третьего коммутатора подключены к информацион- 40 ному входу седьмого коммутатора, первый выход которого подключен к инфор" мационному входу второго регистра

:двига, выход которого подключен к

;-:рвому информационному входу восьмо- 45 го коммутатора, выход которого подключен к первому информационному входу девятого коммутатора, выход которого подключен к первому входу сумматора-вычитателя и первому информационному входу шестого коммутатора, гервый вход третьего коммутатора подключен к информационному входу десятого коммутатора, первый и второй выходы которогс подключены к информационным входам соответственно третьего и четвертого регистров сдвига, вы. ;;,цы которых подключены соответственно к второму информационному входу

50 через элемент И-HF. 75 потенциалом логической "1", поступакщим на вход

V регистра 73 сдвига, устанавливает на его выходах параллельный код

1100. При этом низкий потенциал на выходе четвертого разряда регистра

73 сдвига устанавливает на выходе элемента HF. 76 высокий потенциал.

Формула изобретения восьмого коммутатора и второму информационному входу одиннадцатого коммутатора, выход которого подключен к первому информационному входу двенад— цатого коммутатора, выход которого подключен к второму входу сумматоравычитателя и второму информационному входу а==cToro коммутатора, вторые выходы pToT;ohio и четвертого коммутаторов подключены к информационному вхо-; ду тринадцатого коммутатора, первый и второй выходы которого подключены к информационным входам соответственно пятого и шестого регистров сдвига, выходы которых подключены к первым информационным входам соответственно четырнадцатого и пятнадцатого коммутаторов, выходы которых подключены к вторым информационным входам сооТветственно девятого и двенадцатого коммутаторов, второй выход седьмого коммутатора подключен к информационному входу седьмого регистра сдвига, выход которого подключен к первому информационному входу одиннадцатого коммутатора, выходы первого и восьмого регистров сдвига подключены к вторым информационным входам соответственно четырнадцатого и пятнадцатого коммутаторов, второй выход пятого коммутатора подключен к информационному входу восьмого регистра сдвига, первый выход блока синхронизации подключен к управляющим входам второго, девятого и двенадцатого коммутаторов, второй выход блока синхронизации подключен к управляющим входам пятого, седьмого, десятого и тринадцатого коммутаторов, третий выход блока син,.хронизации подключен к управляющим входам третьего и четвертого коммутаторов, четвертый и пятый выходы

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

1443002

1О сдвига, а тактовый вход, вход запуска и вход задания размера преобразования блока синхронизации являются соответственно тактовым входом, входом запуска и входом задания раэмера преобразования устройства.

1443002

Редактор В.Петраш

Заказ 6386/46

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

У71

0

7

1 вд

Д 1

Юg

1 Я

1

Составитель А,Баранов

Техред И.Ходанич Корректор В.Романенко

Тираж 704 Подписное

ВПИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5