Процессор быстрого преобразования уолша-адамара Советский патент 1993 года по МПК G06F15/332 

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

Известно устройство ортогонального преобразователя цифровых сигналов по Уолшу - Адамару, содержащее блок Формирования временных интервалов, 2N ( размерность преобразования) блоков элементов И, N блоков элементов ИЛИ, N регистров и N сумматоров-вычитателей.

Недостатком такого устройства является его сложность из-за большого числа регистров и сумматоров-вычитателей.

Известно устройство, содержащее шесть коммутаторов, три регистра сдвига,

сумматор-вычитатель и блок синхронизации.

Недостатком этого устройства является низкое быстродействие и его сложность из- за наличия многокаскадных регистров сдвига.

Наиболее близким по технической сущности является процессор быстрого преобразования Уолша - Адамара, содержащий сумматор-вычитатель, счетчик, первый и второй регистры, блок элементов И-ИЛИ, блок памяти, первый и второй переключатели, коммутатор адреса, коммутатор, две ячейки хранения промежуточных данных (ЯХПД), схему модификации адреса, триггер, четыре элемента И и блок синхронизации, первый выход которого подключен к управляющим входам коммутатора, первого

-Ч

ю

ОН

Јь

XJ

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

Недостатком этого процессора является низкое быстродействие из-за последовательного считывания и записи промежуточных данных в блок памяти. При этом все коэффициенты преобразования считываются из блока памяти за 2N(n+1) тактов.

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

0 считывания коэффициентов преобразования и записи новых входных данных.

Это достигается тем, что в процессор введены три блока памяти, второй коммутатор, второй коммутатор адреса, шесть пере5 ключателей, элемент НЕ и четыре шинных формирователя, причем выход первого коммутатора подключен к информационным входам первого, второго, третьего и четвертого шинных формирователей, информаци0 онные входы-выходы которых подключены к информационным выходам-входам соответственно первого, второго, третьего и четвертого блоков памяти, выходы первого., и второго шинных формирователей подклю5 чены к первым информационным входам сумматора-вычитателя и второго коммутатора, выход которого является информационным выходом устройства, выходы третьего и четвертого шинных формирователей под0 ключены к вторым информационным входам сумматора-вычитателя и второго коммутатора, управляющий вход которого подключен к шестому выходу блока синхронизации, седьмой, восьмой и девятый выхо5 ды которого подключены к первым информационным входам соответственно четвертого, пятого и шестого переключателей, выходы которых подключены к входам выбора микросхемы соответственно третье0 го, второго и четвертого блоков памяти, входы разрешения записи-считывания которых соединены с управляющими входами соответственно третьего, второго и четвертого шинных формирователей и подключены к

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

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

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

На фиг. 1 представлен граф быстрого преобразования Уолша-Адамара; на фиг. 2 - функциональная схема процессора; на фиг. 3 - схема блока элементов И-ИЛИ; на фиг. 4 - схема блока синхронизации, на фиг.

5- схема формирователя импульсов; на фиг.

6- временная диаграмма работы процессора для N 16 (N 2 -размерность преобразования).

Процессор содержит сумматор-вычита- тель 1, счетчик 2, блок элементов И-ИЛИ 3, первый блок памяти 4, первый и второй переключатели 5 и 6, первый коммутатор адреса 7, первый коммутатор 8, блок синхронизации 9, три блока памяти 10-12, второй коммутатор 13, второй коммутатор адреса 14, шесть переключателей 15-20, элемент НЕ 21 и четыре шинных формирователя 22-25, причем первый выход блока синхронизации 9 подключен- к управляющим входам первого коммутатора 8, первого и второго переключателей 5 и б, первого коммутатора адреса 7 и входу сброса счетчика 2, выходы младших разрядов 1-п которого подключены поразрядно к первому входу блока элементов ИтИЛИ 3, первый информационный выход которого подключен к первому информационному входу А первого коммутатора адреса 7, а выходы младших разрядов 2-п счетчика 2, кроме первого, подключены поразрядно к второму информационному входу А первого коммутатора адреса 7, выход которого подключен к адресному входу первого блока памяти 4, выходы управления записью/считыванием R/W1 и выбора микросхемы CS1 которого подключены к выходам соответственно пер- вото и второго переключателей 5 и 6, выход п-го разряда счетчика 2 подключен к входу сброса блока синхронизации 9. второй выход которого подключен к второму входу, блока элементов И-ИЛИ 3 и первому информационному входу первого переключателя

