Linear codes and error-correction
Karen Brown · UNI ScholarWorks (University of Northern Iowa) · 1994
The process of encoding information for transmission from one source to another is a vital process in many areas of science and technology. Whenever coded information is sent, there arises a certain possibility that an error will occur, either during transmission or in decoding. Therefore, it is imperative to develop methods to detect and correct errors in a code. The study of coding theory is a "new" area of mathematics which is relatively undeveloped. This paper focuses on the properties of linear codes -and their corresponding methods of error-correction. To simplify the issue, only binary block codes are studied; hence all digits are either 0 or 1. The operation of addition is defined over modulo 2. In the decoding process, the principle of "maximum likelihood decoding" is used. This principle assumes that a minimum number of errors will occur in each codeword, since the overall probability of error decreases exponentially with the total number of errors. Whenever a string of digits is encoded, the digits are multiplied by a generator matrix, which returns the original digits and a specified number of check digits. The check digits are helpful in detecting and correcting errors. The parity check matrix, H, is also determined from the generator matrix. If the product of Hand the transpose of the received word is 0, then the received word is indeed a codeword. If the product is not 0, but is in fact the ith column of H, then an error occurs in the ith digit of the received string. The Hamming codes are specific linear codes which contain a maximum number of distinguishable columns. Therefore, the Hamming codes are ideal for error-correction, provided that only one error occurs in each codeword. It has been speculated that Hadamard matrices are ideal for the coding process, due to the mutual distinguishability of every row and column of the matrix. An Hadamard matrix is a square matrix of order n whose entries are 1 and -1 , and which satisfies the equation HHT = nl, where I is the identity matrix of order n. It is known that Hadamard matrices exist only for orders n = 1, n = 2 or n=0(mod 4). The rows and columns of the Hadamard matrix are orthogonal and linearly independent, which makes them ideal generator matrices. Hadamard matrices can be constructed using several different methods. In his paper Hadamard Matrices and Doubly Even Self-Dual Error Correcting Codes, Michio Ozeki proposed that if the rows of the generator matrix for a binary [n, k] code C all have weights divisible by 4 and are also orthogonal, then C is a doubly even self-dual code. Furthermore, when C is generated by a Hadamard matrix, the result is a doubly even self-dual linear [2n, n] code. It is now necessary to determine whether two codes will be equivalent if their corresponding Hadamard matrices are equivalent. The remainder of the paper will be devoted finding unique [56, 28] Hadamard codes. It is not known how many different Hadamard matrices exist of order 28. The method of integral equivalence will be used to determine the relationship between two distinct Hadamard matrices. A computer program will generate all of the individual codes.