Процессор быстрого преобразования уолша-адамара

 

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

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

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

РЕСПУБЛИК (я)л G 06 F 15/332

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ.1 (21) 4795393/24 (22) 25.12.89 (46) 15.02.93. Бюл. N. 6 (71) Институт кибернетики им. В,М.ГлушкоВа (72) Л.А,Гнатив, В,Е.Коссов, М.А.Гнатив и . Г.Я.Ширмовский (56) Авторское свидетельство СССР

¹ 951320, кл, G 06 F 15/332, 1982.

Патент США N 4446530, кл. G 06 F

15/332, 1984. (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША — АДАМАРА (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для обработки цифровых сигнаИзобретение относится к области автоматики и вычислительной техники и может быть использовано для обработки изображений; для спектрального и корреляцион ного анализа, цифровой фильтрации, сжатия информации, в системах связи и т.д, Известно устройство ортогонального преобразователя цифровых сигналов по

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

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

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

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

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

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

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

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

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

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

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

15

55 подключен к второму информационному входу пятого переключателя и входу элемента НЕ, выход которого подключен к вторым информационным входам четвертого и шестого переключателей, второй информационный выход блока элементов И-ИЛИ и выходы младших разрядов счетчика подключены соответственно к первому и второму информационным входам второго коммутатора адреса, выход которого подключен к адресным входам второго и четвертого блоков памяти, выход первого коммутатора адреса подключен к адресному входу третьего блока памяти, а выход первого переключателя подключен к управляющему входу первого шинного формирователя, Нэ фиг. 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 и 6, первого коммутэтора адреса 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 и первому информационному входу второго переключателя 6, второй информационный вход которого подключен к пятому выходу CS1 блока синхронизации 9, вход 26 размера преобразования и вход 27 запуска которого являются соответственно входом размера преобразования и входом запуска устройства, тактовым и информационным входами которого являются соответственно счетный вход 28 счетчика 2 и первый информационный вход

29 первого коммутатора 8, второй информационный вход которого подключен к выходу сумматора-вычитателя 1, тактовый вход которого подключен к выходу первого разряда счетчика 2, выход первого коммутатора 8 подключен к информационным входам первого, второго, третьего и четвертого шинных формирователей 22-25, информационные входы-выходы которых подключены к информационным выходам-входам соответственно первого, второго, третьего и четвертого блоков памяти 4, 10, 11 и i2, выходы первого и второго шинных формирователей 22, 23 подключены к первым информационным входам сумматора-вычитателя 1 и второго коммутатора 13, выход 30 которого является информационным выходом устройства, выходы третьего и четвертого шинных формирователей 24, 25 подключены к вторым информационным входам сумматора-вычитателя 1 и второго коммутатора 13, управляющий вход которого подключен к шестому выходу блока синхронизации 9, седьмой, восьмой и девятый выходы CS2-CS4 которого подключены к первым информационным входам соответственно четвертого, пятого и шестого пере-. кл ючателей 16-18, выходы которых подключены к входам выбора микросхемы соответственно третьего, второго и четверто о блоков памяти 11, 10 и 12, входы разрешения записи-считывания которых соединены с управляющими входами соответственно третьего, второго и четвертого шинных формирователей 24, 23, 25 и подключены к выходам соответственно третьего, седьмого и восьмого переключателей 15, 19 и 20, первые информационные входы ко- . торых подключены соответственно к десятому, одиннадцатому и двенадцатому выходам R/W2 — В/И/4 блока синхронизации 9, второй выход которого подключен к второму информационному входу восьмого

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

Блок 3 элементов И-ИЛИ (фиг. 3) содер>кит элементы И 31-41 и элементы ИЛИ 4248, причем первые входы элементов И 31-41 являются входами С -Сг блока элементов

И-ИЛИ 3, первый управляющий вход которого соединен с вторыми входами элементов И 31, 33, 35, 37 и 41, а второй управляющий вход соединен с вторыми входами элементов.И 32, 34, 36, 38-40, выходы элементов И 31-38 попарно подключены к входам элементов ИЛИ 42-45, выходы А1-Ап-1 которых представляют адрес А и являются первым выходом А блока 3 элементов ИИЛИ, выходы элементов И 33 и 39 подключены к входам элемента ИЛИ 46, выходы элементов И 37 и 40 подключены к входам элемента ИЛИ 47, выходы элементов И 36 и

41 подключены к входам элемента ИЛИ 48, выходы В1-В>-q элементов ИЛИ 46-48 представляют адрес В и являются вторым выходом В блока 3 элементов И-ИЛИ.

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

И 62, 63 и элементы ИЛИ 64-67, причем

30

45 ется выходом 10 блока 9 синхронизации, 50

5

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

49 импульсов является входом сброса блока

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

ИЛИ 57, выход элемента И 52 является выходом 6 блока 9 синхронизации, выход злемента ИЛИ 57 является выходом 2 блока 9 синхронизации и подключен к элементу НЕ

58, к первым входам элементов И 59, 60 и к первым входам элементов ИЛИ 66, 67, выход элемента НЕ 58 является выходом 4 блока 9 синхронизации и подключен к первым входам элементов И 62, 63 и к первым входам элементов ИЛИ 64, 65, выход элемента И 59 является выходом 5 блока 9 син-хронизации и подключен к второму входу элемента ИЛИ 64, выход которого является выходом 3 блока 9 синхронизации, выход элемента И 60 является выходом 7 блока 9 синхронизации и подключен к второму входу элемента ИЛИ 65, выход которого являвыход элемента И 62 является выходом 8 блока 9 синхронизации и подключен к второму входу элемента ИЛИ 66, выход которого является выходом 11 блока 9 синхронизации, выход элемента И 63 является выходом 9 блока 9 синхронизации и подкл|очен к второму входу элемента ИЛИ

67, выход которого является выходом 12 блока 9 синхронизации.

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

1795471

"-1" вычитающего счетчика 69 соединен с счетными входами С1 и С2 регистра 68 сдвига и является вторым входом формирователя 49 импульсов, первый вход элемента

И-HE 70 является третьим входам 29 формирователя 49 импульсов, выход P-переноса вычитающего счетчика 69 подключен к второму входу элемента И-НЕ 70, выход которого подключен к второму управляющему входу V2 регистра 68 сдвига, выход четвертого (старшего) разряда которого подключен к управляющему входу V вычитающего счетчика 69, первый информационный вход

D> вычитающего счетчика 69 и выход четвертого разряда регистра 68.сдвига являются соответственно первым и вторым выходами формирователя 49 импульсов, причем первый управляющий вход V1, первый и второй информационные входы D1 и 02 регистра

68 сдвига соединены с потенциалом логической "1", а третий и четвертый информационные входы D3 и D4 — с потенциалом логического "0", Процессор работает следующим образом.

Запуск процессора осуществляется потенциалом логического "0", который подается на вход 27 запуска блока 9 синхронизации. При этом на выходе 1 блока

9 синхронизации формируется сигнал "1" (фиг. 6), который задним фронтом сбрасывает счетчик 2 в нулевое состояние. При поступлении тактовых импульсов fT на счетный вход 28 счетчика 2 на выходах его разрядов Cz-C формируется адрес А = В (A =

А1 -A„< ) начального режима работы процесI сора, который через вторые информационные входы коммутаторов адреса 7 и 14 устанавливается на адресных входах всех четырех блоков памяти 4, 10, 11 и 12. Нэ выходе паследнега (и+1)-го разряда счетчика 2 формируется сигнал выбора микросхе. мы (фиг, 6, CS 1 = CS 2), который через первый и второй информационные входы переключателей 6 и 17 потенциалом логического "0" нэ протяжении N/2 тактов выбирает микросхемы блоков памяти 4 и 10. С выходов 2 и 4 блока 9 синхронизации формируются сигналы записи-считывания (фиг, 6, R/W1, R/W3), которые через первый и

I ( второй информационные входы переключателей 5 и 19 поступают на входы записи-считывания блоков памяти 4 и 10. В течение

N/2 тактов блок памяти 4 находится в режиме записи (сигнал й/М/ 1 равен логическому

"0"), а блок памяти 10 — в режиме считывания (сигнал R/WÇ равен логической "1").

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

При этом первая половина отсчетов входно10 го сигнала x(1), х(2), ..., x(N/2) через двунаправленную шину шинного формирователя

22, управляемого сигналом "9" (фиг. 6) с выхода 2 блока 9 синхронизации, записывается в блок памяти 4, а вторая половина

15 отсчетов x(N/2+1), x(N/2+2), ..., x(N) через двунаправленную шину шинного формирователя 24, который управляется сигналом

"10" (фиг. 6) с выхода 4 блока 9 синхронизации, записывается в блок памяти 11. Одно20 временно с этим на протяжении N тактов происходит считывание первой половины коэффициентов преобразования из блока памяти 10 через шинный формирователь 23 на выход коммутатора 13, а затем — считы25 вание из блока памяти 12 через шинный формирователь 25 на выход коммутатора 13 второй половины коэффициентов преобразования от предыдущей выборки. Шинные формирователи 23 и 25 в этом режиме уп30 равляются сигналами "11" и "12" (фиг. 6) с выходов соответственно 4 и 2 блока 9 синхронизации, В течение следующих и/2 тактов(от N+1 до 3/2N) выполняется первая итерация пре35 образования. При этом с тактовой частотой, fT происходит считывание одновременно из блоков памяти 4 и 11 данных, которые через шинные формирователи 22 и 24 поступают на входы сумматора-вычитателя 1. В режи40 ме преобразования входы выбора микросхемы блоков памяти 4 и 11 управляются сигналами CS1 и CS2 (фиг. 6) с выходом соответственно 5 и 7 блока 9 синхронизации. Входы записи-считывания блоков па45 мяти 4 и 11 и шинные формирователи 22 и

24 управляются сигналами R/W1 и R/W2 (фиг. 6) с выходов соответственно 3 и 10 блока 9 синхронизации. В каждом такте на выходе сумматора-вычитателя 1 в соответ50 ствии с графом преобразования (фиг. 1) формируется сумма, а затем разность:

x1(2j-1) = x(j) + x(N/2+j);

x)(2j) = x(j) — х(Й/2+j), j=1,2, „N/2, 55 которые в течение одного такта через второй информационный вход выводятся с частотой 2fT на выход коммутатора 8, управляемого сигналом "1" (фиг. 6) с выхода 1 блока 9 синхронизации. Сумматор-вычитатель 1 работает с частотой 2fT и управляется

1795471 сигналом с выхода первого (младшего) разряда счетчика 2. При этом первая половина результатов (сумма и разность) в течение

Й/4 тактов через шинный формирователь

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

6, "11", "12") с вь1ходов соответственно 11 и

12 блока 9 синхронизации.

В течение следующих N/2 тактов (от

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

В течение следующих N/2 тактов (от

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

На и-й итерации преобразования в течение N/2òàêòîâ, начиная с (n+1)N/2+1-ra такта, на выходе сумматора-вычитателя 1 формируются коэффициенты X(1) — X(N) преобразования Уолша-Адамара, первая половина которых, если n — нечетное число, через коммутатор 8 и шинный формирователь 23 записывается в блок памяти 10, а вторая половина коэффициентов через шинный формирователь 25 — в блок памяти

12, В случае, если n — четное число, то первая половина коэффициентов преобразования через шинный формирователь 22 записывается в блок памяти 4, а вторая половина коэффициентов через шинный формирователь 42 — в блок памяти 11.

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

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

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

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

Блок 3 элементов И-ИЛИ (фиг. 3) на выходах А, В формирует сигналы адресов А = (А1 — An-1) и В = (81 — Вп-1) (фиг. 6), котоРые

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

А1 =(С а Y )V(C2аЬ);

А2 = (С2 Ы з ) V (Сз 5 Уз)

An — 2 = (Cn — 2 K Y3) V (Cn — 1 8 УЗ )

А=

An — 1 = (Сп — 1 8а УЗ ) V (Сп S УЗ ) В1 — — (с1ачз)ч(с2 абаз);

В2 =-{С28 ЧЗ)ч(СЗ ЪЧЗ)

an — 2 =(Сп — 2 ЬЧЗ)М (Сп — 1 ЬЧЗ);

Вл — 1 =(Сп — 1 аЧЗ) Ч (С, а ЧЗ), где C1 — сигнал с выхода i-го разряда счетчика 2;

Уз, Y4 = Уз — сигналы с выходов 2 и 4 блока 9 синхронизации.

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

5р ПрИ ПОдаЧЕ СИГНаЛОВ C1-Сп, ПОСтуПаЮщйх с выходов разрядов 1-и счетчика 2 на первые входы элементов И 31-41 и управляющих сигналов Уз, У4 на вторые входы элементов соответственно И 31, 33, 35, 37, 41 и

55 И 32, 34, 36, 38, 39, 40 на выходах элементов

ИЛИ 42-45 фарМИруатСя СИГНаЛЫ А1-An-1 адреса А, а на выходах элементов ИЛИ 46-48 — СИГНаЛЫ B1 — Ân-1 адрЕСа В.

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

1795471

Y3 = R/W 1=R/W 4=

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

Yi =«Фг, Уг = Y) 8 Cn+), Сп+ V Сп+1. для Ф1=1, Cn+4 V Сп+4, ДЛЯ Ф1 = О, Y4 = Уз = R/W 2=R/W 3=

Сп+4 >>/ Сп+1. дЛя Ф1=1;

Сп+1V Сп+4, для ©I =О, У5 = СЯ1 = УЗ & Сп

Y5 = CS2 = УЗ 8 Cn >

У7 = С )3 = У4 & Сп = УЗ 8 Cn, Ya = CS4 = Y4 & Сп = Y3 8 Cn., Yg = R/W1 = Y4 V У5 = УЗ V (УЗ 8 Cn);

