Joint source/channel decoders that use the residual redundancy in the source are investigated for differential pulse code modulation (DPCM) picture transmission over a binary symmetric channel. Markov sequence decoders employing the Viterbi algorithm that use first-order source statistics are reviewed, and generalized for decoders that use second-order source statistics. To make optimal use of the source correlation in both horizontal and vertical directions, it is necessary to generalize the conventional Viterbi decoding algorithm for a one higher-dimensional trellis. The paths through the trellis become two-dimensional "sheets", thus, the technique is coined "sheet decoding". By objective [reconstruction signal-to-noise ratio (SNR)] and subjective measure, it is found that the sheet decoders outperform the Markov sequence decoders that use a first-order Markov model, and outperform two other known decoders (modified maximum a posteriori probability and maximal SNR) that use a second-order Markov model. Moreover, it is found that the use of a simple rate-2/3 block code in conjunction with Markov model-aided decoding (MMAD) offers significant performance improvement for a 2-bit DPCM system. For the example Lenna image, it is observed that the rate-2/3 block code is superior to a rate-2/3 convolutional code for channel-error rates higher than 0.035. The block code is easily incorporated into any of the MMAD DPCM systems and results in a 2-bit MMAD DPCM system that significantly outperforms the noncoded 3-bit MMAD DPCM systems for channel-error rates higher than 0.04.

Soft-decision-feedback MAP decoders are developed for joint source/channel decoding (JSCD) which uses the residual redundancy in two-dimensional sources. The source redundancy is described by a second order Markov model which is made available to the receiver for row-by-row decoding, wherein the output for one row is used to aid the decoding of the next row. Performance can be improved by generalizing so as to increase the vertical depth of the decoder. This is called sheet decoding, and entails generalizing trellis decoding of one-dimensional data to trellis decoding of two-dimensional data (2-D). The proposed soft-decision-feedback sheet decoder is based on the Bahl algorithm, and it is compared to a hard-decision-feedback sheet decoder which is based on the Viterbi algorithm. The method is applied to 3-bit DPCM picture transmission over a binary symmetric channel, and it is found that the soft-decision-feedback decoder with vertical depth V performs approximately as well as the hard-decision-feedback decoder with vertical depth V+1. Because the computational requirement of the decoders depends exponentially on the vertical depth, the soft-decision-feedbark decoder offers significant reduction in complexity. For standard monochrome Lena, at a channel bit error rate of 0.05, the V=1 and V=2 soft-decision-feedback decoder JSCD gains in RSNR are 5.0 and 6.3 dB, respectively.

This paper presents theoretical and numerical results on the effect of bridged taps on the channel capacity of unshielded twisted pair telephone wiring used in very-high-speed digital subscriber line broadband access systems.

Bidirectional sequential decoding (BSD) substantially reduces the computational variability of conventional sequential decoding without compromising the error performance. However, BSD does not completely eliminate the erasure problem. We propose an erasure-free decoding algorithm which combines the idea of BSD in conjunction with that of the multiple stack algorithm (MSA). It is found that the new bidirectional multiple stack algorithm (BMSA) offers substantial advantages over the MSA in terms of computational effort, memory requirements, and error performance. The BMSA appears as an attractive alternative to the Viterbi algorithm (VA) where low error probabilities and high decoding speeds are required.

A variant of the best-path (BP) algorithm that can be used for deducing a posteriori symbol probabilities for input sequences of unlimited length is proposed. Decoders using the proposed algorithm have fixed memory requirements and fixed decoding delays regardless of the length of the transmitted sequence. This is made possible by utilizing the Viterbi algorithm's ability to self-initialize itself and by segmenting the decoding process.

A soft-output Viterbi algorithm (SOVA) that can be used on trellis-coded modulation (TCM), rate-k/n convolutional codes, and intersymbol interference (ISI) channels is proposed. The algorithm utilizes the postdetector architecture proposed by Berrou et al. (1993) to achieve low computational complexity. By starting with Battail's (1987) generalized revision algorithm and rereferencing the "relative values" to the surviving path to each state, substantial simplifications are made possible. By comparing the revision operations dictated by the simplified revision equation for a rate-1/n convolutional code to the operations mandated by the rate-1/n postdetector algorithm presented by Berrou et al., it is possible to deduce the additional modifications necessary to produce a rate-k/n postdetector algorithm. Computer simulations suggest that the derived rate-k/n algorithm produces reasonably good a posteriori input probability estimates for rate-k/n convolutional codes and trellis codes. The algorithm may also be used for soft-output Viterbi equalization (SOVE) provided that the channel impairments are not too severe.

