Стохастический компаратор

 

ОП ИСАНИ Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

«»970365 (б1) Дополнительное к авт. саид-ву(3 ) М Кл з (22) Заявлено 23. 04. 81 (21) 3277602/18-24 с присоединением заявки ¹

G F 7/70

Государственный комитет

СССР по:делам изобретений и открытий. (23) Приоритет

Опубликовано 301032. Бюллетень № 40 (53) УДК681. 3 (088 ° 8) Дата опубликования описания 30 .10. 82 (72) Авторы изобретения

В.В.Яковлев, О.С.Мальченкова и A.Â.ßêoâëåâ

Ленинградский ордена Ленина институт инженю железнодорожного. транспорта им.акад.В.H.Oáð (71) Заявитель (5 4) СТОХАСТИЧЕСКИЙ КОМПАРАТОР

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

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

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

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

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

max где N - -емкость каждого из счетчиков; р -р„ или р в зависимости от н ак соотношения их значений 633

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

+ малых р „время сравнения Т быстро возрастает.

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

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

ЗО тем, что стохастический компаратор, 970 365

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

3 содержащий первый и второй элементы ственно и через элементы И 3 и 4 на

И, перные входы которых являются входы второго 5 и третьего 6 элеменвходами компаратора, первый элемент тов ИЛИ. При этом вероятность появHJIH, первый и второй входы которого ления символа 1 в выходных случайных соединены с выходами соответственно последовательностях на выходах элепервого и второго элементов И, а вы- 5 ментов ИЛИ 5 и б равна соответственход является выходом компаратора, но триггер, первый и второй выходы которого соединены со вторыми входами р = р,(г — р„) соответственно первого и второго элер = р (г — р ) (г) ментов И, первый и второй счетчики, 2 выходы которых соединены соответст- Эти последовательности поступают ненно с первым и вторым входами триг- на вторые (суммирующие) входы соотгера и с первыми входами соответст- ветственно счетчиков 7 и 8. В счетчивенно второго и первого счетчиков, ках происходит накопление импульсов дополнительно содержит второй и тре- 15 укаэанных случайных .последовательтий элементы ИЛИ, первый и второй ностей. В некоторый момент времени элементы задержки, входы которых один из счетчиков переполняется соединены с первыми входами соответ- первым. Так как среднее число тактов стненно первого и второго элементов е е „íå нн И, а выходы соединены с первыми вхо- Р дами соответственно второго и треть- 0 то первым переполняется счетчик, на его элементов ИЛИ, вторые входы вто- входе которого присутствует последорого и третьего элементов ИЛИ .сое- вательность с р,1,д„(р д„- наибольшая динены с первыми входами соответст- из вероятностей р йли р ) ..

1 2. ненно первого и второго элементов Импульсом переполнения с выхода

И, а выходы второго и третьего эле-. 25 этого счетчика гасится по первому ментов ИЛИ соединены со вторыми вхо- выходу другой счетчик и устанавливадами соответственно первого и второ- . ется в соответствующее положение го,счетчиков. триггер 9, который открываетодин из

На чертеже представлена блок-схе- элементов И (10 или 11). В результама компаратора. 30 те на выход устройства через первый

Компаратор имеет входы 1 и 2 для логический элемент ИЛИ 12 передает сравниваемых случайных последователь- ся одна из входных последовательносностей и содержит первый 3 и второй тей р1 или р2 . .4 элементы задержки, второй 5 и тре-, Прй этом время сравнения двух ветий б элементы ИЛИ, первый-7 и ВТо- 35 личин р и р2 в предлагаемом устройРой 8 счетчики, тРиггеР 9 еРВ и С тве составляет 73- М или с ч

10 и второй 11 элементы И и первый Рощк элемент ИЛИ 12. том (Z) T =

11 элементов И объединены со вторыми 40 мя н устройстве прототипа время сраввходами соответственйо второго 5 и нения н соответствии с (1) составтретьего б элементов ИЛИ и входами ляет Т = И/Йщ . соответственно первого 3 и второго 4 Следовательно в предлагаемом устэлементов задержки, выходы которых ройстве стохастического компаратора соединены с первыми входами соответ- 4 достигается ускорение работы в 7/Т ственно второго 5 и третьего 6 элемен. раз, т.е. в Т/Т =2-Р„,С,„Раз. B пределе тов ИЛИ. Выходы второго 5 и третьего (при p» 0) T/ò = 2.

6 элементов ИЛИ соединены со вторыми Таким образом, технико-экономичесвходами соответственно первого 7 и кий эффект предлагаемого устройства второго 8 счетчикон, выходы которых заключается в повышении его быстросоединены соответственно с первым и действия. вторым входами триггера 9 и первыми входами соответственно второго 8 и первого 7 счетчиков. Первый и второй выходы триггера 9 соединены со вторы- Стохастический компаратор, содерми входами соответственно первого 10 55 жащий первый и второй элементы И, ,второго 11 элементов И, выходы кото- первые входы которых являются входарых соединены соответственно с первым ми компаратора, первый элемент ИЛИ, и вторым входами первого элемента первый и второй входы которого соеИЛИ 12. динены. с выходами соответстненно

Стохастический компаратор работает 60 первого и второго элементов И, а выследующим образом. ход является выходом компаратора, Сравниваемые последовательности с триггер, первый и нторой выходы копараметрами р и р .подаются соответ- торого соединены с вторыми входами

Ф ственно,нa входы 1 и 2 стохастичес-, соответственно первого и второго элекого компаратора и далее непосред- 65 ментов И, первый и второй счетчики, 970365

Составитель О. Майоров

Техред С.Мигунова Корректор Н. Бурям

Редактор С. Юско

Заказ 8389/60 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, М-35, Раушская наб., д. 4/5

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

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

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

1. Гейнс 8. Стохастическая вычислительная машина. "Электроника", 10 1967,. 9 14.

2. Авторское свидетельство СССР

У 732891,). кл. G 06 F 15/36, 1977.

3. Авторское свидетельство СССР

Ю 533931, кл. G 06 F 15/36, 1975

15 (прототип).