У1а = R/W2 = Y4 VY5 = У З V (УЗ 8 Cn), У11 = R/W3 = УЗ V У7 = УЗ V (УЗ 8 Cn);

У1г = R/W3 = Уз V Т8 = Уз V (V3 & Cn), где Фг — сигнал со второго выхода форми. рователя 49 импульсов, Ф1 — сигнал с перваго выхода формирователя 49 импульсов для определения четности двоичного числа и.

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

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

49 импульсов и задним. фронтом устанавливает на прямом выходе триггера 50 потенциал логического "0". По приходу сигнала C„ с выхода и-го разряда счетчика 2 (фиг. 2) на второй вход формирователя 49 импульсов на втором выходе его формируется отрицательный импульс сигнала "1" (фиг. 6), который по заднему фронту сбрасывает счетчик

2 (фиг. 2) в нулевое состояние. Сигнал "2" формируется на выходе элемента И 52 с помощью инверсного сигнала "1" и сигнала

Сп+1 с выхода (и+1)-го разряда счетчика 2, Сигнал "3" формируется на выходе элемента ИЛИ.57 в зависимости от четности числа итераций преобразования и. Однако, при запуске блока 9 синхронизации на инверсном выходе триггера 50 устанавливается потенциал логической "1", который независимо от сигнала с первого выхода формирователя 49 импульсов, зависящего ат четности числа и, разрешает на интервале от 0 до (n+1)N прохождения через элемент И 54 сигнала С +1, На остальных интервалах сигнал "3" формируется в зави5

