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     

Gallager?s Exponent for MIMO Channels: A Reliability-Rate Tradeoff

In this paper, we derive Gallager's random coding error exponent for multiple-input multiple-output (MIMO) Rayleigh block-fading channels, assuming no channel-state information (CSI) at the transmitter and perfect CSI at the receiver. This measure gives insight into a fundamental tradeoff between the communication reliability and information rate of MIMO channels, enabling to determine the required codeword length to achieve a prescribed error probability at a given rate below the channel capacity. We quantify the effects of the number of antennas, channel coherence time, and spatial fading correlation on the MIMO exponent. In addition, the general formulae for the ergodic capacity and the cutoff rate in the presence of spatial correlation are deduced from the exponent expressions. These formulae are applicable to arbitrary structures of transmit and receive correlation, encompassing all the previously known results as special cases of our expressions.     

Sequential decoding based on an error criterion

An analysis of sequential decoding is presented that is based on the requirement that a set probability error P_e be achieved. The error criterion implies a bounded tree or trellis search region: the shape of this is calculated for the case of a binary symmetric channel with crossover probability P and random tree codes of rate R. Since the search region is finite at all combinations of p and R below capacity, there is no cutoff rate phenomenon for any P_e>0. The decoder delay (search depth), the path storage size, and the number of algorithm steps for several tree search methods are calculated. These include searches without backtracking and backtracking searches that are depth- and metric-first. The search depth of the non-backtracking decoders satisfies the Gallager reliability exponent for block codes. In average paths searched, the backtracking decoders are much more efficient, but all types require the same peak storage allocation. Comparisons are made to well-known algorithms     

Variable length coding over an unknown channel

Burnashev in 1976 gave an exact expression for the reliability function of a discrete memoryless channel (DMC) with noiseless feedback. A coding scheme that achieves this exponent needs, in general, to know the statistics of the channel. Suppose now that the coding scheme is designed knowing only that the channel belongs to a family Q of DMCs. Is there a coding scheme with noiseless feedback that achieves Burnashev's exponent uniformly over Q at a nontrivial rate? We answer the question in the affirmative for two families of channels (binary symmetric, and Z). For these families we show that, for any given fraction, there is a feedback coding strategy such that for any member of the family: i) guarantees this fraction of its capacity as rate, and ii) guarantees the corresponding Burnashev's exponent. Therefore, for these families, in terms of delay and error probability, the knowledge of the channel becomes asymptotically irrelevant in feedback code design: there are blind schemes that perform as well as the best coding scheme designed with the foreknowledge of the channel under use. However, a converse result shows that, in general, even for families that consist of only two channels, such blind schemes do not exist.     

Coding theorems for the nonsynchronized channel

Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length.     

Relations Between Random Coding Exponents and the Statistical Physics of Random Codes

The partition function pertaining to finite-temperature decoding of a (typical) randomly chosen code is known to have three types of behavior, corresponding to three phases in the plane of rate versus temperature: the ferromagnetic phase, corresponding to correct decoding, the paramagnetic phase, of complete disorder, which is dominated by exponentially many incorrect codewords, and the glassy phase (or the condensed phase), where the system is frozen at minimum energy and dominated by subexponentially many incorrect codewords. We show that the statistical physics associated with the two latter phases are intimately related to random coding exponents. In particular, the exponent associated with the probability of correct decoding at rates above capacity is directly related to the free energy in the glassy phase, and the exponent associated with probability of error (the error exponent) at rates below capacity, is strongly related to the free energy in the paramagnetic phase. In fact, we derive alternative expressions of these exponents in terms of the corresponding free energies, and make an attempt to obtain some insights from these expressions. Finally, as a side result, we also compare the phase diagram associated with a simple finite-temperature universal decoder, for discrete memoryless channels, to that of the finite-temperature decoder that is aware of the channel statistics.      

A low-rate bound on the reliability of a quantum discrete memoryless channel

We extend a low-rate improvement of the random coding bound on the reliability of a classical discrete memoryless channel (DMC) to its quantum counterpart. The key observation that we make is that the problem of bounding below the error exponent for a quantum channel relying on the class of stabilizer codes is equivalent to the problem of deriving error exponents for a certain symmetric classical channel.     

Error probability and free distance bounds for two-user tree codes on multiple-access channels

