On the universality of Burnashev's error exponent

We consider communication over a time-invariant discrete memoryless channel (DMC) with noiseless and instantaneous feedback. We assume that the transmitter and the receiver are not aware of the underlying channel, however, they know that it belongs to some specific family of DMCs. Recent results show that for certain families (e.g., binary-symmetric channels and Z channels) there exist coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent.     

Fast iterative coding techniques for feedback channels

A class of capacity-achieving, low-complexity, high-reliability, variable-rate coding schemes is developed for communication over discrete memoryless channels with noiseless feedback. Algorithms for encoding and decoding that require computations growing linearly with the number of channel inputs used are developed. The error exponent associated with the scheme is shown to be optimal and implies that capacity is achievable. Simulations are performed and support the analytically predicted high performance and low complexity     

Channel capacity and error exponents of variable rate adaptivechannel coding for Rayleigh fading channels

We have evaluated the information theoretical performance of variable rate adaptive channel coding for Rayleigh fading channels. The channel states are detected at the receiver and fed back to the transmitter by means of a noiseless feedback link. Based on the channel state informations, the transmitter can adjust the channel coding scheme accordingly. Coherent channel and arbitrary channel symbols with a fixed average transmitted power constraint are assumed. The channel capacity and the error exponent are evaluated and the optimal rate control rules are found for Rayleigh fading channels with feedback of channel states. It is shown that the variable rate scheme can only increase the channel error exponent. The effects of additional practical constraints and finite feedback delays are also considered. Finally, we compare the performance of the variable rate adaptive channel coding in high bandwidth-expansion systems (CDMA) and high bandwidth-efficiency systems (TDMA)     

The Error Exponent of Variable-Length Codes Over Markov Channels With Feedback

The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended to finite-state ergodic Markov channels. For these channels, a single-letter characterization of the reliability function is presented, under the assumption of full causal output feedback, and full causal observation of the channel state both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference (ISI). Specifically, the convex-analytic approach to Markov decision processes is adopted in order to handle problems with stopping time horizons induced by variable-length coding schemes.     

Center-of-gravity information feedback

We considerMsignals in aD-dimensional signal space. TheseMsignals are used to communicate over an additive Gaussian white noise channel. It is shown that if a noiseless feedback channel is available one could use this feedback channel to inform the transmitter of the location of the center of gravity of the signal structure and thus obtain a very efficient signaling scheme. Each signal point is assigned a mass proportional to its posterior probability at the particular instant. The center of gravity is used by the transmitter as a new origin for the signal space. It is shown that some previously considered coding schemes for channels with feedback are particular cases of center-of-gravity feedback. The probability of error decreases as a double exponential function of the coding delay as opposed to an exponential decrease for one-way systems. The effect of noise in the feedback path is briefly considered.     

Capacity of memoryless channels and block-fading channels with designable cardinality-constrained channel state feedback

A coding theorem is proved for memoryless channels when the channel state feedback of finite cardinality can be designed. Channel state information is estimated at the receiver and a function of the estimated channel state is causally fed back to the transmitter. The feedback link is assumed to be noiseless with a finite feedback alphabet, or equivalently, finite feedback rate. It is shown that the capacity can be achieved with a memoryless deterministic feedback and with a memoryless device which select transmitted symbols from a codeword of expanded alphabet according to current feedback. To characterize the capacity, we investigate the optimization of transmission and channel state feedback strategies. The optimization is performed for both channel capacity and error exponents. We show that the design of the optimal feedback scheme is identical to the design of scalar quantizer with modified distortion measures. We illustrate the optimization using Rayleigh block-fading channels. It is shown that the optimal transmission strategy has a general form of temporal water-filling in important cases. Furthermore, while feedback enhances the forward channel capacity more effectively in low-signal-to noise ratio (SNR) region compared with that of high-SNR region, the enhancement in error exponent is significant in both high- and low-SNR regions. This indicates that significant gain due to finite-rate channel state feedback is expected in practical systems in both SNR regions.     

A coding scheme for additive noise channels with feedback--I: No bandwidth constraint

