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

\[g(a_i) + g(b_i) = (a_{g(i)} + b_{g(i)}) = g((a_i) + (b_i)).\]

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[source]¶

Bases: object

Minimal, but optimized, binary code object.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> import sage.coding.binary_code
>>> from sage.coding.binary_code import *
>>> M = Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1)]])
>>> B = BinaryCode(M)     # create from matrix
>>> C = BinaryCode(B, Integer(60)) # create using glue
>>> D = BinaryCode(C, Integer(240))
>>> E = BinaryCode(D, Integer(85))
>>> B
Binary [4,1] linear code, generator matrix
[1111]
>>> C
Binary [6,2] linear code, generator matrix
[111100]
[001111]
>>> D
Binary [8,3] linear code, generator matrix
[11110000]
[00111100]
[00001111]
>>> E
Binary [8,4] linear code, generator matrix
[11110000]
[00111100]
[00001111]
[10101010]

>>> M = Matrix(GF(Integer(2)), [[Integer(1)]*Integer(32)])
>>> B = BinaryCode(M)
>>> B
Binary [32,1] linear code, generator matrix
[11111111111111111111111111111111]

apply_permutation(labeling)[source]¶

Apply a column permutation to the code.

INPUT:

labeling – list permutation of the columns

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.coding.binary_code import *
>>> B = BinaryCode(codes.GolayCode(GF(Integer(2))).generator_matrix())
>>> B
Binary [24,12] linear code, generator matrix
[100000000000101011100011]
[010000000000111110010010]
[001000000000110100101011]
[000100000000110001110110]
[000010000000110011011001]
[000001000000011001101101]
[000000100000001100110111]
[000000010000101101111000]
[000000001000010110111100]
[000000000100001011011110]
[000000000010101110001101]
[000000000001010111000111]
>>> B.apply_permutation(list(range(Integer(11),-Integer(1),-Integer(1))) + list(range(Integer(12), Integer(24))))
>>> B
Binary [24,12] linear code, generator matrix
[000000000001101011100011]
[000000000010111110010010]
[000000000100110100101011]
[000000001000110001110110]
[000000010000110011011001]
[000000100000011001101101]
[000001000000001100110111]
[000010000000101101111000]
[000100000000010110111100]
[001000000000001011011110]
[010000000000101110001101]
[100000000000010111000111]

matrix()[source]¶

Return the generator matrix of the BinaryCode, i.e. the code is the rowspace of B.matrix().

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> M = Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1)]])
>>> from sage.coding.binary_code import *
>>> B = BinaryCode(M)
>>> B.matrix()
[1 1 1 1 0 0]
[0 0 1 1 1 1]

print_data()[source]¶

Print all data for self.

EXAMPLES:

Sage

sage: # needs sage.graphs
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

Python

>>> from sage.all import *
>>> # needs sage.graphs
>>> import sage.coding.binary_code
>>> from sage.coding.binary_code import *
>>> M = Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1)]])
>>> B = BinaryCode(M)
>>> C = BinaryCode(B, Integer(60))
>>> D = BinaryCode(C, Integer(240))
>>> E = BinaryCode(D, Integer(85))
>>> B.print_data() # random - actually "print(P.print_data())"
ncols: 4
nrows: 1
nwords: 2
radix: 32
basis:
1111
words:
0000
1111
>>> 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
>>> 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
>>> 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()[source]¶

Put the code in binary form, which is defined by an identity matrix on the left, augmented by a matrix of data.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.coding.binary_code import *
>>> M = Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1)]])
>>> B = BinaryCode(M); B
Binary [6,2] linear code, generator matrix
[111100]
[001111]
>>> 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)[source]¶

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

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)                                         # needs sage.groups
[
[1 1 1 1 0 0]
[0 1 0 1 1 1]
]

Python

