Marker codes for channels with insertions and deletions

Coding for channels with synchronization errors is studied. Marker codes, each consisting of a low-density parity-check code with inserted markers, are developed. At low insertion-deletion probabilities marker codes are shown to outperform watermark codes. Full iterative decoding enhances performance to close to the capacity bounds. The low-density parity-check codes are optimized and the best known rate R = 0.5 code for the insertion-deletion channel presented. The codes are also shown to be effective on the bit-deletion channel.     

Trellis quantization with MAP detection for noisy channels

Maximum a posteriori (MAP) detection is applied to trellis quantizers operating over additive white Gaussian noise (AWGN) channels. The use of the MAP method instead of maximum likelihood is motivated by the fact that the source coder output probabilities, conditioned on the previous outputs (i.e. the state), are not equal. Simulation results indicate that by using MAP detection instead of maximum likelihood, gains as high as 0.57 dB and 2.2 dB can be achieved in terms of signal-to-quantization noise ratio (SQNR) for Gauss-Markov source and speech samples, respectively     

Coding for channels with cost constraints

We address the problem of finite-state code construction for the costly channel. This channel model is a generalization of the hard-constrained channel, also known as a subshift. Adler et al. (1986) developed the powerful state-splitting algorithm for use in the construction of finite-state codes for hard-constrained channels. We extend the state-splitting algorithm to the costly channel. We construct synchronous (fixed-length to fixed-length) and asynchronous (variable-length to fixed-length) codes. We present several examples of costly channels related to magnetic recording, the telegraph channel, and shaping gain in modulation. We design a number of codes, some of which come very close to achieving capacity     

Optimal bit allocation for noisy channels

An asymptotic expression for the optimal bit allocation for noisy channels is derived using high-resolution quantisation theory. Theoretically determined bit allocation based on the derived expression is presented.     

Trellis-coded quantization designed for noisy channels

Trellis-coded quantization (TCQ) of memoryless sources is developed for transmission over a binary symmetric channel. The optimized TCQ coder can achieve essentially the same performance as Ayanoglu and Gray's (1987) unconstrained trellis coding optimized for the binary symmetric channel, but with a much lower implementation complexity for transmission rates above 1 b/sample. In most cases, the optimized TCQ coder also provides larger signal-to-noise ratio than Farvardin and Vaishampayan's (1991) channel-optimized vector quantization. Algorithms are developed for the joint design of trellis-coded quantization/modulation (TCQ/TCM). The jointly designed TCQ/TCM system outperforms the straightforward cascade of separately designed TCQ and TCM systems. The improvement is most significant at low channel signal-to-noise ratio. For a first-order Gauss-Markov source, the predictive TCQ/TCM performance can exceed that of optimum pulse amplitude modulation     

Coding for radio channels

The conventional remedy to time and/or frequency variability of radio channels is diversity. Redundant coding is a kind of diversity, as each coded symbol can be recovered from other symbols. Only linear binary block codes are considered. Any binary random variable can be represented by its algebraic value,a real number whose sign indicates its most likely value and whose absolute value measures the probability of this value. The algebraic value of a received binary symbol is itself a random variable, whose distribution obeys a particular constraint. The algebraic value associated with the maximum likelihood decision on a binary symbol, given a set of independent received replicas of it, and that associated with the sum modulo 2 of binary random variables are also considered. The symbol-by-symbol decoding is then analysed in the case of threshold decoding, then in the general case. An approximate bound on the decoding error probability for additive Gaussian noise and coherent demodulation is used to assess the advantage of coding when unequalenergy symbols are received, according to a deterministic or a Rayleigh distribution. Simulation results are given for the Hamming (15,11) code. Coding affords a significant advantage provided the channel is good enough, while conventional diversity always provides gain.     

Splitting algorithms in noisy channels with memory

Multi-access networks are considered in which the shared channel is noisy. The authors assume a slotted-time collision-type channel, Poisson infinite-user model, and binary feedback. Due to the noise in the shared channel, the received signal may be detected as a collision even though no message or a single message is transmitted. This kind of imperfect feedback is referred to as error. A common assumption in all previous studies of multi-access algorithms in channels with errors is that the channel is memoryless. The authors consider the problem of splitting algorithms when the channel has memory. They introduce a two-state, first-order Markovian model for the channel and analyze the operation of the tree collision-resolution algorithm in this channel. They obtain a stability result, i.e., the necessary conditions on the channel parameters for stability of the algorithm. Assuming that the stability conditions hold, they calculate the throughput of the algorithm. Assuming that the stability conditions hold, they calculate the throughput of the algorithm. Extensions to more general channel moders are discussed     

