Устройство для преобразования по функциям уолша

 

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

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

РЕСПУБЛИК

4 (51) G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К ABTOPCXOMV СВИДЕТЕЛЬСТВУ (21) 3535263/24-24 (22) 10.01.83 (46) 30.01.85. Бюл. ¹ 4 (72) О. Г. Кокаев, В. Б. Смолов, В. Г.,Тарасов и Т. Э. Темирханов .(71) Ленинградский ордена Ленина электротехнический институт им. В. И. Ульянова (Ленина) (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР № 640305, кл. G 06 F 15/332, 1978.

2. Авторское свидетельство СССР № 881761, кл. G 06 F 15/332, 1981.

3. Авторское свидетельство СССР № 918952, кл. G 06 F 15/332, 1982 (прототич).

4. Карцев M А., Брик В. А. Вычислительные системы и синхронная арифметика М., "Радио и связь", 1981. (54)(57) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИИ ПО ФУНКЦИЯМ УОЛТА, содержащее сумматоры, коммутатор тактовых импульсов, регистр сдвига, блок формирования функций Уолша, причем первый вход коммутатора тактовых импульсов соединен с тактовым входом устройства, первый выход коммутатора тактовых импульсов соединен с входом регистра сдвига, выход переполнения которого соединен с вторым входом коммутатора тактовых импульсов, второй выход кото рого соединен с входом блока формирования функций Уолша, информационные

„SU„„1137479 A входы сумматоров объединены и соединены с информационным входом устройства, управляющие входы сумматоров соединены с выходами соответствующих разрядов регистра сдвига, о т л и— ч а ю щ е е с я тем, что, с целью уменьшения аппаратурных затрат, в него введены регистры, преобразователи прямого двоичного кода в обратный, блок суммирования, параллельный сумматор, {fog

И-НЕ, выход которого соединен с управляющим входом блока суммирования.

11374

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

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

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

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

Недостаток устройства -- низкая производительность при обработке последовательности сигналов.

Наиболее близким к предлагаемому по технической сущности является уст-З ройство для преобразования по функциям Уолша f3) которое содержит сумматоры, коммутатор информационных сигналов, сумматоры-вычитатели, коммутатор тактовых импульсов, регистр 4О сдвига, блок формирования функций

Уолша-Радемахера, выходы функций Ðàдемахера которого подключены к управляющим входам коммутатора информацион; ных сигналов, входы которого подключе — 4 ны к выходам сумматоров, информационные входы которых объединены и являются входом устройства, управляющие входы сумматоров подключены к выходам соответствующих разрядов регистра, сдвига, выход переполнения которого соединен с управляющим входом коммутатора тактовых импульсов, первый и второй выходы которого подключены к тактовым входам регистра. сдвига и блока формирования функций Уолша-Радемахера соответственно. Вход коммутатора тактовых импульсов является

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

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

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

Цель изобретения — уменьшение аппаратурных затрат.

Поставленная цель достигается тем, что в устройство для преобразования по функциям Уолша, содержащее сумматоры, коммутатор тактовых импульсов, регистр сдвига, блок формирования функций Уолша, причем первый вход коммутатора тактовых импульсов соединен с тактовым входом устройства, первый выход коммутатора тактовых импульсов соединен с входом регистра сдвига, выход переполнения которого соединен с вторым входом коммутатора тактовых импульсов, второи выход которого соединен с -входом блока формирования функций Уолша, информационные входы сумматоров объединены и соединены с информационным входом устройства, управляющие входы сумматоров соединены с выходами соответствующих разрядов регистра сдвига, введены регистры, преобразователи прямого двоичного кода в обратный, блок суммирования, паралллельный сумматор, .(g N)-входовой элемент И-НЕ (Ийчисло отчетов исследуемого сигнала), причем выходы сумматоров соединены с информационными входами регистров, 1137479 а управляющие входы которых объединены и соединены с выходом переполнения

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

ro с номерами N - 2 + 1 (! = 1, 2, fog>N) соединены с входами элемента

И-НЕ, выход которого соединен с управляющим входом блока суммирования.

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

Устройство для преобразования по функциям Уолша (фиг. 1) содержит сум- "g маторы 1 накапливающего типа, регистры 2, преобразователи 3 прямого дво; ичного кода в обратный, блок 4 сумми- . рования параллельный сумматор 5, коммутатор 6 тактовых импульсов, регистр 7 сдвига, блок 8 формирования функций Уолша, элемент 9 И-НЕ. Информационные входы сумматоров 1 объединены и являются входом устройства, управляющие входы сумматоров 1 соеди- 4 иены с соответствующими выходами регистра 7 сдвига, выходы сумматоров

1 соединены с информационными входами соответствующих регистров 2, управлякицие входы которых объединены и соеди45 иены с выходом переполнения регистра 7 сдвига и с вторым входом коммутатора 6 тактовых импульсов, первый вход которого является тактовым вхоДОм устрОЙства. ВыхОДы регистрОВ 2 у) соединены с информационными входами соответствующих преобразователей 3 прямого двоичного кода в обратный, выходы которых соединены с информационными входами блока 4 суммирования, выход которого соединен с входом сумматора 5, выход которого является выходом устройства. Уйравляющие вхоФ ды преобразователей 3 прямого двоичного кода в обрагныи соединены с соответствующими выходами блока 8 формирования функций Уолша. Выходы блока 8 формивования функций Уолша с номерами М - 2 + 1 (i = 1. 2..... о й) соединены с входами элемента 9

