Although it is traditionally believed that lossy image compression, such as JPEG compression, has a negative impact on the performance of deep neural networks (DNNs), it is shown by recent works that well-crafted JPEG compression can actually improve the performance of deep learning (DL). Inspired by this, we propose JPEG-DL, a novel DL framework that prepends any underlying DNN architecture with a trainable JPEG compression layer. To make the quantization operation in JPEG compression trainable, a new differentiable soft quantizer is employed at the JPEG layer, and then the quantization operation and underlying DNN are jointly trained. Extensive experiments show that in comparison with the standard DL, JPEG-DL delivers significant accuracy improvements across various datasets and model architectures while enhancing robustness against adversarial attacks. Particularly, on some fine-grained image classification datasets, JPEG-DL can increase prediction accuracy by as much as 20.9%. Our code is available on https://github.com/AhmedHussKhalifa/JPEG-Inspired-DL.git.

Dataset distillation (DD) aims to minimize the time and memory consumption needed for training deep neural networks on large datasets, by creating a smaller synthetic dataset that has similar performance to that of the full real dataset. However, current dataset distillation methods often result in synthetic datasets that are excessively difficult for networks to learn from, due to the compression of a substantial amount of information from the original data through metrics measuring feature similarity, e,g., distribution matching (DM). In this work, we introduce conditional mutual information (CMI) to assess the class-aware complexity of a dataset and propose a novel method by minimizing CMI. Specifically, we minimize the distillation loss while constraining the class-aware complexity of the synthetic dataset by minimizing its empirical CMI from the feature space of pre-trained networks, simultaneously. Conducting on a thorough set of experiments, we show that our method can serve as a general regularization method to existing DD methods and improve the performance and training efficiency.

Inverse problems such as inpainting, deblurring, and super-resolution benefit significantly from generative diffusion models, which serve as powerful learned priors. However, incorporating measurement-consistency gradients naively can push the intermediate solutions off the high-likelihood manifold encoded by the diffusion model, leading to artifacts or suboptimal reconstructions. In this paper, we propose a scorebased manifold projection framework that leverages the internal score function of the diffusion model itself to preserve manifold fidelity. Specifically, we exploit the fact that the diffusion score$\boldsymbol{s}_{\theta}(\boldsymbol{x}, t) \approx \nabla_{\boldsymbol{x}} \log p_{t}(\boldsymbol{x})$is ideally orthogonal to manifolds of constant log-likelihood at time$t$. By removing the component of the measurement gradient parallel to$\boldsymbol{s}_{\theta}$, our method constrains each update to remain (to first order) tangent to the learned data manifold. Theoretically, we prove that our approach preserves proximity to the manifold more effectively than an un-projected update, and empirically, we demonstrate improved robustness and quality on various inverse problems, including deblurring, inpainting, and super-resolution. Our results show that scorebased manifold projection not only reduces artifacts but also maintains the fidelity of the reconstructions, offering a simple yet effective enhancement to measurement-guided diffusion solvers.

Inverse problems are prevalent across various disciplines in science and engineering. In the field of computer vision, tasks such as inpainting, deblurring, and super-resolution are commonly formulated as inverse problems. Recently, diffusion models (DMs) have emerged as a promising approach for addressing noisy linear inverse problems, offering effective solutions without requiring additional task-specific training. Specifically, with the prior provided by DMs, one can sample from the posterior by finding the likelihood. Since the likelihood is intractable, it is often approximated in the literature. However, this approximation compromises the quality of the generated images. To overcome this limitation and improve the effectiveness of DMs in solving inverse problems, we propose an information-theoretic approach. Specifically, we maximize the conditional mutual information$\mathrm{I}\left(x_{0}; y \mid x_{t}\right)$, where$x_{0}$represents the reconstructed signal,$y$is the measurement, and$x_{t}$is the intermediate signal at stage$t$. This ensures that the intermediate signals$x_{t}$are generated in a way that the final reconstructed signal$x_{0}$retains as much information as possible about the measurement$y$. We demonstrate that this method can be seamlessly integrated with recent approaches and, once incorporated, enhances their performance both qualitatively and quantitatively.

Although large language models (LLMs) have demonstrated remarkable capabilities in recent years, the potential of information theory (IT) to enhance LLM development remains underexplored. This paper introduces the information theoretic principle of Conditional Mutual Information (CMI) to LLM fine-tuning for classification tasks, exploring its promise in two main ways: minimizing CMI to improve a model's standalone performance and maximizing CMI to enhance knowledge distillation (KD) for more capable student models. To apply CMI in LLM fine-tuning, we adapt the recently proposed CMI-constrained deep learning framework, which was initially developed for image classification, with some modification. By minimizing CMI during LLM fine-tuning, we achieve superior performance gains on 6 of 8 GLUE classification tasks compared to BERT. Additionally, maximizing CMI during the KD process results in significant performance improvements in 6 of 8 GLUE classification tasks compared to DistilBERT. These findings demonstrate CMI's adaptability for optimizing both standalone LLMs and student models, showcasing its potential as a robust framework for advancing LLM fine-tuning. Our work bridges the gap between information theory and LLM development, offering new insights for building high-performing language models.

Deep learning (DL) often achieves success at the cost of large model sizes and high computational complexity, making training and inference challenging in resource-limited environments. To address this, we introduce coded deep learning (CDL), a framework that integrates information-theoretic coding concepts into DL to compress model weights and activations, reduce computational complexity, and enable efficient model/data parallelism. Specifically, CDL: (i) introduces a probabilistic quantization method for model weights and activations, including a differentiable variant for gradient computation; (ii) executes both forward and backward passes on quantized values, significantly reducing floating-point operations and training complexity; (iii) enforces entropy constraints on weights and activations, ensuring compressibility throughout training and lowering communication costs in distributed settings; and (iv) produces a quantized model by default, reducing post-training inference and storage complexity. Extensive experiments demonstrate that CDL outperforms state-of-the-art DNN compression methods.

Inverse problems, where the goal is to recover an unknown signal from noisy or incomplete measurements, are central to applications in medical imaging, remote sensing, and computational biology. Diffusion models have recently emerged as powerful priors for solving such problems. However, existing methods either rely on projection-based techniques that enforce measurement consistency through heuristic updates, or they approximate the likelihood $p(\boldsymbol{y} \mid \boldsymbol{x})$, often resulting in artifacts and instability under complex or high-noise conditions. To address these limitations, we propose a novel framework called coupled data and measurement space diffusion posterior sampling (C-DPS), which eliminates the need for constraint tuning or likelihood approximation. C-DPS introduces a forward stochastic process in the measurement space $\{\boldsymbol{y}_t\}$, evolving in parallel with the data-space diffusion $\{\boldsymbol{x}_t\}$, which enables the derivation of a closed-form posterior $p(\boldsymbol{x}_{t-1} \mid \boldsymbol{x}_t, \boldsymbol{y}_{t-1})$. This coupling allows for accurate and recursive sampling based on a well-defined posterior distribution. Empirical results demonstrate that C-DPS consistently outperforms existing baselines, both qualitatively and quantitatively, across multiple inverse problem benchmarks.

In knowledge distillation (KD), a lightweight student model yields enhanced test accuracy by mimicking the behaviour of a pre-trained large model (teacher). However, the cumbersome teacher model often makes over-confident responses, resulting in poor generalization when presented with unseen data. Consequently, a student trained by such a teacher also inherits this problem. To mitigate this issue, in this paper, we present a new framework of KD dubbed coded knowledge distillation (CKD) in which the student is trained to mimic instead the behaviour of a coded teacher. Compared to the teacher in KD, the coded teacher in CKD has an additional adaptive encoding layer in the front, which adaptively encodes an input image into a compressed version (using JPEG encoding for instance) and then feeds the compressed input image to the pre-trained teacher. Comprehensive experimental results show the effectiveness of CKD over KD. In addition, we extend the deployment of a coded teacher to other knowledge transfer methods, showcasing its ability to enhance test accuracy across these methods.

The success of deep learning (DL) is often achieved at the expense of large model sizes and high computational complexity during both training and post-training inferences, making it difficult to train and run large models in a resource-limited environment. To alleviate these issues, this paper introduces a new framework dubbed “coded deep learning” (CDL), which integrates information-theoretic coding concepts into the inner workings of DL, aiming to substantially compress model weights and activations, reduce computational complexity at both training and post-training inference stages, and enable efficient model/data parallelism. Specifically, within CDL, (i) we first propose a novel probabilistic method for quantizing both model weights and activations, and its soft differentiable variant which offers an analytic formula for gradient calculation during training; (ii) both the forward and backward passes during training are executed over quantized weights and activations, which eliminates a majority of floating-point operations and reduces the training computation complexity; (iii) during training, both weights and activations are entropy constrained so that they are compressible in an information-theoretic sense at any stage of training, which in turn reduces communication costs in cases where model/data parallelism is adopted; and (iv) the trained model in CDL is by default in a quantized format with compressible quantized weights, reducing post-training inference complexity and model storage complexity. Additionally, a variant of CDL, namely relaxed CDL (R-CDL), is presented to further improve the trade-off between validation accuracy and compression at the disadvantage of full precision operation involved in forward and backward passes during training with other advantageous features of CDL intact. Extensive empirical results show that CDL and R-CDL outperform the state-of-the-art algorithms in DNN compression in the literature.

The concepts of conditional mutual information (CMI) and normalized CMI (NCMI) are introduced to measure the concentration and separation performance of a classification deep neural network (DNN) in the output probability distribution space of the DNN, where CMI and the ratio between CMI and NCMI represent the intraclass concentration and interclass separation of the DNN, respectively. By using NCMI to evaluate popular DNNs pretrained over CIFAR-100 and ImageNet in the literature, it is shown that their validation accuracies are more or less inversely proportional to their NCMI values. Based on this observation, the standard deep learning (DL) framework is further modified to minimize the standard cross entropy (CE) function subject to an NCMI constraint, yielding CMI constrained DL (CMIC-DL). A novel alternating learning algorithm is proposed to solve such a constrained optimization problem. Extensive experimental results show that DNNs trained within CMIC-DL outperform the state-of-the-art models trained within the standard DL and other loss functions in the literature in terms of both accuracy and robustness against adversarial attacks. In addition, visualizing the evolution of the learning process through the lens of CMI and NCMI is also advocated.

It is believed that in knowledge distillation (KD), the role of the teacher is to provide an estimate for the unknown Bayes conditional probability distribution (BCPD) to be used in the student training process. Conventionally, this estimate is obtained by training the teacher using maximum log-likelihood (MLL) method. To improve this estimate for KD, in this paper we introduce the concept of conditional mutual information (CMI) into the estimation of BCPD and propose a novel estimator called the maximum CMI (MCMI) method. Specifically, in MCMI estimation, both the log-likelihood and CMI of the teacher are simultaneously maximized when the teacher is trained. In fact, maximizing the teacher's CMI value ensures that the teacher can effectively capture the contextual information within the images, and for visualizing this information, we deploy Eigen-CAM. Via conducting a thorough set of experiments, we show that by employing a teacher trained via MCMI estimation rather than one trained via MLL estimation in various state-of-the-art KD frameworks, the student's classification accuracy consistently increases, with the gain of up to 3.32\%. This suggests that the teacher's BCPD estimate provided by MCMI method is more accurate than that provided by MLL method. In addition, we show that such improvements in the student's accuracy are more drastic in zero-shot and few-shot settings. Notably, the student's accuracy increases with the gain of up to 5.72\% when 5\% of the training samples are available to student (few-shot), and increases from 0\% to as high as 84\% for an omitted class (zero-shot).

As a technique to bridge logit matching and probability distribution matching, temperature scaling plays a pivotal role in knowledge distillation (KD). Conventionally, temperature scaling is applied to both teacher's logits and student's logits in KD. Motivated by some recent works, in this paper, we drop instead temperature scaling on the student side, and systematically study the resulting variant of KD, dubbed transformed teacher matching (TTM). By reinterpreting temperature scaling as a power transform of probability distribution, we show that in comparison with the original KD, TTM has an inherent Rényi entropy term in its objective function, which serves as an extra regularization term. Extensive experiment results demonstrate that thanks to this inherent regularization, TTM leads to trained students with better generalization than the original KD. To further enhance student's capability to match teacher's power transformed probability distribution, we introduce a sample-adaptive weighting coefficient into TTM, yielding a novel distillation approach dubbed weighted TTM (WTTM). It is shown, by comprehensive experiments, that although WTTM is simple, it is effective, improves upon TTM, and achieves state-of-the-art accuracy performance. Our source code is available at https://github.com/zkxufo/TTM.