Shape-gain vector quantization for noisy channels with applicationsto image coding

A new design procedure for shape-gain vector quantizers (SGVQs) which leads to substantially improved robustness against channel errors without increasing the computational complexity is proposed. This aim is achieved by including the channel transition probabilities in the design procedure, leading to an improved assignment of binary codewords to the coding regions as well as a change of partition and centroids. In contrast to conventional design, negative gain values are also permitted. The new design procedure is applied to adaptive transform image coding. Simulation results are compared with those obtained by the conventional design procedure. The new algorithm is particularly useful for heavily distorted or fading channels     

On finite-state vector quantization for noisy channels

Finite-state vector quantization (FSVQ) over a noisy channel is studied. A major drawback of a finite-state decoder is its inability to track the encoder in the presence of channel noise. In order to overcome this problem, we propose a nontracking decoder which directly estimates the code vectors used by a finite-state encoder. The design of channel-matched finite-state vector quantizers for noisy channels, using an iterative scheme resembling the generalized Lloyd algorithm, is also investigated. Simulation results based on encoding a Gauss-Markov source over a memoryless Gaussian channel show that the proposed decoder exhibits graceful degradation of performance with increasing channel noise, as compared with a finite-state decoder. Also, the channel-matched finite-state vector quantizers are shown to outperform channel-optimized vector quantizers having the same vector dimension and rate. However, the nontracking decoder used in the channel-matched finite-state quantizer has a higher computational complexity, compared with a channel-optimized vector-quantizer decoder. Thus, if they are allowed to have the same overall complexity (encoding and decoding), the channel-optimized vector quantizer can use a longer encoding delay and achieve similar or better performance. Finally, an example of using the channel-matched finite-state quantizer as a backward-adaptive quantizer for nonstationary signals is also presented.     

Coding techniques for partial-response channels

A coding technique for improving the reliability of digital transmission over noisy partial-response channels with characteristics (±D^m), m=1, 2, where the channel input symbols are constrained to be ±1, is presented. In particular, the application of a traditional modulation code as an inner code of a concentrated coding scheme in which the outer code is designed for maximum (free) Hamming distance is considered. A performance comparison is made between the concentrated scheme and a coding technique presented by Wolf and G. Ungerboeck (see ibid., vol. COM-34, p.765-773, Aug. 1986) for the dicode channel with transfer function (1- D)     

A study of vector quantization for noisy channels

Several issues related to vector quantization for noisy channels are discussed. An algorithm based on simulated annealing is developed for assigning binary codewords to the vector quantizer code-vectors. It is shown that this algorithm could result in dramatic performance improvements as compared to randomly selected codewords. A modification of the simulated annealing algorithm for binary codeword assignment is developed for the case where the bits in the codeword are subjected to unequal error probabilities (resulting from unequal levels of error protection). An algorithm for the design of an optimal vector quantizer for a noisy channel is briefly discussed, and its robustness under channel mismatch conditions is studied. Numerical results for a stationary first-order Gauss-Markov source and a binary symmetric channel are provided. It is concluded that the channel-optimized vector quantizer design algorithm, if used carefully, can result in a fairly robust system with no additional delay. The case in which the communication channel is nonstationary (as in mobile radio channels) is studied, and some preliminary ideas for quantizer design are presented     

Index allocation in vector quantisation for noisy channels

An index allocation algorithm for vector quantisation coding through noisy channels is presented. By applying this index allocation scheme, the mean square error of the communication system due to channel noise can be reduced remarkably without introducing any redundancy. Furthermore, the scheme is rather simple in computation. The experimental results for a Gaussian memoryless source and a Gauss-Markov source are provided.<>     

Optimum transmit-receive beamforming with noisy channel estimates for correlated MIMO Rayleigh channels

In this paper, we design jointly optimum transmitter and receiver beamforming structures in correlated MIMO Rayleigh fading channels with noisy channel estimates, and evaluate their performance through a closed-form expression for the probability of error. At the receiver, an estimate of the channel is obtained based on the transmitted pilot symbols. The knowledge of the estimate is then made available to the transmitter through a feedback channel. It is assumed that spatial correlation exists, either at the transmitter or at the receiver. A new exact closed-form expression for the probability of error is derived and the joint effects of diversity order and channel estimation accuracy on system performance are analyzed.     

Turbo codes for nonuniform memoryless sources over noisy channels

