We investigate the rate-distortion-leakage region of the Chief Executive Officer (CEO) problem, considering the presence of a passive eavesdropper and privacy constraints. We start by examining the region where a general distortion measure quantifies the distortion. While the inner bound of the region is derived from previous work, this paper newly develops an outer bound. To derive the outer bound, we introduce a new lemma tailored for analyzing privacy constraints. Next, as a specific instance of the general distortion measure, we demonstrate that the tight bound for discrete and Gaussian sources is obtained when the eavesdropper has no side information, and the distortion is quantified by the log-loss distortion measure. We further investigate the rate-distortion-leakage region for a scenario where the eavesdropper has side information, and the distortion is quantified by the log-loss distortion measure and provide an outer bound for this case. The derived outer bound differs from the inner bound by only a minor quantity that appears in the constraints associated with the privacy-leakage rates, and these bounds match when the distortion is large.

In machine learning, one of the methods to solve multiclass classification problems is a framework called Error-Correcting Output Codes (ECOC), which constructs a multiclass classifier by combining a lot of binary classifiers. ECOC assigns binary codewords to each category, and the multiclass classification performance varies depending on the code. In this study, we treat each element of the codeword as a random variable and evaluate the average performance of ECOC. As a result, for$M$class classification if the number of binary classifiers is$O(\log M)$, then the average error probability of various codes approaches that of MAP estimation. We show that the important points are the ratio between the number of binary classifiers and$\log M$and the difference between the maximum posterior probability and the second highest posterior probability for the categories.

The utilization of database such as IoT has progressed. As pioneering work, Yamamoto (1983) assumed the source (database) which consists of public information and private information and found theoretical limits (first-order rate analysis) among the coding rate, privacy for the decoder and utility in two special cases. In this paper, we consider a more general case based on the work by Shinohara and Yagi (2022). Introducing a measure of privacy for the encoder, we investigate two problems as follows: The first problem is the first-order rate analysis among the coding rate, utility, privacy for the decoder, and privacy for the encoder in which utility is measured by the expected distortion or the excess-distortion probability. The second task is establishing the strong converse theorem for utility-privacy trade-offs in which utility is measured by the excess-distortion probability. These results may lead to a more refined analysis such as the second-order rate analysis.

Error-correcting output coding (ECOC) is a method for constructing a multi-valued classifier using a combination of given binary classifiers. ECOC can estimate the correct category by other binary classifiers even if the output of some binary classifiers is incorrect based on the framework of the coding theory. The code word table representing the combination of these binary classifiers is important in ECOC. ECOC is known to perform well experimentally on real data. However, the complexity of the classification problem makes it difficult to analyze the classification performance in detail. For this reason, theoretical analysis of ECOC has not been conducted. In this study, if a binary classifier outputs the estimated posterior probability with errors, then this binary classifier is said to be noisy. In contrast, if a binary classifier outputs the true posterior probability, then this binary classifier is said to be noiseless. For a theoretical analysis of ECOC, we discuss the optimality for the code word table with noiseless binary classifiers and the error rate for one with noisy binary classifiers. This evaluation result shows that the Hamming distance of the code word table is an important indicator.

Secret-key agreement using physical identifiers is a promising security protocol for the authentication of users and devices with small chips, owing to its lightweight security. In the previous studies, the fundamental limits of such a protocol were analyzed, and the results showed that two auxiliary random variables were involved in the capacity region expressions. However, with two auxiliary random variables, it is difficult to directly apply the expressions to derive the computable forms of the capacity regions for certain information sources such as binary and Gaussian sources, which hold importance in practical applications. In this paper, we explore the structure of authentication channels and reveal that for the classes of degraded and less noisy authentication channels, a single auxiliary random variable is sufficient to express the capacity regions. As specific examples, we use the expressions with one auxiliary random variable to derive the computable forms for binary and Gaussian sources. Numerical calculations for the Gaussian case show the trade-off between secret-key and privacy-leakage rates under a given storage rate, which illustrates how the noise in the enrollment phase affects the capacity region.

We analyze the fundamental trade-off of secret key-based authentication systems in the presence of an eavesdropper for correlated Gaussian sources. A complete characterization of the trade-off among secret-key, storage, and privacy-leakage rates of both generated and chosen secret models is provided. One of the main contributions is revealing that unlike the known results for discrete sources, there is no need for the second auxiliary random variable in characterizing the capacity regions for the Gaussian cases. In addition, it is shown that the strong secrecy for secrecy-leakage of the systems can be achieved by an information-spectrum approach, and the parametric expressions (computable forms) of the capacity regions are also derived.

