Weight Enumerators and Weight Distribution of KM Codes

[摘要] In this thesis we will attempt to classify a particular class of KM codes (named after H. Krishna and S.D. Morgera). The construction of these codes is based mainly on the multiplicative complexity problem of multiplying two polynomials together, as this relates directly to a particular type of bilinear form and the main theorem linking codes and bilinear forms (Theorem 3.11) can then be invoked. We review work done by Winograd, Hopcroft and Musinski and Fiduccia on the general multiplicative complexity problem and work done by Lempel, Seroussi and Winograd on the topic of using the Chinese Remainder Theorem on this problem. We introduce a new method of looking for algorithms for polynomial multiplication, by way of diagrams. This will then enable us to produce many more related algorithms. We also develop two new bounds for the minimum number of multiplications needed to multiply two polynomials modulo ueta over F2 (which we denote by M2(eta-1,ueta)), namely one lower bound of 5/2(eta-1) and an attainable upper bound of eta2/4 + eta + 1 for eta even and eta2/4 + eta - 5/4 for eta odd. This attainable bound is used in the construction of the KM codes with wraparound later in the thesis. We also develop an attainable upper bound for the number of multiplications needed to multiply two polynomials modulo P(u) over F2 (which we denote by M2(eta-1,P(u))); again this turns out to be of the order eta2, but the algorithms are easily generalised for any eta. We fully classify KM codes for the parameter N(= k + d - 1) < 4 using these results on complexity and algorithm formation, and attempt the case of N = 5. This enables us to find that the optimal weight enumerator is obtainable by KM codes for N < 5. Next we introduce constant degree codes and obtain tables of the weight enumerators for the shunted (the idea of reducing/increasing k while increasing/decreasing d) families for w (the degree of the coprime polynomials used in the CRT) equals 2 and give the reader the proof of the generalising nature of our work. This last section is done in two separate ways, firstly we obtain results via the dual code weight enumerator and then dualise back to the primary code using the MacWilliams identities, and then we further develop the idea of using the dual code and look at the sets of the relations found and obtain results that use some complex linear algebra and operations on the vectors to express the weight distribution of the codes. The results obtained should serve as a basis for anybody using KM codes.

[发布机构] University:University of Glasgow

[关键词] Mathematics