Based on a study of ABS (Asymmetric Binary Systems), we introduce a new theorem related to Rayleigh's theorem. We also present an extension of ABS to finite source alphabets with probability distribution taking real numbers.

This paper considers noiseless source codes for the unequal cost of bits, a generalization of the cost measured by the codeword length of binary source codes. We generalize AIFV (Almost Instantaneous Fixed-to-Variable length) codes to the case of unequal bit costs taking positive integers.

This paper proposes a new lossless data compression coding scheme named an asymmetric encoding-decoding scheme (AEDS), which can be considered as a generalization of tANS (tabled variant of asymmetric numeral systems) although the class of the AEDS is much wider than the class of the tANS. In this paper, we explain the principle of the AEDS, and evaluate the average code length of the AEDS for several cases.

The Asymmetric Encoding-Decoding Scheme (AED) recently proposed by the authors is a lossless data compression scheme that can attain a compression ratio better than (or at worst the same as) the Huffman code and the tANS (tabled variant of Asymmetric Numeral Systems). In this paper, we will derive an upper bound on the average codeword length of the optimal AEDS for any stationary memoryless source with a finite discrete alphabet and evaluate how fast it converges to the source entropy as the number of internal states increases in the AEDS.

We propose a joint coding scheme using multiple code tables to efficiently transmit a sequence of messages of a discrete memoryless source (DMS) through a finite-state noiseless channel with unequal costs of code letters, which includes a noiseless (d, k)-constrained channel as a particular case. This paper presents a methodology for code design based on two methods. The first method, integer programming, is used to optimize a prefix-free code at each channel state when codeword costs are unequal and vary with each state. The second method is an iterative optimization that minimizes the average cost of the joint coding scheme using multiple code tables. The proposed coding scheme achieves the optimal average cost in the class of joint coding schemes using multiple code tables of prefix-free codes for a given pair of DMS and finite-state channel.

This paper gives a methodology for optimizing AIVF (almost instantaneous variable-to-fixed length) codes based on two algorithms: The first algorithm is the dynamic programming (DP) technique developed by Dubé and Haddad to construct a set of parse trees of AIVF codes. The second algorithm is the iterative optimization algorithm proposed by Fujita, Iwata, and Yamamoto, which can maximize the average parse length of AIVF codes. As a result, the proposed AIVF code achieves a longer average parse length than the known AIVF codes and Tunstall codes.

Hu, Yamamoto, Honda proposed the binary AIFVm codes and proved that the worst-case redundancy of optimal binary AIFV-m codes is exactly 1/m for m ∈{2,3,4}. We derive a new upper bound on the redundancy of optimal binary AIFV-3 codes when the probability of the most likely source symbol is known. Furthermore, it is proved by using the redundancy bound of optimal binary AIFV-3 codes that the worst-case redundancy of optimal binary AIFV-5 codes is exactly 1/5.

In the entropy coding, AIVF (almost instantaneous variable-to-fixed length) codes using multiple parsing trees can attain a better compression rate than the Tunstall code, which attains the best compression rate in the class of VF codes with a single parsing tree. Furthermore, the multiple parsing trees of an AIVF code can be multiplexed into a single parsing tree. In this paper, we propose a new universal data compression code based on the techniques of the AIVF code. The proposed universal code can also be considered as an improvement of the LZW code (Welch code). We explain how the AIVF coding techniques can be applied to universal coding by growing dynamically a single parsing tree, and we evaluate the compression rate of the proposed universal code theoretically and using several corpora.

We call the alphabetic version of the AIFV-m code the alphabetic AIFV-m codes. This paper defines binary alphabetic AIFV-m codes and proposes an algorithm to design the optimal binary alphabetic AIFV-m codes in terms of the minimum average codeword length for stationary memoryless sources. The proposed method is based on an iterative optimization algorithm and a dynamic programming algorithm.

A general time-varying feedback coding scheme is proposed for M-user fully connected symmetric Gaussian interference channels. Based on the analysis of the general coding scheme, we prove a theorem which gives a criterion for designing good time-varying feedback codes for Gaussian interference channels. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference when M = 2. This capacity improvement is more significant when the signal-to-noise ratio (SNR) is not very high. In addition, our coding scheme can be proved mathematically and numerically to outperform the Kramer code for M ≥ 2 when the SNR is equal to the interference-to-noise ratio (INR). Besides, the generalized degrees-of-freedom (GDoF) of our proposed coding scheme can be proved to be optimal in the all network situations (very weak, weak, strong, very strong) for any M. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for M = 2 or the MohajerTandon-Poor lattice coding scheme for M > 2. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme when M = 2 and the Mohajer-TandonPoor lattice coding scheme when M > 2. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by only using marginal posterior distributions under a better cooperation strategy between transmitters.