Federated learning (FL) is a promising technology wherein edge devices/clients collaboratively train a machine learning model under the orchestration of a central server. However, due to the inherent data heterogeneity among clients, local datasets on individual clients often exhibit class imbalance, i.e., samples from majority classes vastly outnumber those from minority classes. This imbalance significantly diminishes the performance of the trained model. To understand why, we first closely examine the output probability distribution clusters of the local deep neural networks (DNNs) in the probability space over the label set, and observe that for class imbalanced datasets, FL has two interesting phenomena: (1) dispersion problem-clusters corresponding to minority classes tend to disperse; and (2) gravity problem-clusters corresponding to minority classes are drawn toward those of majority classes. To overcome these two problems, we then introduce information quantities into FL, propose a new information theoretic loss function for FL, and develop a new FL framework called Fed-IT. It is shown that Fed-IT significantly outperforms previous counterparts, while maintaining client privacy.

In this paper, we introduce the notions of conditional mutual information (CMI) and normalized conditional mutual information (NCMI) for classification deep neural networks (DNNs). In particular, CMI and the ratio between CMI and NCMI quantify the intra-class concentration and inter-class separation of a DNN in its output probability distribution space, respectively. Utilizing NCMI to assess widely recognized DNNs pre-trained on ImageNet reveals a notable inverse relationship between their validation accuracies and NCMI values on the ImageNet validation dataset. Building upon this insight, the conventional deep learning (DL) framework is modified by minimizing the standard cross-entropy function while imposing an NCMI constraint. This refinement results in a novel approach known as CMI-constrained deep learning (CMIC-DL). Comprehensive experimental findings demonstrate that DNNs trained using CMIC-DL outperform state-of-the-art models trained within standard DL and other loss functions in the literature. In addition, some semantic meaning of CMI is also discovered.

Conventional image compression techniques are mostly developed for the human visual system. However, with the extensive use of deep neural networks (DNNs), more and more images will be consumed by DNN-based intelligent machines, which makes it crucial to develop image compression techniques customized for DNN vision while being JPEG compliant. In this paper, we first propose a new distortion measure, dubbed the sensitivity weighted error (SWE). Then, we develop OptS, a DNN-oriented compression algorithm with full JPEG compatibility, which designs optimal quantization tables for DNN models based on SWE. To test the performance of our algorithm, experiments of image classification are conducted on the ImageNet dataset for two prevailing DNN models. Results demonstrate that our algorithm achieves better rate-accuracy (R-A) performance than the default JPEG. For some DNN model, the compression ratio of our algorithm can reach 8.3×1, reducing the compression rate (bits per pixel, bpp) of the default JPEG by 57.4% with no accuracy loss. Our source code is available at https://github.com/zkxufo/OptS.git.

This paper designs a Distributed Arithmetic Coding (DAC) decoder using the depth-first search method. In addition, a method is proposed to control the decoder complexity. Simulation results compare the DFD with the traditional Breadth-First Decoder (BFD) showing that under the same complexity constraints, the DFD outperforms the BFD when the code length is not too long and the quality of side information is not too poor.

This paper revisits the problem of rate distortion optimization (RDO) with focus on inter-picture dependence. A joint RDO framework which incorporates the Lagrange multiplier as one of parameters to be optimized is proposed. Simplification strategies are demonstrated for practical applications. To make the problem tractable, we consider an approach where prediction residuals of pictures in a video sequence are assumed to be emitted from a finite set of sources. Consequently the RDO problem is formulated as finding optimal coding parameters for a finite number of sources, regardless of the length of the video sequence. Specifically, in cases where a hierarchical prediction structure is used, prediction residuals of pictures at the same prediction layer are assumed to be emitted from a common source. Following this approach, we propose an iterative algorithm to alternatively optimize the selections of quantization parameters (QPs) and the corresponding Lagrange multipliers. Based on the results of the iterative algorithm, we further propose two practical algorithms to compute QPs and the Lagrange multipliers for the RA(random access) hierarchical video coding: the first practical algorithm uses a fixed formula to compute QPs and the Lagrange multipliers, and the second practical algorithm adaptively adjusts both QPs and the Lagrange multipliers. Experimental results show that these three algorithms, integrated into the HM 16.20 reference software of HEVC, can achieve considerable RD improvements over the standard HM 16.20 encoder, in the common RA test configuration.

Rate Distortion Optimization (RDO) is employed in the contemporary video coding standard, High Efficiency Video Coding (HEVC), to improve its coding efficiency. Due to its high complexity, RDO is generally performed with fixed quantization parameters (QPs). Fixing QPs, however, does not consider the impact of the current frame on the future frames within the temporal propagation chain, leading to suboptimal performance. To address the adaptive QP design, in this paper, we first estimate the propagation length that is defined as the impact length of the current unit on future units. Based on this impact length, we then propose an adaptive frame-level QP selection algorithm for the low-delay (LD) HEVC standard. Compared to the default HEVC, our method performs significantly better by achieving -4.71% and -3.93% BD-rate gains for LDP and LDB configurations of HEVC, respectively, at a negligible increase in time overhead.

High Efficiency Video Coding (HEVC) improves rate distortion (RD) performance significantly, but at the same time is computationally expensive due to the adoption of a large variety of coding unit (CU) sizes in its RD optimization. In this paper, we investigate the application of fully connected neural networks (NNs) to this time-sensitive application to improve its time complexity, while controlling the resulting bitrate loss. Specifically, four NNs are introduced with one NN for each depth of the coding tree unit. These NNs either split the current CU or terminate the CU search algorithm. Because training of NNs is time-consuming and requires large training data, we further propose a novel training strategy in which offline training and online adaptation work together to overcome this limitation. Our features are extracted from original frames based on the Laplacian Transparent Composite Model (LPTCM). Experiments carried out on all-intra configuration for HEVC reveal that our method is among the best NN methods, with an average time saving of 38% and an average controlled bitrate loss of 1.6%, compared to original HEVC.

Rate-distortion optimization (RDO) is widely applied in video coding, which aims at minimizing the coding distortion at a target bitrate. Conventionally, RDO is performed independently on each individual frame to avoid high computational complexity. However, extensive use of temporal/spatial predictions result in strong coding dependencies among neighboring frames, which make the current RDO be non-optimally used. To further improve video coding performance, it would be desirable to perform global RDO among a group of neighboring frames while maintaining approximately the same coding complexity. In this paper, the problem of global RDO is studied by jointly determining the quantization parameters (QPs) for a group of neighboring frames. Specifically, an adaptive frame-level QP selection algorithm is proposed for the H.265/HEVC random access coding by taking into account the inter-frame dependency. To measure the inter-frame dependency, a model based on the energy of prediction residuals is first established. With the help of the model, the problem of global RDO is then analyzed for the hierarchical coding structure in H.265/HEVC. Finally, the QP and the corresponding Lagrangian multiplier for each coding frame are determined adaptively by considering the total impact of its coding distortion on that of future frames in the encoding order. Experimental results show that in comparison with HM-16.0, the proposed algorithm reduces, on average, the BD-rate by 3.49% with negligible increase of encoding time. In addition, the quality fluctuation of the coded video by the proposed algorithm is lower than that by HM-16.0.

Compared with H.264, High Efficient Video Coding (HEVC) improves the coding efficiency by 50% at the price of significant increase in encoding time, due to Rate Distortion Optimization (RDO) on large variations of block sizes and prediction modes. In this paper, a fast intra coding algorithm is proposed to alleviate the high computational complexity of HEVC intra-frame coding. The proposed algorithm is based on machine learning and Laplacian Transparent Composite Model (LPTCM). Features called Summation of Binarized Outlier Coefficient (SBOC) vectors are firstly extracted from original frames by using LPTCM and then fed into online trained Support Vector Machine (SVM). Two SVMs are combined to predict Coding Unit (CU) decisions so that the encoding process can be significantly sped up. Additionally, a performance controller is introduced to ensure the robustness of machine learning models. It is shown by experiments that compared with HM 16.3, the proposed algorithm reduces the encoding time, on average, by 48% with negligible increase in BD-rate.

In this paper, we address the problems of key generation and management for enabling one-key-for-one-file secure encryption, where every file is encrypted by using an independent random key, which is highly desired in long-term protection of data stored on public clouds and other applications. A new concept dubbed information-theoretical ϵ-security is introduced to measure the security of a keystore (i.e., a set of random keys, ki, 1 ≤ i ≤ Λ, each consisting of l bits) which are generated from a random string of L bits, called the keystore seed. An efficient keystore generation scheme is presented, and the resulting keystore Ψ = {ki:1 ≤ i ≤ Λ} is shown to be information-theoretically e-secure with small e. Specifically, they satisfy the following properties: (1) Λ ≫ L is sufficiently large to realize one-key-for-one-file encryption for applications with a large number of files; (2) for any key index i, the key kiis uniformly distributed over the key space {0,1}1and hence statistically independent of i if i is chosen randomly; (3) for any two independent i, j, 1 ≤ i, j ≤ Λ, the probability that ki = kj is less than (1 - ϵ) × 2-l+ ϵ and (4) for any two independent key indices i and j, knowing i, j, and ki does not reduce the amount of uncertainty about kj significantly, i.e., the conditional Shannon entropy H (kj |i, j, ki)is at least as large as (1 - ϵ)H(kj | j). These security properties along with easy generation of each key ki from the keystore seed and the key index i remove most challenges in distributing and managing a large number of random keys.

In this paper, a suite of lightweight security protocols for the Internet of Things (IoT) is presented. It comprises protocols for lightweight encryption, authentication as well as key management. The key management protocol is the application of our early work on information theoretically secure key management to IoT; it is computationally efficient and information-theoretically secure, and enables that every data item (file) is encrypted with its own random key. The security and computational efficiency of the proposed protocols are compared with those of IPsec, which is the most commonly used suite of network-layer security protocols in Internet based applications but not desirable, due to its computationally-intensive procedures, to IoT applications and cyber-physical systems (CPS) with resource and computation-capability constraints. The proposed security protocols can be employed in IoT and CPS applications, replacing the IPsec core algorithms or the whole IPsec suite, to achieve a higher level of security with a very low resource consumption that helps to maintain the system sustainability.

After our internal code cross-check, we have recently found some mistakes in[1, Table VIII]and[1, Figs. 12 and 13]. As such, we have reimplemented the ideas and methods stated in[1]. The correctedTable VIIIandFigs. 12and13are now shown in this correction. Our code is also available fromhttp://multicom.uwaterloo.ca. To reflect this correction, the following changes have to be made accordingly throughout the paper[1].

To improve the rate-distortion (RD) performance of low delay (LD) High Efficiency Video Coding (HEVC) encoding while enabling scene-based non-linear editing feature (NLEF), in this paper, we present a new scene-based LD HEVC encoding framework in which scene change (SC) detection and coding are conducted jointly. A frame in a sequence to be encoded is deemed a SC if there is a sudden change in the residual energy. SCs are detected using the residual image parameters identified from the newly proposed Laplacian Transparent Composite Model (LPTCM). When a SC is detected, it is designated as an I frame; the quantization parameters for this frame and its subsequent frames before the next SC are determined. Compared to the default LD configuration, experimental results show that an average gain of 0.24 dB in RD performance and reduced overall encoding time are achieved while providing the scene-based NLEF.

Distributed arithmetic coding (DAC) is an effective technique for implementing Slepian-Wolf coding (SWC). It has been shown that a DAC code partitions source space into unequal-size codebooks, so that the overall performance of DAC codes depends on the cardinality and structure of these codebooks. The problem of DAC codebook cardinality has been solved by the so-called codebook cardinality spectrum (CCS). This paper extends the previous work on CCS by studying the problem of DAC codebook structure. We define Hamming distance spectrum (HDS) to describe DAC codebook structure and propose a mathematical method to calculate the HDS of DAC codes. The theoretical analyses are verified by experimental results.

