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

 

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

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

РЕСПУБЛИК

Al (Su 4 G 06 F 15/332

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

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4199803/24-24 (22) 24.02.87 (46) 23.09 .88, Бюл. М- 35 (71) Институт кибернетики им. В.М.Глушкова (72) Л.А.Гнатив, С.Г.Бунин, Г.Я.Ширмовский и Б.М.Шевчук (53) 681. 3 (088,. 8) (56) Патент США Р 3742201 кл. G 06 F 15/332, опублик. 1973.

Авторское свидетельство СССР

У 744555, кл. G 06 F 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША. (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для цифрового спектрального и корреляционного анализа

„„SU„„1425?07 сигналов на основе дискретных ортогональных преобразований в базисе функций Уолша, для цифровой фильтрации, сжатия информации, в технике связи и т.д. Целью изобретения является упрощение устройства. Устройство содержит и регистров сдвига 1.11.n (g — число коэффициентов преобразования), и сумматоров-вычитателей

2.1-2.п, п коммутаторов 3.1-3.п, два счетчика 4.5, и элементов НЕ 4-9, 2п-1 элементов И 10-15. Введение второго счетчика элементов HE И позволяет сократить суммарную разрядность регистров сдвига до 2 -1 (2 разрядов в регистре i-го каскада преобра- Ж .

- n-1 зования, i 1 n) по сравнению с п 2 разрядами в известном устройстве.3 ил lJ У

1425707

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

Целью изобретения является упрощение устройства.

На фиг. 1 представлена функциональная схема устройства; на фиг ° 2

< временная диаграмма; на фнг. 3 — граф 15 быстрого преобразования Уолша-Пэли для N=8, (M=2 ).

Устройство содержит регистры 1,—

1„сдвига, -сумматоры-вычитатели 2,—

: 2„, коммутаторы 3, -3„, счетчики 4 и

5, элементы HF. 6-9, элементы И 1015, информационный 16 и тактовый 17 входы и выход 18. Регистр 1о сдвига, . сумматор-вычитатель 2; и коммутатор

3, образуют i-й каскад преобразования.

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

Входная последовательность х,х<, ...х п,, представляющая отсчеты дискретного сигнала, с частотой такто вых импульсов поступает на вход ре,гистра I сдвига, управляемого с выхода и-го элемента НЕ 9, где задерживается на один такт (в регистре 1, сдвига хранится один отсчет). Срабатывание сумматора- вычитателя 2 управляемого сигналом 2 (фиг. 2) с первого выхода первого (младшего) разряда счетчика 5 синхронизируется в каждом четном такте. На выход коммутатора

3 который управляется сигналом 3 (фиг. 2) с выхода элемента И 10 и работает с частотой в два раза боль- 45 ше, чем тактовая частота регистра 1 сдвига, в течение каждого такта, начиная с второго, выводится сначала сумма, а .затем разность х +х<, х -х,, ...Х „, +Хил,...,Х<< -Х л И т,Д.

В К- ом (К = 2-и) каскаде а соответ5О ствии с графом преобразования (фиг.

3) последовательность промежуточных данных задерживается в регистре 1k

<«-< на 2 тактов. Регистр K-ro каска<«-< 55 да работает с тактовой частотой в 2 раза больше, чем тактовая частота регистра I к сдвига первого каскада.

Сдвигающий вход регистра 1 сдвига

К-ro каскада управляется сигналом с выхода (2К-t)-ro элемента И. Срабатывание сумматора-вычитателя 2„ К-ro каскада синхронизируется сигналом с второго выхода (К-I)-ro элемента И .

Коммутатор 3 К-ro каскада, управляемый с выхода (2К-1)-rо элемента И, работает с частотой в два раза больше, чем тактовая частота регистра 1 сдвига в К-ом каскаде, и на интервале каждого такта сначала выводит сумму, а затем разность, сформированные в К-ом каскаде.

h»

Х +Х .,Х,-Х,;,,...,Х „;,+Х..,, о, -< о 2 -«-2

Х «< « « Х2л

2- -х

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

3„ последнего n-ro каскада преобразол вания с частотой в 2 раз большей частоты следования отсчетов входного сигнала формируются коэффициенты преобразования Уолша с упорядочением по

Пэли. При этом первый коэффициент Х и преобразования получается на 2 -оц такте по приходу последнего 2 -ro л отсчета сигнала, а последний 2 -й коэффициент Х „, до прихода (2"+1)-ro отсчета. Гейератор импульсов формирует импульсы с частотой 2 ° f где

Tl

f — тактовая частота отсчетов входногоо сиг нала .

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

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

Устройство для выполнения быстрого преобразования Уолша, содержащее первый счетчик, вход которого соединен с тактовым входом устройства, п регистров сдвига (2 - число коэффи« циентов преобразования), и сумматороввычитателей, и коммутаторов, причем информационный вход первого регистра сдвига и суммирующий вход первого сумматора-вычитателя соединены с информационным входом устройства, выходы суммы и разности i-го (i-=1-п) суммато1425707 ра-вычитателя подключены к информационным входам i-го коммутатора, выход

j-го (j=1-п-1) коммутатора подключен к информационному входу (j+1)-го ре5 гистра сдвига и к суммирующему входу (j+1) -го сумматора вычитателя, выход

n-i

2 -го разряда и-ro регистра сдвига подключен к вычитающему входу и-го сумматора-вычитателя, выход n-ro ком- 1О мутатора является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит второй счетчик, и элементов

НЕ, 2п-1 элементов 1, причем вход вто- 5 рого счетчика соединен с выходом иго разряда первого счетчика (нумерация со стороны младшего разряда), выход i.-ro разряда первого счетчика соединен с входом i-ro элемента НЕ, вы- 20 ход n-j-го элемента НЕ и выходы разрядов с первого по j-й второго счетчика подключены к входам (2j-1)-го элемента И, выход которого подключен к первому входу 21-го элемента И, к управляющему входу j-го коммутатора и к сдвигающему входу (j+1) -г о р егистра сдвига, второй вход 2j-го элемента

И соединен с выходом (j+1)-ãî разряда второго счетчика, выход 2j-го элемен" та И подключен к синхронизирующему входу (j+1)-го сумматора-вычитателя, тактовый вход устройства и выходы разрядов с первого по и-й второго счетчика подключены к входам (2n-1)-го элемента И, выход которого соединен с управляющим входом и-го коммутатора, выход 2 -го разряда j-ro регистра сдвига подключен к вычитающему входу

j-го сумматора-вычитателя, 1425707 х(з) Корректор В,Бутяга

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

Составитель В.Байков

Редактор О.Головач Техред g.äèäûê

Заказ 4773/49 Тираж 704 Подписное

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

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

1 х()