Information Technology Reference
In-Depth Information
4
A Special Realization Algorithm
In Algorithm 2.1, if
m
= 1 there is a unique vector (
a
1
,
···
,a
n
) in reduction
step such that
j
=1
a
j
θ
(
ω
j
)=
0
n
. However in general there are many choices
about the vector (
a
1
,
,a
n
) and so we give a special choice such that the total
number of reduction steps is as small as possible.
First we introduce length parameters, that is,
N
i
=
v
(
η
(
ω
i
))
···
−
v
(
ω
i
)for1
≤
i
≤
n
. Hence we have
δ
j
(
η
(
ω
i
)
,T
)=
0
p
for
j
=1
,...,N
i
−
1, but
δ
N
i
(
η
(
ω
i
)
,T
)
=
0
p
.Inparticular,
N
i
=
N
+1 if and only if
θ
(
ω
i
)
=
0
m
. According to these
parameters, combine certain reduction steps into a small while-loop and let
r
denote the current number of such small while-loops. It will be showed that at
each
r
, the recursively updated basis
ω
1
,...,ω
n
satisfies the following conditions.
1.
θ
(
ω
1
)
,...,θ
(
ω
p
) are linearly independent over IF and
θ
(
ω
j
)=
0
m
for
j
=
1
,...,p
.
2.
θ
(
η
(
ω
p
+1
))
,...,θ
(
η
(
ω
p
+
m
)) are linearly independent over IF.
3. For each
s
,
p
+1
≤
s
≤
n
,
N
s
>N
j
for
j
=1
,...,p
.
Put
r
←
0 when the same initialization is given as Algorithm 2.1 and at this
time the above conditions are trivially satisfied.
In the above situation one proceeds as follows. If
θ
(
ω
p
+
i
)
=
0
m
for
i
=
1
,...,m
, the basis becomes normal just by rearranging the order of the ba-
sis elements since the basis satisfies Condition 1, 2 and 3, and so let
M
N
(
z
)=
(
η
(
ω
p
+
i
))
1
≤i≤m
and pol(
T
(
z
)
M
N
(
z
))
M
−
N
(
z
)isan
N
th minimal partial realiza-
tion of
T
. Therefore the algorithm terminates.
Otherwise, set
I
=
{
p
+1
≤
s
≤
n
:
θ
(
ω
s
)=
0
m
and
N
s
is minimum
}
.
Choose a number
s
∈
I
and do the following reduction step. Since
θ
(
ω
s
)=
0
m
and so there exists a unique vector (
a
1
,...,a
p
) such that
θ
(
ω
s
)=
j
=1
a
j
θ
(
ω
j
).
Let
h
be an integer such that
v
(
ω
h
)=max
{
v
(
ω
j
): 1
≤
j
≤
p, a
i
=0
}
. We need
to consider two cases.
Case 1. Suppose
v
(
ω
s
)
≥
v
(
ω
h
). In this case we let
p
a
j
z
−v
(
ω
j
)+
v
(
ω
s
)
ω
j
.
ξ
=
ω
s
−
(6)
j
=1
−
j
=1
a
j
z
−v
(
ω
j
)+
v
(
ω
s
)
η
(
ω
j
). From (6) we have
v
(
ξ
)
<
v
(
ω
s
). Then
ω
s
is replaced by
ξ
and the other
ω
j
are unchanged.
Case 2. Suppose
v
(
ω
s
)
<v
(
ω
h
). Then we let
Clearly,
η
(
ξ
)=
η
(
ω
s
)
p
ξ
=
z
−v
(
ω
s
)+
v
(
ω
h
)
ω
s
−
a
j
z
−v
(
ω
j
)+
v
(
ω
h
)
ω
j
.
(7)
j
=1
−
j
=1
a
j
z
−v
(
ω
j
)+
v
(
ω
h
)
η
(
ω
j
). From
(7), we have
v
(
ξ
)
<v
(
ω
h
). Then we replace
ω
h
by
ω
s
,
ω
s
by
ξ
, and leave the
other
ω
j
unchanged.
Similarly, we have
η
(
ξ
)=
z
−v
(
ω
s
)+
v
(
ω
h
)
η
(
ω
s
)
