Transcript Poster - IICQI

Evaluation of bounds of codes defined over hexagonal and honeycomb lattices via linear
programming based on association schemes
M. A. Jafarizadeh, N. Behbood
E-mail: [email protected]
International Iran conference on Quantum Information
September 2007, Kish Island
Introduction
While we can say much about codes without talking about
association schemes, the algebraic structure they provide,
gives us a more complete picture of how codes interact
with the set they belong to. So far, Delsarte has used this
algebraic structure to give one of the strongest bounds on
the size of codes. Typically, the most of works on
Delsarte's linear programming bound have been
developed for the underlying codes of distance regular
association schemes (distance-regular codes). In this
work, by using underlying graphs of association schemes
and Delsarte's linear programming bound, a way has been
introduced for calculating some new bounds for more
general codes which are not distance regular. Hence, for
achieving upper bound for a given code with minimum
distance d, the number of steps needed for covering all
codewords in distance d from an arbitrary codeword
(called reference codeword), is determined via the
structure of the corresponding underlying graph of
association scheme.
Association schemes
Let X be a finite set of cardinality
be subsets of
such that:
.Let
Is independent of the choice of
.
.Therefore, the relation define an abelian association
scheme. The corresponding adjacency matrices recursion
would be as follow
Distribution vectors and Delsarte linear programming
bound
If (X,R) is an association scheme and Y is a subset of X,
then we can define the distribution vector and distribution
matrix of Y as follows. The distribution vector of Y is the
vector a whose ith entry is given by:
The investigated upper bound for
square lattice with the above first
adjacency matrix are shown in
table II.
The perfect code case has been
introduced in follow:
Construction of association scheme from two copies
of hexagonal lattice
We extend the group by
direct product with
and
obtain .
as a vertex set for underlying graph of
association scheme that we want to construct finite
honeycomb lattice is equivalent to two copies of finite
hexagonal lattice. adjacency matrix A corresponding to
finite honeycomb lattice is
Where and
are at distance 2 from
, and
at
distance 3 and
and
at distance 4 of reference
codeword
. So, the underlying graph of association
scheme structure of this example is not distance regular
graph and despite the distance regular once, distance
between any two arbitrary codewords is not equal to the
number of steps needed for going from one codeword to
the another.
Idempotent
Since the matrices Ai commute, they can be diagonalized
simultaneously, i.e., there exists a matrix S such that for each
is a diagonal matrix. Therefore A is semi-simple and has a
second basis
.These are matrices satisfying
The matrix
(where J is the all-one matrix in A) is a
minimal idempotent (idempotent is clear, and minimal follows
from the rank(J)= 1). The
are known as the
primitive idempotent of Y . An idempotent
is primitive if it
is not the sum of two orthogonal idempotents.
are the
matrix
Adjacency matrices of underlying graph for m =7.
.
Such a system
is called an association
scheme of class d on X. The cardinality of n on X is called
the order of association scheme. The sets
.
are called the relations of the association scheme.
In addition to the above properties:
5. If
for all i, j, k is satisfied, then X is called a
commutative association scheme of class d on X.
6. If i’ = i for all i, then X is called a symmetric association
scheme of class d on X.
Another association scheme structure on
association scheme with the first adjacency
equal to:
where
case m = 3
The adjacency matrices of Bose-Mesner algebra are written
as
The objective function and constraints of this case are as
follow:
At following, we will use of Delsarte linear programming
bound for finding upper bound of this code with minimum
distance 3. For this aim, all the array of distribution vector
of whole words which are in distance less than 3 must be
vanished to zero. the words which belong to
are in
distance less than 3, so the related distribution vector array
.
are equal to zero in the objective function and
constraints. For the following objective function with the
related constraints by using linear programming
Bound (Simplex method), the upper bound of code is
achieved.
The `s can be thought of as the average number of
elements in Y at distance i from some other element of Y.
The linear programming bound, presented by Delsarte in
1973, improved the bounds of codes. we know if a is the
distribution vector of a subset Y of an association scheme
(X,R) with dual eigenmatrix Q, then aQ ≥ 0. It can be
resulted from the above that for an association scheme A
with dual eigenmatrix Q, diameter d, and distribution vector
.
Then any code C with minimum distance r in
A satisfies:
the upper bound of related code with minimum distance
d ≤3 is |C|≤3.103.
Quantum codes over GF(4)
One aspect for constructing quantum codes is codes on
the Galois field GF(4). The elements of this field consist of
with
. One additive code C
with length n on GF(4) is one additive subsets on
If one error- correction quantum code [n,k,d] exists, then
there is answers for the following equations.
Some of investigated
bound for codes over
Goalies field GF(4) has
been introduced on
table III.
When constructing a code C with a particular minimum
distance, the above gives a restriction on the distribution
vector of C. The first element of a will be 1, and if we want
to restrict our bound to codes of minimum distance r, the
entries through
should all be zero and the remaining
entries should be non-negative. So we wish to maximize
the sum:
with bellow restriction:
The linear programming bound gives us this last
relationship, and so the solution to this linear program will
be an upper bound on the size of our code.
Construction of two-variable P-polynomial association
schemes from
First we choose the ordering of elements of
as
follows
Where
element
and
will be
. We use the notation (k, l) for the
of the group. Clearly, (k, l)(k’, l’) = (k + k’, l + l’)
.Then the vertex set V of the graph
.For the generating set
(all permutations of the simple roots
and
.
together with the lowest root
of the
root lattice). Then, the orbits
form a partition
P. since any product of two orbits
is invariant
under symmetric group , the set of orbits is closed under
multiplication.
Also,
if
we
use
the
notation
,
it can be shown that the
intersection number:
Table III
The investigated upper bound for hexagonal lattice of
the above example is |C| ≤7 and this code is perfect
code:
The other investigated
upper
bound
for
hexagonal
association
scheme are introdused at
table I.
Table I
Conclusion:
Delsarte linear programming method for achiving upper
bound of codes under association scheme structure which
are not distance regular has been studied. It is showed
that the underlying graph of association schem stratifies
the graph into d+1 disjoint union of strata ( associate class)
which is different from stratification based on distance,
distance, except for distance regular graphs.
References
[1]-P.Delsarte - An algebraic approach to the association
schemes of coding theory -Philips Research Reports
Supplements, (1973)
[2]-A.R.Calderbank , E.M.Rains , P.W.Shor , A.Sloane Quantum error correction and orthogonal geometry ,[quant-ph/9605005] (1996)
[3]-H.Tarnanen - Upper bound on permutation codes via
linear programming – Eroup . J .combinatorics(1999)
20(101-114)