Source coding with a cost function for code symbols is studied and the moment function of the cost is investigated. Our coding theorems show that the optimal exponential moment of the cost is characterized by using the Rényi entropy. Further, coding theorems for$\varepsilon$-coding are also given.

The problem of guessing subject to distortion is considered, and the performance of randomized guessing strategies is investigated. A one-shot achievability bound on the guessing moment (i.e., moment of the number of required queries) is given. Applying this result to i.i.d. sources, it is shown that randomized strategies can asymptotically attain the optimal guessing moment. Further, a randomized guessing scheme which is feasible even when the block size is extremely large is proposed, and a single-letter characterization of the guessing moment achievable by the proposed scheme is obtained.

In this paper, a problem of joint source-channel coding for computing functions of outputs from correlated sources is studied. In particular, the system of computing two input functions where one of two outputs is available at the decoder as full-side information is investigated. Our result reveals that if the sensitivity of functions introduced by Ahlswede and Csiszár and the smoothness of sources introduced by Kuzuoka and Watanabe are satisfied, then the condition that the function is computable over the channel (i.e., the value of the function is correctly decoded) coincides with that for the identity function (i.e., reproducing the entire source outputs).

A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate for providing lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is presented. In particular, a single-letterized formula for a mixture of i.i.d. sources is obtained. It is also shown that our definition is appropriate to characterize the optimal exponential moment of the codeword length in the problem of source coding with common side-information available at the encoder and decoder under a constraint on the probability of a decoding error.

A novel definition of the conditional smooth Rényi entropy, which is different from that of Renner and Wolf, is introduced. It is shown that our definition of the conditional smooth Rényi entropy is appropriate to give lower and upper bounds on the optimal guessing moment in a guessing problem where the guesser is allowed to stop guessing and declare an error. Further a general formula for the optimal guessing exponent is given. In particular, a single-letterized formula for mixture of i.i.d. sources is obtained.

The problem of channel resolvability for channels with countably infinite input alphabet is considered. In particular, Hayashi's lower bound (i.e., converse part) on the optimal rate of channel resolvability, which was proved under the assumption of the finiteness of the input alphabet of the channel, is revisited. Our motivation is to prove the bound without the finiteness of the input alphabet. Although we cannot accomplish the final goal, we introduce a slight modification into the problem of channel resolvability and establish a coding theorem (particularly converse coding theorem) corresponding to Hayashi's result without the assumption of the finiteness of the input alphabet.

Two kinds of problems, (i) hypothesis testing with many-to-one compression and (ii) one-to-many lossy source coding with side-information at decoders, are investigated in a unified way. It is demonstrated that a simple key idea, which is developed by Iriyama for one-to-one source coding systems, can be applied to multiterminal source coding systems. In particular, general bounds on the error exponents of multiterminal hypothesis testing and one-to-many lossy source coding are given.

In this paper, we consider the problem of variable-length source coding allowing errors. The exponential moment of the codeword length is analyzed in the non-asymptotic regime and in the asymptotic regime. Our results show that the smooth Rényi entropy characterizes the optimal exponential moment of the codeword length.

The problem of distributed function computation for the class of smooth sources is studied, where functions to be computed are compositions of symbol-wise functions and some outer functions that are not symbol-wise. The optimal rate for computing those functions is characterized in terms of the Slepian-Wolf rate and an equivalence class of sources induced by functions. To prove the result, a new method to derive a converse bound for distributed computing is proposed; the bound is derived by identifying a source that is inevitably conveyed to the decoder and by explicitly constructing a code for reproducing that source. As a byproduct, it provides a conceptually simple proof of the known fact that computing a Boolean function may require as large rate as reproducing the entire source.

The problem of distributed data compression for function computation is considered, where (i) the function to be computed is not necessarily symbol-wise function and (ii) the information source has memory and may not be stationary nor ergodic. We introduce the class of smooth sources and give a sufficient condition on functions so that the achievable rate region for computing coincides with the Slepian-Wolf region (i.e., the rate region for reproducing the entire source) for any smooth sources. Moreover, for symbol-wise functions, the necessary and sufficient condition for the coincidence is established. Our result for the full side-information case is a generalization of the result by Ahlswede and Csiszár; our dichotomy theorem is different from Han and Kobayashi's dichotomy theorem, which reveals an effect of memory in distributed function computation. All results are given not only for fixed-length coding but also for variable-length coding in a unified manner.

This paper studies variable-length (VL) source coding of general sources with side-information. Novel one-shot coding bounds for Slepian-Wolf (SW) coding, which give nonasymptotic tradeoff between the error probability and the codeword length of VL-SW coding, are established. One-shot results are applied to asymptotic analysis, and a general formula for the optimal coding rate achievable by weakly lossless VL-SW coding (i.e., VL-SW coding with vanishing error probability) is derived. Our general formula reveals how the encoder side-information and/or VL coding improve the optimal coding rate in the general setting. In addition, it is shown that if the encoder side-information is useless in weakly lossless VL coding then it is also useless even in the case where the error probability may be positive asymptotically.