This work addresses the problem of designing turbo codes for nonuniform binary memoryless or independent and identically distributed (i.i.d.) sources over noisy channels. The extrinsic information in the decoder is modified to exploit the source redundancy in the form of nonuniformity; furthermore, the constituent encoder structure is optimized for the considered nonuniform i.i.d. source to further enhance the system performance. Some constituent encoders are found to substantially outperform Berrou's (1996) (37, 21) encoder. Indeed, it is shown that the bit error rate (BER) performance of the newly designed turbo codes is greatly improved as significant coding gains are obtained     

Coding for a class of nonprobabilistic channels with nonzero memory

A class of finite-alphabet discrete-time nonprobabilistic communication channels with finite nonzero memory is defined. The unknown input/output mapping is required to stay fixed for a specified number of channel uses and then can change arbitrarily within a given set of mappings. The frequency with which the input/output mapping can change gives a rate of time-variation for the channel. The class of channels is parametrized by this rate of time-variation, by alphabet size, by memory duration, and by the set of permissible mappings. Zero-error capacity in the sense of Shannon is computed for a collection of special cases within this class.     

Design of sample adaptive product quantizers for noisy channels

Channel-optimized vector quantization (COVQ) has proven to be an effective joint source-channel coding technique that makes the underlying quantizer robust to channel noise. Unfortunately, COVQ retains the high encoding complexity of the standard vector quantizer (VQ) for medium-to-high quantization dimensions and moderate-to-good channel conditions. A technique called sample adaptive product quantization (SAPQ) was recently introduced by Kim and Shroff to reduce the complexity of the VQ while achieving comparable distortions. In this letter, we generalize the design of SAPQ for the case of memoryless noisy channels by optimizing the quantizer with respect to both source and channel statistics. Numerical results demonstrate that the channel-optimized SAPQ (COSAPQ) achieves comparable performance to the COVQ (within 0.2 dB), while maintaining considerably lower encoding complexity (up to half of that of COVQ) and storage requirements. Robustness of the COSAPQ system against channel mismatch is also examined.     

Semianalytic BER evaluation by simulation for noisy nonlinearbandpass channels

The bit error rate (BER) of channels including a memoryless bandpass nonlinearity is evaluated by simulation. This would typically be an onboard travelling wave tube (TWT) amplifier in a satellite repeater, when the noise at the input of such a nonlinear element is non-negligible. The usual evaluation technique, error counting, requires a large amount of computer time if small error probabilities are to be estimated. It is shown that faster semianalytic procedures can be used, provided that a proper model for the nonlinear element is adopted. The output process is decomposed into a signal component plus an additional term representing an equivalent noise component, and an equivalent nonlinear transformation, relating the input useful signal to the output signal component, is derived. In addition, several modes for the probability density function (PDF) of the uplink noise component at the output of the transmission chain are discussed and compared. The procedure has been tested on a transparent satellite link using 4-CPSK modulation format. The results compare well with those of the error-counting technique if a composite rectangular PDF with exponential tails as adopted     

Optimal block cosine transform image coding for noisy channels

A method is presented for the joint source-channel coding optimization of a scheme based on the two-dimensional block cosine transform when the output of the encoder is to be transmitted via a memoryless binary symmetric channel. The authors' approach involves an iterative algorithm for the design of the quantizers (in the presence of channel errors) used for encoding the transform coefficients. This algorithm produces a set of locally optimum (in the mean-squared error sense) quantizers and the corresponding binary codeword assignment for the assumed transform coefficient statistics. To determine the optimum bit assignment among the transform coefficients, the authors have used an algorithm based on the steepest descent method, which, under certain convexity conditions on the performance of the channel-optimized quantizers, yields the optimal bit allocation. Simulation results for the performance of this locally optimum system over noisy channels have been obtained, and appropriate comparisons with a reference system designed for no channel errors have been made. It is shown that substantial performance improvements can be obtained by using this scheme. Furthermore, theoretically predicted results and rate distortion-theoretic bounds for an assumed two-dimensional image model are provided     

Coding theorem for secret sharing communication systems with twonoisy channels

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

Coding techniques for the noisy magnetic recording channel: astate-of-the-art report

Coding techniques for improving the reliability of information storage on noisy magnetic recording channels are considered. It is assumed that the Lorentzian channel model applies and that the retrieved signal is perturbed with additive white Gaussian noise. The immunity against additive noise of state-of-the-art codes such as DC-free, runlength-limited, and trellis codes are assessed