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

Авторы патента:

G06F9/34 - адресация или выборка операнда команды или результата (трансляция адреса G06F 12/00)

G06F17/14 - преобразования Фурье, Уолша или аналогичные преобразования

БЛОК ФОРМИРОВАНИЯ АДРЕСОВ ДЛЯ УСТРОЙСТВА, РКАЛИЗУЮЩЕГО БЫСТРОЕ ПРЕОБРАЗОВАНИЕ 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 ду К-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