Bounds on the symmetric cutoff rate for QAM transmissions overtime-correlated flat-faded channels

This article presents new upper and lower bounds on the symmetric cutoff rate for block-coded quadrature-amplitude-modulated (QAM) signaling over links affected by time-correlated Rayleigh-distributed flat-faded phenomena. The proposed bounds assume maximum-likelihood soft-decoding with perfect channel-state-information at the receiving side and hold for any form of QAM constellations. These bounds are quickly computable and constitute an efficient means to estimate the cutoff rate of systems employing very long codewords, so that an exact evaluation of the cutoff rate results. Analytical and numerical evidence of the tightness of the presented bounds is also provided     

On the generalized symmetric cutoff rate for finite-state channels

Finite-state discrete-time channels with equiprobable M-ary inputs are considered. The generating function bound, which is ubiquitously applied to upper-bound the error probability of uncoded signaling over these channels, is used here to lower-bound the corresponding generalized symmetric cutoff rate, which lower-bounds the practically achievable rates and error exponents in these channels with symmetric signaling. The bound accounts for general additive metrics. For the special case of the optimal maximum-likelihood metric, the corresponding bound is shown to be asymptotically tight in the region where the symmetric cutoff rate approaches its maximum value of log₂ M (bits-per-channel use). For a finite-state additive white Gaussian noise (AWGN) channel this feature is used to relate the minimum Euclidean distance of an uncoded symmetric system to the corresponding symmetric cutoff rate. The results are demonstrated for AWGN channels corrupted by linear and nonlinear intersymbol interference. They are also used to assess the efficiency of concatenated coding over the 4-ary AWGN channel where the finite-state mechanism is defined by simple rate 1/2, four-state Ungerboeck 4-AM trellis code     

Bounds on aperiodic cross-correlation for binary sequences

Results are presented which relate the mean-squared value of the aperiodic crosscorrelation function for periodic binary sequences to their aperiodic autocorrelation function. Bounds on the mean-squared aperiodic crosscorrelation are given in terms of the mean-squared aperiodic autocorrelation.     

Bounds on the reliability of binary coherent systems

The structure function of a binary coherent system is approximated by using only a few of its minimal path sets and minimal cut sets. These two incomplete structure functions are represented as disjoint sums. The average of each is a lower and upper bound, respectively, for the system reliability. The usefulness of these bounds is demonstrated on example networks     

Bounds on the redundancy of binary alphabetical codes

An alphabetical code is a code in which the numerical binary order of the codewords corresponds to the alphabetical order of the encoded symbols. A necessary and sufficient condition for the existence of a binary alphabetical code is presented. The redundancy of the optimum binary alphabetical code is given in comparison with the Huffman code and its upper bound, which is tighter than bounds previously reported, is presented. The redundancy of the optimal alphabetical code is about 5% in comparison with the Huffman coding, which shows the usefulness of the alphabetical code     

The cutoff rate for on-off keying

It is well known that on-off keying (OOK), i.e. the transmission of a pulse for a data one (mark) and transmission of no signal for a data zero (space), exhibits a 3 dB inferiority to antipodal signalling, in terms of the signal-to-noise ratio required to achieve a specified bit error probability. When the channel is characterized by the cutoff rate R₀, this 3 dB inferiority persists, in the sense that the required E_b/N₀ to operate at a given value of R₀ is 3 dB greater for the OOK channel than for the antipodal channel. However, it is shown that, if the definition of cutoff rate is generalized in an appropriate way to reflect the fact that signal energy is expended only in the transmission of marks, part of this penalty is recovered. In fact, it is shown that, in the limit of low R₀, there is no penalty in signal-to-noise ratio. Even at rates of realistic interest, the penalty is significantly less than the expected 3 dB     

Bounds on mixed binary/ternary codes

Upper and lower bounds are presented for the maximal possible size of mixed binary/ternary error-correcting codes. A table up to length 13 is included. The upper bounds are obtained by applying the linear programming bound to the product of two association schemes. The lower bounds arise from a number of different constructions     

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |E_J| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |E_J|, one would need to perform the direct enumeration of error patterns with weight ι ⩽ J. The complexity of enumeration increases exponentially with J, essentially as η^J, where η is the code block length. This limits the application of direct enumeration to codes with small η and J. In this letter, we approximate J and |E_J | by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.     

Capacity and cutoff rate for Poisson-type channels

The capacity of a Poisson-type channel subject both to peak amplitude and average energy constraints is calculated, and its relation to the cutoff rate given by Snyder and Rhodes is determined in the "very noisy" case.     

A lower bound on the cutoff rate for Gaussian channels withpeak-limited inputs

A lower bound on the cutoff rate R_O of a dispersive Gaussian channel with peak- rather than average-power-limited input is evaluated and compared to the lower bound on capacity under the same input constraints. It is assumed that the input symbols are independent and uniformly distributed. Both bounds exhibit the same behavior as a function of an appropriately defined signal-to-noise ratio (SNR), with a discrepancy of 1.68 dB to the disadvantage of R_O, at high SNRs. The lower bound on R_O is evaluated for peak- and slope-limited signals that model magnetic recording systems and is compared to the lower bound on capacity     

