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     

An integrated error correction and detection system for digitalaudio broadcasting

Hybrid in-band on-channel digital audio broadcasting systems deliver digital audio signals in such a way that is backward compatible with existing analog FM transmission. We present a channel error correction and detection system that is well-suited for use with audio source coders, such as the so-called perceptual audio coder (PAC), that have error concealment/mitigation capabilities. Such error mitigation is quite beneficial for high quality audio signals. The proposed system involves an outer cyclic redundancy check (CRC) code that is concatenated with an inner convolutional code. The outer CRC code is used for error detection, providing flags to trigger the error mitigation routines of the audio decoder. The inner convolutional code consists of so-called complementary punctured-pair convolutional codes, which are specifically tailored to combat the unique adjacent channel interference characteristics of the FM band. We introduce a novel decoding method based on the so-called list Viterbi algorithm (LVA). This LVA-based decoding method, which may be viewed as a type of joint or integrated error correction and detection, exploits the concatenated structure of the channel code to provide enhanced decoding performance relative to decoding methods based on the conventional Viterbi algorithm (VA). We also present results of informal listening tests and other simulations on the Gaussian channel. These results include the preferred length of the outer CRC code for 96-kb/s audio coding and demonstrate that LVA-based decoding can significantly reduce the error flag rate relative to conventional VA-based decoding, resulting in dramatically improved decoded audio quality. Finally, we propose a number of methods for screening undetected errors in the audio domain     

Comments on “Weighted sum codes for error detection and theircomparison with existing codes”

A.J. McAuley (IEEE/ACM Trans. Networking, vol.2, p.16-22, 1994) proposed a new family of error detection codes called weighted sum codes. In the present paper it is noted, that these codes are equivalent to lengthened Reed Solomon codes, resp. shortened version of lengthened Reed Solomon codes over GF(2^h/2). It is also shown, that it is possible to use these codes for error correction of one error in the code word over GF(2^h/2)     

Single error correcting and double error detecting coding scheme

A new coding technique for single error correction and double error detection in computer memory systems is proposed. The number of 1s in the parity check matrix for the proposed coding is fewer than all currently available codes for this purpose, except in two cases when they are almost equal to that obtained by Hsiao code. This results in simplified encoding and decoding circuitry for error detection and correction.     

HVD: horizontal-vertical-diagonal error detecting and correcting code to protect against with soft errors

This paper presents a high level error detection and correction method called HVD code to tolerate multiple bit upsets (MBUs) occurred in memory cells. The proposed method uses parity codes in four directions in a data part to assure the reliability of memories. The proposed method is very powerful in error detection while its error correction coverage is also acceptable considering its low computing latency. HVD code is useful for applications whose high error detection coverage is very important such as memory systems. Of course, this code can be used in combination with other protection codes which have high correction coverage and low detection coverage. The proposed method is evaluated using more than one billion multiple fault injection experiments. Multiple bit flips were randomly injected in different segments of a memory system and the fault detection and correction coverages are calculated. Results show that 100% of the injected faults can be detected. We proved that, this method can correct up to three bit upsets. Some hardware implementation issues are investigated to show tradeoffs between different implementation parameters of HVD method.     

字节式单向错误纠错码

介绍了一种有效的字节式单向错误纠错码及其编码和译码算法。从对校验位数下限值的讨论可以看出,这里介绍的码优于字节式对称错误纠错码,并且近似最优。本文还介绍了字节式非对称错误纠错码。     

Continuous error detection (CED) for reliable communication

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques used almost exclusively in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. In this work, we exploit the “continuous” nature of error detection that results from using arithmetic codes for error detection, which provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how this continuous error detection framework improves the overall performance of communication systems, and show how considerable performance gains can be attained. We focus on several important scenarios: 1) automatic repeat request (ARQ) based transmission; 2) forward error correction (FEC frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code; and 3) reduced state sequence estimation (RSSE) for channels with memory. We demonstrate that the proposed CED framework improves the throughput of ARQ systems by up to 15% and reduces the computational/storage complexity of FEC and RSSE by a factor of two in the comparisons that we make against state-of-the-art systems     

Analysis of the interaction between linear cyclic error correcting codes and self-synchronous payload scramblers

In order to protect public network data transmission from potential Layer 1 attacks by malicious users, selfsynchronous scramblers have come into widespread use. Such networks include those using ATM, Packet over SONET (POS), and the new Generic Framing Procedure (GFP). Unfortunately, feedback taps inherent in self-synchronous descramblers cause multiplication of transmission errors, which in turn degrades the performance of most linear cyclic error detection/correction codes. This paper analyzes this scrambler/code interaction with respect to the resulting probability of undetectable errors and transmission error correction capability. The theoretical criteria are derived for a linear cyclic code to maintain its error detection and correction performance in the presence of the scramblers. A novel approach for improving the error correction capabilities is also presented.     

