The class of$k$-symbol delay decodable code-tuples is a set of noiseless source codes, which can achieve an average codeword length less than or equal to that of Huffman codes by utilizing a finite number of code tables and allowing a decoding delay of at most$k$coding symbols. This paper establishes a lower bound of the worst-case redundancy of$d$-ary$k$-symbol delay decodable code-tuples for$d \geq 2, k \geq 1$by proving a stronger theorem that provides a lower bound of the average codeword length.

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.

For an integer$k \geq 0$, k-bit delay decodable code-tuples are source codes that use a finite number of code tables and allow a decoding delay of at most k bits. It is known that the class of k-bit delay decodable code-tuples can achieve a better average codeword length than Huffman codes for$k \geq 2$. However, it is generally challenging to find an optimal k-bit delay decodable code-tuple (i.e., a k-bit delay decodable code-tuple achieving the optimal average codeword length among all k-bit delay decodable code-tuples) because the class of k-bit delay decodable code-tuples is a comprehensive and flexible class containing a variety of source code consisting of any finite number of code tables. AIFV (almost instantaneous fixed-to-variable length) codes are 2-bit delay decodable code-tuples consisting of two code tables satisfying certain constraints. This paper proves that the class of AIFV codes always contains an optimal 2-bit delay decodable code-tuple for any given source distribution. Thus, we can find an optimal 2-bit delay decodable code-tuple in the class of 2-bit delay decodable code-tuples by considering only the class of AIFV codes, which is a very restricted subclass compared to the whole class of 2-bit delay decodable code-tuples.

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.

Huffman code is the optimal code in the class of uniquely decodable codes in the sense of the average length of codeword when a single code tree can represent the code. This paper defines hierarchical subclasses of noiseless source codes by allowing$k$-bit decoding delay for positive integer$k$and clarifies a necessary and sufficient condition for the uniquely decodable codes with$k$-bit decoding delay. Furthermore, we show that AIFV code is the optimal code in the class of uniquely decodable codes with 2-bit decoding delay when two code trees represent the noiseless source code.

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.

This study proposes modular arithmetic erasure channels (MAECs), a novel class of erasure-like channels with an input alphabet that need not be binary. This class contains the binary erasure channel (BEC) and some other known erasure-like channels as special cases. For MAECs, we provide recursive formulas of Arıkan-like polar transform to simulate channel polarization. In other words, we show that the synthetic channels of MAECs are equivalent to other MAECs. This is a generalization of well-known recursive formulas of the polar transform for BECs. Using our recursive formulas, we also show that a recursive application of the polar transform for MAECs results in multilevel channel polarization, which is an asymptotic phenomenon that is characteristic of non-binary polar codes. Specifically, we establish a method to calculate the limiting proportions of the partially noiseless and noisy channels that are generated as a result of multilevel channel polarization for MAECs. In the particular case of MAECs, this calculation method solves an open problem posed by Nasser (2017) in the study of non-binary polar codes.

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.

Polar transforms are central operations in the study of polar codes. This paper examines polar transforms for non-stationary memoryless sources on possibly infinite source alphabets. This is the first attempt of source polarization analysis over infinite alphabets. The source alphabet is defined to be a Polish group, and we handle the Arikan-style two-by-two polar transform based on the group. Defining erasure distributions based on the normal subgroup structure, we give recursive formulas of the polar transform for erasure distributions. We then show concrete examples of multilevel source polarization with countably infinite levels when the group is locally cyclic. We derive this result via elementary techniques in lattice theory.

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.

This study considers a problem of finding an optimal approximation of conditional information measures, like the conditional entropy, of a Bernoulli random variable (RV) given an auxiliary RV. We define an optimality of the problem in terms of the data-processing lemma of conditional information measures; and the problem aims to create an optimal auxiliary RV through partial orders of auxiliary RVs for a given RV. We describe an optimal upgradation algorithm by dynamic programming. Proving a Monge property of the dynamic programming, we describe speeding-up method of the algorithm by applying SMAWK algorithm.

This study examines multilevel channel polarization for a certain class of erasure channels with arbitrary input alphabet size. We derive limiting proportions of partially noiseless channels for such a class. One of the results of this study are proved by an argument of convergent sequences, inspired by Alsan and Telatar's simple proof of polarization [IEEE Transactions on Information Theory, vol. 62, no. 9, pp. 4873-4878, 2016], and without martingale convergence theorems for polarization process. Technical parts of this study can be found in the arXiv at [https://arxiv.org/abs/1801.04422].

