SU1462355A1 - Устройство дл преобразовани Адамара цифровой последовательности - Google Patents

Description

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

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

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

Устройство дл  преобразовани  Адамара цифровой последовательности содержит счетчик 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 четных чисел устройства будут по вл тьс  элементы преобразованной по Адамару входной цифровой последовательности .

Claims (1)

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

   Устройство дл  преобразовани  Адамара цифровой последовательности содержащее первый и второй коммута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-го буферного

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