Distributed arithmetic coding (DAC) is a variant of AC that can realize Slepian-Wolf coding in a nonlinear way. In our previous work, we defined codebook cardinality spectrum (CCS) and Hamming distance spectrum (HDS) for DAC. In this paper, we make use of CCS and HDS to analyze tailed DAC, which is a form of DAC that, as traditional AC, maps the last few symbols of each source block onto non-overlapped intervals. First, we derive the exact HDS formula for tailless DAC, a form of DAC that maps all the symbols of each source block onto overlapped intervals, and show that the HDS formula previously given is in fact approximation. Then, the HDS formula is extended to tailed DAC. Using CCS, we also deduce the average codebook cardinality, which is closely related to decoding complexity, and rate loss of tailed DAC. The effects of tail length are extensively analyzed. It is revealed that by increasing tail length to a value not close to the bitstream length, closely spaced codewords within the same codebook can be removed at the cost of a higher decoding complexity and a larger rate loss. Finally, theoretical analyses are verified by experiments.

Bi-geometric transparent composite models (BGTCM) are used to model distributions of transform coefficients in HEVC (High efficiency video coding). Both Kullback-Leibler divergence and χ2test show that, for both original and quantized transform coefficients in HEVC, BGTCMs provide better modelling performance than popular Laplacian and Cauchy models. Based on BGTCMs, a rate control algorithm is proposed for HEVC. Experimental results using the HEVC reference software show that the proposed algorithm achieves better performance in constant-bit-rate control than previous rate control algorithms based on Laplacian models.

In comparison with H.264/AVC, the newest video coding standard, High Efficiency Video Coding (HEVC), improves video coding rate distortion (RD) performance, but at the price of significant increase in its encoding complexity, due to its complicated inter mode decision process. In HEVC inter coding, the actual RD costs of all combinations of coding units (CUs), prediction units (PUs), and transform units (TUs) have to be computed and then the combination (i.e., mode) with the minimum cost is selected and encoded. To reduce the inter mode decision complexity in HEVC while maintaining its coding efficiency, in this paper, a fast inter mode decision method based on a newly proposed Transparent Composite Model (TCM) is developed. Spatially and temporally homogeneities are identified by TCM, and then used, together with spatiotemporal correlation between CUs, to determine PU and CU partitions so that cost computations of unnecessary modes can be skipped. Experimental results show that, for the low delay main test configuration of HEVC, our method reduces, on average, the encoding time by 60.71% with an insignificant loss in coding efficiency (1.06% BD-Rate increase).

In comparison with H.264/Advanced Video Coding, the newest video coding standard, High Efficiency Video Coding (HEVC), improves video coding rate-distortion (RD) performance, but at the price of significant increase in its encoding complexity, especially, in intra-mode decision due to the adoption of more complex block partitions and more candidate intra-prediction modes (IPMs). To reduce the mode decision complexity in HEVC intra-frame coding, while maintaining its RD performance, in this paper, we first formulate the mode decision problem in intra-frame coding as a Bayesian decision problem based on the newly proposed transparent composite model (TCM) for discrete cosine transform coefficients, and then present an outlier-based fast intra-mode decision (OIMD) algorithm. The proposed OIMD algorithm reduces the complexity using outliers identified by TCM to make a fast coding unit split/nonsplit decision and reduce the number of IPMs to be compared. To further take advantage of the outlier information furnished by TCM, we also refine entropy coding in HEVC by encoding the outlier information first, and then the actual mode decision conditionally given the outlier information. The proposed OIMD algorithm can work with and without the proposed entropy coding refinement. Experiments show that for the all-intra-main test configuration of HEVC: 1) when applied alone, the proposed OIMD algorithm reduces, on average, the encoding time (ET) by 50% with 0.7% Bjontegaard distortion (BD)-rate increase and 2) when applied in conjunction with the proposed entropy coding refinement, it reduces, on average, both the ET by 50% and BD-rate by 0.15%.

Soft decision quantization (SDQ) is an efficient tool for video coding to achieve coefficient-level rate-distortion optimized quantization (RDOQ) with a 6%-8% bit rate saving. However, the software and hardware implementations of SDQ suffer from either high complexity or low throughput capacity due to complex Viterbi trellis search and sequential processing in context-adaptive binary arithmetic coding. In this paper, a fast SDQ algorithm is proposed to decrease the number of trellis stages to decrease the complexity and to break the data dependency in optimal SDQ. First, preselection is performed according to hard decision quantization results by intelligent coding cost estimation and comparison, during which some coefficients are judged to be safely excluded from trellis search, resulting in considerable complexity reduction. Second, a dynamic trellis graph with flexible structure is constructed according to the unsafe nonzero coefficients to accelerate the remaining partial Viterbi search. Third, a dynamic threshold selection model is proposed for adaptive thresholding to increase the probability of right preselection under a constraint on a predefined maximal probability of wrong preselection. The experimental results show that compared with optimal SDQ, the proposed algorithm can at least reduce the computation complexity by 50%-80%, memory accesses by 75%-82%, and the sequential processing latency in hardware implementation by 87.25%, with less than 0.4% Bjøntegaard bit rate increment when a maximum of three unsafe coefficients are kept for trellis search in one block. This paper is suitable for high-throughput hardware and computation-sensitive software implementations for SDQ and RDOQ for H.264/Advanced Video Coding and High Efficiency Video Coding standards.

Recently, a new probability model dubbed the Laplacian transparent composite model (LPTCM) was developed for DCT coefficients, which could identify outlier coefficients in addition to providing superior modeling accuracy. In this paper, we aim at exploring its applications to image compression. To this end, we propose an efficient nonpredictive image compression system, where quantization (including both hard-decision quantization (HDQ) and soft-decision quantization (SDQ)) and entropy coding are completely redesigned based on the LPTCM. When tested over standard test images, the proposed system achieves overall coding results that are among the best and similar to those of H.264 or HEVC intra (predictive) coding, in terms of rate versus visual quality. On the other hand, in terms of rate versus objective quality, it significantly outperforms baseline JPEG by more than 4.3 dB in PSNR on average, with a moderate increase on complexity, and ECEB, the state-of-the-art nonpredictive image coding, by 0.75 dB when SDQ is OFF (i.e., HDQ case), with the same level of computational complexity, and by 1 dB when SDQ is ON, at the cost of slight increase in complexity. In comparison with H.264 intracoding, our system provides an overall 0.4-dB gain or so, with dramatically reduced computational complexity; in comparison with HEVC intracoding, it offers comparable coding performance in the high-rate region or for complicated images, but with only less than 5% of the HEVC intracoding complexity. In addition, our proposed system also offers multiresolution capability, which, together with its comparatively high coding efficiency and low complexity, makes it a good alternative for real-time image processing applications.

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.

Compared with H.264/AVC, the newest video standard called High Efficiency Video Coding (HEVC) further improves video coding performance, but at the price of significant increase in its encoding complexity, especially in intra mode decision due to the adoption of complex block partition scheme and more intra prediction modes. To reduce the intra mode decision complexity in HEVC while maintaining its coding efficiency, in this paper, we first formulate the mode decision as a Bayesian decision problem based on the newly proposed Transparent Composite Model (TCM) and then present an outlier based fast intra mode decision method. Experiments show that for the All-Intra Main test configuration of HEVC, our method reduces, on average, the encoding time by 48% with an insignificant loss in coding efficiency (0.7% BD-Rate increase).

Recently, a new statistical model called the Laplacian transparent composite model (LPTCM) was developed for DCT coefficients, which could identify outlier coefficients in addition to providing superior modeling accuracy. In this paper, we aim at exploring its applications to image compression. To this end, we propose an efficient DCT-based non-predictive image compression system, where quantization and entropy coding are completely re-designed based on the LPTCM. Experimental results show that our proposed system (1) achieves the best rate distortion (RD) coding performance among all non-predictive image compression systems proposed in the literature and compared in the paper, and (2) provides, in comparison with HEVC intra coding, the state-of-the-art predictive image coding, comparable or even better RD coding performance in the highrate region or for complicated images, but with only less than 5% of the encoding complexity of the latter.

A new video standard called High Efficiency Video Coding (HEVC) has been recently finalized. In comparison with the H.264/AVC video coding standard, HEVC further improves the video coding rate distortion (RD) performance, but at the price of significant increase in its encoding complexity, especially in its motion estimation (ME) due to large block sizes and complicated block partition. To reduce the ME complexity in HEVC while maintaining its RD performance, in this paper we first formulate ME at the integer pixel level as a statistical inference problem and then propose a confidence interval-based ME (CIME) method. The proposed CIME method can be applied either on top of the existing fast search implemented in HEVC or on its own to replace the existing fast search implemented in HEVC. Experiments show that for the low-delay main test configuration of HEVC: 1) when applied on top of the existing fast search in HEVC, the proposed CIME method further reduces, on average, the integer-level ME time by 70% with only 1.0% increase in bit rate while maintaining the same reconstruction quality in PSNR and 2) when applied on its own to replace the existing fast search implemented in HEVC, the proposed CIME method achieves performance comparable with that of the fast search in HEVC reference software and better than that of the dynamic system fast algorithm proposed recently 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.

Causal video coding is a coding paradigm where video source frames X1, X2,..., XNare encoded in a frame-by-frame manner, the encoder for each frame can use all previous source frames and all previous encoded frames, and the corresponding decoder can use only all previous encoded frames. In the special case where the encoder for each frame Xkis further restricted to enlist help only from all previous encoded frames, causal video coding is reduced to predictive video coding, which all MPEG-series and H-series video coding standards proposed so far are based upon. In this paper, we compare the rate distortion performance of causal video coding with that of predictive video coding from an information theoretic perspective by modeling each frame Xkitself as a source Xk={Xk(i)}i=1∞. Let Rc*(D1,...,DN) (Rp*(D1,...,DN), respectively) denote the minimum total rate required to achieve a given distortion level D1,...,DNin causal video coding (predictive video coding, respectively). We first show that like Rc*(D1,..., DN), for jointly stationary and totally ergodic sources X1, X2,..., XN, Rp*(D1,...,DN) is equal to the infimum of the nth order total rate distortion function Rp,n(D1,...,DN) over all n, where Rp,n(D1,...,DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then prove that if the jointly stationary and totally ergodic sources X1,..., XNform a (first-order) Markov chain, we have Rp*(D1,...,DN)=Rc*(D1,...,DN). However, this is not true in general if X1,..., XNdo not form a (first-order) Markov chain. Specifically, we demonstrate that for independent and identically distributed vector source (X1,..., XN), if X1,..., XNdo not form a (first-order) Markov chain, then under some conditions on source frames and distortion, Rc*(D1,..., DN) is strictly less than Rp*(D1,..., DN) in general. Our techniques allow us to compare Rp*(D1,..., DN) with Rc*(D1,..., DN) even when the single-letter characterization of Rp*(D1,..., DN), if any, is unknown.

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.

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.

This paper aims to tackle theoretical modeling and dimension reduction, two fundamental issues in large scale image/video data processing, together, by proposing a transparent composite model (TCM) for transformed image/video data. Specifically, to handle the heavy tail phenomenon commonly seen in Discrete Cosine Transform (DCT) coefficients of image/video data, a TCM first separates the tail of a sequence of DCT coefficients from the main body of the sequence. Then, a parametric distribution is used to model the main body while a uniform distribution is used to model the tail. Efficient online algorithms for establishing a TCM are proposed and proved to converge exponentially fast, which suits large-scale image/video data processing. It is also demonstrated that a TCM has an inherent non-linear data reduction capability - DCT coefficients of an image in the heavy tail identified by a TCM reveal some unique global features of the image while being insignificant statistically. This, together with its fast convergence, makes the proposed model a desirable choice for modeling DCT coefficients in large-scale image/video applications, such as online quantization design, entropy coding design, and image/video analytics in Big Data.

Summary form only given. This paper proposes a Multi-Symbol Context Adaptive Binary Arithmetic Coding (CABAC) Framework in Hybrid Video Coding. Advanced CABAC techniques have been employed in popular video coding technologies like H264-AVC, HEVC. The proposed framework aims at extending these technique by providing symbol level scalability in being able to code one or multi-symbols at a time without changing the existing framework. Such a coding not only can exploit higher order statistical dependencies on a syntax element level but also reduce the number of coded bins. New syntax elements and their Probability modeling are proposed as extensions to achieve Multi-Symbol coding. An example variant of this framework, that is coding only maximum of two symbols at a time for quantized coefficient Indices, was implemented on top of JM18.3-H264 CABAC. This example extension when tested with on HEVC test Sequences shows significant throughput improvement (i.e., significant reduction in number of bins to be coded) and at the same time reduces Bit-rate significantly. The Frame-work can be seamlessly extended to code Multiple Symbols greater than two.

A new video standard called High Efficiency Video Coding (HEVC) is now being finalized. In comparison with the H.264/AVC video coding standard, HEVC further improves video coding rate distortion (RD) performance, but at the price of significant increase in its encoding complexity, especially in its motion estimation (ME). To reduce the ME complexity in HEVC while maintaining its RD performance, in this paper, we first formulate ME as a statistical inference problem and then propose a confidence interval based ME method. It is shown by experiments that, for the four test sequences with higher searching complexity under low delay main, our proposed ME method further reduces the integer level ME time of the fast search in HEVC by 73.49% on average with only 1.22% increase in bit rate and 0.024dB loss in PSNR.

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.

This paper investigates the design of optimal vector quantization given channel and error statistics by inclusion of cyclic redundancy checks (CRC) into the consideration. Given a broadcast system with multiresolution vector quantization (MRVQ) and error detection availability for each resolution, a closed-form formula for the weighted end-to-end distortion (EED) is first derived under a random index assignment. Based on the closed-form formula, an iterative algorithm is then proposed for designing optimal MRVQ to minimize the EED with CRC. Experiments show that for a wide range of channel error probability, the inclusion of CRC indeed reduces the EED. Finally, the best tradeoff between the number of bits for quantization and those for CRC is also investigated by experiments.

Let T denote the set of all structurally inequivalent finite rooted ordered binary trees. For each t ϵ e T, let D(t) be the unique minimal DAG representation of t, and let r(t) ϵ (0,1] be the ratio of the number of vertices of D(t) to the number of leaves oft. A lossless prefix encoder φ on {D(t) : t ϵ T} is proposed, and then a two-step lossless encoder φ* on T is defined by φ*(t) =Δφ(D(t)) for t ϵ T. Let γ be the function γ(x) =Δ(x/2)log2(2/x) for x ϵ (0,1]. It is shown that the normalized pointwise redundancy in encoding each t ϵ T via φ* is O(γ(r(t))). Furthermore, given a binary tree source whose output is a sequence of random trees growing in size, weak sufficient conditions on the source are presented under which the normalized average redundancy of φ* with respect to the source vanishes asymptotically. This result allows for the identification of some families of binary tree sources on which φ* acts as a universal code.

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.

This paper investigates the design of optimal multiresolution vector quantizers for broadcast channels with cyclic redundancy checks (CRC). Given a CRC-coded broadcast system with multiresolution vector quantization (MRVQ), a closed-form formula for the weighted end-to-end distortion (EED) is first derived under random index assignment. The closed-form expression is then further utilized to identify necessary optimality conditions to minimize the EED, from which an iterative algorithm is proposed for quantization design. Experiments conducted under both the point-to-point and broadcast channels demonstrate that for a wide range of channel error probability, inclusion of CRC significantly reduces the EED without sacrificing bandwidth. Further analyses are conducted to determine the best tradeoff between bits allocated for source quantization and CRC error detection.

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.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ..., XNare encoded in a frame by frame manner, the encoder for each frame Xkcan use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i) }i=1∞. A novel computation approach is proposed to analytically characterize, numerically compute, and compare the minimum total rate of causal video coding Rc*(D1, ...,DN) required to achieve a given distortion (quality) level D1, ...,DN>; 0. Among many other things, the computation approach includes an iterative algorithm with global convergence for computing Rc*(D1, ...,DN) . The global convergence of the algorithm further enables us to demonstrate a somewhat surprising result (dubbed the more and less coding theorem)-under some conditions on source frames and distortion, the more frames need to be encoded and transmitted, the less amount of data after encoding has to be actually sent. With the help of the algorithm, it is also shown by example that Rc*(D1, ...,DN) is in general much smaller than the total rate offered by the traditional greedy coding method. As a by-product, an extended Markov lemma is established for correlated ergodic sources.

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.

