Устройство для выполнения быстрого преобразования уолша
УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША, содержащее первый и второй коммутаторы , сумматор-вычитатель и блок памяти , причем первьй информационный и управляющий входы первого коммутатора являются соответственно информационным и синхронизирующим входами устройства, отличающееся тем, что, с целью повьшения быстродействия, в него введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор тактовых импульсов, выход которого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к первому входу блока сравнения н к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому и второму информационным входам второго коммутатора, выход которого подключен к адресному входу блока памяти, выход которого подключен к информационным входам третьего и четвертого регистров, выходы которых подключены соответственно к второму и третьему информационным входам Ы первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитателя, вькод которого подключен к информационному входу блока памяти, управляющий вход второго коммутатора соединен с вторым входом блока сравнения и подключен к выходу второго счетчика, счетный вход которого подключен к выходу одновибратора , вход которого является входом запуска устройства, а выход блока сравнения подключен к управляющему входу генератора тактовых импульсов .
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
4(s1) G 06 F 15/332
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ABTOPCKOMV СВИДЕТЕЛЬСТВУ . ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫПФ (21) 3645820/24-24 (22) 27.09.83 (46) 23.02.85. Бюл. У 7 (72) Н.В.Бебих, А.И.Денисов и А.А.Саурин . (71) Северо-Кавказский ордена Дружбы народов горно-металлургический институт (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР
Р 951320, кл. G 06 F 15/332, 1982.
2. Ракоииц В.С. и др. Специализи- . рованные микропроцессоры, реализующие быстрые преобразования.-В кн.
Цифровая обработка сигналов и ее применение ° M., "Наука", 1981, с ° 206217 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ
БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША, содержащее первый и второй коммутаторы, сумматор-вычитатель и блок памяти, причем первый информационный и управляющий входы первого коммутатора являются соответственно информационным и синхронизирующим входами устройства, о т л и ч а ю щ е— е с я тем, что, с целью повыщения быстродействия, в него введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор
„„SU„„1 4142 А тактовых импульсов, выход которого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к первому входу блока сравнения и к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому и второму информационным входам второго коммутатора, выход которого подключен к адресному входу блока памяти, выход которого подключен к информационным входам третьего и четвертого регистров, выходы которых подключены соответственно к второму и третьему информационным входам первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитателя, выход которого подключен к информационному входу блока памяти, управляющий вход второго коммутатора соединен с вторым входом блока сравнения и подключен к выходу второго счетчика, счетный вход которого подключен к выходу одновибратора, вход которого является входом запуска устройства, а выход блока сравнения подключен к управляющему входу генератора тактовых импульсов.
I 1141
Изобретение относится к автоматике и вычислительной технике и может ,быть использовано в аппаратуре цифровой обработки низкочастотных сигналов (для спектрального анализа и синтеза, цифровой фильтрации.и т.д.).
Известно устройство ортогонального преобразования цифровых сигналов по Уолшу-Адамару, содержащее h групп сумматоров-вычитателей по 2 сумма- 10 торов-вычитателей в каждой группе и устройства, содержащие 2 сумматоИ ров-вычитателей, 2" регистров, 2" блоков элементов ИЛИ и 2 блоков
n r элементов И и блок формирования ин- 15 тервалов, причем. -й информационный вход устройства (=1+2") подключен к информационному входу (21-1)-ro блока элементов И, выход < --го сумматора-вычитателя подключен к ин- 2п формационному входу 2 -ro блока элементов И, управляющие входы элемен-. тов И с номерами (21-1) и 21 одключены соответственно к прямому и инверсному входам блока формирования временных интервалов, выходы (21-1)— . го и 2 -ro блоков элементов И через < --й блок элементов ИЛИ подклю Ф чены к входу -го регистра, выходы
A-1 (2 -1)-го и 21-го регистров (I =1+2 ) 3О подключены к входам ) -ro и ()+-2" 1)1 о сумматоров-вычитателей, выходы регистра являются выходами устройства (1) .
Недостатками устройства являются
его сложность и большие аппаратурные . затраты на реализацию, так как устройство содержит 2 однотипных кана0 лов, причем аппаратурные затраты возрВ.cTaI0T с ув еличен нем и Кроме то 40 го,обработка информации происходит не по мере поступления значений исследуемого сигнала, а только после прихода и записи всех выборок х; в регистры устройства и далее значения сигнала обрабатываются эа Ф итераций, это приводит к задержке появления искомых коэффициентов на выходе устройства и следовательно к уменьшению быстродействия обработки в целом.
Наиболее близким по технической сущности к изобретению является устройство для выполнения быстрого преобразования Уолша (БПУ), содержащее 2 сумматора-вычитателя и 2 регистровых ОЗУ (объемом Ж слов каждое), причем входы первого и вы420 ходы второго сумматоров-вычитателей соединены с соответствующими входами первого регистрового ОЗУ, предназначенного для хранения входных данных, а входы второго и выходы первого сумматоров-вычитателей подключены к соответствующим выходам второго регистрового ОЗУ, предназначенного для хранения промежуточных результатов. Для подготов- ки к обработке следующего вектора может быть использовано буферное
ОЗУ, а вместо двух сумматоров-вычитателей — первый сумматор-вычитатель и схемы коммутации, соединенные с соответствующими входами-выходами регистрового ОЗУ. В известном устройстве информация последовательно поступает во входное регистровое ОЗУ и затем на первый сумматор-вычитатель, в котором вычисляется сумма и разность последовательно поступающих пар выборок, а результаты записываются во второе регистровое ОЗУ, предназначенное для хранения промежуточных результатов, являющихся исходными на следующей итерации. Только после того, как входной регистр заполнится и будет получена сумма и разность последней пары выборок, происходит перекачка информации через второй сумматор-вычитатель в освободившийся регистр, т.е. переход к слеДующей итерации и т.д. Паузы между приходом выборок для вычислений не используются (2) .
Недостатками такого устройства является низкое быстродействие, так как всего необходимо совершить
n=log2N шагов преобразований, считывая последовательно все ОЗУ (И слов) и N слов нужно переписать из буферного ОЗУ, т.е. общее число опе-. раций будет Ы(1+1од И) и большой объем памяти, так как требуется
3 ОЗУ по М слов каждое.
Цель изобретения — повышение быстродействия устройства (путем активного использования пауз между приходом выборок исследуемого сигнала для вычислений).
Поставленная цель достигается тем, что в устройство, содержащее первый и второй коммутаторы, сумматор-вычитатель и блок памяти, при;чем первый информационный и управ-. ляющий входы первого коммутатора
420 4
Устройство содержит генератор 1 тактовых импульсов, одновибратор 2, счетчик 3 (на 2 состояний) счетИ
Э чик 4 (на и 2 состояний), блок 5 45 постоянной памяти, блок 6 сравнения, регистры 7 и 8, коммутатор 9, блок 10 памяти (ОЗУ на N слов), регистры 11 и 12 коммутатор 13, сумматор 14, а 2 значений дискрет- 50 ного входного сигнала обрабатыва ются последовательно по мере их поступления, причем сумма и разность каждой пары выборок записывается на
1 место этих же чисел в блок 10. По- 55 следовательность выполнения операций суммирования-вычитания задается блоком 5 таким образом, что в пау3 1141 являются соответственно информационным и синхронизирующим входами устройства, введены четыре регистра, блок сравнения, блок постоянной памяти, первый и второй счетчики, одновибратор и генератор тактовыхимпульсов, выход которого подключен к счетному входу первого счетчика, выход которого подключен к адресному входу блока постоянной памяти, выход которого подключен к первому входу блока сравнения и к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому и второму информационным входам второго коммутатора, выход которого подключен к адресному входу блока памяти, выход которого подключен к информаци-. онным входам третьего и четвертого регистров, выходы которых подключены соответственно к второму и третьему информационным входам первого коммутатора, первый и второй выходы которого подключены соответственно к первому и второму входам сумматора-вычитателя, выход которого подключен к информационному входу бло-. ка памяти, управляющий вход второго коммутатора соединен с вторым входом блока сравнения и подключен к выходу второго счетчика, счетный вход которого подключен к выходу . одновибратора, вход которого является входом запуска устройства, а выход блока сравнения подключен к управляющему входу генератора тактовых импульсов.
На фиг.1 представлена блок-схема устройства; на фиг. 2 — график преобразования для и =4.
40 зах между приходом выборок производится дальнейшая обработка уже полученных промежуточных результатов на следующих итерациях в соответствии с графом преобразования (фиг.2).
Таким образом, к моменту прихода последней выборки, большая часть не-. обходимого числа операций будет выполнена (на фиг.2 эта часть обведена пунктирной линией и выделена).
Для получения конечного результата. останется выполнить 2(2 -1) операй ций вместо (n-1) 2", как в известном устройстве (без учета операций, связанных с использованием буферного ОЗУ) ° При этом выигрыш в быстродействии;будет больше, чем в п/3 раз, где И вЂ” порядок преобразования. Экономия памяти достигается за счет того, что вместо двух ОЗУ на
N слов каждое, используется одно
ОЗУ на N слов и четыре регистра 7, 8, 11 и 12 или ОЗУ на четыре слова для промежуточного хранения слагаемых и их адресов (на время выполнения операций сложения-вычитания). Со. кращение объема памяти составит
2/(1+4/N) раз, т.е. для больших N достигается экономия памяти почти в два раза.
Устройство работает следующим образом.
Яа информационный вход устройства последовательно поступает 2 чиси ленных значений (выборок) исследуемого дискретного сигнала. В момент прихода первой выборки появляется сигнал готовности на входе устройства и срабатывает одновибратор 2, который запускает счетчик 3. На выходе счетчика 3 появляется код адреса, по которому в блок 10 записывается выборка X(O). После прихода второй выборки на выходе счетчика 3 появляется код адреса следующей ячейки в блоке 10 и т.д.
Таким образом, счетчик 3 последовательно выдает адреса ячеек блока
10, в которые записываются выборки и несет информацию о числе пришедших выборок. После окончания процесса записи выборки в блок 10 включается генератор 1, который запускает счетчик 4 и блок 5, на выходе которого появляются адреса ячеек блока 10, над содержимым которых нужно произвести операцию сложения-вычитания.
1141420
7 О О О 1 23 О О 1 39 1 1 О 1 55 О О 1 1
8 0 0 1 1 24 0 1 1 1 40 1 t 1 1 56 1 0 f 1
9 О 1 О О 25 1 О О.О 41 1 О О .О 57 О 1 О О
100101 261001
11 О 1 1 О 27 1 О 1 О
t20111 281011
140110 301-010
150101311001
16 О 1 1 1 32 1 О 1 1
Такая последовательндсть двоичных чисел может быть легко сформулирова42 1 1 0 О 58
43 1 0 О 1 59
44 1 1 О 1 60
45 1 О 1 О 61
46 1 1 1 О 62
47101163
48 1 1 1 f 64 на с помощью подключенных
0101
1101
1 1 f О
011 f
1 1 1 1 четырех мультиплексоров, к второму счетчику 4
Адреса первого и второго слагаемых новибратор 2 восстанавливает свОе (вычитаемых) запоминаются на время состояние, включается генератор 1, и выполнения операции в регистрах 7и Я начинается новый этап вычислений, соответственно, а численные значения слагаемых, извлекаемых из блока 5 Особенность Работы УстРойства
10 — в регистрах 11 и 12. После вы-. заключаетсЯ в том, что в паУзах межполнения операции суммирования-вы- ду приходом выборок возможна обрачитания в сумматоре 14 результат сло- ботка уке полученных промежуточных кения двух чисел записывается в блок РезУльтатов на слеДУюЩих итеРаЦиЯх.
10 по адресу первого числа, который 10 Эта возможность сквозного пРохождехранится в регистре 7, а результат . ниЯ по итеРациЯм обеспечиваетсЯ опревычитания — по адресу второго числа, Деленной послеДовательностью формихранящегося в регистре 8. Затем на рования адресов слагаемых, которая выходе блока 5 появляются адреса но- задается блоком 5 постоянной памяти. вой пары слагаемых, и выполняется 15 Адреса на выходе блока 5 появляются следующий шаг преобразования и т.д. в следующей последовательности
Чтобы схема не зашла вглубь бло- (длЯ Я=16 эта последовательность ка 10, где еще не записаны выборки, легко полУчаетсЯ из гРафа пРеобРазов устройство введен блок 6 сравне- вания, приведенного на фиг.2): ния» на Входы KGTopoI" o поступает ин- 20 О» !» 2» 3 0» 2» 3» формация об адресах с выхода блока 1-Я итеРациЯ 2-Я итеРациЯ
5 и счетчика 3 ° При равенстве адре- 4 5»6»7 4,6,5,7» 0,4,1,5,2,6,3,7 сов на входах блока 6 сравнения на я ите- 2-я ите- 3-я итерация .ее выходе появляется сигнал, который Рация рация останавливает генератор 1, и блок 25 8»9°, 10 11» 8,10,9,11 ждет прихода следующей выборки. С 1-я ите- . 2-я итераприходом выборки на входе появляется Рация ция сигнал, который вновь опрокидывает 12» 13, 14, 15 12, 14, 13, t 5, одновибратор 2, состояние счетчика 1-я итера- 2-я итера3 увеличивается на единицу, и комму- 3Q ция татор 9 подключает выходы этого счет- 8,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 борки, присутствующей на информацион- 4-я итерация ном входе и подаваемой через комму35
Эти адреса ОЗУ. на выходе блока 5 татор 13 в соответствующую ячейку, . должны быть получены в двоичном предблока 10, по окончании которого од- ставлении, т.е. в следующем виде:
1 О О О О 17 О О О О 33 1 1 О О 49 О О О 0
2000 1180100341111501000
3 О О 1 О 19 О О О 1 35 1 1 1 О 51 О О О 1
40011 200101 361111 520001
7 1141420 8 на и 2" состоянии (на 64 состояния действие выполнения БПУ путем активдля N=16) . ного использования пауз между выПо окончании вычислений в ячей- . борками для продолжения вычислений ! ках блока 10 записываются результи- в,п /3 раз где . и =log N — порядок
2 рующие значения коэффициентов преоб- 5 преобразования, и уменьшить объем разования Уолша. памяти почти в два раза (для больТаким образом, предлагаемое уст- ших N5 причем выигрыш тем больше, войство позволяет увеличить быстро- чем больше размер входного вектора.
1141420
Корректор Е. Сирохман
Х(0
Х(1) Х(2), Мз)
X(O)
Ф5) х(6)
Х(72
Х(д)
Х(9)
X(1D)
Х(11)
А (12)
Х(13)
xpg)
Х(15) Составитель А..Баранов
Редактор P.Öèöèêà Техред Л.Иикеш
Заказ 497/37 Тираж 710 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ППП "Патент", r. Ужгород„ ул. Проектная, 4
Cw(0)
C (l)
Cw(2)
С„„(3)
ce(4)
С,„(5)
Ср (б)
СвР) с (8)
cw(9)
C (1P)
СмО1/
Си (12)
Сиi(15)
Св(14)
C (15>
