ABSTRACT
Reed-Muller (RM) codes belong to a class of linear error correcting codes that are both locally testable and decodable. They are some of the oldest codes that have been useful in sending messages over long distances or through channels where error might occur during transmission. They became more prevalent as telecommunications expanded and became useful as self-correcting codes. They are used in the design of probabilistic checkable proofs in complexity theory. Named after their discoverers, Irving S. Reed and D. E. Muller (see Reed [1954] and Muller [1954]), where the latter discovered the codes while the former provided the algorithm of logic decoding, these codes have the following special cases: Hadamard code (Chapter 9), Walsh-Hadamard code (Chapter 9), and Reed-Solomon code (Chapter 13).