We consider Markov chains with finite states, which have unique stationary distributions and satisfy the following conditions I)-III). I) Each state sihas its own discrete parameter ti. II) Each state sihas a local performance function f(ti). III) Each state sihas a transition probability function pi, j(ti) from state sito state sj. In this paper, we give an iterative method to optimize the global average performance of the above Markov chains, which have unique stationary distributions for all sets of the parameters. This method is a generalization of the iterative method to construct the optimal AIFV-m code, which was proposed in our previous paper. But in this paper, the following two points are further refined besides the generalization. (i) We clarify the condition such that the iterative method always terminates and gives correct results although the iterative method is a kind of Las Vegas algorithm. (ii) We provide a closed-form expression of coefficients to solve the local optimization problem of each state.

We extend the concept of compact code trees, i.e., canonical code trees, of Huffman codes to the case of binary AIFV (almost instantaneous fixed-to-variable length) codes. We give an algorithm to enumerate the number of all compact AIFV code trees by using a bijection between the compact AIFV code trees and the proper sequences defined in this paper. Based on the enumeration of compact AIFV code trees, we give an efficient coding scheme to describe the compact AIFV code trees, which is required when we send a decoder the information of code trees used in the encoding of source sequences.

Iwata and Yamamoto proposed an iterative algorithm to obtain the optimal AIFV-m code with m code trees for a given source probability distribution, which can attain better compression rate than Huffman codes generally. In this paper, we generalize the optimization problem of AIFV-m code trees to the optimization problem of the average performance of finite Markov systems with m states, which have a unique stationary distribution. Then, we prove that the generalized iterative algorithm can derive the optimal system with m states, and hence, the original iterative algorithm can derive the optimal AIFV-m code.

An alphabetic code is a code such that the order of codeword sequences coincides with the alphabetic order of source sequences. If we use one code tree, the optimal alphabetic code attaining the minimum average code length can be constructed by the Hu-Tucker algorithm. In this paper, we show that an efficient alphabetic AIFV (almost instantaneous fixed-to-variable length) code can be constructed by using three code trees and allowing at most two-bit decoding delay, and we propose a simple method to construct an alphabetic AIFV code from the Hu- Tucker code tree so that the alphabetic AIFV code can attain better compression rate than the Hu- Tucker code.

In this paper, we propose two types of dynamic AIFV (almost instantaneous fixed-to-variable length) coding schemes for stationary memoryless sources with unknown probability distribution such that the dynamic AIFV code trees are constructed from the dynamic Huffman code tree. The one is based on the AIFV code with two code trees and the other is based on a simplified AIFV-m code with m code trees. The proposed dynamic AIFV coding can be implemented with almost the same complexity as the dynamic Huffman coding, and it can attain better compression rate than the dynamic Huffman code when the probability of the most likely source symbol is larger than about 0.62.

Recently Yamamoto and Ueda proposed multiple object identification (MOID) codes to identify multiple objects via a channel at once, which is an extension of identification (ID) codes. They gave the explicit construction of MOID codes and derived the achievable triplet of coding rate R, the error exponents E1and E2of type I and type II decoding error probabilities. However, they did not treat the converse problem of the coding theorem. In this paper, we consider the coding rate of multiple objects Rkin addition to R, E1, and E2, and derive a condition that (R, Rk, E1, E2) must satisfy for any MOID codes of noiseless channels.

In communication through asymmetric channels the capacity-achieving input distribution is not uniform in general. Homophonic coding is a framework to invertibly convert a (usually uniform) message into a sequence with some target distribution, and is a promising candidate to generate codewords with the nonuniform target distribution for asymmetric channels. In particular, a Variable-to-Fixed length (VF) homophonic code can be used as a suitable component for channel codes to avoid decoding error propagation. However, the existing VF homo-phonic code requires the knowledge of the maximum relative gap of probabilities between two adjacent sequences beforehand, which is an unrealistic assumption for long block codes. In this paper we propose a new VF homophonic code without such a requirement by allowing one-symbol decoding delay. We evaluate this code theoretically and experimentally to verify its asymptotic optimality.

Binary AIFV codes, which can attain better compression rate than Huffman codes, uses two code trees that may have incomplete internal nodes, and source symbols are assigned to some internal nodes in addition to leaves. Although the code trees of Huffman codes, which are full binary trees, are well studied, the AIFV code trees have not been yet studied in detail. In this paper, we show that there exists a bijection between binary AIFV code trees and Schroder paths, and give two coding schemes to represent Schroder paths. The first one is a fixed length coding scheme, which has O(n2) time-complexity. The second one is a variable length coding scheme using a simple AIFV code. The latter attains O(n) time-complexity, but the coding rate has loss less than 4.1% of the optimal coding rate.