This paper studies the design and analysis of multiresolution vector quantization (MRVQ) for broadcast channels. Given a broadcast system with MRVQ, a random index assignment, and a coded broadcast channel, we first obtain a closed-form formula for the weighted end-to-end distortion (EED) of the system. Based on the formula, an iterative algorithm is then proposed for designing optimal MRVQ for the broadcast system. Experimental results demonstrate that multiresolution quantizers jointly designed with channel conditions by the proposed algorithm significantly reduce the weighted EED in comparison with multiresolution quantizers designed without reference to channel conditions.

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.

An improved iterative algorithm is first proposed to calculate the rate-distortion performance of causal video coding for any continuous sources. Instead of using continuous reproduction alphabets, it utilizes finite reproduction alphabets and iteratively updates them along with transitional probabilities from the continuous source to reproduction letters, thus overcoming the computation complexity problem encountered when applying the algorithm recently proposed by Yang et al for discrete sources to continuous sources. The proposed algorithm converges in the sense that the rate-distortion cost is monotonically decreasing until a stationary point is reached. It is then applied to practical video data to establish some theoretic coding performance benchmark. In comparison with H.264, experiments show that under the same motion compensation setting, causal video coding offers a roughly 1 dB coding gain on average over H.264 for the IPPIPP...GOP structure. This suggests that an area one could explore to further improve the rate-distortion performance of H.264 be how quantization and coding should be performed conditionally given previous frames and coded frames and given motion compensation.

A source coding paradigm called interactive encoding and decoding (IED) is considered for a source network where a finite alphabet sourceXis to be encoded, and another finite alphabet sourceYcorrelated withXis available only to the decoder as a helper. The optimal performance achievable asymptotically (OPAA) by IED is investigated, where the performance is measured as the average number of bits per symbol exchanged by the encoder and decoder until the decoder learnsXwith high probability. First, it is shown that for any stationary(X,Y), the OPAA by IED is given by the conditional entropy rateH(X|Y) ofXgivenY. This is in contrast with noninteractive Slepian-Wolf (SW) coding, where the OPAA is shown in general to be strictly greater thanH(X|Y) when(X,Y) is not ergodic. Second, for a memoryless source pair (X, Y), it is shown that IED approachesH(X|Y) faster than SW coding does. Finally, it is demonstrated that one can convert any classical universal data compression algorithm with side information to a universal IED algorithm for the class¿of all stationary ergodic source pairs. In contrast, universal SW coding algorithms for the class¿do not exist.

This paper studies the design of vector quantization on noisy channels and its high rate asymptotic performance. Given a tandem source-channel coding system with vector quantization, block channel coding, and random index assignment, a closed-form formula is first derived for computing the average end-to-end distortion (EED) of the system, which reveals a structural factor called the scatter factor of a noisy channel quantizer. Based on this formula, we propose a noisy-channel quantization design method by minimizing the EED. Experiments and simulations show that quantizers jointly designed with channel conditions significantly reduce the EED when compared with quantizers designed separately without reference to channel conditions, which reveals a practical and effective design for noisy-channel quantization as to simplify the channel model by considering a random index assignment. Furthermore, we have presented the high rate asymptotic analysis of the EED for the tandem system, while convergence analysis of the iterative algorithm is included in the Appendix.

Using fixed rate uniform vector quantization, in this paper, we consider how to design a joint watermarking and compression (JWC) system for Gaussian and Laplacian sources to maximize the robustness in the presence of additive Gaussian attacks under constraints on the compression rate and quantization distortion. Firstly, we construct vector quantizers shaped to match the multidimensional distribution of source signals. Then we scale codebooks corresponding to the vector quantizers to maximize the robustness of the watermarks against the additive Gaussian attacks. Simulation results show that the proposed scheme can achieve up to 0.92 dB distortion-to-noise ratio (DNR) gain over JWC schemes using uniform scalar quantization while maintaining the simplicity of implementation with uniform quantization.

Rate distortion optimization can significantly improve encoder performance in most video coding applications. Taking MPEG-2 as an example, this paper addresses the full rate distortion optimization for the first time by searching the product space of all four free parameters regardless of the computational complexity. An efficient graph-based searching algorithm was extended to the MPEG-2 video coding case from the authors' previous work to find the optimal coefficient indices in the optimization process. The proposed full rate distortion optimization algorithm serves the important role of providing an upper-bound benchmark without considering frame dependence and quantization weight matrix optimization. Two approximations of the full rate distortion optimization algorithms are also presented in order to reduce the computational complexity with a gradual degradation of the rate distortion performance. On average, 2~3dB gain is achieved with the proposed algorithms compared to regular MPEG-2 encoder.

Quantization in H.264 is achieved in the DCT domain using scalar quantizers, which assume a sum distortion constraint and often produce considerably larger distortions on block boundaries than inside a block in the pixel domain. This biased distortion distribution degrades the rate distortion (RD) performance of H.264 intra coding whose prediction is exclusively based on boundary pixels. This paper considers the problem of designing balanced distortion quantizers (BDQs) in the DCT domain, which, in addition to the sum distortion constraint, require evenly distributed distortions in the pixel domain. In a special case where DCT coefficients are independent Gaussian, the problem is solved as a convex optimization problem. Using this approach, we design BDQs and apply them to improve H.264 intra coding. Experimental results on typical frames show that the improved intra coding scheme consistently outperforms its counterpart in H.264 main-profile, averaging 5–9% rate reduction for QCIF frames, and 7–12% for CIF frames with aligned distortions.

This paper proposes two entropy constrained color splitting algorithms through building a binary tree structure for a progressive transmission of palette images. At each step of color splitting, a representative color is split into two new representative colors to minimize the distortion incurred by the reconstructed image subject to an entropy constraint. Among the bit rates of interest, both of the proposed unconditional entropy constrained color splitting algorithms and the conditional entropy constrained color splitting algorithm achieve, on average, 20% more size reduction than the existing distortion-based color splitting algorithm while maintaining the same distortion for our tested images. The superiority of the proposed algorithms is observed for color-quantized nature images and for synthetic images. Furthermore, all the proposed algorithms have a very moderate complexity and can be applied into practical applications like Web browsing through wireless or dialup links.

