<< Chapter < Page Chapter >> Page >
A description of some strategies for minimizing there errors in a transmitted bit-stream.

For the (7,4) example , we have 2 N K 1 7 error patterns that can be corrected. We start with single-bit error patterns, and multiply them by the parity check matrix.If we obtain unique answers, we are done; if two or more error patterns yield the same result, we can try double-bit errorpatterns. In our case, single-bit error patterns give a unique result.

Parity check matrix
e He
1000000 101
0100000 111
0010000 110
0001000 011
0000100 100
0000010 010
0000001 001

This corresponds to our decoding table: We associate the parity check matrix multiplication result with the error pattern andadd this to the received word. If more than one error occurs (unlikely though it may be), this "error correction" strategyusually makes the error worse in the sense that more bits are changed from what was transmitted.

As with the repetition code, we must question whether our (7,4) code's error correction capability compensates for the increasederror probability due to the necessitated reduction in bit energy. [link] shows that if the signal-to-noise ratio is large enough channel coding yields asmaller error probability. Because the bit stream emerging from the source decoder is segmented into four-bit blocks, the fairway of comparing coded and uncoded transmission is to compute the probability of block error: the probability that any bit in a block remains in error despite errorcorrection and regardless of whether the error occurs in the data or in coding buts. Clearly, our (7,4) channel code doesyield smaller error rates, and is worth the additional systems required to make it work.

Probability of error occurring

The probability of an error occurring in transmitted K 4 data bits equals 1 1 p e 4 as 1 p e 4 equals the probability that the four bits are received without error. The upper curve displays how this probability of anerror anywhere in the four-bit block varies with the signal-to-noise ratio. When a (7,4) single-bit errorcorrecting code is used, the transmitter reduced the energy it expends during a single-bit transmission by 4/7, appendingthree extra bits for error correction. Now the probability of any bit in the seven -bit block being in error after error correction equals 1 1 p e 7 7 p e 1 p e 6 , where p e is the probability of a bit error occurring in the channel when channel coding occurs. Here 7 p e 1 p e 6 equals the probability of exactly on in seven bits emerging from the channel in error; The channel decodercorrects this type of error, and all data bits in the block are received correctly.

Note that our (7,4) code has the length and number of data bits that perfectly fits correcting single bit errors. This pleasantproperty arises because the number of error patterns that can be corrected, 2 N K 1 , equals the codeword length N . Codes that have 2 N K 1 N are known as Hamming codes , and the following table provides the parameters of these codes. Hamming codes are the simplest single-bit error correction codes, and thegenerator/parity check matrix formalism for channel coding and decoding works for them.

Hamming codes
N K E (efficiency)
3 1 0.33
7 4 0.57
15 11 0.73
31 26 0.84
63 57 0.90
127 120 0.94

Unfortunately, for such large blocks, the probability of multiple-bit errors can exceed the number of single-bit errorsunless the channel single-bit error probability p e is very small. Consequently, we need to enhance the code'serror correcting capability by adding double as well as single-bit error correction.

What must the relation between N and K be for a code to correct all single- and double-bit errors with a "perfect fit"?

In a length- N block, N single-bit and N N 1 2 double-bit errors can occur. The number of non-zero vectors resulting from H c ^ must equal or exceed the sum of these two numbers.

2 N K 1 N N N 1 2   or   2 N K N 2 N 2 2
The first two solutions that attain equality are (5,1) and (90,78) codes. However, no perfect code exists other than the single-bit error correctingHamming code. (Perfect codes satisfy relations like [link] with equality.)

Got questions? Get instant answers now!

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Fundamentals of electrical engineering i. OpenStax CNX. Aug 06, 2008 Download for free at http://legacy.cnx.org/content/col10040/1.9
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fundamentals of electrical engineering i' conversation and receive update notifications?

Ask
Madison Christian
Start Quiz
Dravida Mahadeo-J...
Start Quiz
Hope Percle
Start Quiz