Устройство для реализации быстрого преобразования Хартли Советский патент 1988 года по МПК G06F17/14 

4 4; 4

СХ)

СП

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

Целью изобретения является повьше ние быстродействия.

На фиг.1 изображена блок-схема устройства; на фиг.2 - структурная схема блока управления.

Устройство (фиг.1) содержит блок памяти, блок 2 постоянной памяти, блок 3 управления, умножитель 4, накапливающий сумматор 5, элемент ИЛИ 6, коммутаторы 7-9, счетчики 10,11, накапливающий сумматор I2, регистры сдвига 13,14.

Блок 3 управления (фиг.2) содержит одновибратор 15,-элемент 16 ИЛИ, триггер 17 обработки, счетчик итераций 18, генератор 19 тактовых импульсов, накапливающий сумматор 20, двоичный счетчик 21, дешифратор 22 нулевой операции, элемент ИСКШОЧАЮ- ЩЕЕ ИЛИ 23, элемент ИПИ-НЕ 24, элемент И 25.

В устройстве реализован алгоритм быстрого преобразования Хартли. Преобразование Хартли действительной функции (tr),-гг 0,1, ...,N-1, определяется как сумма косинусного и синусного преобразований, т.е.

IN

Н() N 2If () cos(2 i-9 4;/NT, ;

TtO

5 о, 1,...,N-1,

где cos 10 cos в + sin б .

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

А + В W , + CW,

где А,В,С - первый,- второй и третий операнды, извлекаемые из блока 1 оперативной памяти;

W и Wj - первый и второй коэффи циенты, извлекаемые из блока 2 постоянной памяти.

Каждое элементарное преобразование выполняется за четыре такта следующим образом. ;

1. Из блока 1 оперативной памяти извлекается первый операнд и заносится в накапливающий сумматор 5.

2. Из блока 1 оперативной памяти извлекается второй операнд и поступает на вход умножителя 4, на другой вход которого поступает коэффициент, извлекаемый из блока 2 постоянной

0 памяти, с выхода умножителя 4 произведение поступает на вход накапливающего сумматора 5,

3,Из-блока 1 оперативной памяти извлекается третий операнд и посту5 пает на вход умножителя 4, на другой вход умножителя 4 поступает коэффициент, извлекаемый из блока 2 постоянной памяти, с выхода умножителя 4. произведение поступает на вход на--.

0 капливающего сумматора 5.

4.С выхода накапливающего сумматора 5 результат сложений записывается в блок 1 оперативной памяти.

На первой итерации преобразования

5 операнды извлекаются из первой обласг ти блока 1 оперативной памяти. Особенностью первой итерации является то, что из блока 1 оперативной памяти извлекаются два операнда, над кот;

0 торыми производятся операции сложения (без умножения на коэффициент), результат записывается во вторую область блока 1 оперативной памяти. На второй итерации первый, второй

5 и третий операнды извлекаются из второй области блока 1 оперативной памяти, а результат вычисления заносится в первую область блока 1 оперативной памяти. На последующих ите0 рациях области блока 1 оперативной памяти попеременно меняются.

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

В исходном состоянии в первую

5 область блока 1 оперативной памяти записана исходная информация в двоично-инверсном порядке, счетчики 10, 11 обнулены, в регистр 13 записана . .нулевая информация, в регистр 14 в

Q младший разряд записан уровень 1, в остальные разряды регистра - уровни О.

По сигналу Запуск обработки, поступающему по входу XI устройства,

е триггер 17 обработки устанавливается в единичное состояние, сигнал 1 с выхода триггера 17 обработки поступает на вход генератора 19 тактовых импульсов, который начинает формировать последовательность тактовых импульсов, поступающих на тактовые входы накапливающего сумматора 20, двухразрядного счетчика 21 и через выход Y5 блока 3 управления- на тактовый вход накапливающего сумматора 5. На счетные входы счетчиков 10, 1 и тактовый вход накапливающего сумматора 12 с выхода Y2 блока 3 уп- равления поступают счетные импульсы, формируемые на выходе одновибра- тора 15 из заднего фронта импульсов, поступающих с выхода накапливающего сумматора 20, эти же сигналы через выход Y3 блока 3 управления поступают на управляющий вход блока 2 постоянной памяти, причем низкий уровень сигнала соответствует выбору значений косинуса, а высокий - сину- са. Сигналы с выходов накапливающего сумматора 20 формируют на выходах элементов ИПИ-НЕ 24 и И 25 уровни сигналов, соответствующие началу первого и четвертого такта. С выхода элемента И 25 через выход Y3 блока 3 управления на управляющий вход коммутатора 9 приходит управляющий сигнал, в результате чего к управляющему входу коммутатора 8 подключается выход регистра 13 (уровень О) или выход регистра 14.(уровень 1). На выходе коммутатора 8, в соответствии с кодами на управляющем входе коммутатора, формир:,потся адреса- для блока 1 оперативной памяти из- кодов, снимаемых с выходов счетчиков 10,1-1 или с выхода Y3 блока 3 управления. .При наступлении на вход элемента ИЛИ 6 кодов адресов коэффициентов, соответствующих значениям коэффициентов либо О, либо -1, либо -I, на выходе элемента ИЛИ 6 формируется уровень О, который через вход ХЗ блока 3 управления поступа- ет на вход элемента ИЛИ 16. Уровень О с выхода элемента ИЛИ 16 через выход Y5 блока управления поступа- ет на управляющий вход коммутатора 7 в результате чего, на вход накаплива- ющего сумматора 5 передается информация с выхода блока 1 оперативной памяти.

На выходе дешифратора 22 нулевой .операции формируется сигнал управ- ления знаком, который через выход Y5 блока 3 управления поступает на тактовый вход накапливающего сумматора 5, причем уровень О соответствует операции сложения, уровень 1 - операции вычитания, на выходе дешифратора 22 нулевой операции формируется сигнал, поступающий на прямой и инверсный входы накапливающего сумматора 20, который формирует код номера такта выполняемого элементарного преобразования.

На четвертом такте каждой итерации на выходе элемента И 25 формируется уровень 1, который поступает на вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 23, на другой вход которого поступает сигнал со старшего разряда счетчика итераций 18. На выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 23 формируется , уровень 1, который через выход Y4 блока 3 управления поступает на управляющий вход блока 1 оперативной памяти, в результате чего информация с выхода накапливаюп;его сумматора 5 записывается во вторую область блока 1 оперативной памяти.

Задним фронтом сигнала с выхода старшего разряда счетчика 10 через вход Х2 блока 3 управления содержимо счетчика итераций 18 увеличивается, на единицу, этим же сигналом в младший разряд регистра 14 записьшается 1 со сдвигом на один разряд исходной информации в сторону старших разрядов, в младший разряд регистра 13 записывается уровень О со сдвигом на один разряд в сторону старших разрядов. Устройство переходит к выполнению второй итерации.

На второй итерации информация считывается из второй области блока 1 оперативной памяти, а результат заносится во вторую область блока 1 оперативной памяти.

На первом такте второй итерации элемент ИЛИ-НЕ 24 формирует на выходе уровень 1, который с помощью элемента ИЛИ 16 на выходе Y5 блока 3 управления формирует уровень О, который поступает на управляющий вход коммутатора 7, в результате чего к входу накапливающего сумматора 5 подключается выход блока 1 оперативной памяти. На последующих тактах элементарного преобразования на вход накапливающего сумматора 5 поступает информация с выхода умножителя .

В остальном вторая итерация заполняется аналогично первой. Последующие итерации выполняются аналогично второй.

После завершения п-й итерации устройство переходит в исходное состояние.

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

Устройство для реализации быстрого преобразования Хартли, содержащее блок постоянной памяти, умножитель, первый коммутатор, первый счетчик, первый регистр сдвига, первый накапливающий сумматор, блок управления и блок памяти, выход которого подключен к первому входу умножителя, второй вход которого подключен к выходу блока постоя нной памяти, адресный вход которого подключен к выходу первого накапливающего сумматора, информационный выход первого счетчика подключен к первому и второму информационным входам первого коммутатора, выход которого подключен к адресному входу блока памяти, выход переноса .первого счетчика подключен к тактовому входу первого регистра сдвига, отличающееся тем, что, с целью повьппения быстродействия, в него введены второй и третий коммутаторы, второй счетчик, второй накапливающий сумматор, второй регистр сдвига, и элемент ИЛИ, выход которого под, 44А8156

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

выход которого подключен к информа- 5

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

10 блока памяти5 выходы разрядов первого накапливающего сумматора подключены к соответству}ощим входам элемента И и входам разрядов нулевой итерации блока управления, четвертый выход ко15 торого подключен к тактовому входу второго накапливающего сумматора и управляющему входу третьего коммутатора, второй информационный вход которого подключен к выходу умножителя,

