Information Technology Reference
In-Depth Information
The n-th element of the sequence
{
v
n
}
is defined as:
v
n
=
g
0
a
n
⊕
g
1
a
n
+1
⊕
g
2
a
n
+2
⊕
...
⊕
g
L−
1
a
n
+
L−
1
,
(2)
are reduced mod
2
L
−
where the sub-indexes of the sequence
{
a
n
}
1
and the
symbol
⊕
represents the XOR logic operation. For
n
≥
0
the decimation rule is
very simple:
1. If
a
n
=1
,then
v
n
is output.
2. If
a
n
=0
,then
v
n
is discarded and there is no output bit.
In this way, a balanced output sequence
b
0
b
1
b
2
...
denoted by
}
is generated. Such a sequence is called the generalized self-shrinking sequence
associated with
G
.
{
b
n
}
or
{
b
(
G
)
Let us see a simple example. For the 4-degree
m
-sequence
{
a
n
}
=
{
011110101
whose characteristic polynomial is
x
4
+
x
3
+ 1, we get 16 generalized
self-shrinking sequences based on
100100
}
{
a
n
}
:
0.
G
= (0000)
,
{
b
(
G
)
}
= 00000000
∼
1.
G
= (1000)
,
{
b
(
G
)
}
= 11111111
∼
G
= (0100)
,
{
b
(
G
)
}
∼
2.
= 11100100
G
= (0010)
,
{
b
(
G
)
}
∼
3.
= 11011000
G
= (0001)
,
{
b
(
G
)
}
∼
4.
= 10101010
5.
G
= (1001)
,
{
b
(
G
)
}
= 01010101
∼
6.
G
= (1101)
, {b
(
G
)
}
= 10110001
∼
7.
G
= (1111)
, {b
(
G
)
}
= 01101001
∼
8.
G
= (1110)
,
{
b
(
G
)
}
= 11000011
∼
9.
G
= (0111)
,
{
b
(
G
)
}
= 10010110
∼
10.
G
= (1010)
,
{
b
(
G
)
}
= 00100111
∼
11.
G
= (0101)
,
{
b
(
G
)
}
= 01001110
∼
12.
G
= (1101)
,
{
b
(
G
)
}
= 10110001
∼
13.
G
= (1100)
,
{
b
(
G
)
}
= 00011011
∼
14.
G
= (0110)
,
{
b
(
G
)
}
= 00111100
∼
15.
G
= (0011)
,
{
b
(
G
)
}
= 01110010
∼
Notice that the generated sequences are not 16 different sequences as some
of them are shifted versions of the others.
3
Cryptographic Sequences as Solutions of Linear
Difference Equations
In this section, structural properties of the previous sequences will be studied in
terms of solutions of linear difference equations.
In this work, the following homogeneous linear difference equations with bi-
nary coecients will be considered:
r
(
E
r
⊕
c
j
E
r−j
)
z
n
=0
,
n
≥
0
(3)
j
=1
Search WWH ::
Custom Search