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

Риг./

3160525

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

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

На фиг„1 представлена функциональтупления отсчетов Х(1). - X(N) входн го сигнала. В нечетные такты (j

« 1 - N-1

, где j - номер тактового

10

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

ная схема устройства; на фиг.2 - гра- 20 этом с тактовой .частотой происходит

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

Устройстве содержит коммутаторы

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

Блок В синхронизации (фиг.З) содержит счетчик 14, формирователь 15 импульсов, счетчик 16, элементы И 17 и 18, счетчик 19, элементы И 20 и 21, элемент НЕ 22, элемент И 23,элемент НЕ 24, элемент И 25, элемент НЕ 26, элементы И 27 и 28, элементы ИЛИ 29 и 30,

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

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

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

2блока 8 синхронизации. При этом коммутатор 1 подключен к инАормацион- ному входу 9 устройства на время пос25

30

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

X,(j/2) X(j - 1) + X(j)

X,(N/2) + j(2)

X(j-1) - X(j), j 2,4,6N

35

40

которые одновременно заносятся в рег стры 5 и 6 (суммы заносятся в регис 5, а разности - в регистр 6). При этом регистр 5 управляется тактовым сигналом f (фиг.5) с выхода 10 бл ка 8 синхронизации (эта связь на сх ма не показана), а регистр 6 - сигн лом 4 (фиг.З). с выхода 4 блока 8 синхронизации. В течение следующих N/2 тактов, начиная с (3/2 N + 1)-г такта происходит считывание данных 45 (сумм) из регистра 5. При этом из регистра 5 через коммутаторы 7,1 и 2 в нечетные такты заносятся в р гистр 3, а в четные такты - в регистр 11. Коммутатор 7 управляется - сигналом 3 (фиг,5) с выхода 5 блок 8 синхронизации. После этого,начиная с (2Н+1)-го такта, в течение следующих N/2 тактов происходит аналогично считывание данных (разностей) из регистра 6 через коммутаторы 7, 1 и 2 в регистры 3 и П. При этом в нечетные такты данные заносятся в регистр 3, а в четные такты - в регистр 11.

50

55

тупления отсчетов Х(1). - X(N) входного сигнала. В нечетные такты (j

« 1 - N-1

, где j - номер тактового

0

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

0 этом с тактовой .частотой происходит

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

X,(j/2) X(j - 1) + X(j)

X,(N/2) + j(2)

X(j-1) - X(j), j 2,4,6N,

5

0

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

0

5

После этого, начиная с (5/2М+1)-го такта, происходит аналогично первой вторая итерация преобразования и т.д., пока не выполнится п итераций преобразования. На последней п-й итерации преобразования в течение N/2 тактов, начиная с (Зп-1 )N/2+1-го такта, на выходах сумматора-вычитйте- ля 4 формируются коэффициенты Х(1)- - X(N) преобразования Уолша-Адамара, первая половина которых заносится в регистр 5, а вторая половина коэффициентов преобразования одновременно заносится в регистр 6. В течение Ы/2 тактов, начиная с (Зп N/2 + + 1)-го такта, происходит считывание с регистра 5 первой половины коэффи- циентдв Х(1) - X(N/2) преобразования, а в течение следующих N/2 тактов считывается с регистра 6 вторая по- ловина коэффициентов X(N/2+I)-X(N) преобразования, которые выводятся на выход коммутатора 7. При этом первый коэффициент Х(1) преобразования выводится на выход коммутатора 7 на (ЭпН/2 1)-м такте, а последний коэффициент X(N) преобразования - на (Зп+2) N/2-M такте. На время считывания коэффициентов преобразования коммутатор 1 подключается к информационному входу 9 устройства и одновременно со считыванием коэд)фициентов происходит занесение в регистры 3 и 11 значений отсчетов.сигнала из следующей выборки.

Блок 8 синхронизации работает следующим образом. Запуск блока 8 синхронизации производится потенциалом логического О, который подается на вход 12 блока 8 синхронизации и запускает формирователь 15 импульсов. При этом на выходе формирователя 15 импульсов формируется отрица- тельный импульс сигнала управления 1 (фиг.5). По приходу тактовых импульсов f (фиг.5) на счетный вход 10 счетчика 14 на выходе 1 первого (младшего) разряда его формируется сигнал управления 2 (фиг.5), а на выходе (п-1)-го разряда счетчика 14 формируется сигнал Т, который посту пает на первый вход Аормирователя 15 импульсов и на счетные входы счетчиков 16 и 19. По приходу сигнала Т на выходе формирователя 15 импульсов формируется сигнал управления, который по переднему фронту сбрасывает счетчик 19 в нулевое состояние,.

0

5

0

5

0

5

0

5

0

5

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

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

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

5и 6,

Формирователь 15 импульсов работает следующим образом. Перед запуском формирователя импульсов на инЛор- маци.онных входах П, - D вычитаюше- го счетчика 32 устанавливается дво- ичньш код числа m(in Зп-2) тактов преобразования. Запуск Формирователя 15 импульсов осуществляется потенциалом логического О, который подается на вход 12 элемента И-НЕ 33, так как в исходном состоянии на выходе Р обратного переноса вычитающего счетчика 32 находится потенциал логической 1, который поступает на второй вход элемента И-НЕ 33. При этом на выходе элемента И-НЕ 33 устанавливается потенциал логической 1, который поступает на управляющий вход V параллельного занесения регистра 31 сдвига. В исходном сое- . тоянии на информационных входах D регистра 31 сдвига устанавливается код 1100 для формирования импульсов с длительностью 2Т, которая получается по приходу третьего импульса сигнала Т , а на входе V последовательного занесения регистра 31 сдвига постоянно присутствует высокий потенциал (логическая 1).По приходу сигнала с периодом Т Ы/2 из выхода (n-l)-ro разряда счетчика 14 блока 8 синхронизации

CM параллельного

на счетньй вход

занесения регистра 31 сдвига по заднему фронту первого импульса сигнала Т.. на выходах 1 - 4 регистра 31

сдвига устанавливается код 1100.Потенциал ом логического О с выхода четвертого (старшего) разряда регистра 31 сдвига в вычитающий счетчик 32 параллельно заносится двоичный код числа т, который установлен на информационных входах D - D вычитающего счетчика 32. При этом на выходе четвертого разряда регистра 31 сдвига устанавливается потенциал логического О.

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

импульса сигнала Т на счетный вход Су регистра 31 сдвига на выходе Р обратного переноса вычитающего счетчика 32 формируется отрицательный импульс, который через элемент , И-НЕ 33 потенциалом логической 1, поступающим на вход регистра 31 сдвига, устанавливает на его выходах параллельный код 1100. При ЭТОМ на выходе четвертого разряда регистра 31 сдвига устанавливается низкий потен циал.

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

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

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

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

5

40

///;

W)

i(m} 1()

i()

Kj(N)

Сложение

о xm ют 1

s 5.

W.; II

( I I

S Q

Ю 5

I

i %

::::: soX/5v;

Вычиггк1ние

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

10

12в.

13

Фиг. В

Фиг.З

П-1

ifkis,&

fr 77-.7 77 Г Т 77 ;П /г 7 7 7 7 --