We present a novel nonasymptotic or finite blocklength achievability bounds for three side-information problems in network information theory. These include: 1) the Wyner-Ahlswede-Körner (WAK) problem of almost-lossless source coding with rate-limited side-information; 2) the Wyner-Ziv (WZ) problem of lossy source coding with side-information at the decoder; and 3) the Gel'fand-Pinsker (GP) problem of channel coding with noncausal state information available at the encoder. The bounds are proved using ideas from channel simulation and channel resolvability. Our bounds for all three problems improve on all previous nonasymptotic bounds on the error probability of the WAK, WZ, and GP problems-in particular those derived by Verdú. Using our novel nonasymptotic bounds, we recover the general formulas for the optimal rates of these side-information problems. Finally, we also present achievable second-order coding rates by applying the multidimensional Berry-Esséen theorem to our new nonasymptotic bounds. Numerical results show that the second-order coding rates obtained using our nonasymptotic achievability bounds are superior to those obtained using existing finite blocklength bounds.

In this paper, we investigate weak variable-length Slepian-Wolf (VL-SW) coding of general sources. First, by using the information-spectrum method, we show novel non-asymptotic trade-off between the error probability and the codeword length of VL-SW coding. Then, we give an asymptotic formula for the optimal coding rate achievable by VL-SW coding. Especially, we investigate VL-SW coding for mixed sources. Our results spotlights the fact that distinguishability between component sources plays an important role in adjusting the coding rate at the encoder. We also demonstrate that our general results derive a known formula for the optimal achievable rate of VL-SW coding for mixture of i.i.d. sources and extend to countably infinite alphabet case with mild condition.

We investigate the Wyner-Ziv coding in which the statistics of the principal source is known but the statistics of the channel generating the side information is unknown except that it is in a certain class. The class consists of channels such that the distortion between the principal source and side information is smaller than a threshold, but channels may be neither stationary nor ergodic. In this situation, we define a new rate-distortion function as the minimum rate such that there exists a Wyner-Ziv code that is universal for every channel in the class. Then, we show an upper bound and a lower bound on the rate-distortion function, and derive a matching condition such that the upper and lower bounds coincide. The relation between the new rate-distortion function and rate-distortion function of the Heegard-Berger problem is also discussed.

We investigate the Wyner-Ziv coding in which the statistics of the principal source is known but the statistics of the channel generating the side-information is unknown except that it is in a certain class. The class consists of channels such that the distortion between the principal source and the side-information is smaller than a threshold, but channels may be neither stationary nor ergodic. In this situation, we define a new rate-distortion function as the minimum rate such that there exists a Wyner-Ziv code that is universal for every channel in the class. Then, we show an upper bound and a lower bound on the rate-distortion function, and derive a matching condition such that the upper and lower bounds coincide.

We present a novel achievability bound for the Wyner-Ahlswede-Körner (WAK) problem of lossless source coding with rate-limited side-information. This bound is proved using ideas from channel simulation and channel resolvability. The bound improves on all previous non-asymptotic bounds on the error probability of the WAK problem. We also present achievable second-order coding rates by applying the multidimensional Berry-Essèen theorem to our new non-asymptotic bound.

A simple technique for bounding the redundancy of Slepian-Wolf coding is given. We demonstrate that our simple technique gives the tight bound established by He et al. Our proof is so simple that it can be easily extended to the case where the source (Xn, Yn) has an n-fold product distribution (i.e., (X1, Y1), ..., (Xn, Yn) are independent but not necessarily identically distributed). It can be also applied to Wyner-Ahlswede-Körner coding and gives novel bounds of the redundancies of the coding rates of the encoder and the helper.

A multiterminal lossy source coding problem, which includes various problems such as the Wyner-Ziv problem and the complementary delivery problem as special cases, is considered. It is shown that any point in the achievable rate-distortion region can be attained even if the source statistics are not known.

Universal lossless source coding for general sources are considered. Our results reveal that the definition of the universality of fixed-to-variable length coding (FV coding) based on the redundancy criterion is not equivalent to the one based on the average codeword length criterion. Moreover, it is clarified that, when we adopt the redundancy criterion, the existence of a universal FV code implies the existence of a universal fixed-to-fixed length code (FF code). On the other hand, it is also clarified that, when we adopt the average codeword length criterion, the existence of a universal FV code does not imply the existence of a universal FF code. Further, the relation between universal source coding and universal hypothesis testing is also investigated.

This paper deals with a universal coding problem for a certain kind of multiterminal source coding network called a generalized complementary delivery network. In this network, messages from multiple correlated sources are jointly encoded, and each decoder has access to some of the messages to enable it to reproduce the other messages. Both fixed-to-fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and the bounds of the error probabilities are clarified by using methods of types and graph-theoretical analysis.

This paper deals with a universal lossy coding problem for a certain kind of multiterminal source coding network called a complementary delivery system. A universal coding scheme based on Wyner-Ziv codes is proposed. While the proposed scheme cannot attain the optimal rate-distortion trade off in general, the rate-loss is upper bounded by a universal constant under some mild conditions. Moreover, the proposed scheme allows us to apply (non-universal) Wyner-Ziv codes to construct a universal lossy complementary delivery code.

This report deals with a universal coding problem for a certain kind of multiterminal source coding system that we call the complementary delivery coding system. Both fixed-to- fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and the bounds of the error probabilities are clarified via type-theoretical and graph-theoretical analyses.