For each positive integer n, let Tnbe a random rooted full binary tree having 2n-1 vertices. We can view H(Tn), the entropy of Tn, as a measure of the structural complexity of tree Tnin the sense that approximately H(Tn) bits suffice to construct Tn. We analyze some random binary tree sequences (Tn: n = 1,2...) for which the normalized entropies H(Tn)/n converge to a limit as n rarr infin, as well as some other sequences (Tn) in which the normalized entropies fail to converge.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ? ? ? XNare encoded in a frame by frame manner, the encoder for each frame Xk, k = 1, ? ? ?, N, can use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i)}i=1?. A novel computation approach is proposed to analytically characterize and numerically compute the minimum total rate Rc(D1, ? ? ?, DN) required to achieve a given distortion (quality) level D1, ? ? ?, DN? 0. Specifically, we first show that for jointly stationary ergodic sources X1, X2, ? ? ?, XN, Rc(D1, ? ? ?, DN) is equal to the infimum of the nthorder total rate distortion function Rc,n(D1, ? ? ?, DN) over all n, where Rc,n(D1, ? ? ?, DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then present an iterative algorithm for computing Rc,n(D1, ? ? ?, DN) and demonstrate the convergence of the algorithm to the global minimum. The global convergence of the algorithm further enables us to establish a single-letter characterization of Rc(D1, ? ? ?, DN) in a novel way when the N sources are an independent and identically distributed vector source. Deep insights from the algorithm are also gained regarding how each frame should be encoded in order to achieve Rc(D1, ? ? ?, DN); it is demonstrated by example that Rc(D1, ? ? ?, DN) is in general much smaller than the total rate offered by the traditional greedy coding method by which each frame is encoded in a local optimum manner based on all information available to the encoder of the frame. In addition, a tight achievable rate distortion region is also derived.

This paper introduces a cross-layer design framework for robust and efficient video multicasting over IEEE 802.16 (also known as WiMAX) networks in metropolitan areas. In the framework, multiple description coding (MDC) on scalable video bitstreams at the source for achieving multiresolution robustness is jointly designed with superposition coding (SCM) on multicast signals at the channel to overcome multiuser channel diversity in wireless multicast. The coded multicast signals under the proposed framework can cope with multiuser channel diversity and mitigate the impact due to short-term channel fluctuations, which are the two most challenging issues in achieving robust and efficient video multicasting in metropolitan areas. We formulate the proposed framework and analyze its video quality performance in terms of the total receivable/ recoverable bitstreams by a receiver. A heuristic methodology is developed for system parameter selection and performance optimization that can be applied to practical scenarios of video multicasting for IPTV services in WiMAX. Simulation is conducted based on actual standard video sequences to verify the proposed methodology on parameter selection and performance optimization. Performance gains of the proposed cross-layer design framework in the presence of fading channel diversity are demonstrated.

In this paper, we study the rate-distortion (RD) optimization of the H.264 main profile encoding. Specifically, a soft decision quantization (SDQ) algorithm is developed based on the context adaptive binary arithmetic coding (CABAC) method in the H.264 main profile. Given motion prediction and quantization step sizes, the proposed SDQ algorithm is proved to achieve near-optimal SDQ for residual coding in the sense of minimizing the true RD cost when the weak adjacent block dependency utilized in CABAC is ignored for optimization. The SDQ algorithm is then used in conjunction with a general RD optimization framework to jointly design motion prediction and residual coding for H.264 main profile coding given previously coded reference frames. Experiments have been conducted based on the reference encoder JM82 of H.264 main profile. Comparative studies show that the joint design method achieves on average 10% rate reduction at the same PSNR when compared with the RD method in the H.264 main-profile reference software, with half of the reduction coming from the proposed SDQ algorithm, and 20% rate reduction at the same PSNR when compared with the RD method in the H.264 baseline-profile reference software.

To maximize rate distortion performance while remaining faithful to the JPEG syntax, the joint optimization of the Huffman tables, quantization step sizes, and DCT indices of a JPEG encoder is investigated. Given Huffman tables and quantization step sizes, an efficient graph-based algorithm is first proposed to find the optimal DCT indices in the form of run-size pairs. Based on this graph-based algorithm, an iterative algorithm is then presented to jointly optimize run-length coding, Huffman coding, and quantization table selection. The proposed iterative algorithm not only results in a compressed bitstream completely compatible with existing JPEG and MPEG decoders, but is also computationally efficient. Furthermore, when tested over standard test images, it achieves the best JPEG compression results, to the extent that its own JPEG compression performance even exceeds the quoted PSNR results of some state-of-the-art wavelet-based image coders such as Shapiro's embedded zerotree wavelet algorithm at the common bit rates under comparison. Both the graph-based algorithm and the iterative algorithm can be applied to application areas such as web image acceleration, digital camera image compression, MPEG frame optimization, and transcoding, etc.

This paper proposes a designing framework for down-sampling compressed images/video with arbitrary ratio in the discrete cosine transform (DCT) domain. In this framework, we first derive a set of DCT-domain down-sampling methods which can be represented by a linear transform with double-sided matrix multiplication (LTDS) in the DCT domain and show that the set contains a wide range of methods with various complexity and visual quality. Then, for a preselected spatial-domain down-sampling method, we formulate an optimization problem for finding an LTDS to approximate the given spatial-domain down-sampling method for a trade-off between the visual quality and the complexity. By modeling LTDS as a multiple layer network, a so-called structural learning with forgetting algorithm is then applied to solve the optimization problem. The proposed framework has been applied to discover optimal LTDSs corresponding to a spatial down-sampling method with Butterworth low-pass filtering and bicubic interpolation. Experimental results show that the resulting LTDS achieves a significant reduction on the complexity when compared with other methods in the literature with similar visual quality.

In this paper, it is shown that each Slepian-Wolf coding problem is related to a dual channel coding problem in the sense that the sphere packing exponents, random coding exponents, and correct decoding exponents in these two problems are mirror-symmetrical to each other. This mirror symmetry is interpreted as a manifestation of the linear codebook-level duality between Slepian-Wolf coding and channel coding. Furthermore, this duality, in conjunction with a systematic analysis of the expurgated exponents, reveals that nonlinear Slepian-Wolf codes can strictly outperform linear Slepian-Wolf codes in terms of rate-error tradeoff at high rates. The linear codebook-level duality is also established for general sources and channels.

In this paper, the redundancy of both variable and fixed rate Slepian–Wolf coding is considered. Given any jointly memoryless source-side information pair$\{(X_i, Y_i)\}_{i=1}^{\infty}$with finite alphabet, the redundancy$R^n(\epsilon_n)$of variable rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$depends on both the block length$n$and the decoding block error probability$\epsilon_n$, and is defined as the difference between the minimum average compression rate of order$n$variable rate Slepian–Wolf codes having the decoding block error probability less than or equal to$\epsilon_n$, and the conditional entropy$H(X\vert Y)$, where$H(X\vert Y)$is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$is defined similarly and denoted by$R^n_F(\epsilon_n)$. It is proved that under mild assumptions about$\epsilon_n,$$R^n(\epsilon_n) = d_v \sqrt{-\log\epsilon_n/n} + o(\sqrt{-\log \epsilon_n/n})$and$R^n_{F}(\epsilon_n) = d_f \sqrt{- \log \epsilon_n / n} + o(\sqrt{-\log \epsilon_n/n})$, where$d_f$and$d_v$are two constants completely determined by the joint distribution of the source-side information pair. Since$d_v$is generally smaller than$d_f$, our results show that variable rate Slepian–Wolf coding is indeed more efficient than fixed rate Slepian–Wolf coding.

One of the most important challenges in cognitive radio is how to measure or sense the existence of a signal transmission in a specific channel, that is, how to conduct spectrum sensing. In this letter, we first formulate spectrum sensing as a goodness of fit testing problem, and then apply the Anderson-Darling test, one of goodness of fit tests, to derive a sensing method called Anderson-Darling sensing. It is shown by both analysis and numerical results that under the same sensing conditions and channel environments, Anderson-Darling sensing has much higher sensitivity to detect an existing signal than energy detector-based sensing, especially in a case where the received signal has a low signal-to-noise ratio (SNR) without prior knowledge of primary user signals.

This paper proposes a designing framework for downsampling compressed images/video frames with arbitrary ratio in the discrete cosine transform (DCT) domain. We first derive a set of DCT-domain down-sampling methods which can be represented by a linear transform with double-sided matrix multiplication (LTDS) in the DCT domain, and show that the set contains a wide range of methods with various complexity and visual quality. Then, based on a pre-selected spatial- domain method, we formulate an optimization problem for finding an LTDS to approximate the given spatial domain method for achieving the best trade-off between the visual quality and the complexity. By selecting a spatial-domain reference method with the popular Butterworth lowpass filtering and bicubic interpolation, the proposed framework discovers LTDSs with better visual quality and lower computational complexity as saving 20%~70% execution time when compared with state-of-the-art methods in the literature.

Analog Gaussian watermarking systems in which transmitted watermarks are reproduced with certain distortion at receivers are addressed in this paper. Achievable distortion regions of private analog Gaussian watermarking systems and public analog Gaussian watermarking system are determined with respect to the mean-squared error distortion measure, with and without joint compression, respectively. The results show that, interestingly, if watermark sources and host signal sources are independent, then the achievable distortion regions of private analog Gaussian watermarking systems and public analog Gaussian watermarking systems coincide.

In this paper, we consider a paradigm of source coding called interactive encoding and decoding (IED). It illustrates this paradigm for a source network with one encoder and one decoder. Contrasting IED with SW coding, we see that in this new paradigm, information flows in both ways, and thus the encoder and decoder are allowed to interact with each other to accomplish a certain task.

This paper studies the design of vector quantization (VQ) on noisy channels and its asymptotic performance analysis. Given a tandem source-channel coding system with VQ and block channel coding, we derive a closed-form formula of the average end-to-end distortion (EED), which reveals a structural factor called the scatter factor for noisy channel quantizers. Based on this formula, an iterative algorithm is developed for jointly designing optimal quantizers with channel conditions. Simulations show that quantizers that are jointly designed with channel conditions significantly reduce the EED when compared with quantizers that are designed separately from channel conditions. Indeed, our asymptotic analyses show that the infimum of the mean squared EED over all possible quantizers with joint quantization design is perrsigma2, where perris the average transmission error probability of the channel and sigma2is the component variance of the source. This is 4.77dB better than that with separate quantization design for an i.i.d. Guassian source.

A cross-layer design (CLD) framework for robust and efficient video multicasting over IEEE 802.16 (or WiMAX) is introduced. In the framework, multiple description coding on scalable video bitstreams at the source for achieving multi-resolution robustness is jointly designed with superposition coding (i.e., multi-resolution modulation) on multicast signals at the channel to overcome the channel diversity problem in wireless multicast. The resulting cross-layer coded multicast signals enable us to recover some lost bitstreams in high quality layers, which is not possible if multi-resolution modulation is used alone for multicasting as in previous works. Simulation results show that indeed our joint design outperforms the scheme using only superposition coded multicast by achieving better video quality for users under multi-user channel diversity.

Consider a source network in which a finite alphabet source X = {Xi}i=0infinis to be encoded and transmitted, and another finite alphabet source Y = {Xi}i=0infincorrelated with X is available only to the decoder as side information. Traditionally, the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with the fact that the encoder does not have access to Y, implies that the encoder has to know the achievable rates before encoding. In this paper, we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assume that the encoder and decoder share a random database that is independent of both X and Y. A string matching-based (variable-rate) block coding algorithm with simple progressive encoding and joint typicality decoding is first proposed for the feedback source network. The simple progressive encoder does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources satisfying some mixing conditions, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes to the conditional entropy H(X | Y) of X given Y asymptotically, and at the same time the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically. The algorithm and the corresponding analysis results are then extended to the case where both X and Y are to be encoded separately, but decoded jointly. Finally, a universal decoding algorithm is proposed to replace the joint typicality decoding, and the resulting universal compression algorithm consisting of the simple progressive encoder and the universal decoding algorithm is further shown to be asymptotically optimal for the class of all jointly memoryless source-side information pairs (X,Y).

In this correspondence, a new digital watermarking scenario is studied, where watermarks and covertexts are correlated with each other. A necessary and sufficient condition is derived under which a watermark is first embedded, and can later be recovered with high probability at the output of a public watermark decoder after the watermarked signal is disturbed by a fixed memoryless attack channel. Interestingly, the condition also implies that the Shannon separation theorem does not hold in this scenario.

JPEG optimization strives to maximize the best rate distortion performance while remaining faithful to the JPEG syntax. Given an image, if soft decision quantization (SDQ) is applied to its DCT coefficients, then Huffman table, quantization step sizes and SDQ coefficients are three free parameters over which a JPEG encoder can optimize. In this paper, we first propose a novel algorithm to find the optimal SDQ coefficient indices in the form of run-size pairs among all possible candidates given that the other two parameters are fixed. Based on this algorithm, we then formulate an iterative algorithm to jointly optimize the run-length coding, Huffman coding and quantization step sizes. The proposed iterative algorithm achieves a compression performance better than any previously known JPEG compression results and even exceeds the quoted PSNR results of some state-of-the-art wavelet-based image coders like Shapiro's embedded zerotree wavelet algorithm at the common bit rates under comparison.

Motivated by the wide adoption of H.264 and the demand of universal multimedia data access over the expanding network with diverse devices, this paper studies H.264-based video transcoding with spatial resolution conversion. First, a practical solution for efficiently determining a reference frame is proposed to take advantage of the new feature of multiple references in H.264. Then, a motion vector estimation algorithm based on a multiple linear regression model is proposed to utilize the motion information in the original scenes for efficiently predicting motion vectors in the down-scaled scene. Experimental results show that, compared with a benchmark solution, the proposed method significantly reduces the transcoding complexity by 16 times while maintaining comparable rate distortion performance with a decrease of 0.06 dB in PSNR and 4% increase in the bit rate.

The Slepian-Wolf coding problem is often viewed as a channel coding problem for the purpose of gaining insight into its properties. In this perspective, source sequences are associated with balls of side information sequences, and then one packs in each bin as many of these balls as possible with little or no overlap. Alternatively, one can treat the problem as a source coding problem in which for a given side information sequence, the set of conditionally probable source sequences is distributed in as many bins as required by a fidelity criterion. In an earlier series of publications we developed the theory of redundancy of variable rate Slepian-Wolf codes using the first viewpoint. In this work, we obtain similar results from the second viewpoint; this direction has unique technical challenges but also reinforces the fundamental role of our previously introduced notion of intrinsic entropy. In one of our key technical contributions, we use an averaging argument resembling Shannon's random coding idea that we expect will be useful in studying other problems of source coding with side information.

With the motivation of constructing Low-Density Parity-Check (LDPC) codes with low error floors, we propose a new code construction scheme based on random 2-lifts. An analysis on stopping set distributions of the proposed code ensembles is presented. The analysis shows that low-weight stopping sets in the resulting codes are typically the results of stopping sets with weak graph expansion properties in the base graphs. Based on this analysis, we propose a set of design criteria for constructing codes with low error floors. According to the design criteria, stopping sets with weak graph expansion properties should be avoided in the base graphs. We present numerical results on constructing capacity-approaching codes over Binary Erasure Channels (BEC). The numerical results show that the codes by the proposed scheme have significantly lower error floors compared with the codes by the standard construction.

Reversible watermarking system with correlated watermarks and covertexts is studied. Necessary and sufficient conditions are derived such that the receiver can reproduce watermarks and covertexts within some distortions to original ones respectively, even watermarked signals are disturbed by an attacker. Furthermore, some interesting special cases are explored.

In this paper we investigate universal data compression with side information at the decoder by leveraging traditional universal data compression algorithms. Specifically, consider a source network with feedback in which a finite alphabet source X = {Xi}i=0infinis to be encoded and transmitted, and another finite alphabet source Y = {Yi}i=0infinavailable only to the decoder as the side information correlated with X. Assuming that the encoder and decoder share a uniform i.i.d. (independent and identically distributed) random database that is independent of (X, Y), we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. Instead of using standard joint typicality decoding, this algorithm derives its decoding rule from the codeword length function of a traditional universal lossless coding algorithm. As a result, neither the encoder nor the decoder assumes any prior knowledge of the joint distribution of (X, Y) or even the achievable rates. It is proven that for any (X, Y) in the class of all stationary, ergodic source-side information pairs with finite alphabet, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy rate H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically.

A typical arithmetic coder consists of three steps: range calculation, renormalization, and probability model updating. In this paper, we propose and analyze from an information theoretic point of view a greedy renormalization method, which has two components: greedy thresholding and greedy outputting. The method significantly reduces the computational complexity of the renormalization step of arithmetic coding by (1) using the greedy thresholding to minimize the number of renormalizations required to encode a sequence and (2) using the greedy outputting to minimize the number of operations within each renormalization. The method is particularly suitable for binary arithmetic coding (BAC). Two BAC algorithms based on this method are presented. The first algorithm replaces the renormalization method in the TOIS BAC with the greedy renormalization method, and keeps other parts of the TOIS BAC unchanged. For binary independent and identically distributed (i.i.d.) sources with the probability of the less probable symbol ranging from --, over gain in speed (on average), and less than loss in compression rate (in the worst case) are observed in the experiments. The second algorithm combines the greedy renormalization method with the QM-Coder. On an average, gain in speed and gain in compression rate are observed in the experiments.

Rate distortion (RD) optimization for H.264 interframe coding with complete baseline decoding compatibility is investigated on a frame basis. Using soft decision quantization (SDQ) rather than the standard hard decision quantization, we first establish a general framework in which motion estimation, quantization, and entropy coding (in H.264) for the current frame can be jointly designed to minimize a true RD cost given previously coded reference frames. We then propose three RD optimization algorithms--a graph-based algorithm for near optimal SDQ in H.264 baseline encoding given motion estimation and quantization step sizes, an algorithm for near optimal residual coding in H.264 baseline encoding given motion estimation, and an iterative overall algorithm to optimize H.264 baseline encoding for each individual frame given previously coded reference frames-with them embedded in the indicated order. The graph-based algorithm for near optimal SDQ is the core; given motion estimation and quantization step sizes, it is guaranteed to perform optimal SDQ if the weak adjacent block dependency utilized in the context adaptive variable length coding of H.264 is ignored for optimization. The proposed algorithms have been implemented based on the reference encoder JM82 of H.264 with complete compatibility to the baseline profile. Experiments show that for a set of typical video testing sequences, the graph-based algorithm for near optimal SDQ, the algorithm for near optimal residual coding, and the overall algorithm achieve on average, 6%, 8%, and 12%, respectively, rate reduction at the same PSNR (ranging from 30 to 38 dB) when compared with the RD optimization method implemented in the H.264 reference software.

In heterogeneous networks, packet losses arise as a result of both congestion and random transmission errors. In these networks, the Transmission Control Protocol (TCP) performs poorly because it assumes all packet losses are caused by congestion and subsequently throttles its transmission rate unnecessarily. This motivates the need to discriminate between different types of packet loss. In this paper, we propose a novel loss discrimination algorithm. Its design guided by a queueing analysis, our algorithm is based on a unique definition of a customer, Lindley's Equation and normalized least-mean square (LMS) prediction. It is accurate, efficient and can be incorporated into any transport layer protocol that employs a congestion control strategy triggered by packet loss. Our simulation results show that when our algorithm is implemented an extension of TCP Reno, throughput can be more than doubled under certain conditions.

Based on the idea of the Blahut-Arimoto algorithm for computing channel capacities and rate-distortion functions, two iterative algorithms are developed for numerical computation of the compression and watermarking rate regions of joint compression and private watermarking systems with finite alphabets. The convergence of the algorithms developed is also proved

In this paper we analyze the redundancy of variable rate Slepian-Wolf coding. For any memoryless source-side information pair (X, Y) = {(Xi,Yi)}Einfini=1with finite alphabet, the redundancy Rn(epsin) of variable rate Slepian-Wolf coding is defined as the minimum of the difference between the compression rate of any variable-rate Slepian-Wolf code resulting from coding XEn1with decoding error probability epsin, and the conditional entropy H(X|Y). It is proved that under mild assumptions, for sufficiently large n, Rn(epsin) is lower bounded by dradiclog n/n, where d > 0 is a constant

In this paper we investigate the relationship between Slepian-Wolf (S-W) coding and channel coding. It is shown that any S-W coding problem is dual to a channel coding problem for a semi-symmetric channel. This result holds for any stationary, ergodic source-side information pair with finite alphabet

Using soft decision quantization rather than the conventional hard decision quantization, this paper studies a joint rate distortion design of motion prediction, quantization and entropy coding for the H.264 main profile encoding. Specifically, a soft decision quantization algorithm is proposed based on the context adaptive binary arithmetic coding method in H.264. The proposed algorithm is proved to achieve optimal soft decision quantization for a block with given motion prediction and quantization step size in the sense of minimizing the true rate distortion cost. It is then used in jointly designing motion prediction and residual coding for H.264 main profile coding. Experiments have been conducted based on the reference encoder JM82 of H.264. Comparative studies show that the proposed joint design method achieves an average 10% rate reduction while maintaining the same quality over the rate distortion method in the reference software of H.264

A new digital watermarking scenario is studied, where a watermark M correlated with a covertext S is to be transmitted by embedding M into S. The configuration of this scenario is different from that treated in existing digital watermarking works, where watermarks are assumed independent of covertexts. Assume that the pair (M, S) is drawn from an independently and identically distributed sequence. A necessary and sufficient condition is derived under which the watermark M can be recovered with high probability at the end of a watermark decoder after the watermarked signal is disturbed by a fixed memoryless attack channel pY|X(y|x). Specifically, it is shown that in the case of public watermarking where the covertext S is not accessible to the watermark decoder, M can be recovered with high probability if and only if H(M) les maxp(x,u|m,s):Ed(S,X)lesD[I(U);M,S) - I(U; M, S) + I(M;U,Y)], where the maximum is taken over all auxiliary random variables U and X jointly distributed with M and S and satisfying Ed(S, X) les D. In particular, the result implies that the Shannon separation theorem can not be extended to this scenario, that is, it is still possible to transmit M reliably even when H(M) is strictly greater than the watermarking capacity. A similar result is also established for combined source coding and Gel'fand Pinsker channel coding