The Yamamoto-Itoh (YI) scheme is a simple two phase coding scheme for discrete memoryless channels with noiseless feedback, which can attain the so-called Burnashev error-exponent. In this paper, we show how we can apply the YI scheme to discrete memoryless broadcast channels, and derive the achievable error-exponents region of the YI scheme for given coding rates.

We propose an algorithm to construct an optimal code that achieves the minimum average codeword length in the class of binary AIFV-m codes with m code trees T0, T1,..., Tm-1for a given stationary memoryless source. The algorithm is an iterative algorithm such that the optimal Tkfor a given set of costs is derived by dynamic programming (DP) and the costs are updated from the set of code trees (T0, T1, · · ·, Tm-1), iteratively. The proposed DP works with polynomial time and space for source alphabet size. We prove the AIFV-m code obtained by the proposed algorithm is optimal for m = 2, 3,4, 5 although the algorithm works for any m and we conjecture the optimality also holds for m ≥ 6. Furthermore, we verify by some examples of sources that the average codeword length of the optimal binary AIFV-m codes can be decreased as m becomes large.

Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with pmax ≥1/2, where pmax is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use m code trees and allow at most m-bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is 1/m for m ≤ 4.

The discrete time channel AWGN(A) with additive white Gaussian noise, strict power constraint and noiseless feedback is considered. The best error decoding exponent is investigated, limiting to the case of non-exponential number of messages (i.e. the rate of transmission R = 0). The new transmission strategy is proposed, showing that for AWGN(A) channel with noiseless feedback at zero rate R = 0 it is possible to achieve the same error exponent as for transmission of two messages. It gives another proof of known result for AWGN(A) channel. The strategy described is applicable to a wider class of channels.

AIFV codes are lossless codes that generalize the class of instantaneous FV codes. The code uses multiple code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to be tight. Along with this, a tight upper bound on the redundancy of optimal binary AIFV codes is derived for the case pmax≥1/2, where pmaxis the probability of the most likely source symbol. This is the first theoretical work on the redundancy of optimal binary AIFV codes, suggesting superiority of the codes over Huffman codes.

In Maurer's universal statistical test and its variations including Coron's test to check the randomness of a binary sequence, the entropy of sequence is calculated from the repetition intervals of L-grams in the sequence, and the randomness is evaluated based on whether or not the entropy attains the maximum. However, since the derivative of the entropy is zero at the maximum, the deviation from the maximum cannot be detected with high sensitivity. In this paper, we propose a new universal statistical test, in which a given sequence is converted into the most sensitive one by changing bit `1' to `0' randomly in the sequence. By simulation, we show that the proposed universal statistical test can detect non-randomness much more sensitively than Maurer's and Coron's tests and T-complexity test.

Private information retrieval scheme for coded data storage is considered in this paper. We focus on the case where the size of each data record is large and hence only the download cost (but not the upload cost for transmitting retrieval queries) is of interest. We prove that the tradeoff between storage cost and retrieval/download cost depends on the number of data records in the system. We propose a class of linear storage codes and retrieval schemes, and derive conditions under which our schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained.

In this paper, we propose a new coding scheme for symmetric Gaussian interference channels with feedback based on the ideas of time-varying coding schemes. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference. This improvement is more significant when the signal-to-noise ratio (SNR) is not very high. It is shown theoretically and numerically that our coding scheme can outperform the Kramer code. In addition, the generalized degrees-of-freedom of our proposed coding scheme is equal to the Suh-Tse scheme in the strong interference case. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for all channel parameters. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by using only marginal posterior distributions under a better cooperation strategy between transmitters.

Polar codes achieve the rate-distortion bound for nonuniform sources and/or asymmetric distortion measures. However, the performance is not always near optimal for finite code length, especially for short code length. In this paper a new scheme for lossy source coding is proposed. In addition to polar coding, arithmetic coding is applied in the scheme. The source is first encoded by polar coding for lossy compression, then it is further compressed losslessly by arithmetic coding. It is shown that the scheme achieves the rate-distortion bound asymptotically with a good empirical performance. It is also shown that the distortion of the scheme has a better second-order exponent than those of the other polar coding schemes.