Secret-key agreement based on biometric or physical identifiers is a promising security protocol for authenticating users or devices with small chips and has been extensively studied recently. Kittichokechai and Caire (2015) investigated the optimal trade-off in a secret-key agreement model with physical identifiers, where the structure of the authentication channels is similar to the wiretap channels, from information theoretic approaches. Later, the model was extended by Günlü et al. (2018) introducing noise in the enrollment phase and cost-constrained actions at the decoder. The results of these studies show that two auxiliary random variables are involved in the expressions of the optimal rate regions of secret-key, storage, and privacy-leakage rates. However, with these two auxiliary random variables, the complexity of computing the rate region may be prohibitively high. Due to this problem, we are interested in exploring classes of authentication channels that need only one auxiliary random variable in the capacity region expression for discrete source settings. The result shows for the class of degraded and less noisy authentication channels, a single auxiliary random variable is sufficient to express the capacity region of the model. As an example, we also derive the capacity region of secret-key, storage, and privacy-leakage rates for binary sources. Furthermore, the capacity region for scalar Gaussian sources is derived under Gaussian authentication channels.

Consider M-valued (M$\geq$3) classification systems realized by combination of N(N$\geq\lceil\log_{2}$M$\rceil$) binary classifiers. Such a construction method is called an Error Correcting Output Code (ECOC). First, focusing on a Reed-Muller (RM) code, we derive a modified RM (mRM) code to make it suitable for the ECOC. Using the mRM code and the Hadamard matrix, we introduce a simplex code which is one of the powerful equidistant codes. Next, from the viewpoint of system evaluation model, we evaluate the ECOC by using constructive coding described above. We show that they have desirable properties such as Flexible, Elastic, and Effective Elastic as M becomes large, by employing analytical formulas and experiments.

Error-Correcting Output Coding (ECOC) is a method for constructing a multi-valued classifier using a combination of binary classifiers. The effectiveness of ECOC for multivalued classification problems has been demonstrated by many experimental evaluations. Therefore, classification performance have strongly depended on the data under consideration, and it is not clear what kind of combinations of binary classifiers have good performance. Motivated by this fact, the authors have clarified the best combination of binary classifiers that makes ECOC, assuming a situation in which each binary classifier can estimate the true posterior probability. They also have proposed a total framework for analytical evaluation when a binary classifier outputs an estimated posterior probability that approximates the true posterior probability. These studies established a framework for evaluating the theoretical performance of ECOC.Based on these findings, this study discusses the theoretical performance of ECOC from the upper bound perspective. The results showed that increasing the Hamming distance between code words can blackuce the error rate. We then evaluate various combinations of binary classifiers based on analytical evaluation.

The biometric identification system, introduced by Willems et al., is a mathematical model to identify users based on their physical features. Although the maximum rate of the number of users which are reliably dealt with in the system (identification capacity) and the exponential behavior of the average error probability (error exponents) of the legitimate users have been revealed via information theoretic approaches, optimum error exponents has not been shown when there exists a nonlegitimate user in the system. In this paper, we formally define the reliability function as the optimum error exponent for legitimate users for a given rate of the number of legitimate users and a given error exponent for the nonlegitimate users. It is shown that the reliability function can be completely characterized by the well-known random coding exponent and the hypothesis testing error exponent.

The intrinsic randomness (IR) problem is considered for general setting. In the literature, the optimum IR rate with respect to the variational distance has been characterized in two ways. One is based on the information spectrum quantity and the other is based on the smooth Rényi entropy. Recently, Nomura has revealed the optimum IR rate with respect to$f$-divergences, which includes the variational distance, the Kullback-Leibler (KL) divergence and so on, by using the informational spectrum quantity. In this paper, we try to characterize the optimum IR rate with respect to a subclass of$f$-divergences by using the smooth Min entropy. The subclass of$f$-divergences considered in this paper includes typical distance measures such as the total variational distance, the KL divergence, the Hellinger distance and so on.

