Efficient codes for single error detection and partial single error correction

Coding schemes are proposed for error control in systems where individual blocks of information are organised as two sub-blocks each requiring a different degree of error control. The codes described guarantee single error correction in one sub-block and provide single error detection and partial single error correction in the other. The main advantages are savings in redundancy and ability to use standard encoding/decoding procedures.     

Error correction and error detection techniques for wireless ATM systems

Error correction and error detection techniques are often used in wireless transmission systems. The Asynchronous Transfer Mode (ATM) employs Header Error Control (HEC). Since ATM specifications have been developed for high‐quality optical fiber transmission systems, HEC has single‐bit error correction and multiple‐bit error detection capabilities. When HEC detects multiple‐bit error, the cell is discarded. However, wireless ATM requires a more powerful Forward Error Correction (FEC) scheme to improve the Bit Error Rate (BER) performance resulting in a reduction in the transmission power and antenna size. This concatenation of wireless FEC and HEC of the ATM may effect cell loss performance. This paper proposes error correction and error detection techniques suitable for wireless ATM and analyzes the performance of the proposed schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Poor error correction codes are poor error detection codes (Corresp.)

We show that binary group codes that do not satisfy the asymptotic Varshamov-Gilbert bound have an undesirable characteristic when used as error detection codes for transmission over the binary symmetric channel.     

Using codes for error correction and detection (Corresp.)

