We analyze the extended stochastic complexity (ESC) which has been proposed by K. Yamanishi. The ESC can be applied to learning algorithms for on-line prediction and batch-learning settings. Yamanishi derived the upper bound of ESC satisfying uniformly for all data sequences and that of the asymptotic expectation of ESC. However, Yamanishi concentrates mainly on the worst case performance and the lower bound has not been derived. In this paper, we show some interesting properties of ESC which are similar to Bayesian statistics: the Bayes rule and the asymptotic normality. We then derive the asymptotic formula of ESC in the meaning of almost sure and mean convergence within an error of o(1) using these properties.

This paper proposes a new formulation which minimizes the differential entropy for an optimal control problem. The conventional criterion of the optimal regulator control is a standard quadratic cost function E[M{x(t)}2} + N{v(t)}2], where x(t) is a state variable, u(t) is an input value, and M and N are positive weights. However, increasing the number of the variables of the system it is complex to find the solution of the optimal regulator control. Therefore, the simplicity of the solution is required. In contrast to the optimal regulator control, we propose the minimum entropy control which minimizes a differential entropy of the weighted sum of x(t) and u(t). This solution is derived on the assumptions that the linear control and x(t)u(t) 0 are satisfied. As the result, the formula of the minimum entropy control is very simple and clear. This result will be useful for the further work with multi variables of simple control formulation.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

Trade-offs between storage and error in the simple binary-valued retrieval problems are analyzed by using the rate distortion theoretic method from the viewpoint of the trade-offs evaluation model. These problems, the table lookup question, the exact match question, and the set of all binary-valued questions, have been proposed as the typical basic model of the information retrieval systems to evaluate the memory cost, the access cost, the state cost, the logic cost, and their relationships. The evaluation critera of memory-error trade-offs are the elastic condition and the excess of information. The former means that drastic savings of the amount of storage with a small error tolerance is feasible. The latter means the measure to evaluate the degree of the possibility for the system to achieve elastic condition. As a result, although the set of all binary-valued questions admits the possible highest excess of information, its statistical property is almost equivalent to that of the table lookup question, and only the exact match question satisfies the elastic condition. Furthermore, considering the conjunctive model which means the combination of each questions for the basic model, the property of elasticity or inelasticity for the basic model is changed from that of the basic model in accordance with the degree of the combination of the questions.

We propose that the model in experimental design be expressed in terms of an orthonormal system. Then, we can easily estimate the effects using Fourier transforms. We also provide the theorems with respect to the sum of squares needed in analysis of variance. Using these theorems, it is clear that we can execute the analysis of variance in this model.

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the response model used most often at present in experimental design is expressed through the effect of each factor, it is straightforward to ascertain how each factor affects the response variable. However, since the response model contains redundant parameters, in the analysis of variance we must calculate the degrees of freedom defined by the number of independent parameters. In this letter, we propose the idea of calculating the degrees of freedom over the model based on an orthonormal system for the first time. In this way, we can easily obtain the number of independent parameters associated with any component, which reduces the risk of mistakes in the calculation of the number of independent parameters and facilitates the implementation of estimation procedures.

Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.

Nishiara and Morita defined an i.i.d. word-valued source which is defined as a pair of an i.i.d. source with a countable alphabet and a function which transforms each symbol into a word over finite alphabet. They showed the asymptotic equipartition property (AEP) of the i.i.d. word-valued source and discussed the relation with source coding algorithm based on a string parsing approach. However, their model is restricted in the i.i.d. case and any universal code for a class of word-valued sources isn't discussed. In this paper, we generalize the i.i.d. word-valued source to the ergodic word-valued source which is defined by an ergodic source with a countable alphabet and a function from each symbol to a word. We show existence of entropy rate of the ergodic word-valued source and its formula. Moreover, we show the recurrence time theorem for the ergodic word-valued source with a finite alphabet. This result clarifies that Ziv-Lempel code (ZL77 code) is universal for the ergodic word-valued source.