The source resolvability problem (or resolvability problem for short) is one of random number generation problems in information theory. In the literature, the optimum achievable rates in the resolvability problem have been characterized in different two ways. One is based on the information spectrum quantity and the other is based on the smooth Rényi entropy. Recently, Nomura has revealed the optimum achievable rate with respect to the f-divergence, which includes the variational distance, the Kullback-Leibler (KL) divergence and so on. On the other hand, the optimum achievable rates with respect to the variational distance has been characterized by using the smooth Rényi entropy. In this paper, we try to extend this result to the case of other distances. To do so, we consider the resolvability problem with respect to the subclass of f-divergences and determine the optimum achievable rate in terms of the smooth Rényi entropy. The subclass of f-divergences considered in this paper includes typical distance measures such as the total variational distance, the KL divergence, the Hellinger distance and so on.

In the present paper, we investigate the fundamental trade-off of identification, secrecy, storage, and privacy-leakage rates in biometric identification systems for hidden or remote Gaussian sources. We introduce a technique for deriving the capacity region of these rates by converting the system to one where the data flow is in one-way direction. Also, we provide numerical calculations of three different examples for the generated-secret model. The numerical results imply that it seems hard to achieve both high secrecy and small privacy-leakage rates simultaneously. In addition, as special cases, the characterization coincides with several known results in previous studies.

In this study, we investigate fundamental trade-off among identification, secrecy, template, and privacy-leakage rates in biometric identification system. Ignatenko and Willems (2015) studied this system assuming that the channel in the enrollment process of the system is noiseless. In the enrollment process, however, it is highly considerable that noise occurs when bio-data is scanned. In this paper, we impose a noisy channel in the enrollment process and establish the capacity region of the rate tuples. The obtained result shows that this result reduces to the one given by Ignatenko and Willems (2015) as a special case where the enrollment channel is noiseless.

To solve multiple classification problems with $M (\geq$ 3) categories, many studies have been devoted using $N (\geq\ \lceil\log_{2}M\rceil)$ binary $(\{0,1\})$ classifiers, where these systems are known as binary Error-Correcting Output Codes (binary ECOC). As an extended version of the binary ECOC, the ternary $(\{0,\ *,\ 1\})$ ECOC have also been discussed, where ternary classifiers classify data into positive examples when the element is 1, into negative examples when the element is 0, and no classification when the element is $*$. In this paper, we discuss the ternary ECOC system from the view point of the system evaluation model based on rate-distortion function. First, we discuss a table of M code words with length N which is given by a ternary matrix W of M rows and N columns. Next, by leveraging the benchmark data for multiclass document classification which is widely used in Japan, the relationships between the probability of classification error Peand the number of the ternary classifiers N for a given M are experimentally investigated. In addition, by assuming the M-dimensional Normal distribution for a classification data model, the relationship between Peand N for a given M is also examined. Finally, we show by the system evaluation model that the ternary ECOC systems have desirable properties such as “Flexible”, “Elastic”, and “Effective Elastic”, when M becomes large.

The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources.

The problem of channel resolvability, where a given output probability distribution over a channel is approximated by encoding uniform random number as a channel input, is addressed. The channel resolvability has recently been generalized to the variable-length setting, where the variable-length uniform random number instead of the fixed-length one is encoded. Though the optimum resolvability rate can be reduced compared with the fixed-length resolvability, it is not yet clear how much resolvability rate can be saved even when the given source and channel are stationary and memoryless. Given a stationary memoryless source and a discrete memoryless channel, this paper establishes a single-letter formula for the variable-length resolvability under the variational distance as an approximation measure. When the channel is a full-rank discrete memoryless channel, the established formula reduces to a further simpler formula characterized by the mutual information between the source and the channel. The established formula also recovers a known formula for the variable-length source resolvability.

In the problem of variable-length δ -channel resolvability, the channel output is approximated by encoding a variable-length uniform random number under the constraint that the variational distance between the target and approximated distributions should be within a given constant δ asymptotically. In this paper, we assume that the given channel input is a mixed source whose components may be general sources. To analyze the minimum achievable length rate of the uniform random number, called the δ -resolvability, we introduce a variant problem of the variable-length δ -channel resolvability. A general formula for the δ -resolvability in this variant problem is established for a general channel. When the channel is an identity mapping, it is shown that the δ -resolvability in the original and variant problems coincide. This relation leads to a direct derivation of a single-letter formula for the δ -resolvability when the given source is a mixed memoryless source. We extend the result to the second-order case. As a byproduct, we obtain the first-order and second-order formulas for fixed-to-variable length source coding allowing error probability up to δ.

