|
Let C be an [n, k] linear code and G a permutation group of degree
n. Then G acts on C in the following way: for a codeword v of
C and a permutation x of G, the image of v under x is obtained
from v by permuting the coordinate positions of v according to x.
We call this the permutation action of G on C.
If C is a non-binary code over a finite field,
there is also a monomial action on C.
Let K be the alphabet of C. A monomial permutation of monomial degree
n is equivalent to a permutation s on
K * x { 1, ..., n } which satisfies the following
property:
(α, i)s = (β, j) implies
(γα, i)s = (γβ, j)
for all α, β, γ ∈K * and i, j ∈{ 1, ..., n }. The actual degree of s is (q - 1)n.
Note that s is completely determined by its action
on the points (1, i) for each i, and
the matrix representation of s is also determined by its action
on the elements (1, i), for 1 ≤i ≤n.
To represent a monomial permutation of monomial degree
n, we number the pair (α, i) by (q - 1)(i - 1) + α and
then use a permutation s of degree (q - 1)n.
The functions in this section allow one to investigate such actions.
The algorithms in Magma to compute with such actions are backtrack
searches due to Jeff Leon [Leo82][Leo97].
There are 4 algorithms which are provided for codes of
length n over a field of cardinality q:
- (a)
- Automorphism group or Monomial group. Computes the
group of monomials which map a code into itself, where monomials
are represented as permutations of degree (q - 1)n (so the
group has degree (q - 1)n).
For this function q may be any small prime or 4.
- (b)
- Permutation group. Computes the group of permutations
which map a code into itself (so the group has degree n).
For this function q may be any small prime or 4.
- (c)
- Equivalence test. Computes whether there is a monomial
permutation which maps a code to another code and, if so, returns
the monomial as a permutation of degree (q - 1)n. For this function,
q may be any small prime or 4.
- (d)
- Isomorphism test. Computes whether there is a permutation
which maps a code to another code and returns the permutation
(of degree n) if so. For this function q may only be 2.
For more information on permutation group actions and orbits, see Chapter
PERMUTATION GROUPS.
Given a codeword v belonging to the [n, k] code C and
an element x belonging to a permutation group G, construct the
vector w obtained from v by the action of x. If G has degree
n, the permutation action is used; otherwise G should have degree
n(q - 1) and the monomial action is used.
Given a codeword v belonging to the [n, k] code C and
a permutation group G (with permutation or monomial action on C),
construct the vector orbit Y of v under the action of G.
The orbit Y is a G-set for the group G.
Given an [n, k] code C and an element x belonging to a
permutation group G (with permutation or monomial action on C),
construct the code consisting of all the images of the
codewords of C under the action of x.
Given an [n, k] code C and a permutation group G
(with permutation or monomial action on C), construct
the orbit Y of C under the action of G. The orbit
Y is a G-set for the group G.
S ^ x : { ModTupFldElt }, GrpPermElt -> { ModTupFldElt }
Given a set or sequence S of codewords belonging to the [n, k] code C
and an element x belonging to a permutation group
(with permutation or monomial action on the codewords),
construct the set or sequence of the vectors obtained by permuting the
coordinate positions of v, for each v in S,
according to the permutation x.
S ^ x : { Code }, GrpPermElt -> { Code }
Given a set or sequence S of codes of length n
and an element x belonging to a permutation group
(with permutation or monomial action on the codes) construct the set
or sequence of the codes consisting of all the
images of the codewords of C under the action of x.
Given an [n, k] code C and a permutation group G of
degree n, find the subcode of C which consists of those
vectors of C which are fixed by the elements of G.
That is, the subcode consists of those codewords that are fixed
by the group G.
MonomialGroup(C: parameters) : Code -> GrpPerm, PowMap, Map
Weight: RngIntElt Default: 0
The automorphism group A of the [n, k] linear code C over the field K,
where A is the group of all monomial-action permutations which preserve the
code. Thus both permutation of coordinates and multiplication of
components by non-zero elements from K is allowed, and the degree
of A is n(q - 1) where q is the cardinality of K.
A power structure P and transfer map t are also returned, so that, given
a permutation g from A, one can create a map f = t(g) which represents
the automorphism g as a mapping P: C -> C.
If the code is known to have very few words of low weight, then it may take
some time to compute the support of the code (a set of low weight words).
The optional parameter
Weight can be used to specify the set of vectors of
the specified weight to be used as the support in the algorithm.
This set should be of a reasonable size, (possibly hundreds for a large code),
while also keeping the weight as small as possible.
Warning: If Weight specifies a set that is too small, then the
algorithm risks getting stuck.
The permutation group G of the [n, k] linear code C over the field K,
where G is the group of all permutation-action permutations which preserve the
code. Thus only permutation of coordinates is allowed, and the degree
of G is always n.
A power structure P and transfer map t are also returned, so that, given
a permutation g from G, one can create a map f = t(g) which represents
the automorphism g as a mapping P: C -> C.
MonomialSubgroup(C) : Code -> GrpPerm, PowMap, Map
A subgroup of the (monomial) automorphism group A of the code C. If the
automorphism group of C is already known then the group returned is the
full automorphism group, otherwise it will be a subgroup generated by
one element.
This allows one to find just one automorphism of C if desired.
A power structure P and transfer map t are also returned, so that, given
a permutation g from A, one can create a map f = t(g) which represents
the automorphism g as a mapping P: C -> C.
MonomialGroupStabilizer(C, k) : Code, RngIntElt -> GrpPerm, PowMap, Map
The subgroup of the (monomial) automorphism group A of the code C, which
stabilizes the first k base points as chosen by the backtrack search.
These base points may be different to those of the returned group.
A power structure P and transfer map t are also returned, so that, given
a permutation g from A, one can create a map f = t(g) which represents
the automorphism g as a mapping P: C -> C.
The power structure A of all automorphisms of the code C
(with monomial action), together with the transfer map t into A
from the generic symmetric group associated with the automorphism group of
C.
The power structure A of all automorphisms of the code C, together with the
transfer map t into A from the generic symmetric group associated with the
automorphism group of C; the string T determines which action type should
be used: "Monomial" or "Permutation".
We compute the automorphism group of the second order Reed--Muller
code of length 64.
> C := ReedMullerCode(2, 6);
> aut := AutomorphismGroup(C);
> FactoredOrder(aut);
[ <2, 21>, [3, 4>, <5, 1>, <7, 2>, <31, 1> ]
> CompositionFactors(aut);
G
| A(5, 2) = L(6, 2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
1
We compute the automorphism group of a BCH code using the set of
vectors of minimal weight as the invariant set. We look first at its
weight distribution to confirm that there is sufficient vectors.
> C := BCHCode(GF(2),23,2);
> C;
[23, 12, 7] BCH code (d = 2, b = 1) over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1]
> WeightDistribution(C);
[ <0, 1>, <7, 253>, <8, 506>, <11, 1288>, <12, 1288>, <15, 506>,
<16, 253>, <23, 1> ]
> AutomorphismGroup(C : Weight := MinimumWeight(C) );
Permutation group acting on a set of cardinality 23
Order = 10200960 = 2^7 * 3^2 * 5 * 7 * 11 * 23
(6, 15, 12)(7, 20, 19)(8, 9, 17)(10, 13, 22)(11, 14, 23)(16,
18, 21)
(5, 17, 9)(6, 21, 20)(7, 16, 23)(10, 13, 22)(11, 12, 19)(14,
18, 15)
(5, 16, 21)(6, 23, 19)(7, 17, 12)(8, 14, 15)(9, 20, 11)(10,
13, 22)
(1, 2)(4, 12)(5, 7)(6, 17)(9, 10)(13, 21)(15, 18)(22, 23)
(2, 3)(4, 21, 6, 20)(5, 10, 12, 17)(7, 13, 9, 11)(15, 18)(16,
19, 22, 23)
(3, 8)(4, 5, 20, 22)(6, 16, 21, 12)(7, 11, 13, 9)(10, 17, 19,
23)(15, 18)
(4, 8, 6, 21, 20)(5, 10, 14, 17, 12)(7, 22, 18, 16, 9)(11,
23, 19, 13, 15)
IsEquivalent(C, D: parameters) : Code, Code -> BoolElt, Map
AutomorphismGroups: MonStgElt Default: "Right"
Weight: RngIntElt Default: 0
Given [n, k] codes C and D, this function returns true if and only
if C is equivalent to D. If C is equivalent to D, an equivalence
map f is also returned from C onto D.
The equivalence is with respect to the monomial action.
The function first computes none, one, or both of the automorphism groups
of the left and right codes. This may assist the isomorphism testing.
The parameter AutomorphismGroups, with valid string values
Both, Left, Right, None, may be used to specify
which of the automorphism groups should be constructed first if not already
known. The default is Right.
In rare cases this algorithm can get stuck, due to an insufficient
set of invariant vectors. In this case, the optional parameter
Weight can be used to specify this set to be the vectors of
the specified weight.
This set should be of a reasonable size, (possibly hundreds for large codes),
while also keeping the weight as small as possible.
Warning: If Weight specifies a set that is too small, then the
algorithm risks getting stuck.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|