Single bit error

30.3.4 Multi-Bit Error Detection and Correction: Bossen’s b-Adjacent Algorithm

The SEC error detection and correction algorithms described thus far focus on the detection and correction of single-bit errors. However, multi-bit errors can and do occur. The trends associated with the scaling of process technology increase a circuit’s sensitivity to SEUs, including the shrinking geometries of basic circuits and the continuing reduction in supply voltage. Thus, multi-bit error detection and correction is increasing in importance. Fortunately, multi-bit error detection and correction algorithms have been developed for systems requiring a high degree of reliability in the memory system.

In a 64-bit data word, a single-bit error can occur in 1 of 64 locations. In the same data word, two randomly located single-bit errors can occur in 2016 different combinations of bit positions. Thus, it is far more difficult to locate and correct two random errors. However, multi-bit errors are usually caused by the same event and thus typically occur in adjacent bit locations. Multi-bit error correction algorithms used in modern computer systems exploit this and focus on detecting and correcting multi-bit errors in adjacent locations.

There are numerous multi-bit error correction algorithms, based on algorithms developed by Hsiao, Carter, Kaneda, Bossen, and others. We illustrate a representative example: Bossen’s b-adjacent algorithm [Bossen 1970]. The example describes a 2-adjacent algorithm; the extension to larger values of b is simply asserted and not illustrated.

Check bits C₇ through C₀ are generated from the transformed parity check matrix through the recursive application of the exclusive-or function to bit positions indicated by the parity check matrix. As an example, the top row of the parity check matrix shows that check bit C₇ can be generated from the recursive application of the exclusive-or function to D₀, D₂, D₄, D₉ … D₆₁, and d₆₂.

In the first matrix, bit 32 of a 64-bit block has been corrupted while stored in memory. The first matrix in Figure 30.12 shows that check bits C₇, C₅, and C₁ would be affected by this. Note that bit 32 in the block is the only bit that would affect these check bits and only these check bits. A comparison of the retrieved check bits against the recomputed check bits results in the ECC syndrome bit vector of 10100010. A check of Table 30.3 shows that an ECC syndrome of 10100010 indicates bit 32 as being corrupt.

In the second example, assume bits 32 and 33 are both corrupted. As a result, check bits C₇, C₆, C₅, C₄, C₁, and C₀ are affected. A comparison of the retrieved check bits against the recomputed check bits results in the ECC syndrome 11110011. Using this as an index into the error location table identifies bits 32 and 33 as corrupted.

5.5.1 DUE FIT from Temporal Double-Bit Error with No Scrubbing

Then the probability of a double-bit error after a time period T = Pd[N] * P[N strikes in time T] for all N. Using this equation, one can solve for the expected value of T to derive the MTTF to a temporal double-bit error.

There is, however, an easier way to calculate MTTF to a temporal double-bit error. Assume that M is the mean number of single-bit errors needed to get a double-bit error. Then, the MTTF of a temporal double-bit error = M * MTTF of a single-bit error. (Similarly, the FIT rate for a double-bit error = 1/M * FIT rate for a single-bit error.) A simple computer program can calculate M very easily as the expected value of Pd[.].

Using a Poisson distribution Saleh et al. [18] came up with a compact approximation for double-bit error MTTFs of large memory systems. Derivation of Saleh et al. shows that the MTTF of such temporal double-bit errors is equal to [1/(72 * f)] * sqrt(pi/2Q), where f = FIT rate of a single bit.

The above calculation does not factor in the reduced error rates because of the AVF. The single-bit FIT/bit can be appropriately derated using the AVF to compute the more realistic temporal double-bit DUE rate.

It is important to note that the MTTF contribution from temporal double-bit errors for a system with multiple chips cannot be computed in the same way as can be done for single-bit errors. If chip failure rates are independent (and exponentially distributed), then a system composed of two chips, each with an MTTF of 100 years, has an overall MTTF of 100/2 = 50 years. Unfortunately, double-bit error rates are not independent because the MTTF of a double-bit error is not a linear function of the number of bits. This is also evident in Saleh’s compact form, which shows that the rate of such double-bit errors is inversely proportional to the square root of the size of the cache. Thus, quadrupling the cache size halves the MTTF of double-bit errors but does not reduce it by a factor of 4.

11.2.1 Synchronization failure

As we have already seen in Chapter 7, a coded video bitstream normally comprises a sequence of variable-length codewords (VLCs). VLC methods such as Huffman or arithmetic coding are employed in all practical image and video coding standards. Fixed-length codewords (FLCs) are rarely used in practice except when symbol probabilities do not justify the use of VLC (e.g., in some header information). A further exception to this is the class of error-resilient methods, including pyramid vector quantization (PVQ), which we will study in Section 11.7.2.

As we will see in the following subsections, the extent of the problem caused will be related to the location where the error occurs and the type of encoding employed.