20 выход второго регистра сдвига подключен к второму информационному входу второго коммутатора, а вход запуска блока управления является входом запуска устройстваэ причем блок управ25 ления содержит триггер, счетчик итераций, накапливающий сумматор, эле-, мент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент РШИ-НЕ, элемент И, дешифратор, элемент РШИ, счетчик, одновибратор..и генератор

30 тактовых импульсов, выход которот о подключен к тактовому входу накапливающего сумматора и счетному входу . счетчика, информационный выход которого подключен к первому входу дешиф

Изобретение относится к области вычислительной техники и может быть использовано для решения задач цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Поставленная цель достигается аа счет того, что в состав устройства входят блок памяти 1, блок постоянной памяти 2, блок управления 3, умножитель 4, накапливающий сумматор 5, элемент ИЛИ 6, коммутаторы 7,8,9, счетчики 10,11, накапливающий сумма- . тор 12, регистры сдвига 13,14 и соответствующие связи между узлами устройства. 2 ил. с iS (Л

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

подключен к управляющему входу перво- 45 ИЛИ-НЕ и элемента И и входу одновиб- го коммутатора, третий информационный вход которого подключен к информационному выходу второго счетчика, второй выход блока управления подключен к управляющему входу второго коммутатора, входу управления считывания блока постоянной памяти и четвертому информационному входу первого коммутатора, выход переноса первого счетчика подключен к тактовому входу второго регистра сдвига и входу новой итерации блока управления, четвертый выход которого подключен к входу управления записьюратора, выход которого подключен к входу обнуления счетчикаj выход старшего разряда и выход переноса которого подключены соответственно к вто- 50 рому входу элемента ИСКЛЮЧАЮЩЕЕ Ш1И и первому установочному входу триггера, выход которого подключен к входу запуска генератора тактовых импульсов, второй вход дешифратора соединен с вторым входом элемента РШИ и является входом простой операции блока управления, входом запуска которого является второй установочный вход триггера, третий вход дешифра55

чен к информационному входу накапливающего сумматора, выход первого разряда которого подключен к первым входам элемента ИЛИ-НЕ и элемента И, вы- 40 ходы которых подключены к первым входам соответственно элемента ИЛИ и элемента ИСКгаО ШЛЩЕЕ ИЛИ, выход второго разряда накапливающего сумматора подключен к вторым входам элемента

ИЛИ-НЕ и элемента И и входу одновиб-

ратора, выход которого подключен к входу обнуления счетчикаj выход старшего разряда и выход переноса которого подключены соответственно к вто- рому входу элемента ИСКЛЮЧАЮЩЕЕ Ш1И и первому установочному входу триггера, выход которого подключен к вхоу запуска генератора тактовых импульсов, второй вход дешифратора соединен с вторым входом элемента РШИ и является входом простой операции блока управления, входом запуска которого является второй установочный вход триггера, третий вход дешифра

. 7144 81

тора является входом нулевой операции блока управления, входом новой итерации которого является счетный вход счетчика итераций, выход одно- вибратора является первьм выходом блока управления, вторым выходом которого являются объединенные между собой выход элемента И и выход второФив. 2

58

го разряда накапливающего сумматора, выход элемента ИСКЛЮЧАКШЩЕ ИЛИ является третьим выходом блока управления, четвертым выходом которого являются объединенные между собой выход элемента ИЛИ, второй выход дешифратора и выход генератора тактовых импульсов.