И-НЕ, выход которого соединен с управляющим входом 10 блока 4 суммирова" ния. Первый и второй выходы коммутатора 6 тактовых импульсов соединены с входами регистра 7 сдвига и блока 8 формирования функций Уолша соответственно.

Блок 4 суммирования (фиг. 2) для сложения N n-разрядных чисел и (и +

+ оц М + 1)- разрядной поправки состоит из одноразрядных трехвходовых сумматоров 11, имеющих по три входа и два выхода: суммы и переноса. Сумматоры 11 сгруппированы по слоям таким образом, что связи между сумматорами 11 внутри слоя отсутствуют. выход суммы сумматора 11 находящегося в 1-м слое и j-ì разрядном сечении, является входом i + 1)-ro слоя j-го разрядного сечения, а выход переноса этого же сумматора ll является входом (! + 1)-ro слоя (р + 1)-го разрядного сечения. Исходные числа являются входами 1-ro слоя пирамиды 4 сумматоров.

Число сумматоров 11 i ãî слоя j-ro разрядного сечения определяется числом входов m и равно а; = (m;;/3), где La) обозначает целую часть а.

11ри этом ш! -3(ш /3)входов передаются через слой без изменения.

В тех случаях, когда это приводит к увеличению числа слоев блока -4 суммирования, поступаем так: если m "—

3(п3 l /3 = m) 3)m1!- /3 = ° ° е