We propose almost instantaneous fixed-to-variable length (AIFV) codes such that two (resp. K - 1) code trees are used, if code symbols are binary (resp. K-ary for K ≥ 3), and source symbols are assigned to incomplete internal nodes in addition to leaves. Although the AIFV codes are not instantaneous codes, they are devised such that the decoding delay is at most two bits (resp. one code symbol) in the case of binary (resp. K-ary) code alphabet. The AIFV code can attain better average compression rate than the Huffman code at the expenses of a little decoding delay and a little large memory size to store multiple code trees. We also show for the binary and ternary AIFV codes that the optimal AIFV code can be obtained by solving 0-1 integer programming problems.

In the case of ordinary identification coding, a code is devised to identify a single object among N objects. But, in this paper, we consider a coding problem to identify K objects at once among N objects in the both cases that K objects are ranked or not ranked. By combining Moulin-Koetter scheme with the ε-almost strongly universal class of hash functions used in Kurosawa-Yoshida scheme, an efficient and explicit coding scheme is proposed for K-multiple-object identification (K-MOID) coding. Furthermore, it is shown that the K-MOID capacity CK-MOID, which is the maximum achievable coding rate in the K-MOID coding, is equal to the ordinary channel capacity, and the proposed scheme can attain CK-MOID.

For information transmission a discrete time channel with independent additive Gaussian noise is used. There is also a feedback channel with independent additive Gaussian noise, and the transmitter observes without delay all outputs of the forward channel via that noisy feedback channel. Transmission of nonexponential number of messages is considered and the achievable decoding error exponent for such a combination of channels is investigated. Transmission/decoding method used in the paper generalizes and strengthens the earlier method used by authors for BSC and Gaussian channel. It allows to improve essentially earlier results. In particular, for small feedback noise, it allows to gain 33.3% (instead of 23.6% in earlier papers).

In the case of ordinary identification coding, a code is devised to identify one object among N objects. But, in this paper, we consider an identification coding problem to identify M objects at once among N objects in the both cases that M objects are or are not ranked. By combining Kurosawa-Yoshida scheme with Moulin-Koetter scheme, an efficient identification code is proposed, which can attain high coding rate and error exponents compared with the case that an ordinary identification code is used M times.

In this paper, a new variable length coding scheme using a low density parity check (LDPC) code is proposed for the lossy compression of general i.i.d. finite sources. It is proved that the proposed scheme achieves the rate-distortion function asymptotically for an LDPC ensemble. For our setting, Miyake-Muramatsu already proposed an asymptotically optimal LDPC coding scheme. In their scheme, a source sequence is first vector-quantized using an LDPC matrix and then it is compressed losslessly by fixed length coding with another LDPC matrix. However, it is not shown whether their scheme can attain good performance practically. This is mainly because of the difficulty of lossless coding by a fixed length code. In the proposed scheme, the lossless compression is performed by arithmetic coding instead of the fixed length code. Combined with vector-quantization using the reinforced belief propagation, the proposed scheme attains performance near the rate-distortion function practically with time complexity roughly equal to${\bf O}(n\log n)$for length$n$source sequences.

In this paper, K-ary almost instantaneous fixed-to-variable-length (AIFV) codes are proposed for K ≥ 3, and it is shown that the K-ary AIFV codes using K - 1 code trees can attain better compression than K-ary Huffman codes for stationary memoryless sources. Furthermore, it is also shown that binary relaxed AIFV codes with two code trees can beat binary Huffman codes.

This paper considers polar coding for asymmetric settings, that is, channel coding for asymmetric channels and lossy source coding for nonuniform sources and/or asymmetric distortion measures. The difficulty for asymmetric settings comes from the fact that the optimal symbol distributions of codewords are not always uniform. It is known that such nonuniform distributions can be realized by Gallager's scheme which maps multiple auxiliary symbols distributed uniformly to an actual symbol. However, the complexity of Gallager's scheme increases considerably for the case that the optimal distribution cannot be approximated by simple rational numbers. To overcome this problem for the asymmetric settings, a new polar coding scheme is proposed, which can attain the channel capacity without any alphabet extension by invoking results on polar coding for lossless compression. It is also shown that the proposed scheme achieves a better tradeoff between complexity and decoding error probability in many cases.

It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity CS, which is usually smaller than the channel capacity C. In order to remove the loss C-CS, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each massage. Several bounds of achievable multiplex coding rate region are derived for general wiretap channels in the sense of information-spectral methods, by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels. Furthermore, the exact region for deterministic coding is determined for stationary memoryless full-rank wiretap channels.