A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;epsilon) leq P(C,t;(q - 1)/q)for allepsilon, 0 leq epsilon leq (q - 1)/q, whereP(C, t; epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probabilityepsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.     

A partial transmit sequence technique with error correction capability and low computation

Orthogonal frequency division multiplexing (OFDM) is a popular transmission technique in wireless communication. Although already widely addressed in many studies, OFDM still has flaws, one of which is the occurrence of high peak‐to‐average power ratio (PAPR) in the transmission signal. The partial transmit sequence (PTS) technique is one method adopted to reduce high PAPR in OFDM systems. However, as PTS utilizes phase factors to generate multiple candidate signals, large amounts of calculation and time are required to search the candidate signal with the minimal PAPR, which will then be adopted as the final transmission signal. This paper proposes a novel PAPR reduction method, which can be applied in OFDM systems with M‐ary phase‐shift keying modulation. It not only requires less computation but also possesses error correction capabilities. More precisely, the proposed method is to divide a block‐coded modulation code into the direct sum of a correcting subcode for encoding information bits and a scrambling subcode for generating phase factors. Our proposed method is a suboptimal technique with low computation, because it uses a genetic algorithm with a partheno‐crossover operator as the transmitted signal selection mechanism. Simulation results show our proposed method has better PAPR performance than the GA‐PTS scheme. Based on the simulation results in Figures 5 and 6, it is evident that our proposed method can be employed in any OFDM system by using M‐PSK modulation.Copyright © 2013 John Wiley & Sons, Ltd.     

Flexible forward error correction codes with application to partial media data recovery

Conventionally, linear block codes designed for packet erasure correction are targeted to recover all the lost source packets per block, when the fraction of lost data is smaller than the redundancy overhead. However, these codes fail to recover any lost packets, if the number of erasures just exceeds the limit for full recovery capability, while it can still be beneficial to recover part of the symbols. In addition, common linear block codes are not well suited for unequal error protection, since different block codes with different rates must be allocated for each priority class separately. These two problems motivate the design of more flexible forward error correction (FEC) codes for media streaming applications. We first review the performance of short and long linear block codes. Long block codes generally offer better error correction capabilities, but at the price of higher complexity and larger coding delay. Short block codes can be more appropriate in media streaming applications that require smooth performance degradation when the channel loss rate increases. We study a new class of linear block codes using sparse generator matrices that permit to optimize the performance of short block codes for partial recovery of the lost packets. In addition, the proposed codes are extended to the design of unequal erasure protection solutions. Simulations of practical video streaming scenarios demonstrate that the flexible sparse codes offer a promising solution with interesting error correction capabilities and small variance in the residual loss rate. They typically represent an effective trade-off between short block codes with limited flexibility, and long block codes with delay penalties.     

Sparse-graph codes for quantum error correction

Sparse-graph codes appropriate for use in quantum error-correction are presented. Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error-correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes.     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

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     

Even-weighted codes for error detection

For a binary symmetric channel, a code V with only evenweighted words performs better than a corresponding code V? with both odd- and even-weighted words, from the point of the probability of undetected errors. We derive an estimate of the improvement in the performance.     

Reduced-redundancy product codes for burst error correction

In a typical burst error correction application of a product code of n_v×n_h arrays, one uses an [n_h, n_h-r_h] code C_h that detects corrupted rows, and an [n_v, n_v-r_v] code C_v that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C_h provides the code C_v with information on many error patterns that exceed the correction capability of C_v. A coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n_hr_v+r_h(lnr_v+O(1))+r_v , where the parameters r_h and r_v are close in value to their counterparts in the conventional case, which has redundancy n_hr_v+n_vr_h-r_h r_v. In particular, when the codes C_h and C _v have the same rate and r_h≪n_h, the redundancy of the proposed scheme is close to one-half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors     

Subspace-based error and erasure correction with DFT codes for wireless channels

This paper deals with the decoding of lowpass discrete Fourier transform (DFT) codes in the presence of both errors and erasures. We propose a subspace-based approach for the error localization that is similar to the subspace approaches followed in the array signal processing for direction-of-arrival (DOA) estimation. The basic idea is to divide a vector space into two orthogonal subspaces of which one is spanned by the error locator vectors. The locations of the errors are estimated from the spanning eigenvectors of the complement subspace. However, unlike the subspace approach in DOA estimation, which is similar to estimating the subspaces from the syndrome covariance matrix after a projection, in the proposed approach, the subspaces are estimated from the modified syndrome covariance matrix after a whitening transform. Simulation results with a Gauss-Markov source reveal that the proposed algorithm is more efficient than the coding theoretic approach on impulsive channels as well as the subspace approach with projection on lossy channels.     

The simplex codes and other even-weight binary linear codes for error correction

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.     

Runlength limited codes for random and burst error correction

A product code approach to the design of multiple error correcting runlength limited codes is presented. In contrast to recent coding schemes of this type they are based entirely on binary coding operations and are therefore relatively simple to realise in hardware. A table of some illustrative codes is presented.<>     

Implementation and evaluation of 2D SEC-DED forward error correction scheme in wireless sensor networks

Numerous applications in wireless sensor networks (WSNs) require collecting data without loss during transmission, long-term sensing, and long system lifetime. Achieving reliable data transfer and long system lifetime is difficult because, from one hand, the wireless transfer is error prone, and, on the other, sensor node (SN), as battery powered device, is energy limited. By using some power-aware techniques, such as duty-cycling and power-gating, it is possible to reduce the energy consumption at an acceptable level. The requirements for higher level of reliability during wireless data transfer have increased the use of error correcting codes (ECCs). Codes represent an effective means of providing protection against injection of single-/double-/multiple bit errors over noisy communication channel. The two basic mechanisms to recover erroneous packets in any network are Automatic Repeat Request (ARQ), and Forward Error Correction (FEC). As energy consumption is a major issue in concern in WSN, packet retransmission is not an option and FEC would be preferred over ARQ. In this paper, an efficient scheme, based on two-dimensional (rectangular) block ECC code, referred as Two Dimensional Single Error Correction and Double Error Detection (2D SEC-DED), has been developed. By using 2D SEC-DED encoding all single-bit and 99.9% of double −/multiple-bit errors, within transferred packets, are recovered. In this way, the number of retransmissions, when WSN operates in harsh environmental (bit error rate (BER), BER > 10^− 4) is decreased, what means that not only energy saving but also extension of the transmit range (transmission distance between the transmitter and receiver), is achieved. As illustration, for indoor environment (the path loss exponent, also known as propagation constant or space loss factor, α = 4) at the target BER of 5 · 10^− 4, the proposed encoding scheme is able to improve the transmission distance by about 18 m or the received signal strength (RSSI) by about 8.5dBm compared to WSN without error correction (WSN which use Cycle Redundancy Check (CRC) encoding as error detection mechanism).     

Weighted sum codes for error detection and their comparison withexisting codes

Describes a new family of error detection codes called weighted sum codes. These codes are preferred over four existing codes (CRC, Fletcher checksum, Internet checksum, and XTP CXOR), because they combine powerful error detection properties (as good as the CRC) with attractive implementation properties. One variant, WSC-1, has efficient software and hardware implementations; while a second variant, WSC-2, is almost as efficient in software (still significantly better than CRC) and offers commutative processing (that enables efficient out-of-order, parallel, and incremental update processing)     

Random error and burst correction by iterated codes

We give a decoding algorithm for iterated codes that can correct up to the number of errors guaranteed by the product minimum distance, rather than about half that number when the iterated codes are decoded independently. This result is achieved by adapting Forney's generalized minimum distance decoding for use with iterated codes. We derive results on the simultaneous burst- and random-error-correction capability of iterated codes that improve considerably on known results.     

On testing for improper error detection codes

A family of tests for improper codes is given. These tests can be used in cases where the complete weight distribution of the code is unknown. It was found that knowledge of the number of minimum weight codewords can be used to greatly increase the effectiveness of the asymptotic Varshamov-Gilbert test. Further improvement is possible as more is known about the number of other weight codewords     

Multiple error detection and correction based on redundant residue number systems

This paper presents some results on multiple error detection and correction based on the Redundant Residue Number System (RRNS). RRNS is often used in parallel processing environments because of its ability to increase the robustness of information passing between the processors. The proposed multiple error correction scheme utilizes the Chinese Remainder Theorem(CRT) together with a novel algorithm that significantly simplifies the error correcting process for integers. An extension of the scheme further reduces the computational complexity without compromising its error correcting capability. Proofs and examples are provided for the coding technique.