SU1141420A1 - Устройство дл выполнени быстрого преобразовани Уолша - Google Patents

Abstract

УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША, содержащее первый и второй коммутаторы , сумматор-вычитатель и блок пам ти , причем первьй информационный и управл ющий входы первого коммутатора  вл ютс  соответственно информационным и синхронизирующим входами устройства, отличающеес  тем, что, с целью повьшени  быстродействи , в него введены четыре регистра, блок сравнени , блок посто нной пам ти, первый и второй счетчики, одновибратор и генератор тактовых импульсов, выход которого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока посто нной пам ти, выход которого подключен к первому входу блока сравнени  н к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому и второму информационным входам второго коммутатора, выход которого подключен к адресному входу блока пам ти, выход которого подключен к информационным входам третьего и четвертого регистров, выходы которых подключены соответственно к второму и третьему информационным входам Ы первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитател , вькод которого подключен к информационному входу блока пам ти, управл ющий вход второго коммутатора соединен с вторым входом блока сравнени  и подключен к выходу второго счетчика, счетный вход которого подключен к выходу одновибратора , вход которого  вл етс  входом запуска устройства, а выход блока сравнени  подключен к управл ющему входу генератора тактовых импульсов .

Description

1 Изобретение относитс  к автомати ке и вычислительной технике и может ;быть использовано И аппаратуре цифр вой обработки низкочастотных сигналов (дл  спектрального анализа и синтеза, цифровой фильтрации, и т.д. Известно устройство ортогонально го преобразовани  Цифровых сигналов по Уолшу-Адамару, содержащее И сумматоров-вычитателей по 2 сумматйров-вычитатепей в каждой группе и устройства, содержащие 2 суммато ров-вычитателей, 2 регистров, 2 блоков элементов ИЛИ и 2 блоков элементов И и блок формировани  интервалов , причем i -и информационны вход устройства (1 1+2) подключен к информационному входу (2i-1)-ro блока элементов И, выход i -го сумматор а-вычитател  подключен к ин формационному входу блока эле ментов И, управл ющие входы элементов И с номерами (2i-1) и 2| подкл чены соответственно к пр мому и инверсному входам блока формировани  временньк интервалов, выходы (2J-1) го и 2j-го блоков элементов И через -и блок элементов ИЛИ подключены к входу {-го регистра, выходы (2|-1)-го и 2j-ro регистров ( подключены к входам j -го и (+2 ) го сумматоров-вычитателей, выходы р гистра  вл ютс  выходами устройства l. Недостатками устройства  вл ютс  его Ъложность и большие аппаратурны затраты на реализацию, так как устройство содержит 2 однотипных кан лов, причем аппаратурные затраты во растают с увеличением П. Кроме того обработка информации происходит не по мере постзтлени  значений исследуемого сигнгша, а только после прихода и записи всех выборок х,- в регистры устройства и далее значени  сигнала обрабатываютс  за At итераций , это приводит к задержке по влени  искомых коэффициентов на выходе устройства и следовательно . к уменьшению быстродействи  обработки в целом. Наиболее близким по технической супщости к изобретению  вл етс  iустройство дл  выполнени  быстрого преобразовани  Уолша (БПУ), содержащее 2 сумматора-вычитател  и 2 регистровых ОЗУ (объемом Л слов каждое), причем входы первого и вы 20 ходы второго сумматоров-вычитателей соединены с соответствующими входами первого регистрового ОЗУ, предназначенного дл  хранени  входных данных, а входы второго и выходы первого сумматоров-вьиитателей подключены к соответствующим выходам второго регистрового ОЗУ, предназначенного дл  хранени  промежуточных результатов. Дл  подготовки к обработке следующего вектора может быть использовано буферное ОЗУ, а вместо двух сумматоров-вычитателей - первый сумма тор-вьгчи та- тель и схемы коммутации, соединенные с соответствующими входами-выходами регистрового ОЗУ. В известном устройстве информаци  последовательно поступает во входное регистровое ОЗУ и затем на первый сумматор-вычитатель, в котором вычисл етс  сумма и разность последовательно поступающих пар выборок, а результаты записываютс  во второе регистровое ОЗУ, предназначенное дл  хранени  промежуточных результатов ,  вл ющихс  исходными на следующей итерации. Только после того, как входной регистр заполнитс  и будет получена сумма и разность последней пары выборок, происходит перекачка информации через второй сумматор-вычитатель в освободившийс  регистр, т.е. переход к следующей итерации и т.д. Паузы между приходом выборок дл  вычислений не используютс  2. Недостатками такого устройства  вл етс  низкое быстродействие, так как всего необходимо совершить n log2N шагов преобразований, считьша  последовательно все ОЗУ (N слов) и N слов нужно переписать из буферного ОЗУ, т.е. общее число one-. раций будет NXl+log N) и большой пам ти, так как требуетс  3 ОЗУ по N слов каждое. Цель изобретени  - повышение быстродействи  устройства (путем активного использовани  пауз между приходом выборок исследуемого сигнала дл  вычислений). Поставленна  цель достигаетс  тем, что в устройство, содержащее ервый и второй коммутаторы, суммаор-вычитатель и блок пам ти, прием первый информационный и управ-,  ющий входы первого коммутатора  вл ютс  соответственно информационным и синхронизирующим входами устройства, введены четыре регистра блок сравнени , блок посто нной пам ти, первый и второй счетчики, одновибратор и генератор тактовых импульсов , выход которого подключён к счетному входу первого счетчика, выход которого подключен к адресному входу блока посто нной пам ти, выход которого пвдключец к первому входу блока сравнени  и к информацио ным входам первого и второго регист ров, выходы которых подключены .соот ветственно к первому и второму ийформационным входам второго коммута тора, выход которого подключен тс адресному входу блока пам ти, выход которого подключен к информадиoHHbw входам третьего и четвертого регистров, выходы которых подключен соответственно к второму и третьему информационным входам первого коммутатора , первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитател , выход которого подключен к информационному входу бло ка пам ти, управл ющий вход второго коммутатора соединен с вторым входом блока сравнени  и подключен к выходу второго счетчика, счетный вход которого подключен к выходу одновибратора, вход которого  вл ет с  входом запуска устройства, а выход блока сравнени  подключен к управл ющему входу генератора тактовых импульсов. На фиг.1 представлена блок-схема устройства на фиг.2 - график преоб разовани  дл  п 4. Устройство содержит генератор 1 тактовых импульсов, одновибратор 2 счетчик 3 (на 2 состо ний), счетчик 4 (нап2 СОС-ЕОЯНИЙ), блок 5 посто нной пам ти, блок 6 сравнени , регистры 7 и 8, коммутатор 9, Элок 10 пам ти (ОЗУ на N слов), регистры 11 и 12, коммутатор 13, сумматор 14, а 2- значений дискрет ного входного сигнала обрабатываютс  последовательно по мере их поступлени , причем сумма и разность каждой пары выборок записьюаетс  на место этих же чисел в блок 10. Последовательность вьтолнени  операци суммировани -вычитани  задаетс  блоком 5 таким образом, что в паузах между приходом выборок производитс  дальнейша  обработка уже полученных промежуточных результатов на следующих итераци х в соответствии с графом преобразовани  (фиг.2). Таким образом, к моменту прихода последней выборки, больша  часть необходимого числа операций будет выполнена (на фиг.2 эта часть обведена пунктирной линией и выделена). Дл  получени  конечного результата останетс  вьтолнить 2(2 -1) операций вместо (п-1)2 , как в известном устройстве (без учета операций, св занных с использованием буферного ОЗУ). При этом вьшгрыш в быстродействии будет больше, чем в «/3 раз, где h - пор док преобразовани . Экономи  пам ти достигаетс  за счет того, что вместо двух ОЗУ на N слов каждое, используетс  одно ОЗУ на N слов и четыре регистра 7, 8, 11 и 12 или ОЗУ на четыре слова дл  промежуточного хранени  слагаемых и их адресов (на врем  выполне- ни  операций сложени -вычитани ). Сокращение объема пам ти составит 2/(1+4/N) раз, т.е. дл  больиих N достигаетс  экономи  пам ти почти в два раза. Устройство работает следующим образом . На информационный вход устройства последовательно поступает 2 численных значений (выборок) исследуемого дискретного сигнала. В момент прихода первой выборки по вл етс  сигнал готовности н входе устройства и срабатывает одновибратор 2, который запускает счетчик 3. На выходе счетчика 3 по вл етс  код адрё-. са, по которому в блок 10 записываетс  выборка Х(0). После прихода второй выборки на выходе счетчика 3 по вл етс  код адреса следующей  чейки в блоке 10 и т.д. Таким образом, счетчик 3 последовательно вьщает адреса  чеек блока 10, в которые записываютс  выборки и несет информацию о числе пришедших выборок. После окончани  процесса записи выборки в блок 10 включаетс  генератор 1, который запускает счетчик 4 и блок 5, на выходе которого по вл ютс  адреса  чеек блока 10, над содержимым которых нужно произвести операцию сложени -вычитани . S1 Адреса первого и второго слагаемых (вычитаемьк) запоминаютс  на врем  вьшолнени  операции в регистрах 7 и соответственно, а численные значе7 ни  слагаемых, извлекаемых из блока 10 - в регистрах 11 и 12. После выполнени  операции суммировани -вычитани  в сумматоре 14 результат сл жени  двух чисел записываетс  в бло 10 по адресу первого числа, который хранитс  в регистре 7, а результат вычитани  - по адресу второго числа хран щегос  .в регистре 8, Затем на выходе блока 5 по вл ютс  адреса но вой пары слагаемых, и выполн етс  следуювщй шаг преобразовани  и т.д. Чтобы схема не зашла вглубь блока 10, где еще не записаны выборки, в устройство введен блок 6 сравне ,ни , на входы которого поступает информаци  об адресах с выхода блока 5 и счетчика 3. При равенстве адресов на входах блока 6 сравнени  на .ее выходе по вл етс  сигнал, который останавливает генератор 1, и блок ждет прихода следующей выборки. С приходом выборки на входе по вл етс  сигнал, который вновь опрокидьшает одновибратор 2, состо ние счетчика 3 увеличиваетс  на единицу, и коммутатор 9 подключает выходы этого счет чика к адресному входу блока 10происходит процесс записи новой выборки , присутствующей на информацион ном входе и подаваемой через коммутатор 13 в соответствующую  чейку блока 10, по окончании которого одibOOO17000 2000 18 010 3001019 О О О 4001120 О 1 О

21О О 1О37

22О 1 1О38

23О О 1139

24О 1 1140

90100 25 1 О О О 41 1 О О О 57 О 1 О О

10О 1О 1

11О 11 О

12О 11 1

13О 1О О

14 а 1 10

15 о 1 о 1 160111

Така  последовательнйсть двоичных чисел может быть легко сформулирова10053О О1О

110541 О.1О .10155О О11

111561 О11

на с помощью четырех мультиплексоров, подключенных к второму счетчику 4 06 новибратор 2 восстанавливает свое состо ние, включаетс  генератор 1, и начинаетс  новьй этап вычислений. Особенность работы устройства заключаетс  в том, что в паузах между приходом выборок возможна обработка уже полученных промежуточных результатов на следующих итераци х. Эта возможность сквозного прохождени  по итераци м обеспечиваетс  определенной последовательностью формировани  адресов слагаемых, котора  задаетс  блоком 5 посто нной .пам ти. Адреса на выходе блока 5 по вл ютс  в следующей последовательности (дл  эта последовательность легко получаетс  из графа преобразовани , приведенного на фиг.2): 0,1,2,3, 0,2,1,3, 1-  итераци  2-  итераци  4,5,6,7 4,6,5,7, - 0,4,1,5,2,6,3,7 1-  ите- 2-  ите- 3-  итераци  раци  раци  8,9,10,11, 8,10,9,11 1-  ите- . 2-  итерараци  ци  12,13,14,15 12,14,13,15, 1-  Итера- 2-  итераци  ци  8,12,9,13,10,14,11,15 3-  итераци  0,8,1,9,2,10,3,11,4,12,5,13,6,14,7,15 4-  итераци  Эти адреса ОЗУ на выходе блока 5 должны быть получены в двоичном представлении , т.е. в следующем виде: 1 1 О О 49 О О О О 1 1 1 1 50 1 О О О 51О О О 1 52О О О 1 7 . на n- 2 состо ний (на 64 состо ни  дл  ). По окончании вычислений в  чейIках блока 10 записываютс  результирующие значени  коэффициентов преоб разовани  Уолша. Таким образом, предлагаемое устоойство позвол ет увеличить быстро208 действие вьтолнени  БПУ путем активного использовани  пауз между выборками дл  продолжени -вьиислений в .и/3 раз, где п log2N - пор док преобразовани , и уменьшить объем пам ти почти в два раза (дл  больших N), причем выигрыш тем больше, чем больше размер входного вектора.

иг.1

CW(D)

Claims (1)

1. УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША, содержащее первый и второй коммутаторы, сумматор—вычитатель и блок памяти, причем первый информационный и управляющий входы первого коммутатора являются соответственно информационным и синхронизирующим входами устройства, отличающееся тем, что, с целью повышения быстродействия, в него введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор тактовых импульсов, выход которого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к первому входу блока сравнения и к информационным входам первого и вто рого регистров, выходы которых подключены соответственно к первому и второму информационным входам второго коммутатора, выход которого подключен к адресному входу блока памятй, выход которого подключен к информационным входам третьего и чет вертого регистров, выходы которых подключены соответственно к второму 5' и третьему информационным входам первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитателя, выход которого подключен к информационному входу блока памяти, управляющий вход вто- рого коммутатора соединен с вторым входом блока сравнения и подключен к выходу второго счетчика, счетный вход которого подключен к выходу одновибратора, вход которого является входом запуска устройства, а выход блока сравнения подключен к управляющему входу генератора тактовых импульсов .

   1 1141420