We propose the concept of quality-aware image, in which certain extracted features of the original (high-quality) image are embedded into the image data as invisible hidden messages. When a distorted version of such an image is received, users can decode the hidden messages and use them to provide an objective measure of the quality of the distorted image. To demonstrate the idea, we build a practical quality-aware image encoding, decoding and quality analysis system, which employs: 1) a novel reduced-reference image quality assessment algorithm based on a statistical model of natural images and 2) a previously developed quantization watermarking-based data hiding technique in the wavelet transform domain.

The paper presents a framework for jointly designing motion compensation, quantization and entropy coding in a hybrid video coding structure to minimize a rate distortion cost. Given motion compensation, a soft decision-based quantization algorithm is first designed to reduce the rate distortion cost by adapting quantization outputs to the baseline entropy coding method in the newest standard H.264. Motion compensation is then optimized by searching for a prediction to reduce the rate distortion cost further based on given quantization outputs. By alternating these two steps, an iterative method is then proposed. The proposed algorithms have been implemented based on the reference encoder of H.264 with complete baseline decoder compatibility. Comparative studies show that the baseline-based iterative optimization method achieves coding performance comparable, or sometimes superior, to that afforded by the main profile encoder.

Consider a source network in which a finite alphabet source X = {Xi}iinfin=0is to be encoded and transmitted, and another finite alphabet source Y = {Yi}iinfin=0available only to the decoder as the side information correlated with X. Traditionally the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with that the encoder does not have access to Y, necessitates that the encoder knows the achievable rates before encoding. In this paper we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assuming that the encoder and decoder share a random database that is independent of both X and Y, we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. This algorithm does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources which includes the class of all memoryless sources, the class of all aperiodic Markov sources, and a large class of finite-state sources as special subclasses, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically

The redundancy rate of the Lempel-Ziv algorithm has been widely investigated. Much of the data compression community believed that the redundancy rate of the LZ78 algorithm should be O((log n)-1), where n is the data length. However, until the present paper, this conjecture had not been proved for sources beyond Markov sources. In this paper, we investigate the upper bound on the pointwise redundancy rate of the Lempel-Ziv algorithm for mixing sources and finite-state sources. The technique we applied in this paper is simple. By studying the dictionary tree resulting from the LZ78 algorithm, we derive certain relationships between the self-information of a sequence emitted by a source and the number of phrases resulting from the LZ78 parsing of the sequence. From these relationships, upper bounds on the pointwise redundancy rate of the LZ78 algorithm on mixing sources and finite-state sources can be obtained. These results show that for mixing sources and finite-state sources, the pointwise redundancy rate is upper bounded by O((log n)-1) for the LZ78 algorithm. We also compare our results with previous results of Savari and Kieffer-Yang

This paper addresses the issue of truly optimizing the rate-distortion (RD) performance for MPEG-1/2 Layer III (MP3) audio coding by presenting a fixed-slope graph-based iterative algorithm to jointly design quantization, Huffman code-book (HCB) selection and region division. Given quantization step sizes and HCB selection, quantization outputs and HCB region division are first adapted to minimize the Lagrangian RD cost function throughout a standard-constrained graph structure. Then quantization step sizes and HCB selection are optimized serially to reduce the RD cost based on given quantization outputs and region division. These three steps are further alternated until convergence occurs. The proposed algorithm has been implemented based on ISO reference codec and LAME 3.96.1 with complete decoder compatibility. Simulation results show that the new MP3 coders resulting from the proposed algorithm indeed improve the RD performance substantially except for extremely low bit rates in both cases

