Package sage :: Package coding :: Module binary_code

Module binary_code

File: sage/coding/binary_code.pyx (starting at line 1)

Fast binary code routines.

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 datastructure
        * union-find based orbit partition
        * optimized partition stack class
        * NICE-based partition refinement algorithm
        * canonical generation function

Classes

[hide private]

BinaryCode
File: sage/coding/binary_code.pyx (starting at line 600) Minimal, but optimized, binary code object.

BinaryCodeClassifier

OrbitPartition
File: sage/coding/binary_code.pyx (starting at line 1135) Structure which keeps track of which vertices are equivalent under the part of the automorphism group that has already been seen, during search.

PartitionStack
File: sage/coding/binary_code.pyx (starting at line 1441) Partition stack structure for traversing the search tree during automorphism group computation.

Functions

[hide private]

test_expand_to_ortho_basis(...)
File: sage/coding/binary_code.pyx (starting at line 428) This function is written in pure C for speed, and is tested from this function.

test_word_perms(...)
File: sage/coding/binary_code.pyx (starting at line 76) Tests the WordPermutation structs for at least t_limit seconds.

Variables

[hide private]

WORD_SIZE = 32

__pyx_capi__ = {'create_array_word_perm': <PyCObject object at...

Function Details

[hide private]

test_expand_to_ortho_basis(...)

File: sage/coding/binary_code.pyx (starting at line 428)

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

TESTS:
    sage: from sage.coding.binary_code import test_expand_to_ortho_basis, BinaryCode
    sage: M = Matrix(GF(2), [[1,1,1,1,1,1,0,0,0,0],[0,0,1,1,1,1,1,1,1,1]])
    sage: B = BinaryCode(M)
    sage: B.put_in_std_form()
    0
    sage: test_expand_to_ortho_basis(B=B)
    INPUT CODE:
    Binary [10,2] linear code, generator matrix
    [1010001111]
    [0101111111]
    Expanding to the basis of an orthogonal complement...
    Basis:
    0010000010
    0001000010
    0000100001
    0000010001
    0000001001

test_word_perms(...)

File: sage/coding/binary_code.pyx (starting at line 76)

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:

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

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

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

TESTS:
    sage: from sage.coding.binary_code import test_word_perms
    sage: test_word_perms()

Variables Details

[hide private]

__pyx_capi__

Value:

{'create_array_word_perm': <PyCObject object at 0xa97f508>,
 'create_comp_word_perm': <PyCObject object at 0xa97f968>,
 'create_id_word_perm': <PyCObject object at 0xa97fc60>,
 'create_inv_word_perm': <PyCObject object at 0xa97f850>,
 'create_word_perm': <PyCObject object at 0xa97fd28>,
 'dealloc_word_perm': <PyCObject object at 0xa97f8c8>,
 'expand_to_ortho_basis': <PyCObject object at 0xa97f3f0>,
 'hamming_weights': <PyCObject object at 0xa97f9b8>,
...