Fast Generation and Covering Radius of Reed-Muller Codes

Reed-Muller codes are known to be some of the oldest, simplest and most elegant error correcting codes. Reed-Muller codes were invented in 1954 by D. E. Muller and I. S. Reed, and were an important extension of the Hamming and Golay codes because they gave more flexibility in the size of the codeword and the number of errors that could be correct. The covering radius of these codes, as well as the fast construction of covering codes, is the main subject of this thesis. The covering radius problem is important because of the problem of constructing codes having a specified length and dimension. Codes with a reasonably small covering radius are highly desired in digital communication environments. In addition, a new algorithm is presented that allows the use of a compact way to represent Reed-Muller codes. Using this algorithm, a new method for fast, less complex, and memory efficient generation of 1st and 2nd order Reed - Muller codes and their hardware implementation is possible. It is also allows the fast construction of a new subcode class of 2nd order Reed-Muller codes with good properties. Finally, by reversing this algorithm, we introduce a code compression method, and at the same time a fast, efficient, and promising error-correction.