In this paper, we investigate the performance of grammar-based codes for sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ if and only if there exists a universal code for /spl Lambda/. Moreover, upper bounds on the worst case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Depending upon the conditions satisfied by length-n individual sequences, these bounds range from O(loglogn/logn) to O(1/log/sup 1-/spl alpha//n) for some 0</spl alpha/<1. These results complement the previous universality and redundancy results in the literature on the performance of grammar-based codes for sources with finite alphabets.

In this paper, the design of low-density parity-check (LDPC) codes for binary erasure channels (BEC) with less number of decoding iterations in the parallel message-passing decoding is presented. We consider only the cases where the capacity is approached with sufficiently low parity-check matrix density.

Grammar-based coding is investigated from three new perspectives. First, we revisit the performance analysis of grammar-based codes by proposing context-based run-length encoding algorithms as new performance benchmarks. A redundancy result stronger than all previous corresponding results is established. We then extend the analysis of grammar-based codes to sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ for which there exists a universal code. Moreover, upper bounds on the worst-case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Finally, we propose a new theoretic framework for compression in which grammars rather than sequential stochastic processes are used as source generating models, and point out some open problems in the framework.

It was suggested by Battail that a good long linear code should have a weight distribution close to that of random coding, rather than a large minimum distance, and a turbo code should be also designed using a random-like criterion. In this paper, we first show that the weight distribution of a high-rate linear block code is approximately Gaussian if the code rate is close enough to one, and then proceed to construct a low-rate linear block code with approximately Gaussian weight distribution by using the turbo-coding technique. We give a sufficient condition under which the weight distribution of multicomponent turbo block (MCTB) codes (multicomponent product (MCP) codes, respectively) can approach asymptotically that of random codes, and further develop two classes of MCTB codes (MCP codes) satisfying this condition. Simulation results show that MCTB codes (MCP codes) having asymptotically Gaussian weight distribution can asymptotically approach Shannon's capacity limit. MCTB codes based on single parity-check (SPC) codes have a far poorer minimum distance than MCP codes based on SPC codes, but we show by simulation that when the bit-error rate is in the important range of 10/sup -1/-10/sup -5/, these codes can still offer similar performance for the additive white Gaussian noise channel, as long as the code length of the SPC codes is not very short. These facts confirm in a more precise way Battail's inference about the "nonimportance" of the minimum distance for a long code.

The compression performance of grammar-based codes is revisited from a new perspective. Previously, the compression performance of grammar-based codes was evaluated against that of the best arithmetic coding algorithm with finite contexts. In this correspondence, we first define semifinite-state sources and finite-order semi-Markov sources. Based on the definitions of semifinite-state sources and finite-order semi-Markov sources, and the idea of run-length encoding (RLE), we then extend traditional RLE algorithms to context-based RLE algorithms: RLE algorithms with k contexts and RLE algorithms of order k, where k is a nonnegative integer. For each individual sequence x, let r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) be the best compression rate given by RLE algorithms with k contexts and by RLE algorithms of order k, respectively. It is proved that for any x, r/sup *//sub sr,k/ is no greater than the best compression rate among all arithmetic coding algorithms with k contexts. Furthermore, it is shown that there exist stationary, ergodic semi-Markov sources for which the best RLE algorithms without any context outperform the best arithmetic coding algorithms with any finite number of contexts. Finally, we show that the worst case redundancies of grammar-based codes against r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) among all length- n individual sequences x from a finite alphabet are upper-bounded by d/sub 1/loglogn/logn and d/sub 2/loglogn/logn, respectively, where d/sub 1/ and d/sub 2/ are constants. This redundancy result is stronger than all previous corresponding results.

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).

Summary form only given. A novel method that significantly reduces the computational complexity of the re-normalization step of arithmetic coding is described. Called greedy re-normalization, the method involves a reduction to both the number of re-normalizations required to encode and the number of operations within each re-normalization. To reduce the number of re-normalizations in the encoding sequence, the method adopts a dynamic re-normalization criterion. Experimental results show that the proposed greedy re-normalization method indeed improved the speed of arithmetic coding.

In this paper we present optimal quantization watermarking strategies with respect to the robustness of a watermarking system given the embedding rate and distortion constraint. Firstly, we investigate the optimal decoding for quantization watermarking and show that by making use of channel statistics, the maximum likelihood decoder is always better than the minimum distance decoder. Secondly, the optimal encoding is designed by exploiting the knowledge of the host signal and channel statistics. Algorithms for designing the optimal uniform quantization encoding scheme and optimal nonuniform quantization encoding scheme are proposed. Simulation results show that the optimal nonuniform quantization watermarking can achieve better performance. Finally, applications to image authentication which is robust to high quality JPEG compression are described.

In this paper, the multilevel pattern matching (MPM) code for compression of one-dimensional (1D) sequences is first generalized to compress two-dimensional (2D) images, resulting in a 2D multilevel pattern matching (MPM) code. It is shown that among all images of n pixels, the worst case redundancy of the 2D MPM code against any finite-template-based arithmetic code is O(1//spl radic/logn). This result contrasts unfavorably with the fact that among all 1D sequences of length n, the MPM code has a worst case redundancy of O(1/logn) against any finite-state arithmetic code; this is caused by the so-called 2D boundary effect. To alleviate the 2D boundary effect, we extend the 2D MPM code to the case of context modeling, yielding a context-dependent 2D MPM code. It is shown that among all images of n pixels, the context-dependent 2D MPM code has an O(1/logn) worst case redundancy against any finite-template-based arithmetic code satisfying a mild condition; this redundancy is better than that of the 2D MPM code without context models. Experimental results demonstrate that the context-dependent 2D MPM code significantly outperforms the 2D MPM code without context models for bi-level images. It is also demonstrated that, in terms of compression rates, the context-dependent 2D MPM code performs significantly better than the progressive coding mode of JBIG1 for both textual and bi-level images, and better than or comparably to the sequential coding mode of JBIG1 and JBIG2. In addition to its excellent compression performance, the context-dependent 2D MPM code allows progressive transmission of images.

For pt. I see ibid., vol.46, p.755-88 (2000). The concept of context-free grammar (CFG)-based coding is extended to the case of countable-context models, yielding context-dependent grammar (CDG)-based coding. Given a countable-context model, a greedy CDG transform is proposed. Based on this greedy CDG transform, two universal lossless data compression algorithms, an improved sequential context-dependent algorithm and a hierarchical context-dependent algorithm, are then developed. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet. Moreover, it is proved that these algorithms' worst case redundancies among all individual sequences of length n from a finite alphabet are upper-bounded by d log log n/log n, as long as the number of distinct contexts grows with the sequence length n in the order of O(n/sup a/), where 0 < /spl alpha/ < 1 and d are positive constants. It is further shown that for some nonstationary sources, the proposed context-dependent algorithms can achieve better expected redundancies than any existing CFG-based codes, including the Lempel-Ziv (1978) algorithm, the multilevel pattern matching algorithm, and the context-free algorithms in Part I of this series of papers.

Throughput bounds are attained for random channel access multichannel code-division multiple-access (CDMA) systems and spread slotted Aloha systems employing multiuser receivers. It is shown that the normalized throughput of these two systems reaches 1.0 exponentially fast in the region r/K0. The maximum throughput of the random channel access multichannel CDMA systems is found as K-/spl radic/(1-(1/M))KlogK-O(logK), where M is the number of channels in the system. The maximum throughput is reached when the average number of simultaneous users is r/sub m/=K-/spl radic/((1-(1/M))KlogK))+O(/spl radic/(K/logK)). The maximum throughput of the spread slotted Aloha systems is K-/spl radic/(KlogK)-O(log K). The maximum throughput is reached when the packet arrival of Poisson distribution has the arrival rate /spl lambda//sub m/=K-/spl radic/(KlogK)+O(/spl radic/(K/logK)).

A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be fully reconstructed. In a grammar-based code, a data sequence is first converted into a grammar by a grammar transform and then losslessly encoded. Among several previously proposed grammar transforms is the multilevel pattern matching (MPM) grammar transform. In this paper, the MPM grammar transform is first extended to the case of side information known to both the encoder and decoder, yielding a conditional MPM (CMPM) grammar transform. A new simple linear-time and space complexity algorithm is then proposed to implement the MPM and CMPM grammar transforms. Based on the CMPM grammar transform, a universal lossless data compression algorithm with side information is developed, which can achieve asymptotically the conditional entropy rate of any stationary, ergodic source pair. It is shown that the algorithm's worst case redundancy/sample against the k-contest conditional empirical entropy among all individual sequences of length n is upper-bounded by c(1/logn), where c is a constant. The proposed algorithm with side information is the first in the coming family of conditional grammar-based codes, whose expected high efficiency is due to the efficiency of the corresponding unconditional codes.

The redundancy problem of universal lossy source coding at a fixed rate level is considered. Under some condition on the single-letter distortion measure, which implies that the cardinality K of the reproduction alphabet is not greater than the cardinality J of the source alphabet, it is shown that the redundancy of universally coding memoryless sources p by nth-order block codes of rate R goes like |(/spl part///spl part/R)d(p,R)|Kln n/2n+o(ln n/n) for all memoryless sources p except a set whose volume goes to 0 as the block length n goes to infinity, where d(p,R) denotes the distortion rate function of p. Specifically, for any sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes, where C/sub n/ is an nth-order block code at the fixed rate R, and any /spl epsiv/>0, the redundancy D/sub n/(C/sub n/,p) of C/sub n/ for p is greater than or equal to |(/spl part///spl part/R)d(p,R)|(K-/spl epsiv/)ln n/2n for all p satisfying some regular conditions except a set whose volume goes to 0 as n/spl rarr//spl infin/. On the other hand, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the rate R such that for any p satisfying some regular conditions, the super limit of D/sub n/(C/sub n/,p)|(ln n/n) is less than or equal to |(/spl part///spl part/R)d(p,R)|K/2.

Summary form only given. Recently, Yang and Kieffer (2000) proposed a novel lossless grammar-based data compression algorithm, called the YK algorithm, in which a greedy sequential grammar transform is applied to the original data to construct an irreducible context free grammar, which is encoded indirectly by using an arithmetic coder. The basic implementation of the YK encoding algorithm consists of a sequentially iterative application of three fundamental steps: parsing, arithmetic encoding, and updating. This paper proposes five modifications of the basic YK algorithm, motivated by applications of the algorithm to the Internet transmission of Web-data. 1) Fast YK encoder: The parsing operation is a major step of the YK algorithm. A variant of the tree data structure is proposed for fast parsing. This is applicable for real-time compression of IP datagrams. 2) Pre-defined source statistics: known source statistics can be exploited to improve compression efficiency, which is particularly effective for small IP datagrams with a known structure. 3) Pre-defined grammar: starting with a "typical" pre-defined grammar can significantly improve the compression efficiency for applications such as HTML Web-page compression. 4) Memory constrained implementation: during YK compression, as the length of the data sequence increases, the grammar also continues to grow in size, which can potentially exhaust the available memory in the system. This paper proposes a way to check memory requirement by reusing variables in the grammar, once a user-chosen limit on grammar size is reached. 5) Error handling capability: the paper identifies all possible contingencies that can arise when an erroneous bit-stream is fed to the YK decoder, and provides explicit ways to handle these. This is important in applications where compressed IP datagrams are transmitted over unreliable links.

We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar G/sub x/ representing x in the sense that x is the unique string belonging to the language generated by G/sub x/. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G/sub x/. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented.

A universal lossless data compression code called the multilevel pattern matching code (MPM code) is introduced. In processing a finite-alphabet data string of length n, the MPM code operates at O(log log n) levels sequentially. At each level, the MPM code detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The MPM code represents information about the matching patterns at each level as a string of tokens, with each token string encoded by an arithmetic encoder. From the concatenated encoded token strings, the decoder can reconstruct the data string via several rounds of parallel substitutions. A O(1/log n) maximal redundancy/sample upper bound is established for the MPM code with respect to any class of finite state sources of uniformly bounded complexity. We also show that the MPM code is of linear complexity in terms of time and space requirements. The results of some MPM code compression experiments are reported.

A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be fully reconstructed. In a grammar-based code, a data sequence is first converted into a grammar by a grammar transform and then losslessly encoded. In this paper, a greedy grammar transform is first presented; this grammar transform constructs sequentially a sequence of irreducible grammars from which the original data sequence can be recovered incrementally. Based on this grammar transform, three universal lossless data compression algorithms, a sequential algorithm, an improved sequential algorithm, and a hierarchical algorithm, are then developed. These algorithms combine the power of arithmetic coding with that of string matching. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source. Moreover, it is proved that their worst case redundancies among all individual sequences of length n are upper-bounded by c log log n/log n, where c is a constant. Simulation results show that the proposed algorithms outperform the Unix Compress and Gzip algorithms, which are based on LZ78 and LZ77, respectively.

If x is a string of finite length over a finite alphabet A, let LZ(x) denote the length of the binary codeword assigned to x by the 1978 version of the Lempel-Ziv data compression algorithm, let t(x) be the number of phrases in the Lempel-Ziv parsing of x, and let /spl mu/(x) be the probability assigned to x by a memoryless source model. Using a very simple technique, we probe the pointwise redundancy bound LZ(x)+log/sub 2//spl mu/(x)/spl les/8t(x)max{-log/sub 2//spl mu/(a):a/spl isin/A}.

In this paper, we propose a novel adaptive arithmetic coding method that uses dual symbol sets: a primary symbol set that contains all the symbols that are likely to occur in the near future and a secondary symbol set that contains all other symbols. The simplest implementation of our method assumes that symbols that have appeared in the previously are highly likely to appear in the near future. It therefore fills the primary set with symbols that have occurred in the previously. Symbols move dynamically between the two symbol sets to adapt to the local statistics of the symbol source. The proposed method works well for sources, such as images, that are characterized by large alphabets and alphabet distributions that are skewed and highly nonstationary. We analyze the performance of the proposed method and compare it to other arithmetic coding methods, both theoretically and experimentally. We show experimentally that in certain contexts, e.g., with a wavelet-based image coding scheme that has appeared in the literature, the compression performance of the proposed method is better than that of the conventional arithmetic coding method and the zero-frequency escape arithmetic coding method.

