1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
|
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (guava) - Chapter 7:
Bounds on codes, special matrices and miscellaneous functions
</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap6.html">Previous Chapter</a> <a href="chapBib.html">Next Chapter</a> </div>
<p><a id="X7A814D518460862E" name="X7A814D518460862E"></a></p>
<div class="ChapSects"><a href="chap7.html#X7A814D518460862E">7. <span class="Heading">
Bounds on codes, special matrices and miscellaneous functions
</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X87C753EB840C34D3">7.1 <span class="Heading">
Distance bounds on codes
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8673277C7F6C04C3">7.1-1 UpperBoundSingleton</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X828095537C91FDFA">7.1-2 UpperBoundHamming</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82EBFAAB7F5BFD4A">7.1-3 UpperBoundJohnson</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A26E2537DFF4409">7.1-4 UpperBoundPlotkin</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X86A5A7C67F625A40">7.1-5 UpperBoundElias</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82366C277E218130">7.1-6 UpperBoundGriesmer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8301FA9F7C6C7445">7.1-7 IsGriesmerCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A5CB74485184FEE">7.1-8 UpperBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FDF54BA81115D88">7.1-9 LowerBoundMinimumDistance</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7CF15D2084499869">7.1-10 LowerBoundGilbertVarshamov</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8217D830871286D8">7.1-11 LowerBoundSpherePacking</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C6A58327BD6B685">7.1-12 UpperBoundMinimumDistance</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B3858B27A9E509A">7.1-13 BoundsMinimumDistance</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X817D0A647D3331EB">7.2 <span class="Heading">
Covering radius bounds on codes
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8320D1C180A1AAAD">7.2-1 BoundsCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7881E03E812140F4">7.2-2 IncreaseCoveringRadiusLowerBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7AD9F1D27C52BC0F">7.2-3 ExhaustiveSearchCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85D671F4824B4B0C">7.2-4 GeneralLowerBoundCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8638F5A67D6E50C1">7.2-5 GeneralUpperBoundCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E7FBCC87D5562AB">7.2-6 LowerBoundCoveringRadiusSphereCovering</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85E20C518360AB70">7.2-7 LowerBoundCoveringRadiusVanWee1</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C72994A825228E7">7.2-8 LowerBoundCoveringRadiusVanWee2</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F95362485759ACB">7.2-9 LowerBoundCoveringRadiusCountingExcess</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X829C14A383B5BF59">7.2-10 LowerBoundCoveringRadiusEmbedded1</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B0C81B88604C448">7.2-11 LowerBoundCoveringRadiusEmbedded2</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D27F6E27B9A0D35">7.2-12 LowerBoundCoveringRadiusInduction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80F8DFAD7D67CBEC">7.2-13 UpperBoundCoveringRadiusRedundancy</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X832847A17FD0D142">7.2-14 UpperBoundCoveringRadiusDelsarte</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X86F10D9E79AB8796">7.2-15 UpperBoundCoveringRadiusStrength</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8585C6A982489FC3">7.2-16 UpperBoundCoveringRadiusGriesmerLike</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82A38F5F858CF3FC">7.2-17 UpperBoundCoveringRadiusCyclicCode</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X806EBEC77C16E657">7.3 <span class="Heading">
Special matrices in <strong class="pkg">GUAVA</strong>
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82899B64802A4BCE">7.3-1 KrawtchoukMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87AFE2C078031CE4">7.3-2 GrayMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E1E7C5287919CDB">7.3-3 SylvesterMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8014A1F181ECD8AA">7.3-4 HadamardMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X797F43607AD8660D">7.3-5 VandermondeMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B47D82485B66F1D">7.3-6 PutStandardForm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D4EDA0A854EBFEF">7.3-7 IsInStandardForm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A97AD477E7638DE">7.3-8 PermutedCols</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B68119F85E9EC6D">7.3-9 VerticalConversionFieldMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8033E9A67BA155C8">7.3-10 HorizontalConversionFieldMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X804AAFF2867080F7">7.3-11 MOLS</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F34306B81DC2776">7.3-12 IsLatinSquare</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X81B9B40B7B2D97D5">7.3-13 AreMOLS</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7AB5E5CE7FDF7132">7.4 <span class="Heading">
Some functions related to the norm of a code
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8032E53078264ABB">7.4-1 CoordinateNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7ED2EF368203AF47">7.4-2 CodeNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D24F8BF7F9A7BF1">7.4-3 IsCoordinateAcceptable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87039FD179AD3009">7.4-4 GeneralizedCodeNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80283A2F7C8101BD">7.4-5 IsNormalCode</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X8308D685809A4E2F">7.5 <span class="Heading">
Miscellaneous functions
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X871286437DE7A6A4">7.5-1 CodeWeightEnumerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84DA928083B103A0">7.5-2 CodeDistanceEnumerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84B2BE66780EFBF9">7.5-3 CodeMacWilliamsTransform</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7903286078F8051B">7.5-4 CodeDensity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85303BAE7BD46D81">7.5-5 SphereContent</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7ACDC5377CD17451">7.5-6 Krawtchouk</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X827E39957A87EB51">7.5-7 PrimitiveUnityRoot</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X78AEA40F7AD9D541">7.5-8 PrimitivePolynomialsNr</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A2B54EF868AA752">7.5-9 IrreduciblePolynomialsNr</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B50D3417F6FD7C6">7.5-10 MatrixRepresentationOfElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7805D2BB7CE4D455">7.5-11 ReciprocalPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7AEA9F807E6FFEFF">7.5-12 CyclotomicCosets</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A4EA98D794CF410">7.5-13 WeightHistogram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X805DF25C84585FD6">7.5-14 MultiplicityInList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8072B0DA78FBE562">7.5-15 MostCommonInList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C5407EF87849857">7.5-16 RotateList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85E526367878F72A">7.5-17 CirculantMatrix</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7969103F7A8598F9">7.6 <span class="Heading">
Miscellaneous polynomial functions
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84D51EBB784E7C5D">7.6-1 MatrixTransformationOnMultivariatePolynomial </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80433A4B792880EF">7.6-2 DegreeMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X83F44E397C56F2E0">7.6-3 DegreesMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E9021697A61A60F">7.6-4 CoefficientMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79E76B6F7D177E27">7.6-5 SolveLinearSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80171AA687FFDC70">7.6-6 GuavaVersion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7EBBE86D85CC90C0">7.6-7 ZechLog</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C8C1E6A7E3497F0">7.6-8 CoefficientToPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8431985183B63BB7">7.6-9 DegreesMonomialTerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X860EF39B841380A1">7.6-10 DivisorsMultivariatePolynomial</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X82257DE97D1822AA">7.7 <span class="Heading">
GNU Free Documentation License
</span></a>
</div>
</div>
<h3>7. <span class="Heading">
Bounds on codes, special matrices and miscellaneous functions
</span></h3>
<p>In this chapter we describe functions that determine bounds on the size and minimum distance of codes (Section <a href="chap7.html#X87C753EB840C34D3"><b>7.1</b></a>), functions that determine bounds on the size and covering radius of codes (Section <a href="chap7.html#X817D0A647D3331EB"><b>7.2</b></a>), functions that work with special matrices <strong class="pkg">GUAVA</strong> needs for several codes (see Section <a href="chap7.html#X806EBEC77C16E657"><b>7.3</b></a>), and constructing codes or performing calculations with codes (see Section <a href="chap7.html#X8308D685809A4E2F"><b>7.5</b></a>).</p>
<p><a id="X87C753EB840C34D3" name="X87C753EB840C34D3"></a></p>
<h4>7.1 <span class="Heading">
Distance bounds on codes
</span></h4>
<p>This section describes the functions that calculate estimates for upper bounds on the size and minimum distance of codes. Several algorithms are known to compute a largest number of words a code can have with given length and minimum distance. It is important however to understand that in some cases the true upper bound is unknown. A code which has a size equalto the calculated upper bound may not have been found. However, codes that have a larger size do not exist.</p>
<p>A second way to obtain bounds is a table. In <strong class="pkg">GUAVA</strong>, an extensive table is implemented for linear codes over GF(2), GF(3) and GF(4). It contains bounds on the minimum distance for given word length and dimension. It contains entries for word lengths less than or equal to 257, 243 and 256 for codes over GF(2), GF(3) and GF(4) respectively. These entries were obtained from Brouwer's tables as of 11 May 2006. For the latest information, please see A. E. Brouwer's tables <a href="chapBib.html#biBBr">[Bro06]</a> on the internet.</p>
<p>Firstly, we describe functions that compute specific upper bounds on the code size (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><b>7.1-1</b></a>), <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>), <code class="func">UpperBoundJohnson</code> (<a href="chap7.html#X82EBFAAB7F5BFD4A"><b>7.1-3</b></a>), <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>), <code class="func">UpperBoundElias</code> (<a href="chap7.html#X86A5A7C67F625A40"><b>7.1-5</b></a>) and <code class="func">UpperBoundGriesmer</code> (<a href="chap7.html#X82366C277E218130"><b>7.1-6</b></a>)).</p>
<p>Next we describe a function that computes <strong class="pkg">GUAVA</strong>'s best upper bound on the code size (see <code class="func">UpperBound</code> (<a href="chap7.html#X7A5CB74485184FEE"><b>7.1-8</b></a>)).</p>
<p>Then we describe two functions that compute a lower and upper bound on the minimum distance of a code (see <code class="func">LowerBoundMinimumDistance</code> (<a href="chap7.html#X7FDF54BA81115D88"><b>7.1-9</b></a>) and <code class="func">UpperBoundMinimumDistance</code> (<a href="chap7.html#X7C6A58327BD6B685"><b>7.1-12</b></a>)).</p>
<p>Finally, we describe a function that returns a lower and upper bound on the minimum distance with given parameters and a description of how the bounds were obtained (see <code class="func">BoundsMinimumDistance</code> (<a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>)).</p>
<p><a id="X8673277C7F6C04C3" name="X8673277C7F6C04C3"></a></p>
<h5>7.1-1 UpperBoundSingleton</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundSingleton</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundSingleton</code> returns the Singleton bound for a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var> over a field of size <var class="Arg">q</var>. This bound is based on the shortening of codes. By shortening an (n, M, d) code d-1 times, an (n-d+1,M,1) code results, with M <= q^n-d+1 (see <code class="func">ShortenedCode</code> (<a href="chap6.html#X81CBEAFF7B9DE6EF"><b>6.1-9</b></a>)). Thus</p>
<p class="pcenter">
M \leq q^{n-d+1}.
</p>
<p>Codes that meet this bound are called <em>maximum distance separable</em> (see <code class="func">IsMDSCode</code> (<a href="chap4.html#X789380D28018EC3F"><b>4.3-7</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundSingleton(4, 3, 5);
25
gap> C := ReedSolomonCode(4,3);; Size(C);
25
gap> IsMDSCode(C);
true
</pre></td></tr></table>
<p><a id="X828095537C91FDFA" name="X828095537C91FDFA"></a></p>
<h5>7.1-2 UpperBoundHamming</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundHamming</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Hamming bound (also known as the <em>sphere packing bound</em>) returns an upper bound on the size of a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var>, over a field of size <var class="Arg">q</var>. The Hamming bound is obtained by dividing the contents of the entire space GF(q)^n by the contents of a ball with radius lfloor(d-1) / 2rfloor. As all these balls are disjoint, they can never contain more than the whole vector space.</p>
<p class="pcenter">
M \leq {q^n \over V(n,e)},
</p>
<p>where M is the maxmimum number of codewords and V(n,e) is equal to the contents of a ball of radius e (see <code class="func">SphereContent</code> (<a href="chap7.html#X85303BAE7BD46D81"><b>7.5-5</b></a>)). This bound is useful for small values of <var class="Arg">d</var>. Codes for which equality holds are called <em>perfect</em> (see <code class="func">IsPerfectCode</code> (<a href="chap4.html#X85E3BD26856424F7"><b>4.3-6</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundHamming( 15, 3, 2 );
2048
gap> C := HammingCode( 4, GF(2) );
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> Size( C );
2048
</pre></td></tr></table>
<p><a id="X82EBFAAB7F5BFD4A" name="X82EBFAAB7F5BFD4A"></a></p>
<h5>7.1-3 UpperBoundJohnson</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundJohnson</code>( <var class="Arg">n, d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Johnson bound is an improved version of the Hamming bound (see <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>)). In addition to the Hamming bound, it takes into account the elements of the space outside the balls of radius e around the elements of the code. The Johnson bound only works for binary codes.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundJohnson( 13, 5 );
77
gap> UpperBoundHamming( 13, 5, 2);
89 # in this case the Johnson bound is better
</pre></td></tr></table>
<p><a id="X7A26E2537DFF4409" name="X7A26E2537DFF4409"></a></p>
<h5>7.1-4 UpperBoundPlotkin</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundPlotkin</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">UpperBoundPlotkin</code> calculates the sum of the distances of all ordered pairs of different codewords. It is based on the fact that the minimum distance is at most equal to the average distance. It is a good bound if the weights of the codewords do not differ much. It results in:</p>
<p class="pcenter">
M \leq {d \over {d-(1-1/q)n}},
</p>
<p>where M is the maximum number of codewords. In this case, <var class="Arg">d</var> must be larger than (1-1/q)n, but by shortening the code, the case d < (1-1/q)n is covered.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundPlotkin( 15, 7, 2 );
32
gap> C := BCHCode( 15, 7, GF(2) );
a cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)
gap> Size(C);
32
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 1 ]
</pre></td></tr></table>
<p><a id="X86A5A7C67F625A40" name="X86A5A7C67F625A40"></a></p>
<h5>7.1-5 UpperBoundElias</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundElias</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Elias bound is an improvement of the Plotkin bound (see <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>)) for large codes. Subcodes are used to decrease the size of the code, in this case the subcode of all codewords within a certain ball. This bound is useful for large codes with relatively small minimum distances.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundPlotkin( 16, 3, 2 );
12288
gap> UpperBoundElias( 16, 3, 2 );
10280
gap> UpperBoundElias( 20, 10, 3 );
16255
</pre></td></tr></table>
<p><a id="X82366C277E218130" name="X82366C277E218130"></a></p>
<h5>7.1-6 UpperBoundGriesmer</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundGriesmer</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Griesmer bound is valid only for linear codes. It is obtained by counting the number of equal symbols in each row of the generator matrix of the code. By omitting the coordinates in which all rows have a zero, a smaller code results. The Griesmer bound is obtained by repeating this proces until a trivial code is left in the end.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundGriesmer( 13, 5, 2 );
64
gap> UpperBoundGriesmer( 18, 9, 2 );
8 # the maximum number of words for a linear code is 8
gap> Size( PuncturedCode( HadamardCode( 20, 1 ) ) );
20 # this non-linear code has 20 elements
</pre></td></tr></table>
<p><a id="X8301FA9F7C6C7445" name="X8301FA9F7C6C7445"></a></p>
<h5>7.1-7 IsGriesmerCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGriesmerCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsGriesmerCode</code> returns `true' if a linear code <var class="Arg">C</var> is a Griesmer code, and `false' otherwise. A code is called <em>Griesmer</em> if its length satisfies</p>
<p class="pcenter">
n = g[k,d] = \sum_{i=0}^{k-1} \lceil \frac{d}{q^i} \rceil.
</p>
<table class="example">
<tr><td><pre>
gap> IsGriesmerCode( HammingCode( 3, GF(2) ) );
true
gap> IsGriesmerCode( BCHCode( 17, 2, GF(2) ) );
false
</pre></td></tr></table>
<p><a id="X7A5CB74485184FEE" name="X7A5CB74485184FEE"></a></p>
<h5>7.1-8 UpperBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBound</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBound</code> returns the best known upper bound A(n,d) for the size of a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var> over a field of size <var class="Arg">q</var>. The function <code class="code">UpperBound</code> first checks for trivial cases (like d=1 or n=d), and if the value is in the built-in table. Then it calculates the minimum value of the upper bound using the methods of Singleton (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><b>7.1-1</b></a>)), Hamming (see <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>)), Johnson (see <code class="func">UpperBoundJohnson</code> (<a href="chap7.html#X82EBFAAB7F5BFD4A"><b>7.1-3</b></a>)), Plotkin (see <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>)) and Elias (see <code class="func">UpperBoundElias</code> (<a href="chap7.html#X86A5A7C67F625A40"><b>7.1-5</b></a>)). If the code is binary, A(n, 2* ell-1) = A(n+1,2* ell), so the <code class="code">UpperBound</code> takes the minimum of the values obtained from all methods for the parameters (n, 2*ell-1) and (n+1, 2* ell).</p>
<table class="example">
<tr><td><pre>
gap> UpperBound( 10, 3, 2 );
85
gap> UpperBound( 25, 9, 8 );
1211778792827540
</pre></td></tr></table>
<p><a id="X7FDF54BA81115D88" name="X7FDF54BA81115D88"></a></p>
<h5>7.1-9 LowerBoundMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundMinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In this form, <code class="code">LowerBoundMinimumDistance</code> returns a lower bound for the minimum distance of code <var class="Arg">C</var>.</p>
<p>This command can also be called using the syntax <code class="code">LowerBoundMinimumDistance( n, k, F )</code>. In this form, <code class="code">LowerBoundMinimumDistance</code> returns a lower bound for the minimum distance of the best known linear code of length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. It uses the mechanism explained in section <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> C := BCHCode( 45, 7 );
a cyclic [45,23,7..9]6..16 BCH code, delta=7, b=1 over GF(2)
gap> LowerBoundMinimumDistance( C );
7 # designed distance is lower bound for minimum distance
gap> LowerBoundMinimumDistance( 45, 23, GF(2) );
10
</pre></td></tr></table>
<p><a id="X7CF15D2084499869" name="X7CF15D2084499869"></a></p>
<h5>7.1-10 LowerBoundGilbertVarshamov</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundGilbertVarshamov</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is the lower bound due (independently) to Gilbert and Varshamov. It says that for each <var class="Arg">n</var> and <var class="Arg">d</var>, there exists a linear code having length n and minimum distance d at least of size q^n-1/ SphereContent(n-1,d-2,GF(q)).</p>
<table class="example">
<tr><td><pre>
gap> LowerBoundGilbertVarshamov(3,2,2);
4
gap> LowerBoundGilbertVarshamov(3,3,2);
1
gap> LowerBoundMinimumDistance(3,3,2);
1
gap> LowerBoundMinimumDistance(3,2,2);
2
</pre></td></tr></table>
<p><a id="X8217D830871286D8" name="X8217D830871286D8"></a></p>
<h5>7.1-11 LowerBoundSpherePacking</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundSpherePacking</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is the lower bound due (independently) to Gilbert and Varshamov. It says that for each <var class="Arg">n</var> and <var class="Arg">r</var>, there exists an unrestricted code at least of size q^n/ SphereContent(n,d,GF(q)) minimum distance d.</p>
<table class="example">
<tr><td><pre>
gap> LowerBoundSpherePacking(3,2,2);
2
gap> LowerBoundSpherePacking(3,3,2);
1
</pre></td></tr></table>
<p><a id="X7C6A58327BD6B685" name="X7C6A58327BD6B685"></a></p>
<h5>7.1-12 UpperBoundMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundMinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In this form, <code class="code">UpperBoundMinimumDistance</code> returns an upper bound for the minimum distance of code <var class="Arg">C</var>. For unrestricted codes, it just returns the word length. For linear codes, it takes the minimum of the possibly known value from the method of construction, the weight of the generators, and the value from the table (see <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>).</p>
<p>This command can also be called using the syntax <code class="code">UpperBoundMinimumDistance( n, k, F )</code>. In this form, <code class="code">UpperBoundMinimumDistance</code> returns an upper bound for the minimum distance of the best known linear code of length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. It uses the mechanism explained in section <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> C := BCHCode( 45, 7 );;
gap> UpperBoundMinimumDistance( C );
9
gap> UpperBoundMinimumDistance( 45, 23, GF(2) );
11
</pre></td></tr></table>
<p><a id="X7B3858B27A9E509A" name="X7B3858B27A9E509A"></a></p>
<h5>7.1-13 BoundsMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BoundsMinimumDistance</code>( <var class="Arg">n, k, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">BoundsMinimumDistance</code> calculates a lower and upper bound for the minimum distance of an optimal linear code with word length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. The function returns a record with the two bounds and an explanation for each bound. The function <code class="code">Display</code> can be used to show the explanations.</p>
<p>The values for the lower and upper bound are obtained from a table. <strong class="pkg">GUAVA</strong> has tables containing lower and upper bounds for q=2 (n <= 257), 3 (n <= 243), 4 (n <= 256). (Current as of 11 May 2006.) These tables were derived from the table of Brouwer. (See <a href="chapBib.html#biBBr">[Bro06]</a>, <span class="URL"><a href="http://www.win.tue.nl/~aeb/voorlincod.html">http://www.win.tue.nl/~aeb/voorlincod.html</a></span> for the most recent data.) For codes over other fields and for larger word lengths, trivial bounds are used.</p>
<p>The resulting record can be used in the function <code class="code">BestKnownLinearCode</code> (see <code class="func">BestKnownLinearCode</code> (<a href="chap5.html#X871508567CB34D96"><b>5.2-14</b></a>)) to construct a code with minimum distance equal to the lower bound.</p>
<table class="example">
<tr><td><pre>
gap> bounds := BoundsMinimumDistance( 7, 3 );; DisplayBoundsInfo( bounds );
an optimal linear [7,3,d] code over GF(2) has d=4
------------------------------------------------------------------------------
Lb(7,3)=4, by shortening of:
Lb(8,4)=4, u u+v construction of C1 and C2:
Lb(4,3)=2, dual of the repetition code
Lb(4,1)=4, repetition code
------------------------------------------------------------------------------
Ub(7,3)=4, Griesmer bound
# The lower bound is equal to the upper bound, so a code with
# these parameters is optimal.
gap> C := BestKnownLinearCode( bounds );; Display( C );
a linear [7,3,4]2..3 shortened code of
a linear [8,4,4]2 U U+V construction code of
U: a cyclic [4,3,2]1 dual code of
a cyclic [4,1,4]2 repetition code over GF(2)
V: a cyclic [4,1,4]2 repetition code over GF(2)
</pre></td></tr></table>
<p><a id="X817D0A647D3331EB" name="X817D0A647D3331EB"></a></p>
<h4>7.2 <span class="Heading">
Covering radius bounds on codes
</span></h4>
<p><a id="X8320D1C180A1AAAD" name="X8320D1C180A1AAAD"></a></p>
<h5>7.2-1 BoundsCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BoundsCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">BoundsCoveringRadius</code> returns a list of integers. The first entry of this list is the maximum of some lower bounds for the covering radius of <var class="Arg">C</var>, the last entry the minimum of some upper bounds of <var class="Arg">C</var>.</p>
<p>If the covering radius of <var class="Arg">C</var> is known, a list of length 1 is returned. <code class="code">BoundsCoveringRadius</code> makes use of the functions <code class="code">GeneralLowerBoundCoveringRadius</code> and <code class="code">GeneralUpperBoundCoveringRadius</code>.</p>
<table class="example">
<tr><td><pre>
gap> BoundsCoveringRadius( BCHCode( 17, 3, GF(2) ) );
[ 3 .. 4 ]
gap> BoundsCoveringRadius( HammingCode( 5, GF(2) ) );
[ 1 ]
</pre></td></tr></table>
<p><a id="X7881E03E812140F4" name="X7881E03E812140F4"></a></p>
<h5>7.2-2 IncreaseCoveringRadiusLowerBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IncreaseCoveringRadiusLowerBound</code>( <var class="Arg">C[, stopdist][, startword]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IncreaseCoveringRadiusLowerBound</code> tries to increase the lower bound of the covering radius of <var class="Arg">C</var>. It does this by means of a probabilistic algorithm. This algorithm takes a random word in GF(q)^n (or <var class="Arg">startword</var> if it is specified), and, by changing random coordinates, tries to get as far from <var class="Arg">C</var> as possible. If changing a coordinate finds a word that has a larger distance to the code than the previous one, the change is made permanent, and the algorithm starts all over again. If changing a coordinate does not find a coset leader that is further away from the code, then the change is made permanent with a chance of 1 in 100, if it gets the word closer to the code, or with a chance of 1 in 10, if the word stays at the same distance. Otherwise, the algorithm starts again with the same word as before.</p>
<p>If the algorithm did not allow changes that decrease the distance to the code, it might get stuck in a sub-optimal situation (the coset leader corresponding to such a situation - i.e. no coordinate of this coset leader can be changed in such a way that we get at a larger distance from the code - is called an <em>orphan</em>).</p>
<p>If the algorithm finds a word that has distance <var class="Arg">stopdist</var> to the code, it ends and returns that word, which can be used for further investigations.</p>
<p>The variable <var class="Arg">InfoCoveringRadius</var> can be set to <var class="Arg">Print</var> to print the maximum distance reached so far every 1000 runs. The algorithm can be interrupted with <strong class="button">ctrl-C</strong>, allowing the user to look at the word that is currently being examined (called `current'), or to change the chances that the new word is made permanent (these are called `staychance' and `downchance'). If one of these variables is i, then it corresponds with a i in 100 chance.</p>
<p>At the moment, the algorithm is only useful for codes with small dimension, where small means that the elements of the code fit in the memory. It works with larger codes, however, but when you use it for codes with large dimension, you should be <em>very</em> patient. If running the algorithm quits GAP (due to memory problems), you can change the global variable <var class="Arg">CRMemSize</var> to a lower value. This might cause the algorithm to run slower, but without quitting GAP. The only way to find out the best value of <var class="Arg">CRMemSize</var> is by experimenting.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> IncreaseCoveringRadiusLowerBound(C,10);
Number of runs: 1000 best distance so far: 3
Number of runs: 2000 best distance so far: 3
Number of changes: 100
Number of runs: 3000 best distance so far: 3
Number of runs: 4000 best distance so far: 3
Number of runs: 5000 best distance so far: 3
Number of runs: 6000 best distance so far: 3
Number of runs: 7000 best distance so far: 3
Number of changes: 200
Number of runs: 8000 best distance so far: 3
Number of runs: 9000 best distance so far: 3
Number of runs: 10000 best distance so far: 3
Number of changes: 300
Number of runs: 11000 best distance so far: 3
Number of runs: 12000 best distance so far: 3
Number of runs: 13000 best distance so far: 3
Number of changes: 400
Number of runs: 14000 best distance so far: 3
user interrupt at...
#
# used ctrl-c to break out of execution
#
... called from
IncreaseCoveringRadiusLowerBound( code, -1, current ) called from
function( arguments ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> current;
[ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
brk>
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X7AD9F1D27C52BC0F" name="X7AD9F1D27C52BC0F"></a></p>
<h5>7.2-3 ExhaustiveSearchCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ExhaustiveSearchCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">ExhaustiveSearchCoveringRadius</code> does an exhaustive search to find the covering radius of <var class="Arg">C</var>. Every time a coset leader of a coset with weight w is found, the function tries to find a coset leader of a coset with weight w+1. It does this by enumerating all words of weight w+1, and checking whether a word is a coset leader. The start weight is the current known lower bound on the covering radius.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> ExhaustiveSearchCoveringRadius(C);
Trying 3 ...
[ 3 .. 5 ]
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X85D671F4824B4B0C" name="X85D671F4824B4B0C"></a></p>
<h5>7.2-4 GeneralLowerBoundCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralLowerBoundCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralLowerBoundCoveringRadius</code> returns a lower bound on the covering radius of <var class="Arg">C</var>. It uses as many functions which names start with <code class="code">LowerBoundCoveringRadius</code> as possible to find the best known lower bound (at least that <strong class="pkg">GUAVA</strong> knows of) together with tables for the covering radius of binary linear codes with length not greater than 64.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> GeneralLowerBoundCoveringRadius(C);
2
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X8638F5A67D6E50C1" name="X8638F5A67D6E50C1"></a></p>
<h5>7.2-5 GeneralUpperBoundCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralUpperBoundCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralUpperBoundCoveringRadius</code> returns an upper bound on the covering radius of <var class="Arg">C</var>. It uses as many functions which names start with <code class="code">UpperBoundCoveringRadius</code> as possible to find the best known upper bound (at least that <strong class="pkg">GUAVA</strong> knows of).</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> GeneralUpperBoundCoveringRadius(C);
4
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X7E7FBCC87D5562AB" name="X7E7FBCC87D5562AB"></a></p>
<h5>7.2-6 LowerBoundCoveringRadiusSphereCovering</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusSphereCovering</code>( <var class="Arg">n, M[, F], false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusSphereCovering( n, r, [F,] true )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusSphereCovering</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p><var class="Arg">F</var> is the field over which the code is defined. If <var class="Arg">F</var> is omitted, it is assumed that the code is over GF(2). The bound is computed according to the sphere covering bound:</p>
<p class="pcenter">
M \cdot V_q(n,r) \geq q^n
</p>
<p>where V_q(n,r) is the size of a sphere of radius r in GF(q)^n.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusSphereCovering(10,32,GF(2),false);
2
gap> LowerBoundCoveringRadiusSphereCovering(10,3,GF(2),true);
6
</pre></td></tr></table>
<p><a id="X85E20C518360AB70" name="X85E20C518360AB70"></a></p>
<h5>7.2-7 LowerBoundCoveringRadiusVanWee1</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusVanWee1</code>( <var class="Arg">n, M[, F], false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusVanWee1( n, r, [F,] true )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusVanWee1</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p><var class="Arg">F</var> is the field over which the code is defined. If <var class="Arg">F</var> is omitted, it is assumed that the code is over GF(2).</p>
<p>The Van Wee bound is an improvement of the sphere covering bound:</p>
<p class="pcenter">
M \cdot \left\{ V_q(n,r) -
\frac{{n \choose r}}{\lceil\frac{n-r}{r+1}\rceil}
\left(\left\lceil\frac{n+1}{r+1}\right\rceil - \frac{n+1}{r+1}\right)
\right\} \geq q^n
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusVanWee1(10,32,GF(2),false);
2
gap> LowerBoundCoveringRadiusVanWee1(10,3,GF(2),true);
6
</pre></td></tr></table>
<p><a id="X7C72994A825228E7" name="X7C72994A825228E7"></a></p>
<h5>7.2-8 LowerBoundCoveringRadiusVanWee2</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusVanWee2</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusVanWee2( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusVanWee2</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \frac{\left( \left( V_2(n,2) - \frac{1}{2}(r+2)(r-1) \right)
V_2(n,r) + \varepsilon
V_2(n,r-2) \right)}
{(V_2(n,2) - \frac{1}{2}(r+2)(r-1) + \varepsilon)}
\geq 2^n,
</p>
<p>where</p>
<p class="pcenter">
\varepsilon = {r+2 \choose 2} \left\lceil
{n-r+1 \choose 2} / {r+2 \choose 2} \right\rceil
- {n-r+1 \choose 2}.
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusVanWee2(10,32,false);
2
gap> LowerBoundCoveringRadiusVanWee2(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7F95362485759ACB" name="X7F95362485759ACB"></a></p>
<h5>7.2-9 LowerBoundCoveringRadiusCountingExcess</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusCountingExcess</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusCountingExcess( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusCountingExcess</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( \rho V_2(n,r) + \varepsilon V_2(n,r-1) \right) \geq
(\rho + \varepsilon) 2^n,
</p>
<p>where</p>
<p class="pcenter">
\varepsilon = (r+1) \left\lceil\frac{n+1}{r+1}\right\rceil - (n+1)
</p>
<p>and</p>
<p class="pcenter">
\rho = \left\{
\begin{array}{l}
n-3+\frac{2}{n}, \ \ \ \ \ \ {\rm if}\ r = 2\\
n-r-1 , \ \ \ \ \ \ {\rm if}\ r \geq 3 .
\end{array}
\right.
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusCountingExcess(10,32,false);
0
gap> LowerBoundCoveringRadiusCountingExcess(10,3,true);
7
</pre></td></tr></table>
<p><a id="X829C14A383B5BF59" name="X829C14A383B5BF59"></a></p>
<h5>7.2-10 LowerBoundCoveringRadiusEmbedded1</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusEmbedded1</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusEmbedded1( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is 'false', then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( V_2(n,r) - {2r \choose r} \right) \geq
2^n - A( n, 2r+1 ) {2r \choose r},
</p>
<p>where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function <code class="code">UpperBound</code> is used to compute this value.</p>
<p>Sometimes <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is better than <code class="code">LowerBoundCoveringRadiusEmbedded2</code>, sometimes it is the other way around.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusEmbedded1(10,32,false);
2
gap> LowerBoundCoveringRadiusEmbedded1(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7B0C81B88604C448" name="X7B0C81B88604C448"></a></p>
<h5>7.2-11 LowerBoundCoveringRadiusEmbedded2</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusEmbedded2</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusEmbedded2( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusEmbedded2</code> is 'false', then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( V_2(n,r) - \frac{3}{2} {2r \choose r} \right) \geq
2^n - 2A( n, 2r+1 ) {2r \choose r},
</p>
<p>where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function <code class="code">UpperBound</code> is used to compute this value.</p>
<p>Sometimes <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is better than <code class="code">LowerBoundCoveringRadiusEmbedded2</code>, sometimes it is the other way around.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
6
gap> LowerBoundCoveringRadiusEmbedded2(10,32,false);
2
gap> LowerBoundCoveringRadiusEmbedded2(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7D27F6E27B9A0D35" name="X7D27F6E27B9A0D35"></a></p>
<h5>7.2-12 LowerBoundCoveringRadiusInduction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusInduction</code>( <var class="Arg">n, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">LowerBoundCoveringRadiusInduction</code> returns a lower bound for the size of a code with length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>If n = 2r+2 and r >= 1, the returned value is 4.</p>
<p>If n = 2r+3 and r >= 1, the returned value is 7.</p>
<p>If n = 2r+4 and r >= 4, the returned value is 8.</p>
<p>Otherwise, 0 is returned.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> LowerBoundCoveringRadiusInduction(15,6);
7
</pre></td></tr></table>
<p><a id="X80F8DFAD7D67CBEC" name="X80F8DFAD7D67CBEC"></a></p>
<h5>7.2-13 UpperBoundCoveringRadiusRedundancy</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusRedundancy</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusRedundancy</code> returns the redundancy of <var class="Arg">C</var> as an upper bound for the covering radius of <var class="Arg">C</var>. <var class="Arg">C</var> must be a linear code.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusRedundancy(C);
10
</pre></td></tr></table>
<p><a id="X832847A17FD0D142" name="X832847A17FD0D142"></a></p>
<h5>7.2-14 UpperBoundCoveringRadiusDelsarte</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusDelsarte</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusDelsarte</code> returns an upper bound for the covering radius of <var class="Arg">C</var>. This upper bound is equal to the external distance of <var class="Arg">C</var>, this is the minimum distance of the dual code, if <var class="Arg">C</var> is a linear code.</p>
<p>This is described in Theorem 11.3.3 of <a href="chapBib.html#biBHP03">[HP03]</a>.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusDelsarte(C);
13
</pre></td></tr></table>
<p><a id="X86F10D9E79AB8796" name="X86F10D9E79AB8796"></a></p>
<h5>7.2-15 UpperBoundCoveringRadiusStrength</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusStrength</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusStrength</code> returns an upper bound for the covering radius of <var class="Arg">C</var>.</p>
<p>First the code is punctured at the zero coordinates (i.e. the coordinates where all codewords have a zero). If the remaining code has <em>strength</em> 1 (i.e. each coordinate contains each element of the field an equal number of times), then it returns fracq-1qm + (n-m) (where q is the size of the field and m is the length of punctured code), otherwise it returns n. This bound works for all codes.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusStrength(C);
7
</pre></td></tr></table>
<p><a id="X8585C6A982489FC3" name="X8585C6A982489FC3"></a></p>
<h5>7.2-16 UpperBoundCoveringRadiusGriesmerLike</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusGriesmerLike</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function returns an upper bound for the covering radius of <var class="Arg">C</var>, which must be linear, in a Griesmer-like fashion. It returns</p>
<p class="pcenter">
n - \sum_{i=1}^k \left\lceil \frac{d}{q^i} \right\rceil
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusGriesmerLike(C);
9
</pre></td></tr></table>
<p><a id="X82A38F5F858CF3FC" name="X82A38F5F858CF3FC"></a></p>
<h5>7.2-17 UpperBoundCoveringRadiusCyclicCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusCyclicCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function returns an upper bound for the covering radius of <var class="Arg">C</var>, which must be a cyclic code. It returns</p>
<p class="pcenter">
n - k + 1 - \left\lceil \frac{w(g(x))}{2} \right\rceil,
</p>
<p>where g(x) is the generator polynomial of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> C:=CyclicCodes(15,GF(2))[3];
a cyclic [15,12,1..2]1..3 enumerated code over GF(2)
gap> CoveringRadius(C);
3
gap> UpperBoundCoveringRadiusCyclicCode(C);
3
</pre></td></tr></table>
<p><a id="X806EBEC77C16E657" name="X806EBEC77C16E657"></a></p>
<h4>7.3 <span class="Heading">
Special matrices in <strong class="pkg">GUAVA</strong>
</span></h4>
<p>This section explains functions that work with special matrices <strong class="pkg">GUAVA</strong> needs for several codes.</p>
<p>Firstly, we describe some matrix generating functions (see <code class="func">KrawtchoukMat</code> (<a href="chap7.html#X82899B64802A4BCE"><b>7.3-1</b></a>), <code class="func">GrayMat</code> (<a href="chap7.html#X87AFE2C078031CE4"><b>7.3-2</b></a>), <code class="func">SylvesterMat</code> (<a href="chap7.html#X7E1E7C5287919CDB"><b>7.3-3</b></a>), <code class="func">HadamardMat</code> (<a href="chap7.html#X8014A1F181ECD8AA"><b>7.3-4</b></a>) and <code class="func">MOLS</code> (<a href="chap7.html#X804AAFF2867080F7"><b>7.3-11</b></a>)).</p>
<p>Next we describe two functions regarding a standard form of matrices (see <code class="func">PutStandardForm</code> (<a href="chap7.html#X7B47D82485B66F1D"><b>7.3-6</b></a>) and <code class="func">IsInStandardForm</code> (<a href="chap7.html#X7D4EDA0A854EBFEF"><b>7.3-7</b></a>)).</p>
<p>Then we describe functions that return a matrix after a manipulation (see <code class="func">PermutedCols</code> (<a href="chap7.html#X7A97AD477E7638DE"><b>7.3-8</b></a>), <code class="func">VerticalConversionFieldMat</code> (<a href="chap7.html#X7B68119F85E9EC6D"><b>7.3-9</b></a>) and <code class="func">HorizontalConversionFieldMat</code> (<a href="chap7.html#X8033E9A67BA155C8"><b>7.3-10</b></a>)).</p>
<p>Finally, we describe functions that do some tests on matrices (see <code class="func">IsLatinSquare</code> (<a href="chap7.html#X7F34306B81DC2776"><b>7.3-12</b></a>) and <code class="func">AreMOLS</code> (<a href="chap7.html#X81B9B40B7B2D97D5"><b>7.3-13</b></a>)).</p>
<p><a id="X82899B64802A4BCE" name="X82899B64802A4BCE"></a></p>
<h5>7.3-1 KrawtchoukMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KrawtchoukMat</code>( <var class="Arg">n, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">KrawtchoukMat</code> returns the n+1 by n+1 matrix K=(k_ij) defined by k_ij=K_i(j) for i,j=0,...,n. K_i(j) is the Krawtchouk number (see <code class="func">Krawtchouk</code> (<a href="chap7.html#X7ACDC5377CD17451"><b>7.5-6</b></a>)). <var class="Arg">n</var> must be a positive integer and <var class="Arg">q</var> a prime power. The Krawtchouk matrix is used in the <em>MacWilliams identities</em>, defining the relation between the weight distribution of a code of length <var class="Arg">n</var> over a field of size <var class="Arg">q</var>, and its dual code. Each call to <code class="code">KrawtchoukMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> PrintArray( KrawtchoukMat( 3, 2 ) );
[ [ 1, 1, 1, 1 ],
[ 3, 1, -1, -3 ],
[ 3, -1, -1, 3 ],
[ 1, -1, 1, -1 ] ]
gap> C := HammingCode( 3 );; a := WeightDistribution( C );
[ 1, 0, 0, 7, 7, 0, 0, 1 ]
gap> n := WordLength( C );; q := Size( LeftActingDomain( C ) );;
gap> k := Dimension( C );;
gap> q^( -k ) * KrawtchoukMat( n, q ) * a;
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
gap> WeightDistribution( DualCode( C ) );
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
</pre></td></tr></table>
<p><a id="X87AFE2C078031CE4" name="X87AFE2C078031CE4"></a></p>
<h5>7.3-2 GrayMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrayMat</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GrayMat</code> returns a list of all different vectors (see GAP's <code class="code">Vectors</code> command) of length <var class="Arg">n</var> over the field <var class="Arg">F</var>, using Gray ordering. <var class="Arg">n</var> must be a positive integer. This order has the property that subsequent vectors differ in exactly one coordinate. The first vector is always the null vector. Each call to <code class="code">GrayMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> GrayMat(3);
[ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ],
[ 0*Z(2), Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
[ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
[ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]
gap> G := GrayMat( 4, GF(4) );; Length(G);
256 # the length of a GrayMat is always q^n
gap> G[101] - G[100];
[ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ]
</pre></td></tr></table>
<p><a id="X7E1E7C5287919CDB" name="X7E1E7C5287919CDB"></a></p>
<h5>7.3-3 SylvesterMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SylvesterMat</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SylvesterMat</code> returns the nx n Sylvester matrix of order <var class="Arg">n</var>. This is a special case of the Hadamard matrices (see <code class="func">HadamardMat</code> (<a href="chap7.html#X8014A1F181ECD8AA"><b>7.3-4</b></a>)). For this construction, <var class="Arg">n</var> must be a power of 2. Each call to <code class="code">SylvesterMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> PrintArray(SylvesterMat(2));
[ [ 1, 1 ],
[ 1, -1 ] ]
gap> PrintArray( SylvesterMat(4) );
[ [ 1, 1, 1, 1 ],
[ 1, -1, 1, -1 ],
[ 1, 1, -1, -1 ],
[ 1, -1, -1, 1 ] ]
</pre></td></tr></table>
<p><a id="X8014A1F181ECD8AA" name="X8014A1F181ECD8AA"></a></p>
<h5>7.3-4 HadamardMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HadamardMat</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">HadamardMat</code> returns a Hadamard matrix of order <var class="Arg">n</var>. This is an nx n matrix with the property that the matrix multiplied by its transpose returns <var class="Arg">n</var> times the identity matrix. This is only possible for n=1, n=2 or in cases where <var class="Arg">n</var> is a multiple of 4. If the matrix does not exist or is not known (as of 1998), <code class="code">HadamardMat</code> returns an error. A large number of construction methods is known to create these matrices for different orders. <code class="code">HadamardMat</code> makes use of two construction methods (the Paley Type I and II constructions, and the Sylvester construction -- see <code class="func">SylvesterMat</code> (<a href="chap7.html#X7E1E7C5287919CDB"><b>7.3-3</b></a>)). These methods cover most of the possible Hadamard matrices, although some special algorithms have not been implemented yet. The following orders less than 100 do not yet have an implementation for a Hadamard matrix in <strong class="pkg">GUAVA</strong>: 52, 92.</p>
<table class="example">
<tr><td><pre>
gap> C := HadamardMat(8);; PrintArray(C);
[ [ 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, -1, 1, -1, 1, -1, 1, -1 ],
[ 1, 1, -1, -1, 1, 1, -1, -1 ],
[ 1, -1, -1, 1, 1, -1, -1, 1 ],
[ 1, 1, 1, 1, -1, -1, -1, -1 ],
[ 1, -1, 1, -1, -1, 1, -1, 1 ],
[ 1, 1, -1, -1, -1, -1, 1, 1 ],
[ 1, -1, -1, 1, -1, 1, 1, -1 ] ]
gap> C * TransposedMat(C) = 8 * IdentityMat( 8, 8 );
true
</pre></td></tr></table>
<p><a id="X797F43607AD8660D" name="X797F43607AD8660D"></a></p>
<h5>7.3-5 VandermondeMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VandermondeMat</code>( <var class="Arg">X, a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">VandermondeMat</code> returns the (a+1)x n matrix of powers x_i^j where <var class="Arg">X</var> is a list of elements of a field, X= x_1,...,x_n, and <var class="Arg">a</var> is a non-negative integer.</p>
<table class="example">
<tr><td><pre>
gap> M:=VandermondeMat([Z(5),Z(5)^2,Z(5)^0,Z(5)^3],2);
[ [ Z(5)^0, Z(5), Z(5)^2 ], [ Z(5)^0, Z(5)^2, Z(5)^0 ],
[ Z(5)^0, Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5)^3, Z(5)^2 ] ]
gap> Display(M);
1 2 4
1 4 1
1 1 1
1 3 4
</pre></td></tr></table>
<p><a id="X7B47D82485B66F1D" name="X7B47D82485B66F1D"></a></p>
<h5>7.3-6 PutStandardForm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PutStandardForm</code>( <var class="Arg">M[, idleft]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>We say that a kx n matrix is in <em>standard form</em> if it is equal to the block matrix (I | A), for some kx (n-k) matrix A and where I is the kx k identity matrix. It follows from a basis result in linear algebra that, after a possible permutation of the columns, using elementary row operations, every matrix can be reduced to standard form. <code class="code">PutStandardForm</code> puts a matrix <var class="Arg">M</var> in standard form, and returns the permutation needed to do so. <var class="Arg">idleft</var> is a boolean that sets the position of the identity matrix in <var class="Arg">M</var>. (The default for <var class="Arg">idleft</var> is `true'.) If <var class="Arg">idleft</var> is set to `true', the identity matrix is put on the left side of <var class="Arg">M</var>. Otherwise, it is put at the right side. (This option is useful when putting a check matrix of a code into standard form.) The function <code class="code">BaseMat</code> also returns a similar standard form, but does not apply column permutations. The rows of the matrix still span the same vector space after <code class="code">BaseMat</code>, but after calling <code class="code">PutStandardForm</code>, this is not necessarily true.</p>
<table class="example">
<tr><td><pre>
gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
[ [ Z(2), 0*Z(2), 0*Z(2), Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2), Z(2) ] ]
gap> PutStandardForm(M); # identity at the left side
(2,3)
gap> PrintArray(M);
[ [ Z(2), 0*Z(2), 0*Z(2), Z(2) ],
[ 0*Z(2), Z(2), 0*Z(2), Z(2) ] ]
gap> PutStandardForm(M, false); # identity at the right side
(1,4,3)
gap> PrintArray(M);
[ [ 0*Z(2), Z(2), Z(2), 0*Z(2) ],
[ 0*Z(2), Z(2), 0*Z(2), Z(2) ] ]
gap> C := BestKnownLinearCode( 23, 12, GF(2) );
a linear [23,12,7]3 punctured code
gap> G:=MutableCopyMat(GeneratorMat(C));;
gap> PutStandardForm(G);
()
gap> Display(G);
1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1
. 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . .
. . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1
. . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 .
. . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . 1
. . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 1
. . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1
. . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .
. . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .
. . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 .
. . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 1
. . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
</pre></td></tr></table>
<p><a id="X7D4EDA0A854EBFEF" name="X7D4EDA0A854EBFEF"></a></p>
<h5>7.3-7 IsInStandardForm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsInStandardForm</code>( <var class="Arg">M[, idleft]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsInStandardForm</code> determines if <var class="Arg">M</var> is in standard form. <var class="Arg">idleft</var> is a boolean that indicates the position of the identity matrix in <var class="Arg">M</var>, as in <code class="code">PutStandardForm</code> (see <code class="func">PutStandardForm</code> (<a href="chap7.html#X7B47D82485B66F1D"><b>7.3-6</b></a>)). <code class="code">IsInStandardForm</code> checks if the identity matrix is at the left side of <var class="Arg">M</var>, otherwise if it is at the right side. The elements of <var class="Arg">M</var> may be elements of any field.</p>
<table class="example">
<tr><td><pre>
gap> IsInStandardForm(IdentityMat(7, GF(2)));
true
gap> IsInStandardForm([[1, 1, 0], [1, 0, 1]], false);
true
gap> IsInStandardForm([[1, 3, 2, 7]]);
true
gap> IsInStandardForm(HadamardMat(4));
false
</pre></td></tr></table>
<p><a id="X7A97AD477E7638DE" name="X7A97AD477E7638DE"></a></p>
<h5>7.3-8 PermutedCols</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PermutedCols</code>( <var class="Arg">M, P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PermutedCols</code> returns a matrix <var class="Arg">M</var> with a permutation <var class="Arg">P</var> applied to its columns.</p>
<table class="example">
<tr><td><pre>
gap> M := [[1,2,3,4],[1,2,3,4]];; PrintArray(M);
[ [ 1, 2, 3, 4 ],
[ 1, 2, 3, 4 ] ]
gap> PrintArray(PermutedCols(M, (1,2,3)));
[ [ 3, 1, 2, 4 ],
[ 3, 1, 2, 4 ] ]
</pre></td></tr></table>
<p><a id="X7B68119F85E9EC6D" name="X7B68119F85E9EC6D"></a></p>
<h5>7.3-9 VerticalConversionFieldMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VerticalConversionFieldMat</code>( <var class="Arg">M, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">VerticalConversionFieldMat</code> returns the matrix <var class="Arg">M</var> with its elements converted from a field F=GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed vertically in the matrix, using the GF(p)-vector space isomorphism</p>
<p class="pcenter">
[...] : GF(q)\rightarrow GF(p)^m,
</p>
<p>with q=p^m.</p>
<p>If <var class="Arg">M</var> is a k by n matrix, the result is a k* m x n matrix, since each element of GF(q^m) can be represented in GF(q) using m elements.</p>
<table class="example">
<tr><td><pre>
gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [ Z(3^2), Z(3^2)^5 ],
[ Z(3^2)^5, Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> VCFM := VerticalConversionFieldMat( M, GF(9) );; PrintArray(VCFM);
[ [ 0*Z(3), 0*Z(3) ],
[ Z(3)^0, Z(3) ],
[ 0*Z(3), 0*Z(3) ],
[ Z(3), Z(3)^0 ] ]
gap> DefaultField( Flat(VCFM) );
GF(3)
</pre></td></tr></table>
<p>A similar function is <code class="code">HorizontalConversionFieldMat</code> (see <code class="func">HorizontalConversionFieldMat</code> (<a href="chap7.html#X8033E9A67BA155C8"><b>7.3-10</b></a>)).</p>
<p><a id="X8033E9A67BA155C8" name="X8033E9A67BA155C8"></a></p>
<h5>7.3-10 HorizontalConversionFieldMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HorizontalConversionFieldMat</code>( <var class="Arg">M, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">HorizontalConversionFieldMat</code> returns the matrix <var class="Arg">M</var> with its elements converted from a field F=GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed horizontally in the matrix.</p>
<p>If <var class="Arg">M</var> is a k x n matrix, the result is a kx mx n* m matrix. The new word length of the resulting code is equal to n* m, because each element of GF(q^m) can be represented in GF(q) using m elements. The new dimension is equal to kx m because the new matrix should be a basis for the same number of vectors as the old one.</p>
<p><code class="code">ConversionFieldCode</code> uses horizontal conversion to convert a code (see <code class="func">ConversionFieldCode</code> (<a href="chap6.html#X81FE1F387DFCCB22"><b>6.1-15</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [ Z(3^2), Z(3^2)^5 ],
[ Z(3^2)^5, Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> HCFM := HorizontalConversionFieldMat(M, GF(9));; PrintArray(HCFM);
[ [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3) ],
[ Z(3)^0, Z(3)^0, Z(3), Z(3) ],
[ 0*Z(3), Z(3), 0*Z(3), Z(3)^0 ],
[ Z(3), Z(3), Z(3)^0, Z(3)^0 ] ]
gap> DefaultField( Flat(HCFM) );
GF(3)
</pre></td></tr></table>
<p>A similar function is <code class="code">VerticalConversionFieldMat</code> (see <code class="func">VerticalConversionFieldMat</code> (<a href="chap7.html#X7B68119F85E9EC6D"><b>7.3-9</b></a>)).</p>
<p><a id="X804AAFF2867080F7" name="X804AAFF2867080F7"></a></p>
<h5>7.3-11 MOLS</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MOLS</code>( <var class="Arg">q[, n]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MOLS</code> returns a list of <var class="Arg">n</var> <em>Mutually Orthogonal Latin Squares</em> (MOLS). A <em>Latin square</em> of order <var class="Arg">q</var> is a qx q matrix whose entries are from a set F_q of <var class="Arg">q</var> distinct symbols (<strong class="pkg">GUAVA</strong> uses the integers from 0 to <var class="Arg">q</var>) such that each row and each column of the matrix contains each symbol exactly once.</p>
<p>A set of Latin squares is a set of MOLS if and only if for each pair of Latin squares in this set, every ordered pair of elements that are in the same position in these matrices occurs exactly once.</p>
<p><var class="Arg">n</var> must be less than <var class="Arg">q</var>. If <var class="Arg">n</var> is omitted, two MOLS are returned. If <var class="Arg">q</var> is not a prime power, at most 2 MOLS can be created. For all values of <var class="Arg">q</var> with q > 2 and q <> 6, a list of MOLS can be constructed. However, <strong class="pkg">GUAVA</strong> does not yet construct MOLS for q= 2 mod 4. If it is not possible to construct <var class="Arg">n</var> MOLS, the function returns `false'.</p>
<p>MOLS are used to create <var class="Arg">q</var>-ary codes (see <code class="func">MOLSCode</code> (<a href="chap5.html#X81B7EE4279398F67"><b>5.1-4</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := MOLS( 4, 3 );;PrintArray( M[1] );
[ [ 0, 1, 2, 3 ],
[ 1, 0, 3, 2 ],
[ 2, 3, 0, 1 ],
[ 3, 2, 1, 0 ] ]
gap> PrintArray( M[2] );
[ [ 0, 2, 3, 1 ],
[ 1, 3, 2, 0 ],
[ 2, 0, 1, 3 ],
[ 3, 1, 0, 2 ] ]
gap> PrintArray( M[3] );
[ [ 0, 3, 1, 2 ],
[ 1, 2, 0, 3 ],
[ 2, 1, 3, 0 ],
[ 3, 0, 2, 1 ] ]
gap> MOLS( 12, 3 );
false
</pre></td></tr></table>
<p><a id="X7F34306B81DC2776" name="X7F34306B81DC2776"></a></p>
<h5>7.3-12 IsLatinSquare</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsLatinSquare</code>( <var class="Arg">M</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsLatinSquare</code> determines if a matrix <var class="Arg">M</var> is a Latin square. For a Latin square of size nx n, each row and each column contains all the integers 1,dots,n exactly once.</p>
<table class="example">
<tr><td><pre>
gap> IsLatinSquare([[1,2],[2,1]]);
true
gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]);
false
</pre></td></tr></table>
<p><a id="X81B9B40B7B2D97D5" name="X81B9B40B7B2D97D5"></a></p>
<h5>7.3-13 AreMOLS</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AreMOLS</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AreMOLS</code> determines if <var class="Arg">L</var> is a list of mutually orthogonal Latin squares (MOLS). For each pair of Latin squares in this list, the function checks if each ordered pair of elements that are in the same position in these matrices occurs exactly once. The function <code class="code">MOLS</code> creates MOLS (see <code class="func">MOLS</code> (<a href="chap7.html#X804AAFF2867080F7"><b>7.3-11</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := MOLS(4,2);
[ [ [ 0, 1, 2, 3 ], [ 1, 0, 3, 2 ], [ 2, 3, 0, 1 ], [ 3, 2, 1, 0 ] ],
[ [ 0, 2, 3, 1 ], [ 1, 3, 2, 0 ], [ 2, 0, 1, 3 ], [ 3, 1, 0, 2 ] ] ]
gap> AreMOLS(M);
true
</pre></td></tr></table>
<p><a id="X7AB5E5CE7FDF7132" name="X7AB5E5CE7FDF7132"></a></p>
<h4>7.4 <span class="Heading">
Some functions related to the norm of a code
</span></h4>
<p>In this section, some functions that can be used to compute the norm of a code and to decide upon its normality are discussed. Typically, these are applied to binary linear codes. The definitions of this section were introduced in Graham and Sloane <a href="chapBib.html#biBGS85">[GS85]</a>.</p>
<p><a id="X8032E53078264ABB" name="X8032E53078264ABB"></a></p>
<h5>7.4-1 CoordinateNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoordinateNorm</code>( <var class="Arg">C, coord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CoordinateNorm</code> returns the norm of <var class="Arg">C</var> with respect to coordinate <var class="Arg">coord</var>. If C_a = c in C | c_coord = a, then the norm of <var class="Arg">C</var> with respect to <var class="Arg">coord</var> is defined as</p>
<p class="pcenter">
\max_{v \in GF(q)^n} \sum_{a=1}^q d(x,C_a),
</p>
<p>with the convention that d(x,C_a) = n if C_a is empty.</p>
<table class="example">
<tr><td><pre>
gap> CoordinateNorm( HammingCode( 3, GF(2) ), 3 );
3
</pre></td></tr></table>
<p><a id="X7ED2EF368203AF47" name="X7ED2EF368203AF47"></a></p>
<h5>7.4-2 CodeNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeNorm</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeNorm</code> returns the norm of <var class="Arg">C</var>. The <em>norm</em> of a code is defined as the minimum of the norms for the respective coordinates of the code. In effect, for each coordinate <code class="code">CoordinateNorm</code> is called, and the minimum of the calculated numbers is returned.</p>
<table class="example">
<tr><td><pre>
gap> CodeNorm( HammingCode( 3, GF(2) ) );
3
</pre></td></tr></table>
<p><a id="X7D24F8BF7F9A7BF1" name="X7D24F8BF7F9A7BF1"></a></p>
<h5>7.4-3 IsCoordinateAcceptable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsCoordinateAcceptable</code>( <var class="Arg">C, coord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsCoordinateAcceptable</code> returns `true' if coordinate <var class="Arg">coord</var> of <var class="Arg">C</var> is acceptable. A coordinate is called <em>acceptable</em> if the norm of the code with respect to that coordinate is not more than two times the covering radius of the code plus one.</p>
<table class="example">
<tr><td><pre>
gap> IsCoordinateAcceptable( HammingCode( 3, GF(2) ), 3 );
true
</pre></td></tr></table>
<p><a id="X87039FD179AD3009" name="X87039FD179AD3009"></a></p>
<h5>7.4-4 GeneralizedCodeNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralizedCodeNorm</code>( <var class="Arg">C, subcode1, subscode2, ..., subcodek</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralizedCodeNorm</code> returns the <var class="Arg">k</var>-norm of <var class="Arg">C</var> with respect to <var class="Arg">k</var> subcodes.</p>
<table class="example">
<tr><td><pre>
gap> c := RepetitionCode( 7, GF(2) );;
gap> ham := HammingCode( 3, GF(2) );;
gap> d := EvenWeightSubcode( ham );;
gap> e := ConstantWeightSubcode( ham, 3 );;
gap> GeneralizedCodeNorm( ham, c, d, e );
4
</pre></td></tr></table>
<p><a id="X80283A2F7C8101BD" name="X80283A2F7C8101BD"></a></p>
<h5>7.4-5 IsNormalCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNormalCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsNormalCode</code> returns `true' if <var class="Arg">C</var> is normal. A code is called <em>normal</em> if the norm of the code is not more than two times the covering radius of the code plus one. Almost all codes are normal, however some (non-linear) abnormal codes have been found.</p>
<p>Often, it is difficult to find out whether a code is normal, because it involves computing the covering radius. However, <code class="code">IsNormalCode</code> uses much information from the literature (in particular, <a href="chapBib.html#biBGS85">[GS85]</a>) about normality for certain code parameters.</p>
<table class="example">
<tr><td><pre>
gap> IsNormalCode( HammingCode( 3, GF(2) ) );
true
</pre></td></tr></table>
<p><a id="X8308D685809A4E2F" name="X8308D685809A4E2F"></a></p>
<h4>7.5 <span class="Heading">
Miscellaneous functions
</span></h4>
<p>In this section we describe several vector space functions <strong class="pkg">GUAVA</strong> uses for constructing codes or performing calculations with codes.</p>
<p>In this section, some new miscellaneous functions are described, including weight enumerators, the MacWilliams-transform and affinity and almost affinity of codes.</p>
<p><a id="X871286437DE7A6A4" name="X871286437DE7A6A4"></a></p>
<h5>7.5-1 CodeWeightEnumerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeWeightEnumerator</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeWeightEnumerator</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} A_i x^i,
</p>
<p>where A_i is the number of codewords in <var class="Arg">C</var> with weight i.</p>
<table class="example">
<tr><td><pre>
gap> CodeWeightEnumerator( ElementsCode( [ [ 0,0,0 ], [ 0,0,1 ],
> [ 0,1,1 ], [ 1,1,1 ] ], GF(2) ) );
x^3 + x^2 + x + 1
gap> CodeWeightEnumerator( HammingCode( 3, GF(2) ) );
x^7 + 7*x^4 + 7*x^3 + 1
</pre></td></tr></table>
<p><a id="X84DA928083B103A0" name="X84DA928083B103A0"></a></p>
<h5>7.5-2 CodeDistanceEnumerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeDistanceEnumerator</code>( <var class="Arg">C, w</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeDistanceEnumerator</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} B_i x^i,
</p>
<p>where B_i is the number of codewords with distance i to <var class="Arg">w</var>.</p>
<p>If <var class="Arg">w</var> is a codeword, then <code class="code">CodeDistanceEnumerator</code> returns the same polynomial as <code class="code">CodeWeightEnumerator</code>.</p>
<table class="example">
<tr><td><pre>
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[0,0,0,0,0,0,1] );
x^6 + 3*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + x
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[1,1,1,1,1,1,1] );
x^7 + 7*x^4 + 7*x^3 + 1 # `[1,1,1,1,1,1,1]' $\in$ `HammingCode( 3, GF(2 ) )'
</pre></td></tr></table>
<p><a id="X84B2BE66780EFBF9" name="X84B2BE66780EFBF9"></a></p>
<h5>7.5-3 CodeMacWilliamsTransform</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeMacWilliamsTransform</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeMacWilliamsTransform</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} C_i x^i,
</p>
<p>where C_i is the number of codewords with weight i in the <em>dual</em> code of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> CodeMacWilliamsTransform( HammingCode( 3, GF(2) ) );
7*x^4 + 1
</pre></td></tr></table>
<p><a id="X7903286078F8051B" name="X7903286078F8051B"></a></p>
<h5>7.5-4 CodeDensity</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeDensity</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeDensity</code> returns the <em>density</em> of <var class="Arg">C</var>. The density of a code is defined as</p>
<p class="pcenter">
\frac{M \cdot V_q(n,t)}{q^n},
</p>
<p>where M is the size of the code, V_q(n,t) is the size of a sphere of radius t in GF(q^n) (which may be computed using <code class="code">SphereContent</code>), t is the covering radius of the code and n is the length of the code.</p>
<table class="example">
<tr><td><pre>
gap> CodeDensity( HammingCode( 3, GF(2) ) );
1
gap> CodeDensity( ReedMullerCode( 1, 4 ) );
14893/2048
</pre></td></tr></table>
<p><a id="X85303BAE7BD46D81" name="X85303BAE7BD46D81"></a></p>
<h5>7.5-5 SphereContent</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SphereContent</code>( <var class="Arg">n, t, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SphereContent</code> returns the content of a ball of radius <var class="Arg">t</var> around an arbitrary element of the vectorspace F^n. This is the cardinality of the set of all elements of F^n that are at distance (see <code class="func">DistanceCodeword</code> (<a href="chap3.html#X7CDA1B547D55E6FB"><b>3.6-2</b></a>) less than or equal to <var class="Arg">t</var> from an element of F^n.</p>
<p>In the context of codes, the function is used to determine if a code is perfect. A code is <em>perfect</em> if spheres of radius t around all codewords partition the whole ambient vector space, where <em>t</em> is the number of errors the code can correct.</p>
<table class="example">
<tr><td><pre>
gap> SphereContent( 15, 0, GF(2) );
1 # Only one word with distance 0, which is the word itself
gap> SphereContent( 11, 3, GF(4) );
4984
gap> C := HammingCode(5);
a linear [31,26,3]1 Hamming (5,2) code over GF(2)
#the minimum distance is 3, so the code can correct one error
gap> ( SphereContent( 31, 1, GF(2) ) * Size(C) ) = 2 ^ 31;
true
</pre></td></tr></table>
<p><a id="X7ACDC5377CD17451" name="X7ACDC5377CD17451"></a></p>
<h5>7.5-6 Krawtchouk</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Krawtchouk</code>( <var class="Arg">k, i, n, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Krawtchouk</code> returns the Krawtchouk number K_k(i). <var class="Arg">q</var> must be a prime power, <var class="Arg">n</var> must be a positive integer, <var class="Arg">k</var> must be a non-negative integer less then or equal to <var class="Arg">n</var> and <var class="Arg">i</var> can be any integer. (See <code class="func">KrawtchoukMat</code> (<a href="chap7.html#X82899B64802A4BCE"><b>7.3-1</b></a>)). This number is the value at x=i of the polynomial</p>
<p class="pcenter">
K_k^{n,q}(x)
=\sum_{j=0}^n (-1)^j(q-1)^{k-j}b(x,j)b(n-x,k-j),
</p>
<p>where $b(v,u)=u!/(v!(v-u)!)$ is the binomial coefficient if $u,v$ are integers. For more properties of these polynomials, see <a href="chapBib.html#biBMS83">[MS83]</a>.</p>
<table class="example">
<tr><td><pre>
gap> Krawtchouk( 2, 0, 3, 2);
3
</pre></td></tr></table>
<p><a id="X827E39957A87EB51" name="X827E39957A87EB51"></a></p>
<h5>7.5-7 PrimitiveUnityRoot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PrimitiveUnityRoot</code>( <var class="Arg">F, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitiveUnityRoot</code> returns a primitive <var class="Arg">n</var>-th root of unity in an extension field of <var class="Arg">F</var>. This is a finite field element a with the property a^n=1 in <var class="Arg">F</var>, and <var class="Arg">n</var> is the smallest integer such that this equality holds.</p>
<table class="example">
<tr><td><pre>
gap> PrimitiveUnityRoot( GF(2), 15 );
Z(2^4)
gap> last^15;
Z(2)^0
gap> PrimitiveUnityRoot( GF(8), 21 );
Z(2^6)^3
</pre></td></tr></table>
<p><a id="X78AEA40F7AD9D541" name="X78AEA40F7AD9D541"></a></p>
<h5>7.5-8 PrimitivePolynomialsNr</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PrimitivePolynomialsNr</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitivePolynomialsNr</code> returns the number of irreducible polynomials over F=GF(q) of degree <var class="Arg">n</var> with (maximum) period q^n-1. (According to a theorem of S. Golomb, this is phi(p^n-1)/n.)</p>
<p>See also the GAP function <code class="code">RandomPrimitivePolynomial</code>, <code class="func">RandomPrimitivePolynomial</code> (<a href="chap2.html#X7ECC593583E68A6C"><b>2.2-2</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> PrimitivePolynomialsNr(3,4);
12
</pre></td></tr></table>
<p><a id="X7A2B54EF868AA752" name="X7A2B54EF868AA752"></a></p>
<h5>7.5-9 IrreduciblePolynomialsNr</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IrreduciblePolynomialsNr</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitivePolynomialsNr</code> returns the number of irreducible polynomials over F=GF(q) of degree <var class="Arg">n</var>.</p>
<table class="example">
<tr><td><pre>
gap> IrreduciblePolynomialsNr(3,4);
20
</pre></td></tr></table>
<p><a id="X7B50D3417F6FD7C6" name="X7B50D3417F6FD7C6"></a></p>
<h5>7.5-10 MatrixRepresentationOfElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MatrixRepresentationOfElement</code>( <var class="Arg">a, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Here <var class="Arg">F</var> is either a finite extension of the ``base field'' GF(p) or of the rationals Q}, and ain F. The command <code class="code">MatrixRepresentationOfElement</code> returns a matrix representation of <var class="Arg">a</var> over the base field.</p>
<p>If the element <var class="Arg">a</var> is defined over the base field then it returns the corresponding 1x 1 matrix.</p>
<table class="example">
<tr><td><pre>
gap> a:=Random(GF(4));
0*Z(2)
gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
.
gap> a:=Random(GF(4));
Z(2^2)
gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
. 1
1 1
gap>
</pre></td></tr></table>
<p><a id="X7805D2BB7CE4D455" name="X7805D2BB7CE4D455"></a></p>
<h5>7.5-11 ReciprocalPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReciprocalPolynomial</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">ReciprocalPolynomial</code> returns the <em>reciprocal</em> of polynomial <var class="Arg">P</var>. This is a polynomial with coefficients of <var class="Arg">P</var> in the reverse order. So if P=a_0 + a_1 X + ... + a_n X^n, the reciprocal polynomial is P'=a_n + a_n-1 X + ... + a_0 X^n.</p>
<p>This command can also be called using the syntax <code class="code">ReciprocalPolynomial( P , n )</code>. In this form, the number of coefficients of <var class="Arg">P</var> is assumed to be less than or equal to n+1 (with zero coefficients added in the highest degrees, if necessary). Therefore, the reciprocal polynomial also has degree n+1.</p>
<table class="example">
<tr><td><pre>
gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> RecP := ReciprocalPolynomial( P );
-Z(3)^0+x_1+x_1^3
gap> ReciprocalPolynomial( RecP ) = P;
true
gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> ReciprocalPolynomial( P, 6 );
-x_1^3+x_1^4+x_1^6
</pre></td></tr></table>
<p><a id="X7AEA9F807E6FFEFF" name="X7AEA9F807E6FFEFF"></a></p>
<h5>7.5-12 CyclotomicCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CyclotomicCosets</code>( <var class="Arg">q, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CyclotomicCosets</code> returns the cyclotomic cosets of q mod n. <var class="Arg">q</var> and <var class="Arg">n</var> must be relatively prime. Each of the elements of the returned list is a list of integers that belong to one cyclotomic coset. A q-cyclotomic coset of s mod n is a set of the form s,sq,sq^2,...,sq^r-1, where r is the smallest positive integer such that sq^r-s is 0 mod n. In other words, each coset contains all multiplications of the coset representative by q mod n. The coset representative is the smallest integer that isn't in the previous cosets.</p>
<table class="example">
<tr><td><pre>
gap> CyclotomicCosets( 2, 15 );
[ [ 0 ], [ 1, 2, 4, 8 ], [ 3, 6, 12, 9 ], [ 5, 10 ],
[ 7, 14, 13, 11 ] ]
gap> CyclotomicCosets( 7, 6 );
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
</pre></td></tr></table>
<p><a id="X7A4EA98D794CF410" name="X7A4EA98D794CF410"></a></p>
<h5>7.5-13 WeightHistogram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeightHistogram</code>( <var class="Arg">C[, h]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">WeightHistogram</code> plots a histogram of weights in code <var class="Arg">C</var>. The maximum length of a column is <var class="Arg">h</var>. Default value for <var class="Arg">h</var> is 1/3 of the size of the screen. The number that appears at the top of the histogram is the maximum value of the list of weights.</p>
<table class="example">
<tr><td><pre>
gap> H := HammingCode(2, GF(5));
a linear [6,4,3]1 Hamming (2,5) code over GF(5)
gap> WeightDistribution(H);
[ 1, 0, 0, 80, 120, 264, 160 ]
gap> WeightHistogram(H);
264----------------
*
*
*
*
* *
* * *
* * * *
* * * *
+--------+--+--+--+--
0 1 2 3 4 5 6
</pre></td></tr></table>
<p><a id="X805DF25C84585FD6" name="X805DF25C84585FD6"></a></p>
<h5>7.5-14 MultiplicityInList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MultiplicityInList</code>( <var class="Arg">L, a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is a very simple list command which returns how many times a occurs in L. It returns 0 if a is not in L. (The GAP command <code class="code">Collected</code> does not quite handle this "extreme" case.)</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
gap> MultiplicityInList(L,1);
3
gap> MultiplicityInList(L,6);
0
</pre></td></tr></table>
<p><a id="X8072B0DA78FBE562" name="X8072B0DA78FBE562"></a></p>
<h5>7.5-15 MostCommonInList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MostCommonInList</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: a list L</p>
<p>Output: an a in L which occurs at least as much as any other in L</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
gap> MostCommonInList(L);
1
</pre></td></tr></table>
<p><a id="X7C5407EF87849857" name="X7C5407EF87849857"></a></p>
<h5>7.5-16 RotateList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RotateList</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: a list L</p>
<p>Output: a list L' which is the cyclic rotation of L (to the right)</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4];;
gap> RotateList(L);
[2,3,4,1]
</pre></td></tr></table>
<p><a id="X85E526367878F72A" name="X85E526367878F72A"></a></p>
<h5>7.5-17 CirculantMatrix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CirculantMatrix</code>( <var class="Arg">k, L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: integer k, a list L of length n</p>
<p>Output: kxn matrix whose rows are cyclic rotations of the list L</p>
<table class="example">
<tr><td><pre>
gap> k:=3; L:=[1,2,3,4];;
gap> M:=CirculantMatrix(k,L);;
gap> Display(M);
</pre></td></tr></table>
<p><a id="X7969103F7A8598F9" name="X7969103F7A8598F9"></a></p>
<h4>7.6 <span class="Heading">
Miscellaneous polynomial functions
</span></h4>
<p>In this section we describe several multivariate polynomial GAP functions <strong class="pkg">GUAVA</strong> uses for constructing codes or performing calculations with codes.</p>
<p><a id="X84D51EBB784E7C5D" name="X84D51EBB784E7C5D"></a></p>
<h5>7.6-1 MatrixTransformationOnMultivariatePolynomial </h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MatrixTransformationOnMultivariatePolynomial </code>( <var class="Arg">AfR</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is an nx n matrix with entries in a field F, <var class="Arg">R</var> is a polynomial ring of n variables, say F[x_1,...,x_n], and <var class="Arg">f</var> is a polynomial in <var class="Arg">R</var>. Returns the composition fcirc A.</p>
<p><a id="X80433A4B792880EF" name="X80433A4B792880EF"></a></p>
<h5>7.6-2 DegreeMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreeMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command takes two arguments, <var class="Arg">f</var>, a multivariate polynomial, and <var class="Arg">R</var> a polynomial ring over a field F containing <var class="Arg">f</var>, say R=F[x_1,x_2,...,x_n]. The output is simply the maximum degrees of all the monomials occurring in <var class="Arg">f</var>.</p>
<p>This command can be used to compute the degree of an affine plane curve.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> DegreeMultivariatePolynomial(poly,R2);
3
</pre></td></tr></table>
<p><a id="X83F44E397C56F2E0" name="X83F44E397C56F2E0"></a></p>
<h5>7.6-3 DegreesMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreesMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of information about the multivariate polynomial <var class="Arg">f</var>. Nice for other programs but mostly unreadable by GAP users.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> DegreesMultivariatePolynomial(poly,R2);
[ [ [ x_1, x_1, 1 ], [ x_1, x_2, 0 ] ], [ [ x_2^2, x_1, 0 ], [ x_2^2, x_2, 2 ] ],
[ [ x_1^3, x_1, 3 ], [ x_1^3, x_2, 0 ] ] ]
gap>
</pre></td></tr></table>
<p><a id="X7E9021697A61A60F" name="X7E9021697A61A60F"></a></p>
<h5>7.6-4 CoefficientMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoefficientMultivariatePolynomial</code>( <var class="Arg">f, var, power, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The command <code class="code">CoefficientMultivariatePolynomial</code> takes four arguments: a multivariant polynomial <var class="Arg">f</var>, a variable name <var class="Arg">var</var>, an integer <var class="Arg">power</var>, and a polynomial ring <var class="Arg">R</var> containing <var class="Arg">f</var>. For example, if <var class="Arg">f</var> is a multivariate polynomial in R = F[x_1,x_2,...,x_n] then <var class="Arg">var</var> must be one of the x_i. The output is the coefficient of x_i^power in <var class="Arg">f</var>.</p>
<p>(Not sure if F needs to be a field in fact ...)</p>
<p>Related to the GAP command <code class="code">PolynomialCoefficientsPolynomial</code>.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> PolynomialCoefficientsOfPolynomial(poly,x);
[ x_2^2, Z(11)^0, 0*Z(11), -Z(11)^0 ]
gap> PolynomialCoefficientsOfPolynomial(poly,y);
[ -x_1^3+x_1, 0*Z(11), Z(11)^0 ]
gap> CoefficientMultivariatePolynomial(poly,y,0,R2);
-x_1^3+x_1
gap> CoefficientMultivariatePolynomial(poly,y,1,R2);
0*Z(11)
gap> CoefficientMultivariatePolynomial(poly,y,2,R2);
Z(11)^0
gap> CoefficientMultivariatePolynomial(poly,x,0,R2);
x_2^2
gap> CoefficientMultivariatePolynomial(poly,x,1,R2);
Z(11)^0
gap> CoefficientMultivariatePolynomial(poly,x,2,R2);
0*Z(11)
gap> CoefficientMultivariatePolynomial(poly,x,3,R2);
-Z(11)^0
</pre></td></tr></table>
<p><a id="X79E76B6F7D177E27" name="X79E76B6F7D177E27"></a></p>
<h5>7.6-5 SolveLinearSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SolveLinearSystem</code>( <var class="Arg">L, vars</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: <var class="Arg">L</var> is a list of linear forms in the variables <var class="Arg">vars</var>.</p>
<p>Output: the solution of the system, if its unique.</p>
<p>The procedure is straightforward: Find the associated matrix A, find the "constant vector" b, and solve A*v=b. No error checking is performed.</p>
<p>Related to the GAP command <code class="code">SolutionMat( A, b )</code>.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> f:=3*y-3*x+1;; g:=-5*y+2*x-7;;
gap> soln:=SolveLinearSystem([f,g],[x,y]);
[ Z(11)^3, Z(11)^2 ]
gap> Value(f,[x,y],soln); # checking okay
0*Z(11)
gap> Value(g,[x,y],col); # checking okay
0*Z(11)
</pre></td></tr></table>
<p><a id="X80171AA687FFDC70" name="X80171AA687FFDC70"></a></p>
<h5>7.6-6 GuavaVersion</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuavaVersion</code>( <var class="Arg"></var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the current version of Guava. Same as <code class="code">guava\_version()</code>.</p>
<table class="example">
<tr><td><pre>
gap> GuavaVersion();
"2.7"
</pre></td></tr></table>
<p><a id="X7EBBE86D85CC90C0" name="X7EBBE86D85CC90C0"></a></p>
<h5>7.6-7 ZechLog</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZechLog</code>( <var class="Arg">x, b, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the Zech log of x to base b, ie the i such that $x+1=b^i$, so $y+z=y(1+z/y)=b^k$, where k=Log(y,b)+ZechLog(z/y,b) and b must be a primitive element of F.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);; l := One(F);;
gap> ZechLog(2*l,8*l,F);
-24
gap> 8*l+l;(2*l)^(-24);
Z(11)^6
Z(11)^6
</pre></td></tr></table>
<p><a id="X7C8C1E6A7E3497F0" name="X7C8C1E6A7E3497F0"></a></p>
<h5>7.6-8 CoefficientToPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoefficientToPolynomial</code>( <var class="Arg">coeffs, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">CoefficientToPolynomial</code> returns the degree d-1 polynomial c_0+c_1x+...+c_d-1x^d-1, where <var class="Arg">coeffs</var> is a list of elements of a field, coeffs= c_0,...,c_d-1, and <var class="Arg">R</var> is a univariate polynomial ring.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> coeffs:=Z(11)^0*[1,2,3,4];
[ Z(11)^0, Z(11), Z(11)^8, Z(11)^2 ]
gap> CoefficientToPolynomial(coeffs,R1);
Z(11)^2*a^3+Z(11)^8*a^2+Z(11)*a+Z(11)^0
</pre></td></tr></table>
<p><a id="X8431985183B63BB7" name="X8431985183B63BB7"></a></p>
<h5>7.6-9 DegreesMonomialTerm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreesMonomialTerm</code>( <var class="Arg">m, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">DegreesMonomialTerm</code> returns the list of degrees to which each variable in the multivariate polynomial ring <var class="Arg">R</var> occurs in the monomial <var class="Arg">m</var>, where <var class="Arg">coeffs</var> is a list of elements of a field.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
PolynomialRing(..., [ a, b ])
gap> c:=X(F,"c",var2);
c
gap> var3:=Concatenation(var2,[c]);
[ a, b, c ]
gap> R3:=PolynomialRing(F,var3);
PolynomialRing(..., [ a, b, c ])
gap> m:=b^3*c^7;
b^3*c^7
gap> DegreesMonomialTerm(m,R3);
[ 0, 3, 7 ]
</pre></td></tr></table>
<p><a id="X860EF39B841380A1" name="X860EF39B841380A1"></a></p>
<h5>7.6-10 DivisorsMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DivisorsMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">DivisorsMultivariatePolynomial</code> returns the list of polynomial divisors of <var class="Arg">f</var> in the multivariate polynomial ring <var class="Arg">R</var> with coefficients in a field. This program uses a simple but slow algorithm (see Joachim von zur Gathen, Jürgen Gerhard, <a href="chapBib.html#biBGG03">[GG03]</a>, exercise 16.10) which first converts the multivariate polynomial <var class="Arg">f</var> to an associated univariate polynomial f^*, then <code class="code">Factors</code> f^*, and finally converts these univariate factors back into the multivariate polynomial factors of <var class="Arg">f</var>. Since <code class="code">Factors</code> is non-deterministic, <code class="code">DivisorsMultivariatePolynomial</code> is non-deterministic as well.</p>
<table class="example">
<tr><td><pre>
gap> R2:=PolynomialRing(GF(3),["x1","x2"]);
PolynomialRing(..., [ x1, x2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);
[ x1, x2 ]
gap> x2:=vars[2];
x2
gap> x1:=vars[1];
x1
gap> f:=x1^3+x2^3;;
gap> DivisorsMultivariatePolynomial(f,R2);
[ x1+x2, x1+x2, x1+x2 ]
</pre></td></tr></table>
<p><a id="X82257DE97D1822AA" name="X82257DE97D1822AA"></a></p>
<h4>7.7 <span class="Heading">
GNU Free Documentation License
</span></h4>
<p>GNU Free Documentation License Version 1.2, November 2002</p>
<p>Copyright (C) 2000,2001,2002 Free Software Foundation, Inc. 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.</p>
<p>0. PREAMBLE</p>
<p>The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.</p>
<p>This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.</p>
<p>We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.</p>
<p>1. APPLICABILITY AND DEFINITIONS</p>
<p>This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law.</p>
<p>A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.</p>
<p>A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.</p>
<p>The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none.</p>
<p>The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words.</p>
<p>A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque".</p>
<p>Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only.</p>
<p>The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.</p>
<p>A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition.</p>
<p>The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.</p>
<p>2. VERBATIM COPYING</p>
<p>You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.</p>
<p>You may also lend copies, under the same conditions stated above, and you may publicly display copies.</p>
<p>3. COPYING IN QUANTITY</p>
<p>If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.</p>
<p>If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.</p>
<p>If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.</p>
<p>It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.</p>
<p>4. MODIFICATIONS</p>
<p>You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:</p>
<p>A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.</p>
<p>B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement.</p>
<p>C. State on the Title page the name of the publisher of the Modified Version, as the publisher.</p>
<p>D. Preserve all the copyright notices of the Document.</p>
<p>E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.</p>
<p>F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.</p>
<p>G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.</p>
<p>H. Include an unaltered copy of this License.</p>
<p>I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.</p>
<p>J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.</p>
<p>K. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.</p>
<p>L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.</p>
<p>M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version.</p>
<p>N. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section.</p>
<p>O. Preserve any Warranty Disclaimers.</p>
<p>If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.</p>
<p>You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.</p>
<p>You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.</p>
<p>The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.</p>
<p>5. COMBINING DOCUMENTS</p>
<p>You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers.</p>
<p>The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.</p>
<p>In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements".</p>
<p>6. COLLECTIONS OF DOCUMENTS</p>
<p>You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.</p>
<p>You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.</p>
<p>7. AGGREGATION WITH INDEPENDENT WORKS</p>
<p>A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document.</p>
<p>If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate.</p>
<p>8. TRANSLATION</p>
<p>Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail.</p>
<p>If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.</p>
<p>9. TERMINATION</p>
<p>You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.</p>
<p>10. FUTURE REVISIONS OF THIS LICENSE</p>
<p>The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.</p>
<p>Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap6.html">Previous Chapter</a> <a href="chapBib.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
|
