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

 

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

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

РЕСПУБЛИК (Я) 4 G 06 F !5/332

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4302198/24-24 (22) 26.06.87 (46) 28 ° 02.89. Бюл. 1Ф 8 (71) Московский институт электронной техники (72). Б.Ю.Алифанов и Б.И.Полянин (53) 681.32(088 ° 8) (56) Авторское свидетельство СССР

Р 1 141420, кл. G 06 F 15/332, 1985.

Патент США М 4446530, кл. G 06 Е 15/332, 1984. ,(54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ .

АДАМАРА ЦИФРОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, (57) Изобретение относится к автоматике и вычислительной технике, в частности к анализаторам спектра сигналов, и может быть использовано при построении устройств обработки цифровых сигналов, например устройств обработки изображений, Цель изобре. тения — повьппение быстродействия.

Поставленная цель достигается за счет того, что в состав устройства входят счетчик 1, триггер 2, комму„„SU„„1462355 А1 таторы 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 ил.

1462355

Изобретение относится к автоматике и вычислительной технике, а именно.к анализаторам спектра сигналов, и может быть использовано при пост5 роении устройств обработки цифровых сигналов, в частности устройств обработки изображений.

Цель изобретения — повышение быстродействия устройства путем вве- 10 дения структуры блоков памяти поэво.

1 ляющей одновременно считывать из блоков памяти аргументы текущего шага преобразования Адамара и затем одновременно записывать результаты вычислений в блоки памяти по требуемыМ согласно алгоритму быстрого преобразования Адамара адресам.

На чертеже приведена схема устройства. 20

Устройство для преобразования Адамара цифровой последовательности содержит счетчик 1, триггер 2, коммутор 3 информационных сигналов, коммутатор 4 формирования адресов, 25 коммутатор 5 адреса, блок 6 памяти, элемент И 7, буферный регистр 8, коммутатор 9 адреса, блок 10 памяти, элемент И 11, буферный регистр l2 коьа утатор 13 адреса, блок 14 памяти, элемент И 15, буферный регистр

16, коммутатор 1? адреса, блок 18 памяти, элемент И 19, буферный регистр 20, коммутатор 21 адреса, блок

22 памяти, элемент И 23, буферный регистр 24, коммутатор 25 адреса, блок 26 памяти, элемент И 27, буферный регистр 28, коммутатор 29 адреса, блок 30 памяти, элемент И 31, буферный регистр 32, коммутатор ЗЗ 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 начинает счет поступающих тактовых импчльсов и выоаботку номера К (К = О, 1,2,...,п/2-1) текущего шага процедуры ввода данных.

Коммутатор 4 вырабатывает четыре текущих адреса по следующему прави» лу: на первом выходе коммутатора 4 будет код А1 = К, на втором выходе коммутатора 4 будет код А2 = 2 (п"1) + К, на третьем выходе коммутатора 4 будет код A3 = 2 К + 1, на четвертом выходе коммутатора 4 будет код А4 = 2+К. Поступающая последовательность записывается в пятый, шестой, седьмой и восьмой блоки памяти. При этом нечетные члены последовательности, поступающие с входа

48 нечетных чисел устройства, записываются в блоки 22 и 30 памяти, а четные члены последовательности, поступающие с входа 48 нечетных чисел устройства, записываются в блоки 26 и 30 памяти. После окончания ввода цифровой последовательности необходимо снять управляющий сигнал логической единицы с входа 50 устройства.

После этого начинается преобразование введенной последовательности в соответствии с быстрым алгоритмом преобразования Адамара, Для последовательности объемом 2+en чисел требуется провести и идентичных итераций преобразования. Каждая итерация состоит из 2»x(n-1) шагов. Обозначий номер шага индексом К. На К-м шаге необходимо произвести вычисления по формулам ... ° .

Х(2 ь К)=Х(К) + Х(К + 2«+(п-1)), Х(2+К + 1) = Х(К) — Х(К + 2+«(и1)), з 146 где Х(К) — элемент последовательности с номером К.

Требуемые номера элементов последовательности, соответствующие их адресам в блоках памяти, генерируются коммутатором 4, Для удобства дальнейшего описания разделим восемь блоков памяти на две одинаковые по составу и внутренним взаимосвязям подгруппы: четную и нечетную.В нечетную подгруппу войдут пятый, шестой, седьмой и восьмой блоки памяти, а в четную подгруппу— первый, второй, третий и четвертый блоки памяти.

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

Рассмотрим подробнее процесс передачи информации в ходе К-ro шага

)-й итерации преобразования, Пусть

j — нечетный номер, тогда передача информации происходит из нечетной подгруппы блоков памяти в четную, В случае нечетной итерации сигнал с инверсного выхода триггера 2 (логический нуль) разрешает чтение информации из блоков памяти .нечетной подгруппы, а сигнал с прямого выхода триггера 2 (логическая единица) разрешает запись информации в блоки памяти четной группы. Кроме того, сигналы с выходов триггера 2 управляют работой всех коммутаторов адреса.

Рассмотрим процесс выборки информации иэ нечетной подгруппы. При этом на входы адреса пятого и шестого блоков памяти через пятый и шестой коммутаторы адреса подается адрес А1 = К, а на входы адреса седьмого и восьмого блоков памяти через седьмой и восьмой коммутаторы адреса подается адрес А2 = К + 2««(п-1),, т,е, происходит выборка по требуемым адресам. Если адрес К четный, элемент И 23 запрещает прохождение

4 информации через буферный регистр

24, а на выход элемента ИЛИ 43 через буферный регистр 28 происходит информация с выхода блока 26 памяти.

Если адрес К нечетный, то сигнал запрета прохождения информации выдается с элемента И 27 и на выход элемента ИЛИ 43 происходит информация с выхода блока памяти 22 через буферный регистр 24. Аналогично функционируют блоки 30 и 34 памяти, т.е. выборка нечетных элементов последовательности осуществляется толь15 ко из блока 30 памяти, а выборка четных элементов последовательности осуществляется только из блока 34 памяти. При этом блоки 22 и 26 памяти предназначены для хранения только

20 элементов последовательности, принадлежащих к младшей половине пространства адресов, а блок 30 и 34 памятидля хранения только элементов последовательности, принадлежащих к стар25 шей половине пространства адресов °

Полученные элементы последовательно поступают через коммутаторы 39 и 40 на входы сумматора 31 и вычитателя

38. На выходе сумматора 37 появляет30 ся значение суммы чисел, а на выходе вычитателя 38 — значение разности чисел °

Рассмотрим процесс записи информации в четную подгруппу блоков па35 мяти который происходит после выполнения операций сложения и вычитания. Строение четной подгруппы аналогично строению нечетной подгруппы.

При этом первый блок памяти четной

4р подгруппы соответствует пятому блоку памяти нечетной подгруппы, второй блок памяти четной подгруппы соответствует шестому блоку памяти нечетной подгруппы, третий блок памя45 ти четной подгруппы соответствует седьмому блоку памяти нечетной подгруппы, четвертый блок памяти четной подгруппы соответствует восьмому блоку памяти нечетной подгруппы. Области значений номеров элементов обрабатываемой последовательности для соответствующих друг другу блоков памяти совпадают. Поэтому элементы последовательности с четными номера55 ми, поступающие с выхода сумматора

37, поступают через коммутатор 3 на информационные входы блоков 10 и 13 памяти. При этом на адресные входы этих блоков памяти через второй 9 и

5 14 четвертый 17 коммутаторы адреса подается выработанный коммутатором 4 адрес А4 = 2 К и происходит запись всех элементов последовательности с четными номерами в эти блоки памяти.

Аналогично все элементы последовательности с нечетными номерами записываются первый 6 и второй 1О блоки памяти. При этом на адресные входы этих блоков памяти через первый 5 и третий 13 коммутаторы адре, са подается выработанный коммутато: ром 4 нечетный адрес A3 = 2+К + l.

Аналогично происходит передача информации при выполнении итерации преобразования с четным номером, но направление передачи меняется на противоположное.

После выполнения и итераций в од ной из подгрупп блоков памяти будут записаны элементы полностью преобразованной по Адамару входной последовательности. Для получения выходных результатов необходимо подавать на вход 46 синхронизации устройства тактовые импульсы, при этом процесс перезаписи информации будет продолжаться и в ходе его на выходе 45 нечетных чисел устройства и на выходе

51 четных чисел устройства будут появляться элементы преобразованной по Адамару входной цифровой последовательности.

Формула изобретения

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

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

62355

55 с второго по восьмой коммутаторы адреса, с второго по восьмой блоки памяти, с первого по восьмой элементы И, с первого по восьмой буферные регистры, с первого по четвертый элементы ИЛИ, вычитатель, третий и четвертый коммутаторы, при этом выход i-ro (i = 2,8) коммутатора адреса подключен к информационному входу i-ro блока памяти, первый выход первого коммутатора подключен к информационному входу j-го (j = 1,4) блока памяти, выход которого подключен к информационному входу j-го буферного регистра, выход которого подключен к первому входу j-ro элемента ИЛИ, второй выход первого коммутатора подключен к информационному входу (j + 4)-ro блока памяти, выход второго подключен к информационному входу (j + 4)-ro буферного регистра, выход которого подключен к второму входу j-ro элемента ИЛИ, первый выход второго коммутатора подключен к первым информационным входам первого, третьего, пятого .и седьмого коммутаторов адреса, второй выход второго коммутатора подключен к первым информационным входам второго, четвертого и восьмого коммутаторов адреса, третий выход второго коммутатора подключен к второму информационному входу j-го коммутатора адреса, четвертый выход второго коммутатора подключен к второму информационному входу (j + 4)-го коммутатора адреса, выходы первого и второго элементов ИЛИ подключены к первым информационным входам соответ. ственно третьего и четвертого коммутаторов, вторые информационные входы которых подключены к выходам соответственно третьего и четвертого элементов ИЛИ, выход переноса счетчика подключен к второму установочному входу триггера, прямой выход которого подключен к управляющим входам первого, второго, пятого и шестого коммутаторов адреса, входам управления записью (считывание) первого, второго, пятого и шестого блоков памяти и управляющему входу четвертого коммутатора, выход кото рого является выходом нечетных чисел устройства и подключен к первым входам сумматора и вычитателя, выход которого подключен к второму информационному выходу первого коммутато7. l462355

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

Техред Л.Олийнык - Корректор Л.Патай

Редактор А.Orap

Заказ 715/49 Тирах 667 Подписное

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

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

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

1-ro (1 1,8) коммутатора адреса подключены соответственно к первому и второму входам 1-го злемента И, выход которого подключен к входу

1п разрешения записи 1-ro буферного регистра,