Huffman code based error screening and channel code optimization for error concealment in perceptual audio coding (PAC) algorithms

The class of perceptual audio coding (PAC) algorithms yields efficient and high-quality stereo digital audio bitstreams at bit rates from 16 kb/sec to 128 kb/sec (and higher). To avoid "pops and clicks" in the decoded audio signals, channel error detection combined with source error concealment, or source error mitigation, techniques are preferred to pure channel error correction. One method of channel error detection is to use a high-rate block code, for example, a cyclic redundancy check (CRC) code. Several joint source-channel coding issues arise in this framework because PAC contains a fixed-to-variable source coding component in the form of Huffman codes, so that the output audio packets are of varying length. We explore two such issues. First, we develop methods for screening for undetected channel errors in the audio decoder by looking for inconsistencies between the number of bits decoded by the Huffman decoder and the number of bits in the packet as specified by control information in the bitstream. We evaluate this scheme by means of simulations of Bernoulli sources and real audio data encoded by PAC. Considerable reduction in undetected errors is obtained. Second, we consider several configurations for the channel error detection codes, in particular CRC codes. The preferred set of formats employs variable-block length, variable-rate outer codes matched to the individual audio packets, with one or more codewords used per audio packet. To maintain a constant bit rate into the channel, PAC and CRC encoding must be performed jointly, e.g., by incorporating the CRC into the bit allocation loop in the audio coder.     

Fast software implementation of error detection codes

Software implementations of error detection codes are considered to be slow compared to other parts of the communication system. This is especially true for powerful error detection codes such as CRC. However, we have found that powerful error detection codes can run surprisingly fast in software. We discuss techniques for, and measure the performance of, fast software implementation of the cyclic redundancy check (CRC), weighted sum codes (WSC), one's-complement checksum, Fletcher (1982) checksum, CXOR checksum, and block parity code. Instruction count alone does not determine the fastest error detection code. Our results show the computer memory hierarchy also affects performance. Although our experiments were performed on a Sun SPARCstation LX, many of the techniques and conclusions will apply to other processors and error detection codes. Given the performance of various error detection codes, a protocol designer can choose a code with the desired speed and error detection power that is appropriate for his network and application     

The MMD codes are proper for error detection

The undetected error probability of a linear code used to detect errors on a symmetric channel is a function of the symbol error probability /spl epsi/ of the channel and involves the weight distribution of the code. The code is proper, if the undetected error probability increases monotonously in /spl epsi/. Proper codes are generally considered to perform well in error detection. We show in this correspondence that maximum minimum distance (MMD) codes are proper.     

Cyclic unequal error protection codes constructed from cyclic codesof composite length

The unequal error correction capabilities of binary cyclic codes of composite length are investigated. Under certain conditions, direct sums of concatenated codes have unequal error correction capabilities. By a modified Hartmann and Tzeng (1973) algorithm, it is shown that a binary cyclic code of composite length is equivalent to the direct sum of concatenated codes. With this, some binary cyclic unequal error protection (UEP) codes are constructed. Finally, the authors present a class of two-level UEP cyclic direct-sum codes which provide error correction capabilities higher than those guaranteed by the Blokh-Zyablov (1974) constructions     

Generalized concatenated codes for channels where unidirectionalbyte errors are predominant

Codes are considered for correction and detection of unidirectional byte errors. A code construction based on the generalized concatenated code construction is proposed. This construction gives a large number of efficient codes. For example, from this construction, a 72-input-bit encoder of the triple unidirectional 8-bit-byte error-correcting and fourfold unidirectional 8-bit-byte error-detecting code with a length of 112 bits and rate 9/14 is obtained, whereas the ordinary triple 8-bit-byte error-correcting and fourfold 8-bit-byte error-detecting code of the same length has only 56 information bits and is of rate 1/2. The proposed construction is generalized to one that gives efficient short-length codes     

Quantum error detection .II. Bounds

For pt.I see ibid., vol.46, no.3, p.778-88 (2000). In Part I of this paper we formulated the problem of error detection with quantum codes on the depolarizing channel and gave an expression for the probability of undetected error via the weight enumerators of the code. In this part we show that there exist quantum codes whose probability of undetected error falls exponentially with the length of the code and derive bounds on this exponent. The lower (existence) bound is proved for stabilizer codes by a counting argument for classical self-orthogonal quaternary codes. Upper bounds are proved by linear programming. First we formulate two linear programming problems that are convenient for the analysis of specific short codes. Next we give a relaxed formulation of the problem in terms of optimization on the cone of polynomials in the Krawtchouk basis. We present two general solutions of the problem. Together they give an upper bound on the exponent of undetected error. The upper and lower asymptotic bounds coincide for a certain interval of code rates close to 1     

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.     