5, второй информационный вход которого подключен к третьему выходу R/W1 блока синхронизации 9, четвертый выход которого подключен к третьему входу блока элементов И-ИЛИ 3, выход (п+1}-го разряда счетчика 2 подключен к входу окончания итерации блока синхронизации 9 и первому информационному входу второго переключателя б. второй информационный вход которого

0 подключен к пятому выходу CS1 блока синхронизации 9, вход 26 размера преобразования и вход 27 запуска которого являются соответственно входом размера преобразования и входом запуска устройства, такто5 вым и информационным входами которого являются соответственно счетный вход 28 счетчика 2 и первый информационный вход 29 первого коммутатора 8, второй информационный вход которого подключен к выходу

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

5 формирователей 22-25, информационные входы-выходы которых подключены к информационным выходам-входам соответственно первого, второго, третьего и четвертого блоков памяти 4, 10, 11 и 12,

0 выходы первого и второго шинных формирователей 22, 23 подключены к первым информационным входам сумматора-вычитателя 1 и второго коммутатора 13, выход 30 которого является информационным выхо5 дом устройства, выходы третьего и четвертого шинных формирователей 24, 25 подключены к вторым информационным входам сумматора-вычитателя 1 и второго коммутатора 13, управляющий вход которо0 го подключен к шестому выходу блока синхронизации 9, седьмой, восьмой и девятый выходы CS2-CS4 которого подключены к первым информационным входам соответственно четвертого, пятого и шестого пере-

5 ключателей 16-18, выходы которых подключены к входам выбора микросхемы соответственно третьего, второго и четвер- TOi о блоков памяти 11, 10 и 12, входы разре- шения записи-считывания которых

0 соединены с управляющими входами соответственно третьего, второго и четвертого шинных формирователей 24, 23, 25 и подключены к выходам соответственно третьего, седьмого и восьмого переключателей 15,

5 19 и 20, первые информационные входы которых подключены соответственно к десятому, одиннадцатому и двенадцатому выходам R/W2 - R/W4 блока синхрониза- ции 9, второй выход которого подключен к второму информационному входу восьмого

переключателя 20, управляющий вход которого соединен с управляющими входами третьего, четвертого, пятого, шестого, и седьмого переключателей 15-19, второго Ьммутатора адреса 14 и подключен к первому выходу блока синхронизации 9, четвертый выход которого подключен к вторым информационным входам третьего и седьмого переключателей 15 и 19, выход (п+1)-го разряда счетчика 2 подключен к второму информационному входу пятого переключателя 17 и к входу элемента НЕ 21, выход которого подключен к вторым информационным входам четвертого и шестого переключателей 16 и 18, второй информационный выход блока элементов И-ИЛИ 3 и выходы младших разрядов 2-п счетчика 2 подключены соответственно к первому и второму информационным входам В и В второго коммутатора адреса 14, выход которого подключен к адресным входам второго и четвертого блоков памяти 10 и 12, выход первого коммутатора адреса 7 подключен к адресному входу третьего блока памяти 11, а выход первого переключателя 5 подключен к управляющему входу первого шинного формирователя 22.

Счетчик 2 является (п+1)-разрядным двоичным счетчиком.

Все блоки памяти 4, 10, 11 и 12 емкостью N/2m бит, где т-число разрядов одного отсчета входного сигнала.

Блок 3 элементов И-ИЛИ (фиг. 3) содержит элементы И 31-41 и элементы ИЛИ 42- 48, причем первые входы элементов И 31-41 являются входами Ci-C2 блока элементов И-ИЛИ 3, первый управляющий вход которого соединен с вторыми входами элементов И 31, 33, 35, 37 и 41, а второй управляющий вход соединен с вторыми входами элементов .И 32, 34, 36, , выходы элементов И 31-38 попарно подключены к входам элементов ИЛИ 42-45, выходы Ai-An-1 которых представляют адрес А и являются первым выходом А блока 3 элементов И- ИЛИ, выходы элементов И 33 и 39 подключены к входам элемента ИЛИ 46, выходы элементов И 37 и 40 подключены к входам элемента ИЛИ 47, выходы элементов И 36 и 41 подключены к входам элемента ИЛИ 48, выходы Bi-Bn-i элементов ИЛИ 46-48 представляют адрес В и являются вторым выходом В блока 3 элементов И-ИЛИ.

