New nonasymptotic random coding theorems (with error probability E and finite block length n) based on Gallager parity check ensemble and general parity check ensembles are derived in this paper. The resulting nonasymptotic achievability bounds, when combined with nonasymptotic equipartition properties developed in this paper, can be easily computed. Analytically, these nonasymptotic achievability bounds are shown to be asymptotically tight up to the second order of the coding rate as n goes to infinity with either constant or subexponentially decreasing E in the case of Gallager parity check ensemble, and to imply that low density parity check (LDPC) codes be capacity-achieving in the case of LDPC ensembles. Numerically, they are also compared favorably, for finite n and E of practical interest, with existing nonasymptotic achievability bounds in the literature.

Quantization table design is revisited for image/video coding where soft decision quantization (SDQ) is considered. Unlike conventional approaches, where quantization table design is bundled with a specific encoding method, we assume optimal SDQ encoding and design a quantization table for the purpose of reconstruction. Under this assumption, we model transform coefficients across different frequencies as independently distributed random sources and apply the Shannon lower bound to approximate the rate distortion function of each source. We then show that a quantization table can be optimized in a way that the resulting distortion complies with certain behavior. Guided by this new design principle, we propose an efficient statistical-model-based algorithm using the Laplacian model to design quantization tables for DCT-based image coding. When applied to standard JPEG encoding, it provides more than 1.5-dB performance gain in PSNR, with almost no extra burden on complexity. Compared with the state-of-the-art JPEG quantization table optimizer, the proposed algorithm offers an average 0.5-dB gain in PSNR with computational complexity reduced by a factor of more than 2000 when SDQ is OFF, and a 0.2-dB performance gain or more with 85% of the complexity reduced when SDQ is ON. Significant compression performance improvement is also seen when the algorithm is applied to other image coding systems proposed in the literature.

The distributions of discrete cosine transform (DCT) coefficients of images are revisited on a per image base. To better handle, the heavy tail phenomenon commonly seen in the DCT coefficients, a new model dubbed a transparent composite model (TCM) is proposed and justified for both modeling accuracy and an additional data reduction capability. Given a sequence of the DCT coefficients, a TCM first separates the tail from the main body of the sequence. Then, a uniform distribution is used to model the DCT coefficients in the heavy tail, whereas a different parametric distribution is used to model data in the main body. The separate boundary and other parameters of the TCM can be estimated via maximum likelihood estimation. Efficient online algorithms are proposed for parameter estimation and their convergence is also proved. Experimental results based on Kullback-Leibler divergence and χ(2) test show that for real-valued continuous ac coefficients, the TCM based on truncated Laplacian offers the best tradeoff between modeling accuracy and complexity. For discrete or integer DCT coefficients, the discrete TCM based on truncated geometric distributions (GMTCM) models the ac coefficients more accurately than pure Laplacian models and generalized Gaussian models in majority cases while having simplicity and practicality similar to those of pure Laplacian models. In addition, it is demonstrated that the GMTCM also exhibits a good capability of data reduction or feature extraction-the DCT coefficients in the heavy tail identified by the GMTCM are truly outliers, and these outliers represent an outlier image revealing some unique global features of the image. Overall, the modeling performance and the data reduction feature of the GMTCM make it a desirable choice for modeling discrete or integer DCT coefficients in the real-world image or video applications, as summarized in a few of our further studies on quantization design, entropy coding design, and image understanding and management.

Motivated by communication through a network employing linear network coding, capacities of linear operator channels (LOCs) with arbitrarily distributed transfer matrices over finite fields are studied. Both the Shannon capacity C and the subspace coding capacity CSSare analyzed. By establishing and comparing lower bounds on C and upper bounds on CSS, various necessary conditions and sufficient conditions such that C = CSSare obtained. A new class of LOCs such that C = CSSis identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that CSSis strictly less than C for a broad class of LOCs. In general, an optimal subspace coding scheme is difficult to find because it requires to solve the maximization of a nonconcave function. However, for an LOC with a unique subspace degradation, CSScan be obtained by solving a convex optimization problem over rank distribution. Classes of LOCs with a unique subspace degradation are characterized. Since LOCs with uniform-given-rank transfer matrices have unique subspace degradations, some existing results on LOCs with uniform-given-rank transfer matrices are explained from a more general way.

This paper tackles the constellation and channel coding rate selection problem in adaptive modulation and coding (AMC) for MIMO systems. Based on information theoretical results in finite blocklength analysis of channel capacity, a new selecting rule is proposed for narrow-band MIMO systems, and further extended to wide-band MIMO OFDM systems over channels subject to frequency-selective fading. When applied to Long Term Evolution (LTE) systems, the proposed selecting rule yields better performance in comparison with existing rules in the literature.

Quantization table design is revisited for image/video coding where soft decision quantization (SDQ) is considered. Unlike conventional approaches where quantization table design is bundled with a specific encoding method, we assume optimal SDQ encoding and design a quantization table for the purpose of reconstruction. Under this assumption, we model transform coefficients across different frequencies as independently distributed random sources and apply the Shannon lower bound to approximate the rate distortion function of each source. We then show that a quantization table can be optimized in a way that the resulting distortion complies with certain behavior. Lastly, guided by this new theoretical result, we propose an efficient statistical-model-based algorithm using the Laplacian model to design quantization tables for JPEG encoding. Compared with the state of the art, the proposed algorithm provides an average 0.5 dB gain in PSNR with computational complexity reduced by a factor of more than 2000 when SDQ is off, and a 0.1 dB performance gain with 85% of the complexity reduced when SDQ is on.

