Recently, Muramatsu proposed source coding algorithms that use the randomness of a past sequence. The technique of his source coding algorithms is one method of constructing codes from the technique of random coding. By using his technique, we propose a channel coding algorithm with random numbers which can be observed by both the encoder and the decoder where the random numbers are independent of the messages to be transmitted. Then the proposed coding algorithm can transmit messages over a discrete memoryless channel up to the channel capacity with an arbitrarily small decoding error rate and arbitrarily small bits of random numbers per message transmission asymptotically.

A channel code is constructed using sparse matrices for stationary memoryless channels that do not necessarily have a symmetric property like a binary symmetric channel. It is also shown that the constructed code has the following remarkable properties. 1. Joint source-channel coding: Combining channel code with lossy source code, which is also constructed by sparse matrices, a simpler joint source-channel code can be constructed than that constructed by the ordinary block code. 2. Universal coding: The constructed channel code has a universal property under a specified condition.

Wyner and Ziv considered the rate-distortion function for source coding with side information at the decoder (we call the Wyner-Ziv problem). In this paper we show an information-spectrum approach to the Wyner-Ziv problem for general class of nonstationary and/or nonergodic sources with side information at the decoder, where the distortion measure is arbitrary and may be nonadditive. We show that a general formula for the rate-distortion function of the Wyner-Ziv problem for general sources with the maximum distortion criterion under fixed-length coding by using the information spectrum approach.

In this paper, we define the distortion at a certain complexity level, which is the dual quantity of the distortion-complexity. We prove a theorem dual to the theorem which we have given of the asymptotic property of the distortion-complexity. We also give a universal data-base for fixed-rate data compression with distortion and prove its asymptotic optimality.

Let {Xk}k=- be a stationary and ergodic information source, where each Xk takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x-1, x0, x1, ) and D > 0 let the approximate D-match recurrence time be defined by Rn (x, D) = min {m n: dn (Xn1, Xm+nm+1) D}, where Xji denotes the string xixi+1 xj and dn: An An [0, ) is a metric of An induced by d for each n. Let R (D) be the rate distortion function of the source {Xk}k=- relative to the fidelity criterion {dn}. Then it is shown that lim supn-1/n log Rn (X, D) R (D/2) a. s.

Research into applying LDPC code theory, which is used for channel coding, to source coding has received a lot of attention in several research fields such as distributed source coding. In this paper, a source coding problem with a fidelity criterion is considered. Matsunaga et al. and Martinian et al. constructed a lossy code under the conditions of a binary alphabet, a uniform distribution, and a Hamming measure of fidelity criterion. We extend their results and construct a lossy code under the extended conditions of a binary alphabet, a distribution that is not necessarily uniform, and a fidelity measure that is bounded and additive and show that the code can achieve the optimal rate, rate-distortion function. By applying a formula for the random walk on lattice to the analysis of LDPC matrices on Zq, where q is a prime number, we show that results similar to those for the binary alphabet condition hold for Zq, the multiple alphabet condition.

The explicit construction of a universal source code for correlated sources is presented. The construction is based on a technique of simulated random coding algorithms [5]. The proposed algorithm simulates the random generation of linear codes. For every pair of correlated sources whose achievable rate region includes a given pair of encoding rates, the decoding error rate of the proposed algorithm goes to zero almost surely as the block length goes to infinity.

We propose a novel decoding algorithm called “sampling decoding”, which is constructed using a Markov Chain Monte Carlo (MCMC) method and implements Maximum a Posteriori Probability decoding in an approximate manner. It is also shown that sampling decoding can be easily extended to universal coding or to be applicable for Markov sources. In simulation experiments comparing the proposed algorithm with the sum-product decoding algorithm, sampling decoding is shown to perform better as sample size increases, although decoding time becomes proportionally longer. The mixing time, which measures how large a sample size is needed for the MCMC process to converge to the limiting distribution, is evaluated for a simple coding matrix construction.

We define the complexity and the distortion-complexity of an individual finite length string from a finite set. Assuming that the string is produced by a stationary ergodic source, we prove that the distortion-complexity per source letter and its expectation approximate arbitrarily close the rate-distortion function of this source as the length of the string grows. Furthermore, we apply this property to construct a universal data compression scheme with distortion.

The achievable rate region related to the problem of generating mutually independent random sequences is determined. Furthermore, it is proved that the output distribution of lossless source encoders with correlated side information is asymptotically independent of the side information. Based on this, we can realize a random number generator that produces mutually asymptotically independent random sequences from random sequences emitted from correlated sources.

Secret key agreement is a procedure for agreeing on a secret key by exchanging messages over a public channel when a sender, a legitimate receiver (henceforth referred to as a receiver), and an eavesdropper have access to correlated sources. Maurer [6] defined secret key capacity, which is the least upper bound of the key generation rate of the secret key agreement, and presented an upper and a lower bound for the secret key capacity. The advantage distillation capacity is introduced and it is shown that this quantity equals to the secret key capacity. Naive information theoretical expressions of the secret key capacity and the advantage distillation capacity are also presented. An example of correlated sources, for which an analytic expression of the secret key capacity can be obtained, is also presented.

We propose source coding algorithms that use the randomness of a past sequence. The proposed algorithms solve the problems of multi-terminal source coding, rate-distortion source coding, and source coding with partial side information at the decoder. We analyze the encoding rate and the decoding error rate in terms of almost-sure convergence.

A data-base for data compression is universal if in its construction no prior knowledge of the source distribution is assumed and is optimal if, when we encode the reference index of the data-base, its encoding rate achieves the optimal encoding rate for any given source: in the noiseless case the entropy rate and in the semifaithful case the rate-distortion function of the source. In the present paper, we construct a universal data-base for all stationary ergodic sources, and prove the optimality of the thus constructed data-base for two typical methods of referring to the data-base: one is a block-shift type reference and the other is a single-shift type reference.

This paper deals with a secret key agreement problem from correlated random numbers. It is proved that there is a pair of linear matrices that yields a secret key agreement in the situation wherein a sender, a legitimate receiver, and an eavesdropper have access to correlated random numbers. A relation between the coding problem of correlated sources and a secret key agreement problem from correlated random numbers are also discussed.

The paper proposes and reports on pototyping a work bench system for novice Prolog programmers which consists of a visually-structured interactive tracer and a prototype-based programming support. The tracer actually is a simulated interpreter in Prolog. It is interpreted by a Prolog interpreter being embedded with facilities interfacing programs in Prolog and the objects programmed in C. It displays, by way of these objects, the past, current and future goals, highlights variable sharing and value substitution, and marks the current goals and backtrack choice points. It is at user's will to let the tracer show and hide subgoals as well as to let it backtrack when it failed, step back for redoing or terminate tracing. The programming support module first provides the programmer with structural prototype patterns and the roles of the constituent functions. We developed a support system for the 2 types of recursive definitions. After having selected the prototype, the user is requested to specify the data types and the names of variables to be put in the arguments, which propagate through the structure. The support module then offers a menu of primitive or user-registered constituent functions as may be useful in processing and/or obtaining user-specified types of data. Thirdly the system lets the user express his/her intention by sample input-output data instances in his/her task goals. It makes the values propagate through the structures thus motivating the user to design the constituent functions. At the goal recursion point, the user is allowed to creep into examining the definitions of the reduced versions of the instances, helping the user find the condition with which the recursion terminates. Finally the module assists the user to convert the structural descriptions into Prolog programs.