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

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

Иллюстрации

Показать все

Реферат

 

БЛОК ФОРМИРОВАНИЯ АДРЕСОВ ДЛЯ УСТРОЙСТВА, РКАЛИЗУЮЩЕГО БЫСТРОЕ ПРЕОБРАЗОВАНИЕ YOJllllA, содержащий регистр, первый счетчик, п(ы 2, где Ы - размер преобразования элементо1з ИЛИ, ныходы которых подключены соответственна к разрядам перього информационного входа мультиплексора, выход которого является информационным выходом блока, разряды второго информационного входа мультиплексора соединены соответс- -венн( с разрядными выходами первого счетчика, счетный вход которого является первым синхровходом , а ггервые входы у элеменчов ИЧИ являются 1рупг1ой информационных входов блока, отличаю щ и йс я тем, что, с целью повышения быстродействия, в него введены второй счетчик, - I) э.пеме1Г1ов И и (п -2) элементов ИЛИ, причем выход i-го (г 2ii) разряда второго счетчика соединен с первыми входами

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИН аю 00 (51) G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЭОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И ABT0PCHOMV СВИДЕТЕЛЬСТВУ (21) 3563932/18-24 (22) 14.03.83 (46) 23.07.84.Бюл. 1 27 (72) П.Н.Гринчук, Ф.Е.Коркмаэский и А.M.ØàðàôàH (71)Специальное конструкторскотехнологическое бюро вычислительной техники (53) 681.32(088.8) (56) 1. Хартмут Х.Ф. Передача информации ортогональными функциями, И., "Связь", 1975, с. 42,88.

2. Авторское свидетельство СССР

548863, кл. G 06 F !5/332, 1975 (прототип). (54) (57) БЛОК ФОР11ИРОВА111И А11РЕСОВ

ДЛЯ УСТРОЙСТВА, РЕАЛИЗУЮЩЕГО БЫСТ1 ОЕ

Пl ЕОБРАЗОВАНИЕ УОЛШ1А, содержащий регистр, первый счетчик, р(и =2, где размер преобразования) элементогз

1г11И, выходы которых подключены соответстнегггго к разряд»м первого информационного входа мультиплексора, выход которого является информационным выходом блока, разряды второго информационггого вход» мультиплексора соединены соответственно с разрядными выходами первого счетчика, счетный вход которого является первым синхровходом, а первые Hxopl,l Q o»oìLèòoâ

ИЛИ являются группой информационных входов блока, о т JI и ч а ю Il(и йс я тем, что, с целью повышеггггя быстродействия, н него ггггедсггы второй счетчик, 2w — 11 элг ментов И и (n -21 элементов ИЛИ, причем выход ъ-го (2 ) разряда второго счетчика соединен с первыми входами (2i -31-го и (2i-21-го элементов И, выходы 2) -го и(2j+ l) -го() =l, гг-21 элементов И подключены соответственно к первому и второму входам (j

И соединены с вторыми входами соответственно первого и р — го элементов

1ГЛИ и подключены соответственно к первому и 0 -му разрядам третьего информационного входа мулы иплекстора, разряды четвертого информационного входа которого соединены соответствен но с разрядными выходами второго с гетг ыгг вход KoTopoI o ется вторым синхровходом блока, прямой выход К вЂ” го (1г=1, ) разряда регистра соединен с вторым входом 2К-го элемента И, второй вход (2Y †11 -ro элемента И подключен к инверсному выходу К-го разряда регистра, вход установки в ноль которого подключен к первому информ»циониому входу блока а вход уст;гновки в единицу (-po (11 =1, 1) разряда регистра соедииеH с

rn-м(щ=2,,„) информационным входом группы блока, управляющий вход мультиплексора является входом задания режима блока.

110452б

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

Уалша.

Известно устройство, реализующее алгоритм. быстрого преобразования

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

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

Уолша.

Наиболее близким по технической сущности к изобретению является блок формирования адресов для устройства, реализующсга быстрое преабра30 эование Фурье, содержащий счетчик, регистр, группу элементов IDIII, и узел выдачи адресов, первый и второй входы котацого соединены саответствен но с выходами группы элементов ИЛИ и счетчика, счетный вход которого является счетным входом блока, выход узла выдачи адресов является информационным выходом блока, а первые входы элементов ИЛИ являются группой информационных входов блока Г2 1, Однако при применении его в качестве адресного блока в устройстве быстРого преобразования Уолша в результате преобразования получаются коэффициенты преобразования, упорядоченные по Адамару и расположенные не в порядке возрастания частасти., Это следует иэ того, чта графы быстрого преобразования Фурье и Уолша-Адамара совпадают. 50

При спектральном анализе сигналов желательно, чтобы коэффициенты преобразования располагались в по:рядке возрастания частости.

Это упрощает получение спектра

55 мощности сигналов да простого суммирования квадратов соседних коэффициентов.

Лереупорядочение коэффициентов преобразования Уолша-Адамара по частости при использовании известного блока в качестве адресного блока устройства быстрого преабрвазования

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

Цель изобретения — повышение быстродействия.

Указанная цель достигается тем, что в блок формирования адресов для устройства, реализующего быстрое преобразование Уолша,содержащий регистр, первый счетчик, (N =2 где N — размер преобразования1элементов ИЛИ, выходы которых подключены соответственно к разрядам первого информационного входа мультиплексора выход которого является информационным выходом блока, разряды второго информационного входа мультиплексора соединены соответственно с разрядными выходами первого счетчика, счетный вход которого является первым синхровхоцом, а первые входы 0 элементов

HJiH являются группой информационных входов блока, введены второй счетчик, 2 — 1) элементов И и М -2) элементов

ИЛИ, причем выход 1, -го (i -2,и) раз ряда второго счетчика соединен с первыми входами (2 ъ — 3) -го и фъ-2) -го элементов И, выходы 2 -го и (2 +1) -го

Я =1,A -2) элементов И подключены соответственно к первому и второму входам (i< )-го элемента ИЛИ, выход которого соединен с )+ I) -м разрядом третьего информационного входа мультиплексора и подключен к второму входу(+1) -го элемента ИЛИ, выходы первого и

2(и -1) -га элементов И соединены с вторыми входами соответственно первого и и -го элементов ИЛИ и подключены соответственно к первому и h -му разрядам третьего информационного входа мультиплексора, разряды четвертого информационного входа которого соединены соответственно с раз рядными выходами в торо го счетчика, счетный вход которого является вторым синхровходом блока, прямой выход К -га(К=I, 6 — 1 разряда регистра соединен с вторым входом 2к-го элемента И, второй вход 1.2к-!) -го элемента И подключен к инверсному выхо1104526

Таблица I.

00

00

0l

00

10

00 ду К-ro разряда регистра, вход установки в ноль которого подключен к, первому информационному входу блока, а вход установки в единицу 8 -го (Ii =1,р -l разряда регистра соединен 5 с 1-м(п2,и)информационным входом группы блока, управляющий вход мультиплексора является входом задания режима блока.

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

Уолша; на фиг. 2 — схема, поясняющая принцип объединения в блоке адресации выходных сигналов второго счет- 15 чика, регистра, группы элементов И и групп элементов ИЛИ для случая обработки 2 =16 выборок входного сигнала, а также формирование последовательности адресов для указан- 20 ного случая.

На фиг. 1 широкими стрелками изображены информационные потоки группы сигналов, а тонкими — отдельные сигналы. 25

Блок адресации фиг. I состоит из (двоичных) счетчиков I и 2, регистра

3,20л — 1) (двухвходовых) элементов И 4, (N-2) элементов ИЛИ 5,д элементов ИЛИ

6, мультиппексатора 7, информационно- 30 го выхода 8 блока, управляющих входов 9 и IO мультиплексора, синхровходов(счетных входов)11 и 12 блока (счетчиков 1 и 2 соответственно) и информационного входа 13 блока.

Блок работает следующим образом.

Двоичный счетчик 1 разрядностью +1) (2 — число обрабатываемых входных данных и формируемых коэффициентов) формирует последовательности ддресов 40 входных данных, передаваемых от аналого-цифрового преобразователя в накопитель данных. Старший р+I) -й разряд его служит дпя выбора одного из двух буферов входных данных.

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