The main drawback of sequential decoding is the variability of its decoding effort which could cause decoding erasures. We propose and analyze an efficient bidirectional sequential decoding (BSD) technique to alleviate this drawback. In the proposed BSD, two decoders are used; one is called a forward decoder (FD), and is used to search the tree from the forward direction; while the other is called a backward decoder (BD), and is used for the backward search of the tree. Forward decoding and backward decoding are performed simultaneously, and stop whenever the FD and BD merge at a common encoder state somewhere in the tree. The relationships between backward coding and forward coding are examined in detail. Good rate 1/2 convolutional codes, with memory m ranging from 2 to 25, suitable for bidirectional decoding found through extensive computer search, are provided. These codes possess the same distance properties from both forward and backward directions. It is found, by means of extensive computer simulations as well as a heuristic argument, that the advantage of the BSD appears as a substantial decrease of the computational variability of the sequential decoding. Our findings suggest that the Pareto exponent of unidirectional sequential decoding (USD) can be practically doubled by using BSD.

Presents a new class of punctured convolutional codes that are complementary (CPC codes). A set of punctured convolutional codes derived from the same original low rate code are said to be complementary if they are equivalent (in terms of their distance properties) and if when combined yield at least the original low rate code. Based on these CPC codes the author proposes and analyzes a variation of the type II hybrid ARQ scheme which is called a type III hybrid ARQ scheme. With the type III hybrid ARQ scheme, the starting code rate can be chosen to match the channel noise requirements, and as with the type II scheme, packets that are detected in error are not discarded, but are combined with complementary transmissions provided by the transmitter to help recover the transmitted message. The main advantage is that any complementary sequence sent for a packet that is detected with errors is self decodable. That is the decoder does not have to rely on previously received sequences for the same data packet for decoding, as is generally the case with incremental redundancy ARQ schemes. This feature is desirable especially in situations where a transmitted packet can be lost or severely damaged as a result of interference. CPC codes can find applications in diversity transmission systems. A novel complementary diversity scheme which makes use of CPC codes is briefly discussed.>

Many digital communication channels are affected by errors that tend to occur in bursts. A great deal of work has been devoted to finding good burst-error-correcting codes and developing burst-error-correcting schemes. However, burst-error-correcting codes are generally not effective for long bursts. Some burst-error-correcting schemes suffer long delay in decoding. Others are very sensitive to random errors in the guard space. Most of these schemes are not adaptive to channel conditions. A new adaptive scheme is proposed to overcome these drawbacks. The scheme employs a combination of two complementary punctured convolutional (CPC) codes. One of the codes is used for burst detection and for channel state estimation, and both codes are used for error correction. The proposed scheme is analyzed over a two state Markov chain channel model. Unlike existing burst-error-correcting schemes, it is shown that the proposed scheme is adaptive to channel conditions and less sensitive to errors in the guard space. For the same delay, the proposed scheme offers better performance than the interleaving schemes. When the channel is heavily corrupted by bursts, the improvement is even more pronounced.

An adaptive scheme for trellis-coded modulation of MPSK signals, called adaptive trellis-coded multiple-phaseshift keying (ATCMPSK), is proposed for slowly Rayleigh fading channels. The adaptive scheme employs a slightly modified rate 1/2 convolutional encoder and the corresponding Viterbi decoder to realize a family of codes of different rates which are employed according to channel conditions. During poor channel conditions, trellis-coded QPSK (TCQPSK) together with repetition schemes are employed. As channel conditions improve, higher rate schemes such as trellis-coded 16 PSK are used. An interleaving/ deinterleaving method suitable for the adaptive scheme is proposed. Theoretical bounds for the error performance and an exact expression for the throughput of the proposed adaptive scheme are derived, and are compared against simulation results. Simulations have been performed to measure the performance of the scheme for different parameters and some nonideal conditions. It is shown that ATCMPSK results in considerable improvement in bit-error-rate (BER) performance of MPSK signals. Under ideal conditions, gains in the range of 3-20 dB are achieved over conventional fixed rate pragmatic trellis-coded schemes.

In this paper, efficient stop-and-wait, go-back-N and selective-repeat hybrid ARQ protocols with adaptive forward error correction (AFEC) using convolutional coding are proposed and analyzed. The basic idea is to vary the coding rate for error correction according to system parameters, such as the signal-to-noise ratio, the round trip delay and the buffer size at the receiver, so as to maximize the throughput efficiency. The performances of the proposed ARQ protocols are evaluated for two channel models: a non-fading and an ideally-interleaved Rayleigh-fading additive white Gaussian noise channel. In all cases it is found that the hybrid ARQ protocols with AFEC yield a comparatively high throughput under all channel conditions.>

