SU1042016A1

SU1042016A1 - Probability device for n-power root extraction

Info

Publication number: SU1042016A1
Application number: SU823404551A
Authority: SU
Inventors: Валентин Васильевич Яковлев; Ольга Станиславовна Мальченкова
Original assignee: Ленинградский Ордена Ленина Институт Инженеров Железнодорожного Транспорта Им.Акад.В.Н.Образцова
Priority date: 1982-03-03
Filing date: 1982-03-03
Publication date: 1983-09-15

Abstract

ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КОРНЯ ft -И СТЕПЕНИ, содержащее первый счетчик, группа ВХОДОВ которого вл етс входа14И устройства, первый блок сравнени , перва группа входов и выход которого соединены соответственно с груп пой ВЫХОДОВ и счетным входом первого счётчика, первый генератор слу чайных чисел, группа вьвсодов которо го соединена с второй группой входо первого блока сравнени , т иггер Нулевой ВХОД которого вл етс ПУСКОВЫМ ВХОДОМ устройства, а единичный 8ХОД соединен с выходом старшего разр да первого счетчика, эле- мент И, первый ВХОД которого соединен с ВЫХОДОМ Триггера, а выход соединен с управл ющими входами пер-, вого генератора случайных чисел и первого блока сравнени , генератор тактовых импульсов, ВЫХОД которого соединен с вторым входом элемента И, второй блок сравнени , второй генератор случайных чисел, группа выходов которого соединена с первой группойВХОДОВ второго блока сравнени , делитель частоты, вход которого подключен к ВЫХОДУ элемента И, а выход соединен с управл к дими входами второго блока сравнени и второго генератора случайных чисел, о т л иЧающее с тем, что, с целью уменьшени аппаратурных затрат, оно содержит второй счетчик и элемент НЕ, ВХОД которого соединён с выходом второго сравнени , а 9ыхрд соединен со счетным входом второго счетчика, перва группа выходов второго счетчика соединена с второй группой ВХОДОВ второго блока сравнени , а втора группа выходов вл етс выходами устройства.PROBABILITY DEVICE FOR ROOT EXTRACT ft - AND DEGREE containing the first counter, the INPUTS group of which is the input14 of the device, the first comparison unit, the first group of inputs and the output of which are connected respectively to the OUTPUT group and the counting input of the first counter, the first random number generator, the group of terminals of which is connected to the second group of inputs of the first comparison unit, the player of the Zero INPUT of which is the START INPUT of the device, and the unit 8 of the INPUT is connected to the output of the higher bit of the first counter, And element, the first INPUT of which is connected to the Trigger OUTPUT, and the output is connected to the control inputs of the first random number generator and the first comparison unit, clock generator, the OUTPUT of which is connected to the second input of the AND element, the second comparison unit, the second a random number generator, a group of outputs of which is connected to the first group of INPUTS of the second comparison unit, a frequency divider whose input is connected to the OUTPUT of the AND element, and the output is connected to control the DMI inputs of the second comparison unit and the second generator and random numbers, so that, in order to reduce hardware costs, it contains the second counter and the element NOT, the INPUT of which is connected to the output of the second comparison, and 9yhrd is connected to the counting input of the second counter, the first group of outputs of the second counter is connected with the second INPUT group of the second comparison unit, and the second group of outputs are the outputs of the device.

Description

