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

1 Т,; библие НИЕ НИЯ 43706 Союз СоветскиСоциалистицесва ОБР пубп ВИДЕТЕДЬСХВ К(32) ПриоритетОпубликовано 25,07.74. Бюллетень1. Кл, 6 061 1/02 осударстеенный комитетСовета Министров СССГпо делам изобретенийн открытий(53 1.3(088 бликования описания 15.01.75 2) Авторы изобрете Ф, Кирьянов, А, А. Скребнев и Б. П. Бондаренко ванский орде 71) Заявител сти тут ого Красного Знамени авиацион) ГЕНЕРАТОР ЦЕПЕЙ МАРКОВА Изобретение относится к области вычислительной техники и может применяться при моделировании случайных процессов.Известные генераторы цепей Маркова, содержащие генератор тактовых импульсов, генератор случайных символов, регистр сдвига,имеют сложное схемное решение,Цель изобретения - упростить схему генератора,Это достигается тем, что генератор содержит элемент И, первый вход которого подключен к выходу генератора случайных символов, разрядные элементы И, первые входы которых соединены с разрядными выходами регистра сдвига, вероятностный (1, т)- 15полюсник, выходы которого соединены со вторыми входами элементов И соответственно,и элемент ИЛИ, входы которого соединеныс выходами элементов И соответственно, авыход - со входом регистра сдвига. 20На чертеже представлена схема предлагаемого генератора цепей Маркова.Генератор содержит регистр сдвига 1, генератор случайных символов 2, генератор тактовых импульсов 3, вероятностный (1, т)-полюсник 4, элемент ИЛИ 5 и элементыИ 6.Выходы регистра сдвига 1 соединены с первыми входами соответствующих элементовИ 6, вторые входы которых соединены с со- ЗО ответствующими выходами вероятностного (1, т)-полюсника 4. Выходь 1 этих элементов соединены со входами элемента ИЛИ 5, выполняющего в данном случае функцию сумматора. Выход элемента ИЛИ 5 соединен с входом регистра сдвига 1.Выход генератора случайных символов 2 соединен с элементом И 6, второй вход которого соединен с соответствующим выходом вероятностного (1, т) -полюсника 4. Выход этого элемента И 6 соединен с одним из входов элемента ИЛИ 5.Генератор тактовых импульсов 3 соединен со входом синхронизации генератора случайных символов 2 и со входом сдвига регистра сдвига 1, В данной схеме предусмотрена установка начальных значений регистра 1 перед работоп генератора марковских последовательностей (для задания начальной переходной вероятности).С каждым импульсом генератора тактовых импульсов 3 осуществляется сдвиг числа в регистре сдвига 1 на один разряд влево и запись в освободившийся разряд выходного символа элемента 5, При совпадении сигнала с выхода регистра сдвига 1 и соответствующего выхода вероятностного (1, т) -полюсника на выходе элемента И 6 появляется сигнал, который поступает на вход элемента ИЛИ 5. Кроме того, на вход этого элемента может прийтисигнал, если импульс от генератора случайных символов 2 совпадает с импульсом канала а (, т)-полюсника.Поскольку тактовые импульсы вызывают и выдачу символов а с генератора случайных символов 2 и символов по каналам а, 6;,= 1 - :т с (1, т)-полюсника, то для выходных символов я сумматора 5 можно записать уравнение:а (1) = аа+бр ( - ), (1)где а, 6; (=1, т) несовместные, Здесь время1 выражается в тактах.Отсюда вытекает следующее равенство(О - а х+Рь "у( ) ( ) где Р - вероятность появления 1 в канале у в 1-тый такт;Р,. - вероятность появления 1 в канале х в 1-тый такт;Ра, Рь, - вероятность появления 1 в соответствующих каналах (1, т)- пол юсника,Из уравнения (1) видно, что в любой момент времени получается вполне определенная вероятность, зависящая от содержимого т предыдущих тактов и не зависящая от постоянной во все другие предшествующие такты.В первоначальный момент времени переходная вероятность может быть задана занесением в сдвиговый регистр начальных условий,Различные цепи Маркова можно получитьизменением Р, Рь а также изменением самого потока Х 1 см. уравнение (1).В качестве примера рассмотрим схему генератора цепей Маркова, когда сдвиговый регистр имеет 4 разряда,Если содержимое предыдущих трех тактовбыло, например, 011, тоР Я =РРЯ+Р +Р, =- Р(1011), (3)где Р (1/011) - вероятность появления 1 навыходе при условии, что предыдущие три такта были 011.15Предмет изобретенияГенератор цепей Маркова, содержащий генератор тактовых импульсов, первый выход которого соединен с генератором случайных символов, а второй - со сдвигающим входом регистра сдвига, отличающийся тем, что, с целью упрощения генератора, он содержит элемент И, первый вход которого подклю чен к выходу генератора случайных символов,разрядные элементы И, первые входы которых соединены с разрядными выходами регистра сдвига, вероятностный (1, т)-полюсник, выходы которого соединены со вторыми вхо дами элементов И соответственно, и элемент ИЛИ, входы которого соединены с выходами элементов И соответственно, а выход - со входом регистра сдвига.енина едакто Заказ 3474(1 Тираж 624 итета Совета Министров ений и открытий шская наб., д. 4/5 ПодпнсоСР Типография, пр. Сапунова,Изд.89дарственного коо делам изобреосква, Ж, Ра ректор В. Брыкс