You are here: Home :: Area NEM :: Mathematics

Sh. R. Nurutdinov

Implementation of Markov chains over Galois fields

The automaton implementation of a determinate function is a probabilistic automaton A ₁ = (S, Y, P_s, λ(s)), where S is the Markov chain state set, P_s is an m₁ × m₁ stochastic matrix, Y is the output alphabet of cardinality m₂ ≤ m₁. The automaton implementation of a probabilistic function is a probabilistic automaton A₂ = (S, Y, P_s, P_y), where S, Y, P_s are of the same sense as in A₁, while P_y is a stochastic m₁ × m₂ 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ⁿ – 1, x, s, b_i, a_ij ∈ GF(2ⁿ).

We give expressions of an automaton A₁ in the framework of a polynomial model over the field GF(2ⁿ) of the form M₁ = (, f₁(x, s), f₂(s)), where is the discrete random variable which takes values µ ∈ GF(2ⁿ) determined by some probability vector = (p₁, . . . , pk₁ ) such that

where B_i are stochastic Boolean matrices and k₁ ≥ – m₁ + 1, and of an automaton M₂ = (, f₁(x, s), f₂(s), , f₃(x, s)), where is a discrete random variable which takes values µ′ ∈ GF(2ⁿ) determined by some probability vector = (p₁, . . . , pk₂) such that

where B_i are stochastic Boolean matrices and k₂ ≥ – m₁ + 1. The problem of representation of a discrete random variable over the field GF(2ⁿ) has been solved earlier.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 14, 07/2004
Pages: 273 - 285

Show full article (external site)

Show all available items of this journal

 

Area NEM