= m;„.„-3(m;„z/31= 2, à m

=за (! -k>l; 9=1,2,3, ...), то в разрядных сечениях с номерами от j -k до j включительно устанавливается дополнительно по одному сумматору ll (его третий вход незадействован или он может быть заменен полусумматором). Сумматоры 11 i-ro слоя можно сгруппировать в многоразрядные сумматоры по и разрядов в каждом, причем число этих и-разрядных сумматоров в i-м слое равно eax f %" .

Ч г э.: а общее число и-разрядных сумматоров

s блоке 4 суммирования равно Й - 1 (что иллюстрируется на фиг. 2 дл(я

1137479 случая и = 8 и n = 2) . Поправочная константа образуется путем подключе- ния управляющегр входа 10 блока 4, суммирования к разрядным входам 1-ro слоя в тех разрядах, в которых попра- 5 вочная константа имеет единичное значение.

Работа устройства основана на математическом определении интегральных функций Уолша, которое можно 1О представить в виде

Р(! .0 1 t) =) W g (! ь )Jg

0«t Т, где 1=0, 1, 2, °, Р(0, t) =1;

>аЕ (1, t) - функции уолша °

Для дискретной формы представленИя данных преобразование (1) можно записать в матричном виде: (1)

P = WE (2) где P — - матрица интегральных функций

Уолша;

W - матрица функций Уолша; 25

Š— теплицева верхнетреугольная матрица, элементы которой, включая главную диагональ, равны единице.

Коэффициенты С разложения произволь-ЗО

1 ного сигнала, представленного совокупностью ординат Х (! = 1,...,Й), в

1 ряд интегральных функций Уолша с учетом (2) равны

С =W Å Х, где

С

С2

С = 2 — вектор коэффициентов разложения;

c„ х<

Х вЂ” вектор ординат иссле, 2 дуемого процесса;

N - число ординат исследуемого процесса.

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

На вход устройства в двоичном коде в такт с синхроимпульсами поступают значения ординат исследуемого процесса. Ординаты поступают на инфор 5 мационные входы сумматоров 1, работой которых управляет регистр 7 сдвига. Управляющий вход каждого сумматора 1 соединен со своим разрядом регистра 7 сдвига так, что -й сумматор 1 соединен с 1-м разрядом регистра 7 сдвига. После прихода на вход регистра 7 сдвига N синхроимпульсов на выходах сумматоров 1 накапливаются суммы, соответствующие произведению процесса Х на матрицу Е. В это время регистр 7 сдвига вырабатывает импульс переполнения. по которому значения сумм из сумматоров 1 переписываются в регистры 2 и который дает разрешение на прохождение синхроимпульсов на тактовый вход блока 8 формирования функций Уолша. После передачи сумм в регистры 2 память сумматоров

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

Выходы функций Уолша блока 8 управляют работой преобразователей 3 прямого двоичного кода в обратный: если значение функции Уолша равно +1, то соответствующее значение из регистра 2 через преобразователь 3 передается в прямом коде; если значение функции Уолша равно — 1, тс содержимое регистра 2 передается в обратном коде, В результате на вход блока 4 суммирования поступают N произведений компонентов вектора сумм, хранящихся в регистрах 2, на дискретную функцию

Уолша. Блок 4 суммирования формирует сумму поступающих на ее входы чисел в виде двухрядного кода по аЛгоритму сложения массива чисел с хранением переносов. Результат преобразования двухрядного кода в однорядный с помощью сумматора 5 пропорционален значению коэффициента разложения при той функции Уолша, значение которой в данный момент присутствует на выходе блока 8.

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

В силу свойств функций Уолша число отрицательных компонентов иа входе блока 4 суммирования во всех случаях, кроме вычисления коэффициента разложения при знакопостоянной функции, одинаково, поэтому заранее мо479 8

При условии реализации устройства на больших интегральных схемах принил

Йаем t = t> = t = ь, где — время с срабатывания логического элемента; тогда t = 24. Блок 4 суммирования для сложения 1024 исходных чисел и числа-поправки содержит шестнадцать слоев сумматоров 11 (в каждом слое связи. между одноразрядными сумматора— ми отсутствуют), и цикл срабатывания подсчитывается по .формуле !!с = 1.о tcq где и „ - время срабатывания одного слоя.

Время работы сверхпараллельного сумматорр а р авно

1137

1 ... 1 0 0 0 ... 0 1

25 (Fog +1) разрядов разрядов жет быть вычислена поправка Р, обеспечивающая сложение массива чисел в дополнительном виде, Поправка P представляет собой константу, которая генерируется в блоке 4 суммирования при формировании всех коэффициентов разложения, кроме первого.

Это обеспечивается тем, что значение каждой функции Уолша, кроме первой, сопровождается единичным сигналом на

1 выходе элемента 9 И-НЕ. Последнее, в свою очередь, обеспечивается, во-первых, тем, что значение функции Уолша равное +1, интерпретируется как логическая единица, а значение, равное !5

-1, — как логический ноль, и, вовторых, тем, что в силу свойств функций Уолша элемент 9 И-НЕ имеет toq N входов, к которым подключены вы::оды функций Уолша с номерами, равными - 20

N " 2 " + 1 (-i = 1, 2,..., tog

Для вычисления поправки P необходимо сложить N/2 одинакбвых чисел, равных для N = 8 и n = 2 значение поправки р = 110100. 30

Оценим быстродействие предлагаемого устройства, считая, что исследуемый сигнал содержит и = 1024 = 2

10 отсчетов, а каждый отсчет представлен

12-разрядным двоичным кодом (n = 12)

35 что является достаточно распространенным случаем. При этом сумматоры 1 могут иметь неодинаковую разрядность но быстродейстьие определяется сумматОрОм 1 с наибОльшей разряднОстью 4 равной и + fog> М = 22 разрядам. Разрядность сумматоров 1 выбирается для наихудшего случая, когда все отсчеты, имеют значения близкие или равные максимальному 7 H при этОм В суммато 5 рах 1 не должно возникать переполнения разрядной сетки. Цикл работы параллельного двоичного накапливающего сумматора с последовательным распространением переносов определяется по формуле

+ + tp, где Се, 1 - соответственно время формирования сигналов переносаи суммыв однораз-55 рядном двоичном сумматоре, - время срабатывания региP .стра памяти. сс = Мй9 + ",tq + м где t — время формирований сигна6 лов подготовительных функций прохождения переноса; время формирования сигналов переноса в каждом из ярусов Ы-ярусной схемы формирования переносов; время формирования суммы

6М . после образования сигналов переноса.

Число ярусов М = 3, так как ири построении схемы переносов отдельные разряды объединяются в группы по 4 разряда. Обозначив через й„p время срабатывания преобразователя 3, по.— лучаем, что время умножения вектора, сумм, хранящихся в регистре 2, на значение функции Уолша равно т = е„ + 16 е „.+ 3 (+ ) + с.

При условии реализации устройства на больших интегральных схемах прил нимаем с " где — время срабатывания логичесу кого элемента, откуда Т = 24 ь,, л

Таким образом, условие балансирования быстродействия сумматоров 1, с одной стороны, и преобразователей

3, блока 4 суммирования и сумматора

5, с другой стороны, выполнено:

24л и Т = 2 4л с

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

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

1137479

10 процессов, основное оборудование, устройства-прототипа при обработке последовательности исследуемых сигналов простаивает в течение 33X рабочего времени. Следовательно, произво- 5 дительность предлагаемого устройства в этом случае больше производительности прототипа на ЗЗХ.

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

При этом из всех возможных реализаций прототипа будем предполагать экономичную реализацию: считаем, что сумматоры-вычитатели являются устройствами !5 параллельного типа с последовательным распространением переноса. Сумматоры, коммутатор тактовых импульсов, регистр сдвига и блок формирования функций Уолша имеются в обоих устрой- 20 ствах, поэтому они исключаются из дальнейшего рассмотрения. Для срав-! нения вариантов будем пользоваться такой характеристикой сложности устройств, как цена по Квайну — суймар, 25 ное число входов элементов, состав.ляющих устройство. Обозначим эту единицу "кв". Считаем все узлы реализованными на элементах типов И, ИЛИ, НЕ. 11ри сравнении будем, также считатьр0 что N = 1024 и и = 12, а при выборе разрядности узлов будем исходить из необходимости устранить переполнение разрядной сетки сумматоров при наихудшем случae1 когда значения всех отсчетов близки к максимально возможTl ному равному 2 -1. Тогда в устройстве-прототипе в сумматорах будет 22 разряда (и + fog Й), а число разрядов в сумМаторах-вычитателях с учетом 40 знакового разряда равно 33 (n +

+2 fogy и < 1 ) . Сложность коммутатора, . представляющего собой (и + fog

М 45 ,без учета ограничения на число входов логических элементов равна

С„ = Зй(и + fog N) = 3 ° 1024 22 =

67584 кв.

Каждый сумматор-вычитатель прото- 50 тйпа состоит из комбинационного сумматора-вычитателя и регйстра. Структура комбинационногосумматора-вычитателя наиболее проста, когда регистр состоит из триггеров Т-типа. Приэтом 55 сложность комбинационного одноразрядного сумматора-вычитателя равна

22 кв, сложность Т-триггера, реализованного по схеме трех триггеров, равна 20 кв, а общая сложность сумматоров-вычитателей прототипа равна

С = (22 + 20) (n + 2 fog

1419264 кв

Таким образом, сложность устройствапрототипа за вычетом исключенных из сравнения узлов равна

С = С»-. + С = 1486848 кв«.

В предлагаемом устройстве разряд-. ность регистров 2 равна 22, и они могут быть реализованы на триггерах

О-типа, имеющих сложность (реализа-ция по схеме трех триггеров) 19 кв.

Затраты оборудования на реализацию регистров 2 составляют

5 = !9 (n + fog N) Й =

19«22" 1024 кв = 428032 кв.

Каждый из преобразователей 3 состоит из (и + tog N) схем типа 2-2И2ИЛИ, поэтому сложность Й преобразо- . вателей прямого двоичного кода в обратный составляет

7 (и + fog,й) Й = 7 "22 х х 024 кв = 157696 кв.

Как было показано выше, блок 4 суммирования состоит из Й-1 многоразрядного сумматора по (n + fog< N) Раз . рядов в каждом. учитывая, что сложность одноразрядного комбийационного сумматора равна 17 кв, общие затраты оборудования на реализацию блока 4 суммирования равны

S<, = 1У. (и q fog N)(N - 1) =

17 22 1023 кв = 382602 кв.

Сложность сверхпараллельного суммато-: ра 5 при 33 разрядах составляет с

Сложность элемента 9 И-НЕ равна

S< = foq N + 1 = 11 кв. Таким обра-. зом, сложность предлагаемого устройства за вычетом исключенных из рассмотрения узлов равна

S<+ trc.+ Scc-+ H

= 969397 кв.

Предлагаемое устройство проще прототипа на 517451 кв. Упрощение достигнуто за счет того, что каждый многоразрядный сумматор в блоке суммирования содержит н4 PoggN разрядов меньше, чем каждый из сумматоров-вычитателей в прототипе.! 137479

1137479 Ь Ч ъ о 9.

ЗНИИПИ Заказ 10526/37 Тирак 710 По Фисное, Филиал ШШ "Ватамт", г.Ужгород, ул.Проектная, 4