0.13 Coding  (Page 22/22)

where $I_k$ is the $k$ by $k$ identity matrix and $P$ is some $k$ by $n-k$ matrix, then

where the 0 is the $k$ by $n-k$ matrix of all zeroes. Hence, define $H=[-P|I_{n-k}]$ . Observe that the (5,2) code is of this form, since inbinary arithmetic $-1=+1$ and so $-P=P$ .

A (7,3) binary code has generator matrix

and parity check matrix

The syndrome [link] is built by calculating which error pattern is most likely (i.e., has the fewest bits flipped) for eachgiven syndrome $e{H}^T$ . This code has $d_{min}=4$ , and hence the code can correct any 1-bit errors, 7 (out of 21) possible 2-bit errors,and 1 of the many 3-bit errors.

Using the code from blockcode52.m , implement the binary (7,3) linear block code. Compare its performance and efficiencywith the (5,2) codeand to the majority rules code.

1. For each code, plot the percentage p of bit flips in the channel versus the percentage of bit flips in thedecoded output.
2. For each code, what is the average number of bits transmitted for each bit in the message?

Sometimes, when the source alphabet is not binary, the elements of the code words are also not binary.In this case, using the binary arithmetic of [link] is inappropriate. For example, consider a source alphabetwith 5 symbols labelled $0,1,2,3,4$ . Arithmetic operations for these elements areaddition and multiplication modulo 5, which are defined in [link] . These can be implemented in M atlab using the mod function. For some source alphabets, the appropriate arithmetic operations are notmodulo operations, and in these cases, it is normal to simply define the desired operationsvia tables like [link] and  [link] .

A (6,4) code using a $q=5$ element source alphabet has generator matrix

and parity check matrix

since, in mod 5 arithmetic, $-4=1$ , $-3+2$ , $-2=3$ , and $-1=4$ . Observe that these fit in the general form of [link] and [link] . The syndrome [link] lists the $q^{n-k}=5^{6-4}=25$ syndromes and corresponding errors.

The code in this example corrects all one-symbol errors (and no others).

Encoding a compact disc

The process of writing to and reading from a compact disc is involved. The essential idea in optical media is that alaser beam bounces off the surface of the disc. If there is a pit, then the light travels a bit further than if there isno pit. The distances are controlled so that the extra time required by the round tripcorresponds to a phase shift of 180 degrees. Thus, the light travelling back interferes destructivelyif there is a pit, while it reinforces constructively if there is no pit. The strength of the beam is monitored todetect a 0 (a pit) or a 1 (no pit).

While the complete system can be made remarkably accurate, the reading and writing procedures are prone to errors.This is a perfect application for error correcting codes! The encoding procedure is outlined in [link] . The original signal is digitized at $44,100$ samples per second in each of two stereo channels. Each sample is 16bits, and the effective data rate is 1.41 Mbps (mega bits per second).The Cross Interleave Reed–Solomon Code (CIRC) encoder (described shortly) has an effective rate of about

3/4, and its output is at 1.88 Mbps. Then control and timing information is added,which contains the track and subtrack numbers that allow CD tracks to be accessed rapidly.The “EFM” (Eight-to-Fourteen Module) is an encoder that spreads the audio information in timeby changing each possible 8-bit sequence into a predefined 14-bit sequence so that each oneis separated by at least two (and at most ten) zeros. This is used to help the tracking mechanism.Reading errors on a CD often occur in clusters (a small scratch may be many hundreds of bits wide) and interleavingdistributes the errors so that they can be corrected more effectively. Finally, a large number of synchronizationbits are added. These are used by the control mechanism of the laser to tell it where to shine the beam in orderto find the next bits. The final encoded data rate is 4.32 Mbps. Thus, about 1/3 of the bits on the CDare actual data, and about 2/3 of the bits are present to help the system function and to detect (and/or correct) errorswhen they occur.

The CIRC encoder consists of two special linear block codes called Reed–Solomon codes (which are named after their inventors).Both use $q=256$ (8-bit) symbols, and each 16-bit audio sample is split into two code words.The first code is a (32,28) linear code with $d_{min}=5$ , and the second code is a linear (28,24) code, also with $d_{min}=5$ . These are nonbinary and use special arithmetic operationsdefined by the “Galois Field” with 256 symbols. The encoding is split into two separate codes so thatan interleaver can be used between them. This spreads out the information over a larger range and helps to spread outthe errors (making them easier to detect and/or correct).

The encoding process on the CD is completely specified, but each manufacturer can implement the decoding as they wish.Accordingly, there are many choices. For instance, the Reed–Solomon codes can be used to correct two errors each, or to detect upto five errors. When errors are detected, a common strategy is to interpolate the audio, which may be transparent to the listeneras long as the error rate is not too high. Manufacturers may also choose to mute the audio when the error rate is too high.For data purposes, the controller can also ask that the data be reread. This may allow correction of the error whenit was caused by mistracking or some other transitory phenomenon, but will not be effective if the cause is a defect in the medium.

For further reading

The paper that started information theory is still a good read half a century after its initial publication.

• C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal , vol. 27, pp. 379–423 and 623–656, July and October, 1948.