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

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

Цель изобретения - повышение быстродействия устройства.

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

Устройство (фиг. 1) содержит мутаторы 1 и 2, регистр 3 сдвига сумматор-вычитатель 4, коммутаторы 5-7, регистры 8 и 9, коммутатор lО блок 11 синхронизации, регистр 12, коммутаторы 13 и 14, входы 15 - 18 устройства.

Блок 11 синхронизации (фиг. 3) содержит счетчик 19,, формирователь 2 импульсов, элементы И 21-23, элемент НЕ 24, элементы и 25 и 26, элемент НЕ 27, элементы И 28 и 29., элемент I НЕ 30, элементы И 31-37, элемент I НЕ 38J элемент И 39, элементы ИЛЧ 40

i

I Формирователь 20 импульсов (фиг. 4) содержит четырехразрядньш регистр 46 сдвига,, вычитающий счетчи

47 и элемент. И-НЕ 48.

I Устройство работает следующим об разом.

Последовательность Гх(1) - x(N)l отсчетов входного сигнахга с частотой ; тактовых импульсов (фиг. 5) через ин формационньй вход 15 коммутатора 1, управляемого с выхода блока 11 син- хррнизации сигналом 1 (фиг. 5),, поступает на информационный вход коммутатора 2, который управляется сигмаИ. j..

о /-л,

2 (фиг. 5) с выхода блока 11.

ТТ Я Т /ЛТЧ1ТТГЧТТ Т -ТТ-г т,-х-ч т-.. .. .4. ..

лом