Блок 9 синхронизации (фиг. 4) содержит .формирователь 49 импульсов, триггер 50, элемент НЕ 51, элемент И 52, элемент ЙЛИ- НЕ 53, элемент И 54, элемент НЕ 55, элемент И 56, элемент ИЛИ 57, элемент НЕ 58, элемент 1/1 59,60, элемент НЕ 61, элементы И 62, 63 и элементы ИЛИ 64-67, причем

первый вход 26 формирователя 49 импульсов является входом задания размера преобразования, второй вход формирователя 49 импульсов является входом сброса блока

9 синхронизации и соединен с вторыми входами элементов И 59, 62 и с входом элемента НЕ 61, выход которого подключен к вторым входам элементов И 60, 63, третий вход 27 формирователя 49 импульсов явля0 ется входом запуска блока 9 синхронизации и соединен с входом сброса триггера 50, счетный вход которого соединен с выходом элемента ИЛИ-НЕ 53, первый выход формирователя 49 импульсов подключен к второ5 му входу элемента ИЛИ-НЕ 53, второй выход формирователя 49 импульсов является выходом 1 блока 9 синхронизации и через элемент НЕ 51 подключен к первым входам . элементов И 52 и ИЛИ-НЕ 53, второй вход

0 элемента И 52 является входом окончания итерации блока 9 синхронизации и соединен с вторым входом элемента И 54 и через элемент НЕ 55 соединен с вторым входом . элемента И 56, инверсный и прямой выходы

5 триггера 50 подключены к первым входам элементов И соответственно 54 и 56, выходы которых подключены к входам элемента ИЛИ 57, выход элемента И 52 является выходом 6 блока 9 синхронизации, выход эле:

.0 мента ИЛИ 57 является выходом 2 блока 9 синхронизации и подключен к элементу НЕ 58, к первым входам элементов И 59, 60 и к первым входам элементов ИЛИ 66, 67, выход элемента НЕ 58 является выходом 4

5 блока 9 синхронизации и подключен к первым входам элементов И 62, 63 и к первым входам элементов ИЛИ 64, 65, выход элемента И 59 является выходом 5 блока 9 син-- хронизации и подключен к второму входу

0 элемента ИЛИ 64, выход которого является выходом 3 блока 9 синхронизации, выход элемента И 60 является выходом 7 блока 9 синхронизации и подключен к второму входу элемента ИЛИ 65, выход которого явля5 ется выходом 10 блока 9 синхронизации, выход элемента И 62 является выходом 8 блока 9 синхронизации и подключен к второму входу элемента ИЛИ 66, выход которого является выходом 11 блока 9

0 синхронизации, выход элемента И 63 является выходом 9 блока 9 синхронизации и подключен к второму входу элемента ИЛИ 67, выход которого является выходом 12 блока 9 синхронизации.

5 Формирователь 49 импульсов (фиг. 5) содержит регистр 68 сдвига, вычитающий счетчик 49 и элемент И-НЕ 70, причем информационные входы Di-Dn вычитающего счетчика 69 являются первым входом 28 формирователя 49 импульсов, счетный вход

-1 вычитающего счетчика 69 соединен с счетными входами С1 и С2 регистра 68 сдвига и является вторым входом формирователя 49 импульсов, первый вход элемента И-НЕ 70 является третьим входом 29 формирователя 49 импульсов, выход Р переноса вычитающего счетчика 69 подключен к второму входу элемента И-НЕ 70, выход которого подключен к второму управляющему входу V2 регистра 68 сдвига, выход четвертого (старшего) разряда которого подключен к управляющему входу V вычитающего счетчика 69, первый информационный вход DI вычитающего счетчика 69 и выход четвертого разряда регистра 68 .сдвига являются соответственно первым и вторым выходами формирователя 49 импульсов, причем первый управляющий вход V1, первый и второй информационные входы D1 и D2 регистра 6.8 сдвига соединены с потенциалом логической 1, а третий и четвертый информационные входы D3 и D4 - с потенциалом логического О.

Процессор работает следующим образом.

