Нелинейный вероятностный преобразователь Советский патент 1978 года по МПК G06F7/58 G06F17/18 

(54) НЕЛИНЕЙНЫЙ ВЕРОЯТНОСТНЫЙ ПРЕОБРАЗОВАТЕЛЬ

Изобретение относится к области вы числительной техники и может быть использовано при моделировании случайных процессов, а также в стохасти еских вычислительных машинах при вводе преобразовании и выводе информации. Известны вероятностные преобразователи, преобразующие случайную пойледовательнорть Бернулли в цифровой код. Математическое ожидание которого пропорционально некоторой функции от Вероятности появления импульса во вхо ном случайном потоке. Известен вероятностный преобразователь, содержащий реверсивный счетчик, схему сравнения и генератор слу Чайных чисел l . Однако он не позвоПяет реализовать заданные функциональ ные зависимости. Известен также преобразователь, со держащий генератор случайных чисел, логические элементы,стохастический ин тегратор {2 J. преобразователь не позволяет получить цифровой код, математическое ожидание которого пропор цнонально некоторой функции от входной переменной.: Наиболее близким .техническим решением к изобретению является нелинейны вероятностный преобразователь, содержащий блок элементов И, выходы которых подключены ко входам элемента ИЛИ, первые входы - к выходам блока суммирования, а вторые входы - к выходам делителя частоты,.вход которого через первый переключатель соединен с выходами генератора двоичной случайной последовательности и Генератора тактовых импульсов, другой выход которого подключен ко входу стохастического умнржителя. Другой вход этого умножителя является входом преобразователя З. Недостатком этого преобразователя является низкая точность его работы. Целью изобретения является повьшение точности работы преобразователя. Для достижения поставленной цели предложенный преобразователь содержит блок задания участков аппроксимации, регистр номера участка, дешифратор номера участка, второй переключатель и блок задания коэффициентов, выходы которого подключены к первой группе входо.в блока суммирования, первая группа входов - к выходам стохастического умножителя, а вторая группа входов л::ерез дешифратор номера участка - к ipynne выходов регистра номера участка, входы которого и выход соединены

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

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

Преобразователь содержит стохастический умножитель 1, блок 2 коэффициентов, блок 3 суммирования, делитель 4 частоты, блок 5 элементов И, элемент. 6 ИЛИ, .блок 7 идентификации участков аппроксимации, регистр 8 ноера участка, дешифратор 9 номера участка, первый переключатель 10, генератор 11 тактовых импульсов, генератор 12 двоичной случайной последовательности, второй Переключатель 13.

Входы умножителя 1 соединены со входом преобразователя.и с выходом генератора 11 тактовых импульсов. Выходы умножителя 1 подключены.ко входам блока 2 коэффициентов, другие входы которого соединены с выходами дешифратора 9. Выходы блока 2 коэффициентов подключены ко входам блока. 3 суммирования, другие входы которого соединены с выходами переключателя 13. Выходы блока 3 суммирования соединены с входами блока 7 идентификации участков аппроксимации, с первым выходом 14 устройства и с первыми входами блока 5 элементов И. Вторые входы блока элементов 5 И подключены к разрядным выходам делителя 4 частоты.- Вход делителя 4 частоты соединен через переключатель 10 с выходами генераторов 11 и 12. Выходы блока элементов И 5 соединены со входами элемента 6 ИЛИ, выход которого подключен к первому входу переключателя 13, второй вход которого соединен с выходом блока 3 суммирования. Входы регистра 8 соединены с выходами блока 7 идентификации участков аппроксимации, а выходы регистра 8 - со входами блока 7 и де1Ифратора 9.

Умножитель 1 содержит регистр 1.6 сдвига, блока И элементов 17 и блок элементов Запрет 18, входы котоого соединены с выходами блока элеентов И 17, входы.которых соединены с выходами регистра 16 и выходами предыдущих элементов И соответственно.

Блок 2 коэффициентов содержит блок элементов И 19, выходы которых соединены со входами блока элементов ИЛИ 20

Преобразователь реализует заданную функцию преобразования F(х) , аргументом которой является вероятность x(t появления импульса во входной последовательности Вернулли г (t) .

fi зависимости от положения переключателя 10 преобразователь может работать в двух режимах: в цифро-вероятностном режиме на вход делителя 4 частоты подается импульсный поток с выхода генератора 12 ив цифро-частотном режиме (на вход делителя 4 поступает импульсная последовательность с выхода генератора 11).

. В каждом режиме в блоке 3 накапливается цифровой код 2 (t) , математическое ожидание которого .(t) пропорционально заданной функций F(x) от входной переменной, т.е. реализуется нелинейное преобразование типа вероятность-код .

Отличие режимов состоит в том, что в зависимости от положения переклю - чателя 10 на выход 15 устройства проходит случайная последовательность импульсов,либо детерминированная последовательность. При этом вероятност появления импульса на выходе 15 (в первом случае) и относительная частота повторения импульсов (во втором случае) пропорциональны заданной функций преобразования F (х.) , т.е. реализуется функциональное преобразование либо типа вероятностьт-вероятность либо типа вероятность-частота. Отличие двух режимов состоит также в том, что они имеют разные точностные характеристики, и во втором режиме может быть получена более высокая точность преобразования типа вероятность-код .

i .

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

Рассмотрим второй режим работы преобразователя (первый режим анализируется аналогично).

При работе во втором режиме переключатель 10 соединяет вход делителя 4 частоты с выходом генератора Ц. При этом реализуется метод кусочнополиноминального представления воспроизводимой функции Р (х, т.е. F( )Pi(x), . p. (к) aj aj, X ... -baj х полином степени тп , приближающий заданную функцию FCX) на участке R; 4 x$R: . . JU tl где Kj - границы участков приближения (фиг.4). Рассмотрим статику работы преобра зователя, т.е. предположим, что вход ная переменная не изменяется во времени ( x(t) X coTi&t ) . При построени устройства, реализующего метод кусоч но-полиноминальной аппроксимации заданной .функции F (.к) необходимо возвес входну ю переменную х в i -ю степен умножить х на коэффициент uj , оп ределить сумму ряда R.).2Ojjx и усреднять полученную сумму р-(х)пс длине реализации, так как входной по ток т Ct) случайный. Операцию возведения в л -ю степень входной переменно выполняет умножитель 1, умножение х на йд , вычисление Р и усреднение . PJ (х)- блок 2 коэффициентов и блок суммирования 3, определение и запоминание номера (J) участка аппрокси мации осуществляют блок 7 и регистр переключение коэффициентов . в зависимости от номера (j ) участка реализуется с помощью управляющих сигна лов с выходов дешифратора 9. Делител частоты, блок 5 элементов И, элемент 6 ИЛИ и генератор 11 обеспечивают, ра боту преобразователя в следящем (дин мическом) режиме. Переключатель 13 не обходим для реализации знакопеременных функций F (). Генератор 12 в рассматриваемом режиме не используется (он необходим для работы устройства в цифро-вероятностном режиме). На вход умножителя 1 поступает поток Бернулли 4(-L с вероятностью появления импульса равной x(t) X. . При этом на выходах умножителя 1 получают случайные потоки (t), вероятности появления импульсов в которых равны соответственно Xa,i- X-rri / причем эти потоки должны быть несовместны, т.е. в любой момент времени импульс может появиться не более чем на одном и э всех (т +1) выходов умножителя 1. Условие несовместимости, потоков (.t) вводится потому, что в противном случае необходимо одновременно суммировать несколько входных величин, что приводит.к значительному усложнению блока суммирования 3. Входной импульс л-го элемента запрет проходит на i-и выход умножь теля только в том случае, если отсу-о. ствует входной импульс ( .L +1)-го элемента Запрет (входной импульс I +1)-го элемента 1+1 является запрещающим импульсом для L-го элемента 18 i . Таким образом, в данный момент времени импульс может появиться только на самом старшем из всех выходов умножителя 1, на которых он мог бы появиться при отсутствии блока элементов Запрет 18. Это объясняется тем, что все входные импульсы младших элементов 18 запрещают один другой (в классическом стохастическом умножителе) при появлении на выходе S-го элемента И 17 импульса и отсутствии на выходе ( s+l)-ro элемента 17. импульса, импульсы обязательно появляются на всех без исключения выходах элементов И 17i, номер которых меньше S , и отсутствуют на выходах всех элементов И 17L номер которых больше S ). При этом вероятность x ( ) появления импульса на соответствующем выходе умножителя 1 равна V-V i V TTl-l Xf X . Полученные несовместимые потоки V (t с выходов умножителя 1 через блок 2 коэффициентов поступают на выходы бло ка 3. С помощью блока элементов И 19 осуществляется переключение участков аппроксимации, так как потоки f (t) проходят только через те элементы И 19Ji на разрешающие входы которых подается управляющий потенциал с выхода дешифратора 9 номера участка г-0тт , j 1-К (где К - число участков аппроксимации) Выход каждого элемента И 19ji соединен с входами элементов ИЛИ блока 20 соединенными с ( Е - . ) -ми входами блока 3, если в г-ом разряде двоичного разложения коэффициента bj имеется единица, где - число разрядов блока 3, отведенных для представления кода результата 2 (-t , т.е. с технической точки зрения i - число разрядов блока 3, охваченных отрицательной обратной связью. Будем считать, что все 1FU) и поэтому запятая в блоке 3 фиксирована между знаковым и первым значащим разрядами (если .х|Р(х)|.1 то необходимо перенести запятую на соответствующее число разрядов с тем, чтобы выделить целую часть числа). Таким образом, импульс с 1-го выхода умножителя 1, вероятность появления которого равна Х| , проходит через блок 2 коэффициентов только на те (-51)-Е входы блока 3, для которых в соответствующих им t -ых разрядах коэффициента bj- имеется единица ( , где п - число разрядов блока 3, отведенных для представления дробной части коэффициента Ь) . ТаКИМ образом, двоичный код коэффициента 6ji поступает (и, следовательно, прибавляется) в блоке 3 с вероятностью Х; . Отсюда имеем , где Mj Е - математическое ожидание числа I (t) в блоке 3 в установившемся режиме. При выборе коэффициента fejt равным учитывая, что - ж получим ,,(0 U} Следовательно, если с помощью блока 2 коэффициентов (т.е. набора простых логических схем И и ИЛИ) реализо вать коэффициенты согласно формуле (1), то получим, что в установившемся режиме матиматическое ожидание цифрового. кода b(t), накапливающегося в блоке 3, равно значению полинома PJ (х) , аппроксимирующего за данную функцию Т (х ) на j -ом участке В предлагаемом устройстве коэффициенты bj д етерминированные, а не слу чайные как в известных устройствах, поэтому значительно увеличена точност преобразования (при заданном быстродействии) и упрощена схема формирования самих коэффициентов разложения. Упрощение схемы формирования коэффици ентов fej{ в предлагаемом устройстве до стигается за счет того, что для задания детерминированных коэффициентов не требуется дорогостоящий прецизионный многоканальный генератор опорных случайных последовательностей, вероят ность появления импульсов в которых равна 0,5. Коэффициенты bj{ в предлагаемом устройстве реализуются простым соединением выходов элементов И 19j со входами тех элементов ИЛИ 20, которые занимают позиции, соответст-. вующие единицам в двоичном разложении коэффициентов bji . Для универсальности выходы элементов И 19ji могут быть соединены со входами элементов ИЛИ 20 не непосредственно, а через переклю - чатели, замыкая и размыкая которые можно получать единицу или нуль в соответствующих разрядах коэффициентов bj{ . Это позволяет легко переходить с одной реализуемой функциональной зависимости F(,x) на другую и, следовательно значительно облегчает условия эксплуатации предлагаемого устрой ства в тех режимах, для которых харак терным является частая перестройка законов функционирования FCt). Динамический (следящий) режим работы преобразователя обеспечивается применением следящего стохастического интегратора, состоящего из блока суммирования 3, делителя 4 частоты, блока 5 элементов И, элемента 6 ИЛИ, ереключателя 13 и генератора такто1ВЫХ импульсов 11. С помощью генератора 11, делителя 4 частоты, группы 5 элементов И и элемента б ИЛИ осуществляется преобразование содержимого блока суммирования 3 в детерминированный импульсный поток, частота следования импульсов в котором пропорциональна цифровому коду, находящемуся в блоке суммирования. Это преобразование осуществляется следующим образом. С разрядных выходов делителя 4 частоты на входы соответствующих элементов И поступают детерминированные последовательности, частоты следования импульсов в которых равны соответственно yrf--.lf ( f - частота следования тактовых импульсов с выхода генератора 11), причем эти потоки должны быть несовместимы. Несовместимые импульсные потоки с выходов делителя 4 частоты проходят на вход элемента ИЛИ 6 только в том случае, если в соответствующих им разрядах блока суммирования 3 будут единицы. Таким образом, каждому S-му разряду блока суммирования 3 соответствует дет.ермированный поток с частотой следования импульсов, равной |- . Поскольку вес S -го разряда блока суммирования 3 равен s ,{ запятая фиксирована перед знаковым разрядом), а потоки с выходов делителя несовместны, частота следования импульсов с выхода элемента б ИЛИ равна l. где i - цифровой код в блоке суммирования, Sg- значение s-ro разряда цифрового кода 2 . Отсюда, средняя частота . повторения импульсов равна cp-;fM. Таким образом получим, что средняя частота ср.следования импульсов с выхода элемента б ИЛИ прямо пропорциональна ма.тематическому ожиданию М Z. цифрового кода в блоке суммирования 3. Поток импульсов с выхода элемента ИЛИ б по цепи отрицательной обратной связи через переключатель 13 поступает на выходы блока суммирования 3, обеспечивая тем самым следящий режим работы стохастического интегра тора и всего устройства в целом. Заметим, что в предлагаемом устройстве на вход блока суммирования 3 по цепи отрицательной - обратной связи поступает детерминированный поток импульсов, а не случайная последовательность. Замена случайного потока на детерминированный позволила устранить погреш ность преобразования, обусловленную неидеальностью генератора равномернораспределенных случайных чисел (ГСЧ), а также упростить и следящий стохасти ческий интегратор за счет исключения из его схемы.дорогостоящего многоразрядного ГСЧ. Переключатель 13 обеспечивает следящий режим стохастического интегратора как для положительных, так и для отрицательеых чисел, находящихся в блоке суммирования 3. Это объясняется тем, что в зависимости от знака числа 2 в блоке суммирования 3 переключатель 13 переключает выходной поток элементов ИЛИ 6 либо на суммирующий вход (для отрицательных чисел 2), либ на вычитающий вход (для положительных чисел 2.) блока суммирования 3. Учитывая, что сложение (вычитание) кода 2. происходит с числом равным 2 , для упрощения блока суммирования 3 можно предложить операцию вычитания делать в дополнительном коде, т.е. вместо вычитания значения 2 следует прибавлять значение (1-2), что равносильно сложению числа с цифровым кодом/ у которого во всех раэрядах начиная со знакового и до разряда с номером , будут единицы. Следовательно, один выход электронного переключателя 10 следует подключит на -и разряд блока суммирования 3, а второй выход - на все старшие разряды этого блока до Е -го разряда включительно. Таким образом, можно реализовать знакопеременные функциональные зависимости F(xi без усложнения блока суммирования 3, который работает только в режиме сложения поступающих на его вход чисел. Если в разложении функции F(x) в ряд встречаются отрицательные коэффициенты bji, то они также должны быть представлены в дополнительном коде. Таким образом, предлагаемый преобразователь не накладывает никаких ограничений ни на значения коэффициентов fej ни на саму функцию 1(х). Однако функция (х)долж на иметь полиноминальное представлени Согласно теореме Вейерштрасса все непрерывные ограниченные, функции Р ( ) можно приблизить полиномом степени тп со сколь угодно малой погрешностью. Это позволяет значительно расширить функциональные возможности предлагаемого преобразователя по сравнению с известными устройствами. Рассмотрим особенности работы блоков 7, 8 и 9. Блок 7 идентификации участков аппроксимации необходим для формирования сигналов, по которым в регистр 8 номера участка заносится код участка, на котором в данный момент работает преобразователь. В простейшем случае блок 7 может состоять, например, из набора многоходовых элементов И, соединенных с разрядными выходами блока суммирования 3, при этом на выходах элементов И сигнал появляется только в те моменты времени, когда на их входы поступает цифровой код г ,. равный значению функции F(Rj) на границах участков. Число многовходовых элементов И должно быть равно числу границ участков аппроксимации, которые необходимо идентифицировать. Таким образом в момент времени, когда цифровой код Е станет равным значению f(Rj), по сигналу с одного из выходов блока 7 в регистр 8 номера участка заносится код нового участка. При этом преобразователь переходит в режим работы на новом участке аппроксимации. Дешифратор 9 номера участка переключает элементы И 19 блока, изменяя тем самым коэффициенты разложения полинома PJ (х). В некоторых случаях более целесообразно осуществлять переход с одного участка аппроксимации на другой не по значению кода . в блоке суммирования, а анализируя значение входной переменной х . в таких случаях схема блока 7 должна быть изменена, например, она может состоять из цифрового фильтра, который оценивает значение входной переменной X, и набора многовходовых элементов И. При любом варианте схемы блока 7 логика работы преобразователя аналогична. Рассмотрим динамику работы преобразователя. Работу преобразователя можно описать следующим разностным уравнением: Mj x(tn)).Fb.. х.-2-г- у(1) (3 где у (t) - относительная средняя частота следования импульсов с выхода элемента ИЛИ 6; Vit2(tl - математическое ожидание цифрового кода E(t) для j -го участка аппроксимации F (. Из решейия разностного уравнения (3) для случая, когда x(i)x const в установившемся режиме (т.е. при ) получим () Выражение (4) прлностью совпадает с формулой (2), полученной ранее. Оценим, частотные возможности (быстродействие) преобразователя, для чего решим разностное уравнение (3) для случая, когда вероятность x(t) изменяется во времени по синусоидальному закону. Из решения уравнения (3; получим следующую оценку для верхней граничной частоты ш изменения вероятности X. (t/ при Зсшанных динамических погрешностях преобразования как по амплитуде 6 , так и по фазе ДТ: ig ДУ, 2 Т. m где Т - период повторения тактовых импульсов. Из выражений (5) видно, что с ростом степени полинома (nO и числа разрядов (П , охваченных отрицательной обратной связью, ухудшаются частотные возможйости устройства при заданных динамических погрешностях. Статистическую погрешность преобразователя можно подсчитать по следую щей формуле: .cp , (6) (b-in)(l-xi).(,-i), где дисперсия числа при реализации полинома PjИз формул (6) видно, что с ростом степени полинома (тп) резко возрастает статистическая погрешность преобразования. Дисперсию DJ IJ можно уменьшит за счет увеличения числа разрядов f , но это ухудшает частотные возможности преобразователя. В предлагаемом устройстве целесооб разно степень полинома брать не более 2-3, в точности приближения заданной функции Р() полиномами достигать за счет увеличения числа участков аппрок симации. Следовательно, применение метода кусочно-полиноминальной аппрок симации позволяет значительно, уменьшать статическую погрешность преобразования и повысить быстродействие пре лагаемого устройства за счет уменьшения степени аппроксимирующего полинома., но ценой увеличения числасамих участков аппроксимации. Использование новых элементов - бл ка коэффициентов, делителя частоты, группы элементов И, элемента ИЛИ, бло ка идентификации участков аппроксимации, регистра номера участка, дешифратора номера участка, электронного переключателя, генератора тактовых импульсов, генератора двоичной случайной последовательности/ определенным образом взаимосвязанных меходу собой и другими элементами схемы поэволяет повысить точность работы, быстродействие и расширить функциональные возможности преобразователя 1Формула изобретения Нелинейный вероятностный преобра- . зователь, содержащий блок элементов И, выходы которых подключены ко входам элемента ИЛИ, первые входы - к выходам блока суммирований, а вторые входы - к выходам делителя частоты, вход которого через первый переключатель соединен с выходами генератора двоичной случайной последовательности и генератора тактовых импульсов, другой выход которого подключен ко йходу стохастического умножителя, другой вход которого является входом преобразователя, отличающ-ийся тем, что, с целью повышения точности работы преобразователя, он содержит блок идентификации участков аппроксимации, регистр номера участка, дешифратор номера участка, второй переключатель и блок коэффициентов, выходы которого подключены к первой группе входов блока суммирования, первая группа входов - к выходам стохастического умножителя, а вторая группа входов через дешифратор номера участка - к группе выходов регистра номера участка, входы которого и выход соединены соответственно с выходами и первым входом блока идентификации участков аппроксимации, второй вход которого подключен к первому выходу преобразователя и к выходу блока суммирования, вторая группа входов и выход знакового разряда которого соединены через второй переключатель с выходом элемента ИЛИ и вторым эыходом преобразователя, Источники информации, принятые во Знимание при экспертизе: 1,Galnes, B.,St,octtaaUc computer tFinVes jn noice , , EtectroTiic 1967, (14, 2,Кирьянов Б,Ф, Реализация стохастических функциональных преобразователей на основе цифрового интегратоС а стохастического типа, в об, Прием и обработка информации в структурносложных информационных системах . Казань, изд, КГУ, 1970, 3,Яковлев В.В,, Федоров Р,Ф, Стохастические вычислительные машины. Л., Машиностроение, 1974, стр,155.