Изобретение относитс к вычислительной технике и предназначаетс дл выполнени операции извлечени корн п-й степени из числа А (В {, А 0-1, п - целое положительное число) в стохастических вычислительных машинах.The invention relates to computing and is intended to perform an operation of extracting an nth root from among A (B {, A 0-1, n is a positive integer) in stochastic computers.

Известно веро тностное устройство дл извлечени корн п-й степени/ содержащее двоичные счетчики, генераторы случайных чисел, блоки сравнени , генератор тактовых импульсов , логические элементы И, триггер I Основньм недостатком такого устройства вл етс значительные затраты оборудовани , св занные с необходимостью использовани реверсивного счетчика дл оценивани выходной переменной в двоичном коде, .A probabilistic device for extracting a root of the nth degree / containing binary counters, random number generators, comparison blocks, clock pulse generator, logic elements AND, trigger I. The main drawback of such a device is the considerable equipment costs associated with the need to use a reversible counter. for evaluating the output variable in binary code,.

Наиболее близким к изобретению вл етс веро тностное устройство дл извлечени корн п-й степени, содержащее первый счетчик, первый и второйблоки сравнени , первый и второй генератора случайных чисел, триггер , генератор тактовых импульсов, логический элемент И и делитель частоты , вход которого соединен с управл ющими входами первого блока сравнени и первого генератора случайных чисел, выходы которого подключены к вторым входам первого блока сравнени , первые входы которого соединены с выходами первого счетчика , разр дные входы которого подклюгчёны к числовым входам устройства, суммирующий вход соединен с выходом первого блока сравнени , а выход старшего разр да подключен к единичному входу триггера, нvлeвoй вход которого соединен с входом пуска, устройства , а выход - с первым входом логического элемента И, второй вход ко-. торого подключен к выходу генератора тактовых импульсов, а выход соединен с входом делител частоты, выход которого соединен с управл ющими входами второго блока сравнени и вто-г рого генератора случайных чисел, выходы которого подключены к вторым входам второго блока сравнени .Closest to the invention is a probabilistic device for extracting a root of nth degree, comprising a first counter, first and second comparison blocks, a first and second random number generator, a trigger, a clock generator, an AND gate and a frequency divider whose input is connected to the control inputs of the first comparison unit and the first random number generator, the outputs of which are connected to the second inputs of the first comparison unit, the first inputs of which are connected to the outputs of the first counter, bit inputs connected to the device’s numerical inputs, the summing input is connected to the output of the first comparison unit, and the high-order output is connected to the single trigger input, the input of which is connected to the start input of the device, and the output to the first input of the logic element I, the second input to -. The output is connected to the output of the clock pulse generator, and the output is connected to the input of a frequency divider, the output of which is connected to the control inputs of the second comparison unit and the second random number generator, the outputs of which are connected to the second inputs of the second comparison unit.

Недостатком данного устройства вл етс аппаратурна сложность, обусловленна использованием реверсивного счетчика дл получени выходной переменной в двоичном коде.The disadvantage of this device is hardware complexity, due to the use of a reversible counter for obtaining the output variable in binary code.

Цель изобретени - уменьшение аппаратурных затрат.The purpose of the invention is to reduce hardware costs.

Поставленна цель достигаетс , тем, что веро тностное устройство дл извлечени корн п-й степени (п 1, 2, 3, ..«.), содержащее первый счетчик, группа входов которого вл етс входами устройства, первый блок сравнени , перва группа входов и выход которого соединен соответственно с группой выходов и счетным входом первого счетчика, первыйThe goal is achieved by the fact that a probabilistic device for extracting a root of nth degree (n 1, 2, 3, .. ".) Containing the first counter, the input group of which is the device inputs, the first comparison unit, the first group of inputs and the output of which is connected respectively to the group of outputs and the counting input of the first counter, the first

генератор случайных чисел, группа выходов которого соединена с второй группой входов первого блока сравнени , триггер, нулевой вход которо го вл етс пусковым входом устройства , а единичный вход соединен с выходом старшего разр да первого счетчика, элемент И, первый вход которого соединен с выходом триггера , а выход соединен с управл кадими входами первого генератора случайных чисел и первого блока сравнени генератор тактовых импульсов, выход которого соединен С вторым входом элемента И, второй блок сравнени , второй генератор случайных чисел, ;Группа выхрдов которого соединена с первой ; группой входов второго блока сравнени , делитель частотТа, вход которого подключен к выходу элемента И, а выход соединен с управл ющими входами второго блока сравнени и второго генератора случайных чисел, дополнительно содержит , второй счётчик и элемент НЕ, вход.которого соединен с выходом второго блока сравнени , а выход соединен со счетным входом второго счетчика, перва группа выходов второго счетчика соединена с второй группой входов второго блока сравнени , а втора группа выходов вл етс выходами устройства.a random number generator, a group of outputs of which is connected to a second group of inputs of the first comparison unit, a trigger, the zero input of which is the starting input of the device, and a single input connected to the high-order output of the first counter, the And element, the first input of which is connected to the trigger output and the output is connected to the control cadmium inputs of the first random number generator and the first comparison unit, the clock pulse generator, the output of which is connected to the second input of the And element, the second comparison block, the second generator ayynyh numbers;; The group of vykhradov which is connected with the first; the group of inputs of the second comparison unit, the frequency divider, whose input is connected to the output of the element I, and the output connected to the control inputs of the second comparison unit and the second random number generator, further comprises a second counter and an element NOT whose input is connected to the output of the second block comparison, and the output is connected to the counting input of the second counter, the first group of outputs of the second counter is connected to the second group of inputs of the second comparison unit, and the second group of outputs is the device outputs.

На чертеже представлена блоксхема предлагаемого устройства. The drawing shows the block diagram of the proposed device.

Схема содержит первый счетчик 1, первый блок 2 сравнени , первый генератор 3 случайных чисел, триггер 4 генератор 5тактовых импульсов/ элемент б И, делитель 7 частоты, второй счетчик 8, второй блок 9 сравнени , второй генератор 10 случайных чисбл элемент 11 НЕ.The scheme contains the first counter 1, the first comparison block 2, the first random number generator 3, the trigger 4 the 5-pulse generator / element b, the frequency divider 7, the second counter 8, the second comparison block 9, the second random generator 10 element 11.

Группа выходов первого счетчика 1 соединена с первой группой входов первого блока 2 сравнени , а выход старшего разр да соединен с единичным входом триггера 4, выход которого соединен с первым входом элемента бИ. Нулевой вход триггера 4 вл етс пусковым входом устройства. Группа выходов первого генератора 3 случайных чисел соединена со второй группой входов первого блока 2 сравнени , выход которого соединен со счетным входом первбго счетчика 1. Выход генератора 5 тактовых импульсов соединен с вторым входом элемента б И, выход которого соединен с управл ющими входами первого блока 2 сравнени , первого генератора 3 случайных чисел и входом делител 7 частоты. Выход делител 7 частоты соединен с управл ющими входами второго блока 9 сравнени и второго генератора 10 случайных чисел. Группа выходов второго генератора 10 случайных чисел соединена с первой группой входрв второго блоха 9 срав нени , втора группа входов и выход которого соединены соответствен но с первой группой выходов второго счетчика 8. входом элемента И НЕ, выход которою соединен со счетным входом второго счетчика 8, Работа устройства начинаетс с занесени кода А по входам устройства в первый счетчик 1 и подачи им пульса на пусковой вход устройства, в результате чего на вход элемента б и соединенный с нулевым выходом триггера 4 подаетс разрешающий . сигнал. Таким образом, импульсы син хронизации с частотой F поступают на управл ющие входы первого генера тора 3 случайных чисел и первого блока 2 сравнени , а с частотой W - (после делени .частоты делителем частоты) - на управл ющие входы вторых блока 9 сравнени и генератора 10 случайных чисел. Единичный сигнал на-выходе первого блока 2 сравнени по вл етс , если содержимое первого счетчика 1 не меньше значени кода на выходе первого генератора 3 случайных чисел в каждом такте управлени (с часто той г), В процессе работы содержимое первого счетчика 1 нарастаетг ив некоторой момент времени счетчик переполн етс . Импульсом перепол нени по единичному входу выключаетс триггер 4, формиру на своем выход е временной импульс, длительнос1;ь которого с равна . где. 1 - разр дность счетчика (оба счетчика, блоки сравнеишг и генераторы случайных чи . сел имеют одинаковую разр дность ). Покажем, что за это врем . на выходе второго счетчика 8 формируетс результат выполнени операции . Математическое ожидание содержимого второго счетчика 8 может быть определено как Mt м.,+ 1 -yt , где Мц. - математическое .ожидание содержимого счетчика в п-м тактеJ . бинарный символ на выходе второго блока 9 сравнени . Учитыва , что математическое ожидание М | ц | ., где 1 - разр дность счетчика, а также то, что управление вторым блоком 9 сравнени и вторым генератором 10 случайных чисел осуществл етс с частотой F/n дл момента времени ь получим I - - Подставив в это выражение соотношение дл и из (1), окончательно получим . . nr- |Мл-«-е НЖ, Выражение (2) показывает, что. в предлож(еннсж устройстве, как и в устройстве-прототипе, выполн етс операци извлечени корн степени . Предлагаемое устройствопроще, так как второй счетчик не вл етс реверсивным. В последнем дл обеспечени логики вычитани необходимо использовать логическую схему 2И-2И2И-ЗИЛИ . В базисе интегргшьных схем серии К155 такой элемент реализуетс минимальио на одном логическом модуле . . - .. Таким образом, технико-экономический эффект предлагаемого устройства по сравнению с прототипом за- . ключаетс в сокращении аппаратурных Затрат (вдвое в базисе серий-к155).The output group of the first counter 1 is connected to the first group of inputs of the first comparison unit 2, and the high-order output is connected to a single input of the trigger 4, the output of which is connected to the first input of the BI element. The zero input of the trigger 4 is the starting input of the device. The group of outputs of the first random number generator 3 is connected to the second group of inputs of the first comparison unit 2, the output of which is connected to the counting input of the first counter 1. The generator output 5 clock pulses is connected to the second input of the element b And the output of which is connected to the control inputs of the first block 2 comparison, the first generator of 3 random numbers and the input of the frequency divider 7. The output of the frequency divider 7 is connected to the control inputs of the second comparison unit 9 and the second random number generator 10. The group of outputs of the second generator 10 random numbers is connected to the first group of entrances of the second flea 9 of comparison, the second group of inputs and the output of which are connected respectively to the first group of outputs of the second counter 8. the input of the element is NOT, the output of which is connected to the counting input of the second counter 8, The operation of the device begins with entering code A through the inputs of the device into the first counter 1 and applying pulse to the starting input of the device, as a result of which the permitting is applied to the input of element b and connected to the zero output of trigger 4. signal. Thus, synchronization pulses with frequency F are fed to the control inputs of the first generator 3 of random numbers and the first comparison unit 2, and with the frequency W - (after dividing the frequency by the frequency divider) - into the control inputs of the second comparison unit 9 and the generator 10 random numbers. A single signal at the output of the first comparison unit 2 appears if the contents of the first counter 1 are not less than the code value at the output of the first generator 3 random numbers in each control cycle (often with that r). During operation, the contents of the first counter 1 increase to some time counter overflows. The overflow pulse on a single input turns off trigger 4, forming at its output a time pulse whose duration is equal to c. Where. 1 — counter width (both counters, blocks compared to random number generators, villages have the same width). We show that during this time. at the output of the second counter 8, the result of the operation is formed. The mathematical expectation of the contents of the second counter 8 can be defined as Mt m., + 1 -yt, where Mc. - the mathematical expectation of the contents of the counter in the nth tact. a binary symbol at the output of the second comparison unit 9. Considering that the mathematical expectation of M | c | , where 1 is the counter size and the fact that the control of the second comparison unit 9 and the second random number generator 10 is performed at a frequency F / n for a moment of time, we get I - - Substituting the ratio for and from (1 ), finally get. . nr- | Ml - “- e NZH, Expression (2) shows that. in the proposal (the encode device, as in the prototype device, a root degree extraction operation is performed. The proposed device is simpler, since the second counter is not reversible. In the latter, the 2I-2I2I-ZILI logic must be used to provide the subtraction logic. In the basis integrated circuits of the K155 series, such an element is realized by a minimum of one logic module ... - Thus, the technical and economic effect of the proposed device in comparison with the prototype is in the reduction of hardware Costs ( howling in the base-K155 series).

Claims

PROBABILITY DEVICE FOR EXTRACTING THE ROOT OF THE fi -TH DEGREE, containing the first counter, the group of inputs of which are the inputs of the device, the first comparison unit, the first group of inputs and the output of which

X pyilUCl 0L (/ D1 / s P *> YAKAC-j .:

For example, the first random number generator, the output group of which is connected to the second group of inputs of the first comparison unit, has a trigger, the zero input of which is the starting input of the device, and the single input is connected to the output older -; the first discharge of the first counter, the element And, the first input of which is connected to the trigger output, and the output is connected to the control inputs of the first, random number generator and the first comparison unit, a clock generator whose output is connected to the second input of the element And, the second a comparison unit, a second random number generator, the group of outputs of which is connected to the first; group of inputs of the second comparison unit, the frequency divider, the input of which is connected to the output of the And element, and the output is connected to the control inputs of the second comparison unit and the second random number generator, characterized in that, for the purpose of § reducing hardware costs, it contains the second counter and the element / Л NOT, the input of which is connected to the output j of the second block of comparison, and you. the stroke is connected to the counting input of the second counter, the first group of outputs g of the second counter is connected to the second ** group of inputs of the second block compared to | ny, and the second group of outputs is the p * outputs of the device. .

TO

E => t k1 b

g — I I Yu

-h] * no