Запуск процессора осуществляется потенциалом логического О, который подает- ся на вход 27 запуска блока 9 синхронизации. При этом на выходе 1 блока 9 синхронизации формируется сигнал 1 (фиг. 6), который задним фронтом сбрасывает счетчик 2 в нулевое состояние. При поступлении тактовых импульсов fT на счетный вход 28 счетчика 2 на выходах его разрядов Са-Cn формируется адрес А В (А AI -Ап-1) начального режима работы процессора, который через вторые информационные входы коммутаторов адреса 7 и 14 устанавливается на адресных входах всех четырех блоков памяти 4, 10, 11 и 12. На выходе последнего (п+1)-го разряда-счетчика 2 формируется сигнал выбора микросхе- мы (фиг. 6, CS 1 CS 2), который через первый и второй информационные входы переключателей 6 и 17 потенциалом логического О на протяжении N/2 тактов выбирает микросхемы блоков памяти 4 и 10. С выходов 2 и 4 блока 9 синхронизации формируются сигналы записи-считывания (фиг. 6, R/w l, R/w 3), которые через первый.и второй информационные входы переключателей 5 и 19 поступают на входы записи-считывания блоков памяти А и 10. В течение N/2 тактов блок памяти 4 находится в режиме записи (сигнал R/W 1 равен логическому О), а блок памяти 10 - в режиме считывания (сигнал R/w 3 равен логической 1). Процессор готов к начальному режиму работы. При этом последовательность х(1), х(2), .... x(N) отсчетов входного сигнала с частотой

тактовых импульсов ft (фиг.б) через первый информационный вход 29 коммутатора 8 поступает на информационные входы шинных формирователей 22 и 24. Коммутатор 8 уп- 5 равляется сигналом 1 (фиг, 6) с выхода 1 блока 9 синхронизации и на время поступления отсчетов входного сигнала подключен к информационному входу 29 процессора. При этом первая половина отсчетов входно0 го сигнала х(1), х(2), ..., x(N/2) через двунаправленную шину шинного формирователя 22, управляемого сигналом 9 (фиг. 6) с выхода 2 блока 9 синхронизации, записывается в блок памяти 4, а вторая половина

5 отсчетов x(N/2+1), x(N/2+2), .... х(М) через двунаправленную шину шинного формирователя 24, который управляется сигналом 10 (фиг. 6) с выхода 4 блока 9 синхронизации, записывается в блок памяти 11. Одно- 0 временно с этим на протяжении N тактов происходит считывание первой половины коэффициентов преобразования из блока памяти 10 через шинный формирователь 23 на выход коммутатора 13, а затем - считы5 вание из блока памяти 12 через шинный формирователь 25 на выход коммутатора 13 второй половины коэффициентов преобразования от предыдущей выборки. Шинные формирователи 23 и 25 в этом режиме уп0 равляются сигналами 11 и 12 (фиг. 6) с выходов соответственно 4 и 2 блока 9 синхронизации.

