The Reed–Muller $RM(m, m)$ code sends the *message* $p(X_0, \ldots , X_{m - 1}) = \sum_{S \subset \{0, \ldots , m - 1\}} \alpha_S \cdot X_S$ to its set of evaluations $\left\{ p(x_0, \ldots , x_{m - 1}) \right\}_{(x_0, \ldots , x_{m - 1}) \in \{0, 1\}^m}$. This code is perhaps not very useful in practice, because both its message length and block size are $2^m$, its distance is 1, and its encoding function is a bijection. On the other hand, (efficiently) decoding (i.e., inverting) this map seems rather interesting. Decoding a codeword $\left\{ \beta_{x_0, \ldots , x_{m - 1}} \right\}_{(x_0, \ldots , x_{m - 1}) \in \{0, 1\}^m}$ amounts to finding its algebraic normal form. Though various methods apparently exist, I want to propose one:

It's fairly easy to show that decoding $\left\{ \beta_{x_0, \ldots , x_{m - 1}} \right\}_{(x_0, \ldots , x_{m - 1}) \in \{0, 1\}^m}$ amounts to multiplying it by the inverse of a certain $2^m \times 2^m$ matrix related to Pascal's triangle. This matrix appears in OEIS A047999; it's also discussed by Massey in connection with RM codes (see the matrix $\mathbf{M}_m$ in the section "two useful matrices"). It also appears in a number of places throughout the literature (see e.g. Preparata, Saluja and Ong, and an extremely interesting treatment by Callan which shows that the Thue–Morse sequence shows up in its inverse!). It also apparently shows up in the LU decomposition of the Walsh matrix; see this image. As an example, $\mathbf{M}_3$ is reproduced here:

$$\mathbf{M}_3 = \begin{bmatrix} 1 & & & & & & & \\ 1 & 1 & & & & & & \\ 1 & & 1 & & & & & \\ 1 & 1 & 1 & 1 & & & \\ 1 & & & & 1 & & & \\ 1 & 1 & & & 1 & 1 & & \\ 1 & & 1 & & 1 & & 1 & \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} $$

You can see that its 1 entries take the shape of Sierpinski's triangle.

Naïvely multiplying $\left\{ \beta_{x_0, \ldots , x_{m - 1}} \right\}_{(x_0, \ldots , x_{m - 1}) \in \{0, 1\}^m}$ by the inverse of this matrix would take $\Theta((2^m)^2)$ time. It seems like there should be an FFT-like recursive procedure which instead takes $O(2^m \cdot m)$ time. In fact, I'm sure I could work it out. But someone else must have done this already! Any reference would be appreciated. Thanks.