35 симости от четности числа и. В случае, если

n — нечетное число, то на первом выходе . формирователя 49 импульсов, на выходе 01 первого (младшего) разряда вычитающего счетчика 49 (фиг. 5) находится потенциал логической "1", который через элемент

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

"1", который разрешает прохождение через элемент И 54 сигнала Сп+, В случае, если и — четное число, то на первом выходе формирователя 49 импульсов находится потенциал логического "0", который через элемент

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

И 56 инверсного сигнала Cn+>. Сигнал "4" формирует на выходе элемента НЕ 58 из сигнала "3", Сигналы "5" и "6" формируются на выходах элементов И 59, 60 с помощью сигнала "3", прямого и инверсного сигналов

Сп, Сп. Сигналы "7" и "8" формипуются на выходах элементов И 62, 63 с помощью сигнала "4", прямого и инверсного сигналов Сп, Сп. Остальные сигналы "9" — "1?" формируются на выходах элементов ИЛИ 64-67 с помощью сигналов "3" — "8", Формирователь 49 импульсов работает следующим образом.

Перед запускам формирователя на информационных входах D)-Dn вычитающего счетчика 69 устанавливается двоичный код числа и итераций преобразования. Заг>уск формирователя 49 импульсов осуществляется потенциалом логического "0", который подается на первый вход 29 элемента И-НЕ