Two-user tree codes are considered for use on an arbitrary two-user discrete memoryless multiple-access channel (MAC). A two-user tree Is employed to achieve true maximum likelihood (ML) decoding of two-user tree codes on MAC's. Each decoding error event has associated with it a configuration indicating the specific time slots in which a decoding error has occurred for the first user alone, for the second user alone, or for both users simultaneously. Even though there are many possible configurations, it is shown that there are five fundamental configuration types. An upper bound on decoding error probability, similar to Liao's result for two-user block codes, is derived for sets of error events having a particular configuration. The total ML decoding error probability is bounded using a union bound first over all configurations of a given type and then over the five configuration types. A two-user tree coding error exponent is defined and compared with the corresponding block coding result for a specific MAC. It is seen that the tree coding error exponent is larger than the block coding error exponent at all rate pairs within the two-user capacity region. Finally, a new lower bound on free distance for two-user codes is derived using the same general technique used to bound the error probability.     

A Class of Soft Decision Error Detectors for the Gaussian Channel

The main idea of this concise paper is to use symbol reliability information for improving the performance of error detectors. A class of soft decision error detectors (SDED's) is presented, where low weight error patterns are selectively corrected. The reliability numbers govern which error pattern to correct. Asymptotic performance and bounds are derived for the Gaussian channel. It is shown that singleerror correcting SDED's without thresholds have an exponentially lower repeat request probability than the hard decision error detector, but the same exponent in the probability of undetected errors. Detectors with thresholds are also considered. In this case it is possible to contruct an error detector with both better probability of undetected errors and better probability of repeat request than for the hard decision error detector (HDED). Bounds and computer simulations are presented and SDED's are compared to HDED's.     

High-SNR Analysis of Outage-Limited Communications With Bursty and Delay-Limited Information

This work analyzes the high-SNR asymptotic error performance of outage-limited communications with fading, where the number of bits that arrive at the transmitter during any timeslot is random but the delivery of bits at the receiver must adhere to a strict delay limitation. Specifically, bit errors are caused by erroneous decoding at the receiver or violation of the strict delay constraint. Under certain scaling of the statistics of the bit-arrival process with SNR, this paper shows that the optimal decay behavior of the asymptotic total probability of bit error depends on how fast the burstiness of the source scales down with SNR. If the source burstiness scales down too slowly, the total probability of error is asymptotically dominated by delay-violation events. On the other hand, if the source burstiness scales down too quickly, the total probability of error is asymptotically dominated by channel-error events. However, at the proper scaling, where the burstiness scales linearly with ${{ 1}over { sqrt {log {rm SNR} }}}$ and at the optimal coding duration and transmission rate, the occurrences of channel errors and delay-violation errors are asymptotically balanced. In this latter case, the optimal exponent of the total probability of error reveals a tradeoff that addresses the question of how much of the allowable time and rate should be used for gaining reliability over the channel and how much for accommodating the burstiness with delay constraints.      

Universal decoding for finite-state channels

Universal decoding procedures for finite-state channels are discussed. Although the channel statistics are not known, universal decoding can achieve an error probability with an error exponent that, for large enough block length (or constraint length in case of convolutional codes), is equal to the random-coding error exponent associated with the optimal maximum-likelihood decoding procedure for the given channel. The same approach is applied to sequential decoding, yielding a universal sequential decoding procedure with a cutoff rate and an error exponent that are equal to those achieved by the classical sequential decoding procedure.     

衰落信道上TAS/MRC的错误指数

使用梅哲-G 函数,推导了Nakagami-m 衰落发射天线选择（TAS）/最大比合并（MRC）系统的随机编码错误指数（RCEE）、遍历容量、截止速率、删改指数的精确表达式。计算结果表明,Nakagami-m衰落TAS/MRC系统的错误指数与信道衰落参数、信道编码速率、收发天线数目、信道相干时间等因素有关。信道衰落系数越大、编码速率越大、收发天线数目越多,通信系统的RCEE越大,相应的译码错误概率越小,系统的通信可靠性越高。对于给定译码错误概率的MIMO无线通信系统,可以通过计算系统的RCEE来估计信道所需的编码长度、收发天线数目、信道相干时间和空间衰落相关时的编码需求。     

On the Impact of HDLC Zero Insertion and Deletion on Link Utilization and Reliability

In HDLC, a zero is inserted after every five consecutive "ones" in order to resolve ambiguity about the location of delimiters. In this paper, we generalize the number "five" as an arbitrary positive integernand study the impacts ofnon the link utilization for a noiseless channel and on the reliability for a noisy channel. The entropy of the sequence after this generalized zero insertion is found for a noiseless channel. An expression for the optimalnthat maximizes a quantity called the delimiter efficiency is also found in terms of the frame size. It is shown thatn = 5achieves a delimiter efficiency close (within 2 percent) to that achievable by the optimaln. For a noisy channel, the reliability of HDLC is derived. It is shown that the probability of an undetectable error in HDLC is dominated by the errors that propagate through a created flag or incorrect zero deletion, and is in the neighborhood of 10^-7for typical parameters. Increasingnby 8 is shown to improve the reliability by two orders of magnitude. It is proposed to use a two byte flag and a four byte frame check sequence to improve the reliability by seven orders of magnitude.     

Multibeam cellular communication systems with dynamic channel assignment across multiple sectors

In cellular communication systems, directional multibeam antennas at cell sites can be used to reduce cochannel interference, increase frequency reuse and improve system capacity. When combined with dynamic channel assignment (DCA), additional improvement is possible. We propose a multibeam scheme using dynamic channel assignment across multiple sectors. A cell is divided into several sectors, each of which is covered by several directional beams. Specific channels are allocated to each sector as in fixed channel assignment (FCA). A channel of a sector is dynamically assigned to a wireless user who communicates through one of the several beams of the sector. The assignment is made so that constraints on the allowable cochannel interference are satisfied. Limitations due to cochannel interference are analyzed. A tractable analytical model for the proposed scheme is developed using multidimensional birth–death processes. Theoretical traffic performance characteristics such as call blocking probability, forced termination probability, handoff activity, carried traffic and channel rearrangement rate are determined. With the proposed scheme, call blocking probability can be reduced significantly for a fixed offered traffic. Alternatively, system capacity can be increased while blocking probability is maintained below the required level. Smaller forced termination probability is obtainable in comparison with corresponding FCA schemes.     

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.     

Asymptotical analysis and comparison of two coded modulationschemes using PSK signaling .I

An asymptotical analysis and comparison of two coded modulation systems using phase-shift keying (PSK) signaling with the transmission taking place over the additive white Gaussian noise (AWGN) channel is provided. In this paper, bounds for the decoding error probability of conventional coded modulation are derived. Both block and trellis coding are considered. The state-complexity error exponent is introduced     

MIMO Channels in the Low-SNR Regime: Communication Rate, Error Exponent, and Signal Peakiness

We consider multiple-input multiple-output (MIMO) fading channels and characterize the reliability function in the low signal-to-noise (SNR) regime as a function of the number of transmit and receive antennas. For the case when the fading matrix H has independent entries, we show that the number of transmit antennas plays a key role in reducing the peakiness in the input signal required to achieve the optimal error exponent for a given communication rate. Further, by considering a correlated channel model, we show that the maximum performance gain (in terms of the error exponent and communication rate) is achieved when the entries of the channel fading matrix are fully correlated. The results we presented in this work in the low-SNR regime can also be applied to the infinite bandwidth regime     

Capacity and error exponent for the direct detection photonchannel. II

For pt.I see ibid., vol.34, no.6, p.1449-61 (1980). The discussion of the capacity and error exponent of the direct detection optical channel is continued. The channel input in a T-second interval is a waveform satisfying certain peak and average power constraints for the optical signals. The channel output is a Poisson process with an intensity parameter that accounts for the dark-current component. An upper bound is obtained on the error exponent which coincides with the lower bound. Thus, this channel is one for which the error exponent can be known exactly     

Improved error exponent for time-invariant and periodicallytime-variant convolutional codes

An improved upper bound on the error probability (first error event) of time-invariant convolutional codes, and the resulting error exponent, is derived. The improved error bound depends on both the delay of the code K and its width (the number of symbols that enter the delay line in parallel) b. Determining the error exponent of time-invariant convolutional codes is an open problem. While the previously known bounds on the error probability of time-invariant codes led to the block-coding exponent, we obtain a better error exponent (strictly better for b>1). In the limit b→∞ our error exponent equals the Yudkin-Viterbi (1967, 1971, 1965) exponent derived for time-variant convolutional codes. These results are also used to derive an improved error exponent for periodically time-variant codes     

On the Effect of Timing Errors in Run Length Codes

Many redundancy removal algorithms employ some sort of run length code. Blocks of timing words are coded with synchronization words inserted between blocks. The probability of incorrectly reconstructing a sample because of a channel error in the timing data is a monotonically nondecreasing function of time since the last synchronization word. In this paper we compute the "probability that the accumulated magnitude of timing errors equal zero" as a function of time since the last synchronization word for a zero-order predictor (ZOP). The result is valid for any data source that can be modeled by a first-order Markov chain and any digital channel that can be modeled by a channel transition matrix. An example is presented.