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

 

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

. СООЗ СОВЕТСНИХ сОщиАлистичесних

РЕСПУБЛИН (у) 5 G 06 F 15/332

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

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

С:

ГОСУДАРСТВЕННЫЙ НОМИТЕТ пО изОБРетениям и ОтнРытиям

ПРИ 1 ННТ СССР

1 (21) 4452770/24-24 (22) 07,07.88 (46) 07.11.90.Áþë. У 41 (71) Институт кибернетики им. В.М.Глушкова (72) Л.А.Гнатив, Я.Е.Визор, М.А.Гнатив и Г.Я.Ширмовский (53) 681.32 (088.8) (56) Авторское свидетельство СССР

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

R.Jarlagadda, I.Å.Herchey. Architecture of the fast V1a1sh — Hada: mard.and East Fourier transforms, with change transfer devices. lnt J, Electronics, 1981, чо1.51, .У 5, р.677, fig.2, (прототип)..,90„„1605254 А 1

2 (54) УСТРОЙСТВО -ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША-АДАМАРА (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для цифровой обработки сигналов на основе дискретных ортогональных преобразований в базисе функций Уолша, для цифровой фильтрации, сжатия информации, для цифрового спектрально-корреляционного анализа случайных процессов, в технике связи и т.д. Цель изобретения — повышение быстродействия. Цель достигается sa счет того, что в сос" тав устройства входят коммутаторы

1,2, регистр 3 сдвига, сумматор-вычитатель 4, регистры 5, 6 сдвига, коммутатор 7, блок 8 синхронизации, регистр ll сдвига. 5 ил.

1605254

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

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

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

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

Формирователя импульсов, на фиг. 5 временная диаграмма работы устрой- 25 ства для Б = 8 (Б 2 ), Устройство содержит коммутаторы

i и 2, регистр 3 сдвига, сумматор-вычитатель 4, регистры 5 и б сдвига, коммутатор 7, блок 8 синхронизации, информационный вход 9, тактовый вход 10, регистр 11 сдвига, вход 12 запуска и вход 13 задания размера преобразователя, Влрк 8 синхронизации (фигез) ср» держит счетчик 14, формирователь 15 импульсов, счетчик 16, элементы И 17 и 18, счетчик 19, элементы И 20 и

21, элемент НЕ 22, элемент И 23,элемент НЕ 24, элемент И 25, элемент

НЕ 2б, элементы И 27 и 28, элементы

ИЛИ 29 и 30.

Формирователь 15 импульсов (фиг,4) содержит четырехразрядный регистр 31 сдвига, вычитающий счетчик 32 и эле- 45 и-не зз.

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

Последовательность X (1 ), Х (2), ° ° ° ...Х(Б) отсчетов входного сигнала с частотой тактовых импульсов через первый информационный вход коммутатора 1, управляемого с выхода 1 блока

8 синхронизации сигналом 1 (фиг,5), поступает на вход коммутатора 2,кото55 рый управляется сигналом 2 с выхода

2 блока 8 синхронизации. При этом коммутатор 1 подключен к информационному входу 9 устройства на время поступления отсчетов Х(l ) — K(N) входного сигнала. В нечетные такты (j

1 — Б-1, где I — номер тактового импульса), через первый выход коммутатора 2 значения нечетных отсчетов входного сигнала X(l), Х(3),...,K(N-1) заносятся в регистр 3, .а в четные такты (j = 2 — N) значения четных отсчетов входного сигнала Х(2), Х(4),...,Х(Б) через второй выход коммутатора 2 заносятся в регистр 11.

При этом регистры 3 и 11 управляются задними фронтами тактовых импульсов сигналов соответственно 5 и 6 (фиг.5) с выходов 5 и 6 блока 8 синхронизации. На протяжении Б/2 тактов,начиная с (N+1)-ro такта, выполняется первая итерация преобразования. При этом с тактовой частотой происходит считывание одновременно с регистров

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

Х1{j/2) = X(j — 1) + X(j)

Х (N/2) + j (2)

Х{.1-1) — X(j ), j = 2,4,6...,N, которые одновременно заносятся в регистры 5 и 6 (суммы заносятся в регистр

5, а разности — в регистр 6), При этом регистр 5 управляется тактовым сигналом К (фиг.5) с выхода 10 блока 8 синхронизации (эта связь на схема не показана), а регистр б — сигналом 4 (фиг.5) с выхода 4 блока 8 синхронизации. В.течение следующих

Б/2 тактов, начиная с (3/2 Б + 1)-го такта происходит считывание данных (сумм) иэ регистра 5. При этом данные из регистра 5 через коммутаторы 7,1 и 2 в нечетные такты заносятся в регистр 3, а в четные такты — в регистр 11. Коммутатор 7 управляется— сигналом 3 (фиг.5) с выхода 5 блока

8 синхронизации. После этого, начиная с (2Б+1)-го такта, в течение следующих Б/2 тактов происходит аналогично считывание данных (разностей) из регистра 6 через коммутаторы 7, 1 и 2 в регистры 3 и ll ° При этом в нечетные такты данные заносятся в регистр 3, а в четные такты — в регистр 11.

5 .16

После этого, начиная с (5/2И+1)-ro т акт а, происходит аналогично первой вторая итерация преобразования и т.д,, пока не выполнится и итераций преобразования. На последней и-й итерации преобразования в течение

N/2 тактов, начиная с (3n-1}Н /2+1-ro такта, на выходах сумматора-вычитйтеля 4 формируются коэффициенты Х(1)- X(N) преобразования Уолша-Адамара, первая половина которых заносится в регистр 5, а вторая половина коэффициентов преобразования одновременно заносится в регистр 6. В течение

N/2 тактов, начиная с (3n N/2 +

+ 1)-ro такта, происходит считывание с регистра 5 первой половины коэффициентов Х(1) — X(N/2) преобразования, а в течение следующих И/2 тактов считывается с регистра 6 вторая по ловина коэффициентов Х(11/2+1)-X(N) преобразования, которые выводятся на выход коммутатора 7. Прн этом первый коэффициент Х(1} преобразования выводится на выход коммутатора 7 на (3п11/2 + 1)-м такте, а последний коэффициент X{N) преобразования — на (3n+2) 11/2-м такте. На время считывания коэффициентов преобразования коммутатор 1 подключается к информацион.ному входу 9 устройства и одновремен-. но со считыванием коэффициентов происходит занесение в регистры 3 и 11 значений отсчетов, сигнала из следующей выборки.

Блок 8 синхронизации работает следующим образом, Запуск блока 8 синхронизации производится потенциалом логического "0", который подается на вход 12 блока 8 синхронизации и запускает формирователь 15 импульсов. При этом на выходе формирователя 15 импульсов формируется отрицательный импульс сигнала управления

1 (фиг.5). По приходу тактовых импульсов f (фиг.5) на счетный вход

I0 счетчика 14 на выходе 1 первого

{младшего) разряда его формируется сигнал управления 2 (фиг,5), а на

f выходе (и-l)-ro разряда счетчика 14 формируется сигнал Т „ который поступает на первый вход формирователя 15 импульсов и на счетные входы счетчиков 16 и 19, По приходу сигнала Т на выходе формирователя 15 импульсов формируется сигнал управления, который по переднему фронту сбрасывает счетчик 19 в нулевое состояние., 05254

25 30

Сигналы с выходов первого и второго разрядов счетчика 16 поступают на входы элемента И 17, на выходе которого формируется сигнал управления

4 (фиг.5). С помощью тактового сигнала f и сигнала управления 4 кормит руется на выходе элемента И 18 сигнал управления 3, Сигналы с выходов первого и второго разрядов счетчика

19 поступают на входы элемента И 20, на выходе которого формируется сигнал, который поступает на первые входы элементов И 21 и 27 и через элемент

НЕ 24 поступает на первый вход элемента И 25„ С помощью прямого и инверсного сигналов управления 1,которые поступают на входы элементов И 21, 23, 25, 27 и 28, прямого и инверсного сигналов управления 2, которые поступают на входы элементов И 21, 23, 27. и 28, а также с помощью тактового сигнала Е, который поступает на вход элемента И 25, на выходах элементов ИЛИ 29 и 30 Формируются сигналы управления соответственно

5и6.

Формирователь 15 импульсов работает следующим образом. Перед запуском формирователя импульсов на информационных входах D, - D вычитаишего счетчика 32 устанавливается двоичный код числа m(m = 3n-2} тактов преобразования. Запуск формирователя 15 импульсов осуществляется потенциалом логического "0", который подается на вход 12 элемента И-НЕ 33, так как в исходном состоянии на выходе Р обратного переноса вычитаюшего счетчика 32 находится потенциал логической "1", который поступает на второй вход элемента И-НЕ 33, При этом на выходе элемента И-НЕ 33 устанавливается потенциал логической

"1", который поступает на управляющий вход Ч параллельного занесения регистра 31 сдвига. В исходном соc-, тоянии на информационных входах

П вЂ” Dy регистра 31 сдвига устанавливается код 1100 для формирования импульсов с длительностью 2Т, которая получается по приходу третьего импульса сигнала Т, а на входе V» последовательного занесения регистра

31 сдвига постоянно присутствует высокий потенциал (логическая "1").По прйходу сигнала с периодом T

11/2 из выхода (n-1)-ro разряда счетчика 14 блока 8 синхронизации

1605254 8 на счетный вход С параллельного занесения регистра 31 сдвига по заднему фронту первого импульса сигнала

Т на выходах 1 - 4 регистра 31

0 сдвига устанавливается код 1100.Потенциалом логического "0" с выхода четвертого (старшего) разряда р егистра 31 сдвига в вычитающий счетчик 32 параллельно заносится двоичный код числа ш, который установлен на информационных входах 0< - П„, вычитающего счетчика 32. При этом на выходе четвертого разряда регистра 3! сдви" га устанавливается потенциал логического "0", Так как на управляющем входе 7 регистра 31 сдвига устанавливается низкий потенциал (логический "0") и на входе V< постоянно присутствует высокий потенциал, то по приходу второго импульса сигнала Т на счетный вход С регистра 31 сдвига (по заднему фронту импульса сигнала Т ) на его выходах происходит сдвиг вйраво ранее занесенного параллельного кода

1 100. На выходах регистра 31 сдви га получается код 1110, т.е. состояние четвертого разряда на выходе не изменилось и равно логическому "0",что не разрешает запускать вычитающий счетчик 32. С приходом очередного третьего импульса сигнала То по заднему фронту на выходе четвертого разряда регистра 31 сдвига после очередного сдвига вправо устанавливает" ся потенциал логической "1",который запускает вычитающий счетчик 32.При этом вычитающий счетчик 32 начинает вычитать. После прихода (Зп-2)-ro импульса сигнала Т на счетный вход

С регистра 31 сдвига на выходе P обратного переноса вычитающего счет. чика 32 формируется отрицательный импульс, который через элемент .

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

ЗО

4Î

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

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

1б05254

ii = l

Х(Ц

Х(7 1() п-1

Х(2

Х71/2) д-1 (Ю) х (н х (ю) Фиг. 3

12

Х (Я

Х1(ф/2.1) 1605254 a © 1 Я g мъ <э а ад esp gN »Ф Ф <се с> е гэ Фм> юе ф е Фз ъ» миф

ЛлФ/Я (8п+Ю)Ф/Я

Редактор Н,Тупица

Заказ 3455 Тираж 569 Подпи сно е

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

1 0

2 6

J 1

4 1 а

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

Техред М.Дидык Корректор Т.Палий