A generalized type II automatic-repeat-request (ARQ) scheme using punctured convolutional coding on a two-state Markov model of a nonstationary channel is analyzed. A simple ARQ scheme with memory is also analyzed. It is shown that the simple memory ARQ scheme offers a substantial throughput improvement over a conventional ARQ scheme at severe channel conditions. Furthermore, the generalized type II ARQ scheme yields a better performance than the conventional type II ARQ scheme under all channel conditions, thus making it attractive for use over time-varying channels.>

Sequential decoding is analyzed in conjunction with an efficient incremental redundancy automatic repeat request (ARQ) scheme using punctured convolutional coding. With the incremental redundancy ARQ scheme, whenever the decoding time of a given data packet exceeds some predetermined value T/sub max/, decoding of that data packet is stopped and incremental redundancy bits are provided by the transmitter, a few bits at a time, as needed. It is shown that the incremental redundancy ARQ scheme provides throughput improvement over the partial retransmission code combining ARQ scheme. The advantage of the incremental redundancy ARQ scheme is that the throughput increases as the starting coding rate increases over all ranges of signal-to-noise ratios.>

Several modifications of an efficient automatic repeat request (ARQ) scheme proposed by Weldon (see IEEE Trans. Commun., vol.COM-30, p.480, 1982) are studied. Unlike Weldon's scheme, in which all erroneous data packets are discarded, the present schemes make use of copies of the data packet which may contain errors. A number of channel models are considered, namely, a binary symmetric channel, a nonfading, and a Rayleigh fading channel with additive white Gaussian noise. In most cases, it is found that the throughput can be substantially increased. Under poor channel conditions, the use of forward error correction can lead to further improvement. A type-II ARQ scheme which does not suffer the throughput degradation under good channel conditions due to overhead parity bits associated with conventional forward error correction is also analyzed.>

An incremental redundancy selective-repeat ARQ (automatic-repeat-request) scheme, called the AIR (adaptive incremental redundancy) scheme, for use in systems with limited buffer receivers, based on the use of punctured convolutional codes, is introduced. Its throughput is compared to that of E. J. Weldon's (1982) scheme and a type-II ARQ scheme studied previously by the authors (1990). The AIR scheme is found to have a relatively good throughput over a wide range of channel conditions, thus making it attractive for use on time-varying channels.>

The authors present and analyze an efficient partial retransmission automatic repeat request (ARQ) strategy using convolutional coding and sequential decoding in conjunction with code combining. In the proposed ARQ scheme, whenever a packet of data needs to be retransmitted that packet is not repeated entirely as in the case of conventional full retransmission ARQ strategies. Instead, symbols of that packet are repeated a few at a time, sequentially, as needed, hence making a more effective use of the channel. It is shown that partial repetitions and code combining still yields an increase of the apparent Pareto exponent of sequential decoding, as in the case of full repetition-code combining. A throughput analysis shows that the partial retransmission ARQ strategy yields a substantial throughput improvement over the full retransmission-code combining ARQ strategies.>

An analysis is presented of the selective-repeat type II hybrid ARQ (automatic-repeat-request) scheme, using convolutional coding and exploiting code combining. With code combining, at successive decoding attempts for a data packet, the decoder for error correction operates on a combination of all received sequences for that packet rather than only on the two most recent received ones as in the conventional type II hybrid ARQ scheme. It is shown by means of analysis and computer simulations that with code combining, a significant throughput is achievable, even at very high channel error rates.>

A method is presented to construct rate-compatible convolutional (RCC) codes from known high-rate punctured convolutional codes, obtained from best-rate 1/2 codes. The construction method is rather simple and straightforward, and still yields good codes. Moreover, low-rate codes can be obtained without any limit on the lowest achievable code rate. Based on the RCC codes, a generalized type-II hybrid ARQ scheme, which combines the benefits of the modified type-II hybrid ARQ strategy of J. Hagenauer (1988) with the code-combining ARQ strategy of D. Chase (1985), is proposed and analyzed. With the proposed generalized type-II hybrid ARQ strategy, the throughput increases as the starting coding rage increases, and as the channel degrades, it tends to merge with the throughput of rate 1/2 type-II hybrid ARQ schemes with code combining, thus allowing the system to be flexible and adaptive to channel conditions, even under wide noise variations and severe degradations.>

Sequential decoding with ARQ (automatic-repeat-request) and code combining under the timeout condition is considered. That is, whenever the decoding time of a given packet exceeds some predetermined duration, decoding is stopped and retransmission of the packet is requested. However, the unsuccessful packets are not discarded, but are combined with their retransmitted copies. It is shown that the use of code combining allows sequential decoding to operate efficiently even when the coding rate R exceeds the computational cutoff rate R/sub comp/. Furthermore, an analysis of the selective-repeat ARQ scheme shows that the use of code combining yields a significant throughput even at very high channel error rates, thus making the system very robust under severe degradations of the channel.>