In this paper, the problem of constellation and rate selection in adaptive modulation and coding according to the channel condition is considered. A new selecting rule based on the finite blocklength analysis of channel capacity is proposed. When applied to the LTE system, the proposed selecting rule reveals interesting, new combinations of constellation and rate which yield significantly better performance in comparison with corresponding combinations suggested in the LTE system.

Interactive encoding and decoding based on binary low-density parity-check codes with syndrome accumulation (SA-LDPC-IED) is proposed and investigated. Assume that the source alphabet isGF(2), and the side information alphabet is finite. It is first demonstrated how to convert any classical universal lossless codeCn(with block lengthnand side information available to both the encoder and decoder) into a universal SA-LDPC-IED scheme. It is then shown that with the word error probability approaching 0 subexponentially withn, the compression rate (including both the forward and backward rates) of the resulting SA-LDPC-IED scheme is upper bounded by a functional of that ofCn, which in turn approaches the compression rate ofCnfor each and every individual sequence pair (xn,yn) and the conditional entropy rate H (X|Y) for any stationary, ergodic source and side information (X,Y) as the average variable node degreel̅of the underlying LDPC code increases without bound. When applied to the class of binary source and side information (X,Y) correlated through a binary symmetrical channel with crossover probability unknown to both the encoder and decoder, the resulting SA-LDPC-IED scheme can be further simplified, yielding even improved rate performance versus the bit error probability whenl̅is not large. Simulation results (coupled with linear time belief propagation decoding) on binary source-side information pairs confirm the theoretic analysis and further show that the SA-LDPC-IED scheme consistently outperforms the Slepian-Wolf coding scheme based on the same underlying LDPC code. As a by-product, probability bounds involving LDPC established in the course are also interesting on their own and expected to have implications on the performance of LDPC for channel coding as well.

Recently, a new decoding rule called jar decoding was proposed, under which the decoder first forms a set of suitable size, called a jar, consisting of sequences from the channel input alphabet considered to be closely related to yn, and then takes any codeword from the jar as the estimate of the transmitted codeword. In this paper, we show that under jar decoding, the analysis of low density parity check (LDPC) codes is much easier compared to maximum a posteriori (MAP) or maximum likelihood (ML) and Belief Propagation (BP) decoding, and new general LDPC coding theorems can be established. Specifically, it is proved that LDPC codes can approach the mutual information, with diminishing bit error probability, of any binary input memoryless channel with uniform input distribution when the average variable node degree is large. Moreover, simulation shows an interesting connection between jar decoding and BP decoding, i.e., BP decoding can be regarded as one of many ways to pick up a codeword from the jar for LDPC codes when it succeeds in outputting a codeword.

Interactive encoding and decoding with tree decoding (referred to simply as tree interactive encoding and decoding (TRIED)) is considered for the problem of lossless source coding with decoder only side information. A TRIED scheme is proposed and demonstrated that when applied to encode any conditionally Φ-mixing source of length n, its error probability decays polynomially with respect to n, average rate is around conditional entropy rate, and average computational complexity of encoding and decoding is O(n ln n).

Linear interactive encoding and decoding (IED) for near lossless source coding with decoder only side information is considered, where the interactive encoder uses linear codes (described by parity-check matrices over a finite fieldX) for encoding. It is first demonstrated how to convert any classical universal lossless codeCn(with block lengthnand with side information available to both the encoder and decoder) into a universal random linear IED scheme based on Gallager's parity check ensemble. It is then shown that there is no performance loss by restricting IED to linear IED, and that the universal random linear IED scheme based on Gallager's parity check ensemble achieves essentially the same rate performance as doesCnfor each and every individual sequence pair (xn,yn) while the word decoding error probability goes to 0 asn→ ∞ . Define the density of a linear IED scheme as the percentage of nonzero entries in its parity-check matrix. To reduce the encoding complexity of linear IED, low density linear IED is further investigated in terms of the trade-off among its rate, decoding error probability, and density.

The concept of error exponent to redundancy ratio (EERR) of interactive encoding and decoding (IED), as well as Slepian-Wolf coding (SWC), is defined and investigated in this paper. The EERR of universal IED is determined. In the non-universal coding case, it is shown that for any stationary ergodic source-side information pair, a two stage IED scheme with 3 rounds of interactions or less can be constructed such that its EERR ≥1. Meanwhile, for any memoryless source-side information pair, the EERR of SWC is strictly less than 1 in the region where the error exponent of SWC is determined. Furthermore, practical two stage IED schemes are proposed and implemented by using LDPC codes and Belief Propagation (BP) Decoding, and simulation shows that the error probability of the proposed two stage IED schemes is indeed significantly lower than that of SWC schemes.

Linear operator channels (LOCs) are motivated by the communications through networks employing random linear network coding (RLNC). Following the recent information theoretic results about LOCs, we propose two coding schemes for LOCs and evaluate their performance. These schemes can be used in networks employing RLNC without constraints on the network size and the field size. Our first scheme makes use of rank-metric codes and generalizes the rank-metric approach of subspace coding proposed by Silva et al. Our second scheme applies linear coding. The second scheme can achieve higher rate than the first scheme, while the first scheme has simpler decoding algorithm than the second scheme. Our coding schemes only require the knowledge of the expectation of the rank of the transformation matrix. The second scheme can also be realized ratelessly without any priori knowledge of the channel statistics.