For information transmission a discrete time channel with independent additive Gaussian noise is used. There is also feedback channel with independent additive Gaussian noise, and the transmitter observes without delay all outputs of the forward channel via that feedback channel. Transmission of nonexponential number of messages is considered and the achievable decoding error exponent for such a combination of channels is investigated. It is shown that for any finite noise in the feedback channel the achievable error exponent is better than similar error exponent of the no-feedback channel. Method of transmission/decoding used in the paper strengthens the earlier method used by authors for BSC. In particular, for small feedback noise, it allows to get the gain up to 23.6% (instead of 14.3% earlier for BSC).

We consider channel coding of binary asymmetric memoryless channels with polar codes. The difficulty for asymmetric channels comes from the fact that the optimal input probability distributions are not always uniform. Şaşoğlu et al. realized a nonuniform input distribution by mapping multiple auxiliary symbols distributed uniformly to an actual input symbol. However, the complexity of the scheme increases considerably for the case that the input distribution cannot be approximated by simple rational numbers. To overcome this problem, we propose another polar coding scheme for asymmetric channels, which realizes the optimal nonuniform input distribution by randomizing symbols in the frozen bits with an appropriate probability distribution.

Coding theorems on a$(2,2)$-threshold scheme with an opponent are discussed in an asymptotic setup, where the opponent tries to impersonate one of the two participants. A situation is considered where$n$secrets$S^{n}$from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to$S^{n}$with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a$(2, 2)$-threshold scheme that is secure against the impersonation attack by the opponent. It is shown that if the correlation level between the two shares equals to$\ell \geq 0$, the minimum attainable rates coincide with$H(S)+\ell $, where$H(S)$denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to$\ell $. It is also shown that a simple scheme using an ordinary$(2,2)$-threshold scheme attains all the bounds as well.

Arikan and Merhav proved joint source-channel coding theorems for guessing decoders based on Gallager's method. But, in this paper, only channel coding is considered to derive a stronger channel coding theorem for constant composition universal codes based on the method of types. Furthermore, the coding theorem is applied to the wiretap channel coding problem.

We propose a new data compression scheme based on T-codes [3] using a dictionary method such that all phrases added to a dictionary have a recursive structure similar to T-codes. Our scheme can compress the Calgary Corpus more efficiently than known schemes based on T-codes [2] and the UNIX compress, a variant of LZ78.

Ignatenko and Willems (2009) proved coding theorems for a biometric secret generation model and a biometric secret transmission model. But, they treated only the case of perfect secrecy and they did not consider the coding rate of a public channel. In this paper, we derive general coding theorems including the coding rate of a public channel in the case of general security levels for secret information and biometric information.

In this paper, Yamamoto-Itoh scheme, which is a blockwise variable length coding scheme originally proposed to the case of noiseless feedback, is generalized to the case of noisy feedback, and some lower bounds of the error exponent of the generalized Yamamoto-Itoh scheme are derived for discrete memoryless channels and additive white Gaussian channels. Furthermore, it is shown that error exponent can be improved by the generalized Yamamoto-Itoh scheme even if a feedback channel is noisy, and the error exponent of the generalized Yamamoto-Itoh scheme tends to the one of the original Yamamoto-Itoh scheme as the feedback noise becomes small.

It is shown that the T-complexity can be derived from a differential equation which represents how average codeword length increases by the T-augmentation. Furthermore, the proposed differential equation method can be applied to the LZ-complexity in the same way. This new approach is simple, and the obtained expressions coincide with the ones in previous studies.

Ngai-Yeung and Erez-Feder independently derived the capacity region of network coding with a single source and two sinks, in which a common message is sent from the source to both sinks but each private message is sent to only the corresponding sink. In this paper, it is shown that the above capacity region can be achieved by separate linear coding such that three routes of private and common messages are perfectly separated. This means that each private message can be sent to the corresponding sink only by routing while the common message can be sent to both sinks by a relatively simple multicast linear network code.

LDPC codes initially studied for channel coding can be applied to source coding, and Miyake-Muramatsu showed theoretically that the rate-distortion function can be achieved asymptotically by using LDPC codes for any stationary memoryless finite source. In their scheme, a source sequence is first vector-quantized by using an LDPC matrix and then it is compressed losslessly by another LDPC matrix. So, their scheme is fixed length coding. Unfortunately, it is not shown that their scheme can attain a good performance practically. In this paper, we propose a new variable length coding scheme, which uses linear programming for vector-quantization and arithmetic coding with probability estimated by belief propagation for lossless coding. The proposed variable length lossy coding can attain the rate-distortion function asymptotically. Furthermore, it can practically attain a performance considerably better than the so-called time sharing bound of the rate-distortion function.

It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.

For the information transmission a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes without delay all the outputs of the forward channel via that feedback channel. The overall transmission time is fixed. The transmission of a exponential number of messages (i.e. the transmission rate is positive) is considered. The achievable decoding error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the best known lower bound for the error exponent of the no-feedback channel.

