Confidential information held by companies and individuals is often stored on storage devices. When the migration or disposal of such devices is required, it is necessary to overwrite and erase the information from the devices. In order to avoid degradation or to reduce the erasure time, it is desirable to minimize the cost of information erasure, such as the number of overwriting locations. In this paper, we consider the case where confidential information is distributed and stored in multiple storage devices. To analyze the costs of information erasure for this setting, we consider the achievable cost region, i.e., the region of possible cost values. We then show that this region can be characterized using single-letter random variables of bounded cardinalities. Here, we assume that the confidential information is generated by a stationary memoryless source and that a common random number is available in storage devices for erasure.

The Slepian-Wolf (SW) coding system is a source coding system with two encoders and a decoder, where these encoders independently encode source sequences from two correlated sources into codewords, and the decoder reconstructs both source sequences from the codewords. In this paper, we consider the situation in which the SW coding system is asynchronous, i.e., each encoder samples a source sequence with some unknown delay. We assume that delays are unknown but maximum and minimum values of possible delays are known to encoders and the decoder. We also assume that sources are discrete stationary memoryless and the probability mass function (PMF) of the sources is unknown but the system knows that it belongs to a certain set of PMFs. For this asynchronous SW coding system, we clarify the achievable rate region which is the set of rate pairs of encoders such that the decoding error probability vanishes as the blocklength tends to infinity. We show that this region does not always coincide with that of the synchronous SW coding system in which each encoder samples a source sequence without any delay.

This paper addresses the rumor source identification problem, where the goal is to find the origin node of a rumor in a network among a given set of nodes with the rumor. In this paper, we focus on a network represented by a regular tree which does not have any cycle and in which all nodes have the same number of edges connected to a node. For this network, we clarify that, with quite high probability, the origin node is within the distance “3” from the node selected by the optimal estimator, where the distance is the number of edges of the unique path connecting two nodes. This is clarified by the probability distribution of the distance between the origin and the selected node.

In this paper, we consider a source coding with side information partially used at the decoder through a codeword. We assume that there exists a relative delay (or gap) of the correlation between the source sequence and side information. We also assume that the delay is unknown but the maximum of possible delays is known to two encoders and the decoder, where we allow the maximum of delays to be subject to change by the block length. In this source coding, we give an inner bound and an outer bound on the achievable rate region, where the achievable rate region is the set of rate pairs of encoders such that the decoding error probability vanishes as the block length tends to infinity. Furthermore, we clarify that the inner bound coincides with the outer bound when the maximum of delays for the block length converges to a constant.

This paper considers a joint channel coding and random number generation from channel outputs. Specifically, we want to transmit a message to a receiver reliably and at the same time the receiver extracts pure random bits independent of the channel input. We call this problem as the joint channel coding and intrinsic randomness problem. For stationary memoryless channels, we show exponential upper bounds on both the decoding error probability and the variational distance between the distribution of the obtained random number and the uniform distribution. We also clarify that the obtained both bounds vanish as the block length tends to infinity, whenever a pair of coding rate and random bit rate is within the achievable rate region. Further, the above performance can be obtained by a universal scheme which does not depend on the channel.

We normally hold a lot of confidential information in hard disk drives and solid-state drives. When we want to erase such information to prevent the leakage, we have to overwrite the sequence of information with a sequence of symbols that is independent of the information. The overwriting is needed only at places where overwritten symbols are different from original symbols. Then, the cost of overwrites such as the number of overwritten symbols to erase information is important. In this paper, we deal with the worst-case cost which is the cost to erase the most laborious sequence and the average cost which is the expectation of the cost with respect to sequences. We clarify the minimum worst-case cost such that the mutual information between the original sequence and the overwritten sequence normalized by the blocklength of the sequences goes to zero as the blocklength tends to infinity. We also clarify the minimum average cost for stationary memoryless sources in the finite blocklength regime.

This paper deals with a multicast network with a server and many users. The server has content files with the same size, and each user requests one of the files. On the other hand, each user has a local memory, and a part of information of the files is cached (i.e., stored) in these memories in advance of users' requests. By using these cached information as side information, the server encodes files based on users' requests. Then, it sends a codeword through an error-free shared link for which all users can receive a common codeword from the server without error. We assume that the server transmits either of whole or partial information of requested files at each different transmission rate (i.e., the codeword length per file size). In this paper, we focus on the region of pairs of these two rates such that (whole or partial) information of requested files are recovered at each user with an arbitrary small error probability. We give inner and outer bounds on this region.

In this paper, we deal with the fixed-length lossy compression with the ε-fidelity criterion which is a kind of the distortion criterion such that the probability of exceeding a given distortion level is less than a given probability level. We give an achievability bound and a converse bound of the minimum number of codewords with this criterion. We show that our converse bound is tighter than that of Kostina and Verdú. We also show a numerical example which demonstrates that there exists some cases where our achievability bound is tighter than that of Kostina and Verdú.