70, так как в исходном состоянии на выходе

Р-обратного переноса вычитающего счетчика 69 находится потенциал логической "1", который поступает на второй вход элемента

И-НЕ 70, При этом на выходе элемента И-НЕ

75 устанавливается потенциал логической 1", который поступает на управляющий вход V2 параллельнога занесения регистра

68 сдвига. В исходном состоянии на информационных входах D>-D4 регистра 68 сдвига устанавливается код 1100 для формирования импульсов длительностью 2Сп, которая получается по приходу третьего импульса сигнала Сп, а на входе Ч1 последовательного занесения регистра 68 сдвига постоянно присутствует высокий потенциал (логическая "1").

1795471

15

2 и+1 л72 ";1

20 и+1 и+2

К

По приходу сигнала с периодом С =

N/2 из выхода и-го разряда счетчика 2 (фиг.

2) на счетный вход.С2 параллельного занесения регистра 68 сдвига по заднему фронту первого импульса сигнала Сп на выходах 1-4 регистра 68 сдвига устанавливается код

1100. Потенциалом логического "0" с выхода четвертого (старшего) разряда регистра

68 сдвига в вычитающий счетчик 69 параллельно заносится двоичный код числа и итераций преобразования, .который установлен на информационных входах D>Dn вычитающего счетчика 69. При этом на выходе четвертого разряда регистра 68 сдвига устанавливается потенциал логического "0" (фиг, 6, "1"), Так как на управляющем входе V2 регистра 68 сдвига устанавливается низкий потенциал (логический "0") и на его входе V1 постоянно присутствует высокий потенциал (логическая "1"), то по приходу второго импульса сигнала Сп на счетный вход С2 регистра 68 сдвига (по заднему фронту импульса сигнала С ) на его выходах происходит сдвиг вправо ранее занесенного параллельного кода 1100. На выходах регистра 68 сдвига получается код 1110, т.е, состояние старшего разряда на выходе не изменилось и равно логическому "0", что не разрешает за пускать в ычита ющий счетчик 69.

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

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

