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

(р) С 06 Г 15/332 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРпО делАм изОБРетений и ОтнРытийОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМ,К СВИДЕТЕЛЬСТВУ(71)Специальное конструкторскотехнологическое бюро вычислительнойтехники(56) 1, Хартмут Х.Ф. Передача информации ортогональными функциями, М(54)(57) БЛОК ФОРМИРОВАНИЯ А 11 РЕСОВДЛЯ УСТРОЙСТВА, РЕАЛИЗУЮЩЕГО БЫСТ 1 ОЕП 1 ЕОБРАЗОВАНИЕ УОЛШ 1 А, содержди 1 ийрегистр, первый счетчик, о(и =2, гдеразмер преобрдзовднин) элементов11 И выходы которых подкпючен 1 и соответстненно к рдзряддм первого информационного нходд мультиплексора, выход которого является информационнымвыходом блока, разряды второго информационного вход муль гиппексора соединены соответственно с разряднымивыходами первого счетчика, счетныйвход которого является первым синхровходом, а первые входы 1 эпемен 1 овИЛИ являются группой и 11 формдционныхвходов блока, о т п и ч д ю и 1 и йс я тем, что, с целью повышениябыстродействия, н него 11 ведвывторой счетчик, 2 м - 1) эпемеп 1 ов И и (л -2) элементов ИЛИ, причем выходъ-го Д 21 разряда второго счетчикасоединен с первыми входами(2 -3) -гои (2 ъ) -го элементов И, выходы 2 Д -гои (2+1) -го =1, 11-2) элементов И подключены соответственно к первому ивторому входам Ц 1.И 1-го элемента ИЛИ,выход которого соединен (с+1) -мразрядом третьего информационноговхода мультиплексора и подключен квторому входу(+1) -го элемента ИЛИ,выходы первого и 2(И-го элементовИ соединены с вторыми входами соответственно первого и р-го элементов1 ГЛИ и подключены соответственно кпервому и О -му разрядам третьегоинформационного входа мулы иплекстора,разряды четвертого информационноговхода которого соединены соотнетстненно с разрядными выходами второгосчетчика счетный ВхОд которого является вторым синхровходом блока, прямой выход К - го (1 Г: 1, .1) разряда регистра соединен с вторым входом 2 К-гоэлементд И, второй вход (2 К - 1) -гоэлемента И подключен к инверсномувыходу К-го разряда регистра, входустановки н ноль которого подключенк первому информационному входу блокаа вход установки в единицу К-го (0=1,4 - 1) разряда регистра соединен счъ-м(щ=2,) информационным входом группы блока, управляющий вход мультиплексора является входом заданиярежима блока.Изобретение относится к вычислительной технике и может быть исполь-,зовано при построении устройств, реализующих быстрое преобразованиеУолша.5Известно устройство, реализующееалгоритм. быстрого преобразованияУолша, содержащее в своем составеаналого-цифровой преобразователь,первый цифровой накопитель для накопления входных данных, арифметическое устройство и второй цифровой накопитель для накопления результатов преобразования входных данных1-1 315Однако адресация данных в накопителях может производиться арифметическим устройством, что снижаетскорость преобразования входныхданных из-за отвлечения арифметического устройства на адресацию данных или может использоваться отдельный блок адресации, адресующий данные в накопителе в соответствии салгоритмом быстрого преобразованияУолша.Наиболее близким по техническойсущности к изобретению являетсяблок формирования адресов для устройства, реализующсго быстрое преобра 30эование Фурье, содержащий счетчик,регистр, группу элементов ИЛИ, иузел выдачи адресов, первый и второйвходы которого соединены соответственно с выходами группы элементов ИЛИи счетчика, счетный вход которогоявляется счетным входом блока, выходузла выдачи адресов является информационным выходом блока, а первыевходы элементов ИЛИ являются группойинформационных входов блока Г 2 1,Однако при применении его вкачестве адресного блока в устройстве быстрого преобразования Уолшав результате преобразования получаются коэффициенты преобразования,упорядоченные по Адамару и расположенные не в порядке возрастаниячастасти Это следует иэ того, чтографы быстрого преобразования Фурьеи Уолша-Адамара совпадают, 50При спектральном анализе сигналов желательно, чтобы коэффициенты преобразования располагались в порядке возрастания частости,Это упрощает получение спектра55 мощности сигналов да простогосуммирования квадратов соседнихкоэффициентов,Переупорядочение коэффициентовпреобразования Уолша-Адамара почастости при использовании известного блока в качестве адресного блокаустройства быстрого преобрвазованияУолша приводит к значительным аппаратурцым затратам. Кроме того, необходимо тратить дополнительное времяна переупорядочение коэффициентов,что снижает быстродействие устройства, реализующего быстрое преобразование Уолша,Цель изобретения - повышениебыстродействия,Указанная цель достигается тем,что в блок формирования адресов дляустройства, реализующего быстроепреобразование Уолша,содержащийрегистр, первый счетчик,1 М =2где ив размер преобразования 1 элементов ИЛИ, выходы которых подключенысоответственно к разрядам первогоинформационного входа мультиплексоравыход которого является информационным выходом блока, разряды второгоинформационного входа мультиплексорасоединены соответственно с разряднымивыходами первого счетчика, счетныйвход которого является первым синхровхоцом, а первые входы О элементовИ 161 являются группой информационныхвходов блока, введены второй счетчик,2 и - 1) элементов И и М -2) элементовИЛИ, причем выход Ъ -го(Ъ -2,И)разрядавторого счетчика соединен с первымивходами (2 ъ - 3) -го и 12-2) -го элементов И, выходы 2 д-го и 2+1) -гоЯ =1,о:2) элементов И подключены соответственно к первому и второму входам(Ьи)-го элемента ИЛИ, выход которогосоединен с +1) -м разрядом третьегоинформационного входа мультиплексораи подключен к второму входу(+1) -гоэлемента ИЛИ, выходы первого и2(и -1) -го элементов И соединены свторыми входами соответственно первого и о -го элементов ИЛИ и подключенысоответственно к первому и П -муразрядам третьего информационноговхода мультиплексора, разрядычетвертого информационного входакоторого соединены соответственнос раз рядными выходами в торо го счетчика,счетный вход которого является вторым синхровходом блока, прямой выход К -го(К=1, 6 - 1 разряда регистрасоединен с вторым входом 2 к-го элемента И, второй вход 1,2 к-) -го элемента И подключен к инверсному выхо104526 Таблица 1 01 00 О 00 1 О 01 01 00 10 О 00 ду К-го разряда регистра, вход установки в ноль которого подключен к , первому информационному входу блока, а вход установки в единицу 6 -го Я =1,-1 разряда регистра соединен 5 съ-мп 2,и)информационным входом группы блока, управляющий вход мультиплексора является входом задания режима блока.На Фиг. 1 показана функциональная схема блока адресации для устройства, реализующего быстрое преобразование Уолша; на фиг. 2 - схема, поясняющая принцип объединения в блоке адресации выходных сигналов второго счет чика, регистра, группы элементов И и групп элементов ИЛИ для случая обработки 2 =16 выборок входного сигнала, а также формирование последовательности адресов для указан ного случая.На фиг. 1 широкими стрелками изображены информационные потоки группы сигналов, а тонкими - отдельные сигналы. 25Блок адресации Фиг. 1 состоит из (двоичных) счетчиков 1 и 2, регистра 3,2(и - 1) (двухвходовых) элементов И 4, (и) элементов ИЛИ 5,и элементов ИЛИ 6, мультиппексатора 7, информационно го выхода 8 блока, управляющих входов 9 и 10 мультиплексора, синхровходов(счетных входов)11 и 12 блока (счетчиков 1 и 2 соответственно) и информационного входа 3 блока.Блок работает следующим образом.Двоичный счетчик 1 разрядностью 1+1) (2 - число обрабатываемых входных данных и формируемых коэффициентов) Формирует последовательности адресов 40 входных данных, передаваемых от аналого-цифрового преобразователя в накопитель данных. Старший р+1) -й разряд его служит для выбора одного из двух буферов входных данных. Двоичный счетчик 2 разрядностьр и, формирует последовательность адресов результата алгебраического сум" мирования двух операндов в процессе выполнения алгоритма быстрого преобразования Уолша.Регистр 3 разрядностью(иУправляет сдвигом информационных сигналов счетчика 2, осуществляемым группой элементов И 4.Группа элементов ИЛИ 5 осуществляет объединение соответствующих сигналов группы элементов И 4 и формирование на своих выходах разрядов с 2-го по(и - 1) -й адреса первого операнда, При этом младшим и старшим разрядом адреса первого операнда являются выходные сигналы первого и последнего элементов группы элементов И 4.Группа элементов ИЛИ 6 осуществляет объединение входных информационных сигналов блока, представляющих собой позиционный код номера итерации и соответствующих разрядов адреса первого операнда,и формирует на своих выходах адрес второго операнда. Мальтиплексор 7 представляет собой цифровой четырехканальный мульиплексор и осуществляет выдачу на информационный выход 8 блока одного иэ четырех и+2) -разрядных адресов: адреса входных данных, адреса первого операнда, дреса второго операнда и адреса результата, Комбинация старших двух разрядов(и+21 -го и р+1) -го определяет один пэ трех буферов емкостью 2 а слов, к которым происходит обращение в процессе выполнения быстрого преобразования Уолша или записи входных данных и зависит от состояния(и+1) -го разряда счетчика 1 и номера итерации в соответствии с табл. 1.Графы табл. означают; 1 - состояниеи+1) -го разряда счетчика 1;2 - состояние младшего разряда двоичного кода номера итерации, считая, что код первой итерации 00; 3 - 5 состоянием+2) -го и(и+1) -го разрядов кода адреса записываемых входных данных; 4 - состояние(и+2)-го и и+1) -го разрядов кода адреса операнда; 5 - состояние(и+2) -го и (о+1) -го разрядов О кода адреса результата.Интерпретация табЛ. 1 следующая.Если в текущий момент, времени ("1+1) -й разряд счетчика 1 находится в состоянии "0", то запись входных 5 данных от аналого-цифрового преобразователя производится в первый буфер (код "00" в графе Э . При этом, если код номера итерации четный("0" н графе 2), то операнды извлекаются из 20 второго буфера(код "0 "н графе 4), а результаты помещаются в третий буфер(код "1 0"в графе 5). Если же код номера итерации нечетный("1" в графе 2 1, то операнды извлекаются из 25 третьего буфера(код "1 0" н графе 4), а результаты помещаются но второй буфер(код "0 1" в графе 5).Если в текущий момент времени (м+)-й разряд счетчика 1 находится в состоянии "1", то запись входных данных от аналого-цифрового преобраэонателя производится во второй буфер (код "0 1" в графе 3), операнды в четных итерациях("0" в графе 2)иэвле 35 каются из первого буфера (код "0 0" в графе 4), а результаты записываются в третий буфер код "1 0" в графе 5), в нечетных итерациях("1" в графе 2) операнды извлекаются из третьего буфера(код "1 0" н графе 4), а результаты помещаются в буфер первый(код "О 0" в графе 5).В процессе функционирования по алгоритму быстрого преобразования Уолша блок управления циклически вырабатывает на управляющих входах 9 и 10 мультиплексора 7(фиг. 1) последовательность кодов: "1 0", "0 0", "1 1". При этом мультиплексор 7 передает со своих Э-го, 2-го50 и 4-го информационных входов на выход 8 последовательно адреса 1-го и 2-го операндов и результата. После съема адреса результата блок управления генерирует импульс на счетном входе 12 счетчика 2, увеличивая его содержимое на "+1" и подготавливая его к новому циклу выдачи адресов. После 2" циклов текущая итерация быстрого преобразования Уолша заканчивается, счетчик 2 переполняется (переходит в состояние "00" 1, на входе 13 блока появляется новый код номера итерации, который вызывает установку в "1" очередного триггера регистра Э, начиная с младшего разряда, Начинается генерация последовательности адресов на новой итера. ции. К началу последней й -й итерации последний из триггеров регистра 3 устананливается в "1". После2 счетных импульсов, поступивших на счетчик 2, заканчивается весь цикл генерации адресов по алгоритму быстрого преобразования Уолша.Параллельно с функционированием по алгоритму быстрого преобразования Уолша предлагаемый блок может адресовать один из двух накопителей (буферов 1 входных данных с помощью счетчика 1, При обращении к аналогоцифровому преобразователю эа входными данными блок управления генерирует код "0 1" на входах 9 и 10 мультиплексора 7. При этом состояние и младших разрядов счетчика 1 передается с 1-го информационного входа на выход 8 мультиплексора 7 в качестве адреса входных данных, Код номера буфера вырабатывается в старших 2-х разрядах адреса н соответствии с табл. 1. После записи входных данных в соответствующий буфер блок управления наращивает на "+1" содержимое счетчикапо входу .1 и может продолжить съем адресов для алгоритма быстрого преобразонания Уолша с прерванного места путем генерации последовательности кодов на входах 9 и 10 узла 7 выдачи адресов.Рассмотрим принцип объединения сигналов счетчика 2, регистра Э, группы элементов И 4 и групп элементов ИЛИ 5 и 6 для случая обработки массива из 16-ти(и=4) входных слов, представленный на фиг. 2. Последовательность адресов 1-го, 2-го операндов и результата обработки для четь: - рех итераций укаэанного случая представлена в табл. 2. Знаки "+" и перед адресами дают представление о знаке, с которым берутся операнды, извлекаемые иэ указанных адресов.Группа двухвходоных элементов И содержит 2(в) элементов 1 - 1 - 1-6, (и =4 для рассматриваемого случаи). Первые входы каждой пары элементов111-1 и 1-2, 1-3 и 1-4, 1-5 и 1-6)группы элементов И соединены состаршимии) разрядами счетчика 2,которые подаются на входы 5-2 - 5-4.При этом на вход 5-2 подается выход 52-го разряда, а на вход 5-4 - старшего 4-го разряда счетчика 2, амладший разряд счетчика 2, поступающий на вход 5-1, не подвергается пре.образованию, На вторые входы 7-1., -7-3 всех нечетных элементов группыИ подаются прямые выходы регистра 3,а на вторые входы 6-1 - 6-3 всехчетных элементов группы И подаютсяинверсные выходы регистра Э, 15Выходы элементов 1-2 - 1-5 группыэлементов И, кроме первого 1-1 ипоследнего 1-6, объединяются 2(о -1)-21:2 элементами 2-1 и 2-2 второйгруппы элементов ИЛИ. Вьжодные 20сигналы второй группы 2-1 и 2-2элементов ИЛИ совместно с выходнымисигналами первого 1-1 и последнего1-6 элементов группы элементов Ипредставляют собой адрес первого 25операнда. При этом сигнал с вьжодаэлемента 1-6 является младшим, а свыхода элемента 1-1 - старшим разрядом кода адреса первого операнда,Код адреса первого операнда с выхода второй группы элементов 2- и 2-2ИЛИ и первого 1-1 и последнего 1-6 элементов группы элементов И объединяется с кодом номера итераг.ии, по ступающим из блока управления на вхо 35ды 8-1 - 8-4. При этом номера итераций с 1-й по 4-ю представляютсякодами: "0001", "0010","0100" и"000"Вес разрядов справа налево1,2,4,8,На выходах 4-1 - 4-4 группы ъэлементов ИЛИ 3-1 - 3-4 формируютсяадреса второго операнда с младшимразрядом на выходе 4-4. Адресом результата является состояние выходовсчетчика 2.В к-й итерации табл. 2 разрядыадреса первого операнда можно получить изб) старших разрядов счетчи"ка.2 адреса результата в табл, 21путем передачи (к)младших иэ ука"занных разрядов счетчика 2 в качестве младших разрядов адреса первогооперанда и сдвига остальных(и-к)указанных разрядов счетчика 2 наодин разряд в сторону старших раэря"дов. В предлагаемом устройстве этодостигается тем, что на к-й итерации 1 к)младших разрядов регистра3 установлень 1 в "1" и разрешаютпередачу Кмладших из(и) старшихразрядов счетчика 2 через нечетныеэлементы группы элементов И беэсдвига, а остальные и-к) разрядовсчетчика 2 сдвигаются на один разрядв сторону старших разрядов через четные элементы группы элементов И засчет того, что старшие из (И-к) раэ"рядов регистра 3 находятся в "0".Адрес второго операнда в соответствии с табл. 2 получается путемобъединения разрядов адреса первогооперанда с разрядами кода номераитерации:"0001", "0010", "0100" и"1000" с помощью первой группы Ь,двухвходовых элементов ИЛИ,Таким образом, благсдаря введениюновых узлов и новых вэаимосвязейпредлагаемый блок позволяет адресовать устройства, выполняющие алгоритм быстрого преобразования Уолшвс упорядочением коэффициентов преобразования по частости. Благодаряэтому, получение спектральных коэффи.циентов мощности упрощается до суммирования квадратов соседних паркоэффициентов, что позволит повыситьбыстродействие.110452 Ь Таблица 2 Первая итерация Вторая итерация Адрес 1-го Адрес 2-го Адрес реэульоперанда операнда тата Адрес 1-го Адрес 2-го Адрес резульоперанда операнда тата 000012Продолаение табл, 2 1104526 Четвертая итерация Третья итерация Адрес 1-гооперанда Адрес 2-гооперанда Адрес 1-гооперанда 0000 0000 000 0001 0010 0010 0011 0031 0100 0100 0101 01011104526 Составитель А.Барановицика Техред А.Кикемезей Корректор М.Максимишинец едакт аз 6146 и лиал ППП "Патент", г. Ужгород, ул. Проектная,4 Тираж 698 ВНИИПО Государственног по делам изобретен 113035, Москва, Ж, Подписноеитета СССРоткрытийкая наб д.4