Регистр 3 разрядностью(n-1) управляет сдвигом информационных сигналов счетчика 2, осуществляемым группой элементов И 4.

Группа элементов ИЛИ 5 осуществляет объединение соответствующих сигналов группы элементов И 4 и формирование на своих выходах разрядов с

2-ro no(n — I) -й адреса первого операнда. При этом младшим и старшим разрядом адреса первого операнда являются выходные сигналы первого и последнего элементов группы элементов И 4.

Группа элементов ИЛИ 6 осуществляет объединение входных информационных сигналов блока, представляющих собой позиционный код номера итерации и соответствующих разрядов адреса первого операнда,и формирует на своих выходах адрес второго операнда.

Мальтиплексор 7 представляет собой цифровой четырехканальный мульиплексор и осуществляет выдачу на информационный выход 8 блока одного иэ

I четырех и+2) -разрядных адресов: адреса входных данных, адреса первого операнда, «дреса второго операнда и адреса результата. Комбинация старших двух разрядов(и+2) -го и (и+1) -го определяет один цз трех буферов емкостью 2а слов, к которым происходит обращение в процессе выполнения быстрого преобразования Уолша или записи входных данных и зависит от состояния (H+I) -го разряда счетчика

i и номера итерации в соответствии с табл. I ..

1104526

