International Journal of Algebra, Vol. 1, 2007, no. 1, 11 - 24
NEW GOOD QUASI-CYCLIC CODES OVER GF(3) Stelios D. Georgiou Department of Statistics and Actuarial-Financial Mathematics University of the Aegean 83200 Karlovassi, Samos, Greece e-mail:
[email protected] Christos Kravvaritis Department of Mathematics University of Athens Panepistemiopolis 15784 Athens, Greece e-mail:
[email protected] Abstract In this paper some good quasi-cyclic codes over GF(3) are presented. These quasi-cyclic codes improve the already known lower bounds on the minimum distance of the previously known quasi-cyclic codes. Even though these codes do not improve the minimum distance of the best unstructured code known, their beautiful structure and simplicity provide several advantages in comparison to other random codes. Also, three of the ternary quasi-cyclic codes presented have parameters [66, 11, 33; 3], [65, 13, 30; 3], [56, 14, 24; 3] and so their minimum distances beat the minimum distances of the previously known quasi-cyclic codes and meet the minimum distances of the best unstructured linear codes with these parameters.
Mathematics Subject Classification: 94B05, 94B25 Keywords: Quasi-cyclic codes, linear codes over GF(3).
1
Introduction
Let GF(q) denote the Galois field of q elements. A linear code over GF(q) of length n, dimension k and minimum Hamming distance d is called an [n, k, d; q]-code.
12
S. Georgiou and C. Kravvaritis
A code C is said to be quasi-cyclic (QC) if a cyclic shift of any codeword by p positions is also a codeword in C. This definition is a generalization of a cyclic code, which is actually a QC code with p = 1. Thus, quasi-cyclic codes are structured codes which can be generated, encoded and decoded easier and faster than random or unstructured codes. Their beautiful structure and simplicity attracted many researchers in this field, see for example [1, 4, 5, 8] and the references therein. It can be easily proved that QC codes can be characterized in terms of (m × m) circulant matrices. This means that a QC code can be described by a generator matrix of the form G = [R0 R1 R2 . . . Rp−1 ], where Ri , i = 0, 1, . . . , p − 1, are m × m circulant matrices of the form ⎡
R=
⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣
r0
r1 r0
rm−1 rm−2 rm−1 .. .. . . r1 r2
r2 · · · rm−1 r1 · · · rm−2 r0 · · · rm−3 .. .. . . r3 · · · r0
⎤ ⎥ ⎥ ⎥ ⎥ ⎥. ⎥ ⎥ ⎦
Consequently, n = mp. The algebra of m × m circulant matrices over GF (q) is isomorphic to the algebra of polynomials in the ring GF (q)[x]/(xm − 1) if R is mapped onto the polynomial r(x) = r0 + r1 x + r2 x2 + . . . + rm−1 xm−1 formed from the entries in the first row of R [4]. The polynomials ri (x) associated with a QC code are called the defining polynomials of the code. A good quasi-cyclic code [n, k, d; 3] is defined to be the one which has the maximum known minimum distance, among all quasi-cyclic codes, for given n and k, i.e., it attains or exceeds the known lower bound on the minimum distance. The purpose of this paper was to improve the known results on quasicyclic ternary codes regarding the minimum distance of such codes. Moreover, the authors intend to compare the results they found with the quasi-cyclic codes that were given in [3] and [5], and also to provide some new good quasicyclic codes for practical applications. This was done by developing the appropriate algorithms on the computer and by performing random searches when the exhaustive search was computationally impossible.
2
Some good QC codes
In this section some good quasi-cyclic codes are presented. The parameters of these codes are given in Tables 1- 7. The minimum distances dB of the
New good quasi-ciclic codes over GF(3)
13
best unstructured known code is given for comparison, and also the reference where this distance has been found. Table 8 gives the minimum distance dD of the best previously known quasi-cyclic codes. In the proof of the theorem, after the parameters of a code, its generators (the coefficients of the defining polynomials) are given separated by a comma and the weight distributions are calculated and presented in the form 01 , ab , cd , . . .. This form denotes that there exist one codeword of weight zero, b codewords of weight a, d codewords of weight c etc. In the following Tables by a ∗ and ∗∗ are denoted the extended BCH and the quadratic residue code respectively. In some cases more than one quasi-cyclic code was found and some of them where inequivalent since they have a different weight enumerator. For saving of space, these codes are not presented in this paper but are available on request. Theorem 2.1 There exist quasi-cyclic codes with parameters: [24, 8, 11; 3], [32, 8, 16; 3], [40, 8, 21; 3], [48, 8, 25; 3], [56, 8, 30; 3], [64, 8, 35; 3], [72, 8, 40; 3], [80, 8, 45; 3], [88, 8, 50; 3], [96, 8, 55; 3], [27, 9, 12; 3], [36, 9, 18; 3], [45, 9, 23; 3], [54, 9, 28; 3], [63, 9, 33; 3], [72, 9, 39; 3], [81, 9, 44; 3], [90, 9, 49; 3], [99, 9, 55; 3], [30, 10, 13; 3], [40, 10, 18; 3], [50, 10, 24; 3], [60, 10, 30; 3], [70, 10, 36; 3] [80, 10, 42; 3], [90, 10, 48; 3], [100, 10, 54; 3], [33, 11, 13; 3], [44, 11, 20; 3], [55, 11, 26; 3], [66, 11, 33; 3], [77, 11, 39; 3], [88, 11, 45; 3], [99, 11, 52; 3], [36, 12, 15; 3], [48, 12, 21; 3], [60, 12, 28; 3], [72, 12, 35; 3], [84, 12, 42; 3], [96, 12, 49; 3], [39, 13, 14; 3], [52, 13, 23; 3], [65, 13, 30; 3], [78, 13, 37; 3], [91, 13, 45; 3], [42, 14, 16; 3], [56, 14, 24; 3], [70, 14, 31; 3], [84, 14, 39; 3], [98, 14, 47; 3] Proof of Theorem 2.1 The generator matrix and the weight enumerator of each code is given. The generator vectors are separated by a comma. [24, 8, 11; 3]-code: 1 0 0 0 0 0 0 0, 2 0 2 0 2 2 0 0, 1 2 2 0 2 1 2 1 01 11224 12272 13416 14840 151024 16642 171536 18776 19384 20316 21112 2216 242 [32, 8, 16; 3]-code: 1 0 0 0 0 0 2 1, 0 0 2 2 0 2 0 2, 01 1 1 2 0 1 1, 2 1 0 2 1 2 00 01 16260 17352 18496 19512 20792 21864 221008 23896 24600 25448 26224 2764 2840 324 [40, 8, 21; 3]-code: 1 0 0 0 0 0 0 0, 1 1 1 1 1 0 2 0, 21 1 0 1 0 0 1, 1 1 0 1 1 0 1 1, 0 11 1 0 1 2 2 01 21544 241676 272576 301496 33256 3612 [48, 8, 25; 3]-code:
14
S. Georgiou and C. Kravvaritis
1 0 0 0 0 0 0 0, 2 1 0 0 0 1 1 0, 1 1 2 1 0 1 1 2, 2 0 1 1 2 1 0 2, 0 0 1 2 1 2 2 0, 11222222 01 25176 26240 2780 28400 29688 30272 311040 321108 33192 34928 35624 36168 37320 38224 3916 4052 4132 [56, 8, 30; 3]-code: 1 0 0 0 0 0 0 0, 0 1 1 2 0 0 0 1, 1 0 1 1 0 0 2 1, 1 2 0 2 0 2 2 0, 2 1 1 2 2 2 0 0, 0 2 2 0 1 2 2 0, 1 1 1 0 2 0 2 0 01 30208 31160 32252 33288 34400 35560 36792 37768 38856 39560 40552 41352 42280 43240 44140 4596 4640 4816 [64, 8, 35; 3]-code: 1 0 0 0 0 0 0, 2 0 1 2 0 1 1 1, 0 0 2 1 0 0 2 0, 1 0 1 2 2 2 2 1 2, 2 0 0 2 0 2 1 2, 0 0 0 0 0 1 0 2, 2 0 0 1 1 1 2 2, 2 2 0 2 1 0 2 0 01 35144 36160 37256 38392 39448 40592 41576 42512 43768 44620 45592 46488 47320 48296 49128 50192 5116 5236 5316 568 [72, 8, 40; 3]-code: 1 0 0 0 0 0 0 0, 2 1 0 1 2 2 0 1, 1 1 2 1 0 0 0 1, 1 0 2 1 1 1 0 1, 0 0 2 0 0 2 1 2, 2 1 1 1 0 0 1 2, 1 1 2 0 0 1 1 0, 1 1 2 2 0 1 1 2, 1 0 2 2 2 2 2 0 01 40120 41144 42352 43336 44384 45560 46392 47576 48912 49512 50432 51512 52440 53336 54264 55112 5672 5748 5816 6024 6116 [80, 8, 45; 3]-code: 1 0 0 0 0 0 0 0, 0 1 0 1 1 2 0 0, 2 2 2 2 2 0 0 0, 2 0 0 0 1 0 1 2, 1 2 0 1 0 0 2 0, 0 2 2 2 2 2 1 1, 1 1 0 1 2 2 2 2, 1 2 1 0 0 2 1 2, 2 2 2 1 2 1 2 2, 0 0 2 2 0 1 2 1 01 45336 48924 511408 541896 571312 60572 6380 6632 [88, 8, 50; 3]-code: 1 0 0 0 0 2 0 2, 0 0 0 2 1 2 0 2, 2 1 2 0 1 0 1 0, 0 0 1 0 1 2 1 2, 0 1 1 2 0 0 0 0, 1 0 0 2 0 2 1 0, 1 0 2 0 2 1 0 2, 1 0 0 2 1 2 1 2, 0 2 2 2 0 2 1 2, 2 1 2 2 2 0 1 1, 20112211 01 5088 51160 52240 53320 54448 55512 56516 57496 58400 59592 60560 61448 62432 63304 64370 65240 66200 67128 6864 708 7116 7218
New good quasi-ciclic codes over GF(3)
15
[96, 8, 55; 3]-code: 1 0 0 0 0 0 0 2, 0 0 1 1 1 1 1 2, 2 1 1 1 2 1 2 1, 0 1 0 1 0 1 1 0, 1 0 1 1 0 1 2 2, 1 0 2 2 0 0 2 2 01 55176 56304 5716 58328 59384 68604 6996 70312 71176 7232 73128
1 1 0 2 0 1 1 2, 2 2 0 1 0 1 2 2, 0 0 0 1 1 0 0 2, 2 1 0 0 0 2 0 1, 2 2 1 1 1 0 0 1, 0 2 0 1 2 2 1 2, 60216 61528 62568 63192 64836 65784 66160 67576 7464 7516 7632 7732
[27, 9, 12; 3]-code: 1 0 0 0 0 0 0 0 0, 0 0 1 1 1 0 0 0 2, 1 2 2 0 0 2 1 2 1 01 12576 154446 189420 214878 24360 272 [36, 9, 18; 3]-code: 1 0 0 0 0 0 0 1 1, 0 0 0 2 1 1 2 0 2, 1 2 1 1 1 1 1 1 2, 2 2 1 0 1 1 1 2 0 01 181110 214536 248100 275120 30810 366 [45, 9, 23; 3]-code: 1 0 0 0 0 0 0 0 0, 0 1 2 1 1 1 1 2 0, 1 1 1 0 2 0 2 2 1, 0 2 1 2 0 0 0 0 2, 2 2 0 2 20211 01 23576 24522 262160 271508 294500 302448 324230 331638 351512 36408 38144 3936 [54, 9, 28; 3]-code: 1 0 0 0 0 0 0 0 0, 0 1 0 1 1 0 1 2 1, 0 2 1 1 0 1 1 1 2, 0 0 2 1 2 2 0 2 0, 1 1 2 1 0 2 1 1 1, 0 1 0 1 1 0 0 2 0 01 28252 29414 30630 31810 321152 331356 341926 352016 362240 372070 381980 391770 401260 41774 42510 43306 44126 4554 4618 4718 [63, 9, 33; 3]-code: 1 0 0 0 0 0 0 0 0, 1 1 0 0 2 2 0 0 2, 2 1 2 1 0 0 1 1 0, 1 2 0 1 2 0 0 0 1, 2 2 0 1 1 2 2 0 1, 2 1 2 2 2 2 0 2 0, 0 0 2 2 0 2 0 1 2 01 33414 361896 394338 426084 454770 481926 51252 542 [72, 9, 39; 3]-code: 1 0 0 0 0 0 0 0 0, 0 0 2 1 1 2 2 1 1, 1 0 1 2 0 1 0 2 1, 2 1 1 2 2 2 0 0 0 , 2 0 0 1 1 2 2 0 1, 1 2 0 1 2 1 0 0 0, 0 2 0 2 1 0 0 0 1, 1 0 2 0 0 0 1 1 0 01 39594 422070 454134 485778 514572 542156 57324 6054 [81, 9, 44; 3]-code: 1 0 0 0 0 0 0 0 0, 0 0 0 0 0 1 1 2 2, 1 1 1 0 0 0 2 2 1, 0 1 1 1 0 1 1 2 0, 2 1 1 0 1 2 2 1 2, 0 1 1 0 2 2 0 2 1, 1 1 0 2 1 1 2 0 0, 1 21 1 1 1 1 2 2, 0 1 2 0 0 1 0 2 1 01 44144 45290 46432 47486 48528 49882 501404 511530 521584 531656 541788 551746 561620 571458 581134 59990 60744 61612 62270 63198 6472 6572 6624 6718
16
S. Georgiou and C. Kravvaritis
[90, 9, 49; 3]-code: 1 0 0 0 0 0 0 1 1, 0 0 1 1 2 1 0 2 0, 0 2 1 2 0 2 1 1 0, 1 0 0 1 1 2 0 0 2, 1 0 1 0 2 1 2 0 2, 1 0 2 0 1 1 1 0 0, 0 1 2 1 0 1 0 2 0, 2 20 2 2 1 1 1 2, 0 1 2 2 2 0 0 0 1, 012212221 01 49144 50162 51240 52450 53414 54782 551116 561170 571332 581620 591296 601794 611728 621530 631548 641134 65126066558 67450 68432 69252 70144 7154 7254 7318 [99, 9, 55; 3]-code: 1 0 0 0 0 0 0 0 0, 1 1 0 2 1 0 1 2 2, 0 1 2 1 1 0 0 1 1, 0 0 1 1 2 1 1 0 1, 1 1 2 0 0 1 2 1 2, 2 1 2 0 0 1 1 0, 2 0 2 2 0 2 1 0 1 2, 0 20 0 1 0 1 2 2, 1 2 0 0 0 0 2 2 1, 2 1 1 0 0 0 2 2 1, 1 2 0 2 2 1 0 2 1 01 5590 56216 57180 58540 59738 60972 61810 621224 631326 641278 651710 661656 671224 681728 691350 701098 711098 72804 73612 74450 75216 76126 77126 7854 7936 812 8218 [30, 10, 13; 3]-code: 1 0 0 0 0 0 0 0 0 0, 2 2 0 0 0 2 1 1 1 1, 1 0 0 1 1 0 1 0 1 0 01 13440 14870 151420 162600 174440 186550 197940 209036 218980 227030 234980 242630 251360 26600 27100 2870 302 [40, 10, 18; 3]-code: 1 0 0 0 0 0 0 0 0 2, 0 2 1 1 0 0 1 2 0 2, 0 2 2 0 2 0 2 0 1 0, 2 1 1 1 0 0 0 0 0 1 01 18240 19360 20690 211400 222320 233400 245400 256140 268070 277240 287690295640 305128 312660 321460 33720 34250 35180 3640 3720 [50, 10, 24; 3]-code: 1 0 0 0 0 0 0 0 0 0, 0 1 2 0 0 2 0 1 0 0, 2 1 2 1 0 0 0 0 0 2, 1 0 2 0 1 2 2 2 0 1, 0121021111 01 24210 25360 26780 271180 282100 292960 304550 314820 326080 337340 346760355804 366100 373960 382890 391480 40934 41400 42280 4320 4440 [60, 10, 30; 3]-code: 1 0 0 0 0 0 0 0 0 2, 0 0 1 2 0 2 0 1 1 2, 0 0 2 0 0 0 2 2 0 0 1, 1 0 1 2 0 1 1 0 2, 1 1 0 1 1 1 0 1 2 1, 1 1 1 2 1 2 2 2 2 1 01 30632 333020 3610640 3917900 4217470 457484 481790 51100 5410 602 [70, 10, 36; 3]-code: 1 0 0 0 0 0 0 0 0 2, 0 1 0 2 2 1 0 2 1 0, 0 0 1 2 2 1 0 2 0 1, 1 2 0 0 0 0 2 0 1 0, 0 0 1 1 0 1 1 0 0 2, 0 2 1 2 2 0 2 1 2 0, 0 1 1 1 2 2 0 0 1 1 01 36170 37520 38500 39900 401592412020 423220 433780 444840 455284 465430 475600 485660 494840 504542 513440 522790 531940 541010 55500 56140 57160 58150 5920
New good quasi-ciclic codes over GF(3)
17
[80, 10, 42; 3]-code: 1 0 0 0 0 0 0 0 0 0, 0 0 0 0 2 0 1 0 0 2, 2 2 0 0 2 2 0 2 2 0, 0 0 1 1 2 2 1 1 0 2, 1 1 2 1 1 2 0 0 1 2, 0 0 0 1 1 0 1 2 1 2, 1 0 2 1 2 0 2 2 0 2, 0 0 2 2 1 2 1 1 1 0 01 42630 452424 487520 5113520 5417130 5711900 604694 631000 66200 6920 7210 [90, 10, 48; 3]-code: 1 0 0 0 0 0 0 0 0 0, 2 0 1 1 0 0 0 0 0 2, 2 1 1 0 2 1 1 0 0 0, 0 1 0 1 1 1 2 1 0 0, 2 2 2 0 1 0 2 2 2 1, 0 1 2 1 1 2 1 2 2 0, 0 1 2 2 2 2 1 0 0 2, 0 1 1 2 0 0 1 2 0 0, 1010121200 01 48160 49320 50436 51940 521260531720 542020 552380 563750 573640 584810 595220 605342 615240 624670 634040 643610 652740 662620 671500 681130 69720 70280 71240 72200 7340 7420 [100, 10, 54; 3]-code: 1 0 0 0 0 0 0 0 0 0, 0 2 2 2 1 2 0 0 1 1, 0 1 2 2 0 2 0 1 2 2, 0 0 1 2 1 0 2 1 2 2, 0 0 2 1 2 2 2 2 0 2, 2 1 0 0 2 0 0 0 1 1, 0 2 0 2 0 2 0 1 1 2, 1 1 2 0 1 0 2 2 1 2, 0 2 1 0 2 2 1 1 1 0, 1 1 1 0 1 1 1 0 2 1 01 54240 55260 56450 57600 581090591300 601992 612160 623080 633600 644310 654920 664510 674900 684540 694620 704296 712880 723000 731980 741620 75920 76730 77580 78180 79180 8070 8120 8220
[33, 11, 13; 3]-code: 1 0 0 0 0 0 0 0 0 0 2, 0 1 1 0 2 2 2 1 2 1 1, 2 2 0 0 2 2 2 1 1 2 2 01 13242 14484 15968 162288 174796 189284 1914080 2018084 2123584 2225852 2325564 2420284 2514872 269064274752 281958 29792 30176 3222 [44, 11, 20; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 0 2 1 0 0 0 1 0 0 2 2, 0 1 2 1 1 2 0 0 1 1 1, 0 1 2 0 2 2 0 0012 01 20704 21858 236204 245280 2624596 2716544 2944528 3022176 3232604 3311946 358756 362112 38704 39132 442 [55, 11, 27; 3]-code: 1 0 0 0 0 0 0 0 0 0 2, 0 1 0 1 2 2 0 0 1 2 2, 0 0 2 2 2 0 1 0 0 1 2, 0 0 2 1 0 1 0 2 1 0 1, 1 1 0 2 1 2 1 0 2 1 1 01 271848 309856 3334476 3657970 3950380 4219272 453190 48154 [66, 11, 33; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 1 1 2 0 1 1 0 0 2 2 2, 1 0 2 1 0 0 2 1 0 0 0, 0 2 0 2 2 0 0 0 2 1 1, 0 0 2 1 2 0 1 2 1 0 0, 1 2 0 0 1 0 2 0 2 2 2 01 331234 366534 3923386 4246090 4555506 4832164 5110582 541562 5788
18
S. Georgiou and C. Kravvaritis
[77, 11, 39; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 2 0 1 0 0 1 1 0 2 2 1, 0 0 1 2 2 2 1 0 0 0 2, 2 2 0 0 1 1 1 2 0 2 1, 1 0 1 2 0 0 0 2 2 2 1, 0 2 1 1 0 0 0 1 0 0 0, 2 0 0 2 0 1 0 2 2 2 0 01 39968 424070 4515664 4835948 5151656 5441976 5720306 605852 63616 6690 [88, 11, 45; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 2 2 1 2 0 1 1 2 2 1 1, 0 2 2 2 2 1 0 1 1 1 1, 0 2 2 0 1 0 1 1 2 2 2, 0 0 2 1 0 0 0 1 0 1 0, 1 2 1 2 1 1 0 1 1 0 2, 2 1 0 2 0 0 0 0 2 0 1, 00022112122 01 45572 482574 5111088 5427324 5742702 6047322 6329788 6612432 692970 72374 [99, 11, 52; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 1 0 1 1 1 2 2 0 1 0 1, 0 1 0 2 2 1 0 0 1 2 1, 2 1 1 0 2 2 0 2 0 1 1, 2 1 0 2 2 2 2 0 1 1 1, 1 0 0 0 0 0 1 2 2 2 1, 1 2 1 1 1 0 0 1 0 1 0, 2 2 1 1 0 2 0 0 1 0 0, 2 0 0 1 2 0 0 2 1 0 2 01 52132 53594 54528 551144 561826 572200 583762 594906 606886 618866 629658 6311264 6413838 6514630 6615798 6713772 6813244 6913574 7010208 719042 726402 735060 744070 752464 761738 77792 78330 79264 8044 8166 8222 8422 [36, 12, 15; 3]-code: 1 0 0 0 0 0 0 0 0 0 1 0, 0 0 0 2 0 2 0 2 2 2 1 2, 0 2 1 1 1 0 1 2 1 0 2 2 01 151992 1825660 21122880 24224460 27133320 3022524 33600 364 [48, 12, 21; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 1, 0 2 1 2 2 1 0 0 0 2 1 1, 2 0 2 2 0 1 0 2 2 1 1 0, 0 1 0 1 10120011 01 21528 22684 231464 244512 256288 2611712 2723744 2826268 2935544 3064128 3154528 3258320 3376608 3448828 3538400 3639408 3718120 3811112 397056402676 41912 42528 4372 [60, 12, 28; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0, 2 1 2 1 0 2 2 1 2 0 1 0, 1 2 0 0 2 0 0 0 0 0 2 1, 1 1 1 2 0 1 0 0 2 2 2 0, 2 0 0 0 2 0 2 1 2 1 2 2 01 28504 29912 302032 312952 324878339664 3415084 3521960 3633094 3738664 3848744 3954368 4058302 4156880 4250708 4342840 4433168 4523216 4615588 478736 485070 492304 501116 51432 52180 5324 5420 [72, 12, 35; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 0 0 0 1 0 1 1 1 1 1 2 2 0, 2 0 0 2 1 1 1 2 0 0 0 2, 2 0 1 2 2 2 2 1 0 0 1 1, 0 1 1 1 0 2 1 2 0 1 1 2, 0 2 1 0 1 2 1 1 2 0 1 0 01 35456 36814 371560 382904 394512407386 4110632 4218068 4322416 4433312 4537248
New good quasi-ciclic codes over GF(3)
19
4645888 4750952 4852756 4953184 5045720 5141048 5234128 5325008 5418028 5510800 567146 573656 581908 591176 60530 61120 6284 [84, 12, 42; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 0 2 1 0 0 2 0 0 1 0 1 1 0, 0 2 2 1 0 2 2 2 0 0 0 2, 1 1 0 2 0 2 1 2 1 1 0 2, 0 0 2 2 0 2 2 0 1 1 2 1, 0 2 0 1 1 0 1 1 1 0 2 0, 1 1 1 2 0 2 0 0 0201 01 421020 456600 4826220 5175192 54128992 57144288 6097200 6341672 669276 69864 72116 [96, 12, 49; 3]-code: 1 0 0 0 0 0 0 0 0 0 0, 0 1 2 2 0 0 2 1 0 2 1 0 1, 1 1 0 1 2 0 1 0 0 1 0 0, 1 1 1 1 2 1 2 1 2 1 1 0, 1 2 1 1 0 2 0 0 1 2 1 1, 2 1 1 1 1 2 2 0 0 1 2 1, 2 0 2 2 2 0 2 2 0 1 0 2, 2 0 1 0 2 0 0 1 0 1 2 2 01 49384 50672 511096 521932 532976 544728 556960 569906 5714736 5819044 5924192 6032054 6135664 6241304 6345856 6444646 6545096 6642372 6738064 6831284 6926912 7020196 7114592 7210894 736552 744020 752616 761422 77768 78256 7996 80150 [39, 13, 14; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 2, 0 2 0 2 0 1 0 1 2 0 0 2 1, 1 2 1 2 1 0 0 0 2 1 0 2 1 01 15442 161040 172704 186240 1914638 2028106 2150856 2285332 23123864 24165646 25198874 26215126 27207038 28175448 29135538 3089778 3151246 3225740 3311284 344056 351092 36156 3778 [52, 13, 23; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0, 0 0 0 1 0 0 2 2 0 2 1 0 1, 0 1 0 2 0 0 2 1 0 2 0 2 0, 1 021122121020 01 231716 241898 2616252 2716120 2992794 3070902 32268944 33162500 35369928 36175526 38241384 3986112 4165130 4217186 446526 451196 47208 [65, 13, 30; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 2, 0 1 2 1 1 0 2 2 0 2 0 2 1, 0 0 2 1 2 0 2 2 1 2 0 1 0, 0 1 0 0 1 2 2 2 2 2 2 2 1, 2 1 2 1 2 0 0 1 0 1 1 2 2 01 301482 3315028 3678832 39257194 42463216 45461890 48245752 5162998 547566 57364 [78, 13, 37; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0, 0 1 2 0 1 1 0 1 2 2 2 0 1, 2 0 0 0 2 1 2 0 1 2 1 0 1, 2 1 2 2 1 0 0 0 1 1 0 1 0, 0 2 2 0 1 0 1 2 0 2 0 2 1, 0 1 0 1 2 1 2 0 1 2 1 0 1 01 37546 38858 391534 402678 415018429854 4315262 4424570 4535828 4652572 4775140 4896226 49115284 50130338 51145418 52153246 53150852 54137644 55119912 5697968 5777922 5856264 5936920 6023166 6114300 628346 633614 642002 65676 66208 67104 6826 6926 [91, 13, 45; 3]-code:
20
S. Georgiou and C. Kravvaritis
1 0 0 0 0 0 0 0 0 0 0 0 0, 1 0 0 2 2 1 1 2 1 1 2 1 2, 0 2 1 0 0 2 0 0 0 2 1 2 2, 0 0 0 2 0 1 1 1 0 2 2 2 0, 2 2 1 2 1 2 1 1 0 0 0 2 2, 1 1 1 2 2 2 0 1 2 2 0 2 0, 0 2 22202122211 01 451118 489750 5144304 54139984 57298246 60411060 63382226 66215098 6974646 7215834 752002 7854 [42, 14, 16; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0 0, 1 1 0 0 1 2 0 2 1 1 0 0 0 2, 0 0 1 2 2 0 2 0 1 1 1 1 1 2 01 16630 171708 183822 1910332 2024010 2147940 2295648 23163856 24260190 25370496 26486108 27584836 28619178 29598248 30519722 31401296 32275758 33166208 3489656 3541132 3615610 374900 381316 39364 424 [56, 14, 24; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0 0, 0 1 0 1 1 0 2 1 2 0 2 0 0 1, 1 0 2 1 0 0 1 0 2 0 2 1 0 1, 2 1 2 1 1 0 2 1 1 0 2 0 0 2 01 242058 2727132 30196280 33745920 361477084 391482152 42696648 45144592 4810850 51252 [70, 14, 31; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0 2, 0 1 2 0 2 0 1 2 0 1 1 1 0 2, 2 0 2 0 1 1 1 1 0 0 0 0 0 2, 1 1 1 1 2 2 1 1 1 1 0 1 1 2, 1 0 1 2 1 0 2 2 1 2 2 1 2 2 01 31504 32630 331540 343388 357784 3614224 3726040 3845108 3976972 40117110 41170800 42233300 43303436 44376754 45435960 46468202 47480340 48462630 49420308 50347410 51270900 52199892 53135940 5485946 5548776 5626084 5713496 585600 592632 60756 61336 62112 6356 702 ou [84, 14, 39; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0 1, 0 1 1 2 1 2 1 2 1 2 0 0 1 1, 2 2 2 0 1 0 1 2 0 0 2 2 2 2, 0 0 0 1 0 1 1 2 2 1 0 0 1 1, 1 2 2 2 2 0 1 0 2 0 2 0 0 1, 2 2 1 1 1 2 2 1 1 1 1 221 01 39364 40798 411288 422830 436776 4410542 4519180 4630870 4751772 4881998 49118272 50166054 51224196 52279510 53340788 54391090 55420868 56439154 57427140 58404236 59356244 60298830 61236824 62173446 63115892 6478092 6549056 6628616 6714336 687518 693920 701554 71644 72238 7528 774 [98, 14, 47; 3]-code: 1 0 0 0 0 0 0 0 0 0 0 0 0 0, 2 2 0 1 1 0 2 0 2 0 1 1 1 0, 0 2 2 2 2 0 0 2 0 0 2 1 2 2, 1 0 2 1 0 1 0 1 2 2 2 0 1 0, 2 0 0 1 0 2 2 2 21 2 0 1, 1 2 2 0 1 1 2 1 2 2 2 0 0 1 0, 1 1 2 1 0 2 2 0 2 2 0 0 1 1 01 47224 48728 491260 502716 514760 528134 5313468 5421938 5537324 5654908 5785036 58118426 59163212 60208390 61260260 62306740 63357900 64386736 65407960 66402808 67383124 68353878 69309064 70256004 71198072 72153258 73108136 7472688 7545500 7628126 7716072 788246794172 801974 811008 82406 83224 8460 8528
21
New good quasi-ciclic codes over GF(3)
code [24, 8] [32, 8] [40, 8] [48, 8] [56, 8] [64, 8] [72, 8] [80, 8] [88, 8] [96, 8]
d 11 16 21 25 30 35 40 45 50 55
dB 11 16 [3] 21 [3] 26 [3] 31 [7] 37 [3] 42 [7] 48 [2] 52 [6] 57 [8]
Table 1: Quasi-cyclic codes over GF(3), m = 8.
code [27, 9] [36, 9] [45, 9] [54, 9] [63, 9] [72, 9] [81, 9] [90, 9] [99, 9]
d dB 12 12 [11] 18 18 [9] 23 24 [9] 28 28 [8] 33 34 [3] 39 40 [3] 44 48 [2] 49 53 [6] 55 57 [8]
Table 2: Quasi-cyclic codes over GF(3), m = 9.
References [1] V. K. Bhargava, G. E. Sguin, and J. M. Stein, Some (mk.k) cyclic codes in quasi-cyclic form, IEEE Trans. Inform. Theory, 24 (1978), 630?632. [2] J. Bierbrauer and Y. Edel, New code parameters from Reed-Solomon subfield subcodes, IEEE Trans. Inf. Th. 43 (1997) 953-968. [3] A.E. Brouwer, Bounds on the minimum distance of linear codes, [Online], http:// www.win.tue.nl/ ∼aeb/ voorlincod.html, Available e-mail:
22
S. Georgiou and C. Kravvaritis
code [30, 10] [40, 10] [50, 10] [60, 10] [70, 10] [80, 10] [90, 10] [100, 10]
d 13 18 24 30 36 42 48 54
dB 13 [3] 19 [3] 25 [3] 31 [3] 36 [3] 45 ∗ 51 [3] 55 [3]
Table 3: Quasi-cyclic codes over GF(3), m = 10. code [33, 11] [44, 11] [55, 11] [66, 11] [77, 11] [88, 11] [99, 11]
d 13 20 26 33 39 45 52
dB 13 ∗∗ 21[3] 27 [3] 33 [3] 42 [3] 48 [3] 54 [3]
Table 4: Quasi-cyclic codes over GF(3), m = 11. code [36, 12] [48, 12] [60, 12] [72, 12] [84, 12] [96, 12]
d 15 21 28 35 42 49
dB 15 ∗∗ 21 [3] 28 [3] 36 [3] 45 [2] 51 [3]
Table 5: Quasi-cyclic codes over GF(3), m = 12.
[email protected], Eindhoven University of Technology, Eindhoven, The Netherlands. [4] Zhi Chen, Six New Binary Quasi Cyclic Codes, IEEE Trans. Inform. Theory, 40 (1994), 1666-1667. [5] R. N. Daskalov and T. A. Gulliver, New Good Quasi-Cyclic Ternary and
23
New good quasi-ciclic codes over GF(3)
code [39, 13] [52, 13] [65, 13] [78, 13] [91, 13]
d 14 23 30 37 45
dB 15 ∗∗ 23 [3] 30 [3] 41 [3] 47 [3]
Table 6: Quasi-cyclic codes over GF(3), m = 13.
code [42, 14] [56, 14] [70, 14] [84, 14] [98, 14]
d 16 24 31 39 47
dB 16 ∗∗ 24 [3] 32 [3] 43 [3] 49 [3]
Table 7: Quasi-cyclic codes over GF(3), m = 14.
code [44, 11] [55, 11] [66, 11] [48, 12] [60, 12] [52, 13] [65, 13] [56, 14]
d dD 20 20 26 26 33 32 21 21 28 28 23 24 30 29 24 23
Table 8: Comparison of the new quasi-cyclic codes with the previously best known quasi-cyclic codes.
Quaternary Codes, IEEE Trans. Inform. Theory, 43 (1997), 1647-1650. [6] M.A. de Boer, A ternary [91,9,54] code, preprint, 9504; A dual quaternary BCH code, 9502. Codes spanned by quadratic and Hermitian forms, IEEE Trans. Inform. Theory 42 (1996) 1600-1604. [7] T. A. Gulliver, New optimal ternary linear codes, IEEE Trans. Inform. Theory 41 (1995) 1182-1185.
24
S. Georgiou and C. Kravvaritis
[8] T. A. Gulliver and V. K. Bhargava, Two new rate 2/p binary quasi-cyclic codes, IEEE Trans. Inf. Theory 40 (1994) 1667-1668. [9] F.R. Kschischang and S. Pasupathy, Some ternary and quaternary codes and associated sphere packings, IEEE Trans. Inform. Theory 38 (1992) 227-246. [10] F. J. Mac Williams and N. J. A. Sloane, The Theory of Error-Correcting Codes, New-York:North-Holland, (1977). [11] V. Pless, On a new family of symmetry codes and related new 5-designs, Bull. Amer. Math. Soc. 75 (1969) 1339-1342. Received: July 11, 2006
