Устройство для преобразования адамара цифровой последовательности

, 14623 А 1 9) 6 Р 15/33 ТЕНИЯ г ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБР АВТОРСКОЬЮСВИДЕТЕЛЬСТ(71) Московский институт электронной техники(56) Авторское свидетельство СССРМф 1141420, кл. С 06 Р 15/332, 1985.Патент США У 4446530,кл. С 06 Р 15/332, 1984. ,(54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ . АДАМАРА ЦИФРОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ , (57) Изобретение относится к авто" матике и вычислительной технике, в частности к анализаторам спектра сигналов, и может быть использовано при построении устройств обработки цифровых сигналов, например устройств обработки изображений, Цель изобре. тения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят счетчик 1, триггер 2, коммутаторы 3, 4, 5, блок памяти 6, элемент И 7, буферный регистр 8, коммутатор адреса 9, блок памяти 10,элемент И 11, буферный регистр 12,коммутатор адреса 13, блок памяти14, элемент И 15, буферный регистр16, коммутатор адреса 17, блок памяти 18, элемент И 19, буферный регистр 20, коммутатор адреса 21,блокпамяти 22, элемент И 23, буферныйрегистр 24, коммутатор адреса 25,блок памяти 26, элемент И 27, буферный регистр 28, коммутатор адреса29, блок памяти 30, элемент И 31,буферный регистр 32, коммутатор адреса 33, блок памяти 34, элемент.И 35, буферный регистр 36, сумматор37, вычитатель 38, коммутаторы 39,40, элементы ИЛИ 41-44, выход 45 нечетных чисел, вход синхронизации 46установочный вход 47, вход 48 четныхчисел, вход 49 нечетных чисел, вход50 задания режима, выход 51 четныхчисел. 1 ил.Изобретение относится к автоматике и вычислительной технике, а именно.к анализаторам спектра сигналов,и может быть использовано при пост 5роении устройств обработки цифровыхсигналов, в частности устройств обработки изображений.Цель изобретения - повьппениебыстродействия устройства путем введения структуры блоков памяти поэволяющей одновременно считывать изблоков памяти аргументы текущего шага преобразования Адамара и затемодновременно записывать результатывычислений в блоки памяти по требуемыМ согласно алгоритму быстрого преобразования Адамара адресам.На чертеже приведена схема устройства. 20Устройство для преобразования Адамара цифровой последовательностисодержит счетчик 1, триггер 2, коммутор 3 информационных сигналов,коммутатор 4 формирования адресов, 25коммутатор 5 адреса, блок 6 памяти,элемент И 7, буферный регистр 8,коммутатор 9 адреса, блок 10 памяти,элемент И 11, буферный регистр 12,коюутатор 13 адреса, блок 14 памяти, элемент И 15, буферный регистр16, коммутатор 1 адреса, блок 18памяти, элемент И 19, буферный регистр 20, коммутатор 21 адреса, блок22 памяти, элемент И 23, буферныйрегистр 24, коммутатор 25 адреса,блок 26 памяти, элемент И 27, буферный регистр 28, коммутатор 29 адреса, блок 30 памяти, элемент И 31,буферный регистр 32, коммутатор 33 40адреса, блок 34 памяти, элемент И 35,буферный регистр 36, сумматор 37,вычитатель 38, коммутаторы 39 и 40информационных сигналов, элементыИЛИ 41-44, выход 45 нечетных чиселустройства, вход 46 синхронизацииустройства, установочный вход 47устройства, вход 48 счетных чиселустройства, вход 49 нечетных чиселустройства, вход 50 заданного режимаустройства и выход 51 четных чиселустройства.Устройство работает следующим образом.Перед началом преобразования Адамара происходит ввод исходной цифро 55вой последовательности длины 2 пв оперативные запоминающие устройства. Для этого на вход 50 устройства подается сигнал логической единицы, который разрешает прохождение подаваемого на вход 48 четных чисел ина вход 49 нечетных чиселустройствавходной последовательности черезкоммутатор 3 на входы блоков памяти,одновременно на установочный вход47 устройства подается установочныйимпульс, который переводит счетчик1 и триггер 2 в начальное состояние.Кроме того, необходимо подавать навход 46 синхронизации устройства тактовые импульсы, соответствующие поступлению входной последователькости. Счетчик 1 начинает счет поступающих тактовых импчльсов и выоаботку номера К (К = 0,1,2 п/2-1)текущего шага процедуры ввода данных.Коммутатор 4 вырабатывает четыретекущих адреса по следующему правилу: на первом выходе коммутатора 4 будет код А 1 = К, на втором выходе коммутатора 4 будет код А 2 = 2 Ф(п- "1) + К, на третьем выходе коммутатора 4 будет код АЗ = 2 К + 1, начетвертом выходе коммутатора 4 будет код А 4 = 2 К. Поступающая последовательность записывается в пятый, шестой, седьмой и восьмой блоки памяти, При этом нечетные члены последовательности, поступающие с входа 48 нечетных чисел устройства, записываются в блоки 22 и 30 памяти, а четные члены последовательности, поступающие с входа 48 нечетных чисел устройства, записываются в блоки 26 и 30 памяти. После окончания ввода цифровой последовательности необходимо снять управляющий сигналлогической единицы с входа 50 устройства.После этого начинается преобразование введенной последовательности в соответствии с быстрым алгоритмом преобразования Адамара, Для последовательности объемом 2 и чисел требуется провести и идентичных итераций преобразования. Каждая итерация состоит из 2(п) шагов. Обозначий номер шага индексом К. На К-м шаге необходимо произвести вычисления по формулам,Х(2+ К):Х(К) + Х(К + 2(п,Х(2 К + 1) = Х(К) - Х(К + 2 м(п эз 146где Х(К) - элемент последовательности с номером К,Требуемые номера элементов последовательности, соответствующие ихадресам в блоках памяти, генерируются коммутатором 4,Для удобства дальнейшего описанияразделим восемь блоков памяти надве одинаковые посоставу и внутренним взаимосвязям подгруппы; четнуюи нечетную,В нечетную подгруппу войдут пятый, шестой, седьмой и восьмойблоки памяти, а в четную подгруппу -первый, второй, третий и четвертыйблоки памяти.Выполнение одной итерации заключается в выборке двух чисел из однойподгруппы блоков памяти, выполненииопераций сложения и вычитания и за-.писи результатов этих операций в.другую подгруппу блоков памяти. Привыполнении итерации с нечетным номером - первой, третьей и т.д., происходит передача информации из нечетной подгруппы в четную, а при выполнении итерации с четным номером - второй, четвертый и т.д., происходит передача информации из четной подгруппы в нечетную. Рассмотрим подробнее процесс передачи информации в ходе К-го шага -й итерации преобразования, Пусть- нечетный номер, тогда передача информации происходит из нечетной подгруппы блоков памяти в четную, В случае нечетной итерации сигнал с инверсного выхода триггера 2 (логический нуль) разрешает чтение информации из блоков памяти .нечетной подгруппы, а сигнал с прямого выхода триггера 2 (логическая единица) разрешает запись информации в блоки памяти четной группы, Кроме того, сигналы с выходов триггера 2 управляют работой всех коммутаторов адреса.Рассмотрим процесс выборки информации иэ нечетной подгруппы. При этом на входы адреса пятого и шестого блоков памяти через пятый и шестой коммутаторы адреса подается адрес А 1 = К, а на входы адреса седьмого и восьмого блоков памяти через седьмой и восьмой коммутаторы адреса подается адрес А 2 = К + 2+(п) т,е, происходит выборка по требуемым адресам. Если адрес К четный, элемент И 23 запрещает прохождение 23554информации через буферный регистр24, а на выход элемента ИЛИ 43 через буферный регистр 28 происходитинформация с выхода блока 26 памяти,Если адрес К нечетный, то сигналзапрета прохождения информации выдается с элемента И 27 и на выходэлемента ИЛИ 43 происходит информа ция с выхода блока памяти 22 черезбуферный регистр 24. Аналогичнофункционируют блоки 30 и 34 памяти,т.е, выборка нечетных элементов последовательности осуществляется толь ко из блока 30 памяти, а выборка четных элементов последовательностиосуществляется только из блока 34памяти. При этом блоки 22 и 26 памяти предназначены для хранения только 20 элементов последовательности, принад.лежащих к младшей половине простран"ства адресов, а блок 30 и 34 памятидля хранения только элементов последовательности, принадлежащих к стар шей половине пространства адресовПолученные элементы последовательнопоступают через коммутаторы 39 и 40на входы сумматора 31 и вычитателя38. На выходе сумматора 37 появляет ся значение суммы чисел, а на выходе вычитателя 38 - значение разностичисел.Рассмотрим процесс записи информации в четную подгруппу блоков па фмяти который происходит после выполнения операций сложения и вычитания. Строение четной подгруппы аналогично строению нечетной подгруппы.При этом первый блок памяти четной 40 подгруппы соответствует пятому блокупамяти нечетной подгруппы, второйблок памяти четной подгруппы соответствует шестому блоку памяти нечетной подгруппы, третий блок памя ти четной подгруппы соответствуетседьмому блоку памяти нечетной подгруппы, четвертый блок памяти четнойподгруппы соответствует восьмомублоку памяти нечетной подгруппы. Области значений номеров элементовобрабатываемой последовательности длясоответствующих друг другу блоковпамяти совпадают. Поэтому элементыпоследовательности с четными номера ми, поступающие с выхода сумматора37, поступают через коммутатор 3 наинформационные входы блоков 10 и 13памяти. При этом на адресные входыэтих блоков памяти через второй 9 и5 14 четвертый 17 коммутаторы адреса подается выработанный коммутатором 4 адрес А 4 = 2 К и происходит запись всех элементов последовательности с четными номерами в эти блоки памяти. Аналогично все элементы последовательности с нечетными номерами записываютсяпервый 6 и второй 1 О блоки памяти, При этом на адресные входы этих блоков памяти через первый 5 и третий 13 коммутаторы адре, са подается выработанный коммутато: ром 4 нечетный адрес АЗ = 2+К + 1.Аналогично происходит передача информации при выполнении итерации преобразования с четным номером, но направление передачи меняется на противоположное,После выполнения и итераций в од ной из подгрупп блоков памяти будут записаны элементы полностью преобразованной по Адамару входной последовательности. Для получения выход" ных результатов необходимо подавать на вход 46 синхронизации устройства тактовые импульсы, при этом процесс перезаписи информации будет продолжаться и в ходе его на выходе 45 нечетных чисел устройства и на выходе 51 четных чисел устройства будут появляться элементы преобразованной по Адамару входной цифровой последовательности.Формула изобретенияФУстройство для преобразованияАдамара цифровой последовательности, содержащее первый и второй коммутаторы, триггер, сумматор, первый коммутатор адреса, первый блок памяти и счетчик, счетный вход которого является входом синхронизации устройства, входом задания режима кото рого является управляющий вход первого коммутатора, первый информационный вход которого подключен к выходу сумматора, информационный выход счетчика подключен к информационному и управляющему входам второго коммутатора, выход первого коммутатора адреса подключен к адресному входу первого блока памяти, а установочный вход счетчика соединен с первым установочным входом;триггера и является установочным входом устройства, о т л и ч а ю - щ е е с я тем, что, с целью повыше- ния быстродействия, в него введены62355 5 10 15 20 25 30 35 40 45 50 55 с второго по восьмой коммутаторыадреса, с второго по восьмой блокипамяти, с первого по восьмой элементы И, с первого по восьмой буферныерегистры, с первого по четвертыйэлементы ИЛИ, вычитатель, третий ичетвертый коммутаторы, при этом выход -го ( = 2,8) коммутатора адреса подключен к информационномувходу 1-го блока памяти, первый выход первого коммутатора подключен кинформационному входу 3-го Ц = 1,4)блока памяти, выход которого подключен к информационному входу 3-гобуферного регистра, выход которогоподключен к первому входу 1-го элемента ИЛИ, второй выход первого коммутатора подключен к информационному входу Ц + 4)-го блока памяти,выход второго подключен к информационному входу Ц + 4)-го буферногорегистра, выход которого подключенк второму входу 3-го элемента ИЛИ,первый выход второго коммутатораподключен к первым информационнымвходам первого, третьего, пятого .иседьмого коммутаторов адреса, второйвыход второго коммутатора подключенк первым информационным входам второго, четвертого и восьмого коммутаторов адреса, третий выход второго коммутатора подключен к второмуинформационному входу 1-го коммутатора адреса, четвертый выход второгокоммутатора подключен к второму информационному входу (3 + 4)-го коммутатора адреса, выходы первого ивторого элементов ИЛИ подключены кпервым информационным входам соответ.ственно третьего и четвертого коммутаторов, вторые информационныевходы которых подключены к выходамсоответственно третьего и четвертого элементов ИЛИ, выход переносасчетчика подключен к второму установочному входу триггера, прямойвыход которого подключен к управляющим входам первого, второго, пятогои шестого коммутаторов адреса, входам управления записью (считывание)первого, второго, пятого и шестогоблоков памяти и управляющему входучетвертого коммутатора, выход которого является выходом нечетных чиселустройства и подключен к первым входам сумматора и вычитателя, выходкоторого подключен к второму информационному выходу первого коммутато7,462355 Составитель А,БарановТехред Л.Олийнык Корректор Л.Патай Редактор А.Огар Заказ 715/49 Тирак 667 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г.уагород, ул. Гагарина, 101 ра, третий н четвертый информационные входы которого являются входами соответственно четных и нечетньк чисел устройства, инверсный выход триггера подключен к управляющим входам третьего, четвертого, седьмого и восьмого коммутаторов, входам управления записью (считыванием) . третьего, четвертого, седьмого и восьмого блоков памяти и управляющему входу третьего коммутатора, выход которого является выходом четныхчисел устройства и подключен к вторым входам сумматора и вычитателя,выходы старшего и младшего разрядов1-го (11,8) коммутатора адресаподключены соответственно к первомуи второму входам 1-го злемента И,выход которого подключен к входуразрешения записи 1-го буферногорегистра,