Графы табл.! означают: 1 — состояние (и+1) -ro разряда счетчика 1;

2 — состояние младшего разряда двоичного кода номера итерации, считая, что код первой итерации 0...0; 3 - 5 состояние и +2) -ro и(и+1) -го разрядов кода адреса записываемых входных данных; 4 — состояние(и+2) -ro и (и+11 -ro разрядов кода адреса операнда; 5— состояние(+2) -го и {n+1) -го разрядов кода адреса результата.

Интерпретация табй. 1 следующая.

Если в текущий момент, времени (и+!) -й разряд счетчика 1 находится в состоянии "0", то запись входных !5 данных от аналого-цифрового преобразователя производится в первый буфер (код "00" в графе Э 1. При этом, если код номера итерации четный("0" н графе 21, то операнды извлекаются из 20 второго буфера(код "0 I"â графе 4), а результаты помещаются в третий буфер(код "1 0"в графе 5). Ег:и же код номера итерации нечетный("1" н графе 2 1, то операнды извлекаются из 25 третьего буфера(код "1 0" н графе 4), а результаты помещаются но второй буфер(код "0 1" н графе 5).

Если в текущий момент времени (и+1)-й разряд счетчика 1 находится в состоянии "1", то запись входных данных от аналого-цифрового преобраэонателя производится во второй буфер (код "0 I" в графе 3), операнды н четных итерациях("0" в графе 2)иэвле35 каются из первого буфера(код "0 0" в графе 4 ), а результаты записываются в третий буфер код "1 0" в графе 51, в нечетных итерациях("1" в графе 2) операнды извлекаются из третьего буфера(код "1 0" в графе 4), а резуль1таты помещаются в буфер первый(код

° "0 0" в графе 5).

В процессе функционирования по алгоритму быстрого преобразования

Уолша блок управления циклически вырабатывает на управляющих входах

9 и 10 мультиплексора 7(фиг. 1) последовательность кодов: "1 0", "0 0", "1 1". При этом мультиплексор 7 передает со своих Э-ro, 2-ro

50 и 4-ro информационных входов на выход 8 последовательно адреса 1-ro u

2-го операндов и результата. После съема адреса результата блок управления генерирует импульс на счетном входе 12 счетчика 2, увеличивая его содержимое на "+1" и подготавливая

его к новому циклу выдачи адресов.

После 2" циклов текущая итерация быстрого преобразования Уолша заканчивается, счетчик 2 переполняется (переходит н состояние "0...0" 1, на входе 13 блока появляется новый код номера итерации, который вызывает установку в "!" очередного триггера регистра Э, начиная с младшего разряда, Начинается генерация последовательности адресов на новой итерации. К началу последней п -й итерации последний иэ триггеров регистра

3 устананливается в "1". После 2 счетных импульсов, поступивших на счетчик 2, заканчивается весь цикл генерации адресов по алгоритму быстрого преобразования Уолша.

Параллельно с функционированием по алгоритму быстрого преобразования

Уолша предлагаемый блок может адресовать один из двух накопителей (буферов1нходных данных с помощью счетчика 1. При обращении к аналогоцифровому преобразователю эа входными данными блок управления генерирует код "0 I на входах 9 и 10 мультиплексора 7. При этом состояние и младших разрядов счетчика 1 передается с 1-ro информационного нхода на выход 8 мультиплексора 7 в качестве адреса входных данных. Код номера буфера вырабатывается н старших

2-х разрядах адреса н соответствии с табл. 1. После записи входных данных в соответствующий буфер блок управления наращивает на "+1" содержимое счетчика I по входу .Il и может продолжить съем адресов для алгоритма быстрого преобразонания Уолша с прерванного места путем генерации последовательности кодов на входах

9 и 10 узла 7 выдачи адресов.

Рассмотрим принцип объединения сигналов счетчика 2, регистра Э, группы элементов И 4 и групп элементов ИЛИ 5 и 6 для случая обработки массива из 16-ти(и=41 входных слов, представленный на фиг. 2. Последовательность адресов l-го, 2-го операндов и результата обработки для четь:— рех итераций укаэанного случая представлена в табл. 2. Знаки "+" и перед адресами дают представление о знаке, с которым берутся операнды, извлекаемые иэ указанных адресов. Группа двухвходоных элементов И содержит 2(в-1) элементов I — 1 — 1-6, (и =4 для рассматриваемого случаи).

Первые входы каждой пары элементов

1104526

1(1-1 и 1-2, 1-3 и 1-4, 1-5 и 1-6 )

1 группы элементов И соединены со старшими(и-1) разрядами счетчика 2, которые подаются на входы 5-2 — 5-4.

При этом на вход 5-2 подается выход 5

2-го разряда, а на вход 5-4 — старшего 4-го разряда счетчика 2, а младший разряд счетчика 2, поступающий на вход 5-1, не подвергается преобразованию. На вторые входы 7-1,—

7-3 всех нечетных элементов группы

И подаются прямые выходы регистра 3, а на вторые входы 6-1 — 6-3 всех четных элементов группы И подаются инверсные выходы регистра 3. 15

Выходы элементов 1-2 — 1-5 группы элементов И, кроме первого 1-1 и последнего 1-6, объединяются i2(o -I)-21:2 элементами 2-1 и 2-2 второй группы элементов ИЛИ. Выходные 20 сигналы второй группы 2-1 и 2-2 элементов ИЛИ совместно с выходными сигналами первого 1-1 и последнего

1-6 элементов группы элементов И представляют собой адрес первого 25 операнда. При этом сигнал с вьжода элемента 1-6 является младшим, а с выхода элемента 1-1 — старшим разрядом кода адреса первого операнда.

Код адреса первого операнда с выхода второй группы элементов 2-1 и 2-2

ИЛИ и первого 1-1 и последнего 1-6 элементов группы элементов И объединяется с кодом номера итера ии, по ступающим из блока управления на вхо35 ды 8-1 — 8-4. При этом номера итераций с 1-й по 4-ю представляются кодами: "0001", "0010","0100" и

"1000". Вес разрядов справа налево

1,2,4,8.

На выходах 4-1 — 4-4 группы и, элементов ИЛИ 3-1 — 3-4 формируются адреса второго операнда с младшим разрядом на выходе 4-4. Адресом результата является состояние выходов счетчика 2.

В к-й итерации табл. 2 разряды адреса первого операнда можно получить из(п-1) старших разрядов счетчи" ка.2 1адреса результата в табл. 21 путем передачи (к- 1)младших иэ ука" занных разрядов счетчика 2 в качестве младших разрядов адреса первого операнда и сдвига остальных(и-к) указанных разрядов счетчика 2 на один разряд в сторону старших раэря" дов. В предлагаемом устройстве это достигается тем, что на к-й итерации (к.-I)ìëàämèõ разрядов регистра

3 установлены в "1" и разрешают передачу И -11младших из(й-1) старших разрядов счетчика 2 через нечетные элементы группы элементов И беэ сдвига, а остальные(и-к) разрядов счетчика 2 сдвигаются на один разряд в сторону старших разрядов через четные элементы группы элементов И за счет того, что старшие из (И-к.) раэ" рядов регистра 3 находятся в "0".

Адрес второго операнда в соответствии с табл. 2 получается путем объединения разрядов адреса первого операнда с разрядами кода номера итерации:"0001", "0010", "0100" и

"1000" с помощью первой группы h. двухвходовых элементов ИЛИ.

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

О!

104526

Таблица 2

Первая итерация

Вторая итерация

Адрес 1-го Адрес 2-ro Адрес реэульоперанда операнда тата

Адрес 1-ro Адрес 2-го Адрес резуль. операнда операнда тата

0000

+0001

0000

+0001

0001

0001

001 O

0010

0011

00)1

0100

01О0

0101

0101

0110

0110

OlI1

011!

l 000

1000

1001

IOOI

-1011

1010

1010

†10

+1110

+lll0 — 1111

-I I 11

l O11

101 1

1100

I1OO

+1100

-1100

+1110

-!!!О

1101

1101

1110

lllO

+0000

-0000

+00!0

-0010

+0100

-0100

+OilÎ

-Oll0

+1000

— IOOO

+10!0

-1010

+00!1

+001!

+0101

+0101

+0111

+0111

+1001

+1001

+1011

+1011

+1101

+1!Ol

+1111

+ l l l l

+0000

-0000

+0001

-0001

+0100

-О!,00

+0!01

-0101

+1000

-1000

+1001 †10

+ll0O

-1100

+i!0!

†11

+0010

+0010

-0011

-0011

+01 1,О

+0110

-0111

-Ol! l

+10!0

+101O!

Продолжение табл. 2

1104526

Третья итерация

Адрес 1-го операнда

Адрес 2-го операнда

Адрес 1-ro операнда

0000

0000

0001

0001

0010

0010

001 1

00 1 l

0100

0100

0101

0101. 0110

Ol l O

Oil!

Olll

1000

1000

1001

1001

1010

1010

1 011

IOll

1 100

1100

1101

I 101

1110

1!10

+1011

+0000

-0000

+0001

-0001

-0010

+0010

-0011

+001!

+1000

-1000

+1001

-100!

-101 0

+1010

-1011

Адрес 2-ro Адрес реэульоперанда тата

+0100

+0100

-0101

-0101

-0110

-0110

+0111

+01!1

+1100

+1100 — I 101

-1101 — 1110

— lllO

+1 I I

+1111

+0000

-0000

+0001

-0001

-0010

+0010

-0011

+0011

+0100

-0100

+0101

-O l.0!

-0110

+0110

-0111

+Olll

Четвертая итерация

+1000

+ I 000

-1001

-1001

-1010

-1010

+10!1

+1011

+1100

+1100

†11

-1!01

— lllO

-IllO

+1111

+1!11

Адрес резуль" тата

l I04526

1104526

4-1

Составитель А.Баранов

Редактор Р.Цицика Техред А.Кикемезей Корректор M.Ìàêñèìèøèíåö

Заказ 6146 Тираж 698 Подписное

ВНИИПО Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная,4