This paper examines the exact ranges between the symmetric capacity and Gallager's reliability function E0for ternary-input discrete memoryless channels (T-DMCs) under a uniform input distribution. We first derive the two extremal ternary-input strongly symmetric channels taking the maximum and minimum values of the E0function among all ternary-input strongly symmetric channels with a fixed capacity. Extending the results of ternary-input strongly symmetric channels, we second derive the exact ranges between capacity and the E0function for ternary-input Gallager-symmetric channels. We third show that the exact ranges between the symmetric capacity and the E0function of T-DMCs coincide with the ranges of ternaryinput Gallager-symmetric channels. In particular, we identify the extremal channels taking the maximum and minimum of E0among all T-DMCs with a fixed symmetric capacity. As applications of the results, we describe some bounds of error exponents for T-DMCs with a fixed symmetric capacity.

This study examines quantization for outputs of binary-input discrete memoryless channels (B-DMCs) by concatenating its output with another DMC, so-called a quantizer. As an objective function of channel quantization, we employ the α-mutual information of a B-DMC, which connects to more powerful coding theorem than the ordinary mutual information. Showing a Monge property of the α-mutual information, we propose an optimal quantizer design algorithm for given B-DMC in polynomial time complexity with respect to the output alphabet size and the quantized level. Since the proposed method employs the SMAWK algorithm due to the Monge property, our algorithm is faster than a naive dynamic programming.

This study examines sharp bounds on Arimoto's conditional Rényi entropy of order β with a fixed another one of distinct order α ≠ β. Arimoto inspired the relation between the Rényi entropy and the ℓr-norm of probability distributions, and he introduced a conditional version of the Rényi entropy. From this perspective, we analyze the ℓr-norms of particular distributions. As results, we identify specific probability distributions which achieve our sharp bounds on the conditional Rényi entropy. The sharp bounds derived in this study can be applicable to other information measures which are strictly monotone functions of the conditional Rényi entropy.

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.

The paper examines relationships between the conditional Shannon entropy and the expectation of ℓα-norm for joint probability distributions. More precisely, we investigate the sharp bounds of the expectation of ℓα-norm with a fixed conditional Shannon entropy, and vice versa. As applications of the results, we derive the sharp bounds between the conditional Shannon entropy and several information measures which are determined by the expectation of ℓα-norm, e.g., Arimoto's conditional Rényi entropy and the conditional R-norm information. Moreover, we apply these results to discrete memoryless channels under a uniform input distribution. Then, sharp bounds are obtained for Gallager's reliability functions E0with a fixed mutual information under a uniform input distribution.

The polar transform of a binary erasure channel (BEC) can be exactly approximated by other BECs. Arikan proposed that polar codes for a BEC can be efficiently constructed by using its useful property. This study proposes a new class of arbitrary input generalized erasure channels, which can be exactly approximated the polar transform by other same channel models, as with the BEC. One of the main results is the recursive formulas of the polar transform of the proposed channel. In the study, we evaluate the polar transform by using the α-mutual information. Particularly, when the input alphabet size is a prime power, we examines the following: (i) inequalities for the average of the α-mutual information of the proposed channel after the one-step polar transform, and (ii) the exact proportion of polarizations of the α-mutual information of proposed channels in infinite number of polar transforms.

Dube and Beaudoin have proposed a technique of lossless data compression called compression via substring enumeration (CSE) for a binary source alphabet. Dube and Yokoo proved that CSE has a linear complexity both in time and in space worst-case performance for the length of string to be encoded. Dubé and Yokoo have specified appropriate predictors of the uniform and combinatorial prediction models for CSE, and proved that CSE has the asymptotic optimality for stationary binary ergodic sources. Our previous study evaluated the worst-case maximum redundancy of the modified CSE for an arbitrary binary string from the class of k-th order Markov sources. We propose a generalization of CSE for k-th order Markov sources with a finite alphabet X based on Ota and Morita in this study.

In the refinement of a channel coding theorem, error exponents characterize the exponential convergence rates of decoding error probabilities. Error exponents are sometime called as reliability functions. In this study, we consider analyzing the reliability functions based on Gallager's E0function. The region of the E0function of binary-input memoryless and symmetric channels for a fixed capacity was clarified by Guillén i Fàbregas et al. in their 2013 study. More precisely, binary erasure and binary symmetric channels have maximal and minimal E0functions, respectively, among the binary-input memoryless and symmetric channels for a fixed capacity. In this study, we extend their results from binary- to ternary-input channels that are not necessarily symmetric. First, we identify the extreme channels among the ternary-input strongly symmetric channels. Next, we identify the extreme channels among the ternary-input memoryless and symmetric channels. In addition, using channel symmetrization, we investigate whether the feasible regions of symmetric capacity and the E0functions for discrete memoryless channels (DMCs) are identical to those for symmetric channels if the channel inputs follow a uniform distribution. We describe the feasible regions for ternary-input DMCs under a uniform input distribution. In particular, we reveal the channels with maximal E0function among ternary-input DMCs for a fixed symmetric capacity and uniform input distribution.