4.3.1 Single-Bit-Flip Errors

The strategy for detecting errors is to add three “temporary” qubits |t0t1t2〉, set to |000〉, which will hold “parity” results. We then XOR various bits together, putting the results in the added three qubits: t₀ is bit 0 XOR bit 1, t₁ is bit 0 XOR bit 2, and t₂ is bit 1 XOR bit 2. This leaves a unique pattern, called a syndrome, for each error. The third column of Table II shows the respective syndromes for each error.

Measuring the added three qubits yields a syndrome, while maintaining the superpositions and entanglements we need. Depending on which syndrome we find, we apply one of the three corrective operations given in the last column to the original three repetition encoding qubits. The operation X flips a bit; that is, it changes a 0 to a 1 and a 1 to a 0. The identity operation is I. We illustrate this process in the following example.

Burst Errors and Interleaving

So none of the methods we just examined do anything about the issue of burst errors. Single bit errors are fine to correct, but many errors come not as single events that smash individual bits, but longer bursts of static or other types of impulse noise that wipes out several bits in a row: often tens of bits, sometimes hundreds, occasionally thousands. In cases where thousands of bits might be flipped or simply eradicated, one of the reasons that we have layered protocols comes into play. One of the main tasks of an upper layer is to recover from uncorrectable errors that occur at a lower layer. For example, uncorrectable errors that might occur on a hop between two intermediate systems can be detected and fixed by an end-to-end resend between the client and server at the endpoints.

But maybe we can do something about our error-correcting system to make it more robust in the face of limited burst errors (there will always be a point where the length of the burst exceeds the ability of the designed correction code’s to fix bit errors).

The method commonly used is called interleaving, sometimes seen as scrambling. With interleaving, we do not send the code bits sequentially as soon as we get them. We buffer the bits, both the data bits and derived parity bits, at the sender until we have a set of bits in some predefined structure. Then we can interleave the bits and send them not sequentially as they arrived, but in another pattern altogether.

Let’s look at a simple example using of initial (3,1) code which sent every data bit three times, so 0 became 000 and 1 became 111. As we saw, single bit errors could be corrected as 010 -> 000 or 110 -> 111 due to the Hamming distance characteristics. But if 000 became 110, we lost that ability by trying to correct the string to 111.

But let’s buffer five of these code words together first. So if, for instance, 0 came in and became 000, we would not send it right away. Let’s call that AAA and wait for another bit like 1 to became 111. That would be BBB in our simple system, with the three letters standing for a particular 000 or 111.

In fact, let’s do this five times: AAA BBB CCC DDD EEE. (Note that the spaces are simply for convenience of visualization: in practice, the bits would all run together.)

Not we’re ready to send the 15 bits…but interleaved. We would send ABCDE ABCDE ABCDE. At the received, even before error correction, the original “frame” structure would be recovered by “unscrambling” the bits. Only after de-interleaving would error correction be applied (010 -> 000) and the bits decoded into the sent information (000 -> 0).

Now, suppose a burst error wiped out four consecutive bits in the stream, perhaps like this:

ABCDE ABXXXX BCDE

When this sequence was un-interleaved, we would have: AAX BBB CXC DXD EXE.

We have just, through the process of interleaved, made four single bit errors out of a four-bit burst error! We have, with this simple method, created a system that can recover from bursts up to five bits long. However, we have also introduced another buffering and processing delay at the sender and receiver, and delay and processing burden that grow with complexity and robustness. But given the delay and burden of resending large chunks of errored data, the trade-off is often more than worthwhile.

In practice, we can interleave much more complex “transmission frames” and actually nest the interleavings to create more and more robust burst error correction methods. Audio CDs next interleavings and error correction to create a method that can recover from some 3600 consecutive bits in error. This “delay” is acceptable because audio is strictly a one-way process from disc to your ear. The interleaving delay is absorbed long before the disc is burned, and the delay to de-interleave when you press “play” is acceptable because once the audio pipeline is filled, the decoding is a continuous process.

1.20 The Hamming code

This code provides a minimum distance of three between codewords, a necessary condition that must be provided in order to achieve single-bit error detection and correction. For any value of r, where r represents the number of check bits, 2^r − 1 codeword bits can be formed consisting of r check bits and k message bits where k = 2^r − 1 − r. For r = 3, k ≤ 4 so that four message bits are the maximum number that can be checked for r = 3.

Noise Sensitivity

Huffman and arithmetic codes are more compact than a simple fixed-length code of size log₂ K, but they are also more sensitive to errors. For a constant-length code, a single bit error modifies the value of only one symbol. In contrast, a single bit error in a variable-length code may modify the whole symbol sequence. In noisy transmissions where such errors might occur, it is necessary to use an error correction code that introduces a slight redundancy in order to suppress the transmission errors [18].