In this letter, we generalize the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We define the overflow probability as the probability of codeword length, not per symbol, is larger than ηn and we introduce the ε-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to ε. Then we show that the ε-achievability of variable-length codes is essentially equivalent to the ε-achievability of fixed-length codes for general sources. Moreover by using above results, we show the condition of ε-achievability for some restricted sources given ε.

The reliability-based heuristic search methods for maximum likelihood decoding (MLD) generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Test error patterns are stored in lists and its space complexity is crucially large for MLD of long block codes. Based on the decoding algorithms both of Battail and Fang and of its generalized version suggested by Valembois and Fossorier, we propose a new method for reducing the space complexity of the heuristic search methods for MLD including the well-known decoding algorithm of Han et al. If the heuristic function satisfies a certain condition, the proposed method guarantees to reduce the space complexity of both the Battail-Fang and Han et al. decoding algorithms. Simulation results show the high efficiency of the proposed method.

Code construction for digital fingerprinting, which is a copyright protection technique for multimedia, is considered. Digital fingerprinting should deter collusion attacks, where several fingerprinted copies of the same content are mixed to disturb their fingerprints. In this paper, we consider the averaging attack, which is known to be effective for multimedia fingerprinting with the spread spectrum technique. We propose new methods for constructing fingerprinting codes to increase the coding rate of conventional fingerprinting codes, while they guarantee to identify the same number of colluders. Due to the new fingerprinting codes, the system can deal with a larger number of users to supply digital contents.

Reliability-based hybrid ARQ (RB-HARQ) is a kind of incremental-redundancy ARQ recently introduced. In the RB-HARQ, the receiver returns both NAK signal and set of unreliable bit indices if the received sequence is not accepted. Since each unreliable bit index is determined by the bitwise posterior probability, better approximation of that probability becomes crucial as the number of retransmissions increases. Assuming the systematic code for the initial transmission, the proposed RB-HARQ scheme has the following two features: (a) the sender retransmits newly encoded and interleaved parity bits corresponding to the unreliable information bits; (b) the retransmitted parity bits as well as the initial received sequence are put all together to perform the message passing decoding i.e. the suboptimal MAP decoding. Finally, simulation results are shown to evaluate the above two features.

By considering an analogy between information theory and predicate logic in artificial intelligence (AI) systems, we obtain interesting results in the field of both AI and information theory. First, we define the self-information and the entropy of formulas in predicate logic. Since inference of logic is regarded as information transformation, the information structure of logic is clarified by using mutual information based on the analogy with source coding. Next, we introduce a new concept of hierarchy of information, which have not been very clear in information theory, to discuss the similarity between inference and source coding. Finally, a new theoretical method is proposed for processing uncertain knowledge which can not be treated by the ordinary logic from the foregoing information theoretical concepts.

Y. S. Han et al. have proposed an efficient maximum likelihood decoding (MLD) algorithm using A* algorithm which is the graph search method. In this paper, we propose a new MLD algorithm for linear block codes. The MLD algorithm proposed in this paper improves that given by Han et al. utilizing codewords of dual codes. This scheme reduces the number of generated codewords in the MLD algorithm. We show that the complexity of the proposed decoding algorithm is reduced compared to that given by Han et al. without increasing the probability of decoding error.

In this paper, the criterion for evaluating inductive inference is considered from the information theoretical concept, especially from the view points of source coding and decision theory. Although the finite behavior of the inductive inference methods is important in the application field, there is no theoretical criterion for evaluating hypotheses at a finite stage of process. In the previous paper, we have defined an amount of semantic information included in well-formed formulas (wff) and denoted an analogy between inference and source coding. Inductive inference is regarded as source encoding, assuming that observed facts are compressed into a hypothesis similar to the way a source sequence is compressed into a codeword. By using the above definition, we can apply the criterion of source coding especially Minimum Description Length (MDL) to inductive inference. Therefore, the description length for representing a hypothesis is suitable for the criterion for evaluating a hypothesis inference at the finite stage of the inductive inference process. Moreover, by using the relation between the MDL criterion and Bayes risk, inductive inference can be interpreted with Bayes decision theory. The algorithm for the inductive inference of Horn clause is shown as an application of the proposed criterion. In the algorithm, the search space of hypotheses is restricted by using a refinement relation for increasing efficiency.

Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operarions, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.