>>> from sage.all import *
>>> from sage.coding.binary_code import *
>>> BC = BinaryCodeClassifier()
>>> B = BinaryCode(Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1)]]))
>>> BC.generate_children(B, Integer(6), Integer(4))                                         # needs sage.groups
[
[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

sage: # needs sage.groups
sage: soc_iter = codes.databases.self_orthogonal_binary_codes(12, 6, 4)
sage: L = list(soc_iter)
sage: for n in range(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

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> soc_iter = codes.databases.self_orthogonal_binary_codes(Integer(12), Integer(6), Integer(4))
>>> L = list(soc_iter)
>>> for n in range(Integer(13)):
...   s = 'n=%2d : '%n
...   for k in range(Integer(1),Integer(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)[source]¶

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

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]

Python

>>> from sage.all import *
>>> from sage.coding.binary_code import *
>>> BC = BinaryCodeClassifier()
>>> B = BinaryCode(codes.GolayCode(GF(Integer(2))).generator_matrix())
>>> B.apply_permutation(list(range(Integer(24),-Integer(1),-Integer(1))))
>>> B
Binary [24,12] linear code, generator matrix
[011000111010100000000000]
[001001001111100000000001]
[011010100101100000000010]
[001101110001100000000100]
[010011011001100000001000]
[010110110011000000010000]
[011101100110000000100000]
[000011110110100001000000]
[000111101101000010000000]
[001111011010000100000000]
[010110001110101000000000]
[011100011101010000000000]
>>> BC.put_in_canonical_form(B)
>>> 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[source]¶

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.

See Wikipedia article Disjoint-set_data_structure

class sage.coding.binary_code.PartitionStack[source]¶

Bases: object

Partition stack structure for traversing the search tree during automorphism group computation.

cmp(other, CG)[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> import sage.coding.binary_code
>>> from sage.coding.binary_code import *
>>> M = Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],
...                    [Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1)], [Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)]])
>>> B = BinaryCode(M)
>>> P = PartitionStack(Integer(4), Integer(8))
>>> P._refine(Integer(0), [[Integer(0),Integer(0)],[Integer(1),Integer(0)]], B)
181
>>> P._split_vertex(Integer(0), Integer(1))
0
>>> P._refine(Integer(1), [[Integer(0),Integer(0)]], B)
290
>>> P._split_vertex(Integer(1), Integer(2))
1
>>> P._refine(Integer(2), [[Integer(0),Integer(1)]], B)
463
>>> P._split_vertex(Integer(2), Integer(3))
2
>>> P._refine(Integer(3), [[Integer(0),Integer(2)]], B)
1500
>>> P._split_vertex(Integer(4), Integer(4))
4
>>> P._refine(Integer(4), [[Integer(0),Integer(4)]], B)
1224
>>> P._is_discrete(Integer(4))
1
>>> Q = PartitionStack(P)
>>> Q._clear(Integer(4))
>>> Q._split_vertex(Integer(5), Integer(4))
4
>>> Q._refine(Integer(4), [[Integer(0),Integer(4)]], B)
1224
>>> Q._is_discrete(Integer(4))
1
>>> Q.cmp(P, B)
0

print_basis()[source]¶

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> import sage.coding.binary_code
>>> from sage.coding.binary_code import *
>>> P = PartitionStack(Integer(4), Integer(8))
>>> P._dangerous_dont_use_set_ents_lvls(
...     list(range(Integer(8))),
...     list(range(Integer(7))) + [-Integer(1)],
...     [Integer(4),Integer(7),Integer(12),Integer(11),Integer(1),Integer(9),Integer(3),Integer(0),Integer(2),Integer(5),Integer(6),Integer(8),Integer(10),Integer(13),Integer(14),Integer(15)],
...     [Integer(0)]*Integer(16))
>>> 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})
>>> P._find_basis()
>>> P.print_basis()
basis_locations:
4
8
0
11

print_data()[source]¶

Print all data for self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> import sage.coding.binary_code
>>> from sage.coding.binary_code import *
>>> P = PartitionStack(Integer(2), Integer(6))
>>> 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)[source]¶

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 = \text{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)[source]¶

Test 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 \mapsto 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 WordPermutation objects. 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)[source]¶

Compute the weight distribution of the row space of \(M\).

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.coding.binary_code import weight_dist
>>> M = Matrix(GF(Integer(2)), [
...  [Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1)],
...  [Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1)],
...  [Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1)]])
>>> weight_dist(M)
[1, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 1]
>>> M = Matrix(GF(Integer(2)), [
...  [Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1)],
...  [Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(1)]])
>>> weight_dist(M)
[1, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 4, 0, 0, 0, 0, 0]
>>> M = Matrix(GF(Integer(2)), [
...  [Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0)],
...  [Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(1)]])
>>> weight_dist(M)
[1, 0, 0, 0, 0, 0, 68, 0, 85, 0, 68, 0, 34, 0, 0, 0, 0, 0]