Modeling Markov chains in Galois fields
Sh. R. Nurutdinov
Abstract:
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.
UDC:
519.7 Received: 10.04.2002
DOI:
10.4213/dm159
Fulltext:
PDF file (1024 kB)