С на счетный вход С2 регистра 68 сдвига на выходе P- обратного переноса вычитающего счетчика 69 формируется отрицательный импульс, который через элемент И-НЕ 70 потенциалом логической "1", поступающим на вход V2 регистра 68 сдвига, устанавливаФормула изобретения

Процессор быстрого преобразования

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

45 ет на его выходах параллельный код 1100.

При этом на выходе четвертого разряда регистра 68 сдвига устанавливается потенциал логического "0" {фиг. 6, "1");

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

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

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

Следовательно, быстродействие п редлагаемого процессора rio сравнению с известным процессором-прототипом повышается примерно в 4 раза.

В качестве блока памяти можно использовать серийные ОЗУ, например 537РУ10, 8 качестве коммутаторов можно использовать 4-х разрядные селекторы 2-1 типа КП11. коммутатора адреса и входу сброса счетчи ка, выходы младших разрядов которого подключены поразрядно к первому входу блока элементов И-ИЛИ, первый информационный выход которого подключен к первому информационному входу первого коммутатора адреса, а выходы младших разрядов счетчика, кроме первого, подключены поразрядно к второму информационному входу первого коммутатора адреса, выход

1795471

18 которого подключен к адресному входу первого блока памяти, входы управления записью-считыванием и выбора микросхемы которого подключены к выходам соответственно первого и второго переключателей, 5 выход и-ro разряда счетчика подключен к входу сброса блока синхронизации, второй выход которого подключен к второму входу блока элементов И-ИЛИ и первому информационному входу первого переключателя, 10 второй информационный вход второго подключен к третьему выходу блока синхронизации, четвертый выход которого подключен к третьему входу блока элементов И-ИЛИ, выход (и+1)-ro разряда счетчика 15 подключен к входу окончания итерации блока синхронизации и первому информационному входу второго переключателя, второй информационный вход которого подключен к пятому выходу блока синхронизации, вход 20 размера преобразования и вход запуска которого являются одноименными входами процессора. тактовым и информационным входами которого являются соответственно счетный вход счетчика и первый информа- 25 ционный вход первого коммутатора, второй информационный вход которого подключен к выходу сумматора-вычитателя, тактовый вход которого подключен к выходу первого разряда счетчика, о т л и ч а ю щи Й с я тем, ЗО что, с целью повышения быстродействия, в него введены три блока памяти, второй коммутатор, второй коммутатор адреса, шесть переключателей, элемент НЕ и четыре шинных формирователя, причем выход первого 35 коммутатора подключен к информационным входам с первого по четвертый шинных формирователей. информационные входывыходы которых подключены к информационным выходам-входам соответственно с 40 первого по четвертый блоков памяти, выходы первого и второго шинных формирователей подключены к первым информационным входам сумматора-вычитателя и второго коммутатора, выход которого является 45 информационным выходом процессора, выходы третьего и четвертого шинных формирователей подключены к вторым информационным входам сумматора-вычитателя и второго коммутатора, управляющий вход которого подключен к шестому выходу блока синхронизации, седьмой, восьмой и девятый выходы которого подключены к первым информационным входам соответственно . четвертого, пятого и шестого переключателей, выходы которых подключены к входам выбора микросхемы соответственно третьего, второго и четвертого блоков памяти, входы разрешения записи-считывания которых соединены с управляющим входами соответственно третьего, второго и четвертого шинных формирователей и подключены к выходам соответственно третьего, седьмого и восьмого переключателей, первые информационные входы которых подключены соответственно к десятому. одиннадцатому и двенадцатому выходам блока синхронизации, второй выход которого подключен к второму информационному входу восьмого переключателя, управляющий вход которого соединен с управляющими входами с третьего по седьмой переключателей, второго коммутатора адреса и подключен к первому выходу блока синхронизации, четвертый выход которого подключен к вторым информационным входам третьего и седьмого переключателей, выход (и+1 -го разряда пятого счетчика подключен к второму информационному входу пятого переключателя и входу элемента НЕ, выход которого подключен к вторым информационным входам четвертого и шестого переключателей, второй информационный выход блока элементов И-ИЛИ и выходы младших разрядов счетчика подключены соответственно к первому и второму информационным входам второго коммутатора адреса, выход которого подключен к адресным входам второго и четвертого блоков памяти, выход первого коммутатора адреса подключен к адресному входу третьего блока памяти, выход первого переключателя— к управляющему входу первого шинного формирователя.

1795471 с = г

Х б) 6-f

X Яь)

)И кР) х и

П-I

l,(г) X (ly-ñ)

1 х,() Х (+) словенце

Х()

Х(г)

Й о

)((zi-0

X(»4) х ург ) о-

_#_() вычитание

1795471

1795471

1795471

Ag

А2

А3

4 в, 83

8

Фиг. Е

Составитель Л.Гнатив

Техред M.Ìîðãåíòàë

Редактор Т.Иванова

Корректор А.Козориз

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 432 Тираж Подписное

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

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