The quantizer design algorithm was recently proposed by Kurkoski and Yagi for arbitrary binary-input discrete memoryless channels using dynamic programming. This study proposes an improvement of the time complexity of the quantizer design algorithm using the SMAWK algorithm for arbitrary binary-input discrete memoryless channels.

We consider a situation where n-tuples generated from a general source are encoded by a fixed-length code and discuss coding theorems on the worst-case redundancy, where the worst-case redundancy is defined as the maximum of the difference between the rate and the ideal codeword length per symbol with respect to all the correctly decodable n-tuples. We treat the four cases where the decoding error probability εnis required to satisfy (a) limn→∞εn= 0, (b) lim infn→∞εn= 0, (c) lim supn→∞εn≤ ε, and (d) lim infn→∞εn≤ ε, respectively, where ε ∈ [0; 1) is an arbitrary constant. We give general formulas of the optimum worst-case redundancy that are closely related to the width of the entropy-spectrum of a source.

This paper is concerned with the redundancy rate of fixed length source code for a general source with a countably infinite alphabet. We evaluate the minimum achievable redundancy rate R of fixed-to-fixed length (FF) and variable-to-fixed length (VF) codes with two definitions of redundancy rates, which are (i) the difference between the coding rate and the spectral sup-entropy rate and (ii) the difference between the coding rate and the self information rate. First we show that, when we restrict the fixed-length code class within the class of FF codes, R with definition (i) is zero, but R with definition (ii) can be positive. Next we show that, by taking the VF codes into account, R with definition (ii) can be decreased to zero.

This paper investigates the minimum achievable redundancy rate of fixed-to-fixed length lossless source codes (FF codes) for general sources. This paper defines the redundancy rate of the FF code by the difference between the coding rate and the self information rate. We prove that the minimum achievable redundancy rate is equal to the limit superior in probability of the width of the information spectrum, which is defined in this paper. This paper also considers the ε-source coding. We show two criteria for bounding the error probability. The first one bounds the sum of the decoding error probability and the redundancy-overflow probability, and the other one bounds these two probabilities separately. We also give the minimum achievable redundancy rate of these two types of ε-source coding.

We consider a problem to build good prefix-free code for the transmission of a stationary memoryless source across a finite-state noiseless channel with unequal symbol costs. Our scheme is an improvement of Golin and Rote's algorithm for constructing good prefix-free codes to the state dependent noiseless channel case by removing an assumption that channel has only one state. As an application of our scheme, we suggest better codes to minimize the expected cost for given discrete memoryless sources and the run-length coding with (d, k)-constrained noiseless channel.

Summary form only given. M. Crochemore et al. introduced a two-pass lossless data compression scheme called data compression using antidictionaries (DCA) (see Proc. IEEE, vol.88, no.11, p.1756-68, 2000). DCA finds some words (minimal forbidden words) that never appear in the text to be compressed, and chooses a subset of minimal forbidden words as an antidictionary (AD). We develop improved DCAs in two ways. (1) We propose an improved DCA using, instead of the AD, predictable dictionaries made up of the words whose last symbols are uniquely determined by their prefixes. The good properties of the original DCA hold in this extension. (2) We present an algorithm to construct the AD (or predictable dictionary) by using a suffix array of the text. We can reduce the amount of memory necessary to construct an AD by using the suffix array. Moreover, by applying a suffix array instead of a suffix tree, we can exploit the relationship between the suffix array and the BWT (Burrows-Wheeler transform), giving us the chance of choosing between DCA and the Burrows-Wheeler compression algorithm (BWCA).

The problem of minimizing an L/sub 2/-sensitivity measure subject to L/sub 2/-norm dynamic-range scaling constraints for state-space digital filters is considered. A novel iterative technique is developed to solve the constraint optimization problem directly. The proposed solution method is largely based on the use of a Lagrange function and some matrix-theoretic techniques. Computer simulation results are also presented to demonstrate the effectiveness of the proposed technique.

This paper revisits a multiple-access communication system for correlated sources with an array of independent channels in view of information spectrum method, and characterizes new necessary and sufficient conditions for the separation theorem holds for general class of sources and channels. This result increases the understanding of the source-channel separation theorem. Moreover, this theorem has not only theoretical, but also has a practical aspect, because the separation principle of this paper can divide communication systems for sending correlated sources over an array of independent channels into general correlated source coding subsystems and general channel coding subsystems. We also provide the necessary and sufficient conditions for the transmission of general correlated sources over general MAC by using the information spectrum method.