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

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, по окончании которого одibOOO170002000 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)