Reed-Muller Codec simulation performance.(Technical report)

INTRODUCTION

Reed-Muller (RM) Codes are a family of linear error-correcting codes used in communications and are one of the oldest error correcting codes. However, error correcting codes play an important role in computational complexity theory and are very useful in sending information over long distances in which errors might occur in the message.

These codes were discovered by D.E Muller and were provided with a decoding algorithm by Irving S. Reed in 1954. As telecommunication expanded, Reed- Muller Codes become more prevalent as the needs for Codes has been widely used in many applications, as it is the most well known decomposable codes. In fact, Reed-Muller Code was used by Mariner 9 to transmit black and white photographs of Mars in 1972 (1).

The outline of this paper is as follows. The coding theory of Reed-Muller codes and its parameters were presented. The implementation of these codes was shown where Reed-Muller codes were introduced and the encoding and decoding matrices were constructed. The example of encoding and decoding a message using this code was shown. Apart from that, the encoding and decoding of Reed-Muller codes using MATLAB simulation was included under this part, in which the Reed-Muller codes were encoded in MATLAB and the output is compared with the theoretical one. The findings, discussion and analysis of the results were presented

MATERIALS AND METHODS

Coding theory of RM codes and its parameters: Reed-Muller can be defined as follow: r rank RM code R (r, m) is the code we get when the true table of a m elements Boolean function whose order is not larger than r is treated. In other words, an rth order of Reed- Muller Code R (r, m) is the set of all binary string (vectors) of length n = [2.sup.m]

RM codes consist of three theorems that could be deduced from the definition above (2), (3).

Theorem 1: Assume that the check matrix of Hamming Code is H and its column vectors equal to the correspondent column serial number and then the dual code of increased Hamming code is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a 1st order RM code R (1, m).

Theorem 2: Generator matrix of (r+1) order RM codeR (r+1, m+1) order can be derived from the generator matrix (r+1) order of RM code R R (r+1, m) and of [r.sub.th] order of RM code R(r, m) by equation below R(r+1, m) and of [r.sub.th] order of RM code R (r, m) by equation below:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Theorem 3: For any 0 [less than or equal to] r [less than or equal to] m-1, R (m-r-1, m) and R (r, m) are dual reciprocally.

From the se the orem stated above, it is known that RM codes are linear nonsystematic codes on GF (2) field. for every integer m and r <m, there exist a rth order of [2.sup.m] length RM code. The parameters of Reed-Muller code are:

Block length: n = [2.sup.m] (2)

Information length: k = [r.[summation over (i=0)]] [C.sub.m] (3)

Minimum distance: d = [2.sup.[m-r]] (4)

As the definition stated before, a[r.sup.th] order of Reed- Muller …