A construction of Reed-Muller codes from boolean functions

Abstract

Boolean functions have important applications in cryptography and coding theory. A famous class of binary codes derived from Boolean functions are the Reed-Muller (RM) codes. These were defined by Reed, and Muller built the way of decoding and implicitly detecting and correcting errors. One of these codes (RM(1,5)) was used in 1969 by the Mariner probe to transmit images from the Moon. Each pixel in the image was assigned one of 26 = 64 degrees of shade, and the six bits of information were encoded in a word of length 32. The RM(1,5) code can correct up to 7 independent errors.