We define the topological entropy of the discretized Markov transformations. Previously, we obtained the topological entropy of the discretized dyadic transformation. In this research, we obtain the topological entropy of the discretized golden mean transformation. We also generalize this result and give the topological entropy of the discretized Markov β-transformations with the alphabet Σ={0,1,…,k-1} and the set F={(k-1)c,…,(k-1)(k-1)}(1≤c≤k-1) of (k-c) forbidden blocks, whose underlying transformations exhibit a wide class of greedy β-expansions of real numbers.

We define discretized Markov transformations and find an algorithm to give the number of maximal-period sequences based on discretized Markov transformations. In this report, we focus on the discretized dyadic transformations and the discretized golden mean transformations. Then we find an algorithm to give the number of maximal-period sequences based on these discretized transformations. Moreover, we define a number-theoretic function related to the numbers of maximal-period sequences based on these discretized transformations. We also introduce the entropy of the maximal-period sequences based on these discretized transformations.

We design M(≥3)-phase spreading sequences of Markov chains optimal in terms of bit error probabilities in asynchronous SSMA (spread spectrum multiple access) communication systems. To this end, we obtain the distributions of the normalized MAI (multiple access interference) for such systems and find a necessary and sufficient condition that the distributions become independent of the phase shifts.

We study asynchronous SSMA communication systems using binary spreading sequences of Markov chains and prove the CLT (central limit theorem) for the empirical distribution of the normalized MAI (multiple-access interference). We also prove that the distribution of the normalized MAI for asynchronous systems can never be Gaussian if chains are irreducible and aperiodic. Based on these results, we propose novel theoretical evaluations of bit error probabilities in such systems based on the CLT and compare these and conventional theoretical estimations based on the SGA (standard Gaussian approximation) with experimental results. Consequently we confirm that the proposed theoretical evaluations based on the CLT agree with the experimental results better than the theoretical evaluations based on the SGA. Accordingly, using the theoretical evaluations based on the CLT, we give the optimum spreading sequences of Markov chains in terms of bit error probabilities.

Recently there have been several attempts to construct a Markov information source based on chaotic dynamics of the PLM (piecewise-linear-monotonic) onto maps. Study, however, soon informs us that Kalman's 1956 embedding of a Markov chain is to be highly appreciated. In this paper Kalman's procedure for embedding a prescribed Markov chain into chaotic dynamics of the PLM onto map is revisited and improved by using the PLM onto map with the minimum number of subintervals.

We extend the sliding block code in symbolic dynamics to transform J (≥2) sequences of Markov chains with time delays. Under the assumption that the chains are irreducible and aperiodic, we prove the central limit theorem (CLT) for the normalized sums of extended sliding block codes from J sequences of Markov chains. We apply the theorem to the system analysis of asynchronous spread spectrum multiple access (SSMA) communication systems using spreading sequences of Markov chains. We find that the standard Gaussian approximation (SGA) for estimations of bit error probabilities in such systems is the 0-th order approximation of the evaluation based on the CLT. We also provide a simple theoretical evaluation of bit error probabilities in such systems, which agrees properly with the experimental results even for the systems with small number of users and low length of spreading sequences.

Recently binary or real-valued sequences generated by Chebyshev maps are proposed as spreading sequences in DS/CDMA systems. In this article, we consider sequences of real-valued functions of bounded variation, which include binary functions, of iterates generated by Chebyshev maps, and evaluate explicitly the upper bound of mixing rate of such sequences by defining the modified Perron-Frobenius operator associated with the Chebyshev maps.

We point out that the interval algorithm can be expressed in the form of a shift on the sequence space. Then we clarify that, by using a Bernoulli process, the interval algorithm can generate only a block of Markov chains or a sequence of independent blocks of Markov chains but not a stationary Markov process. By virtue of the finitary coding constructed by Hamachi and Keane, we obtain the procedure, called the finitary interval algorithm, to generate a Markov process by using the interval algorithm. The finitary interval algorithm also gives maps, defined almost everywhere, which transform a Markov measure to a Bernoulli measure.

We consider both-ends-fixed k-ary necklaces and enumerate all such necklaces of length n from the viewpoints of symbolic dynamics and β-expansions, where n and k(≥ 2) are natural numbers and β(> 1) is a real number. Recently, Sawada et al. proposed an efficient construction of k-ary de Bruijn sequence of length kn, which for each n ≥ 1, requires O(n) space but generates a single k-ary de Bruijn sequence of length kn in O(1)-amortized time per bit. Based on the enumeration of both-ends-fixed k-ary necklaces of length n, we evaluate auto-correlation values of the k-ary de Bruijn sequences of length kn constructed by Sawada et al. We also estimate the asymptotic behaviour of the obtained auto-correlation values as n tends to infinity.

The interval in ℕ composed of finite states of the stream version of asymmetric binary systems (ABS) is irreducible if it admits an irreducible finite-state Markov chain. We say that the stream version of ABS is irreducible if its interval is irreducible. Duda gave a necessary condition for the interval to be irreducible. For a probability vector (p,1-p), we assume that p is irrational. Then, we give a necessary and sufficient condition for the interval to be irreducible. The obtained conditions imply that, for a sufficiently small ε, if p∈(1/2,1/2+ε), then the stream version of ABS could not be practically irreducible.