Optimized low-level binary code representation¶
Some computations with linear binary codes. Fix a basis for \(GF(2)^n\). A linear binary code is a linear subspace of \(GF(2)^n\), together with this choice of basis. A permutation \(g \in S_n\) of the fixed basis gives rise to a permutation of the vectors, or words, in \(GF(2)^n\), sending \((w_i)\) to \((w_{g(i)})\). The permutation automorphism group of the code \(C\) is the set of permutations of the basis that bijectively map \(C\) to itself. Note that if \(g\) is such a permutation, then
Over other fields, it is also required that the map be linear, which as per above boils down to scalar multiplication. However, over \(GF(2),\) the only scalars are 0 and 1, so the linearity condition has trivial effect.
AUTHOR:
Robert L Miller (Oct-Nov 2007)
compiled code data structure
union-find based orbit partition
optimized partition stack class
NICE-based partition refinement algorithm
canonical generation function
- class sage.coding.binary_code.BinaryCode¶
Bases:
object
Minimal, but optimized, binary code object.
EXAMPLES:
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) # create from matrix sage: C = BinaryCode(B, 60) # create using glue sage: D = BinaryCode(C, 240) sage: E = BinaryCode(D, 85) sage: B Binary [4,1] linear code, generator matrix [1111] sage: C Binary [6,2] linear code, generator matrix [111100] [001111] sage: D Binary [8,3] linear code, generator matrix [11110000] [00111100] [00001111] sage: E Binary [8,4] linear code, generator matrix [11110000] [00111100] [00001111] [10101010] sage: M = Matrix(GF(2), [[1]*32]) sage: B = BinaryCode(M) sage: B Binary [32,1] linear code, generator matrix [11111111111111111111111111111111]
- apply_permutation(labeling)¶
Apply a column permutation to the code.
INPUT:
labeling – a list permutation of the columns
EXAMPLES:
sage: from sage.coding.binary_code import * sage: B = BinaryCode(codes.GolayCode(GF(2)).generator_matrix()) sage: B Binary [24,12] linear code, generator matrix [100000000000101011100011] [010000000000111110010010] [001000000000110100101011] [000100000000110001110110] [000010000000110011011001] [000001000000011001101101] [000000100000001100110111] [000000010000101101111000] [000000001000010110111100] [000000000100001011011110] [000000000010101110001101] [000000000001010111000111] sage: B.apply_permutation(list(range(11,-1,-1)) + list(range(12, 24))) sage: B Binary [24,12] linear code, generator matrix [000000000001101011100011] [000000000010111110010010] [000000000100110100101011] [000000001000110001110110] [000000010000110011011001] [000000100000011001101101] [000001000000001100110111] [000010000000101101111000] [000100000000010110111100] [001000000000001011011110] [010000000000101110001101] [100000000000010111000111]
- matrix()¶
Returns the generator matrix of the BinaryCode, i.e. the code is the rowspace of B.matrix().
EXAMPLES:
sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: from sage.coding.binary_code import * sage: B = BinaryCode(M) sage: B.matrix() [1 1 1 1 0 0] [0 0 1 1 1 1]
- print_data()¶
Print all data for
self
.EXAMPLES:
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1]]) sage: B = BinaryCode(M) sage: C = BinaryCode(B, 60) sage: D = BinaryCode(C, 240) sage: E = BinaryCode(D, 85) sage: B.print_data() # random - actually "print(P.print_data())" ncols: 4 nrows: 1 nwords: 2 radix: 32 basis: 1111 words: 0000 1111 sage: C.print_data() # random - actually "print(P.print_data())" ncols: 6 nrows: 2 nwords: 4 radix: 32 basis: 111100 001111 words: 000000 111100 001111 110011 sage: D.print_data() # random - actually "print(P.print_data())" ncols: 8 nrows: 3 nwords: 8 radix: 32 basis: 11110000 00111100 00001111 words: 00000000 11110000 00111100 11001100 00001111 11111111 00110011 11000011 sage: E.print_data() # random - actually "print(P.print_data())" ncols: 8 nrows: 4 nwords: 16 radix: 32 basis: 11110000 00111100 00001111 10101010 words: 00000000 11110000 00111100 11001100 00001111 11111111 00110011 11000011 10101010 01011010 10010110 01100110 10100101 01010101 10011001 01101001
- put_in_std_form()¶
Put the code in binary form, which is defined by an identity matrix on the left, augmented by a matrix of data.
EXAMPLES:
sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0],[0,0,1,1,1,1]]) sage: B = BinaryCode(M); B Binary [6,2] linear code, generator matrix [111100] [001111] sage: B.put_in_std_form(); B 0 Binary [6,2] linear code, generator matrix [101011] [010111]
- class sage.coding.binary_code.BinaryCodeClassifier¶
Bases:
object
- generate_children(B, n, d=2)¶
Use canonical augmentation to generate children of the code B.
INPUT:
B – a BinaryCode
n – limit on the degree of the code
d – test whether new vector has weight divisible by d. If d==4, this ensures that all doubly-even canonically augmented children are generated.
EXAMPLES:
sage: from sage.coding.binary_code import * sage: BC = BinaryCodeClassifier() sage: B = BinaryCode(Matrix(GF(2), [[1,1,1,1]])) sage: BC.generate_children(B, 6, 4) [ [1 1 1 1 0 0] [0 1 0 1 1 1] ]
Note
The function
codes.databases.self_orthogonal_binary_codes
makes heavy use of this function.MORE EXAMPLES:
sage: soc_iter = codes.databases.self_orthogonal_binary_codes(12, 6, 4) sage: L = list(soc_iter) sage: for n in range(0, 13): ....: s = 'n=%2d : '%n ....: for k in range(1,7): ....: s += '%3d '%len([C for C in L if C.length() == n and C.dimension() == k]) ....: print(s) n= 0 : 0 0 0 0 0 0 n= 1 : 0 0 0 0 0 0 n= 2 : 0 0 0 0 0 0 n= 3 : 0 0 0 0 0 0 n= 4 : 1 0 0 0 0 0 n= 5 : 0 0 0 0 0 0 n= 6 : 0 1 0 0 0 0 n= 7 : 0 0 1 0 0 0 n= 8 : 1 1 1 1 0 0 n= 9 : 0 0 0 0 0 0 n=10 : 0 1 1 1 0 0 n=11 : 0 0 1 1 0 0 n=12 : 1 2 3 4 2 0
- put_in_canonical_form(B)¶
Puts the code into canonical form.
Canonical form is obtained by performing row reduction, permuting the pivots to the front so that the generator matrix is of the form: the identity matrix augmented to the right by arbitrary data.
EXAMPLES:
sage: from sage.coding.binary_code import * sage: BC = BinaryCodeClassifier() sage: B = BinaryCode(codes.GolayCode(GF(2)).generator_matrix()) sage: B.apply_permutation(list(range(24,-1,-1))) sage: B Binary [24,12] linear code, generator matrix [011000111010100000000000] [001001001111100000000001] [011010100101100000000010] [001101110001100000000100] [010011011001100000001000] [010110110011000000010000] [011101100110000000100000] [000011110110100001000000] [000111101101000010000000] [001111011010000100000000] [010110001110101000000000] [011100011101010000000000] sage: BC.put_in_canonical_form(B) sage: B Binary [24,12] linear code, generator matrix [100000000000001100111001] [010000000000001010001111] [001000000000001111010010] [000100000000010110101010] [000010000000010110010101] [000001000000010001101101] [000000100000011000110110] [000000010000011111001001] [000000001000010101110011] [000000000100010011011110] [000000000010001011110101] [000000000001001101101110]
- class sage.coding.binary_code.OrbitPartition¶
Bases:
object
Structure which keeps track of which vertices are equivalent under the part of the automorphism group that has already been seen, during search. Essentially a disjoint-set data structure*, which also keeps track of the minimum element and size of each cell of the partition, and the size of the partition.
- class sage.coding.binary_code.PartitionStack¶
Bases:
object
Partition stack structure for traversing the search tree during automorphism group computation.
- cmp(other, CG)¶
EXAMPLES:
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: M = Matrix(GF(2), [[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: B = BinaryCode(M) sage: P = PartitionStack(4, 8) sage: P._refine(0, [[0,0],[1,0]], B) 181 sage: P._split_vertex(0, 1) 0 sage: P._refine(1, [[0,0]], B) 290 sage: P._split_vertex(1, 2) 1 sage: P._refine(2, [[0,1]], B) 463 sage: P._split_vertex(2, 3) 2 sage: P._refine(3, [[0,2]], B) 1500 sage: P._split_vertex(4, 4) 4 sage: P._refine(4, [[0,4]], B) 1224 sage: P._is_discrete(4) 1 sage: Q = PartitionStack(P) sage: Q._clear(4) sage: Q._split_vertex(5, 4) 4 sage: Q._refine(4, [[0,4]], B) 1224 sage: Q._is_discrete(4) 1 sage: Q.cmp(P, B) 0
- print_basis()¶
EXAMPLES:
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(4, 8) sage: P._dangerous_dont_use_set_ents_lvls(list(range(8)), list(range(7))+[-1], [4,7,12,11,1,9,3,0,2,5,6,8,10,13,14,15], [0]*16) sage: P ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1,2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2,3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3,4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4,5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5,6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6,7}) ({4},{7},{12},{11},{1},{9},{3},{0},{2},{5},{6},{8},{10},{13},{14},{15}) ({0},{1},{2},{3},{4},{5},{6},{7}) sage: P._find_basis() sage: P.print_basis() basis_locations: 4 8 0 11
- print_data()¶
Prints all data for self.
EXAMPLES:
sage: import sage.coding.binary_code sage: from sage.coding.binary_code import * sage: P = PartitionStack(2, 6) sage: print(P.print_data()) nwords:4 nrows:2 ncols:6 radix:32 wd_ents: 0 1 2 3 wd_lvls: 12 12 12 -1 col_ents: 0 1 2 3 4 5 col_lvls: 12 12 12 12 12 -1 col_degs: 0 0 0 0 0 0 col_counts: 0 0 0 0 col_output: 0 0 0 0 0 0 wd_degs: 0 0 0 0 wd_counts: 0 0 0 0 0 0 0 wd_output: 0 0 0 0
- sage.coding.binary_code.test_expand_to_ortho_basis(B=None)¶
This function is written in pure C for speed, and is tested from this function.
INPUT:
B – a BinaryCode in standard form
OUTPUT:
An array of codewords which represent the expansion of a basis for \(B\) to a basis for \((B^\prime)^\perp\), where \(B^\prime = B\) if the all-ones vector 1 is in \(B\), otherwise \(B^\prime = ext{span}(B,1)\) (note that this guarantees that all the vectors in the span of the output have even weight).
- sage.coding.binary_code.test_word_perms(t_limit=5.0)¶
Tests the WordPermutation structs for at least t_limit seconds.
These are structures written in pure C for speed, and are tested from this function, which performs the following tests:
- Tests create_word_perm, which creates a WordPermutation from a Python
list L representing a permutation i –> L[i]. Takes a random word and permutes it by a random list permutation, and tests that the result agrees with doing it the slow way.
- 1b. Tests create_array_word_perm, which creates a WordPermutation from a
C array. Does the same as above.
- Tests create_comp_word_perm, which creates a WordPermutation as a
composition of two WordPermutations. Takes a random word and two random permutations, and tests that the result of permuting by the composition is correct.
- Tests create_inv_word_perm and create_id_word_perm, which create a
WordPermutation as the inverse and identity permutations, resp. Takes a random word and a random permutation, and tests that the result permuting by the permutation and its inverse in either order, and permuting by the identity both return the original word.
Note
The functions permute_word_by_wp and dealloc_word_perm are implicitly involved in each of the above tests.
- sage.coding.binary_code.weight_dist(M)¶
Computes the weight distribution of the row space of M.
EXAMPLES:
sage: from sage.coding.binary_code import weight_dist sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], ....: [0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0], ....: [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1], ....: [0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1], ....: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 1] sage: M = Matrix(GF(2),[ ....: [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], ....: [0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0], ....: [0,0,0,0,0,1,0,1,0,0,0,1,1,1,1,1,1], ....: [0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 4, 0, 0, 0, 0, 0] sage: M=Matrix(GF(2),[ ....: [1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0], ....: [0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0], ....: [0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0], ....: [0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0], ....: [0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0], ....: [0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0], ....: [0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0], ....: [0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1]]) sage: weight_dist(M) [1, 0, 0, 0, 0, 0, 68, 0, 85, 0, 68, 0, 34, 0, 0, 0, 0, 0]