Устройство для преобразования Адамара цифровой последовательности Советский патент 1989 года по МПК G06F17/14 

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

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

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

Устройство для преобразования Адамара цифровой последовательности содержит счетчик 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 синхро1шзации устройства, установочный вход 47 устройства, вход 48 счетных чисел устройства, вход 49 нечетных чисел устройства, вход 50 заданного режима устройства и выход 51 четных чисел устройства.

Устройство работает следукщим образом.

Перед началом преобразования Адамара происходит ввод исходной цифро- вой последовательаости дпины в оперативные запоминающие устройства. Для этого на вход 50 устройства

14

, 10

15

20

25

к - 5, а

462355

подается сигнал логической единицы, который разрешает прохождение подаваемого на вход 48 четных чисел и на вход 49 нечетных чисел устройства входной последовательности через коммутатор 3 на входы блоков памяти, одновременно на установочный вход 47 устройства подается установочный импульс, который переводит счетчик 1 и триггер 2 в начальное состояние. Кроме того, необходимо подавать на вход 46 синхронизации устройства тактовые импульсы, соответствующие поступлению входной последователь- кости. Счетчик 1 начинает счет поступающих тактовых ИМПУЛЬСОВ и выоа- ботку номера К (К О,1,2,..,,п/2-1) текущего шага процедуры ввода данных.

KoMNryTaTop 4 вырабатывает четыре текущих адреса по следующему прави - лу: на первом выходе коммутатора 4 будет код А1 К, на втором выходе коммутатора 4 будет код А2 2(п- -1) К, на третьем выходе коммутатора 4 будет код A3 2 К + 1, на четвертом выходе коммутатора 4 будет код А4 . Поступающая последовательность записывается в пятый, шестой, седьмой и восьмой блоки памяти. При этом нечетные члены последовательности, поступаюпще с входа 48 нечетных чисел устройства, записываются в блоки 22 и 30 памяти, а четные члены последовательности, поступающие с входа 48 нечетных чисел устройства, записываются в блоки 26 и 30 памяти. После окончания ввода цифровой последовательности необходимо снять управляющий сигнал логической единицы с входа 50 устройства.

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

30

35

40

45

50

55 х(2 К)Х(К) + Х(К + 2(п-1)),

Х( + 1) Х(К) - Х(К + 2(п - - 1)).

где Х(К) - элемент последовательности с номером К.

Требуемые номера элементов последовательности, соответствующие их адресам в блоках памяти, генерируются коммутатором 4.

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

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

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

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

5

5

0

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

Рассмотрим процесс записи информации в четную подгруппу блоков памяти, который происходит после выполнения операций сложения и вычитания. Строение четной подгруппы аналогично строению нечетной подгруппы. При этом первый блок памяти четной подгруппы соответствует пятому блоку памяти нечетной подгруппы, второй блок памяти четной подгруппы соответствует шестому блоку памяти нечетной подгруппы, третий блок памя- 5 ти четной подгруппы соответствует седьмому блоку памяти нечетной под- группы, четвертый блок памяти четной подгруппы соответствует восьмому блоку памяти нечеткой подгруппы. Области значений номеров элементов обрабатываемой последовательности для соответствующих друг другу блоков памяти совпадают. Поэтому элементы последовательности с четными номера- 55 ми, поступающее с выхода сумматора 37, поступают через коммутатор 3 на информационные входы блоков 10 и 13 памяти. При этом на адресные входы этих блоков памяти через второй 9 и

5

0

0

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

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

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

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

Устройство для преобразования Адамара цифровой последовательности содержащее первый и второй коммута10

15

С второго по восьмой коммутаторы адреса, с второго по восьмой блоки памяти, с первого По восьмой элементы И, с первого по восьмой буферные регистры, с первого по четвертый элементы ИЛИ, вычитатель, третий и четвертый коммутаторы, при этом выход i-ro (i 2,8) коммутатора адреса подключен к информационному входу i-ro блока памяти, первый выход первого коммутатора подключен к информационному входу j-ro (j 1,4) блока памяти, выход которого подключен к информационному входу j-ro буферного регистра, выход которого подключен к первому входу j-ro элемента ИЛИ, второй выход первого коммутатора подключен к информационному входу (J + 4)-го блока памяти-, выход второго подключен к информа- ционному входу (j + 4)-го буферного регистра, вькод которого подключен к второму входу j-ro элемента ИЛИ, 25 первый выход второго коммутатора подключен к первьш информационным входам первого, третьего, пятого .и седьмого коммутаторов адреса, второй выход второго коммутатора подключен к первым информационным входам второго, четвертого и восьмого коммутаторов адреса, третий выход второго коммутатора подключен к второму информационному входу j-ro коммутатора адреса, четвертьй выход второго коммутатора подключен к второму информационному входу (j + 4)-го коммутатора адреса, выходы первого и второго элементов ШШ подключены к

20

30

35

„ «п первым информационным входам соответ- торы, триггер, сумматор, первьш ком- 40 ч v v

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

5

С второго по восьмой коммутаторы адреса, с второго по восьмой блоки памяти, с первого По восьмой элементы И, с первого по восьмой буферные регистры, с первого по четвертый элементы ИЛИ, вычитатель, третий и четвертый коммутаторы, при этом выход i-ro (i 2,8) коммутатора адреса подключен к информационному входу i-ro блока памяти, первый выход первого коммутатора подключен к информационному входу j-ro (j 1,4) блока памяти, выход которого подключен к информационному входу j-ro буферного регистра, выход которого подключен к первому входу j-ro элемента ИЛИ, второй выход первого коммутатора подключен к информационному входу (J + 4)-го блока памяти-, выход второго подключен к информа- ционному входу (j + 4)-го буферного регистра, вькод которого подключен к второму входу j-ro элемента ИЛИ, 5 первый выход второго коммутатора подключен к первьш информационным входам первого, третьего, пятого .и седьмого коммутаторов адреса, второй выход второго коммутатора подключен к первым информационным входам второго, четвертого и восьмого коммутаторов адреса, третий выход второго коммутатора подключен к второму информационному входу j-ro коммутатора адреса, четвертьй выход второго коммутатора подключен к второму информационному входу (j + 4)-го коммутатора адреса, выходы первого и второго элементов ШШ подключены к

0

0

5

ственно третьего и четвертого коммутаторов, вторые информационные входы которых подключены к выходам соответственно третьего и четверто5 го элементов ИЛИ, выход переноса счетчика подключен к второму установочному входу триггера, прямой выход которого подключен к управляющим входам первого, второго, пятого и шестого ко№1утаторов адреса, входам управления записью (считывание) первого, второго, пятого и шестого блоков памяти и управляющему входу четвертого коммутатора, выход кото.

5 рого является выходом нечетных чисел устройства и подключен к первым входам сумматора и вычитателя, выход которого подключен к второму информационному выходу первого коммутатор

0

7-. 14623558

pa, третий и четвертьй информацион-ход которого является вьосЬдом четных

ные входы которого являются входаьшчисел устройства и подключен к втосоответственно четных и нечетных чи-рым входам сумматора и вычитателя,

сел устройства инверсный выход, выходы старшего и младшего разрядов

триггера подключен к управляющим1-го (1 - 1,8) коммутатора адреса

входам третьего, четвертого, седьмо-подключены соответственно к первому

го и восьмого кокиутаторов входами второму входам 1-го элемента И,

управления записью (считыванием)выход которого подключен к входу

третьего, четвертого, седьмого ию разрешения записи 1-го буферного

восьмого блоков памяти и управляюще-регистра, му входу третьего коммутатора, вы