Генератор систем базисных функций аристова Советский патент 1992 года по МПК G06F1/02 

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

Известен генератор функций Уолша, содержащий элемент НЕ, четыре элемента И, два n-разрядных счетчика, два элемента ИЛИ, n-входовый сумматор по mod 2, п-1 сумматоров по mod 2 первой группы, п-1 сумматоров no mod 2 второй группы, п коммутаторов.

Данный генератор формирует базисные функции Уолша, принимающие значения i 1, что является его недостатком, так

VI

как не позволяет формировать другие систе- у мы базисных функций.СО

Наиболее близким к предлагаемому по Јь технической сущности является генератор О систем базисных функций, содержащий (Jp| два n-разрядных счетчика (N-2 - размер- « ность системы функций), п элементов НЕ, Р n(m + 1)-разрядных коммутаторов (т - число hO разрядов в двоичной представлении числа М/2-1, М - число значений, принимаемых функциями, М - четное целое число, сумматор по mod М/2, л регистров сдвига, п ключевых элементов, п формирователей дополнительного кода, n-разрядный коммутатор, детектор рядом стоящих единиц, три преобразователя кодов, формирователь п временных стробов, вход задания системы

функций, вход тактовых импульсов, функциональный выход, выход номера генерируемой функции, выход конца периода генерируемых функций, в котором счетный вход первого счетчика и входы синхронизации п регистров сдвига подключены к входу тактовых импульсов генератора, разрядные выходы первого счетчика подключены к входам элемента И, выход которого подключен к входу управления записью п регистров сдвига, счетному входу второго счетчика и выходу конца периода генерируемых функций генератора, разрядные выходы второго счетчика подключены к входу детектора рядом стоящих единиц, входу данных первого преобразователя коде первому информационному входу n-разрядного коммутатора, входу формирователя п временных стробов и выходу номера генерируемой функции генератора, выход формирователи п временных стробов подключен к первому информационному входу второго преобразователя кодов и управляющему входу первого преобразователя кодов, выход которого подключен к второму информационному входу n-разрядного коммутатора, управляющий вход которого подключен к выходу детектора рядом стоящих единиц, выход n-разрядного коммутатора подключен к второму информационному входу второго преобразователя кодов, выходы разрядов с 1-го по n-й которого соединены соответственно с управляющими входами с 1-го по n-й ключевых элементов, выходы разрядов с 1-го по (п + 1)-й второго преобразователя кодов подключены к входу третьего преобразователя кодов, выходы разрядов с 1-го по n-й которого подключены к входам управления соответственно с 1-го по n-й (т + 1)-разрядных коммутаторов, выходы которых подключены к соответствующим входам сумматора no mod M/2, выход которого соединен с функциональным выходом генератора, 1-я разрядная группа параллельного входа 1-го регистра сдвига (I - 1, N/2 , i 1,п) соединена с (I 2м)-й разрядной группой входа задания системы функций генератора (размер группы равен m + 1), выход N/2 -и разрядной группы 1-го регистра сдвига подключен к входам данных i-ro ключевого элементы, выходы которых соединены о входами соответствующих формирователей дополнительного кода и первымич/жформационными входами соответствующих (т + 1)-разрядных коммутаторов, вторые информационные входы которых подключены к выходам соответствующих формирователей дополнительного кода, первый выход М/2 -й разрядной группы 1-го регистра сдвига через 1-й элемент НЕ

подключен к первому входу группы последовательно входа соответствующего регистра сдвига, выходы с 2-го rfo (m + 1)-й N/2 -и разрядной группы 1-го регистра сдеига соединены с соответствующими входами группы последовательного входа каждого регистра сдвига непосредственно.

Недостатком данного генератора системы базисных функций является его неспо0 собность формировать системы базисных функций с отличными от д° значениями первого элемента системообразующего вектора A (N/2) (аппаратно формируется значение д° 1), что приводит к сужению его

5 функциональных возможностей (фактически формируется системы базисных функций).

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

Поставленная цель достигается тем, что

5 в генератор систем базисных функций, содержащий два n-разрядных счетчика (N 2п-размерность системы функций), п элементов НЕ, п (т + 1)-разрядных коммутаторов (т - число разрядов в двоичном пред0 ставлении числа М/2-1, М - число значений, принимаемых функциями, М - четное целое число), сумматор по mod M/2, n регистров сдвига, п ключевых элементов, п формирователей дополнительного кода, п-разряд5 ный коммутатор, детектор рядом стоящих единиц, три преобразователя кодов, формирователь п временных стробов, вход задания системы функций, вход тактовых импульсов, функциональный выход, выход

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

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

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

преобразователя кодов, выход которого соединен с вторым информационным входом n-разряДного коммутатора, управляющий вход которого подключен к выходу детектора рядом стоящих единиц, выход п-разряд- 5 ного коммутатора подключен к второму информационному входу второго преобразователя кодов, выходы разрядов с 1-го по п-й которого подключены соответственно к входам управления с 1-го по n-й ключевых 10 элементов, выходы разрядов второго преобразователя кодов с 1-го по (п + 1)-й подключены к входу третьего преобразователя кодов, выходы разрядов с 1-го по n-й кото- рого подключены к входам управления соот- 15 ветственно с 1-го по n-й (т + 1)-разрядных коммутаторов, выходы которых подключены к п входам сумматора по mod M-2, выход которого соединен с функциональным выходом генератора, вход 1-й разрядной группы 20 1-го регистра сдвига (I 1, N/2, I 1,п) соединен с (I 2и)-й разрядной группой входа задания системы функций генератора (размер группы равен m + 1), выход N/2 -и разрядной группы 1-го регистра сдвига под- 25 ключей к входу данных соответствующего ключевого элемента, выходы ключевых элементов соединены с входами соответствующих формирователей дополнительного кода и первыми информационными входа- 30 ми соответствующих (т + 1)-рэзрядных коммутаторов, вторые информационные входы которых подключены к выходам соответствующих формирователей дополнительного кода, первый выход N/2 -u разрядной груп- 35 пы i-ro регистра сдвига через 1-й элемент НЕ подключен к первому входу группы последовательного входа соответствующего регистра сдвига, выходы с 2-го по (т + 1)-й Г4-2 -й разрядной группы 1-го регистра сдви- 40 га соединены с соответствующими входами группы последовательного входа каждого регистра непосредственно, введен (п + 1)-й ключевой элемент, причем n-й выход формирователя п временных стробов соединен 45 с входом управления (п + 1)-го ключевого элемента, n/2-я разрядная группы входа задания системы функций генератора соеди- нена с входом данных (п + 1)-го ключевого элемента, выход которого 50 соединен с (п + 1)-м входом сумматора по mod M-2.

На фиг. 1 приведена функциональная схема генератора для N 8; на фиг. 2-55 временные диаграммы, поясняющие работу генератора; на фиг. 3 - система базисных функций, соответствующая вектору А « {gg g1g°} и основанию степенного базиса д 1,5.

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

G(r(k).p)us%Јffi s f.t.fbtt

G(1.(2k p)-modN),.

где k 0,1п. G(1,p) А-А; А - системооб А

разующий вектор, А {gi }, I О, N/2-1; g - основание степенного базиса; М - число значений, принимаемых функциями. М - четное целое число; Д€ О, М/2-1, (1) mod дм 2 - операция деления степеней g&no mod М/2.

Системы функций (1) не зависятот основания степенного базиса д (инвариантны по отношению к нему). Поэтому одна и та же система функций, формируемая предлагаемым генератором, может быть использована для проведения различных преобразований. Например, А {g°g1g2g3}.

In

М N 8, при g expQ -rr ) преобразование Фурье, при g 2 - преобразование Ферма, при g 1 - преобразование Уолша. В качестве примера рассмотрим построение системы функций А «{g3g д д0}, M N 8

gVgWflW

3„2Г1„ог.У JL -1

g g g a -g rV9i ду-д фу-93-913

9з 9зЧЧ1 9зЧ9з

93-92дГ909 3929 190

gVgV-gV-gV

Система (2) ортогональна для любых значений g (действительных, комплексных, векторных, матричных и их расширениях) в соответствии с условием ортогональности

Е GtGV

IN.I-J.

где GJ - сопряженная функция, элементы которой являются обратными элементами, функции GJ в смысле групповой операции.

Система функций, сопряженная системе (2), имеет вид

G (8Г

-«УгУо ЗУ 1

gy$ 0 -g23g;g;-g13-gfg1p3

-gV-g gVgVg1

З%:й1з2«

V93 929 39291

gV-g2-g-gWg1

Обратная матрица G (8) для проведения обратного преобразования находится по общему для ортогональных преобразований правилу: транспортируется матрица прямого преобразования G(N), элементы транспонированной матрицы заменяются их обратными значениями.

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

д° 000; д1 001;д2 010; д3 011;

- д° - 100; -д1 101; -д2 110; -д3 - 111.

В закодированном виде операция деления степеней длв (1) сводится к арифметическим операциям над кодами показателей и знаков степеней и не зависит от основания степеней g

A(r(k),p) (A(1,(2k-p)x

х mod N- A (2k-rfk),p)) mod M/2; S(r(k),P} S(1,(2kP)x xmodN)©S(2k-r(k), p)@l,

где

О, если знак степени лен;

g Д положите1, если знак степени дД отрицателен; 1 - перенос, формируемый при выполнении (5).

0,ейли выделение целого М/2 произошло четное число раз;

1,если выделение целого М/2 произошло нечетное число раз.

Матрица (2) в закодированном виде (в котором ее формирует предлагаемый генератор) имеет вид

011 011 011 011011 011 011 0111 011 010 001 000 111 110101 100 011 001 111 101 011001 111 101 G(8) 000101010111100101110011 011 111 011 111011 111011 111 011 110001 100111 010101000 000010 100110000010100110 000001 010011 100101 110111. Генератор (фиг. 1) содержит вход 1 задания системы функций, вход 2 тактовых импульсов, п(п 3) регистров сдвига - соответственно 3-5, первый п-разрядный счетчик 7, второй n-разрядный счетчик б, детектор 8 рядом стоящих единиц в коде

данных, первый преобразователь 9 кодов, п элементов НЕ-10, п ключевых элементов 11, n-разрядный коммутатор 12, п формирователей 13 дополнительного кода, (п + 1)-й

ключевой элемент 14, n(m + 1)-разрядных коммутаторов 15, второй преобразователь 16 кодов, третий преобразователь 17 кодов, формирователь 18 п временных стробов, сумматор 19 по mod М/2, функциональный

0 выход 20, выход 21 номера генерируемой функции, выход 22 конца периода генерируемых функций.

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

5 - выход переполнения первого счетчика 7; 3-5 выходы разрядов второго счетчика 6, 6-8 выходы формирователя 18 временных стробов; 9-11 выходы 4-й разрядной группы первого регистра сдвига 3, 12-14 - выходы

0 первого формирователя 13 дополнительного кода; 15-17 - выходы разрядов функционального выхода генератора 20, - на примере формирования системы функций 7v {gVg1g } 011 010 001 ооо, м - N 8

5 (g 1,5).

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

Закодированные значения элементов системообразующего вектора A (N/2) под0 ают на вход задания системы генератора 1 соответственно, на вход четвертой разрядной группы - значение первого элемента, на вход третьей разрядной группы - значения второго элемента и т.д. Первый счетчик 7

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

0 поступающие на его вход импульсы переполнения счетчика 7 (фиг. 2.2) и формирует на своих выходах параллельный код номера генерируемой функции (фиг. 2.3-5) В начале каждого периода по переднему фронту

5 0-го тактового импульса, производится опрос состояния входа 1 генератора и соответствующая информация фиксируется в регистрах 3-5 сдвига. В тактах 1-7 регистры 3-5 сдвига работают в режиме сдвига запи0 санной в них информации, формируя на выходах 4, 2 и 1-й соответственно разрядных групп отсчеты модифицированных функций Радемахера - RI (фиг. 2.9-11), R2 и R, которые поступают на входы с 1-го по n-й ключе5 вых элементов 11, где над ними выполняется операция, эквивалентная возведению в степень 1 (отсчеты функции проходят без изменения при наличии на входе управления ключевого элемента сигнала вы- сокого уровня) или 0 (запрет прохождения).

В формировании отсчетов функций Ri- R2 и участвуют элементы НЕ 10, формирующие знаковый разряд (т + 1)-й отсчетов функций, С выхода ключевых элементов 11 отсчеты модифицированных функций Раде- махера поступают на входы соответствующих формирователей 19 дополнительного кода, в которых прямой код отсчетов функций заменяется их двоичным дополнением, и на первые информационные входы (т + 1) разрядных коммутаторов 15, На вторые информационные входы коммутаторов 15 поступают отсчеты функций в дополнительном коде (фиг. 2,12-14). В зависимости отзначе- ния сигналов на управляющих входах коммутаторов 15 на входы 1-п сумматора 19 по mod М/2 отсчетов функций Ri, R2, R4 поступают либо в прямом коде (производится сложение показателей степеней, что соответствует умножению степеней с одинаковыми основаниями), либо в дополнительном коде (производится вычитание показателей, что соответствует делению степеней). На (п + 1)-й вход сумматора 19 по mod M/2 поступают отсчеты дополнительной модифицированной функции Радемахера - RO с выхода (п + 1)-го ключевого элемента 14, Функция RO участвует в формировании генерируемых функций Gs, Ge, G, Go.

С выхода сумматора 19 по mod M/2 отсчеты генерируемых функций (фиг. 2.15-17) поступают на функциональный выход генератора 20.

Элементы 8,9,12,16,17 и 18 генератора участвуют в формировании необходимых сигналов управления.

Детектор 8 рядом стоящих единиц формирует на своем выходе сигнал при условии обнаружения в n-разрядном коде данных двух и более рядом стоящих единиц. Детектор реализуется логическими элементами 2И(п-1)ИЛИ.

Первый преобразователь 9 кодов осуществляет преобразование первых k бит входного n-разрядного кода и в их двоичное дополнение в соответствии с выражением

Q(n) D(n-k) + D(k(v)+t, где D(k(Y)) - операция инвертирования k первых разрядов входного кода D; k toQ2 - 1ЛГ- двоичный эквивалент сигнала управления. Преобразователь 9 реализуется элементами ИЛИ-НЕ и сумматором rro fnod/2.

Второй преобразователь 16 кодов осуществляет поразрядное сложение по ИЛИ двоичных данных с двух входов, сдвинутых на один разряд, в соответствии с выражением

Г dip), gi J di-i(1)Vdi(2), l 2,n,

ldn(1). l-n + 1,

где di(1), di(2)- соответственно i-e разряды данных с первого и второго входов;У- операция логического ИЛИ.

Преобразователь реализуется логическими элементами ИЛИ.

Третий преобразователь 17 осуществ- ляет преобразование входного (п-М)-го разрядного кода в n-разрядный выходной в соответствии с выражением

п+1 9п (Е di)mod2,

I k

где di - значение 1-го двоичного разряда (0,1) входного кода, k 1,п. Преобразователь реализуется логическими элементами, выполняющими функцию сложения по mod 2.

Формирователь 18 п временных стробов формирует на своих выходах временные стробы длительностью

Sk У r,(k)

где г (п) - период следования тактовых импульсов; i(k)-i-e состояние п-раэряяногр входа формирователя, k 1,п, I 2+1,2 Формирователь 18 реализуется п-разрядным дешифратором и элементами ИЛИ, осуществляющими сборку сигналов, соот- ветствующих заданным входным состоянием.

В таблице приведены значения кодов,

формируемых преобразователями и формирователями генератора (позиции 6,8, 18, 9, 12, 16, 17), при формировании системы базисных функций К- {g g у g }. М N 8. В отличие от прототипа предлагаемый

генератор формирует все системы дискреУ- ных базисных функций, определяемых cwd- темообразующим вектором A (N/2) и не зависящих от основания степенного базиса д.

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

Генератор систем базисных функций по авт. ев, № 1599850, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет формиро- вания М систем базисных функций, инвариантных к основанию степенного базиса, он содержит п 1-й блок элементов И, причем информационный вход п + 1-го блока элементов И соединен с N/2-м входом задания системы функций генератора, выход п + 1-го блока элементов И соединен с п + 1-м входом сумматора по модулю М/2.

О .1 3 Э. 4 S 6. 7.

Изобретение относится к автоматике и вычислительной технике и может быть использовано, например, в цифровых системах передачи данных. С целью расширения функциональных возможностей генератора путем формирования М систем функций. определяемых N/2-x элементным системообразующим вектором и инвариантных к основанию степенного базиса, генератор содержит два n-разрядных счетчика (N 2 - размерность системы функций), п элементов НЕ, п (т + 1)-разрядных коммутаторов (т - число разрядов в двоичном представлении числа М/2 - 1, М - число значений, принимаемых функциями, М - четное целое число), сумматор по mod М/2, п регистров сдвига, п + 1 ключевых элементов, п формирователей дополнительного кода, п-разряд- ный коммутатор, детектор рядом стоящих единиц, три преобразователя кодов, формирователь п временных стробов, вход задания системы функций, вход тактовых импульсов, функциональный выход, выход номера генерируемой функции, выход конца периода генерируемых функций. 1 табл.. Зил. «W е

.АЬ

ж:

л/г2

jj-.

Фиг.З