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

Put 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.

type codeword¶: Machine-word type used to store a binary word.

struct WordPermutation¶: Internal structure representing a word permutation.

WordPermutation *create_word_perm(void *list_perm)¶: Create a word permutation from a Python list permutation.

WordPermutation *create_array_word_perm(int *array, int start, int degree)¶: Create a word permutation from a C array.

WordPermutation *create_comp_word_perm(WordPermutation *g, WordPermutation *h)¶: Create a composition of two word permutations.

WordPermutation *create_inv_word_perm(WordPermutation *g)¶: Create the inverse of a word permutation.

WordPermutation *create_id_word_perm(int degree)¶: Create the identity word permutation.

int dealloc_word_perm(WordPermutation *wp)¶: Free the memory used by a word permutation.

codeword permute_word_by_wp(WordPermutation *wp, codeword word)¶: Apply the word permutation to a 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]