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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU, 1615742 щ) G 06 F 15/332

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

Я Q Q+QPQQQfg+ СЯЩД ЯД(ф(; Я /

ГОСУДАРСТВЕННЫЙ НОМИТЕТ, ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4661319/24-24 (22) 23. 01. 89, (46) 23, 12.90. Бюл. N - 47 (71) Институт кибернетики им. В. M. Глушкова (72) Л. А. Гнатив, М. А. Гнатив, Я. Е. Визор и Г. Я. Ширмовский (53) 681.32(088.8) (56) Авторское свидетельство СССР

Ф 951320, кл, G 06 F 15/332, 1982.

Yarlagadda R. НегзЬеу J. Е. АгсЬ tecture of the fast Malsh — Radamard

and fast Fourier transforms vith

charge transfer devices.-Int.J.Electronics 1981, vol 51 М 5, р. 677, Fig. 2. (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ОРТОГО, НАЛЬНОГО ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ

СИГНАЛОВ ПО УОЛШУ-АДАМАРУ (57) Изобретение относится к автоматике, вычислительной технике и может быть использовано для обработки цифровых сигналов на основе быстрых ортогональных преобразований в базисе функций Уолша, для цифрового спектрального и кбрреляционного анализа сигналов, цифровой фильтрации, цифровой обработки изобретений, сжатия информании и т,д. Цель изобретенияповышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят коммутаторы 1 и 2, регистр 3, сумматор-вычитатель 4, коммутаторы 5-7, регистры Я

8 и 9 коммутатор 10, блок 11 синхронизации, регистр 12 коммутаторы 13 и 14. 5 ил.

1615742

Изобретение относится к автомати-, ке и вычислительной технике и может

1 быть использовано для обработки циф" ровых сигналов на основе быстрых ор5 тогональных преобразований в базисе функций Уолша, для цифрового спектрального и корреляционного анализа

1 сигналов, цифровой фильтрации,, цифровой обработки изображений, сжав"ия 10 информации и т.д.

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

Устройство (фиг. 1) содержит ком"мутаторы 1 и 2, регистр 3 сдвига сумматор-вычитатель 4, коммутаторы

5-7, регистры 8 и 9, коммутатор 10, блок 11 синхронизации, регистр 12, коммутаторы 13 и 14, входы 15 " 18 устройства.

Блок 1 l синхронизации (фиг. 3) содержит счетчик 19. формирователь 20 30 импульсов, элементы И 21-23 элем нт

НЕ 24„ элементы И 25 и 26, элемент

НЕ 27, элементы И 28 и 29, элемент, НЕ 30, элементы И 31-37, элемент

i HE 38, элемент И 39, элементы ИЛИ 40: 45.

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

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

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

Последовательность fx(1) — z(N)l отсчетов входного сигнала с частотой

J тактовых импульсов (фиг. 5) через инеоГ форма.цианный вход 15 коммутатора управляемого с выхода блока 11 синхронизации сигналом "1" (фиг. 5), поступает на информационный Вход коммутатора 2, который управляется сигналом "2" (фиг. 5) с выхода блока 11, Коммутатор l подключен к информационному входу 15 устройства на время поступления отсчетов входного сигнала.

При этом первая половина отсчетов входного сигнала х(1) " x(N/2) через выход коммутатора 2 заносится в ре-: гистр 3 сдвига, а вторая половина от-. счетов x(N/2+1)-x(N) через выход каммутатора. 2 — в регистр 12 сдвига, Все отсчеты Входного сигнала заносятся z регистры 3 и 12 сдвига„ которые уп- ( равляются передними франтами тактоВых импульсов сигналов соответственно

"5" и. "б" (фиг. 5) с выходов блока 11 синхронизации, за N тактов. На протяжении следующих Л/2 тактов выпалняет ся первая итерация преобразования.

Нри этом с гактавай частотой К чраисхадит считывание с регистров 3 и 12 сдвига дянньгх, которые через информационные Входь1 коммутаторов 13 и 14поступают Ia входы сумматора-Вычитателя 4. 0 каждом та ò.å на Выходах

C ÌÌcITO,".,--ВЬГ.. ЛтатЕЛя 4 В СООТВЕТСТВИИ с графам преобразования (r)II 2) фар-" мируютс я суммы и DB зн асти х (2,1-1) = x(j) ь х(И /2+1-,,;. х (21) .= Х(1) — х(М/2+1)), j = 1, И/2, которые в течение Х/4 тактов через коммутатор 5, первые Выходы коммута"opoF» 6 н 7 заносятся (сна.ала сумма,. а затем " разность/ с частОтай 2 1 -; в регистр 8, а в те--:енгле следующих

N/", тактов через выход коммутатора 7 с тай же частотой 2 F..„. - в регисT» 9, Коммутатор ., .оправляется сигналам 2 Л с тактового Входа бла.:;;: 11, а коммутаторы б и 7 — соответственна сигна..-.ями "4" и 2 " (фиг. 5) с выходов блока 1 1 . с еГистры 8 е: с управляются тактовыми сигналами "!" г с выходов блока 11. В те-. .ени.: следую= паж И/2 тактов, начиняя с (3/2 И+1)Io такта, Вьшолняется Вторая итерация преобразования, Прн этом .":,яннь,е из

5) регистров 6 и 9 через информационные

Входы коммутаторов 13 и 14 с тактава частотаи f- поступают ня входы сумма тара-Вычи ателя 4. Результаты, пал ЧаСоМЫЕ IicI ВЫХадах Сутоа4ата .Icl БЫ LHTc ТЕ ля 4,„г;аступают,OIIÿ säëd. Сумма, затем — ргз наст.".) через ксммутг.тар 5, ВЫХад XOMMQ TcITOpc 6 И ВХОД КО1 ;М ЧТОTO ра ", ня информят ланный вход коммутатора 2„ При этом первая половина ре- зультатов в течение М 4 тактов через выход коммутатора ? с -.астатай 2 заносится в регистр 3, а ВTapcsI -.. îëîВина результатов в течеь:-е слcäóêèöèx

N/м тактов черсз Вььхад коммутатора

2 — В регистр 12. 1осле этого, начи1615 ная с (2N+1)-ro такта, происходит аналогично первой третья итерация преобразования, затем четвертая ите рация аналогично второй и т.д., пока не выполнится п итераций преобразоваНИЯ °

На и-й итерации преобразования в течение N/2 тактов, начиная с ((и+1)

N/2+1)-го такта> на выходах сумматора-вычитателя 4 формируются коэффициенты х(1)-x(N) преобразования Уолша- цамара, первая половина которых, если n — нечетное число, заносится в регистр 8, а в-.,орая половина коэффициентов преобразования — H регистр

9. В случае, если п — четное, то первая половина коэффициентов преобразования заносится в регистр 3, а вторая половина коэффициентов « в ре-..: гиотр 12. В. течение следующих N тактов, начиная с ((и+2) N/2+1g-го такта, происходит считывание с тактовой частотой f сначала с регистра 8, а затем с регистра 9 (если 11 — нечетное) или с регистра 3, а затем с регистра 12 (если n — четное) коэффициентов преобразования, которые через коммутаторы 13 и 14 выводятся на выход коммутатора 10. При этом последний коэффициент x(N) преобразования выводится на выход коммутатора 10 на (и+4) N/2-м такте. Коммутатор 10 управляется сигналом "4" (фиг, 5) с выхода блока 11. Одновременно со считыванием коэффициентов преобразования происходит занесение через коммутаторы 1 и 2 в регистры 3 и 12 сдвига значений отсчетов входного сигнала из следующей выборки. Во время считывания коэффициентов преобразования коммутатор 1 подключается к информационному входу 15 устройства.

Блок 11 на выходах формирует управляющие сиГналы y > ) ys (фиГ ° 5), которые описываются с помощью логических функций следующими уравнениями: у — сигнал с первого выхода формирователя 20 импульсов; у1. (У<3 r )v(y gr ); у -(@,6У,3 r„)V(9,3 3 г„)/(У,IC. «„);

У1.=

У = (у 3(гф Й fr)М (У g, r„g 1)1

Иу В r% «11-1В rf ) i

y6 = (У,Ь -„В,)У(у,8 r„K f )V

V (y)K «Д«11 i 3(г,-);

У7 = (У, g, r g fz) V(y„g г„ f ) ( 4(y Й Я,r t,-t g, rf );

742

6 у = (у K rp II

q(y< (r„g r„, 3 гЙ ), 5 где r — сигнал с выхода и-го раэря11-да счетчика 19;

Х вЂ” сигнал тактовой частоты, который формируется на выходе первого разряда счетчика 19;

10 — сигнал с второго выхода формирователя 20 импульсов для определения четности двоичного числа и.

Запуск блока 11 синхронизации про-. изводится потенциалом логического "0" который подается на вход 18 блока 11 синхронизации и запускает формирователь 20 импульсов. При этом на выходе формирователя 20 импульсов форми-.

20 руется отрицательный импульс сигнала управления У1. По приходу импульсов с частотой 2 Е г на счетный вход 16 счетчика 19 на вых;де первого (младшего) разряда его формируется тактовый сиг25 нал f, на выходе и -го разряда счетчика 19 - сигнал управления у, а на выходе (n-1)-го разряда сигнал «11„, который поступает на второй вход формирователя 20 импульсов. По приходу

30 сигнала гд„ на первом выходе формирователя 20 импульсов формируется сигнал управления у,„ который по заднему фронту сбрасывает -.четчик 19 в нулевое состояние. Сигнал PZ, получаемьй на втором выходе формирователя 20 импульсов, зависит от значения младшего разряда кода двоичного числа и который устанавливается на входе 17 установки размерности преобразования.

40 Если п нечетное число, то сигнал равен логической "1", а если и четное, то сигнал Р равен логическому

It tt

С помоц1ью прямого и инверсного ..

45 сиГналов yg y (и сиГналов 1 д гр р которые проходят через элементы И 21 и 25 и элемент ИЛИ 40, на выходе эле мента ИЛИ 40 формируется сигнал управления у . Сигналы у,, у,, rn, г„1, и Р с помощью элементов И 22, 25, 26, 37, 39 и элемента:ИЛИ 41 формирут ют на выходе элемента ИЛИ 41 сигнал управления y . Сигналы у, у,, г„„г„, Ет и 2 1 с помощью элементов

И 22, 23, 26, 31, 33 и 34 и элемента, ИЛИ 42 на выходе элемента ИЛИ 42 фор мируют сигнал управления у . Сигнал управления у- форм.1руется на выходе элемента ИЛИ 43 с помощью сигналов

1615742

8 п n n-» г " Г KoTo- " регистра 46 сдвига устанавливается

r r r рые проходят через элементы И 22, низкий потенциал (логический "0") и

:23 25 28 34

3 и 35 и элемент ИЛИ 43. на его входе V постоянно присутствуСигнал управления у формируется на ет высокий потенциал (логическая "1 ) выходе элемента ИЛИ 44 с помощью сиг- по приходу второго импульса сигнала налову у r r г К 2 f

У1, У1, <, „, r z „К z и 2 "-F, rq, на счетныи вход С, регистра 46

:которые проходят через элементы И 22, сдвига на его выходах происходит .23 26 32 33 и 36 и элемент ИЛИ 44. сдвиг (задним фронтом импульса сигнапомощью сигналов сигналов у p g) rп Ри 10 JIG lq 4) вправо ранее занесенного па г „ Гт, 2 К Г и элементов И 22, 23, раллельного кода l100. На выходах

5, 29, 35 и 36 на выходе элемента 1-4 регистра 46 сдвига получается

ЛИ 45 формируется сигнал управления код 1l10 т.е. состояние четвертого

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

Ф что не разрешает запускать вычитающий счетчик 47. С

Перед запуском формирователя 20 приходом очередного третьего импульмпуг:ьсов на информационных входах са сигнала r на на выходе четвертого — П вычитающего счетчика 47 уста- разряда регистра 46 сдвига после очеавливается двоичный код числа итера- редного сдвига впр

20 вправо устанавливается и преобразования. Запуск формирова- потенциал логич " "1", логическои, который заеля 20 импульсов осуществляется по- пускает вычитающий счетчик 47 Вычи1Ф 1!

9 енциалом логического "0, который тающий счетчик 47 начинает вычитать. одается на первый вход 18 элемента После прихода и-го импульса сигнала

-НЕ 48, так как в исходном состоянии 25 г,„, на счетный вход С, регистра 46 а выходе P обратного переноса вычи- сдвига на выходе Р обратного переко1 ающего счетчика 47 находится потенци- са вычитающего счетчика 47 ф ц ормируетлогической "i,", который поступает ся отрицательный импульс, который чена второй вход элемента И 33. При рез элемент И-НЕ 48 потенциалом логиэтом на выходе элемента И 33 устенав- 30 ческой "1", поступающим а вход V, ливается потенциал логической "1", ко- регистра 46 сдвига, устанавливает на торыи поступает на управляющий вход его выходах параллельный код l 100.

Ч параллельного занесения регистра При этом на выходе четвертого разря4 сдвига. В исходном состоянии на ин= да регистра 46 сдвига устанавливается ф рмационных входах . D — D 4 регистра потенциал логического "0" Г

4 сдвига устанавливается код 1100 вьгходе формирователя 20 импульсов под я формирования импульсов с длитель- стоянно присутствует потенциал логик стью N, которая получается по при- ческой "1" если и— если и — нечеткое число х ду третьего импульса сигнала r„ „ и потенциал логического "О"— — при а на входе Vl последовательного зане- четном и. сфния регистра 46 сдвига присутствует

40 потенциал логической "1". По приходу Ф о р м у л а и б ла из о ретения сигнала r <> с периодом Т = И/2 из выхода (и-1) -го разряда счетчика l9 Устройство для быстрого ортагональлока 11 синхронизации на счетный

45 ного преобразован ф овакия цифровых сигналоь вход С параллельного занесения реги- по Уолшу-Адама у ару, содержащее сумматорстра 46 сдвига по заднему фронту пер - вычитатель четыре регистра, шесть вого импульса сигнала r„> на выходах коммутаторов . б и лок синхронизации, его 1-4 устанавливается код 1100. выход первого ком ого коммутатора подключен

Потенциалом логического "0" с вы- к инйормаци ционному входу второго комхоца четвертого (старшего) разряда 50 мутатора в атора, выход суммы сумматора-вырегистра 46 сдвига в вычитающий счет- читателя подкл дключек к первому информачиК 47 параллельно заносится двоич- oííoì нному входу третьего коммутатора, ный код числа, который установлен на первый в х выход четвертого коммутатора информационных входах D - D вычита- подключе ф н к ин ормационному входу пяющ го счетчика 47. При этом на выходе 55 того коммута мутатора первый выход коточетвертого разряда регистра 46 сдвига рого подключе ф чек к ин ормационному вхоус . анавливается потенциал логическо- ду первого р .r 1 И регистра, первый — пятый го 0 . Так как ка управляющем входе выходы блока синхронизации подключе10

1615742

Хд. (7) х,р) Х(2) АЯ

Xï-4) X(2J -7) х(г ) Л"1(Я ) р, м„.,(+1

Х1(2„-7) Х1(2Я

x(g) х„,,(р)

М(@-1), (и) X(N) 3ыуытаюе слажеию ны соответственно к управляющему входу первого коммутатора, тактовым вхо" дам первого — четвертого регистров, шестой, седьмой и восьмой выходы блока синхронизации подключены к управляющим входам соответственно четвертого, пятого и шестого коммутаторов, а первый информационный вход первого коммутатора является информационным входом устройства, тактовым входом, входом задания размера преобразования и входом запуска которого являются соответственно тактовый вход, вход режима и вход запуска блока син- 15 хронизации, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него вьедены седьмой и восьмой коммутаторы, при этом первый и второй выходы второго коммутатора подключены к информационным входам соответственно второго и третьего регистров, выходы которых подключены к первым информационным входам соответственно шестого и седьмого коммутато- 25 ров, выходы которых подключены соответственно шестого компутатора — к первому входу сумматора-вычитателя и первому информационному входу восьмо!

x(i) x®

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

1615742

1615747

Г ЧР па лп

У/ Ф Ы

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

Техред Д.Сердокова Корректор М. Пожо

Редактор А. Козориз

Заказ 3989

Тираж 569

Подписное

ВНЯЛИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5, Производственно-издательский комбинат "Патент", г. Ужгород, чп. Гагарина, 101