17.4.1.3 RAID 2: Bit-Level Striping With Hamming Code

Theorem 3

In equation 8.6, scalars a_i and b_i are compared, where a: = (a₁, …, a_n)^T and b: = (b₁, …, b_n)^T are the LHS and RHS, respectively of equation 8.6. The above result means that single bit errors in either a_i or b_i can be detected for each i even when single-precision integer arithmetic is used. The following result is regarding the maximum number of arbitrarily distributed errors (i.e., not necessarily restricted to one error per scalar component of the check) that can be detected by the mantissa checksum test.

3.9.1 A Brief Introduction to Error Detection and Error Correction Codes

When designing an FEC code, a main consideration is the number of bit errors that the code will be able to correct. In other words, the number of bit transitions (0-to-1 or 1-to-0) that can occur within a given-length stream of bits transmitted and yet the original data value can still be determined.

Consider the 8-bit data value 11001100. A single bit error could give rise to, for example, 10001100, 11011100, or 11001110. Two bit errors could give rise to, for example, 00001100, 11101110, or 01001101.

The number of bits that are different in the data (from the original to the modified versions) is called the Hamming distance (d); the single-bit error examples shown above have a Hamming distance of 1 (i.e., d = 1), while the two-bit error examples have a Hamming distance of 2 (i.e., d = 2).

If all bit combinations in a particular code are possible correct values, then the value of d for the data code is 1 and there is no redundancy; that is, a single bit change shifts the code from one legal value to another and therefore cannot be detected as an error. Consider a 4-bit code that holds a Customer ID (CID) and that CIDs can range from 0 to 15 (decimal). The following binary values are all acceptable: 0000, 0001, 0010, 0011, …, 1111. If, during transmission, a single bit error occurs in any of these values, the resulting code (which is wrong) has the value of another acceptable code and is thus undetectable as an error. For example, 0010 can become 0011, which are both valid codes, and thus, the receiver of the value 0011 cannot tell if this is the value that was actually sent or if an error has occurred turning a different value into 0011.

To perform error detection or correction on an original data message, additional information must be added at the point of transmission. The additional information is a form of overhead (also referred to as “redundant bits”) since it must be transmitted as part of the new larger message but does not carry any application-level information.

The simplest way to detect a single bit error in the 4-bit code is to use parity checking, in which case one additional bit must be added (the parity bit). In this case, for every four data bits transmitted, a fifth parity bit must be transmitted, so the overhead is 20%; or alternatively, you can consider that the efficiency is 80%; since 80% of the bits transmitted carry application data, the remaining 20% are redundant from the application viewpoint.

Consider “even parity” in which the number of “1” bits must be even in the 5-bit code that is transmitted. CID values 0000, 0011, and 1001 are examples where the number of “1” bits is already even; thus, a parity bit of “0” will be added, turning these values into 00000, 00110, and 10010, respectively. CID values 0001, 0010, and 1101 are examples where the number of “1” bits is odd; thus, a parity bit of “1” will be added, turning these values into 00011, 00101, and 11011, respectively.

If a single bit error occurs now, for example, 00110 becomes 00100 during transmission, the error will be detected by the receiver, because the parity check will fail (there are not an even number of “1s”). Notice that although the error is detected, it cannot be corrected because there are many possible valid codes that could have been translated into the received value 00100 by a single bit translation, including 00101, 10100, and 01100.

To achieve error correction, additional redundant bits must be added such that there is only one valid data code that could be translated into any particular received value, as long as the number of bit errors does not exceed the number supported by the error correction code. The theory aspect of error correcting codes is a complex subject, so the discussion will be limited to a simple example based on the triple modular redundancy technique to provide an introduction.

In a triple modular redundancy code, each bit is repeated three times, that is, transmitted as 3 bits, so each “0” becomes “000” and each “1” becomes “111.” There are only two valid code patterns per three-bit sequence that can be transmitted, and it is not possible for a single bit error to convert one valid code into another. A single bit error turns 000 into one of 001, 010, or 100, all of which are closer to 000 than 111, and thus, all are interpreted as a 0 and not a 1 data value. Similarly, a single bit error turns 111 into one of 110, 101, or 011 all of which are closer to 111 than 000, and thus, all are interpreted as a 1 data value. Thus, a single bit error can be automatically corrected, but at the cost of a significantly increased message size. For the triple modular redundancy technique, the overhead is 67%; in other words, the code efficiency is 33%; since 33% of the bits transmitted carry useful data, the remaining 67% are redundant. Fortunately, more efficient error-correcting codes do exist.

If triple modular redundancy were applied to the earlier customer ID example, each 4-bit CID value would be transmitted as a 12-bit message. For example, 0001 would be transmitted as 000000000111, and 0010 would be transmitted as 000000111000.