Устройство для быстрого преобразования Уолша-Адамара Советский патент 1988 года по МПК G06F17/14 

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

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

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

Устройство (фиг 1 ) содерж гт ком- мутаторы -4, регистры 5-8 сдчига, коммутаторы 9-14 (две группы), cyt-i матор-вьтитатель 15 коммутаторы 6- 19, регистры 20-23 сдвига, копмутато .24, блок 25 синхронизации, вх(ды

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

Блок 25 синхронизации (фиг. 2) содержит счетчкк 30, .формирователь 31 импульсов J элемент И 32, элемсшты НЕ ЗЗ-Зб, элементы И 37-46 элементы ИЖ 47 и 48э элементы И 49 и 50, элементы ИЖ 51, элемент НЕ 52 элемент ИЛ 53j элементы И 54--585, элемент ИЛИ 59 элемент И 60-6 2, элемент Й.ПИ бЗр эле меНт И 64; элементы ИЛИ 65-72,

Формирователь 31 импульсов (фиГоЗ содержит регистр 73 сдвига j вь читаю- щнй счетчик 74,, элемент И-НЕ 75 и эл мент НЕ 76,

Устройство работает следз/тор гм образом,

Последовательность Хд,,,, -sXtj. отс:четов входного сигнала с ч;4стотой тактовых импульсов через коммутатор I, управляемый с второго вьгхо1:;а бюр- М1 рователя 31 импульсов блока 25 управления сигналом 4 (фиг. 4;. поступает на вход коммутатора .:, При этом коммутатор 1 включен на гремя поступления отсчетов Хд- х в аэдкого сигнала,

В четные такты ( - (N-2:3 где ,j - номер тактового импульса) чере

вькоды коммутаторов 2 и 3 значения первой половины четных отсчетов

входного сигнала х

о л

В/4

заносятся в регистр 5 сдвига, а значения второй половины четных отсчетов входного сигнала ,., через выход коммутатора 2 и выход коммутатора 3 в четные такты заносятся в регистр 6 сдвига Аналогично в нечетные такты (N-l) значения чторой половинь нечетных отсчетов акодного сигнала Х; х s .. . ,х ;2 |Через выход коммутатора 2 и выход коммутатора 4 заносятся в регистр 7 сдвига, а вторая половина нечетных отсчетов входного сигнала , рез выход коммутаторов 2 и гистр 8 сдвига.

Э

Д

v- чев ре0

5 0

0

-

5

При этом коммутатор 2 управляется сигналом с выхода первого (младшего) разряда счетчика 30 блока 25 синхронизации, а коммутаторы 3 и 4 - сигналом с выхода (п)-гс разряда счетчнка 30 Регистры 5-8 сдвига уп равляются соответственно сигналами 7-10 (фиг, 4) с выходов элементов ИЛИ 65-68 блока 25 синхронизации (фиг. 2).На протяжении N/2 тактов (от N до 3/2 N) выполняется первая итерация преобразоваш4я. При этом в четные такты начиная с N-ro такта, происходит синхронно сдвиг информации в регистрах 5 и 6 сдвига, а в нечетные такты - сдвиг информации в регистрах 7 и 8 сдвига.

В четные такты из регистров 5 и .6 сдвига на входы сумг 1атора-вьгчитателя 15 через первые входы коммутаторов 9, 10, 13 и 14 постзшают значения четных отсчетов сигнала. В нечет- Hbie такты, на входы с умматора-вычитате-- ля 15 через входы конмутаторо:-г 1 I и 12 и входы KOt iMyTaTopoa i3 и i ; , ступают значения нечетг-ых отсчетов сигнала, которые содержатся в регистрах 7 и 8 сдвига. Коммутаторы 9-12 упра.;8ЛЯ1отся сигналом 6 (фиг. 4) с выхода элемента ИЛИ 63 блока 25 син:;с ронйзации, а в:оммутаторы 3 и 1ч- - сигналом с выхода первого (, младизет-с , разряда счетчш а 30 блока 25 синхро низации, В каждом такте на выходе сумматора-вычитателя i5 Б соответствии с графом преобразования фс рмиру- ются суммы ,,() 05 i , 2, . , . ,N/2-1 i первая половина котг1рых через вхо . коммутаторов 16 и 18 зяносится в регистр 20 сдвига, а вторая половина сумм через выходы коммутаторов 16 и 18 заносится в регистр 21 сдвига, Од- новременко с этим в каждом такте на втором выходе сумматора-вычитятеля

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

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

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

В течение следующих N/2 тактов (от 3/2 N до 2 N) вьтолняется вторая итерация преобразования. При этом на входы сумматора-вычитателя 15 в четные такты (начиная с 3/2 N-ro такта) через входы коммутаторов 9 и Ю и входы коммутаторов 13 и 14 поступают данные регистров 20 и 21 сдвига, а в нечетные такты через входы коммутаторов 11-14 на входы сумматора-вы- читателя 15 поступают данные из регистров 22 и 23 сдвига. На вЫход коммутатора 16 в каждом такте выводятся суммы Xj(j)(j+N/2), где (N/ /2-1), сформированные на выходе сум- матара-вычитателя 15, первая половина которых через выход коммутатора 3 заносится в регистр 5 сдвига, а рая половина сумм через выход коммутатора 3 - в регистр 6 сдвига. Одновременно с этим в каждом такте на выход коммутатора I7 вьгоодятся раз- ности Х2(5 )( J+N/2), сформированные йа выходе сумматора-вычитателя 15, первая половина которых через выход коммутатора 4 заносится в регистр 7 сдвига, а вторая половина разностей через выход коммутатора 4 - в регистр 8 сдвига,

В течение следуюпо1х N/2 тактов (от 2 N до 5/2 N) данные из регистров 5-8 сдвига поступают на входы сумма- тора-вычитателя 15, а результаты (сумма и разность), полученные в каждом такте на выходах сумматора-вычитателя 15-, заносятся в регистры 20-23 сдвига и т.д., пока не выполняется п итераций преобразования. На последней п-й итерации преобразования в течение N/2 тактов, начиная с M+(n-l)N/2 -го такта, на выходах сумматора-вычитателя 15 формируются коэффициенты х(0)- х() преобразования Уолша-Адамара, которые в зависимости от числа п итераций преобразования попарно заносятся в соответствующие регистры сдвига В случае, если п - четное число, то коэффициенты преобразования заносятся в регистры 5-8 сдвига, а если п - нечетное, то в регистры 20-23 сдвига, Таким образомд последняя пара коэффициентов х(К-2), x(N-l) преобразования в зависимости от четности числа п заносится соответственно в регистры 6 и В сдвига или в регистры 21 и 23 сдвига на (N+nN/2-l)-м такте,

Последовательное считывание коэффициентов преобразования из регистров сдвига производится через коммутаторы 9-14 и 24 во время занесения значений отсчетов сигнала из последующей выборки. Считьюание коэффициентов преобразования из регистров 5-8 или 20-23 сдвига производится передними фронтами импульсов сигналов 7-10 или 11-14 (фиг. 4),а занесение значений отсчетов сигнала в регистры 5-8 сдвига - задними фронтами импульсов этих сигналов. При этом первый коэффициент х(0) преобразования получается на (N+nN/2)-M такте на выходе коммутатора 24, управляемого сигналом 5 (фиг. 4) с выхода элемента И 35блока 25 синхронизации, а последний коэффициент x(N-l) преобразования - иа (2N+nN/ /2-1)-м такте.

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

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

сигналы управления 1-3. По приходу сигнала Т с выхода (n-l)-ro разряда счетчика 30 на первый вход формирователя 3 импульсов на втором вьп:оде формирователя 31 импульсов формируется сигнал 4 (фиг. А). Сигнал 4 через элемент И 32 формирует сигнал 5 (фиг. 4). Сигнал 6 формиГ уется в зависимости от четности числа п. iri В случае, если п -. нечетное число, т.. на первом выходе формирователя 31, импульсов, на выходе D, первого; (мла,;- шего) разряда вычитающего счетч даа 74 (фиг. З), находится потенциал логической I, который разрешает прохождение через элемент И 62 сигналs б формируемого на выходе элемента И 46 с помощью инверсных сигналов 4 и 3, В случае, если п - четное числоg 20 то на первом выходе формировате гя 3i импульсов находится потенциал логического О, который через элемент НЕ 52 разрешает прохождение

исходном состоянии на информационных входах D,-D, регистра 73 сдвига уста навливается код 1100 для формировани импульсов длительностью 2Тд, которая, получается по приходу третьего импуль са сигнала Тд, а на входе У последовательного занесения регистра 73 сдв га постоянно присутствует высокий потенциал (логическая 1).

По приходу сигнала с периодом Т -N/2 из выхода (п-1)-го разряда счет ji-nca 30 блока 25 синхронизации на счетный вход С параллельного зане- 5 сания регистра 73 сдвига по заднему рронту первого импульса сигнала Т н выходах 1-4 регистра 73 сдвига устанавливается код 1100о Потенциалом логического О с выхода четвертого (старшего) разряда регистра 73 СДВИГ в вычитающий счетчик 74 параллельно заносится двоичный код числа п итераций преобразования, который -устано лен на информационных входах D, -D„

элемент И 64 сигнала формиз1уемо-- 5 1-:ычитающего счетчика 74. При этом на

уходе элемента НЕ 76 итенциал логической

го с помощью сигнала и сипгала

устанавливаете 1

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

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

считывания коэффициентов преобразова- ЗО низкий потенциал (логической ния сигнал 6 имеет потенциал .л оги- на выходе постоянно присутствуе ческой,1, который переключает коммутаторы 9-12 для считывания ко:51|1фици-- ентов преобразования с регистров 5-8 v сдвига, так как при четном п коэ1|)фи- нему фронту импульса сигнала Т

О)

циенты преобразования находятся в регистрах 5-8 сдвига. Остальные сигналы 7-14 формируются на вькодах -элементов ИЛИ 65-72 с помощью прямых и инварс- ных сигналов 1-4.

Фop mpoвaтeль 31 импульсов раЗота- ет следующим образом.

Перед запуском фррмкрователя иа информационных входах Cj-Dfj вычитшэще- го счетчика 74 устанавливается ддюич- ный код числа п итераций преобразования. Запуск формирователя, 31 сов осуществляется потенциалом логического О, который подается на перрегистра 73 сдвига устанавливается

и

высокий потенциал, то по приходу второго импульса сигнала Т на счетный вход С, регистра -73 сдвига (по задна

«ГО-выходах происходит сдвиг вправо ранее занесенного параллельного кода 1100. На вькодах,регистра 73 сдвига получается код 1110, т.е, состояние

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

С приходом очередного, третьего

- импульса сигнала Т,, гго заднему фрокгу на выходе четвертого (старшего) разряда регистра 73 сдвига после очередного сдвига вправо устанавливает ся потенциал логической 1, которьй запускает вычитающий счетчик 74,. Яри этом счетчик 74 начинает вычи- ;;aTbj а на выходе элемента НЕ 76 ус- гакавлизается потенциал логическо- го о.

вый вход 28 элемента И-НЕ 75р та): как в исходном состоянии на выходе Р„ обратного переноса вьгчитающего счетчика 74 находится потенциал логической 1, который поступает на второй вход элемента И-НЕ 75, При этом на выходе элемента И-НЕ 75 устанавливается потенциал логической I, который поступает на управляющий вход V парш пель- кого занесения регистра 73 сдвига:- F

исходном состоянии на информационных входах D,-D, регистра 73 сдвига устанавливается код 1100 для формирования импульсов длительностью 2Тд, которая, получается по приходу третьего импульса сигнала Тд, а на входе У последовательного занесения регистра 73 сдвига постоянно присутствует высокий потенциал (логическая 1).

По приходу сигнала с периодом Т -N/2 из выхода (п-1)-го разряда счет- ji-nca 30 блока 25 синхронизации на счетный вход С параллельного зане- сания регистра 73 сдвига по заднему рронту первого импульса сигнала Т на выходах 1-4 регистра 73 сдвига устанавливается код 1100о Потенциалом ло. гического О с выхода четвертого (старшего) разряда регистра 73 СДВИГЕ в вычитающий счетчик 74 параллельно заносится двоичный код числа п итераций преобразования, который -установлен на информационных входах D, -D„

1-:ычитающего счетчика 74. При этом на

устанавливаете 1

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

О низкий потенциал (логической на выходе постоянно присутствуе v нему фронту импульса сигнала Т

О)

0

регистра 73 сдвига устанавливается

и

высокий потенциал, то по приходу второго импульса сигнала Т на счетный вход С, регистра -73 сдвига (по задна

«ГО-выходах происходит сдвиг вправо ранее занесенного параллельного кода 1100. На вькодах,регистра 73 сдвига получается код 1110, т.е, состояние

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

С приходом очередного, третьего

- импульса сигнала Т,, гго заднему фрокгу на выходе четвертого (старшего) разряда регистра 73 сдвига после очередного сдвига вправо устанавливается потенциал логической 1, которьй запускает вычитающий счетчик 74,. Яри этом счетчик 74 начинает вычи- ;;aTbj а на выходе элемента НЕ 76 ус- гакавлизается потенциал логическо- го о.

После прихода импульса сиг5

нала Тд на счетный вход С регистра 73 сдвига на выхлде Р„, братного ле- ианоса вьгаитающего счетчика 74 фс-ркя - С Уется отрицательный и шульС;, который

через элемент И-НЕ 75 потенциалом логической 1, поступающим на вход V регистра 73 сдвига, устанавливает на его выходах параллельный код 1100. При этом низкий потенциал на выходе четвертого разряда регистра 73 сдвига устанавливает на выходе элемента НЕ 76 высокий потенциал.

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

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

с 0

0 5 Q Q

5

0

5

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

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

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

Фие.д

Р

1

Фаг.