Стохастический компаратор Советский патент 1982 года по МПК G06F7/70 

.(54) СТОХАСТИЧЕСКИЙ КОМПАРАТОР

Изобретение относится к вычислительной технике и предназначается для исследования cлiгчaйныx процессов.

Известны устройства стохастических колтараторов, содержащие двоичные счетчики и регистры, триггеры, элементы И, элементы ИЛИ Г1 и Г2.

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

Наиболее близким техническим решением к предлагаемому является стоха тический компаратор/ содержащий пеЬвый элемент ИЛИ, первый и второй элементы И, триггер, два счетчика, выход первого счетчика подключен к . первым входам триггерс1 и второго счетчика, выход второго счетчика соединен с вторым входом триггера и первым входом первого счетчика, выходы триггера подключены соответственно к первым входам первого и второго элементов И, вторые входы которых подключены к входам компаратора, а выходы - к входам элемента ИЛИ. . .

На суммирующие вторые) входы счетчиков подаются случайные последовательности с параметрами (математическими ожиданиями) соответственно р и р.. В зависимости от наличия переполнения первого или второго счетчиков устанавливается, у ка10кой из последовательностей наибольший уровень вероятности появления символа 1. При этом среднее время, необходимое для сравнения параметров р и РЛ в устройстве определяет15ся по формуле

N

(1)

Р- max

N - емкость каждого из счетчигде

20 ков;

PmaxPi Pi ° зависимости от соотнесения их значений С31 .

Недостаток устройства состоит в низком быстродействии, так как при

25 мгишх время сравнения Т быстро возрастает.

Цель изобретения - повышение быстродействия .

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

30 тем, что стохастический компаратор. содержащий первый и второй элементы И, первые входы которых являются входами компаратора, первый элемент ИЛИ, первый и второй входы которого соединены с выходами соответственно первого и второго элементов И, а выход является выходом компаратора, триггер, первый и второй выходы которого соединены со вторыми входами соответственно первого и второго эле ментов И, первый и второй счетчики, выходы которых соединены соответственно с первым и вторым входами триг гера и с первыми входами соответственно второго и первого счетчиков, дополнительно содержит второй и третий элементы ИЛИ, первый и второй .элементы задержки, входы которых |соединены с первыми входами соответственно первого и второго элементов И, а выходы соединены с первыми входами соответственно второго и третьего элементов ИЛИ, вторые входы второго и третьего элементов ИЛИ.соединены с первыми входами соответственно первого и второго элементов И, а выходы второго и третьего эле-, ментов ИЛИ соединены со вторыми входами соответственно первого и второго .счетчиков. На чертеже представлена блок-схема компаратора. Компаратор имеет входы, 1 и 2 для сравниваемых случайных последователь ностей и содержит первый 3 и второй 4 элементы задержки, второй 5 и третий 6 элементы ИЛИ, первый7 и второй 8 счётчики, триггер 9,первый 10и второй 11 элементы И и первый элемент ИЛИ 12. Первые входы первого 10 и второго 11элементов И объединены со вторыми входами соответственно второго 5 и третьего 6 эл ементов ИЛИ и входами соответственно первого 3 и второго 4 элементов задержки, выходы которых . соединены с первыми входами соответственно второго 5 и третьего б элеме тов ИЛИ. Выходы второго 5 и третьего б элементов ИЛИ соединены со вторыми входами соответственно первого 7 и второго 8 счетчиков, выходы которых соединены соответственно с первым и вторым входа ш триггера 9 и первыми входами соответственно второго 8 и первого 7 счетчиков. Первый и второй выходы триггера 9 соединены со вторы ми входами соответственно первого 10 vL второго 11 элементов И, выходы кот рых соединены соответственно с первы и вторым входами первого элемента ИЛИ 12. Стохастический компаратор работае следующим образом. Сравниваемые последовательности с параметрами р и р, подаются соответ ственно,на входы 1 и 2 стохастического компаратора и далее непосредтвенно и через элементы И 3 и 4 на ходы второго 5 и третьего 6 элеменов ИЛИ. При этом вероятность появения символа 1 в выходных случайных оследовательностях на вьоходах элеентов ИЛИ 5 и 6 равна соответственно Р,(2 - Р,)1 Р,(2 Эти последовательности поступают на вторые (суммирующие) входы соответственно счетчиков 7 и 8. В счетчиках происходит накопление импульсов указанных случайных .последовательностей . В некоторый момент времениодин из счетчиков переполняется первым. Так как среднее число тактов переполнения счетчика равно -5L , IР то первым переполняется счетчик, на входе которого присутствует последовательность с P naxfPrnctit наибольшая иэ вероятностей р или р ). Импульсом переполнения с выхода этого счетчика гасится по первому выходу другой счетчик и устанавливается в соответствующее положение триггер 9, который открываетодин из элементов И (10 или 11). В результате на выход устройства через первый логический элемент ИЛИ 12 передается одна из входных последовательностей р или р. При этом время сравнения двух величин р и р в п{эедлагаемом устройстве составляет .Т -или с учето, том (2) Т у В то же вреniax(ma5i) мя вустройстве прототипа время сравнения в соответствии с (1) составляет N/fS axСледовательнр в предлагаемом устройстве стохастического компаратора достигается ускорение работы в Т/Т раз, т.е. в Т/тгг-р д раз . В пределе (при )т/Т 2. Таким образом, технико-экономический эффект предлагаемого устройства заключается в повышении его быстродействия. Формула изобретения Стохастический компаратор, содер, жащий первый и второй элементы И, первые входы которых являются входами компаратора, первый элемент ИЛИ, первый и второй входы которого соединены с выходами соответственно первого и второго элементов И, а выход является выходом компаратора. триггер, первый и второй выходы которого соединены с вторыми входами соответственно первого и второго элементов И, первый и второй счетчики.

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

соответственно первого и второго элементов И, а выходы второго и третьего элементов ИЛИ соединены с втбрыми входами соответственно первого и второго счетчиков.

Источники информации, принятые во внимание при экспертизе

3.Авторское свидетельство СССР 533931, кл. G 06 F 15/36, 1975 (прототип).