ERROR-DETECTING CODES AND UNDETECTED ERROR PROBABILITIES

The definition of good codes for error-detection is given. It is proved that a (n, k) linear block code in GF(q) are the good code for error-detection, if and only if its dual code is also. A series of new results about the good codes for error-detection are derived. New lower bounds for undetected error probabilities are obtained, which are relative to n and k only, and not the weight structure of the codes.     

Bounds on the undetected error probabilities of linear codes forboth error correction and detection

The author investigates the (n, k, d⩾2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) [2^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

A simple derivation of the undetected error probabilities of complementary codes

Recently, Fu, Klove, and Wei (2003) have shown that the undetected error probability of a binary code is related to that of its complement, and the undetected error probability of a constant-weight binary code is related to that of its complement relative to the set of all constant-weight vectors. We generalize these relations to cover the complements of any binary or nonbinary code relative to a distance-invariant code containing the first code. We prove the generalization using a much simpler argument than the published proofs of the special cases.     

On the undetected error probability for binary codes

In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's (1997) lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.     

On weak convergence of probability measures, channel capacity andcode error probabilities

The relationship between weak convergence of channel probability measures, channel capacity, and error probability of block codes is examined for memoryless channels with general input and output alphabets. It is shown that channel capacity is a lower semi-continuous function and that every block code with maximal probability of error δ for a nominal channel for any ϵ>0 can be modified such that the modification has a probability of error less than δ+ϵ for all channels in a sufficiently small neighborhood of the nominal channel     

On the undetected error probability of nonlinear binary constantweight codes

The undetected error probability (UEP) of binary (n, 2δ, m) nonlinear constant weight codes over the binary symmetric channel (BSC) is investigated, where n is the blocklength, m is the weight of codeword and 2δ is the minimum distance of the codes. The distance distribution of the (n, 2, m) nonlinear constant weight codes is evaluated. It is proven in this paper that the (5, 2, 2) code, (5, 2, 3) code, (6, 2, 3) code, (7, 2, 4) code, (7, 2, 3) code and (8, 2, 4) code are the only proper error-detecting codes in the (n, 2, m) nonlinear constant weight codes for n⩾5, in the sense that their UEP is increased monotonically with the channel error rate p, of course all these proper codes are m-out-of-n codes. Furthermore, it is conjectured that except for the cases of n⩽4δ, there are no proper error-detecting binary (n, 2δ, m) nonlinear constant weight codes, for n>8 and δ⩾1     

Bounds on the worst case probability of undetected error

Upper and lower bounds on the average worst-case probability of undetected error for linear [n,k,q] codes are given     

The worst case probability of undetected error for linear codes onthe local binomial channel

The worst case probability of undetected error for a linear [n,k:q] code used on a local binomial channel is studied. For the two most important cases it is determined in terms of the weight hierarchy of the code. The worst case probability of undetected error is determined explicitly for some classes of codes     

Generic error probabilities

This paper presents new forms for an error probability associated, with the phase angle between two vectors perturbed by Gaussian noise. An interesting consequence of the underlying generic form is a new expression for the symbol error rate in MDPSK that is very similar to its counterpart for MPSK. The generic error probability is further shown to contain as special cases MPSK, MDPSK, CPFSK, and digital FM; and to give a new expression for the Marcum Q-function. The generic error probability also simplifies the error probability expressions in other situations such as nonorthogonal signaling, maximum likelihood differential detection of DPSK with block-by-block detection, and Gray coding of MDPSK     

On error probabilities of DS-CDMA systems with arbitrary chipwaveforms

The error probabilities of asynchronous DS-CDMA systems using random signature sequences depend on the number of users, the processing gain and the chip waveforms employed. The exact calculation of the error probabilities is computationally difficult and therefore approximations and bounds are more commonly used. In this article, the improved Gaussian approximation proposed by Holtzman (1992) is extended to include arbitrary chip waveforms. Comparisons to the exact calculation and the standard Gaussian approximation are also made to evaluate the accuracy of the improved Gaussian approximation     

On some properties of the undetected error probability of linear codes (Corresp.)

A recent paper [1] discussed the2^{-p}bound (wherep = n- k) for the probability of undetected errorP(epsilon)for an(n,k)block code used for error detection on a binary symmetric channel. This investigation is continued and extended and dual codes are studied. The dual and extension of a perfect code obey the2^{-p}bound, but this is not necessarily true for arbitrary codes that obey the bound. Double-error-correcting BCH codes are shown to obey the bound. Finally the problem of constructing uniformly good codes is examined.     

Further results on the bit error probabilities of MDPSK over thenonselective Rayleigh fading channel with diversity reception

This paper presents a fundamental approach for deriving the bit error probability of BDPSK and QDPSK over the nonselective Rayleigh fading channel for a receiver with an arbitrary IF filter, and for a fading process with an arbitrary Doppler spectrum with arbitrary Doppler bandwidth. The results generalize those published earlier which were restricted to matched filter reception and to a fading process with a small Doppler bandwidth compared to the symbol rate. This allows the error probability to be studied in the presence of varying degrees of ISI due to the bandlimitation of the received signal by the IF filter, and in the presence of fading fluctuations of various rates. The analytical approach presented is simple, and yet powerful in that it can handle the case of diversity reception. This is a great advantage over the alternative approach of using the distribution of the differential phase of the received signal over a symbol interval. The bit error probability results apply to both conventional BDPSK and QDPSK, as well as π/2-2DPSK and π/4-4DPSK, and allow the irreducible bit error probability as well as the SNR at which this irreducible value sets in to be studied as a function of the Doppler bandwidth and IF filter bandwidth. The computed results are applicable to the design of digital cellular mobile communication systems     

Computing the probability of undetected error for shortened cycliccodes

The authors present a general technique for computing P _e for all possible shortened versions of cyclic codes generated by any given polynomial. The technique is recursive, i.e. computes P_e for a given code block length n from that of the code block length n-1. The proposed computation technique for determining P_e does not require knowledge of the code weight distributions. For a generator polynomial of degree r, and |g| nonzero coefficients, the technique yields P_e for all code block lengths up to length n in time complexity O(n|g |2^r+|g|). Channels with variable bit error probabilities can be analyzed with the same complexity. This enables the performance of the code generator polynomials to be analyzed for burst errors     

A lower bound on the undetected error probability and strictlyoptimal codes

Error detection is a simple technique used in various communication and memory systems to enhance reliability. We study the probability that a q-ary (linear or nonlinear) block code of length n and size M fails to detect an error. A lower bound on this undetected error probability is derived in terms of q, n, and M. The new bound improves upon other bounds mentioned in the literature, even those that hold only for linear codes. Block codes whose undetected error probability equals the new lower bound are investigated. We call these codes strictly optimal codes and give a combinatorial characterization of them. We also present necessary and sufficient conditions for their existence. In particular, we find all values of n and M for which strictly optimal binary codes exist, and determine the structure of all of them. For example, we construct strictly optimal binary-coded decimal codes of length four and five, and we show that these are the only possible lengths of such codes     

Concerning a bound on undetected error probability (Corresp.)

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.     

Tight bounds on Rician-type error probabilities and someapplications

Consider the classic problem of evaluating the probability that one Rician random variable exceeds another, possibly correlated, Rician random variable. This probability is given by Stein (1964) in terms of the Marcum's Q-function, which requires numerical integration on the computer for its evaluation. To facilitate application in many digital communication problems, we derive here tight upper and lower bounds on this probability. The bounds are motivated by a classic result in communication theory, namely, the error probability performance of binary orthogonal signaling over the Gaussian channel with unknown carrier phase. Various applications of the bounds are reported, including the evaluation of the bit error probabilities of MDPSK and MPSK with differential detection and generalized differential detection, respectively. The bounds prove to be tight in all cases. Further applications will be reported in the future     

Exponential-type error probabilities for multiterminal hypothesistesting

Multiterminal hypothesis testing is considered, subject to the exponential-type constraint α_n⩽exp(-nr) on the error probability of the first kind. The problem is to determine the minimum β*_n of the error probability of the second kind under the given constraint at limited rates R₁ and R₂ for observing the respective pairs of variables. Good lower bounds on the power exponent for β*_n are presented by invoking basic properties of r-divergent sequences. In particular, the one-bit and the zero-rate compression cases are considered. The power exponent for the former and a lower bound for the latter are established     

Calculation of error probabilities for distance-invariant nonlinear error control codes

Expressions are given for the distance distribution of some nonlinear codes which enable error probabilities to be calculated using methods commonly associated with linear error control codes.<>     

Efficiency of error-control schemes for real-time wireless applications on the Gilbert channel

The design of a bandwidth-efficient physical layer for wireless access has always been a challenging task, due to the harsh environment, characterized by impairing phenomena such as radio interference, fading, and shadowing. With circuit switching, a bit-error rate suitable for real-time applications such as voice and video is guaranteed by adopting robust forward error correction (FEC) codes and proper power-budget margins to face fading problems. With this approach, automatic repeat request (ARQ) is used only for applications that require a much lower error rate and can tolerate high delays. The introduction of the packet technique allows the use of ARQ even for real-time traffic. We compare the efficiency of three error-recovering techniques in the presence of traffic with delay constraints, when the memory property of the wireless segment is represented by the Gilbert-Elliot channel. The techniques compared are FEC with interleaving, real-time ARQ, and erasure coding (EC). The comparisons are performed by using both analytical and simulation tools. Two new analytical models are introduced to evaluate the performance of FEC and EC. Simulation is used to validate the analytical results and to derive the performance of real-time ARQ. The numerical results show that when the channel memory increases well beyond the packet-transmission time, the performance of FEC impairs due to the limited interleaving depth, while ARQ and EC remain effective.