Моделирование расширенных цепей Маркова минимальными полиномами над полем GF(q)

Abstract

Предложен метод представления и моделирования минимальными полиномами расширенных и определенного вида сложных цепей Маркова над конечным полем GF(q). Задача моделирования решается как задача построения по алгоритму Берлекэмпа-Мэсси минимального полинома над полем GF(q). Полином вырабатывает последовательность длины N. Соответствующая этой последовательности стохастическая матрица аппроксимирует заданную стохастическую матрицу расширенной цепи Маркова с заданной точностью, пропорциональной величине 1/N. Построенный полином однозначно определяет структуру q-ичного линейного регистра сдвига для моделирования расширенных цепей Маркова. A method is proposed for representing and simulating minimal polynomials of expanded and definite types of complicated Markov chains over a finite field GF(q). The simulation problem is solved as a construction problem using the Berlekamp-Massey algorithm for the minimal polynomial over the field GF(q). The polynomial produces a sequence of length N. The stochastic matrix corresponding to this sequence approximates the given stochastic matrix of the expanded Markov chain with a given accuracy proportional to the 1/N value. The constructed polynomial uniquely determines the structure of the q-ary linear shift register for modeling expanded Markov chains.