Устройство для преобразования по функциям Уолша Советский патент 1985 года по МПК G06F17/14 

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для преобразования по функциям Уолша, содержащее сумматоры, коммутатор тактовых импульсов, регистр сдвига, блок формирования функций Уолша, причем первый вход коммутатора тактовых импульсов соединен с Тактовым входом устройства, первый выход коммутатора тактовых импульсов соединен с входом регистра сдвига, выход переполнения которого соединен с вторым входом коммутатора тактовых импульсов, второй выход ко торого соединен с входом блока формирования функций Уолша, информационные входы сумматоров объединены и соединены с информационным входом устройства, управлякяцие входы сумматоров соединены с. выходами соответствующих разрядов регистра сдвига, введены регистры, преобразователи прямого двоичного кода в обратный, блок суммирования, парапллельный сумматор, . ()-входовой элемент И-НЕ (N число отчетов исследуемого сигиала), причем выходы сумматоров соедииеиы с информационными входами регистров. управляклцие которых объединены и соединены с выходом переполнения I регистра сдвига, выходы регистров соединены с информационными входами преобразователей прямого двоичного кода в обратный, выходы которых соединены с информационнымл входами блока суммирования, выход которого соединен с входом параллелльного сум .матора, выход которого является выходом устройства, управляюпщй вход каждого ;преобразователя прямого двоичного кода в обратный соединен с соответствуклчим выходом блока формирования функций Уолша, выходы которо го с номерами N - + 1 (i 1, 2, EogjN) соединены с входами элемента И-НЕ, выход которого соединен с управляющим входом блока суммирования, На фиг. 1 приведена структурная схема устройства; на фиг. 2 - функци ональная электрическая схема блока суммирования для случая сложения вос ми двухбитовых чисел и числа-поправки, являкяцегося шестибитовым числом, поскольку сумма восьми двухбитовых чисел со знаком в любом случае может быть представлена шестью битами. Устройство для преобразования по . функциям Уолша (фиг. 1) содержит сум маторы 1 накапливающего типа, регист ры 2, преобразователи 3 прямого двоичного кода в обратный, блок 4 рования,параллельный сумматор 5, ком мутатор 6 тактовых импульсов, регистр 7 сдвига, блок 8 формирования функций Уолша, элемент 9 И-НЕ, Инфор мащюнные входы сумматоров 1 объеди иены и являются входом устройства, управляющие входы сумматоров I соеди нены с соответствующими выходами регистра 7 сдвига, выходы сумматоров 1 соединены с информационными входам соответствующих регистров 2, управля кщие входы которых объединены и соед нены с выходом переполнения регистра 7 сдвига и с вторым входом коммутатора 6 тактовых импульсов, первый вход которого является тактовым входом устройства. Выходы регистров 2 соединены с информационными входами соответствуклцих преобраз,ователей 3 прямого двоичного кода в обратный, выходы которых соединены с информаци онными входами блока 4 суммирования, выход которого соединен с входом сум матора 5, выход которого является выходом устройства. Управляющие вхо,1ды преобразователей .3 прямого двоичного кода в обратный соединены с соответствующими выходами блока 8 формирования функций Уолша. Выходы блока 8 формиоования функций Уолша с номерами N - 2 + 1 (i 1 2 . ..... ) соединены с входами элемента 9 И-НЕ, выход которого соединен с управляюпр1м входом 10 блока 4 суммирования. Первый и второй выходы коммутатора 6 тактовых импульсов соединены, с входами регистра 7 сдвига и блока 8 формирования функций Уолша соответст венно. Блок 4 суммирования (фиг. 2) для сложения N п-разрядных чисел и (п + oq-N + 1)- разрядной поправки состоит из одноразрядных трехвходовых сумматоров 1 1, имегацих по т|5И входа и два выхода: суммы и переноса. Сумматоры I1 сгруппированы по ёлоям таким образом, что связи между суймат.О рами II внутри слоя отсутствуют, выход суммы сумматора 11. находящегося в i-м слое и J-M разрядном сеченин, является входом v i + 1) го слоя j то разрядного сечения, а выход переноса этого же сумматора 11 является входом (i + 1)-го слоя ( 1)-го разрядного сечения. Исходные числа являются входами 1-го слоя пирамиды 4 сумматоров. Число сумматоров 1 i-ro слоя j-го разрядного сечения определяется числрм входов и равно ,3 Г-., где ta обозначает целую часть d. При этом m,i -3( /З входов передаются через слой без изменения. В тех случаях, когда это приводит к увеличению числи слоев блока -4 суммирования, поступаем так: если ,.j/3l .,, ,, /3 .:. m,j, (ц,./3 2, a т,,..-, 31 (j - 1, 2, 3,...), TO в разрядных сечениях с номерами от до j включит ьно устанавливается дополнительно цо одному сумматору 11 его третий вход незадействован или он может быть заменен полусумматором. Сумматоры 11 i-ro слоя можно сгруппировать в многоразрядные сумматоры по п разрядов в каждом прнчем число этих п-разрядных сум- маторов в i-M слое равно max {ll,j3 . а общее число п-разрядных сумматоров в блоке 4 суммирования равно N - 1 (что йллнх:трируется на фиг. 2 ддя 51 случая N n 2). Поправочная константа образуется путем подключения управляющего входа 10 блока 4, v. суммирования к разрядным входам 1-го слоя в тех разрядах, в которых попра вочная константа имеет единичное зна чение . Работа устройства основгша на математическом определении интегральных функций Уолша, которое можно представить в виде 4 P(i + 1, t) J Wa ( ,1: )dT; Ost sT, где i 0, 1, 2, ...; P(0, t) 1; Wa Z (i, t) - функции Уолша. Для дискретной формы представления данньЕХ преобразование (I) можно записать в матричном виде: Р WE,(2) где Р - матрица интегральных функций Уолша; W - матрица функций Уолша; Е - тепЛицева верхнетреугольная матрица, элементы которой, включая главную диагональ, равны единице. Коэффициенты С разложения произволь кого сигнала, представленного совоку ностью ординат Xj (i I,...,N), в ряд интегральных функций Уолша с уче том (2) равны С W Е X, вектор коэффициенто разложения; вектор ординат иссл дуемого процесса; число -ординат иссле дуемого процесса. .Устройство работает следующим об разом. На вход устройства в двоичном ко де в такт с синхроимпульсами поступ ют значения ординат исследуемого процесса. Ординаты поступают на инф

мационные входы сумматоров 1 , работой которых управляет регистр 7 сдвига. Управляющий вход каждого сумматочаях, кроме вычисления коэффициента разложения при знакопостоянной функции, одинаково, поэтому заранее мо9ра 1 соединен со своим разрядом регистра 7 сдвига так, что i-й сумматор 1 соединен с i-м разрядом регистра 7 сдвига. После прихода на вход регистра 7 сдвига N синхроимпульсов на выходах сумматоров 1 накапливаются суммы; соответствующие произведению процесса X на матрицу Е. В это время регистр 7 сдвига вырабатывает импульс переполнения, по которому значения сумм из сумматоров 1 переписьшаются в регистры 2 и который дает разрешение на прохождение синхроимпульсов на тактовый вход блока 8 формирования функций Уолша. После передачи сумм в регистры 2 память сумматоров 1 накапливающего типа сбрасывается в ноль. Цепи сброса на фиг. 1 не показаны. На вход устройства начинают поступать ординаты следующего исследуемого процесса. Выходы функций Уолша блока 8 управляют работой преобразователей 3 прямого двоичного кода в обратный; если значение функции Уолша равно +1, то соответствующее значение из регистра 2 через преобразователь 3 передается в прямом коде; если значение .. функции Уолша равно -1, тс содержимое регистра 2 передается в обратном коде В результате на вход блока 4 суммирования поступают N произведений компонентов векто за сумм, хранящихся в регистрах 2, на дискретную функцию Уолша. Блок 4 суммирования формирует сумму поступаюш 1х на ее входы чисел в виде двухрядного кода по аЛгоритму сложения массива чисел с хранением переносов. Результат преобразования двухрядного кода в ОДНОРЯДЙЫЙ с ПОМО щью сумматора 5 пропорционален значению коэффициента разложения при той функции Уолша, зИачение которой в данный момент присутствует на выходе блока 8. При балансировке быстродействия сумматоров , с одной стороны, и преобразователей 3, блока 4 суммирования и сумматора 5, с другой стороны, темп выдачи коэффициентов раз;|Ожения равен темпу поступления цифровых кодов на входе устройства. В силу свойств функций Уолша число отрицательных компонентов на входе блока 4 суммирования во всех служет быть вычислена поправка Р, обеспечивающая сложение массива чисел в дополнительном виде. Поправка Р представляет собой константу, которая генерируется в блоке 4 суммирования при формировании всех коэффициентов разложения, кроме первого. Это о.беспечивается тем, что значение каждой функции Уолша, кроме первой, сопровождается единичным сигналом на выходе элемента 9 И-НЕ. Последнее, в свою очередь, обеспечивается, во-первых, тем, что значение функции Уолша, равное +1, интерпретируется как логическая единица, а значение, равное -I, - как логический цель, и, вовторых, тем, что в силу свойств функций Уолша элемент 9 И-НЕ имеет входов, к которым-подключены выходы функций Уолша с номерами, равными N - + 1 (. 1, 2,..., ). Для вычисления поправки Р необходимо сложить N/2 одинаковых чисел, равных Для N 8 и п 2 значение поправки Р 110100. Оценим быстродействие предлагаемо го устройства, считая, что исследуемый сигнал содержит N 1024 2 отсчетов, а каждый отсчет представле 12-разрядным двоичным кодом (п 12) что является достаточно распространенным случаем. При этом сумматоры 1 могут иметь неодинаковую разрядность но быстродейстБие определяется сумма тором 1 с наибольшей разрядностью, равной п + tog2N 22 разрядам. Разрядность сумматоров 1 выбирается для наихудшего случая, когда все отсчеты имеют значения близкие или равные максимальному, и при этом в сумматоpax 1 не должно возникать переполнения разрядной сетки. Цикл работы параллельного двоичного накапливающего сумматора с последовательным распространением переносов определяется по формуле tg 22 tg + t + tp, где te, t соответственно время формирования сигналов переносаи суммы в однораз-55 рядном двоичном сумматоре J tp - время срабатывания реги.стра памяти. ™,« Ири условии . реализации устройства на больших интегральных схемах приниhfaeM tp t tn , где С - время срабатывания логического элемента; тогда tc 24. Блок 4 суммирования для сложения 1024 исходных чисел и числа-поправки содержит шестнадцать слоев сумматоров 1 Г (в каждом слое связи, мезкду одноразрядными сумматорами отсутствуют) , и цикл срабатывания, подсчитывается по формуле ,Чс 1. ten где tji - время срабатывания одного слоя. ремя работы сверхпараллельного сумматора равно tco Mtg + МЦ + , где t. - время формирований сигначлов подготовительных функций прохождения переноса; время формирования сигналов переноса в каждом из ярусов М-ярусной схемы формирования переносов; время формирования суммы после образования сигналов переноса. Число ярусов М 3, так как при построении схемы переносов отдельные разряды объединяются в группы по 4 разряда. Обозначив через tпо время срабатывания преобразователя 3, по,лучаем, что время умножения вектора , сумм, хранящихся в регистре 2, на значение функции Уолша равно ( ц) + ц„, 16 tf, .+ 3 При условии реализации устройства на больших интегральных схемах при- нимаем tpp ct-- у вм где (, - время срабатываниялогического элемента, откуда Т 24 t),. Таким образом, условие балансирования быстродействия сумматоров 1, „ „ с одной стороны, и преобразователей 3, блока 4 суммирования и сумматора 5, с другой стороны, выполнено: и Т Z4C, Поэтому задержка в обработке двух последовательных процессов отсутствует, a это приводит к повьшению степени загрузки оборудования и увеличению производительности устройства, В этом случае, когда темп последовательной вьщачи коэффициентов разложения в устройстве-прототипе равен темпу поступления ординат исследуемых

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

Покажем, что в предлагаемом устройстве затраты оборудования умень- Ю шаются по сравнению с прототипом. При этом из всех возможных реализаций прототипа будем предполагать экономичную реализацию: считаем, что сумматоры-вьгчитатели являются устройствами 15 параллельного типа с последовательным распростране нием переноса. Сумматоры, коммутатор тактовых импульсов, регистр сдвига и блок формирования функций Уолша имеются в обоих устрой-20 ствах, поэтому они исключаются из дальнейшего рассмотрения. Для сравнения вариантов будем пользоваться такой харгжтеристикой сложности устройств, как цена по Квайну - суймар, 25 ноечисло входов элементов, составляющих устройство. Обозначим эту единицу KB. Считаем все узлы реализованными на элементах типов И, ИЛИ, НЕ. При сравнении будем также считать о что N 1024 и п 12, а при выборе разрядности узлов будем исходить из необходимости устранить переполнение раз15ядной сетки сумматоров при наихудшем случае, когда значения всех ,. отсчетов близки к максимально возможному, равному 2 -1. Тогда в устройстве-прототипе в сумматорах будет 22 разряда (п + tog-N), а число разрядов в сумматорах-вычитателях с учетом 40 знакового разряда равно 33 (п + +2 1). Сложность коммутатора, представляющего собой (п + tog2N) схем - 2 -... -2 - 2 И,- ИЛИ

К45

.без учета ограничения на число входов

логических элементов равна

Cj. 3N(n + fogjN) 3102422

67584 кв. Каждый сумматор-вычитатель прото- 50

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

С.. (22 + 20) (п + 2 + + 1) 42ЗЗ-1024 KB

1419264 KB

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

С С,. +Сее 1486848 KBj

В предлагаемом устройстве разрядность регистров 2 равна 22, и они могут быть реализованы на триггерах D-типа, имеющих сложность (реализация по схеме трех триггеров) 19 кв.. Затраты оборудования на реализацию регистров 2 составляют

SP - 19 (п + og2N).N

19.22-1024 KB 428032 кв.

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

$ц 7- (п + ) N. 7-22 X X 10.24 кв 157696 кв.

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

17. (п )(N - 1) « 17 22 4023 KB 382602 кв.

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

1056 кв.

fc

Сложность элемента 9 И-НЕ равна Sj + 1 11 кв. Таким образом, сложность предлагаемого устройства за вычетом исключенных из рассмотрения узлов равна

S Sp + S, + Snc.+ Sec-+ SH 969397 кв.

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

СИ