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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 4(5 Ц 6 06 Р 15/332 ЗФЕЮМФЗКФГ тл ЮУ ОПИСАНИЕ ИЗОБРЕТЕНК АВТОРСКОМУ СВИДЕТЕЛЬСТВУГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬ(71) Северо-Кавказский ордена Дружбы народов горно-металлургический институт(56) 1. Авторское свидетельство СССР Р 951320, кл. С 06 Р 15/332, 1982.2. Ракоииц В.С, и др. Специализи- . рованные микропроцессоры, реализующие быстрые преобразования.-В кн. Цифровая обработка сигналов и ее применение. М., "Наука", 1981, с. 206- 217 (прототип),(54) (57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША, содержащее первый и второй коммутаторы, сумматор-вычитатель и блок памяти, причем первый информационный и управляющий входы первого коммута тора являются соответственно информационным и синхронизирующим входами устройства, о т л и ч а ю щ е - е с я тем, что, с целью повыщения быстродействия, в него введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор,801 4142 тактовых импульсов, выход которогоподключен к счетному входу первогосчетчика, выход которого подключенк адресному входу блока постояннойпамяти, выход которого подключен кпервому входу блока сравнения и кинформационным входам первого и второго регистров, выходы которых подключены соответственно к первому ивторому информационным входам второго коммутатора, выход которогоподключен к адресному входу блокапамяти, выход которого подключен кинформационным входам третьего и четвертого регистров, выходы которыхподключены соответственно к второмуи третьему информационным входампервого коммутатора, первый и второйвыходы которого подключены соответственно к первому и второму входамсумматора-вычитателя, выход которого подключен к информационному входублока памяти, управляющий вход второго коммутатора соединен с вторымвходом блока сравнения и подключен квыходу второго счетчика, счетныйвход которого подключен к выходу одновибратора, вход которого являетсявходом запуска устройства, а выходблока сравнения подключен к управляющему входу генератора тактовых импульсов.1 1141Изобретение относится к автоматике и вычислительной технике и может ,быть использовано в аппаратуре цифровой обработки низкочастотных сигналов (для спектрального анализа исинтеза, цифровой фильтрации.и т.д.).Известно устройство ортогонального преобразования цифровых сигналов по Уолшу-Адамару, содержащее й групп сумматоров-вычитателей по 2 сумма торов-вычитателей в каждой группе и устройства, содержащие 2 сумматоИ ров-вычитателей, 2" регистров, 2" блоков элементов ИЛИ и 2блоков элементов И и блок формирования ин тервалов, причем.-й информационный вход устройства (=1+2") подключенк информационному входу (2 -1)-го блока элементов И, выход-го сумматора-вычитателя подключен к ин О формационному входу 2 -го блока элементов И, управляющие входы элемен-. тов И с номерами (2-1) и 21 подключены соответственно к прямому и инверсному входам блока формирования 25 временных интервалов, выходы (21-1) - . го и 2 -го блоков элементов И через ( -й блок элементов ИЛИ подключены к входу 1 -го регистра, выходыФ ф-1 (2-1)-го и 2-го регистров (=1+2 ) 3 О подключены к входам ) -го и +.2" 1)- го сумматоров-вычитателей, выходы регистра являются выходами устройства Я.Недостатками устройства являются его сложность и большие аппаратурные затраты на реализацию, так как устройство содержит 2 однотипных канаОлов, причем аппаратурные затраты возрастают с увеличением 0 Кроме то 4 р го,обработка информации происходит не по мере поступления значений исследуемого сигнала, а только после прихода и записи всех выборок х; в регистры устройства и далее значения сигнала обрабатываются эа Ф итераций, это приводит к задержке появления искомых коэффициентов на выходе устройства и следовательно к уменьшению быстродействия обработки в целом,Наиболее близким по техническойсущности к изобретению являетсяустройство для выполнения быстрогопреобразования Уолша (БПУ), содержащее 2 сумматора-вычитателя и 2регистровых ОЗУ (объемом Ж словкаждое), причем входы первого и вы 420ходы второго сумматоров-вычитате" лей соединены с соответствующими входами первого регистрового ОЗУ, предназначенного для хранения входных данных, а входы второго и выходы первого сумматоров-вычитате" лей подключены к соответствующим выходам второго регистрового ОЗУ, предназначенного для хранения промежуточных результатов. Для подготов- ки к обработке следующего вектора может быть использовано буферное ОЗУ, а вместо двух сумматоров-вычитателей - первый сумматор-вычитатель и схемы коммутации, соединенные с соответствующими входами-выходами регистрового ОЗУ, В известном устройстве информация последовательнопоступает во входное регистровое ОЗУ и затем на первый сумматор-вычитатель, в котором вычисляется сумма и разность последовательно поступающих пар выборок, а результаты записываются во второе регистровое ОЗУ, предназначенное для хранения промежуточных результатов, являющихся исходными на следующей итерации. Только после того, как входной регистр заполнится и будет получена сумма и разность последней пары выборок, происходит перекачка информации через второй сумматор-вычитатель в освободившийся регистр, т,е, переход к слеДующей итерации и т.д. Паузы между приходом выборок для вычислений не используются 21.Недостатками такого устройства является низкое быстродействие, так как всего необходимо совершить п=1 оя 2 И шагов преобразований, считывая последовательно все ОЗУ (И слов) и И слов нужно переписать из буферного ОЗУ, т,е. общее число опе-. раций будет Ы(1+1 ор И) и большой объем памяти, так как требуется 3 ОЗУ по М слов каждое.Цель изобретения - повышение быстродействия устройства (путем активного использования пауз между приходом выборок исследуемого сигнала для вычислений).Поставленная цель достигается тем, что в устройство, содержащее первый и второй коммутаторы, сумматор-вычитатель и блок памяти, при;чем первый информационный и управ-. ляющий входы первого коммутатора420 4 Устройство содержит генератор 1тактовых импульсов, одновибратор 2,счетчик 3 (на 2 состояний) счетйЭчик 4 (на и 2 состояний), блок 5 45постоянной памяти, блок 6 сравнения, регистры 7 и 8, коммутатор 9,блок 10 памяти (ОЗУ на И слов),регистры 11 и 12 коммутатор 13,сумматор 14, а 2 значений дискретного входного сигнала обрабатываются последовательно по мере их поступления, причем сумма и разностькаждой пары выборок записывается наместо этих же чисел в блок 10. Последовательность выполнения операцийсуммирования-вьиитания задаетсяблоком 5 таким образом, что в пау 3. 1141 являются соответственно информаци- ,ь онным и синхронизирующим входами устройства, введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор тактовых- импульсов, выход котоРого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока постоянной памяти, 10 выход которого подключен к первому входу блока сравнения и к информационным входам первого и второго регистров, выходы которых подключены .соответственно к первому и второму ин формационным входам второго коммутатора, выход которого .подключен к адресному входу блока памяти, выход которого подключен к информаци-. онным входам третьегои четвертого регистров, выходы которых подключены соответственно к второму и третьему информационным входам первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вьиитателя, выход которого подключен к информационному входу бло-. ка памяти, управляющий вход второго коммутатора соединен с вторым входом блока сравнения и подключен к выходу второго счетчика, счетный вход которого подключен к выходу . одновибратора, вход которого является входом запуска устройства, а выход блока сравнения подключен к управляющему входу генератора тактовых импульсов.На фиг.1 представлена блок-схема устройства; на фиг.2 - график преобразования для й =4.40 зах между приходом выборок производится дальнейшая обработка уже полученных промежуточных результатов на следующих итерациях в соответствии с графом преобразования (фиг.2).Таким образом, к моменту прихода последней выборки, большая часть не-. обходимого числа операций будет выполнена (на фиг.2 эта часть обведена пунктирной линией и выделена). Для получения конечного результата. останется выполнить 2(2 -1) операйций вместо (и) 2" , как в известном устройстве (без учета операций, связанных с использованием буферного ОЗУ)При этом выигрыш в быстродействии;будет больше, чем в п/3 раз, где И - порядок преобразования. Экономия памяти достигается за счет того, что вместо двух ОЗУ на Б слов каждое, используется одно ОЗУ на Я слов и четыре регистра 7, 8, 11 и 12 или ОЗУ на четыре слова для промежуточного хранения слагаемых и их адресов (на время выполнения операций сложения-вычитания). Со кращение объема памяти составит 2/(1+4/М) раз, т.е, для больших И достигается экономия памяти почти в два раза.Устройство работает следующим образом.Яа информационный вход устройства последовательно поступает 2 числ ленных значений (выборок) исследуемого дискретного сигнала. В момент прихода первой выборки появляется сигнал готовности на входе устройства и срабатывает одновибратор 2, который запускает счетчик 3. На выходе счетчика 3 появляется код адреса, по которому в блок 10 записывается выборка Х(0), После прихода второй выборки на выходе счетчика 3появляется код адреса следующейячейки в блоке 10 и т.д. Таким образом, счетчик 3 последовательно выдает адреса ячеек блока 10, в которые записываются выборки и несет информацию о числе пришедших выборок, После окончания процесса записи выборки в блок 10 включается генератор 1, который запускает счетчик 4 и блок 5, на выходе которого появляются адреса ячеек блока 10, над содержимым которых нужно произвести операцию сложения-вычитания.1141420 5 0 0 0 0 21 О 0 1 0 37 1 1 0 0 53 0 0 1 0 6 0 0 1 0 22 0 1 1 О 38 1 1 1 О 54 1 0 .1 0 7 0 О 0 1 23 0 0 139 1 1 0 1 55 0 0 1 1 8 О О 1 1 24 О 1 1 1 40 11 1 56 1 О 1 1 9 0 1 0 0 25 1 0 0.0 41 1 0 0 .0 57 0 1 0 0 10 О 1 О 1 26 1 О О 1 11 0 1 1 0 270 1 0 12 01 1 28 1 0 1 1 13 00 0 29 1 0 0 0 140110 301010 150101 311001 160111 321011Такая последовательность двоичных чисел может быть легко сформулирова 42 1 1 0 0 58 43 1 0 О 1 59 44 1 1 0 1 60 45 1 0 1 0 61 46 1 1 1 0 62 47 1 0 1 1 63 48 1 1 1 1 64на с помощью подключенных 110001011101011011100111111 четырех мультиплексоровк второму счетчику 4 Адреса первого и второго слагаемых новибратор 2 восстанавливает свОе (вычитаемых) запоминаются на время состояние, включается генератор 1, и выполнения операции в регистрах 7 и 8 начинается новый этап вычислений. соответственно, а численные значения слагаемых, извлекаемых из блока 5 Особенность работы устройства 10 - в регистрах 11 и 12. После вы-. заключается в том, что в паузах межполнения операции суммирования-вы- ду приходом выборок возможна обрачитания в сумматоре 14 результат сло- ботка уке полученных промежуточных жения двух чисел записывается в блок результатов на следующих итерациях.10 по адресу первого числа, который 1 О Эта возможность сквозного прохождехранится в регистре 7, а результат . ния по итерациям обеспечивается опревычитания - по адресу второго числа, деленной последовательностью формихранящегося в регистре 8. Затем на рования адресов слагаемых, которая выходе блока 5 появляются адреса но- задается блоком 5 постоянной памяти. вой пары слагаемых, и выполняется 15 Адреса на выходе блока 5 появляются следующий шаг преобразования и т.д. в следующей последовательностиЧтобы схема не зашла вглубь бло- (длЯ Я=16 эта последовательность ка 10, где еще не записаны выборки, легко получается из графа преобразов устройство введен блок 6 сравне- вания, приведенного на фиг.2): ния, на ВхОДы котОРОГО пОступает ин 023 023 формация об адресах с выхода блока 1-я итерация 2-я итерация 5 и счетчика 3При равенстве адре 4,6,5,7,0,4,1,5,2,6,3,7 сов на входах блока 6 сравнения на 1-я ите-я ите-3-я итерация .ее выходе появляется сигнал, который Рация рация останавливает генератор 1, и блок 25 8,9,10,11, 8,10,9,11 ждет прихода следующей выборки. С 1-я ите- , 2-я итера- приходом выборки на входе появляется Рация ция сигнал, который вновь опрокидывает 12,13,14,15 12,14, 13,15, одновибратор 2, состояние счетчика1-я итера-я итера увеличивается на единицу, и коммуция татор 9 подключает выходы этого счет,12,9,13,10,14,11,15 чика к адресному входу блока 10 - , 3-я итерация происходит процесс записи новой вы- , 0,8,1,9,2, 10,3,11,4,12,5,13,6,14,7,15 борки, присутствующей на информацион-я итерация ном входе и подаваемой через комму 35Эти адреса ОЗУ на выходе блока 5 татор 3 в соответствующую ячейку, должны быть получены в двоичном пред- блока 10, по окончании которого од- ставлении, т.е. в следующем виде:1 О О О 0 17 О О О О 33 1 1 О О 49 О О О О2 0 0 0 1 18 0 1 0 0 34 1 1 1 1 50 1 0 0 030010 190001 351110 51000140011 200101 361111 5200017 1141420 8 на п 2" состоянии (на 64 состояния действие выполнения БПУ путем активдля И=16). ного использования пауз между выПо окончании вычислений в ячей- . борками для продолжения вычислений ках блока 10 записываются результи- н и /3 раз где .и =1 оя Н - порядокф г рующие значения коэффициентов преоб" 5 преобразования, и уменьшить объем разования Уолша, памяти почти в два раза (для больТаким образом, предлагаемое уст- ших В), причем выигрыш тем больше, оойство позволяет увеличить быстро- чем больше размер входного вектора.1