Modeling Markov chains in Galois fields

Sh. R. Nurutdinov

Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 136-147.

Résumé

The automaton implementation of a determinate function is a probabilistic automaton $A_1=(S,Y,P_s,\lambda(s))$, where $S$ is the Markov chain state set, $P_s$ is an $m_1\times m_1$ stochastic matrix, $Y$ is the output alphabet of cardinality $m_2\le m_1$. The automaton implementation of a probabilistic function is a probabilistic automaton $A_2=(S,Y,P_s,P_y)$, where $S$, $Y$, $P_s$ are of the same sense as in $A_1$, while $P_y$ is a stochastic $m_1\times m_2$ matrix. In this paper, we solve the problem of synthesis of generators of finite homogeneous Markov chains on the base of the analytical apparatus of polynomial functions over a Galois field. We suggest a method to calculate the coefficients of a polynomial in several variables which implements any mapping of the Galois field into itself. We study the case of implementing a finite automaton by a homogeneous computing structure defined over a Galois field; automaton mappings are implemented as polynomial functions over the Galois field. As the base polynomials, we use polynomial functions over the Galois field $$ f_1(x, s)=\sum_{i,j=0}^ra_{ij}x^js^i, \qquad f_2(s)=\sum_{i=0}^rb_is^i, $$ where $r=2^n-1$, $x,s,b_i,a_{ij}\in\mathit{GF}(2^n)$. We give expressions of an automaton $A_1$ in the framework of a polynomial model over the field $\mathit{GF}(2^n)$ of the form $M_1=(\hat\mu_1, f_1(x,s),f_2(s))$, where $\hat\mu_1$ is the discrete random variable which takes values $\mu\in\mathit{GF}(2^n)$ determined by some probability vector $\bar P=(p_1,\ldots,p_{k_1})$ such that $$ P_s=\sum_{i=1}^{k_1}p_iB_i, $$ where $B_i$ are stochastic Boolean matrices and $k_1\ge m_1^2-m_1+1$, and of an automaton\linebreak $M_2=(\hat\mu_1, f_1(x,s),f_2(s),\hat\mu',f_3(x',s))$, where $\hat\mu_1'$ is a discrete random variable which takes values $\mu' \in\mathit{GF}(2^n)$ determined by some probability vector $\hat P=(p_1,\ldots,p_{k_2})$ such that $$ P_y=\sum_{i=1}^{k_2}p_iB_i, $$ where $B_i$ are stochastic Boolean matrices and $k_2\ge m_1^2-m_1+1$. The problem of representation of a discrete random variable over the field $\mathit{GF}(2^n)$ has been solved earlier. This research was supported by the Russian Foundation for Basic Research, grant 99–01–00163.

Bibliographie

[1] Pospelov D. A., Veroyatnostnye avtomaty, Energiya, Moskva, 1970 | MR

[2] Bukharaev R. G., Zakharov V. M., Upravlyaemye generatory sluchainykh kodov, Izd-vo Kazanskogo un-ta, Kazan, 1978 | Zbl

[3] Lidl R., Niderraiter G., Konechnye polya, t. 1, 2, Mir, Moskva, 1988 | Zbl

[4] Nurutdinov Sh. R., “Realizatsiya kombinatsionnoi skhemy pri pomoschi mnogochlena ot neskolkikh peremennykh nad konechnym polem”, Tezisy dokladov VIII Vsesoyuznoi konferentsii po kibernetike, ch. 2. Gorkii, 1988, 61–62

[5] Nurutdinov Sh. R., Stolov E. L., “Realizatsiya avtomata asinkhronnoi setyu”, Kibernetika, 1988, no. 6, 108–109 | MR

[6] Zakharov V. M., Nurutdinov Sh. R., Shalagin S. V., “Sintez avtonomnykh veroyatnostnykh avtomatov na osnove polei Galua”, Issledovaniya po informatike, Otechestvo, Kazan, 2000, 107–116 | MR | Zbl

[7] Nurutdinov Sh. R., “Markov chains in Galois fields”, Intern. Conf. OFEA'2001, St. Peterburg, 47–49

[8] Zakharov V. M., Nurutdinov Sh. R., Shalagin S. V., “Polinomialnoe predstavlenie tsepei Markova nad polem Galua”, Vestnik Kazanskogo gos. tekhn. un-ta, 2001, no. 3, 27–31

[9] Zakharov V. M., Nurutdinov Sh. R., Shalagin S. V., “Postroenie modeli umnozhitelya v polyakh Galua”, Materialy VII Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya” ch. I, Izd-vo tsentra prikladnykh issledovanii pri mekhaniko-matematicheskom fakultete MGU, Moskva, 2001, 62–65

[10] Nurutdinov Sh. R., Shalagin S. V., “Minimizatsiya kolichestva elementov odnorodnoi vychislitelnoi struktury”, Issledovaniya po informatike, Otechestvo, Kazan, 2000, 117–124 | MR | Zbl