6.37 Information communication problems  (Page 6/8)

Universal product code

The Universal Product Code (UPC), often known as a bar code, labels virtually every sold good. An example of a portion of the code is shown.

Here a sequence of black and white bars, each having width $d$ , presents an 11-digit number (consisting of decimal digits) that uniquely identifies theproduct. In retail stores, laser scanners read this code, and after accessing a database of prices, enter the priceinto the cash register.

1. How many bars must be used to represent a single digit?
2. A complication of the laser scanning system is that the bar code must be read either forwards or backwards.Now how many bars are needed to represent each digit?
3. What is the probability that the 11-digit code is read correctly if the probability of reading a singlebit incorrectly is $p_e$ ?
4. How many error correcting bars would need to be present so that any single bar error occurring in the11-digit code can be corrected?

Error correcting codes

A code maps pairs of information bits into codewords of length 5 as follows.

1. What is this code's efficiency?
2. Find the generator matrix $G$ and parity-check matrix $H$ for this code.
3. Give the decoding table for this code. How many patterns of 1, 2, and 3 errors are correctlydecoded?
4. What is the block error probability (the probability of any number of errors occurring in the decoded codeword)?

Digital communication

A digital source produces sequences of nine letters with the following probabilities.

1. Find a Huffman code that compresses this source. How does the resulting code compare with the best possible code?
2. A clever engineer proposes the following (6,3) code to correct errors after transmission through a digital channel.

   $c_1=d_1$	$c_4=d_1\mathop{\mathrm{xor}}{d}_2\mathop{\mathrm{xor}}{d}_3$
   $c_2=d_2$	$c_5=d_2\mathop{\mathrm{xor}}{d}_3$
   $c_3=d_3$	$c_6=d_1$

   What is the error correction capability of this code?
3. The channel's bit error probability is 1/8. What kind of code should be used to transmit data over this channel?

Overly designed error correction codes

An Aggie engineer wants not only to have codewords for his data, but also to hide the information from Rice engineers(no fear of the UT engineers). He decides to represent 3-bit data with 6-bit codewords in which none of the databits appear explicitly.

1. Find the generator matrix $G$ and parity-check matrix $H$ for this code.
2. Find a $3\times 6$ matrix that recovers the data bits from the codeword.
3. What is the error correcting capability of the code?

Error correction?

It is important to realize that when more transmission errors than can be corrected, error correction algorithmsbelieve that a smaller number of errors have occurred and correct accordingly. For example, consider a (7,4) Hammingcode having the generator matrix $$G=\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ \end{pmatrix}$$ This code corrects all single-bit error, but if a double bit error occurs, it corrects using a single-bit error correction approach.

1. How many double-bit errors can occur in a codeword?
2. For each double-bit error pattern, what is the result of channel decoding? Express your result as abinary error sequence for the data bits.