In some communication problems, it is a good assumption that the channel consists of an additive white Gaussian noise forward link and an essentially noiseless feedback link. In this paper, we study channels where no bandwidth constraint is placed on the transmitted signals. Such channels arise in space communications. It is known that the availability of the feedback link cannot increase the channel capacity of the noisy forward link, but it can considerably reduce the coding effort required to achieve a given level of performance. We present a coding scheme that exploits the feedback to achieve considerable reductions in coding and decoding complexity and delay over what would be needed for comparable performance with the best known (simplex) codes for the one-way channel. Our scheme, which was motivated by the Robbins-Monro stochastic approximation technique, can also be used over channels where the additive noise is not Gaussian but is still independent from instant to instant. An extension of the scheme for channels with limited signal bandwidth is presented in a companion paper (Part II).     

Lower bounds on reliability functions of variable-length nonsystematic convolutional codes for channels with noiseless feedback

A variable-length, nonsystematic, convolutional encoding, and successive-decoding scheme is devised to establish significant improvements in the reliability functions of memoryless channels with noiseless decision feedback. It is shown that, for any but pathological discrete memoryless channels with noiseless feedback, there exists a variable-length convolutional code such that the reliability function of the channel can be bounded below by the channel capacityCfor all transmission rates less thanC. By employing a modified version of this scheme, it is also constructively shown that, for an additive-white-Gaussian-noise (AWGN) channel with noiseless feedback it is possible to find a variable-length convolutional code such that the channel reliability function can be bounded below byalpha_0 c_{infty}for all rates less than the channel capacityC_{infty}, wherealpha_0 = max (1, gamma/2)andgammais the maximum allowable expected-peak-to-expected-average-power ratio at the transmitter.     

Subband image coding using entropy-coded quantization over noisychannels

Under the assumption of noiseless transmission the authors develop two entropy-coded subband image coding schemes. The difference between these schemes is the procedure used for encoding the lowest frequency subband: predictive coding is used in one system and transform coding in the other. After demonstrating the unacceptable sensitivity of these schemes to transmission noise, the authors also develop a combined source/channel coding scheme in which rate-compatible convolutional codes are used to provide protection against channel noise. A packetization scheme to prevent infinite error propagation is used and an algorithm for optimal assignment of bits between the source and channel encoders of different subbands is developed. It is shown that, in the presence of channel noise, these channel-optimized schemes offer dramatic performance improvements     

Feedback communication using orthogonal signals

We consider a feedback communication system in which the forward and feedback channels are disturbed by additive noise and constrained in average power. Two block coding schemes are proposed in which the signals are orthogonal waveforms. A finite number of forward and feedback transmissions per message is made. Information received over the feedback channel is used to reduce the expected value of forward signal energy on all iterations after the first. Similarly, the expected value of feedback signal energy is reduced on all iterations after the first. These schemes, which are modifications of a feedback coding scheme due to Kramer, obtain improved error performance over one-way coding at all rates up to the forward channel capacity, provided only that the feedback channel capacity is greater than the forward channel capacity. They require less feedback power than existing feedback coding schemes to achieve a given error performance.     

A Simple Converse of Burnashev's Reliability Function

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.     

Asymptotic performance of a modified Schalkwijk-Barron scheme for channels with noiseless feedback (Corresp.)

A modified Schalkwijk-Barron transmission scheme is presented for channels with noiseless feedback. The modified scheme employs blockwise decision and a fixed length transmission in place of Viterbi's sequential decision feedback. The reliability functions of the modified scheme are derived for the additive white Gaussian noise (AWGN) channel and discrete memoryless channels (DMC's). For the AWGN channel the result obtained is asymptotically the same as in the case of the Schalkwijk-Barron scheme. On the other hand, the new result obtained for DMC's shows that the modified scheme also attains high reliability functions for DMC's.     

Adaptive entropy coded subband coding of images

The authors describe a design approach, called 2-D entropy-constrained subband coding (ECSBC), based upon recently developed 2-D entropy-constrained vector quantization (ECVQ) schemes. The output indexes of the embedded quantizers are further compressed by use of noiseless entropy coding schemes, such as Huffman or arithmetic codes, resulting in variable-rate outputs. Depending upon the specific configurations of the ECVQ and the ECPVQ over the subbands, many different types of SBC schemes can be derived within the generic 2-D ECSBC framework. Among these, the authors concentrate on three representative types of 2-D ECSBC schemes and provide relative performance evaluations. They also describe an adaptive buffer instrumented version of 2-D ECSBC, called 2-D ECSBC/AEC, for use with fixed-rate channels which completely eliminates buffer overflow/underflow problems. This adaptive scheme achieves performance quite close to the corresponding ideal 2-D ECSBC system.     

