Cryptography Reference
In-Depth Information
a given coset, we call this vector a coset leader . The coset leader need not be
unique, in which case we select one at random and call it the coset leader.
It is possible to form an arrayof vectors from
q arranged as the cosets of
F
C in the following fashion.
Slepian Standard Array
The following is an algorithm for setting up a q n k
q k matrix for a linear
×
[ n,k ]-code, called a Slepian standard array . (See [265].)
1. List the codewords of C beginning with the zero vector c 1 = 0 , as the first
row: c 1 , c 2 ,..., c k .
2. Choose anyone of the remaining q n
q k vectors of minimum weight, a 1 as
the first element of the second row, and let
a j = a 1 + c j for j =2 , 3 ,...,q k
be the remaining elements of the second row.
3. Select an element b 1 of minimum weight from the remaining q n
2 q k vectors
as the first element of the third row, and let
b j = b 1 + c j for j =2 , 3 ,...,q k
be the remaining elements of the third row.
4. Continue in the above fashion until all q n k rows are filled and everyvector
of
F
q appears exactlyonce in one of those rows.
Example 11.10 Let C be the binary [4 , 2] -code with generating matrix,
G = 1010
0111
.
Then n =4 , k =2 , q k =2 2 , q n =2 4 ,
C =
{
c 1 , c 2 , c 3 , c 4 }
=
{
(0 , 0) G, (0 , 1) G, (1 , 0) G, (1 , 1) G
}
=
{
0000 , 0111 , 1010 , 1101
}
.
This forms the first row of the Slepian array. The balance are given in the
q n k
×
q k =4
×
4 matrix,
0000 0111 1010 1101
0100 0011 1110 1001
0010 0101 1000 1111
0001 0110 1011 1100
,
wherein the first column consists of the coset leaders, and the rows represent the
elements in the cosets of C . ( Notice that in the third row, 1000 could also have
Search WWH ::




Custom Search