By: Neil E. Cotter	Probability
		Binomial dist/Bernoulli
		Example 4

---

Ex: Error correction schemes for transmission of binary bits add extra bits so errors can be detected and corrected. For example, an extra bit could be included to make the number of 1's in a transmission be an even number. A one-bit error may be detected at the receiving end by counting how many 1's are in the received number.

More sophisticated error-correction schemes map binary numbers to longer binary numbers that differ from one another in as many bits as possible so multiple bit flips may be detected. (Actually, things are a bit more involved than this description, but this basic description will suffice here.) An error correction coding scheme maps received binary messages to the nearest binary codeword as measured by Hamming distance (i.e., the number of bits that differ for two binary numbers.) This works perfectly unless too many bits are erroneous, which causes the received pattern to be closer to an incorrect codeword.

a) Consider a codeword consisting of 8 bits. Determine how many other 8-bit binary patterns are within a Hamming distance of 3 or less of this codeword. Calculations of this sort tell us how many bit errors must occur before the error correction scheme fails.

b) If the probability of error for each bit is p = 0.2, independent of other bits, find the probability that 3 or less bits out of 8 will be erroneous. Calculations of this sort tell us the probability of errors occurring in the decoding process.

Sol'n: a) Since we are considering only which bits are different, we may choose any 8-bit word as the starting point and then determine which binary words differ from it by one, two, or three bits. (Note that, since the problem asked about "other 8-bit patterns...", we exclude a difference of zero bits which would be taking the distance from the word to itself.)

Without loss of generality, we take our base word to be 00000000. With this choice, words that differ in one, two, or three bits are those 8-bit words that have one, two, or three 1's.

To count the number of 8-bit words with m 1's, we use combinatoric coefficients:

# patterns of n bits with m 1's = nCm =

We calculate the following values:

# patterns of 8 bits with one 1's = 8C1 =

# patterns of 8 bits with two 1's = 8C2 =

# patterns of 8 bits with three 1's = 8C3 =

Taking the sum, the total number of patterns is 92.

b) We first observe that patterns with different numbers of 1's are mutually exclusive events. Thus, since we may equate a 1 with a bit error, we may calculate the probability of patterns for each of the different numbers of 1's and sum the results.

For any one pattern with m ones out of n bits, the probability of that pattern is a product of probabilities since bits are independent:

where

We multiply the number of patterns by the probability of that pattern and sum, (now including the probability of zero errors):

or

An alternate approach is to use a table of sums for binomial distributions, such as Table A.1 found in [1]:

The parameters are n = 8, r = 3, p = 0.2.

Ref: [1] Ronald E. Walpole, Raymond H. Myers, Sharon L. Myers, and Keying Ye, Probability and Statistics for Engineers and Scientists, 7th Ed., Upper Saddle River, NJ: Prentice Hall, 2002.