Pascal matrices, Reed--Muller expressions and Reed--Muller error correcting codes

Radomir S. Stanković, Jaakko Astola, Claudio Moraga

Reed--Muller expressions are a way to analytically describe binary sequences viewed as truth-vectors of switching functions. Reed--Muller codes are a mean to improve reliability in transmitting binary sequences. Both concepts can be defined in terms of Reed--Muller matrices. These matrices can be viewed as a Pascal matrix (matrix of binomial coefficients) computed modulo $2$. The Pascal matrix is a key concept starting from which these two concepts, the Reed--Muller expressions and the Reed--Muller codes, can be developed. Further, the Pascal matrices give a way towards two different, but equally possible, interpretations of the Reed--Muller expressions. Their elements are coefficients in polynomial expressions, while their columns can be viewed as basis functions in particular spectral representations. Particular rows of the Pascal matrix modulo $2$ are selected to form the generator matrix of the Reed--Muller code. The link to Pascal matrices permits generalizations of the binary Reed--Muller codes into $p$-ary Reed--Muller codes. This link can be used conversely to define new functional expressions for $p$-valued functions.