A decision criterion called LR+Th for decision feedback scheme was proposed by Hashimoto. Though Forney’s decision criterion (FR) is optimal and meets the Neyman-Pearson’s lemma, LR+Th is suboptimal. However, the error exponent of LR+Th is shown to be asymptotically equivalent to that of FR by random coding arguments for block codes. In this paper, applying the technique of DS2 bound, we derive an upper bound for the error probability of LR+Th with the ensemble of linear block codes. It elucidates the relation between the random coding exponents of block codes and those of linear block codes.

The variable-length source coding with unequal cost allowing error probability is considered for general sources. In this setting, the first- and second-order optimum mean codeword cost have already been determined. On the other hand, we focus on the overflow probability of codeword cost and determine the general formulas of the first- and second-order optimum achievable overflow threshold. We also apply our general formulas to the stationary memoryless source.

This paper shows some new results for the problem of variable-length lossy source coding. We deal with the case where both the excess distortion probability and the overflow probability of codeword lengths are less than or equal to positive constants. Our previous study for the problem of variable-length (noiseless) lossy source coding has derived the general formula of the infimum of the thresholds on the overflow probability by using the quantity based on the smooth max entropy. This study extends this result in two directions. First, we derive the single-letter characterization of the infimum of the thresholds on the overflow probability for stationary memoryless sources. Second, for the problem of variable-length noisy lossy source coding, also known as the problem of remote lossy source coding, we establish the general nonasymptotic formula on the converse bound by using the new quantity based on the smooth max entropy.

A binary-input, memoryless channel with a continuous-valued output quantized to one bit is considered. For arbitrary noise models, conditions on an optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output, are given. This result is obtained by considering the “backward” channel and applying Burshtein et al.'s theorem on optimal classification. In this backward channel, there exists an optimal quantizer for which the quantizer preimage is convex. It is possible no optimal forward quantizer is convex, but by working with the backward channel, the optimal quantizer may be found. However, if the channel satisfies a certain condition, then a convex optimal forward quantizer exists.

This paper investigates the problem of variable-length lossy source coding. We deal with the case where both the excess distortion probability and the overflow probability of codeword length are less than or equal to positive constants. The infimum of the thresholds on the overflow probability is characterized by a smooth max entropy-based quantity. Both non-asymptotic and asymptotic cases are analyzed. To show the achievability results, we do not utilize the random coding argument but give an explicit code construction.

In the problem of channel resolvability, where a given output probability distribution via a channel is approximated by transforming the uniform random numbers, characterizing the asymptotically minimum rate of the size of the random numbers, called the channel resolvability, has been open. This paper derives formulas for the channel resolvability for a given general source and channel pair. We also investigate the channel resolvability in an optimistic sense. It is demonstrated that the derived general formulas recapture a single-letter formula for the stationary memoryless source and channel. When the channel is the identity mapping, the established formulas reduce to an alternative form of the spectral sup-entropy rates, which play a key role in information spectrum methods.

We introduce the problem of variable-length source resolvability, where a given target probability distribution is approximated by encoding variable-length uniform random numbers, and the asymptotically minimum average length rate of the uniform random numbers, called the (variable-length) resolvability, is investigated. We first analyze the variable-length resolvability with the variational distance as an approximation measure. We then extend the analysis to the case under the divergence as an approximation measure. When the asymptotically exact approximation is required, it is shown that the resolvability under the two kinds of approximation measures coincides. We also analyze the second-order variable-length resolvability.

The variable-length coding problem allowing the error probability up to some constant is considered for general sources. In this problem, we focus on the overflow (or excess codeword length) probability We also consider another expression of our general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem.

We consider a new concept of achievability in the variable-length lossy source coding on the basis of the probability of the union of the overflow of codeword length and the excess distortion. In this setting, our main concern is to determine the achievable rate-distortion region for a given source and distortion measure. To this end, we first derive non-asymptotic upper and lower bounds, and then we derive general formulas of this achievable rate-distortion region in the first- and second-order sense. Finally, we apply our general formulas to stationary memoryless sources with an additive distortion measure.

This paper investigates the first- and second-order maximum achievable rates of codes with/without cost constraints for mixed channels whose channel law is characterized by a general mixture of (at most) uncountably many stationary and memoryless discrete channels. These channels are referred to as mixed memoryless channels with general mixture and include the class of mixed memoryless channels of finitely or countably memoryless channels as a special case. For the mixed memoryless channels with general mixture, the first-order coding theorem which gives a formula for the ε-capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios.

