# The art of error correcting coding - Moreloz R.H.

ISBN 0471-49581-6

**Download**(direct link)

**:**

**17**> 18 19 20 21 22 23 .. 86 >> Next

An elegant definition of binary RM code is obtained with the use of binary polynomials (or Boolean functions). With this definition, RM codes become close relatives of BCH codes and RS codes, all members of the class of polynomial codes1.

2.3.1 Boolean polynomials and RM codes

This section closely follows the development of [MS]. Let /(xi,X2, ? ,xm) denote a Boolean junction on m binary-valued variables xi,x2, ,xro. It is well known that such a function can be specified by a truth table. The truth table lists the value of / for all 2m combinations of values of its arguments. All the usual Boolean operations (such as AND,OR) can be defined in a Boolean function.

Example 15 Consider the function f(xi, x2) with the following truth table:

X2 0 0 1 1

Xi 0 1 0 1

fix 1,X2) 0 1 1 0

Then,

f{xi,x2) = (xi AND NOT(x2)) OR (NOT(xj) AND x2).

Associated with each Boolean function /, let / denote the binary vector of length 2m which is obtained from evaluating / at all possible 2m values of the m variables x\, x2, ? , xm. In the example above, / = (0110), where the convention taken for ordering the bit positions of / is in accordance to a binary representation of integers, with xj being the least-significant bit (LSB) and xm the most-significant bit (MSB).

Note also that a Boolean function can be written directly from its truth table to get the disjunctive normal form (DNF). Using the DNF, any Boolean function can be expressed as

2 Polynomial codes are presented in Section 3.4.

28

THE ART OF ERROR CORRECTING CODING

the sum3 of 2m elementary functions: l,x\,X2, ,xm, xix2, , X1X2 ??? xm, such that

/ = 1 + aixi + a2x2 H + amxm + ai2xix2 H h ai2...mx\X2 %, (2-4)

where I is added to account for independent terms (degree 0). For Example 15, f = x 1 + x2-A binary RM (2m, k, 2m-r) code, denoted RMrim, is defined as the set of vectors associated with all Boolean functions of degree up to r in m variables. RMr,m is also known as the r-th order RM code of length 2m. The dimension of RMrjfn can easily by shown to be equal to

which corresponds to the number of ways polynomials of degree up to r can be constructed with m variables.

In view of Equation (2.4), a generator matrix for RMrim is formed by taking as rows the vectors associated with the k Boolean functions which can be expressed as polynomials of degree up to r in m variables.

Example 16 The first-order RM code of length 8, RMij3, is an (8,4,4) binary code, and can be constructed from Boolean functions of degree up to 1 in 3 variables: {\,x\,x2,xi}, so that

1= 11111111 X! = 0 0 0 0 1 1 1 1

x2 = 0 0 1 1 0 0 1 1

x3 = 0 1 0 1 0 1 0 1

A generator matrix for RMi,3 is thus

/ 1 \ /1 1 1 1 1 1 1 1\

_ ( xx I [OOOOIIII]

G - *2 - 0 0 1 1 0 0 1 1 (2 5)

\x3J Vo 1 0 1 0 1 0 1/

Note that code RMii3 can be also obtained from a Hamming (7,4,3) code by appending at the end of each codeword an overall parity-check bit. The only difference between the extended Hamming code and RMj 3 will be a possible permutation of bit (column) positions.

Dual codes of RM codes are also RM codes

It can be shown that RMm_r-i,m is the dual code of RMr-m. In other words, the generator matrix of RMm_r_i,m can be used as a parity-check matrix of RMrjTO.

2.3.2 Finite geometries and majority-logic decoding

RM codes can be formulated in terms of a finite geometry. An Euclidean geometry EG(m, 2) of dimension m over GF{2) consists of 2m points, which are all the binary vectors of length

3 sum means logical XOR and multiplication means logical AND in this context.

HAMMING, GOLAY AND REED-MULLER CODES

29

m. Note that the columns of the matrix formed by the last three rows of the generator matrix of RMlj3, see Example 16 above, are the 8 points of EG(3,2). If the zero point is deleted, then a projective geometry PG(m 1,2) is obtained. The reader is referred to [LC] for an excellent treatment of finite geometries and RM codes. Finite geometry codes are in fact a generalization of RM codes4.

The connection between codes and finite geometries can be introduced as follows: Consider EG(m, 2). The columns of the matrix (xjxf ? ? ? xJn)T are taken as the coordinates of points of the geometry EG(m, 2). Then, there is a one-to-one correspondence between the components of binary vectors of length 2TO and the points of EG(m, 2). A given binary vector of length 2m is associated with a subset of points of EG(m, 2). In particular, a subset of EG(m, 2) can be associated with each binary vector w = (v]\, W2, , 1^2) of length 2m,

by interpreting it as selecting points whenever to* = 1. Stated otherwise, w is an incidence

vector.

Binary Reed-Muller codes can then be defined as follows: The codewords of RMr,m are the incidence vectors of all subspaces (i.e., linear combinations of points) of dimension m r in EG(m, 2) (Theorem 8 of [MS]). From this it follows that the number of minimum weight codewords of RMr-ni is

m~r~ 4 tym-i -1

A2m_, = 2r TT -----------: (2.6)

**17**> 18 19 20 21 22 23 .. 86 >> Next