A source coding system with side information at the decoder is a typical multiterminal source coding system where output sequences of two sources are independently encoded, but a decoder recovers only one output sequence from two codewords. Since Wyner, Ahlswede and Körner independently investigated this system, we call it as the WAK coding system. This paper investigates the ε-achievable rate region of the WAK coding system which allows the probability of error within a fixed tolerance ε(∈ (0, 1)), and clarifies the ε-achievable rate region for correlated general sources in terms of the smooth max-entropy and the smooth max Rényi divergence. To this end, we show a new one-shot converse theorem for the WAK coding system, and a one-shot covering lemma which is a refined version of Warsi's result. Then, combining these results, we clarify the ε-achievable rate region of the WAK coding system.

In this paper, we consider a lossy source coding problem with an encoder and two decoders, in which side information is available at one of the decoders with an unknown delay. We assume that the maximum of delay is known to among the encoder and two decoders. In this coding problem, we show upper and lower bounds on the rate-distortion (RD) function, where the RD function is the infimum of rates of codes of which the distortion between the source sequence and the reproduction sequence satisfies a certain distortion level. We also show that the upper bound coincides with the lower bound when the maximum of delay per block length converges to a constant. Furthermore, we show a condition such that the RD function is strictly larger than that for the case of no delay.

This paper clarifies the ε-achievable rate region of the Slepian-Wolf (SW) coding problem for general sources. We propose new upper and lower bounds on the error probability of the SW coding system for finite block lengths. The proposed bounds are mathematically simple and characterized by an optimization problem on the subset of pairs of output sequences which is closely related to the smooth max-entropy, and are tighter than those obtained by Han. By using these bounds, we clarify the ε-achievable rate region. Further, we also show outer and inner bounds on the ε-achievable rate region in terms of the smooth max-entropy. These two bounds coincide when the error probability vanishes.

This paper clarifies the rate-distortion function for general sources in terms of the smooth max Rényi divergence. To this end, we investigate the fixed-length coding problem with two kinds of distortion criteria. One criterion is the maximum distortion criterion, and the other is the average distortion criterion. We show a new achievability result for the latter criterion and new meta-converse theorems for both criteria, and clarify the rate-distortion functions in terms of the smooth Rényi divergence instead of the spectral mutual information.

Weissman introduced a channel coding problem for channels with action-dependent states. In this coding problem, there are two encoders and a decoder. One encoder outputs an action that affects states of the channel. Then, the other encoder encodes a message by using the channel state, and its codeword is fed into the channel. The decoder receives a noisy observation of the codeword, and reconstructs the message. For this coding problem, Weissman showed the capacity when states and the channel are stationary memoryless. In this paper, we show a general formula of the capacity when states and the channel may not be stationary memoryless, which is expressed by mutual information spectrum-sup/inf proposed by Verdú and Han. Our general formula coincides with the capacity derived by Tan when actions cannot affect states of channels. We also show that the capacity for nonstationary memoryless channels can be expressed by using ordinary mutual information.

Heegard and Berger introduced the model of lossy source coding in which side information is available at many decoders. For this model, their showed an upper bound of the rate-distortion function in the case where the source is stationary memoryless. In this paper, we extend their model to the case where the source may be nonstationary and/or nonergodic, and clarify the rate-distortion function for this model. This result is based on the information-spectrum method introduced by Han and Verdú. We also show some special cases of the rate-distortion function, and a single-letterized upper bound of the rate-distortion function in the case where the source is stationary memoryless.

Low-density parity-check (LDPC) codes become very popular in channel coding, since they can achieve the performance close maximum-likelihood (ML) decoding with linear complexity of the block length. Muramatsu et al. proposed a code using LDPC matrices for Slepian-Wolf source coding. However, since they employed ML decoding, their code is not universal, that is their decoder needs to know the probability distribution of the source. On the other hand, if there exists a universal code using LDPC matrices, we can arbitrary decrease the error probability for all sources whose achievable rate region contains the rate pair of encoders even if the probability distribution of sources is unknown. To this end, we show the existence of a universal Slepian-Wolf source code using LDPC matrices in the case where the source is stationary memoryless.

Wyner's source coding system is one of the most fundamental fixed-length source coding systems with side information available only at the decoder. In this coding system, Wyner showed the achievable rate region which is the set of rate pairs of encoders such that the probability of error can be made arbitrarily small for sufficiently large block length. However, the closed form of this region is not clarified because the region is expressed by the union of indefinitely many sets. This paper deals with two correlated sources whose conditional distribution is represented by binary input output symmetric channels, and clarifies closed forms of the achievable rate region for Wyner's source coding system.