The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to finite-state decoders or trellis-structured decoders. When this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where /spl lambda/>0 and -/spl lambda/ are designated to be the slope of the rate distortion function R(D) of the source at some D; the quantity is close to R(D)+/spl lambda/D when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented; this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes. The resulting variable-rate trellis source codes are very efficient in low-rate regions. With k=8, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers; with k=8 and the number of states in the decoder=32, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, with k=8 and the number of states in the decoder=256, the mean-squared error encoding performance at the rates of a fraction of 1 bit/sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion rate function.

The redundancy problem of lossy source coding with abstract source and reproduction alphabets is considered. For coding at a fixed rate level, it is shown that for any fixed rate R>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the rate R such that the distortion redundancy of C/sub n/ (defined as the difference between the performance of C/sub n/ and the distortion rate function d(P, R) of P) is upper-bounded by |(/spl part/d(P,R))/(/spl part/R)| ln n/2n+o(ln n/n). For coding at a fixed distortion level, it is demonstrated that for any d>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the fixed distortion d such that the rate redundancy of C/sub n/ (defined as the difference between the performance of C/sub n/ and the rate distortion function R(P,d) of P) is upper-bounded by (7ln n)/(6n)+o(ln n/n). These results strengthen the traditional Berger's (1968, 1971) abstract alphabet source coding theorem, and extend the positive redundancy results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997, and ibid., vol.42, p.803-21, 1996) on lossy source coding with finite alphabets and the redundancy result of Wyner (see ibid., vol.43, p.1452-64, 1997) on block coding of memoryless Gaussian sources.

The shortest common superstring problem and its extension to approximate matching are considered in the probability model where each string in a given set has the same length and letters of strings are drawn independently from a finite set. In the exact matching case, several algorithms proposed in the literature are shown to be asymptotically optimal in the sense that the ratio of the savings resulting from the superstring constructed by each of these algorithms, that is the difference between the total length of the strings in the given set and the length of the superstring, to the optimal savings from the shortest superstring approaches in probability to 1 as the number of strings in the given set increases. In the approximate matching case, a modified version of the shortest common approximate matching superstring problem is analyzed; it is demonstrated that the optimal savings in this case is given approximately by nlogn/I/sub l/(Q,Q,2D), where n is the number of strings in the given set, Q is the probability distribution governing the selection of letters of strings, I/sub l/(Q,Q,2D) is the lower mutual information between Q and Q with respect to 2D, and D/spl ges/0 is the distortion allowed in approximate matching. In addition, an approximation algorithm is proposed and proved asymptotically optimal.

Summary form only given. The multilevel pattern matching data compression system is one of a class of compression algorithms introduced by Kieffer and Yang (see ERA Amer. Math. Soc., vol.3, p.11-16, 1997). The MPM system is currently of interest because of its good redundancy performance in losslessly compressing data strings of arbitrary length over a finite alphabet. An MPM system consists of a preprocessor, encoder/decoder, and a reconstruction engine. The preprocessor detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The preprocessor operates at several levels sequentially, with the number of levels selected by the user. The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The preprocessor represents information about matching patterns at each level as a string of tokens which is passed to the encoder of the MPM system. The decoder of the MPM system recovers these token strings, from which the reconstruction engine rebuilds the input data string. The preprocessor is the most complex component of the MPM system. We exhibit an implementation of the preprocessor of linear complexity in terms of execution time and space requirements; the number of levels satisfies O(log/sub 2/log/sub 2/n) for input data strings of length n.

Lossless and lossy data compression algorithms based on string matching are considered. In the lossless case, a result of Wyner and Ziv (1989) is extended. In the lossy case, a data compression algorithm based on approximate string matching is analyzed in the following two frameworks: (1) the database and the source together form a Markov chain of finite order; (2) the database and the source are independent with the database coming from a Markov model and the source from a general stationary, ergodic model. In either framework, it is shown that the resulting compression rate converges with probability one to a quantity computable as the infimum of an information theoretic functional over a set of auxiliary random variables; the quantity is strictly greater than the rate distortion function of the source except in some symmetric cases. In particular, this result implies that the lossy algorithm proposed by Steinberg and Gutman (1993) is not optimal, even for memoryless or Markov sources.

For pt.II see ibid., vol.42, p.822-36 (1996). The Gold-washing data compression algorithm is an adaptive vector quantization algorithm with vector dimension n. In this paper, a redundancy problem of the Gold-washing data compression algorithm is considered. It is demonstrated that for any memoryless source with finite alphabet A and generic distribution p and for any R>0, the redundancy of the Gold-washing data compression algorithm with dimension n (defined as the difference between the average performance of the algorithm and the distortion-rate function D(p,R) of p) is upper-bounded by |/sub /spl delta/R///sup /spl delta//D(p,R)|((|A|+2/spl xi/+4 log n)/2n)+/spl sigma/(logn/n) where /sub /spl delta/R///sup /spl delta//D(p,R) is the partial derivative of D(p,R) with respect to R, |A| is the cardinality of A, and /spl xi/>0 is a parameter used to control the threshold in the Gold-washing algorithm. In connection with the results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997) on the redundancy of lossy source coding, this shows that the Gold-washing algorithm has the optimal convergence rate among all adaptive finite-state vector quantizers.

A new coding problem is introduced for a correlated source (X/sup n/,Y/sup n/)/sub n=1//sup /spl infin//. The observer of X/sup n/ can transmit data depending on X/sup n/ at a prescribed rate R. Based on these data the observer of Y/sup n/ tries to identify whether for some distortion measure /spl rho/ (like the Hamming distance) n/sup -1/ /spl rho/(X/sup n/,Y/sup n/)/spl les/d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X/sup n/ and Y/sup n/ are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X/sup n/ and Y/sup n/ are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory.

The redundancy problem of the fixed-database Lempel-Ziv (1977) algorithm is considered. It is demonstrated that for a class of /spl phi/-mixing sources which includes Markov sources, unifilar sources, and finite-state sources as special cases, the redundancy of the fixed-database Lempel-Ziv algorithm with database size n is lower-bounded by H(loglogn)/logn+O((logloglogn)/logn) and upper-bounded by 2H(loglogn)/logn+O((logloglogn)/logn) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to variable-length codes.

Corresponding to any lossless codeword length function l, three universal lossy data compression schemes are presented: one is with a fixed rate, another is with a fixed distortion, and a third is with a fixed slope. The former two universal lossy data compression schemes are the generalization of Yang-Kieffer's (see ibid., vol.42, no.1, p.239-45, 1995) results to the general case of any lossless codeword length function l, whereas the third is new. In the case of fixed-slope /spl lambda/>0, our universal lossy data compression scheme works as follows: for any source sequence x/sup n/ of length n, the encoder first searches for a reproduction sequence y/sup n/ of length n which minimizes a cost function n/sup -1/l(y/sup n/)+/spl lambda//spl rho//sub n/(x/sup n/, y/sup n/) over all reproduction sequences of length n, and then encodes x/sup n/ into the binary codeword of length l(y/sup n/) associated with y/sup n/ via the lossless codeword length function l, where /spl rho//sub n/(x/sup n/, y/sup n/) is the distortion per sample between x/sup n/ and y/sup n/. Under some mild assumptions on the lossless codeword length function l, it is shown that when this fixed-slope data compression scheme is applied to encode a stationary, ergodic source, the resulting encoding rate per sample and the distortion per sample converge with probability one to R/sub /spl lambda// and D/sub /spl lambda//, respectively, where (D/sub /spl lambda//, R/sub /spl lambda//) is the point on the rate distortion curve at which the slope of the rate distortion function is -/spl lambda/. This result holds particularly for the arithmetic codeword length function and Lempel-Ziv codeword length function. The main advantage of this fixed-slope universal lossy data compression scheme over the fixed-rate (fixed-distortion) universal lossy data compression scheme lies in the fact that it converts the encoding problem to a search problem through a trellis and then permits one to use some sequential search algorithms to implement it. Simulation results show that this fixed-slope universal lossy data compression scheme, combined with a suitable search algorithm, is promising.

The problem of redundancy of source coding with respect to a fidelity criterion is considered. For any fixed rate R>0 and any memoryless source with finite source and reproduction alphabets and a common distribution p, the nth-order distortion redundancy D/sub n/(R) of fixed-rate coding is defined as the minimum of the difference between the expected distortion per symbol of any block code with length n and rate R and the distortion rate function d(p,R) of the source p. It is demonstrated that for sufficiently large n, D/sub n/(R) is equal to -(/spl part///spl part/R)d(p,R) ln n/2n+o(ln n/n), where (/spl part///spl part/R)d(p,R) is the partial derivative of d(p,R) evaluated at R and assumed to exist. For any fixed distortion level d>0 and any memoryless source p, the nth-order rate redundancy R/sub n/(d) of coding at fixed distortion level d (or by using d-semifaithful codes) is defined as the minimum of the difference between the expected rate per symbol of any d-semifaithful code of length n and the rate-distortion function R(p,d) of p evaluated at d. It is proved that for sufficiently large n, R/sub n/(d) is upper-bounded by ln n/n+o(ln n/n) and lower-bounded by In n/2n+o(In n/n). As a by-product, the lower bound of R/sub n/(d) derived in this paper gives a positive answer to a conjecture proposed by Yu and Speed (1993).

A general class of sequential codes for lossless compression of individual sequences on a finite alphabet is defined, including many types of codes that one would want to implement. The principal requirement for membership in the class is that the encoding and decoding operations be performable on a computer. The OPTA function for the class of codes is then considered, which is the function that assigns to each individual sequence the infimum of the rates at which the sequence can be compressed over this class of sequential codes. Two results about the OPTA function are obtained: (1) it is shown that any sequential code in the class compresses some individual sequence at a rate strictly greater than the rate for that sequence given by the OPTA function; and (2) it is shown that the OPTA function takes a value strictly greater than that of the Kolmogorov (1965) complexity rate function for some individual sequences.

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-known Lempel-Ziv algorithm. In the case of fixed rate R, the universal lossy data compression scheme works as follows: first pick a codebook B/sub n/ consisting of all reproduction sequences of length n whose Lempel-Ziv codeword length is /spl les/nR, and then use B/sub n/ to encode the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion performance as n/spl rarr//spl infin/ is given almost surely by the distortion rate function. A similar result is shown in the context of fixed distortion lossy source coding.

For pt.I see ibid., vol.42, no.3, p.803-21 (1996). Two versions of the gold-washing data compression algorithm, one with codebook innovation interval and the other with finitely many codebook innovations, are considered. The version of the gold-washing algorithm with codebook innovation interval k is a variant of the gold-washing algorithm such that the codebook is innovated once every k+1 source words during the process of encoding the entire source. It is demonstrated that when this version of the gold-washing algorithm is applied to encode a stationary, /spl phi/-mixing source, the expected distortion performance converges to the distortion rate function of the source as the codebook length goes to infinity. Furthermore, if the source to be encoded is a Markov source or a finite-state source, then the corresponding sample distortion performance converges almost surely to the distortion rate function. The version of the gold-washing algorithm with finitely many codebook innovations is a variant of the gold-washing algorithm in which after finitely many codebook innovations, the codebook is held fixed and reused to encode the forthcoming source sequence block by block. Similar results are shown for this version of the gold-washing algorithm. In addition, the convergence speed of the algorithm is discussed.

In this paper, a variant of address vector quantization (ADVQ) algorithm for image compression using conditional entropy lossless coding is presented. The motivation of the proposed approach is derived from Shannon's basic entropy concept that conditional entropy is less than joint entropy.

A novel concept of distortion Kolmogorov-chaitin complexity is proposed. Bearing analogy to ordinary Kolmogorov-Chaitin complexity that represents the information content of a single message, distortion Kolmogorov-Chaitin complexity can be regarded as the amount of information about a single message that must be conveyed in order to reproduce it with a bounded distortion. This explanation is justified by the properties of distortion Kolmogorov-Chaitin complexity and the equivalences between distortion Kolmogorov-Chaitin complexity and the rate-distortion function, which are analogous to those between ordinary Kolmogorov-Chaitin complexity and the Shannon entropy. Some implications for universal almost sure data compression are also discussed.>