A binary symmetric channel is considered. A transmitter observes without delay all the outputs of the forward channel via a noisy binary symmetric channel (a feedback). For illustrative purposes, we consider the transmission of only three messages. The best achievable error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than some positive level, then the achievable error exponent is better than the similar error exponent of the no-feedback channel. In particular, it is the case if the crossover probability of the feedback channel is eight (or more) times smaller than the crossover probability of the forward channel. The transmission strategy described in this talk and the corresponding lower bound for the error exponent can be strengthened and extended to the positive transmission rates as well.

The security level of the Shannon cipher system is traditionally measured by equivocation, where is a secret plaintext with length and is its cryptogram. But, Merhav and Arikan have considered another security criterion, which is measured by the number of guesses needed for a wiretapper to uncover from . Merhav has also considered the third security criterion, which measured by the probability of correct guess of a wiretapper. On the other hand, in the case of the traditional security criterion, Yamamoto has treated a coding problem for correlated source outputs and such that only is secret against wiretappers and only must be transmitted to a legitimate receiver. In this correspondence, coding theorems are proved for the case that Yamamoto's coding problem is applied to Merhav-Arikan's security criterion or Merhav's security criterion.

The bit commitment can be realized by using a noisy channel. Winter-Nascimento-Imai showed that the bit commitment capacity of a noisy channel is given by Cb= maxpNH(X\Y) where X and Y are the input and output of the channel. In this paper, the idea of a multiplex coding, which was first introduced into the coding problem of a wiretap channel by Kobayashi-Yamamoto-Ogawa, is applied to the bit commitment coding. The coding theorem is proved for the multiplex coding of bit commitment based on a noisy channel, and it is shown that several mutually independent secrets can be committed at the same time via a nosiy channel attaining the perfect secrecy of each secret with the total coding rate log \X\, where \X\ is the cardinality of channel input alphabet.

The security level of the Shannon cipher system is traditionally measured by the equivocation 1/NH(Y|Z), where Y is a secret plaintext and Z is its cryptogram. But, Merhav and Arikan have considered another security criterion, which is measured by moments of the number of guesses needed for a wiretapper to uncover Y from Z. On the other hand, in the case of the traditional security criterion, Yamamoto has treated the coding problem with correlated source outputs X and Y such that only X is secret against wiretappers and only Y must be transmitted to a legitimate receiver. In this paper, we extend these two results and prove the coding theorems for the correlated source outputs in Merhav-Arikan's security criterion

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case where some information about the secret leaks from a non-qualified set of shares, and hence, they are more desirable than weak ramp SS schemes. However, it is not known how to construct the strong ramp SS schemes in the case of general access structures. In this paper, it is shown that a strong ramp SS scheme can always be constructed from a SS scheme with plural secrets for any feasible general access structure. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong

In key management schemes that realize secure multicast communications encrypted by group keys on a public network, tree structures are often used to update the group keys efficiently. Selcuk and Sidhu have proposed an efficient scheme which updates dynamically the tree structures based on the withdrawal probabilities of members. In this paper, it is shown that Selcuk-Sidhu scheme is asymptotically optimal for the cost of withdrawal. Furthermore, a new key management scheme, which takes account of key update costs of joining in addition to withdrawal, is proposed. It is proved that the proposed scheme is also asymptotically optimal, and it is shown by simulation that it can attain good performance for nonasymptotic cases

The Move-to-front (MTF) scheme is a data-compression method which converts each symbol of a source sequence to a positive integer sequentially, and encodes it to a binary codeword. The compression performance of this algorithm has been analyzed usually under the assumption of the so-called symbol extension. But, in this paper, upper and lower bounds are derived for the redundancy of the MTF scheme without the symbol extension for stationary ergodic sources and Markov sources. It is also proved that for the stationary ergodic first-order Markov sources, the MTF scheme can attain the entropy rate if and only if the transition matrix of the source is a kind of doubly stochastic matrix. Moreover, if the source is a Kth-order Markov source (K/spl ges/2), the MTF scheme cannot attain the entropy rate of the source generally.

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.

This paper shows the derivation procedure of optimal secret sharing scheme (SSS) for a given access structure in the multiple assignment schemes based on integer programming.

In this article, low-density parity-check (LDPC) codes are applied to lossy source coding and we study how the asymptotic performance of MacKay's (see ibid, vol.45, p.399-431, Mar. 1999 and vol.47, p.2101, July, 2001) LDPC codes depends on the sparsity of the parity-check matrices in the source coding of the binary independent and identically distributed (i.i.d.) source with Pr{x=1}=0.5. In the sequel, it is shown that an LDPC code with column weight O(logn) for code length n can attain the rate-distortion function asymptotically.

