Vorlesung im Wintersemester 2004/05

Algorithmen für Gruppen und Codes

(Dr. Markus Grassl)


14. Vorlesung: Symmetrien und weitere Codeeigenschaften

Beispiel: C=[156,37,55]3

Vergleich: quasizyklischer Code mit 3 Generatormatrizen & allgemeiner Code mit 4 Generatormatrizen
w dlbqc dlb Anzahl Codeworte
1 8 9 185=2^7
2 12 15 6845=2^12
3 16 18 162245=2^17
4 20 24 2804045=2^21
5 24 27 37675805=2^25
6 28 30 409641245=2^28
7 32 36 3704192285=2^31
8 36 39 28413325085=2^34
9 40 45 187649958685=2^37
10 44 48 1079375106845=2^39
11 48 51 5456934925085=2^42
12 52 55 24426360804125=2^44
13 56   97385691108125=2^46

verbose output von Magma

> time MinimumWeight(c);
Linear Code over GF(3) of length 156 with 37 generators.
Lower Bound: 1, Upper Bound: 120
Constructed 3 distinct generator matrices
Relative Ranks:  37  37  37 
Cyclic Blocks:   52  52  52 
Time Taken: 0.02
Starting search for low weight codewords... (reset timings)
Enumerating using 1 generator at a time:
     New codeword identified of weight 79, time 0.00
     New codeword identified of weight 73, time 0.00
     New codeword identified of weight 72, time 0.00
     New codeword identified of weight 71, time 0.00
   Completed Matrix  1:  lower =  7, upper = 71. Elapsed: 0.00s
     New codeword identified of weight 69, time 0.00
   Completed Matrix  2:  lower =  8, upper = 69. Elapsed: 0.00s
   Completed Matrix  3:  lower =  9, upper = 69. Elapsed: 0.00s
Termination predicted with 15 generators at matrix 3
predicting enumerating 668788326465195 vectors (0.148526% of 156 37 code)
Enumerating using 2 generators at a time:
     New codeword identified of weight 65, time 0.00
   Completed Matrix  1:  lower = 11, upper = 65. Elapsed: 0.00s
   Completed Matrix  2:  lower = 13, upper = 65. Elapsed: 0.00s
     New codeword identified of weight 62, time 0.00
   Completed Matrix  3:  lower = 15, upper = 62. Elapsed: 0.00s
Termination predicted with 14 generators at matrix 1
predicting enumerating 108460669730475 vectors (0.024087% of 156 37 code)
Enumerating using 3 generators at a time:
   Completed Matrix  1:  lower = 16, upper = 62. Elapsed: 0.00s
   Completed Matrix  2:  lower = 17, upper = 62. Elapsed: 0.00s
     New codeword identified of weight 59, time 0.00
     New codeword identified of weight 58, time 0.00
   Completed Matrix  3:  lower = 18, upper = 58. Elapsed: 0.00s
Termination predicted with 13 generators at matrix 1
predicting enumerating 29247682543275 vectors (0.006495% of 156 37 code)
Enumerating using 4 generators at a time:
     New codeword identified of weight 56, time 0.00
   Completed Matrix  1:  lower = 20, upper = 56. Elapsed: 0.02s
   Completed Matrix  2:  lower = 22, upper = 56. Elapsed: 0.04s
   Completed Matrix  3:  lower = 24, upper = 56. Elapsed: 0.06s
Termination predicted with 12 generators at matrix 3
predicting enumerating 14655816482475 vectors (0.003255% of 156 37 code)
Enumerating using 5 generators at a time:
   Completed Matrix  1:  lower = 25, upper = 56. Elapsed: 0.36s
   Completed Matrix  2:  lower = 26, upper = 56. Elapsed: 0.63s
   Completed Matrix  3:  lower = 27, upper = 56. Elapsed: 0.89s
Termination predicted with 12 generators at matrix 3
predicting enumerating 14655816482475 vectors (0.003255% of 156 37 code)
Enumerating using 6 generators at a time:
   Completed Matrix  1:  lower = 28, upper = 56. Elapsed: 3.72s
   Completed Matrix  2:  lower = 29, upper = 56. Elapsed: 6.55s
   Completed Matrix  3:  lower = 30, upper = 56. Elapsed: 9.40s
Termination predicted at 560509 s (6 d 11 h 41 m 49 s) with 12 generators at matrix 3
predicting enumerating 14655816482475 vectors (0.003255% of 156 37 code)
Enumerating using 7 generators at a time:
   Completed Matrix  1:  lower = 32, upper = 56. Elapsed: 34.72s
   Completed Matrix  2:  lower = 34, upper = 56. Elapsed: 60.03s
   Completed Matrix  3:  lower = 36, upper = 56. Elapsed: 85.34s
Termination predicted at 562819 s (6 d 12 h 20 m 19 s) with 12 generators at matrix 3
predicting enumerating 14655816482475 vectors (0.003255% of 156 37 code)
Enumerating using 8 generators at a time:
   Completed Matrix  1:  lower = 37, upper = 56. Elapsed: 276.40s
   Completed Matrix  2:  lower = 38, upper = 56. Elapsed: 467.25s
   Completed Matrix  3:  lower = 39, upper = 56. Elapsed: 658.16s
Termination predicted at 565815 s (6 d 13 h 10 m 15 s) with 12 generators at matrix 3
predicting enumerating 14655816482475 vectors (0.003255% of 156 37 code)
Enumerating using 9 generators at a time:
   Completed Matrix  1:  lower = 41, upper = 56. Elapsed: 1879.96s
     New codeword identified of weight 55, time 1879.96
   Completed Matrix  2:  lower = 43, upper = 55. Elapsed: 3100.69s
   Completed Matrix  3:  lower = 45, upper = 55. Elapsed: 4321.63s
Termination predicted at 416922 s (4 d 19 h 48 m 42 s) with 12 generators at matrix 2
predicting enumerating 10861931306667 vectors (0.002412% of 156 37 code)
Enumerating using 10 generators at a time:
   Completed Matrix  1:  lower = 46, upper = 55. Elapsed: 11146.52s
   Completed Matrix  2:  lower = 47, upper = 55. Elapsed: 17969.18s
   Completed Matrix  3:  lower = 48, upper = 55. Elapsed: 24782.42s
Termination predicted at 415650 s (4 d 19 h 27 m 29 s) with 12 generators at matrix 2
predicting enumerating 10861931306667 vectors (0.002412% of 156 37 code)
Enumerating using 11 generators at a time:
   Completed Matrix  1:  lower = 49, upper = 55. Elapsed: 58261.93s
   Completed Matrix  2:  lower = 50, upper = 55. Elapsed: 91723.54s
   Completed Matrix  3:  lower = 51, upper = 55. Elapsed: 125191.34s
Termination predicted at 415319 s (4 d 19 h 21 m 58 s) with 12 generators at matrix 2
predicting enumerating 10861931306667 vectors (0.002412% of 156 37 code)
Enumerating using 12 generators at a time:
   Completed Matrix  1:  lower = 53, upper = 55. Elapsed: 270424.92s
   Completed Matrix  2:  lower = 55, upper = 55. Elapsed: 415408.97s
Computation complete 10861931306667 vectors enumerated in total
 (0.002412% of 156 37 code)
Final Results: lower = 55, upper = 55, Total time: 415408.98
55
Time: 415409.010
>


zurück zur Hauptseite
Diese Seite wird betreut von
Markus Grassl (grassl@ira.uka.de), IAKS, Arbeitsgruppe Quantum Computing, Fakultät für Informatik, Universität Karlsruhe
Letzte Änderung: 18.02.2004