19: Designs and Codes
( \newcommand{\kernel}{\mathrm{null}\,}\)
- 19.1: Introduction
- When information is transmitted, it may get garbled along the way. Error-correcting codes can make it possible for the recipient of a garbled message to figure out what the sender intended to say.
- 19.2: Error-Correcting Codes
- In order to be able to correct errors in transmission, we agree to send only strings that are in a certain set C of codewords. (So the information we wish to send will need to be “encoded” as one of the codewords.) The set C is called a code. Choosing the code cleverly will enable us to successfully correct transmission errors. When a transmission is received, the recipient will assume that the sender transmitted the codeword that is “closest” to the string that was received.
- 19.3: Using the Generator Matrix For Encoding
- Although many important error-correcting codes are constructed by other methods, we will only discuss the ones that come from generator matrices (except in Section 19.5).
- 19.4: Using the Parity-Check Matrix For Decoding
- Every Hamming code can correct all single-bit errors. Because of their high efficiency, Hamming codes are often used in real-world applications. But they only correct single-bit errors, so other binary linear codes (which we will not discuss) need to be used in situations where it is likely that more than one bit is wrong.
- 19.5: Codes From Designs
- An error-correcting code can be constructed from any design BIBD(v,k,λ) for which λ=1. Namely, from each block of the design, create a binary string of length v, by placing a 1 in each of the positions that correspond to points in the design, and 0s everywhere else. (However, this will not usually have a generator matrix, so it is not a binary linear code.)
- 19.6: Summary
- This page contains the summary of the topics covered in Chapter 19.