This paper deals with a fixed-length lossy source coding problem with some excess distortion probability called the source coding problem with ε-fidelity criterion. In this problem, the rate-distortion function and the distortion-rate function have already been characterized for i.i.d. sources with an additive distortion measure in the sense of first-order and second-order coding rates. However, general formulas for these functions have not been revealed up to present. Hence, in this paper we derive general formulas for the rate-distortion function and the distortion-rate function with the ε-fidelity criterion in both of the first-order and second-order cases. A relationship between our general formulas and previous results are also discussed.

This paper studies the first- and second-order maximum achievable rates of codes with/without cost constraints for general mixed channels whose channel law is characterized by a mixture of uncountably many stationary and memoryless discrete channels. These channels are referred to as general mixed memoryless channels and include mixed memoryless channels of finitely or countably many memoryless channels as a special case. For general mixed memoryless channels, the first-order coding theorem which gives a formula for the ε-capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of general mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios.

This paper addresses two problems of variablelength coding with a fidelity criterion for general sources, in which either the probability of codeword length overflow or that of excess distortion for a given threshold is allowed up to ε. In each problem, a general formula for the achievable region of coding rates and distortion levels is established via information spectrum methods. It is shown that there is a tight connection between the two problems, and the achievable regions are the same under a mild condition on the distortion measure. As a consequence, it turns out that superficially different general formulas for the two coding problems coincide with each other.

For the class of mixed channels decomposed into stationary memoryless channels, single-letter characterizations of the ε-capacity have not been known except for restricted classes of channels such as the regular decomposable channel introduced by Winkelbauer. This paper gives single-letter characterizations of ε-capacity for mixed channels decomposed into at most countably many memoryless channels with a finite input alphabet with/without cost constraints. It is shown that the given characterization reduces to the one for the channel capacity given by Ahlswede when ε is zero. Some properties of the function of the ε-capacity are analyzed.

The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. An algorithm, which finds an optimal quantizer, in the sense of maximizing mutual information between the channel input and quantizer output is given. This result holds for arbitrary channels, in contrast to previous results for restricted channels or a restricted number of quantizer outputs. In the worst case, the algorithm complexity is cubic M3in the number of channel outputs M. Optimality is proved using the theorem of Burshtein, Della Pietra, Kanevsky, and Nádas for mappings, which minimize average impurity for classification and regression trees.

For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.

The problem of finding the optimum output quantizer for a given discrete memoryless channel is investigated, where the quantizer output has fewer values than the channel output. While mutual information has received attention as an objective function for optimization, the focus of this paper is use of the random coding exponent, which was originally derived by Gallager, as criteria. Two problems are addressed, where one problem is a partial problem of the other. The main result is a quantizer design algorithm, and a proof that it finds the optimum quantizer in the partial problem. The quantizer design algorithm is based on a dynamic programming approach, and is an extension of a mutual-information maximization method. For the binary-input case, it is shown that the optimum quantizer can be found with complexity that is polynomial in the number of channel outputs.

Consider a binary-input, M-output discrete memoryless channel (DMC) where the outputs are quantized to K levels, with K <; M. The subject of this paper is the maximization of mutual information between the input and quantizer output, over both the input distribution and channel quantizer. This can be regarded as finding the capacity of a quantized DMC. An algorithm is given, which either finds the optimal input distribution and corresponding quantizer, or declares a failure.

In this paper, a new attack model in which the number of colluders are distributed according to a certain probability distribution is introduced. Two classes of collusion attacks which include well-known collusion attacks in the context of multimedia fingerprinting are provided. For these two attack classes, achievable rates for the unknown size of the actual colluders are derived. Based on the derived achievable rates, achieve rates for some particular attacks are investigated. For the AND attack, the bound derived in this paper coincides with the previous known bound, although the attack model in this paper does not assume that the decoder knows the actual number of colluders. Moreover, for the averaging attack, it is clarified that derived achievable rate is larger than previously known bound with random linear codes.

A simple four node network in which cooperation improves the information-theoretic secrecy is studied. The channel consists of two senders, a receiver, and an eavesdropper. One or both senders transmit confidential messages to the receiver, while the eavesdropper tries to decode the transmitted message. The main result is the derivation of a newly achievable rate-equivocation region that is shown to be larger than a rate-equivocation region derived by Lai and El Gamal for the relay-eavesdropper channel. When the rate of the helping interferer is zero, the new rate-equivocation region reduces to the capacity-equivocation region over the wire-tap channel; hence, the new achievability scheme can be seen as a generalization of a coding scheme proposed by Csiszár and Körner.