Parallel error correcting codes

We introduce the concept of "parallel error correcting" codes, the error correcting codes for parallel channels. Here, a parallel channel is a set of channels such that the additive error over a finite field occurs in one of its members at time T if the same error occurs in all members at the same time. The set of codewords of a parallel error correcting code has to be a product set, if the messages transmitted are from independent information sources. We present a simple construction of optimal parallel error correcting codes based on ordinary optimal error correcting codes and a construction of optimal linear parallel codes for independent sources based on optimal ordinary linear error correcting codes. The decoding algorithms for these codes are provided as well     

Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes

This paper presents a procedure for synthesizing sequential machines with concurrent error detection based on Bose-Lin codes. Bose-Lin codes are an efficient solution for providing concurrent error detection as they are separable codes and have a fixed number of check bits, independent of the number of information bits. Furthermore, Bose-Lin code checkers have a simple structure as they are based on modulo operations. Procedures are described for synthesizing circuits in a way that their structure ensures that all single-point faults can only cause errors that are detected by a Bose-Lin code. This paper presents an efficient scheme for concurrent error detection in sequential circuits with no constraint on the state encoding. Concurrent error detection for both the state bits and the output bits is based on a Bose-Lin code and their checking is combined such that one checker suffices. Results indicate low area overhead. The cost of concurrent error detection is reduced significantly compared to other methods based on other codes.     

The duals of MMD codes are proper for error detection

A linear code, when used for error detection on a symmetric channel, is said to be proper if the corresponding undetected error probability increases monotonically in /spl epsiv/, the symbol error probability of the channel. Such codes are generally considered to perform well in error detection. A number of well-known classes of linear codes are proper, e.g., the perfect codes, MDS codes, MacDonald's codes, MMD codes, and some Near-MDS codes. The aim of this work is to show that also the duals of MMD codes are proper.     

Compression and error sensitivity of two-dimensional facsimile coding techniques

Seven proposals were submitted to the International Telegraph and Telephone Consultative Committee (CCITT) for selection of a standard two-dimensional code as an extension of the current CCITT standard one-dimensional code. The CCITT specified the use of particular parameters and procedures to compare the candidate techniques on a quantitative basis. The compression ratio and error sensitivity of all seven coding techniques were measured for a wide range of operational conditions. For example, tests are performed with small K-factors for application to error-prone transmission over switched circuits, and also at infinite K-factor to simulate packet switching networks possessing error control. Particular attention is paid to the error detection/correction procedure to insure that the error sensitivity parameter is as realistic as possible. The essential differences between the seven proposed coding techniques are presented, and the measurement parameters and procedures are reviewed.     

Single- and Double-Output Embedded Checker Architectures for Systematic Unordered Codes<Superscript>∗</Superscript>

For the detection of all unidirectional errors, Berger codes have been found to be an optimal choice in the general case. But for some particular cases other systematic unordered codes are superior to Berger codes. We present checker architectures for Berger-type codes that are similar to Berger codes. They cover codes by Parhami so that the proposed checkers can also be used for these codes. We also describe new checker architectures for Bose AUED codes and Biswas-Sengupta AUED codes. The design of these checkers is based on translating the code words to words of a Berger-type code which are then checked by a Berger-type code checker. The translation circuits are very simple. All checkers can be tested with only a few code words, or achieve the self-testing property almost independent of the provided set of code words, and are therefore very suitable as embedded checkers. The proposed checkers can be designed to have a single periodic output or a two-rail encoded output. Further, our checkers are not code-disjoint in the common sense but able to detect all single and multiple unidirectional errors.Steffen Tarnick received the diploma degree in mathematics from the Dresden University of Technology, Dresden, Germany, in 1989, and the Dr. rer. nat. degree from the University of Potsdam, Germany, in 1995. From 1989 to 1991 he was a Research Assistant at the Institute of Cybernetics and Information Processes of the East German Academy of Sciences in Berlin. Then he spent one year as visiting scientist at the TIMA Laboratory in Grenoble, France. From 1992 to 1995 he was with the Max Planck Society Group for Fault-Tolerant Computing at the University of Potsdam, Germany. Until 2002 he was a research staff member at SATCON GmbH in Teltow, Germany. He is currently the head of the Secure Systems Department at 4TECH GmbH in Teltow, Germany. His main research interests include self-checking circuits design, built-in self-test, and cryptography.