| Abstract |
Transmitting and transferring messages across noisy channels is an important practical problem. Coding theory provides methods which minimize the presence of errors during transmitting a message. The rise of the computers after 1950 was significant for the development of the so- called error-correcting codes, codes which detect and correct errors occurred during transmitting a message. The rise of this new field is mainly due to Shannon and Hamming. A code consists of three main parameters. The number M of the codewords, the length n of the codewords and the minimum distance d between them. It is important to construct codes with large M and small n for cheap transfers and also with large d in order to correct as much errors as possible. Main purpose of the essay is to find linear codes for which one of the three parameters is, given the other two, optimal. These problems are called main problems of the Coding Theory. We connect the problem of finding the maximum n, given n k, d and q, for which there exists an [n, k, d]q-code with another known problem: the finite packing problem. The problem, although it was solved quickly for d ≤ 3, it remains open until our days. We make use of Finite Geometries to face the problem and we present all the known results until now. We also introduce the known results in the case of the MDS codes (codes with d = k + 1), the well-known main conjecture on the MDS codes. Then, we try another approach to our problem, this of finding the minimum n, given k, n and d, for which there exists an [n, k, d]q-code. The use of the Griesmer bound and a theorem of Belov make our problem a finite problem. We present all the known results in the case of the binary and the quaternary codes. Finally, we make use of the Gröbner Bases Theory to present a decoding algorithm for cyclic codes which can be generalized for all linear codes.
|
Εύρεση και αποκωδικοποίηση βέλτιστων κωδίκων με χρήση Πεπερασμένης Γεωμετρίας και Βάσεων Groebner
