1 /* File code.c. Contains miscellaneous functions for computations with
2 binary codes. */
3
4 #include <stdlib.h>
5
6 #include "group.h"
7
8 #include "errmesg.h"
9 #include "storage.h"
10
CHECK(code)11 CHECK( code)
12
13
14 /*-------------------------- reduceBasis ----------------------------------*/
15
16 /* The function reduceBasis allocates an infoSet for a code (unless one is
17 already allocated -- if so, it must have the right size) and then performs
18 elementary row operations on the generator matrix in order to make
19 entry infoSet[j],i equal to delta(i,j). */
20
21 void reduceBasis(
22 Code *const C)
23 {
24 Unsigned row, col, i, j, mu;
25
26 if ( !C->infoSet )
27 C->infoSet = malloc( (C->dimension+2) * sizeof(Unsigned) );
28 for ( row = 1 ; row <= C->dimension ; ++row ) {
29 for ( col = 1 ; col <= C->length && C->basis[row][col] == 0; ++col )
30 ;
31 if ( col > C->length )
32 ERROR( "reduceBasis", "Basis vectors not independent.")
33 C->infoSet[row] = col;
34 if ( C->fieldSize == 2 )
35 for ( i = 1 ; i <= C->dimension ; ++i )
36 if ( i != row && C->basis[i][col] != 0 )
37 for ( j = 1 ; j <= C->length ; ++j )
38 C->basis[i][j] ^= C->basis[row][j];
39 else
40 ;
41 else {
42 mu = C->field->inv[C->basis[row][col]];
43 for ( j = 1 ; j <= C->length ; ++j )
44 C->basis[row][j] = C->field->prod[mu][C->basis[row][j]];
45 for ( i = 1 ; i <= C->dimension ; ++i )
46 if ( i != row && C->basis[i][col] != 0 ) {
47 mu = C->basis[i][col];
48 for ( j = 1 ; j <= C->length ; ++j )
49 C->basis[i][j] = C->field->dif[C->basis[i][j]]
50 [C->field->prod[mu][C->basis[row][j]]];
51 }
52 }
53 }
54 }
55
56
57 /*-------------------------- codeContainsVector ----------------------------*/
58
59 /* The function codeContainsVector( C, v) returns true is the vector v is
60 contained in the code C and false otherwise. The vector v is destroyed.
61 Here a vector is simply an array of characters. If C does not have a
62 canonical basis, one is constructed. */
63
codeContainsVector(Code * const C,char * const v)64 BOOLEAN codeContainsVector(
65 Code *const C,
66 char *const v)
67 {
68 Unsigned i, j, col, mu;
69
70 /* If a canonical basis is not available for C, construct one. */
71 if ( !C->infoSet )
72 reduceBasis( C);
73
74 /* Try to reduce v. */
75 for ( i = 1 ; i <= C->dimension ; ++i ) {
76 col = C->infoSet[i];
77 if ( C->fieldSize == 2 ) {
78 if ( v[col] != 0 )
79 for ( j = 1 ; j <= C->length ; ++j )
80 v[j] ^= C->basis[i][j];
81 }
82 else
83 if ( v[col] != 0 ) {
84 mu = C->basis[i][col];
85 for ( j = 1 ; j <= C->length ; ++j )
86 v[j] = C->field->dif[v[j]][C->field->prod[mu][C->basis[i][j]]];
87 }
88 }
89
90 /* Check if reduction gave the zero vector. */
91 for ( j = 1 ; j <= C->length ; ++j )
92 if ( v[j] != 0 )
93 return FALSE;
94
95 return TRUE;
96 }
97
98
99 /*-------------------------- isCodeIsomorphism ----------------------------*/
100
101 /* The function isCodeIsomorphism( C1, C2, s) returns TRUE if permutation s
102 is an isomorphism of code C1 to code C2 and returns false otherwise. */
103
isCodeIsomorphism(Code * const C1,Code * const C2,const Permutation * const s)104 BOOLEAN isCodeIsomorphism(
105 Code *const C1,
106 Code *const C2,
107 const Permutation *const s)
108 {
109 char *tempVec = allocBooleanArrayDegree();
110 Unsigned i, j, temp, mu, lambda;
111 Unsigned collapsedDegree;
112
113 if ( C1->length != C2->length || C1->dimension != C2->dimension ||
114 C1->length > s->degree )
115 ERROR( "isCodeIsomorphism", "Lengths or degrees not compatible.")
116
117
118 /* If the field size exceeds 2, check that s satisfies monomial property. */
119 if ( C1->fieldSize > 2 ) {
120 collapsedDegree = C1->length / (C1->fieldSize-1);
121 for ( i = 1 ; i <= collapsedDegree ; ++i ) {
122 /* Find mu,j such that s(1*i) = mu*j. */
123 temp = s->image[(C1->fieldSize-1)*(i-1)+1];
124 j = (temp-1) / (C1->fieldSize-1) + 1;
125 mu = (temp-1) % (C1->fieldSize-1) + 1;
126 for ( lambda = 2 ; lambda < C1->fieldSize ; ++lambda )
127 if ( s->image[(C1->fieldSize-1)*(i-1)+lambda] !=
128 (C1->fieldSize-1)*(j-1) + C1->field->prod[lambda][mu] ) {
129 freeBooleanArrayDegree( tempVec);
130 return FALSE;
131 }
132 }
133 }
134
135 /* Now check that each basis vector of C1 lies in C2. */
136 for ( i = 1 ; i <= C1->dimension ; ++i ) {
137 for ( j = 1 ; j <= C1->length ; ++j )
138 tempVec[s->image[j]] = C1->basis[i][j];
139 if ( !codeContainsVector(C2,tempVec) ) {
140 freeBooleanArrayDegree( tempVec);
141 return FALSE;
142 }
143 }
144
145 freeBooleanArrayDegree( tempVec);
146 return TRUE;
147 }
148
149