Composition bounds for channel block codes

The performance of Channel block codes for a general channel is studied by examining the relationship between the rate of a code, the joint composition of pairs of codewords, and the probability of decoding error. At fixed rate, lower bounds and upper bounds, both on minimum Bhattacharyya distance between codewords and on minimum equivocation distance between codewords, are derived. These bounds resemble, respectively, the Gilbert and the Elias bounds on the minimum Hamming distance between codewords. For a certain large class of channels, a lower bound on probability of decoding error for low-rate channel codes is derived as a consequence of the upper bound on Bhattacharyya distance. This bound is always asymptotically tight at zero rate. Further, for some channels, it is asymptotically tighter than the straight line bound at low rates. Also studied is the relationship between the bounds on codeword composition for arbitrary alphabets and the expurgated bound for arbitrary channels having zero error capacity equal to zero. In particular, it is shown that the expurgated reliability-rate function for blocks of letters is achieved by a product distribution whenever it is achieved by a block probability distribution with strictly positive components.     

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.     

Location-correcting codes

We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(√(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t∈{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded     

The serial concatenation of rate-1 codes through uniform random interleavers

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.     

On decoding of low-density parity-check codes over the binary erasure channel

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.     

Tradeoff between source and channel coding on a Gaussian channel

Consider a system that quantizes and encodes analog data for transmission across an additive noise Gaussian channel. To minimize distortion, the channel code rate must be chosen to optimally allocate the available transmission rate between lossy source coding and block channel coding. We establish tight upper and lower bounds on the channel code rate that minimizes the average distortion of a vector quantizer cascaded with a channel coder and a Gaussian channel, thus extending some recently obtained results for the binary-symmetric channel. The upper hounds are obtained by averaging, whereas the lower bounds are uniform, over all possible index assignments. Analytic expressions are derived for large and small signal-to-noise ratios, and also for large source vector dimension. As in the binary-symmetric channel, the optimal channel code rate is often substantially smaller than the channel capacity and the distortion decays exponentially with the number of channel uses. Exact exponents are derived     

Upper bounds on the rate of LDPC codes as a function of minimum distance

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.     

Error Control Codes for Parallel Asymmetric Channels

We consider transmission of messages encoded into binary matrices to be send over a parallel asymmetric channel. Two different channel models are introduced. They depend on the conditions on errors in the subchannels. For each channel model codes are constructed for error correction and for error detection and bounds are derived.     

Performance of quantizers on noisy channels using structuredfamilies of codes

Achievable distortion bounds are derived for the cascade of structured families of binary linear channel codes and binary lattice vector quantizers. It is known that for the cascade of asymptotically good channel codes and asymptotically good vector quantizers the end-to-end distortion decays to zero exponentially fast as a function of the overall transmission rate, and is achieved by choosing a channel code rate that is independent of the overall transmission rate. We show that for certain families of practical channel codes and binary lattice vector quantizers, the overall distortion can be made to decay to zero exponentially fast as a function of the square root of transmission rate. This is achieved by carefully choosing a channel code rate that decays to zero as the transmission rate grows. Explicit channel code rate schedules are obtained for several well-known families of channel codes     

Low-rate super-orthogonal channel coding for fiber-optic CDMAcommunication systems

In this paper, we consider using practical low-rate error correcting codes in fiber-optic code division multiple-access (CDMA) communication systems. To this end, a different method of low-rate channel coding is proposed. As opposed to the conventional coding schemes, this method does not require any further bandwidth expansion for error correction in fiber-optic CDMA communication systems. The low-rate channel codes that are used for demonstrating the capabilities of the proposed method are super-orthogonal codes. These codes are near optimal and have a relatively low complexity. We evaluate the upper bounds on the bit-error probability of the proposed coded fiber-optic CDMA system assuming both on-off keying and binary pulse position modulation schemes. It is shown that the proposed method significantly outperforms the uncoded systems for various receiver structures such as a correlator with and without hard-limiter and chip-level detector. Furthermore, the performance of the proposed coded fiber-optic CDMA system is also evaluated in the presence of different values of dark current     

Tight exponential upper bounds on the ML decoding error probability of block codes over fully interleaved fading channels

We derive tight exponential upper bounds on the decoding error probability of block codes which are operating over fully interleaved Rician fading channels, coherently detected and maximum-likelihood decoded. It is assumed that the fading samples are statistically independent and that perfect estimates of these samples are provided to the decoder. These upper bounds on the bit and block error probabilities are based on certain variations of the Gallager bounds. These bounds do not require integration in their final version and they are reasonably tight in a certain portion of the rate region exceeding the cutoff rate of the channel. By inserting interconnections between these bounds, we show that they are generalized versions of some reported bounds for the binary-input additive white Gaussian noise channel.     

Performance evaluation of multicast relay network using LDPC and convolutional channel codes along-with XOR network coding

In this paper,we have compared the performance of joint network channel coding(JNCC) for multicast relay network using low density parity check(LDPC) codes and Convolutional codes as channel codes while exclusive or(XOR) network coding used at the intermediate relay nodes.Multicast relay transmission is a type of transmission scheme in which two fixed relay nodes contribute in the second hop of end-to-end transmission between base transceiver station(BTS) and a pair of mobile stations.We have considered one way and two way multicast scenarios to evaluate the bit error rate(BER) and throughput performance.It has been shown that when using XOR network coding at the intermediate relay nodes,the same transmission becomes possible in less time slots hence throughput performance can be improved.Moreover we have also discussed two possible scenarios in the proposed system model,in which both diversity and multiplexing gain has been considered.It is worth notifying that BER and throughput achieved for LDPC codes is better than Convolutional codes for all the schemes discussed.     

适用于大气弱湍流信道的自适应码率极化码

为了提高光通信链路在大气弱湍流信道下的解码性能和传输效率,基于极化码的信息位嵌套特性,设计了一种自适应码率极化码。该码字在弱湍流信道中能充分地极化,纠错效果较好。为了调节码率,引入CRC校验码作为发送端的停止标志,逐次发送更低码率的码字直到译码结果通过校验,此时的码字码率即是保证可靠传输的最大码率。不同湍流强度下的仿真结果表明,在误帧率为10-8时,相比传统极化码,自适应码率极化码可以获得1.7~2.3 dB的性能增益。对自适应码率极化码的时延进行了仿真分析,并结合误帧率得到了自适应码率极化码的信息吞吐率,结果表明,在弱湍流信道中,自适应码率极化码的信息吞吐率能满足FSO的传输需求。     

Performance of lattice codes over the Gaussian channel

We derive an upper bound on the error probability of lattice codes combined with Quadrature Amplitude Modulation (qam) over the additive white Gaussian noise channel. This bound depends on a lattice figure of merit and is readily put in exponential form by using Chernoff bound. An interesting lower bound is derived by a similar reasoning. We also examine the estimation of the average information rate based upon the continuous approximation of the average power normalized to two dimensions, and suggest to improve it by using the sphere packing idea. Examples of performance evaluation are given for a few lattices. Finally, we present upper and lower bounds on the best fundamental coding gains per dimension (due to both density and thickness) for an arbitrarily large number of dimensions. It is shown in the Appendix that, as the Ungerboeck codes, the lattice codes do not shape the signal power spectrum.     

Bounds on the maximum-likelihood decoding error probability oflow-density parity-check codes

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent     

A comparison of known codes, random codes, and the best codes

This paper calculates new bounds on the size of the performance gap between random codes and the best possible codes. The first result shows that, for large block sizes, the ratio of the error probability of a random code to the sphere-packing lower bound on the error probability of every code on the binary symmetric channel (BSC) is small for a wide range of useful crossover probabilities. Thus even far from capacity, random codes have nearly the same error performance as the best possible long codes. The paper also demonstrates that a small reduction k-k˜ in the number of information bits conveyed by a codeword will make the error performance of an (n,k˜) random code better than the sphere-packing lower bound for an (n,k) code as long as the channel crossover probability is somewhat greater than a critical probability. For example, the sphere-packing lower bound for a long (n,k), rate 1/2, code will exceed the error probability of an (n,k˜) random code if k-k˜>10 and the crossover probability is between 0.035 and 0.11=H^-1(1/2). Analogous results are presented for the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel. The paper also presents substantial numerical evaluation of the performance of random codes and existing standard lower bounds for the BEC, BSC, and the AWGN channel. These last results provide a useful standard against which to measure many popular codes including turbo codes, e.g., there exist turbo codes that perform within 0.6 dB of the bounds over a wide range of block lengths     

Operational rate-distortion performance for joint source andchannel coding of images

This paper describes a methodology for evaluating the operational rate-distortion behavior of combined source and channel coding schemes with particular application to images. In particular, we demonstrate use of the operational rate-distortion function to obtain the optimum tradeoff between source coding accuracy and channel error protection under the constraint of a fixed transmission bandwidth for the investigated transmission schemes. Furthermore, we develop information-theoretic bounds on performance for specific source and channel coding systems and demonstrate that our combined source-channel coding methodology applied to different schemes results in operational rate-distortion performance which closely approach these theoretical limits. We concentrate specifically on a wavelet-based subband source coding scheme and the use of binary rate-compatible punctured convolutional (RCPC) codes for transmission over the additive white Gaussian noise (AWGN) channel. Explicit results for real-world images demonstrate the efficacy of this approach.     

A joint source and channel coding algorithm for error-resilient SPIHT-coded video bitstreams

We propose an analytical rate-distortion optimized joint source and channel coding algorithm for error-resilient scalable encoded video for lossy transmission. A video is encoded into multiple independent substreams to avoid error propagation and is assigned forward error correction (FEC) codes and source bits using Lagrange optimization. Our method separates video coding and packetization into different tiers which can be easily incorporated into any coding structure that generates a set of independent compressed bit-streams. To demonstrate the performance, we use the 2-state Markov model to describe the burst loss channel and Reed-Solomon codes as forward error correction codes. Simulation results show that the proposed channel incorporated rate-distortion optimization approach have better performance.     

A direct geometrical method for bounding the error exponent for anyspecific family of channel codes. I. Cutoff rate lower bound for blockcodes

A direct, general, and conceptually simple geometrical method for determining lower and upper bounds on the error exponent of any specific family of channel block codes is presented. It is considered that a specific family of codes is characterized by a unique distance distribution exponent. The tight linear lower bound of slope -1 on the code family error exponent represents the code family cutoff rate bound. It is always a minimum of a sum of three functions. The intrinsic asymptotic properties of channel block codes are revealed by analyzing these functions and their relationships. It is shown that the random coding technique for lower-bounding the channel error exponent is a special case of this general method. The requirements that a code family should meet in order to have a positive error exponent and at best attain the channel error exponent are stated in a clear way using the (direct) distance distribution method presented     

On coding without restrictions for the AWGN channel

Many coded modulation constructions, such as lattice codes, are visualized as restricted subsets of an infinite constellation (IC) of points in the n-dimensional Euclidean space. The author regards an IC as a code without restrictions employed for the AWGN channel. For an IC the concept of coding rate is meaningless and the author uses, instead of coding rate, the normalized logarithmic density (NLD). The maximum value C_∞ such that, for any NLD less than C_∞, it is possible to construct an PC with arbitrarily small decoding error probability, is called the generalized capacity of the AWGN channel without restrictions. The author derives exponential upper and lower bounds for the decoding error probability of an IC, expressed in terms of the NLD. The upper bound is obtained by means of a random coding method and it is very similar to the usual random coding bound for the AWGN channel. The exponents of these upper and lower bounds coincide for high values of the NLD, thereby enabling derivation of the generalized capacity of the AWGN channel without restrictions. It is also shown that the exponent of the random coding bound can be attained by linear ICs (lattices), implying that lattices play the same role with respect to the AWGN channel as linear-codes do with respect to a discrete symmetric channel