A NEW GENERALIZATION OF REED–MULLER CODES

Todd D. Vance

Abstract. An error–correcting code can be defined as a set of functions mapping P, called the set of places, to A, called the alphabet. With classical Generalized Reed–Muller Codes, P is an m–dimensional vector space F^{m} over a finite field F, and A is just the finite field F. Then, C = GRM(ν, m) is defined to be the set of all functions from P to A which, when represented as a polynomial of minimal degree through Lagrange interpolation, (see [2], for example) has degree less than or equal to ν.

This procedure can be generalized. C = A_{ν} is taken to be an element of the filtration of some filtered F –algebra B. A is another F –algebra, and P = HOM_{ALG} (B, A). Then, C = C_{ν}(B, A) is the set of elements of B_{ν} viewed as functions from P to A via b(x) := x(b) for x ∈ P and b ∈ B.

1. Filtered Algebras.

\underline{Definition 1 (Algebra)}. Let A be a vector space over a field F. In addition, define a multiplication μ : A × A → A that makes A a ring with unity. Assume also that F is injected in the center of A via f ↦ f1, where 1 is the identity of A. Then, A is an F –algebra or simply an algebra.

\underline{Definition 2 (Algebra Homomorphism)}. Let f: B → A, where A and B are F –algebras, be a linear map of vector spaces that is also a ring homomorphism taking the unit of B to the unit of A. Then, f is called a homomorphism from B to A. The set of all homomorphisms from B to A will be denoted HOM_{ALG} (A, B).

An example which motivates the remainder of the paper follows: let F be a field and X be any set. Then, we define the polynomial algebra with coefficients in F and indeterminates in X as the algebra F [X]: let X̂ be the free Abelian monoid generated by X. Then, the underlying set of F [X] is the vector space over F with standard basis X̂. Multiplication is just the multiplication in X̂ extended bilinearly to all of F [X]. For example, if X = {x_{1}, x_{2}, …, x_{n}}, then F [X] = F [x_{1}, x_{2}, …, x_{n}] is just the set of all polynomials over F with variables x_{1}, x_{2}, …, x_{n} along with the standard polynomial addition and multiplication.

It can be shown that F [X] is a free commutative F –algebra over the set X. This means that, given any set map ϕ : X → A, A any algebra, there is a unique algebra homomorphism ϕ^{♯}: F [X] → A that extends the domain of ϕ as a set map. For example, if X = {x_{1}, x_{2}, …, x_{m}} is a finite set and F [X] is the m–variable polynomial algebra over F, then let A = F be the one–dimensional algebra. Then, a set map ϕ: F [X] → F can be viewed as substitution of field elements for the variables. That is, each such ϕ is identified with an m–tuple (a_{1}, a_{2}, …, a_{m}) ∈ F^{m}. Then, ϕ^{♯} is just the homomorphism from F [X] to F that sends a polynomial f to f(a_{1}, a_{2}, …, a_{m}). In fact, all homomorphisms from F [X] to F arise in this way (by restriction of the homomorphism to X ⊂ F [X]). Thus, we have the identification of sets HOM_{ALG} (F [X], F) = F^{m}. More generally, for any X and any F –algebra A, we have HOM_{ALG} (F [X], A) = A^{X}, where A^{X} is the set of all set maps from X to A.

\underline{Definition 3 (Filter)}. Let B be an F –algebra. Let ℤ^{+} be the set of non– negative integers, i.e. ℤ^{+} = {0, 1, 2, … }. Suppose

B = ⋃_{ν∈ℤ^{+}} B_{ν}

where

B_{0} ⊂ B_{1} ⊂ B_{2} ⊂ · · · .

If, in addition, B_{ν}B_{μ} ⊂ B_{ν+μ} for ν, μ ∈ ℤ^{+}, then we say B is filtered. The list {B_{0}, B_{1}, … } is called a filter on B.

A filter is just a generalization of the degree of a polynomial. For example, if B = F [x_{1}, …, x_{m}] is the polynomial ring of m variables, then the standard filtering on B is

B_{ν} = {f ∈ B | deg f ≤ ν}.

More information about algebras and filtered algebras can be found in [4] and [5].

2. Algebraic Reed–Muller Codes.

\underline{Definition 4 (Code)}. Let A and P be sets. Let A^{P} be the set of all set maps f: P → A. Then a code is a subset C ⊂ A^{P}. A is called the alphabet of the code and P is the set of places.

Most often P and A, and therefore C are finite. Also, A is often taken to be a field and C is taken to be a vector subspace of A^{P}, which has a vector space structure on it through pointwise addition and scalar multiplication of the functions. See [1] for more information about codewords defined as functions.

Let B be any filtered F –algebra (with filtration {B_{0}, B_{1}, … }) and A another algebra. Then, let P = HOM_{ALG} (B, A). Then, we have a set map ρ: B → A^{P} defined as follows: for b ∈ B and x ∈ P, ρ(b): P → A via ρ(b)(x) = x(b). Note that more than one element of B can have the same image in A^{P} under ρ.

\underline{Definition 5 (Algebraic Reed–Muller Code)}. Let F be any field, and B, \{B_{ν}\}, A, P, and ρ be as above. The code

C_{ν}(B, A) = {c ∈ A^{P} | ρ(b) = c for some b ∈ B_{ν}}

is called the ν–th order algebraic Reed–Muller code in B and over A.

For example, if A = F is a finite field and A = F [x_{1}, …, x_{m}], then the C_{ν}(B, A) are just the classical generalized Reed–Muller codes which are well studied and often used in applications. Thus, we have a new generalization of Reed–Muller codes. (More information about classical generalized Reed–Muller codes can be found in [6], [3], and [1].)

Note that it is routinely shown that if A = F is a finite field and B any filtered algebra, then the C_{ν}(B, A) are equivalent to classical generalized Reed–Muller codes with some coordinate positions deleted. On the other hand, if A is an algebra that is not a field, then we have a generalization of Reed–Muller codes to a large class of non–field alphabets.

\underline{References}

1. E. F. Assmus and J. D. Key, Designs and Their Codes, Vol. 103 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 1993.

2. C. de Boor, “Topics in Multivariate Approximation Theory,” Topics in Numerical Analysis, Vol. 965 Lecture Notes in Mathematics, Springer–Verlag, New York, 1982, 39–78.

3. P. Delsarte, J.–M. Goethals, and F. J. MacWilliams, “On Generalized Reed– Muller Codes and Their Relatives,” Information and Control, 16 (1970), 403– 442.

4. N. Jacobson, Basic Algebra II, 2nd ed., W. H. Freeman and Company, New York, 1989.

5. C. Kassel, Quantum Groups, Vol. 155 of Graduate Texts in Mathematics, Springer–Verlag, New York, 1995.

6. T. Kasami, S. Lin, and W. W. Peterson, “Generalized Reed–Muller Codes,” Electron. Commun. Japan, 51 (1968), 96–104.

Todd D. Vance HC 66, Box 55 Moorefield, WV 26836