On the T-user M-frequency noiseless multiple-access channel with and without intensity information

Two specific noiseless multiple-access channel models, theT-userM-frequency multiple-access channel with and without intensity information, are studied in this paper. Information-theoretic bounds on the transmission rate for both models are presented. Constructive coding schemes are given for both channels which achieve zero error probability and whose rate sum is close to the information-theoretic bounds. Although the problem is formulated in terms of frequencies, the results are applicable to any signaling scheme where M orthogonal signals are used in each signaling interval including time partitioning of the interval.     

A coding scheme for additive noise channels with feedback--II: Band-limited signals

In Part I of this paper, we presented a scheme for effectively exploiting a noiseless feedback link associated with an additive white Gaussian noise channel with {em no} signal bandwidth constraints. We now extend the scheme for this channel, which we shall call the wideband (WB) scheme, to a band-limited (BL) channel with signal bandwidth restricted to(- W, W). Our feedback scheme achieves the well-known channel capacity,C = W ln (1 +P_{u,v}/N_{0} W), for this system and, in fact, is apparently the first deterministic procedure for doing this. We evaluate the fairly simple exact error probability for our scheme and find that it provides considerable improvements over the best-known results (which are lower bounds on the performance of sphere-packed codes) for the one-way channel. We also study the degradation in performance of our scheme when there is noise in the feedback link.     

On the reliability function of the ideal Poisson channel withnoiseless feedback

A coding scheme for the channel under peak power and average power constraints on the input is presented, and its asymptotic error exponent is shown to coincide, at all rates below capacity, with the sphere packing error exponent, which, for the case at hand, is known to be unachievable without feedback for rates below the critical rate. An upper bound on the error exponent achievable with feedback is also derived and shown, under a capacity reducing average power constraint, to coincide with the error exponent achieved by the proposed coding scheme; in such a case the coding scheme is asymptotically optimal. Thus, the ideal Poisson channel, limited by a capacity-reducing average power constraint, provides a nontrivial example of a channel for which the reliability function is known exactly both with and without feedback. It is shown that a slight modification of the coding scheme to one of random transmission time can achieve zero-error probability for any rate lower than the ordinary average-error channel capacity     

Repetitive signaling using a noisy feedback channel

Several feedback coding schemes considered recently are repetitive signaling schemes. The sender retransmits the message, if necessary, on the basis of information received over the feedback channel. This paper considers a repetitive signaling scheme in which the user's estimate of the transmitted message is sent over the feedback channel to the sender with high energy if the user is uncertain of the estimate and with lower energy if otherwise. The sender retransmits the message with high energy if it decides the user's estimate is incorrect. This scheme is applied to a wide-band, additive-white-Gaussian-noise, average-power-constrained feedback communication system. Orthogonal signals are used for transmission over both forward and feedback channels. A lower bound is obtained for the probability of error when arbitrary decision rules are used. This lower bound is achieved asymptotically for long block duration by using decision rules implemented with correlation receivers. The resulting asymptotic error performance is superior to that of any feedback coding scheme previously considered for use in a wide-band additive-white-Gaussian-noise system for any values of the forward and feedback channel capacities.     

Extended balanced space-time block coding for wireless communications

Diversity techniques are very effective tools to increase signal reception quality in Rayleigh fading channels. A well-known method to increase diversity in multi-input multi-output (MIMO) communication is transmit antenna selection (TAS). However, TAS is very sensitive to feedback errors. One of the alternative techniques to TAS is balanced space-time block coding (BSTBC) which guarantees full diversity for any number of transmit antennas, provided that few bits of feedback from the destination to the source are available. The main drawback of the BSTBC is limited coding gain since few numbers of code matrices can be generated in the originally proposed scheme. In this work, the authors extend the balanced space-time block code family to improve its coding performance. In our proposed scheme, larger number of codes can be generated for improved coding gain. The performance of the proposed scheme is investigated for both multi-input singleoutput (MISO) and cooperative communication cases. Relay selection (RS) algorithm - the TAS equivalent in the cooperative communications - is also considered. Simulation results show that near optimal (infinite feedback) performance can be achieved with four bit extension of the BSTBC and better signal-to-noise ratio can be obtained compared to TAS or RS schemes. The difference in performance becomes more prevalent in the presence of feedback errors.