В течение следующих п/2 тактов (от N+1 до 3/2N) выполняется первая итерация пре5 образования. При этом с тактовой частотой fr происходит считывание одновременно из блоков памяти 4 и 11 данных, которые через шинные формирователи 22 и 24 поступают на входы сумматора-вычитателя 1. В режи0 ме преобразования входы выбора микросхемы блоков памяти 4 и 11 управляются сигналами CS1 и CS2 (фиг. 6) с выходом соответственно 5 и 7 блока 9 синхронизации. Входы записи-считывания блоков па5 мяти 4 и 11 и шинные формирователи 22 и 24 управляются сигналами R/W1 и R/W2 (фиг. 6) с выходов соответственно 3 и 10 блока 9 синхронизации. В каждом такте на выходе сумматора-вычитателя 1 в соответ0 ствиис графом преобразования (фиг.- формируется сумма, а затем разность: xi(2j-1} x(j) + x(N/2+j); xi(2j) x(j)-x(N/2+j); j 1,2,..., N/2,

5 которые в течение одного такта через второй информационный вход выводятся с частотой 2fT на выход коммутатора 8, управляемого сигналом 1 (фиг. 6) с выхода 1 блока 9 синхронизации. Сумматор-вычита- тель 1 работает с частотой 21 и управляется

сигналом с выхода первого (младшего) разряда счетчика 2. При этом первая половина результатов (сумма и разность) в течение N/4 тактов через шинный формирователь 23 записывается с частотой 2fT в блок памяти 10, а в течение следующих N/4 тактов через шинный формирователь 25 с той же частотой 2fT в блок памяти 12 записывается вторая половина результатов. В этом режиме преобразования входы выбора микросхемы блоков памяти 10 и 12 управляются сигналами CS3 и CS4 (фиг. 6, 7, 8) с выходов 8 и 9 блока 9 синхронизации, а шинные формирователи 23 и 25 и входы записи-считывания блоков памяти 10 и 12 управляются сигналами R/W3 и R/W4 (фиг. 6, 11, 12) с выходов соответственно 11 и 12 блока 9 синхронизации.

В течение следующих М/2 тактов (от 3/2N + 1 до 2N) выполняется вторая итерация преобразования. При этом из блоков памяти 10 и 12 одновременно с тактовой частотой fr считываются данные, которые через шинные формирователи 23, 25 поступают на входы сумматора-вычитателя 1. На выходе сумматора-вычитателя 1 в каждом такте получаются результаты сумма, затем разность, которые с частотой 2fr выводятся на выход коммутатора 8. При этом первая половина результатов в течение N/4 тактов через шинный формирователь 23 записывается с частотой 2fr в блок памяти 10, а вторая половина результатов в течение следующих N/4 тактов через шинный формирователь 25 с той же частотой 2tr - в блок памяти 12.

В течение следующих N/2 тактов (от 2N+1 до5/2М) выполняется аналогично первой третья итерация преобразования,затем от 5/2N+1 до 3N тактов выполняется аналогично второй четвертая итерация и т.д., пока не выполнится п итераций преобразования.

На n-й итерации преобразования в течение N/2 тактов, начиная с (n+1)N/2+1-ro такта, на выходе сумматора-вычитателя 1 формируются коэффициенты Х(1) - X(N) преобразования Уолша-Адамара, первая половина которых, если п - нечетное число,. через коммутатор 8 и шинный формирователь 23 записывается в блок памяти 10, а вторая половина коэффициентов через шинный формирователь 25 - в блок памяти 12. В случае, если п четное число, то первая половина коэффициентов преобразования через шинный формирователь 22 записывается в блок памяти 4, а вторая половина коэффициентов через шинный формирователь 42 - в блок памяти 11.

В течение следующих N тактов, начиная с (n+2)N/2+1-ro такта, происходит считывание с тактовой частотой fT сначала с блока памяти 10, а затем с блока памяти 12 (если п - нечетное число) или с блока памяти 4, а затем с блока, памяти 11 (если п - четное

число) коэффициентов преобразования, которые выводятся на выход коммутатора 13. При этом последний коэффициент X(N) преобразования выводится на выход коммутатора 13 на (п+4)М/2-ом такте, Одновременно

со считыванием коэффициентов преобразования происходит запись через коммутатор 8 и шинные формирователи 22 и 24 в блок памяти 4, а затем в блок памяти 11 (если п - нечетное) или через шинные формирователи 23 и 25 - в блок памяти 10, а затем в блок памяти 12 (если п - четное) значений отсчетов входного сигнала из следующей выборки. Во время считывания коэффициентов преобразования коммутатор 8 подключается к информационному входу 29 процессора.

Блок 3 элементов И-ИЛ1/1 (фиг. 3) на выходах А, В формирует сигналы адресов А (Ai - An-i) и В (Bi - Bn-i) (фиг. 6), которые

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

В 4

А1(С1&Уз)У(С2&Уз)- A2(C2&Y3)V(C3&Y3); An -2 (Cn -2 & Y3 ) V ( Cn - i & Y3 ); An-i(Cn-i&Y3)V(Cn&Y3)t

Bi (Ci&Y3)v(c2&y3); B2(C2&Y3)v(C3&Y3); Bn-2(cn 2&Y3)v(cn -1 &Ys); Bn-1 (Cn-1 &Y3)v(cn&Y3),

где О - сигнал с выхода i-го разряда счетчика 2;

Ya, Y4 Ys - сигналы с выходов 2 и 4 блока 9 синхронизации.

Блок 3 элементов И-ИЛИ работает следующим образом.

При подаче сигналов СгСп, поступающих с выходов разрядов 1-п счетчика 2 на первые входы элементов И 31-41 и управляющих сигналов Ys, Y4 на вторые входы элементов соответственно Л 31, 33, 35, 37,41 и

-И32,34, 36,38,39,40на выходах элементов ИЛИ 42-45 формируются сигналы Ai-An-i адреса А, а на выходах элементов ИЛИ 46-48 - сигналы В1 - Вп-1 адреса В.

Блок 9 синхронизации на выходах 1-12 формирует управляющие сигналы Yi-Yi2

{фиг. 6), которые описываются логическими функциями в виде следующих уравнений:

У1 Ф2,

Y2 Yi & Сп+1,

Y3 R/W 1 R/W 4

Cn-HVCn-Н.для

Cn+W Сп + 1, ДЛЯ Ф1 0,

Y4 Уз R/W 2 R/W 3 Cn+WCn + T, для Cn + tVCn+f, для Ot 0,

У 5 CS1 Y3 & Сп- Ye CS2 Уз & Сп ,

Y7 CS3 Y4 & Сп - Уз & Сп , .Y8 CS4-Y4&Cn Y3-&Cn-, Yg R/W1 Y4 V Y5 V3 V (Y3 & Cn); . Yio R/W2 Y4 VYe 73 V (Уз & ) Y11 R/W3 Ys V Y Ys V (Уз & Cn)- Yi2 R/W3 Y3 V T8 Уз V (3 & Cn), где Ф2 - сигнал со второго выхода формирователя 49р импульсов, 01 - сигнал с первого выхода формирователя 49 импульсов для определения четности двоичного числа п.

Блок 9 синхронизации работает следующим образом.

Запуск блока 9 синхронизации осуществляется потенциалом логического О, который подается на вход 27 блока 9 синхронизации и запускает формирователь 49 импульсов и задним.фронтом устанавливает на прямом выходе триггера 50 потенциал логического О. По приходу сигнала Сп с выхода п-го разряда счетчика 2 (фиг. 2) на второй вход формирователя 49 импульсов на втором выходе его формируется отрицательный импульс сигнала 1 (фиг. 6), который по заднему фронту сбрасывает счетчик 2 (фиг. 2) в нулевое состояние. Сигнал 2 формируется на выходе элемента И 52 с помощью инверсного сигнала 1 и сигнала Сп+1 с выхода (п+1)-го разряда счетчика 2. Сигнал 3 формируется на выходе элемента ИЛИ 57 в зависимости от четности числа итераций преобразования п. Однако, при запуске блока 9 синхронизации на инверсном выходе триггера 50 устанавливается по- тенциал логической 1, который независимо от сигнала с первого выхода формирователя 49 импульсов, зависящего от четности числа п, разрешает на интервале от 0 до (п+1)М прохождения через элемент И 54 сигнала Сп+1. На остальных интервалах сигнал 3 формируется в зависимости от четности числа п. В случае, если п - нечетное число, то на первом выходе формирователя 49 импульсов, на выходе DI первого (младшего) разряда вычитающего

счетчика 49 (фиг. 5) находится потенциал логической 1, который через элемент ИЛИ-НЕ 53 не разрешает прохождение сигнала 1, управляющего работой триггера 50 по заднему фронту. При этом состояние

триггера 50 не изменилось и на инверсном его выходе находится потенциал логической 1, который разрешает прохождение через элемент И 54 сигнала Сп-н. В случае, если п

- четное число, то на первом выходе формирователя 49 импульсов находится потенциал логического О, который через элемент ИЛИ-НЕ 53 разрешает прохождение сигнала 1, поступающего на счетный вход триггера 50. .При этом сигнал 1 по заднемуфронту устанавливает на прямом выходе триггера 50 потенциал логической 1, который разрешает прохождение через элемент И 56 инверсного сигнала Cn-н. Сигнал 4 формирует на выходе элемента НЕ 58 из

сигнала 3. Сигналы 5 и 6 формируются на выходах элементов И 59, 60 с помощью сигнала 3, прямого и инверсного сигналов Сп, Сп. Сигналы 7 и 8 формируются на выходах элементов l/i 62, 63 с помощью сигнала 4, прямого и инверсного сигналов Сп, Сп. Остальные сигналы 9 - 12 формируются на выходах элементов ИЛИ 64-67 с помощью сигналов 3 - 8.

Формирователь 49 импульсов работает

следующим образом.

Перед запуском формирователя на информационных входах D-|-Dn вычитающего

счетчика 69 устанавливается двоичный код числа п итераций преобразования. Запуск

формирователя 49 импульсов осуществляется потенциалом логического О, который подается на первый вход 29 элемента И-НЕ 70, так как в исходном состоянии на выходе Р-обратного переноса вычитающего счетчика 69 находится потенциал логической Г, который поступает на второй вход элемента И-НЕ 70. При этом на выходе элемента И-НЕ 75 устанавливается потенциал логической 1, который поступает на управляющий

вход V2 параллельного занесения регистра 68 сдвига. В исходном состоянии на информационных входах регистра 68 сдвига устанавливается код 1100 для формирования импульсов длительностью 2Сп, которая

получается по приходу третьего импульса сигнала Сл, а на входе V1 последовательного занесения регистра 68 сдвига постоянно присутствует высокий потенциал (логическая 1).

По приходу сигнала с периодом Сп N/2 из выхода n-го разряда счетчика 2 (фиг. 2) на счетный вход С2 параллельного занесения регистра 68 сдвига по заднему фронту первого импульса сигнала Сп на выходах 1-4 регистра 68 сдвига устанавливается код 1100. Потенциалом логического О с выхода четвертого (старшего) разряда регистра 68 сдвига в вычитающий счетчик 69 параллельно заносится двоичный код числа п ите- раций преобразования, .который установлен на информационных входах Di Dn вычитающего счетчика 69. При этом на выходе четвертого разряда регистра 68 сдвига устанавливается потенциал логического О (фиг, 6, Г).

Так как на управляющем входе V2 регистра 68 сдвига устанавливается низкий потенциал (логический О) и на его входе V1 постоянно присутствует высокий потенциал (логическая 1), то по приходу второго импульса сигнала Сп на счетный вход С2 регистра 68 сдвига (по заднему фронту импульса сигнала Сп) на его выходах происходит сдвиг вправо ранее занесенного параллельного кода 1100. На выходах регистра 68 сдвига получается код 1110, т.е. состояние старшего разряда на выходе не изменилось и равно логическому О, что не разрешает- запускать вычитающий счетчик 69.

С приходом очередного третьего импульса сигнала Cn.no заднему фронту на выходе четвертого разряда регистра 68 сдвига после очередного сдвига вправо устанавливается потенциал логической 1, который запускает вычитающий счетчик 69. При этом счетчик 69 начинает вычитать.

После прихода п-го импульса сигнала Сп на счетный вход С2 регистра 68 сдвига на выходе Р- обратного переноса вычитающего счетчика 69 формируется отрицательный импульс, который через элемент И-НЕ 70 потенциалом логической 1, поступающим на вход V2 регистра 68 сдвига, устанавливает на его выходах параллельный код 1100. При этом на выходе четвертого разряда регистра 68 сдвига устанавливается потенциал логического О (фиг. 6, 1);

В известном процессоре-прототипе последний коэффициент преобразования формируется на выходе сумматора-вычитателя на (2n+1)N-OM такте.. В предлагаемом процессоре последний

коэффициент преобразования формируется на выходе сумматора-вычитателя на (1+п/2)М-ом такте.

Таким образом, коэффициент К повышения быстродействия в предлагаемом

процессоре определяется выражением

(2n+1)N 2 п + 1 K(n/2.+ 1 )N n/2 +Г

что при п 3-14 составляет 2,8-3,6 раза. Однако, если учесть то, что в предлагаемом процессоре в отличие от известного процессора-прототипа операция считывания коэффициентов преобразования выполняется одновременно С операцией записи новых значений отсчетов входного сигнала из следующей выборки, то коэффициент повышения быстродействия будет определяться следующим выражением

, (n + 1)2N 4.n+1

к -(n/2 + i)N А тг+т .; что при п. 3-14 составляет 3,2-3,8 раза. Следовательно, быстродействие предлагаемого процессора по сравнению с известным процессором-прототипом повышается примерно в 4 раза..

В качестве блока памяти можно исполь- зовать серийные ОЗУ, например 537РУ10.

В качестве коммутаторов можно использовать 4-х разрядные селекторы 2-1 типа КП11.

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

Формула изобр е т е н и я Процессор быстрого преобразования Уолша - Адамара, содержащий сумматор- вычитатель, счетчик, блок элементов Й- ИЛИ, первый блок памяти, первый и второй переключатели, первый коммутатор адреса, первый коммутатор и блок синхронизации, первый выход которого подключен к управляющим входам первого коммутатора, первого и второго переключателей, первого

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

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

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

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

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

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

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

Коэффициенты преобразования (Уев умножения на 1/У )

Фиг.З

Фи г. 5