19: Designs and Codes
- Page ID
- 60172
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
- 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.