Based on the concept used in the generalization of concatenated codes, new coding and decoding schemes which have unequal symbol reliability are proposed. Error exponents for symbols in different positions of the codewords are derived over discrete memoryless channels and proved to have unequal values for any nonzero rates less than the channel capacity. Similar techniques presented in this paper are also applicable to product codes.

In this paper, we propose a method for enhancing performance of a sequential version of the belief-propagation (BP) decoding algorithm, the group shuffled BP decoding algorithm for low-density parity-check (LDPC) codes. An improved BP decoding algorithm, called the shuffled BP decoding algorithm, decodes each symbol node in serial at each iteration. To reduce the decoding delay of the shuffled BP decoding algorithm, the group shuffled BP decoding algorithm divides all symbol nodes into several groups. In contrast to the original group shuffled BP, which automatically generates groups according to symbol positions, in this paper we propose a method for grouping symbol nodes which generates groups according to the structure of a Tanner graph of the codes. The proposed method can accelerate the convergence of the group shuffled BP algorithm and obtain a lower error rate in a small number of iterations. We show by simulation results that the decoding performance of the proposed method is improved compared with those of the shuffled BP decoding algorithm and the group shuffled BP decoding algorithm.

The original iterated codes proposed by P. Elias can be regarded as the codes constructed by iterating two dimensional product codes. While the modified product codes have been proposed and shown to be able to increase the rates without increasing the probability of decoding error. On the other hand, we have proposed new codes, called modified iterated codes A, and improved the performance for the original iterated codes by applying the coding and the decoding schemes of the modified product codes to these product codes. It has been proved that the rates of codes A were always much higher than those of the original iterated codes for cross-over probability p0.1617. In this paper, by additionally combining the coding and the decoding schemes of the superimposed codes constructed on the basis of the modified product codes, which are able to increase the rates with the same minimum distance, the performance for codes A can be further improved. We call codes thus constructed modified iterated codes B. It is shown that the rates of codes B are partially higher than those of codes A for p0.0959.

In digital signal processing, the sampling theorem states that any real valued function f can be reconstructed from a sequence of values of f that are discretely sampled with a frequency at least twice as high as the maximum frequency of the spectrum of f. This theorem can also be applied to functions over finite domain. Then, the range of frequencies of f can be expressed in more detail by using a bounded set instead of the maximum frequency. A function whose range of frequencies is confined to a bounded set is referred to as bandlimited function. And a sampling theorem for bandlimited functions over Boolean domain has been obtained. Here, it is important to obtain a sampling theorem for bandlimited functions not only over Boolean domain (GF(2)n domain) but also over GF(q)n domain, where q is a prime power and GF(q) is Galois field of order q. For example, in experimental designs, although the model can be expressed as a linear combination of the Fourier basis functions and the levels of each factor can be represented by GF(q), the number of levels often take a value greater than two. However, the sampling theorem for bandlimited functions over GF(q)n domain has not been obtained. On the other hand, the sampling points are closely related to the codewords of a linear code. However, the relation between the parity check matrix of a linear code and any distinct error vectors has not been obtained, although it is necessary for understanding the meaning of the sampling theorem for bandlimited functions. In this paper, we generalize the sampling theorem for bandlimited functions over Boolean domain to a sampling theorem for bandlimited functions over GF(q)n domain. We also present a theorem for the relation between the parity check matrix of a linear code and any distinct error vectors. Lastly, we clarify the relation between the sampling theorem for functions over GF(q)n domain and linear codes.