Rate-splitting, in which rates are split into smaller rates and successive decoding is used, has been developed for memoryless multiple access channels (MACs). This scheme realizes any rate in the capacity region of a MAC with decoding complexity proportional to that for single-user codes, even when time-sharing cannot be used. This paper proposes rate-splitting schemes for multiple-receiver channels, such as compound MACs and interference channels. For interference channels, rate-splitting can achieve any rate in the celebrated Han-Kobayashi rate region with low decoding complexity. Rate-splitting is particularly effective in the frame-asynchronous case, and an achievable rate region for the asynchronous IC is given.

Code construction is considered for arbitrary discrete memoryless compound multiple access channels (MACs) with common information. This class of channels includes MACs with/without common messages or with partially cooperating encoders. A construction method of code ensembles based on coset codes is proposed for these channels. Assuming joint maximum likelihood decoding, the performance of the proposed code ensemble is analyzed by deriving a lower bound on error exponents. A condition assuring that codes achieve the capacity region on average is given. It is seen that an elaborate combination of good linear codes gives capacity achieving codes for compound MACs with common messages or with partially cooperating encoders. The use of restricted ensembles with low-density parity check (LDPC) codes as component codes is also discussed. It is shown that a coset code ensemble based on nonbinary regular LDPC codes approaches the random coding exponent, and thus is capacity-achieving.

We study quantizers with lpnorm, with p ≥ 1, for the root lattices. Our algorithms extend the ones proposed by Conway and Sloane [1] with l2norm. They proposed an interesting algorithm for Anlattice, but without proof of the optimality. We give the proof of the optimality with our extended case of lpnorm. We also give an algorithm for E6and its dual, which are not described in [1].

Coding for discrete memoryless compound multiple access channels (MACs) with common information is considered. A construction method for an ensemble of MAC codes is proposed based on non-binary low-density parity check (LDPC) codes. It is shown that an overall MAC code asymptotically approaches the random coding exponent for the compound MAC with common information under joint maximum likelihood decoding. The analysis of decoding error probability shows that several regular LDPC codes which are good for a single-user channel are sufficient for achieving the random coding exponent or the capacity region for this channel.

Or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. F In the analysis of the decoding error probability, it is important to characterize the error exponent, since it indicates how fast the probability of decoding error converges to zero asymptotically. Over a symmetric memoryless channel, an error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, is given. Over a general discrete memoryless channel, the same analysis shows the expected error exponent of an ensemble of coset codes generated by a given linear code.

An iterative decoding algorithm of rate-compatible punctured low-density parity-check (RCP-LDPC) codes of high coding rates is developed. This algorithm performs a predetermined recovering process of punctured bits sums at the beginning of each iteration of the standard belief-propagation (BP) decoding algorithm. By propagating messages of two punctured bits sum, this algorithm can recover much more punctured bits than the standard BP decoding algorithm. It is shown that the proposed algorithm is applicable for RCP-LDPC codes of higher coding rates with little increase of decoding complexity.

This paper considers code construction for arbitrary discrete memoryless compound multiple access channels (MACs) with common information. This class of channels includes a MAC with/without common messages or with partially cooperating encoders. A construction method of code ensembles based on coset codes is proposed for these channels. Assuming joint maximum likelihood decoding, the performance of the proposed code ensemble is analyzed by deriving error exponents. A condition is shown such that codes achieve the capacity region on average. The result obtained here reduces to the result of Slepian and Wolf or other conventional works if restricted to a single MAC. A combination of good linear codes gives capacity achieving codes for compound MACs with common messages or with partially cooperating encoders.

This paper introduces two channel models of correlated parallel channels. Then we analyze structure of error correcting codes over these correlated parallel channels. We derive necessary and sufficient conditions for these codes and some code construction is presented. We also show some upper and lower bounds on the coding rate of the error correcting codes for correlated parallel channels. The introduced channel models are related to burst error channels and the codes analyzed in this paper can be used as asymmetric interleaving codes for burst error channels.

Digital fingerprinting, a copyright protection technique for digital contents, 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 has effect for multimedia fingerprinting. We propose new collusion-secure fingerprinting codes based on finite geometries (FGs) which increase the rate of conventional collusion-secure codes, while they guarantee to identify the same number of colluders. Due to the new FG-based fingerprinting codes, the system can deal with a larger number of users to distribute a digital content.