One-shot coding and repeated coding are considered for the class of almost instantaneous variable-to-fixed length (AIVF) codes, C/sub AIVF/, which includes some nonproper VF codes in addition to the class of proper VF codes, C/sub PVF/. An algorithm is given to construct the average-sense optimal (a-optimal) AIVF code in one-shot coding that attains the maximum average parse length in C/sub AIVF/. The algorithm can also be used to obtain an AIVF code with multiple parse trees, which can attain good performance for repeated coding. Generally, the a-optimal code for one-shot coding and the good code for repeated coding are more efficient than the Tunstall (1967) code in A-ary cases if A/spl ges/3 although they coincide with the Tunstall code in the binary case. The competitively optimal (c-optimal) VF code is also considered for one-shot coding, and it is shown that the c-optimal code does not always exist in C/sub PVF/ and in C/sub AIVF/. Furthermore, whenever the c-optimal code exists, the Tunstall code is c-optimal in C/sub PVF/ and the a-optimal code obtained by our algorithm is c-optimal in C/sub AIVF/ if A=2 or 3, but the a-optimal code is not always c-optimal in C/sub AIVF/ if A/spl ges/4.

A new recursive universal code of the positive integers is proposed, in which any given sequence can be used as a delimiter of codeword while bit "0" is used as a delimiter in known universal codes, e.g., Levenshtein code, Elias /spl omega/ code, Even-Rodeh code, Stout code, Bentley-Yao code, etc. The codeword length of the proposed code is shorter than log/sub 2//sup n/ n in almost all of sufficiently large positive integers although the known codes are longer than log/sub 2//sup n/ n for any positive integer n.

Rate distortion theory is considered for the Shannon cipher system (SCS). The admissible region of cryptogram rate R, key rate R/sub k/, legitimate receiver's distortion D, and wiretapper's uncertainty h is determined for the SCS with a noisy channel. Furthermore, inner and outer bounds of the admissible region of R, R/sub k/, D, and wiretapper's attainable minimum distortion D/spl tilde/ are derived for the SCS with a finite discrete source and a noiseless channel.

A rate-distortion problem is considered for a triangular communication system (TCS), which has one encoder f and two decoders g/sub X/ and g/sub Y/. The encoder f maps correlated source outputs (X/sup K/,Y/sup K/) to two codewords W/sub X/ and W/sub Y/, which are sent to g/sub X/ and g/sub Y/, respectively. The decoders g/sub X/ and g/sub Y/ can communicate with each other via rate-constrained channels as many times as they need, and g/sub X/ reproduces X/spl circ//sup K/ while g/sub Y/ reproduces Y/spl circ//sup K/. The admissible rate-distortion region is determined for this TCS. Furthermore, the relations between the TCS and the Gray-Wyner (1974) system, Wyner's (1974) common information, Yamamoto's cascade communication system (1981), and the successive refinement system are discussed.

Competitively optimal coding is considered and the following is proved. (1) If the competitively optimal code exists for a given source probability p(x), then it also attains the minimum expected codeword length. (2) If the Huffman code tree for p(x) is unbalanced in probability weight, then the competitively optimal code does not exist. Furthermore, the relation between competitively optimal coding and game theory is considered.

Source coding problems are treated for Shannon's (1949) cipher system with correlated source outputs (X,Y). Several cases are considered based on whether both X and Y, only X, or only Y must be transmitted to the receiver, whether both X and Y, only X, or only Y must be kept secret, or whether the security level is measured by (/sup 1//spl sol//sub K/H(X/sup K//spl verbar/W), (/sup 1//spl sol//sub K/H(Y/sup K//spl verbar/W)) or /sup 1//spl sol//sub K/H(X/sup K/Y/sup K//spl verbar/W) where W is a cryptogram. The admissible region of cryptogram rate and key rate for a given security level is derived for each case. Furthermore, two new kinds of common information of X and Y, say C/sub 1/(X;Y) and C/sub 2/(X;Y), are considered. C/sub 1/(X;Y) is defined as the rate of the attainable minimum core of (X/sup K/,Y/sup K/) by removing each private information from (X/sup K/,Y/sup K/) as much as possible, while C/sub 2/(X;Y) is defined as the rate of the attainable maximum core V/sub C/ such that if one loses V/sub C/, then each uncertainty of X/sup K/ and Y/sup K/ becomes H(V/sub C/). It is proved that C/sub 1/(X;Y)=I(X;Y) and C/sub 2/(X;Y)=min /spl lcub/H(X), H(Y)/spl rcub/. C/sub 1/(X;Y) justifies the author's intuitive feeling that the mutual information represents a common information of X and Y.>