Bounds for binary codes of length less than 25

Improved bounds forA(n,d), the maximum number of codewords in a (linear or nonlinear) binary code of word lengthnand minimum distanced, and forA(n,d,w), the maximum number of binary vectors of lengthn, distanced, and constant weightwin the rangen leq 24andd leq 10are presented. Some of the new values areA     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

Raptor codes on binary memoryless symmetric channels

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.     

Channel combining and splitting for cutoff rate improvement

The cutoff rate R₀(W) of a discrete memoryless channel (DMC) W is often used as a figure of merit alongside the channel capacity C(W). If a channel W is split into two possibly correlated subchannels W₁, W₂, the capacity function always satisfies C(W₁)+C(W₂)lesC(W), while there are examples for which R₀(W₁)+R₀(W₂ )>R₀(W). The fact that cutoff rate can be "created" by channel splitting was noticed by Massey in his study of an optical modulation system. This paper gives a general framework for achieving similar gains in the cutoff rate of arbitrary DMCs by methods of channel combining and splitting. The emphasis is on simple schemes that can be implemented in practice. We give several examples that achieve significant gains in cutoff rate at little extra system complexity. Theoretically, as the complexity grows without bound, the proposed framework is capable of boosting the cutoff rate of a channel to arbitrarily close to its capacity in a sense made precise in the paper. Apart from Massey's work, the methods studied here have elements in common with Forney's concatenated coding idea, a method by Pinsker for cutoff rate improvement, and certain coded-modulation techniques, namely, Ungerboeck's set-partitioning idea and Imai-Hirakawa multilevel coding; these connections are discussed in the paper     

EXIT functions for binary input memoryless symmetric channels

Use of extrinsic information transfer (EXIT) functions, characterizing the amplification of mutual information between the input and output of the maximum a posteriori (MAP) decoder, significantly facilitates analysis of iterative coding schemes. Previously, EXIT functions derived for binary erasure channels (BECs) were used as an approximation for other channels. Here, we improve on this approach by introducing more accurate methods to construct EXIT functions for binary-input memoryless symmetric (BMS) channels. By defining an alternative pseudo-MAP decoder coinciding with the MAP decoder over BEC, we provide an expression for the EXIT functions of block codes over BEC. Furthermore, we draw a connection between the EXIT function over BEC and the EXIT function over the BMS channel under certain conditions. This is used for deriving accurate or approximate expressions of EXIT functions over BMS channels in certain scenarios.     

Encoding of analog signals for binary symmetric channels

Various encoding schemes are examined from the point of view of minimizing the mean magnitude error of a signal caused by transmission through a binary symmetric channel. A necessary property is developed for optimal codes for any binary symmetric channel and any set of quantization levels. The class of optimal codes is found for the case where the probability of error is small but realistic. This class of codes includes the natural numbering and some unit distance codes, among which are the Gray codes.     

Integer metrics for binary input symmetric output memorylesschannels

Consider a coded communication system where antipodal signaling is used over symmetric memoryless channels. A mismatch decoder employing metrics which assume values in a finite set of integers is used. Two performance measures for achievable rates are considered, the generalized cutoff rate and the mismatch capacity. Two different integer metric assignments which maximize these criteria are found. The optimal metric assignment holds for any binary input symmetric output memoryless channels. It is calculated explicitly for the faded additive white Gaussian noise channel with and without diversity, an interference channel model and the additive “Cauchy” channel. The difference in terms of achievable rates between decoding using the optimal continuous metric and integer metric is calculated for these channels. The degradation for fairly low number of quantization levels is found to be small, e.g. for nine quantization levels degradation is less than 0.3 dB for all analyzed channels. The sensitivity of the generalized cutoff rate and the mismatch capacity to the exact location of the quantization levels is rather mild. The difference between the mismatch capacity corresponding to the optimal integer quantization and the mismatch capacity obtained by the quantization which optimizes the generalized cutoff rate is found to be quite small     

Coding for the binary symmetric broadcast channel with two receivers

Block coding for the binary symmetric broadcast channel with two receivers is investigated. A graph-theoretic approach to the construction of a class of block codes with unequal error protection for two different sets of messages is presented. A code in this class is a direct sum of two component codes; each set of messages is encoded based on one component code. The codes in this class are easy to implement. Decoding of these codes is presented, and lower bounds on the achievable rates of these codes are derived. The bounds are tighter than the Katsman's bounds.     

An upper bound on the cutoff rate of sequential decoding

An upper bound is given on the cutoff rate of discrete memoryless channels. This upper bound, which coincides with a known lower bound, determines the cutoff rate, and settles a long-standing open problem     

Capacity and cutoff rate calculations for a concatenated codingsystem

A model is developed for a concatenated coding system, and from it the overall channel cutoff rate and capacity is found using random coding arguments. The effects of interleaving between the inner and outer codes and of the availability of side information to the outer decoder are considered. The performance of several specific concatenated coding systems is calculated and used for comparison with the random coding result. From the analysis, a number of general conclusions regarding the design of concatenated coding systems are presented. All the results are derived assuming a block inner code