Генератор цепеей маркова

 

1 Т .; библи е.

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

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

Социалисти мескита

Республик (61) Зависимое от авт. свидетельства (22) Заявлено 24.04.73 (21) 1913128/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 25.07.74. Бюллетень № 27

Дата опубликования описания 15.01.75 (51) М. Кл. G 061 1J02

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

Совета Министров СССГ по делам изобретений н открытий (53) УДК 681.3(088.8) (72) Авторы изобретения

Б. Ф. Кирьянов, А. А. Скребнев и Б. П. Бондаренко (71) Заявитель Казанский ордена Трудового Красного Знамени авиационный институт (54) ГЕНЕРАТОР ЦЕПЕЙ МАРКОВА

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

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

Цель изобретения — упростить схему генератора.

Это достигается тем, что генератор содержит элемент «И», первый вход которого подключен к выходу генератора случайных символов, разрядные элементы «И», первые входы которых соединены с разрядными выходами регистра сдвига, вероятностный (1, m)полюсник, выходы которого соединены со вторыми входами элементов «И» соответственно, и элемент «ИЛИ», входы которого соединены с выходами элементов «И» соответственно, а выход — со входом регистра сдвига.

На чертеже представлена схема предлагае-. мого генератора цепей Маркова.

Генератор содержит регистр сдвига 1, генератор случайных символов 2, генератор тактовых импульсов 3, вероятностный (1, m) -полюсник 4, элемент «ИЛИ» 5 и элементы

«И» 6.

Выходы регистра сдвига 1 соединены с первыми входами соответствующих элементов

«И» 6, вторые входы которых соединены с соответствующими выходами вероятностного (1, т)-полюсника 4. Выходь1 этих элементов соединены со входами элемента «ИЛИ» 5, выполняющего в данном случае функцию сумматора. Выход элемента «ИЛИ» 5 соединен с входом регистра сдвига 1.

Выход генератора случайных символов 2 соединен с элементом «И» 6, второй вход которого соединен с соответствующим выходом

10 вероятностного (1, т) -полюсника 4. Выход этого элемента «И» 6 соединен с одним из входов элемента «ИЛИ» 5.

Генератор тактовых импульсов 3 соединен со входом синхронизации генератора случай15 ных символов 2 и со входом сдвига регистра сдвига 1. В данной схеме предусмотрена установка начальных значений регистра 1 перед работой генератора марковских последовательностей (для задания начальной переход20 ной вероятности) .

С каждым импульсом генератора тактовых импульсов 3 осуществляется сдвиг числа в регистре сдвига 1 на один разряд влево и запись в освободившийся разряд выходного символа

25 элемента 5. При совпадении сигнала с выхода регистра сдвига 1 и соответствующего выхода вероятностного (1, т) -полюсника на выходе элемента «И» 6 появляется сигнал, который поступает на вход элемента «ИЛИ» 5. Кроме

30 того, на вход этого элемента может прийти

43706! сигнал, е ли импульс or генератора случайных символов 2 совпадает с импульсом канала а (!, m)-полюсника.

Поскольку тактовые импульсы вызывают и выдачу символов а., с генератора случайных символов 2 и символов по каналам а, b;, = 1 —:т с (1, т)-полюсника, то для выходных символов n„сумматора 5 можно записать уравнение: а (/) = ао. Я + 3 бр (/ — t), (1)

1=2 где а, b; (i=1, m) несовместные. Здесь время

1 выражается в тактах.

Отсюда вытекает следующее равенство

Р Я = Р P (t) + QP, (1 — i), (2) =1 где P> (t) — вероятность появления «1» в канале у в t-тый такт;

Р.,-(t) — вероятность появления «1» в канале х в t-тый такт;

t a> Рь, — вероятность появления «1» в соответствующих каналах (1, m)полюсника.

Из уравнения (1) видно, что в любой момент времени получается вполне определенная вероятность, зависящая от содержимого

m предыдущих тактов и не зависящая от постоянной во все другие предшествующие такты.

В первоначальный момент времени переходная вероятность может быть задана занесением в сдвиговый регистр начальных условий.

Различные цепи Маркова можно получить изменением Р„Pp,, а также изменением самого потока Х (см. уравнение (1)).

В качестве примера рассмотрим схему генератора цепей Маркова, когда сдвиговый регистр имеет 4 разряда.

Если содержимое предыдущих трех тактов было, например, 011, то

Р Я = Р,Р„Я + Р,, + Р„, =- Р (1!011), (3) где Р (1/011) — вероятность появления «1» на выходе при условии, что предыдущие три такта были 011.

Предмет изобретения

Генератор цепей Маркова, содержащий генератор тактовых импульсов, первый выход которого соединен с генератором случайных символов, а второй — со сдвигающим входом регистра сдвига, отличающийся тем, что, с целью упрощения генератора, он содержит элемент «И», первый вход которого подклю25 чен к выходу генератора случайных символов, разрядные элементы «И», первые входы которых соединены с разрядными выходами регистра сдвига, вероятностный (1, т)-полюсник, выходы которого соединены со вторыми вхо30 дами элементов «И» соответственно, и элемент «ИЛИ», входы которого соединены с выходами элементов «И» соответственно, а выход — со входом регистра сдвига.

437061

Составитель А. Карасов

Техред А. Дроздова

Редактор О. Стенина

Корректор В. Брыксина

Заказ 3474/1 Изд. № 89 Тираж 624 Подписное

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

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

Типография, пр. Сапунова, 2