Коммутатор 1 подключен к информационному входу 15 устройства на время поступления отсчетов входного сигнала. При этом первая половина отсчетов входного сигнала х(1) - x(N /2) через выход коммутатора 2 заносится в ре- : гистр 3 сдвига, а вторая половина отсчетов x(N/2+O-x(N) через выход ком

424

мутатора 2 - в регистр 12 сдвига. Все отсчеты входного сигнала заносятся в регистры 3 к 12 сдвига, которые уп- равляются передними фронтами такте- Еых импульсов сигналов соответственно

IffJ .., Ч/rl /-L г-

- И. b (.фиг. 5; с выходов блока 11 сршхронизации, за N тактов. Иа протяжении следующих N/2 тактов вьшолняетг

ся первая итерация преобразования. Яри этом с тактовой частотой f-j. исходит считывание с регистров 3 и 12 данньКг которые через информационные входы коммутаторов 13 и 14

поступают па входы сумматора-вычита- теля 4. В каждом такте на выходах с-умматора-вьр.гятателя 4 в соответстБии с графом преобразования (фиг, 2) фои- мир тотся суммы и разности

Xj() - x(j) -ь x(N /2-fij)|

25

x(j) - K(N/24-1j),

j Т Гш,,

которые в течение К/4 тактов через коммутатор 5, первые выходы коммутаторов 6 и 7 заносятся (сначала сумма,

а затем - разностьУ с частотой 2 f..,- в регистр 8. а в течени:е следующи N/if тактов через выход коммутатора 7 с той же частотой 2 f.,. - в регистр 9, Коммутатор .:; управляется сигналом 2 f

с тактового входа блоха П, а комму- таторы 6 и 7 - соответственно -игна- лаки 4 и 2 (фиг. 5) с выходов йлока 11. Регистры 8 к 9 управляются

(Аиг, 5У

тактовыми сигналами и

jJc-.iHucTbj ч

выход коммутатора

с выходов блока 11. В те гекиа следую ЩК51 N/2 тактов, начиная с (3/2 N-fl)- го такта, вьтолняется вторая итераци-я пг)ео6разования, При этом данные из регистров 3 и 9 через .информационные входы коммутаторов 13 и 14 с тактовой частотой fY поступаат на входы тора-вычктатеяя 4„ Результаты, получаемые на выходах .1атора -вычитаге nf: 4 5 поступают (сначал а сумг-та, затем - разность) через коммутатор 5,

и вход ко1.;мутатора 1 на информационный вход ком чута- тора 2. При этом первая половина ре-- зультатов в течение N/4 тактов через выход коммутатора 2 с частотой 2 f.-p заносигся в регистр 3, а вторая половина результатов в течек-е следующих /4 тактов через вькод коммутатора 2 - в регистр 12. После этого, начи 161

ная с (2N+1)-ro такта, происходит аналогично первой третья итерация преобразования, затем четвертая ите- рация аналогично второй и т.д., пока не вьшолнится п итераций преобразования.

На п-й итерации преобразования в течение N/2 тактов, начиная с (п+1) N/2+Л-го такта, на выходах суммато- ра-вычитателя 4 формируются коэффи- 1щенты x(1)-x(N) преобразования Уол- ша-Адамара, первая половина которьЬс, если п - нечетное число, заносится в регистр 8, а вторая половина козффи- щентов преобразования - в регистр 9 В случае, если п - четное, то первая половина коэффициентов преобразования заносится в регистр 3, а вторая половина коэффициентов - в per-: гиотр 12. В. течение следующих N так тов, начиная с (п+2) N/2+1j-ro такта, происходит считывание с тактовой частотой f сначала с регистра 8, а затем с регистра 9 (если п - нечет- ное) или с регистра 3, а затем с регистра 12 (если п - четное) коэффициентов преобразования, которые через коммутаторы 13 и 14 выводятся на выход коммутатора 10. При этом послед- НИИ коэффициент x(N) преобразования выводится на выход Коммутатора 10 на (п+4) N/2-M такте. Коммутатор 10 управляется сигналом 4 (фиг. 5) с вы

хода блока 11. Одновременно со счи- тыванием коэффициентов преобразования происходит занесение через коммутаторы 1 и 2 в регистры 3 и 12 сдвига значений отсчетов входного сигнала из следующей выборкиi Во время считывания коэффициентов преобразования коммутатор 1 подключается к информационному входу 15 устройства.

Блок 11 на выходах формирует управляющие сигналы у, Уа (фиг. 5), ко- торые описываются с помощью логических функций следующими уравнениями:

- сигнал с первого выхода формирователя 20 импульсов;

у. (у, & г„)У(у,г„.; ,

),)v(2X У. ,(Д п

yj (Д .)у(у,Х 5Д fT)V (УД гД г,.Дг,);

УЙ (уД гД)У(уД Д f)V

У(у,&гДг„.Л rf);

У7 УД гД)У(уД гД)У

V(y, );

У. (уД гД f)V(yJ ,)V У(.Д rf,).

Q 5 0 5 о

5

0

5

0

где г - сигнал с выхода п-го разря- V

да счетчика 19;

f - сигнйл тактовой частоты, ко- торьш формируется на выходе первого разряда счетчика 19; Y - сигнал с второго выхода формирователя 20 импульсов для определения четности двоичного числа п.

Запуск блока 11 синхронизации производится потенциалом логического О которьй подается на вход 18 блока 11 ci- нхронизации и запускает фо1)мирова- тель 20 импульсов. При этом на выходе формирователя 20 импульсов формит. руется отрицательньм импульс сигнала управления у,. По приходу импульсов с частотой 2 т на счетный вход 16 счетчика 19 на выходе первого (младшего) разряда его формируется тактовый сигнал fy, на выходе п-го разряда счетчика 19 - сигнал управления Уф, а на выходе (n-l)-ro разряда сигнал г.ц, которьй поступает на второй вход формирователя 20 импульсов. По приходу сигнала г„, на первом выходе форшфо- вателя 20 импульсов формируется сигнал управления у,, которьй по заднему фронту сбрасывает гчетчик 19 в нулевое состояние. Сигнал Р пол чае- мьй на втором выходе формирователя 20 импульсов, зависит от значения младшего разряда кода двоичного числа п, которьй устанавливается на входе 17 установки размерности преобразования. Если п нечетное число, то сигнал равен логической 1, а если п четное, то сигнал ф равен логическому О,

С помощью прямого и инверсного . сигналов у, у, и сигналов г„, , которые проходят через элементы И 21 и 25 и элемент ИЛИ 40, на выходе эле- мента ИЛИ 40 формируется сигнал управления у.,. Сигналы у,, у,, г„, г., . 2 и . с помощью элементов И 22, 25, 26, 37, 39 и элемента iMJM 41 формирут ют на рыходе элемента ИЛИ 41 сигнал управления Хз- Сигналы у., у, г„, г, г„.,, f-r и 2 fp с помощью элементов И 22, 23, 26, 31, 33 и 34 и элемента, ИЛИ 42 на выходе элемента ИЛИ 42 фор. мируют сигнал управления у. Сигнал , управления у формируется на выходе элемента ИЛИ 43 с помощью сигналов

1, У). п t r 2 f-r, кото- .рыё проходят через элементы И 22, |23, 25j 28j 34 и 35 и элемент ИЛИ 43. I Сигнал управления у., формируется на выходе элемента ИЛИ помощью сиг- ;налов у, у, г,, г„, г„.„ и 2 , |которые проходят через элементы И 22, |23, 26, 32, 33 и 36 и элемент ИЛИ 44, С помощью сигналов у, у, г, „, fl-i т 2 и элементов И 22, 23, 25, 29, 35 и 36 на выходе элемента ЛЛИ 45 формируется сигнал управления Уб1615742

V,

10

разряда на вых Формирователь 20 импульсов работа- j но логическому

СЛРПЛЛППГММ /-ifinao/ix -

регистра 46 сдвига устанавливаетс низкий потенциал (логический О) и на его входе V, постоянно присутству ет высокий потенциал (логическая 1 по приходу второго импульса сигнала г„, на счетньй вход С регистра 46 сдвига на его выходах происходит сдвиг (задним фронтом импульса сигна n-i) вправо ранее занесенного параллельного кода 1100. На выходах 1-4 регистра 46 сдвига получается код 1110, т.е, состояние четвертого разряда на выходе не изменилось и рав

0 , что не разрешает

iJT следующим образом.

Перед запуском формирователя 20

мпульсов на информационных входах

:| - DJ, вычитающего счетчика 47 уста авливается двоичньй код числа итера ий преобразования. Запуск формирователя 20 импульсов осуществляется потенциалом логического О, которьй подается на первый вход 18 элемента

,L-™.-™r S;-;,-.™-т:. ™

:

Ягом „а вь„о„е sneM.a и Is ySLas- ,„ --нииалон „„.и- л вается потенциал логической 1, которьй поступает на управляющий вход

запускать вычитающий счетчик 47. С приходом очередного третьего импульса сигналд г на выходе четвертого разряда регистра 46 сдвига после оче- 20 редного сдвига вправо устанавливается потенциал логической 1, которьй запускает вычитаюидай счетчик 47. Вычитающий счетчик 47 начинает вычитать. После прихода импульса сигнала

II -1 ti

, поступающим на вход V

V

Ф

г параллельного занесения регистра 3 сдвига. В исходном состоянии на ин-- эрмационных входах . D, - D регистра -го сдвига устанавливается код 1100 для формирования импульсов с длительностью N, которая получается по при- хфду третьего импульса сигнала ,, а;на входе Vj последовательного зане- сфния регистра 46 сдвига присутствует пфтенциал логической 1. По приходу сигнала г,,, с периодом Т N/2 из вырегистра 46 сдвига, устанавливает на его выходах параллельньй код 1100. При этом на выходе четвертого разряда регистра 46 сдвига устанавливается потенциал логического О. На втором вьгходе формирователя 20 импульсов постоянно присутствует потентдиал логической 1, если п - нечетное число и потенциал логического О - при четном п.

Формул

изобретени

х0да (п-1) -го разряда счетчика 19 блока 1I синхронизации на счетньй вз4од С 2 параллельного занесения реги- CTlpa 46 сдвига по заднему фронту пер- импульса сигнала г., на выходах его 1-4 устанавливается код 1100с,

Потенциалом логического О с вы- xofta четвертого (старшего) разряда регистра 46 сдвига в вычитающий счет- чик 47 параллельно заносится двоичный код числа, которьй установлен на информационных входах D - D вычита1ППТ(Ьт1Л тттттч-я im / 7т-г

Устройство для быстрого ортогональ- 45 ного преобразования цифровых сигналов по Уолшу-Адамару, содержащее сумматор- вычитатель, четыре регистра, шесть коммутаторов к блок синхронизации, выход первого коммутатора подключен к информационному входу второго коммутатора, выход сумматора-вы- читателя подключен к первому информационному входу третьего коммутатора первьй выход четвертого коммутатора подключен к информационному входу пя ФПТП ,«„ . , - iJ - и БЫЧИТЯющ.Ьго счетчика 47. При этом на выходе 55 того коммутатопл п.

.:™L -l:-r . .0 о..,х„ .. „. ,„;а,„я„ег:г:е -- , ГV,

0

разряда на вых но логическому

регистра 46 сдвига устанавливается низкий потенциал (логический О) и на его входе V, постоянно присутствует высокий потенциал (логическая 1) по приходу второго импульса сигнала г„, на счетньй вход С регистра 46 сдвига на его выходах происходит сдвиг (задним фронтом импульса сигна- n-i) вправо ранее занесенного параллельного кода 1100. На выходах 1-4 регистра 46 сдвига получается код 1110, т.е, состояние четвертого разряда на выходе не изменилось и рав0 , что не разрешает

S;-;,-.™-т:. ™

запускать вычитающий счетчик 47. С приходом очередного третьего импульса сигналд г на выходе четвертого разряда регистра 46 сдвига после оче- 0 редного сдвига вправо устанавливается потенциал логической 1, которьй запускает вычитаюидай счетчик 47. Вычитающий счетчик 47 начинает вычитать. После прихода импульса сигнала

,„ --нииалон „„.и-

II -1 ti

, поступающим на вход V

регистра 46 сдвига, устанавливает на его выходах параллельньй код 1100. При этом на выходе четвертого разряда регистра 46 сдвига устанавливается потенциал логического О. На втором вьгходе формирователя 20 импульсов постоянно присутствует потентдиал логической 1, если п - нечетное число и потенциал логического О - при четном п.

Формул

изобретени

ны соответственно к управляющему входу первого коммутатора, тактовым входам первого - четвертого регистров, шестой, седьмой и восьмой выходы блока синхронизации подключены к управ ляющим входам соответственно четвертого, пятого и шестого коммутаторов, а первьш информационньш вход первого коммутатора является информационным входом устройства, тактовым входом, входом задания размера преобразова ния и входом запуска которого являются соответственно тактовьй вход, вход режима и вход запуска блока сии- хронизации5 отличающееся тем, что, с целью повьш1ения быстродействия, в него введены седьмой и восьмой коммутаторы, при этом первый и второй выходы второго коммутатора подключены к информационным входам соответственно второго и третьего регистров, выходы которых подключены к первым информационным входам соответственно шестого и седьмого коммутато- ров, вькоды которых подключены соответственно шестого коммутатора - к первому входу сумматора-вычитателя и первому информацио нному входу восьмоХ(7) ,-1:1- Х;(|}

Xj(2)

Ш

(

)

х()

)

.X(W)

Х;(А/-7) X,(/V)

0

с 5

0

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

П()

n-iiJ)

.;()

-- X,.,(N)

Изобретение относится к автоматике, вычислительной технике и может быть использовано для обработки цифровых сигналов на основе быстрых ортогональных преобразований в базисе функций Уолша, для цифрового спектрального и корреляционного анализа сигналов, цифровой фильтрации, цифровой обработки изобретений, сжатия информации и т.д. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят коммутаторы 1, 2, регистр 3, сумматор-вычитатель 4, коммутаторы 5, 6, 7, регистры 8, 9, коммутатор 10, блок синхронизации 11, регистр 12, коммутаторы 13 и 14. 5 ил.

сложение

вычитание

Фи.г

Фиг.