Implementation of Markov chains over Galois fields
Sh. R. Nurutdinov · Discrete Mathematics and Applications · 2004
The automaton implementation of a determinate function is a probabilistic automaton A 1 = ( S, Y, P s , λ( s )), where S is the Markov chain state set, P s is an m 1 × m 1 stochastic matrix, Y is the output alphabet of cardinality m 2 ≤ 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 × 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. As the base polynomials, we use polynomial functions over the Galois field where r = 2 n – 1, x, s, b i , a ij ∈ GF (2 n ). We give expressions of an automaton A 1 in the framework of a polynomial model over the field GF (2 n ) of the form M 1 = (, f 1 ( x, s ), f 2 ( s )), where is the discrete random variable which takes values µ ∈ GF (2 n ) determined by some probability vector = ( p 1 , . . . , pk 1 ) such that where B i are stochastic Boolean matrices and k 1 ≥ – m 1 + 1, and of an automaton M 2 = (, f 1 ( x, s ), f 2 ( s ), , f 3 ( x, s )), where is a discrete random variable which takes values µ′ ∈ GF (2 n ) determined by some probability vector = ( p 1 , . . . , pk 2 ) such that where B i are stochastic Boolean matrices and k 2 ≥ – m 1 + 1. The problem of representation of a discrete random variable over the field GF (2 n ) has been solved earlier.