Information Technology Reference
In-Depth Information
A Lattice-Based Minimal Partial Realization
Algorithm
Li-Ping Wang
Center for Advanced Study, Tsinghua University,
Beijing 100084, People's Republic of China
wanglp@mail.tsinghua.edu.cn
Abstract.
In this paper we extend a minimal partial realization algo-
rithm for vector sequences to matrix sequences by means of a lattice basis
reduction algorithm in function fields. The different ways of transforming
a given basis into a reduced one lead to different partial realization algo-
rithms and so our technique provides a unified approach to the minimal
partial realization problem.
1
Introduction
As one of the most fundamental problem in linear systems theory, the minimal
partial realization problem has attracted considerable attention since the early
1960s, which brings a lot of minimal partial realization algorithms [1, 2, 3, 5, 9,
10, 12, 18]. In information theory the minimal partial realization problem is also
called the linear feedback register synthesis problem, which plays an important
role in the analysis and design of cryptosystems since especially in recent years
there has been an increasing interest in the study of multivariable cryptosystems
[4,7,11].
Let us recall the problem. Consider an infinite sequence
T
of
p
×
m
matri-
ces
over an arbitrary field IF, and so we regard as specifying the
transfer function in the linear system via
{
T
1
,T
2
,
···
,
}
T
(
z
)=
∞
T
i
z
−i
.
i
=1
For a positive integer
N
, the aim is to find an
m
m
nonsingular polynomial
matrix
M
N
(
z
) and a polynomial matrix
Y
N
(
z
) such that the first
N
terms of
the Laurent expansion of
Y
N
(
z
)
M
−
1
N
×
.There-
fore
Y
N
(
z
)
M
−
N
(
z
) will be called an
N
th (right) partial realization of
T
(
z
)or
T
. If the degree of det(
M
N
(
z
)) (also called the McMillan degree) is minimal,
Y
N
(
z
)
M
−
N
(
z
)isan
N
th (right) minimal partial realization of
T
(
z
)or
T
.
For the single-input-single-output (SISO) systems
p
=
m
=1,asweallknow,
there is an effective algorithm (Berlekamp-Massey algorithm) [16]. For the sys-
tems
m
=1and
p>
1, that is, vector sequences, there are several synthesis
algorithms [6, 8, 19, 20].
(
z
)areequalto
{
T
1
,T
2
,...,T
N
}
