MK&REŽ Telecommunications

Design of Good Linear Error Correcting Codes

One of the major issues in algebraic coding theory is the determination of bounds on the maximum achievable distance between codewords for a given code size. Lower bounds are usually devised through construction techniques which provide a code with the required parameters. A good code is defined as one which achieves the largest known minimum distance. The resulting "error-control codes" of our program insert redundancy into the transmitted codeword. As a result, the receiver can detect and correct errors that occur through the transmission path.  

This project, supervised by Dr. Aaron Gulliver of Electrical and Computer Engineering Department, investigated the development of techniques and/or application of existing techniques for constructing good codes which improve these bounds. The aim of this project,  was to design and test a C program which generates all the "error-correction codes", which would be used in any communication system's receiver. These codes, namely "Greedy Codes", are generated, using the following parameters as the program's inputs:

• n   is the length of the typical codeword (i.e. the number of bits per codeword) that is being transmitted through the channel,

• q   is the arithmetic base that we are working with. For instance, "binary" will have q=2, "quaternary" would have q=4,

• dmin is the minimum tolerance of the Hamming distance (i.e. the number of different bits) between any two codewords.

The program's results will be based on the three parameters. The result will comprise of the error-correction codes PLUS the dimension of the matrix which contains the codes. This would give Dr.Gulliver the chance to double-check his results on any system which he is analyzing, for his research. These codes must be "orthogonal" and "self-orthogonal". The first one means that ANY two code vectors must have inner product of zero. Second means that they must be orthogonal with respect to each other, PLUS any codeword be orthogonal to itself also.

At the end, the summary of results of our program are tabulated according to Dr.Gulliver's request inside the final report. The final report could be found from the Reports page.