Генератор случайного марковского процесса

В состоянии а блок 1 управлениявыдает сигналы: "Запуск" на датчик 6равномерно распределенных случайныхчисел и "Сложить" на накапливающийсумматор-вычитатель 11.В состоянии а 2 блок 1 управлениявыдает сигнал "Запись" в счетчик 3и в накапливающий сумматор 5.В состоянии ад блок 1 управлениявь 1 дает сигналы "Сдвиг" на регистр 13сдвига и "Сложить" на накапливающийсумматор-вычитатель 11.В состоянии а 4 блок 1 управлениявыдает сигналы "Сдвиг" на регистр 1315сдвига и "Вычесть" на накапливающийсумматор-вычитатель 11.В состоянии а блок 1 управлениявыдает сигнал "Съ,ржить" на накапливающий сумматор-вычитатель 11,20В состоянии аб блок 1 управлениявыдает сигнал "Запись" в счетчик 3и в накапливающий сумматор 5.В состоянии а 7 блок 1 управлениявыдает сигналы Вычесть" на счетчик 3 и "Сложить" на накапливающийсумматор 5.Накапливающий сумматор 5 предназначен для формирования и хранения модифицированных элементов стохастической матрицы переходов. При подачеуправляющего сигнала Запись" на накапливающий сумматор 5 в нем записы"вается информация, поступающая с выхода блока 1 О памяти элементов строк.При подаче на накапливающий сумматор 5 управляющего сигнала "Сло:кить"к текущему его значению добавляетсязначение регистра 7.Блоки 8-10 памяти предназначены40для хранения в сжатой. форме стохастической матрицы переходов. Считываниеинформации иэ блоков 8-10 памяти происходит при поступлении соответствующих адресов на их адресные входы.45Накапливающий сумматор-вычитатель 11предназначен для формирования и хранения адреса, по которому осуществляется обращение к блокам 9 и 10 памяти.Регистр 13 сдвига предназначендля хранения и сдвига в сторону .младщего разряда информации, поступающейна его информационные входы, Запись исдзиг информации в регистр 13 осуще 11 11ствляется по сигналам Запись и"Сдвиг" соответственно, поступающим.на его управляющие входы,Генератор работает следующим образом. Пусть задан марковский процесс, описываемый конечным множеством состояний Я = 8; 1 = О, и - 1 и стохастической матрицей переходов( Р,1 1, где Р," - вероятность перехода за один такт из состояния Я, в состояние с 1, 1,1 = О, и - 1, Р, = 0112-, где (К,1 - целое, ш - параметр, определяющий точность представления элементов матрицы Р.Стохастическая матрица Р хранится в сжатом виде в виде векторовч = и,1;0 = 1 1 ЕИК = 1 г 11;К = 11 г;Т =Е 11Векторы 7, Я, К, К и Т получают таким образом, что устанавливают я = О, г = О, г = О, й О. Сжимают строку Р матрицы Р. Для этого в строке Р выделяют подстроки Р(2 гоР. Р из последовательно расположенных друг за другом фоновых элементов, Пусть в строке Ро Ко подстрок и 10 базовых элементов. Устанавливают Ч = К+.Просматривая строку Р слева направо, в координаты г 1,г 2,ее,г, гп 1, векторов К, К 1и Т последовательно выписывают:если встречается подстрока Ро а = 1, К, в К выписывают Ь + 1, вК . выписывают 1, а в Т выписывают 1Р ,где Ь - индекс столбца0последнего элемента подстроки Ро;если встречается базовый элемент1 Р, в К выписывают я + 1, в К выпи 3 сывают О, а в Т выписывают ", Р,Сс О где я - индекс столбца, где находитсяэлемент Р 1, т.е. Б = 3Пусть при сжатии строки Р в К, К и Т были выписаны позначений.устанавливают Ч = 0,+ 1 гроФг 11 Ор 18 т( 0Аналогично строке Р сжимают строку Р, . Пусть в строке Р, К 1 подстрок и , базовых элементов. Устанавлива ч, = к,.,.Просматривая строку Р слева направо в векторах К,К и Т выписывают соответствующие значения. Пусть при этом в векторах К,К и Т записаны по 1 значений.5 161926Устанавливают о =+ , + 2 :йЧ+ , + 1, гр 8, = 0г (1 офР 1 ., о 922Аналогичным образом сжимают строки Р Р, Р и, определяязначения координат г,г (ъо+(3Фг Ро Р,Ф , "1. го 1,в+- ) - Ч . + 3 . + ,а также 25Чг Ка+ )23 Эщ Кгде КККл30- число подстрок и число базовых элементов строк 2,3п - 1 соответственно.Векторы Ч и Я загружают в блок 8памяти, При этом координаты Ч1 = 0,1,2п - 1 записываются в35поле старших: разрядов (им соответствует выход 8.1), а координаты ц -в поле младших: разрядов (им соответствует выход 8.2) блока 8 памяти. 40Векторы К и К загружают в блок 9памяти. При этом координаты г записываются в поле старших разрядов (имсоответствует выход 9,1), а координаты г - в поле нулевого разряда145(им соответствует выход 9.2) блока 9памяти.Вектор Т загружается в блок 10памяти элементов строк, причем в память записываются только числители0( , уменьшенные на единицу, дробей-Фвида г= М 1, 2Перед началом работы векторы Ч,К К и Т вычисляются и загружаются1в соответствующие блоки 8-10 памяти(на фиг.1 устройство загрузки не показано). Фоновый элемент с знакомзаписывается в дополнительном коде в регистр 7. 36Начальное состояние Я цепи задается следующим образом.В счетчик 3 загружают код Г состояния Б. При этом на выходе 8.1 блока 8 памяти появляется координатаЧ ( число подстрок и базовых элементов строки Р) а на выходе 8.2 появляется координата 1 (указательначала строки Р в блоках 9 и 10 памяти.На этом процесс загрузки исходныхданных завершен.Работа генератора сводится к реализации алгоритма управления, представленного на фиг.2,После загрузки начального состояния блок 1 управления находится всостоянии аа и появляется сигнал, который поступает на управляющие входы"Запись" регистра 13 сдвига. и накапливающего сумматора-вычитателя 11При этом в регистр 13 сдвига записывается координата Ч вектора Ч, а внакапливающем сумматоре-вычитателе 1записывается координата овектора Я.После этого блок 1 управления переходит в состояние а. В состоянии аподается управляющий сигнал "Запуск"на датчик 6 равномерно распределенных случайных чисел, управляющий сигнал "Сложить" - на накапливающий сумматор-вычитатель 11. При этом датчик 6 вырабатывает ш-разрядное двоичное число 2 = х 2и величина хподается на вторую группу информационных входов схемы 4 сравнения. Одновременно в накапливающем сумматоревычитателе 11 формируется текущий адрес А, по которому выполняется обрашение к блоку 9 памяти и к блоку 1 Опамяти элементов строк. Навыходахблока 9 памяти появляются координатыг и г , а на выходе блока 10 памятипоявляется координата Г, Эти координаты находятся по адресу А = й ++11/2 + С , где С о - значение младшего разряда регистра 13 сдвига,Блок 1 управления переходит в состояние а , в котором подается управляющий сигнал Запись" в счетчик 3 ив накапливающий сумматор 5. При этомв счетчик 3 записывается считаннаяиз блока 9 памяти координата г вектора К, которая поступает на блок 8 памяти, а в накапливающий сумматор 5координата г вектора Т, которая поступает на первый вход схемы 4 сравнения.В зависимости от значения сигналовс выхода схемы 4 сравнения, с выхода9.2 блока 9 памяти и с выхода элемента ИЛИ 12, поступающих на соответствующие логические входы блока 1 управ"ления, он устанавливается в одно изследующих состояний: при признаке" ) " (число от датчика 6 равномернораспределенных случайных чисел большечисла от накапливающего сумматора 5)и сигнале "0" на выходе элементаИЛИ 12 устанавливается состояние а,при признаке " ) " и сигнале "1" навыходе элемента ИЛИ 12 устанавливается состояние а, при признаке " ( "( число от датчика 6 равномерно распределенных случайных чисел меньшечисла от накаплив ющего сумматора 5)и сигнале "О" с выхода элементаИЛИ 12 устанавливается состояниеа 1, при признаке =" (число от датчика 6 равномерно распределенных случайных чисел равно числу от накапливаюг:,его сумматора 5 либо при приз" 25наке "с " и сигналах "1" и "0" навыходе элемента ИЛИ 12 и на выходе 9.2 блока 9 памяти соответственноустанавливается состояние а 8, припризнаке " " и сигналах "1" на выходе элемента ИЛИ 12 на выходе 9,2блока 9 памяти устанавливается состояние ау,В состоянии а подается управляю"щий сигнал "Сдвчг" на регистр 13сдвига и управляющии сигнал Сложитьм 11 и 35на накапливающий сумматор-вычит"тель 11. В результате этого в накапливающем сумматоре-вычитателе 11 формируется новый адрес А. На выходах 40блока 9 памяти и выходе блока 10памяти элементов строк появляютсяновые координаты г,г и 1., которые+ С45Блок 1 управления вновь перехо"дит в состояние а. Вновь подаетсяуправляющий сигнал "Запись" в счетчик 3 и в накапливающий сумматор 5.При этом в счетчик 3 записываетсясчитанная из блока 9 памяти новая50координата г вектора К,которая по"ступает на блок 8 памяти, а в накапливающий сумматор 5 - новая координата г вектора Т, которая поступаетна первый вход схемы 4 сравнения.55Вновь срабатывает схема 4 сравненчя, в зависимости от признака сравнения и от значений сигналов на выходе элемента ИЛИ-НЕ и на выходе 9,2блока 9 памяти, вновь блок 1 управления устанавливается в одно из состояний а 1 ас 1 а ф а 7 т а 6Пусть блок 1 управления переходитв состояние а 1, В состоянии а подается управляющий сигнал "Сдвиг" на регистр 13 сдвига и управляющий сигнал"Вычесть" на накапливающий сумматорвычитатель 11. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес А . На выходахблока 9 памяти и выходе блока 10 памяти элементов строк появляются координаты г,г и С, находящиеся по адресу А = А-7/8 -- С . Блок 1 управления переходит всостояние а , в котором выдаетсясоответствующий управляющий сигнал,фиксирующий в счетчике 3 и в накапливающем сумматоре 5 вновь считанные координаты г и г, а блок 1 управлениявновь переходит в одно из состоянийафПусть блокуправления переходит в состояние а (код 0101). Управляющий сигнал подается на управляющий вход "Сложить" накапливающегосумматора-вычитателя 11. В результате в накапливающем сумматоре-вычитателе 11 формируется новый адрес Ау(А = А + С ), так как на выходе13,1 регистра 13 сдвига устанавливается нулевой код, который соответствует первому элементу сжатой строки Р.,Считываются блоки 9 и 10 памяти,а блок 1управления переходит в состояние а,В состоянии а выдается управляю"щий сигнал Запись , фиксирующий всчетчик 3 и в накапливающем сумматоре 5 считанные координаты г и г В эа"висимости от значения сигнала на выходе 9.2 блока 9 памяти, блок 1 управления переходит в состояние а(навыходе 92 - "0") либо в состояние а7(на выходе 9.2 - "1"),Таким образом, смена состоянийа- а обеспечивает поиск в сжатойстроке Р матрицы Р такой координаты 1, вектора Т, для которой х 1 с СПоиск координатыосуществляетсяне последовательным перебором координат Г вектора Т, а методом половинного деления.Если х= е 1, блок 1 управленияпосле состояния а перейдет в состояние аа. При этом будет выработан управляющий сигнал "Вычесть" на счет 1 б 19263чик 3, который сформирует в нем очередное состояние цепи Маркова. Блок 1управления переходит в исходное состояние а, с которого начинается оче"редной цикл работы генератора.Если хсси координатасоответствует базовому элементу либо подстроки, состоящей ровно из одного фонового элемента (на выходе 9,2 блока 9 памяти сигнал "О" ), после состояния алибо а блок 1 управления переходит в состояние аб.Если же х й , но координатасоответствует подстроке из фоновыхэлементов с длиной больше(на выходе 9.2 блока 9 памяти сигнал "1"),блок 1 управления после состояния аипи а переходит в состояние а.В состоянии а выдается сигнал"Сложить" на накапливающий сумматор 5и сигнал "Вычесть" на счетчик 3. Этимобеспечивается последовательное формирование в счетчике 3 номеров возможных будущих состояний цепи, которые 25были сжаты и которые в явном виде нехранятся. Одновременно из содержимого накапливающего сумматора 5 вычитается значение фонового элемента,формируя, тем самым, промежуточнве модифи 3 Оцированные значения вероятностей переходов именно в те состояния, номера которых вырабатываются в счетчике 3,Из состояния а блок 1 управления35может перейти в одно из состояний аа либо а.Если схема 4 сравнения вырабатывает признак сравнения " ", в счетчике 3 сформирован код следующего со Остояния цепи Маркова и блокуправления переходит в состояние аЕсли схема 4 сравнения вырабатывает признак сравнения "=", то в счетчике 3 хранится код будущего состояния цепи, увеличенный на единицу,поэтому блок 1 управления переходитв состояние аЕсли же схема 4 сравнения вырабатывает признак " с:, то возможны дваслучая.Если признак " ( " выработан для состояния Я т.е. подстрока из фоновых элементов находится в начале строки Р, то следующим состоянием цепиМаркова будет состояние Яд,на выходе55дешифратора 2 вырабатывается сигнал"1", а блок 1 управления переходитв состояние а . В противном случае блокуправления остается в состоянии а и с приходом очередного тактового сигнала вновь из счетчика 3 вычитается единица, из накапливающего сумматора 5 вычитается фоновый элемент, анализируется признак сравнения и т.д.Цикл выработки очередного состояния цепи Маркова завершается с переходом блока 1 управления в состояние а. При этом сигнал на стробирующем выхо- де генератора указывает, что получено очередное состояние цепи.Формула изобретенияГенератор случайного марковского процесса, содержащий блок управления, первый, второй и третий блоки памяти, накапливаюший сумматор, регистр памяти, счетчик, датчик равномеоно распределенных случайныхчисел и схему сравнения, причем первый выход блока управления соединен с входом опроса датчика равномерно распределенных случайных чисел, выход которого соединен с первым информационным входом схемы сравнения, выходы которой соединены с группой входов задания логических условий блока управления, второй выход которого соединен с входом разрешения суммирования накапливающего сумматора, выход которого соединен с вторым информационным входом схемы сравнения, выход регистра памяти соединен с входом первого слагаемого накапливающего сумматора, вход второго слагаемого которого соединен с выходом первого блока памяти, вход разрешения записи накапливающего сумматора соединен с третьим выходом блока управления , о т л и ч а ю - щ и й с я тем, что, с целью повышения быстродействия, в него введены дешифратор, регистр сдвига, накапливающий сумматор-вычитатель и элемент ИЛИ, причем третий выход блока управления соединен с входом разрешения параллельной записи счетчика, вычитающий вход которого соединен с четвертым выходом блока управления, первый вход задания логических условий которого соединен с выходом младшего раз." ряда второго блока памяти, выходы старших разрядов которого соединены с информационными входами счетчика, выход которого является информационным выходом генератора и соединен садресным входом третьего блока памяти и информационным входом дешифрато" ра, выход которого соединен с вторым входом задания логических условий.5 блока управления, пятый выход которого является стробирующим выходом генератора и, соединен, с входами разрешения записи регистра сдвига и накапливающего сумматора-вычитателя, выход которого соединен с адресными входами первого и второго блоков памя-, ти, выход. старших разрядов третьего блока памяти соединен с информационным входом регистра сдвига, выход ко торого соединен с первым информаци онным входом накапливающего сумматора-вычитателя, второй информационныйвход которого соединен с выходом младших разрядов третьего блока памяти,выход старших разрядов регистра сдви"га соединен с входом элемента ИЛИ,выход которого соединен с третьимвходом задания логических условий блока управления, шестой выход которогосоединен с входом разрешения сложениянакапливающего сумматора-вычитателя,вход разрешения вычитания которого соединен с седьмым выходом блока управ"ления, восьмой выход которого соеди"нен с входом сдвига регистра сдвига,1619263 Пусн йргонак адненгж ложищь на какал" цФюи 1 одсужатор-Ььчитатель Ааад гСоставител Техред И д Феликсон Корректор С,Шевку Редактор А.Мотил акаэ 48 Тираж ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при113035, Москва, Ж, Раушская наб д, 4/5 роизводствеино-иэдательский комбинат "Патент", г. Ужгород, уп. Гагарина, 101 г нарегисщо а апь"на накала цц срмнмарбычислийель 11 ьи 7 д леменпюоФ-и г.