Problems are listed in approximate order of difficulty. A single dot (•) indicates straigh...

Problems are listed in approximate order of difficulty. A single dot (•) indicates straightforward problems involving just one main concept and sometimes requiring no more than substitution of numbers in the appropriate formula. Two dots (••) identify problems that are slightly more challenging and usually involve more than one concept. Three dots (•••) indicate problems that are distinctly more challenging, either because they are intrinsically difficult or involve lengthy calculations. Needless to say, these distinctions are hard to draw and are only approximate.

•• An efficient error-correcting code. Consider a signal consisting of 16-bit message blocks accompanied by 8-bit check blocks; that is, 1/3 of the signal consists of check bits. Each 16-bit message block is arranged into a 4 × 4 array, and the 8 check bits are aligned with the top row and left column of the message, as shown, with the 16-bit message in the dark square in the lower right.

Each check bit is set so that there are an even number of 1s in every column and every row (in those 4 rows and 4 columns containing message bits). You should verify that this is true for the (message + check) array shown here. (a) Suppose a single-bit error occurs somewhere in the message block. How many check bits will violate the “even sum” rule? How can this information be used to identify and correct the mistake? (b) Suppose a single-bit error occurs somewhere in the check block. How many check bits will violate the “even-sum” rule? How does this information indicate that the error is not in the message, but in the check block? (c) Suppose that N × N message blocks are used instead of 4 × 4 message blocks. How many check bits are required? What fraction of signal bits are check bits? (d) Explain why this simple scheme fails if two errors occur in the same row or column.