Combining a note by J. Rissanen (1983) and an idea of enumerative coding, the authors obtain a new implementation of the Ziv-Lempel incremental parsing algorithm for coding and decoding discrete data sequences. The space and the time complexities are linear for both the encoder and the decoder. The authors describe the algorithm.>

A coding theorem is proved for the secret sharing communication system (SSCS) with two Gaussian wiretap channels. This communication system is an extension of both the SSCS with two noiseless channels and the Gaussian wiretap channel (GWC). The admissible region of rates and security levels for the SSCS with two GWCs is described by the capacities and secrecy capacities of two GWCs. The following three cases are considered: two wiretappers cannot cooperate with each other: they can cooperate to decipher the transmitted information; and it is not known whether they can cooperate or not.>

A new universal binary code for the positive integers is proposed as a modified version of M. Wang's (see ibid., vol.34, p.324-6, Mar. 1988) flag encoding scheme. The codeword length of the new scheme is shorter than Wang's, on an average, for large initial segments of the positive integers. The performance of the new scheme is also compared with that of other universal schemes. Furthermore, it is shown that an asymptotically optimal code can be achieved by modifying the new flag scheme such that the flag length varies dynamically.>

The coding theorem is proved for the system with two noisy channels, each of which is a broadcast channel. It is assumed that the legitimate channel is less noisy than the wiretapped channel. The admissible region of rates and security levels is obtained completely. The relationship of the present results to previous results is examined.>

A rate-distortion problem is considered for a communication system (f, phi /sub 1/) with a secondary decoder phi /sub 2/ to be hindered which uses a different distortion measure from the primary system. The least achievable distortion of the secondary decoder is evaluated for the most secure primary system. Source coding for sources with additional outputs to be kept secret from the receiver or wiretappers is also discussed. Security is evaluated by distortion measures instead of the equivocation function used by H. Tamamoto (1983).>

The source coding problem is considered for secret sharing communication systems (SSCS's) with two or three channels. The SSCS, where the informationXis shared and communicated through two or more channels, is an extension of Sbannon's cipher communication system and the secret sharing system. The security level is measured with equivocation; that is,(1/N)H(X|W_{i}), (1/N)H(X|W_{i}W_{i}), etc., whereW_{i}andW_{j}are the wire-tapped codewords. The achievable rate region for the given security level is established for the SSCS's with two or three channels.

A new source coding problem is considered for a one-way communication system with correlated source outputs\{XY\}. One of the source outputs, i.e.,\{X\}, must be transmitted to the receiver within a prescribed distortion tolerance as in ordinary source coding. On the other hand, the other source output, i.e.,\{Y\}, has to be kept as secret as possible from the receiver or wiretappers. For this case the equivocation-distortion function\Gamma \ast(d)and the rate-distortion-equivocation functionR\ast (d,e)are defined and evaluated. The former is the maximum achievable equivocation of\{Y\}under the distortion tolerancedfor\{X\}, and the latter is the minimum rate necessary to attain both the equivocation toleranceefor\{Y\}and the distortion tolerancedfor\{X\}. Some examples are included.

A source coding problem is considered for the Wyner-Ziv type system where the decoder is required to estimate the value of some function of the encoder input and the side information. The rate-distortion function is established for this system, and for some binary cases parametric expressions are obtained to enable numerical calculations.

A source coding problem is considered for cascade and branching communication systems. The achievable rate region is established for the cascade systems and bounds are obtained for the branching systems. Some examples are also included.

Using the Viterbi decoding algorithm with repeat request for convolutional codes is proposed, and the resulting performance is analyzed by random coding and generating function arguments and by simulation. It is shown that the reliability function of the proposed decoding algorithm is asymptotically twice that of the Viterbi decoding algorithm without repeat request, and that in certain practical situations the proposed algorithm can save about 50 percent in constraint length over the ordinary Viterbi algorithm for a given performance.

A modified Schalkwijk-Barron transmission scheme is presented for channels with noiseless feedback. The modified scheme employs blockwise decision and a fixed length transmission in place of Viterbi's sequential decision feedback. The reliability functions of the modified scheme are derived for the additive white Gaussian noise (AWGN) channel and discrete memoryless channels (DMC's). For the AWGN channel the result obtained is asymptotically the same as in the case of the Schalkwijk-Barron scheme. On the other hand, the new result obtained for DMC's shows that the modified scheme also attains high reliability functions for DMC's.