Algorithmic aspects of algebraic system theory
Algorithmic aspects of algebraic system theory
复制标题
代数系统论的算法方面
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
E. Zerz
中科院分区：
文献类型：
--
作者：
Kristina Schindelar;E. Zerz
设置本节，我们必须基于可控性与许多重要系统类别的参数范围相吻合的事实，当时我们将其称为线性抽象系统控制器。 l∈Dq×l，使得b = {ω∈A|∃∈A：ω= l•`}。拟议的解释。当且仅当im（·r）= ker（·l）时，对B的基本原理进行了直接表征通过假设，D是一个域。是，DX ∈IM（·r）。有限生成的Noetherian域上的无扭转模块可以嵌入最终生成的自由模块中。 3.R是左边Syzygy矩阵。 →m，x 7→[x]。依靠确定D的结构属性，可以将B分解为1.4节中的自主子系统。 ω= [ωt1，ωt2] t被相应地分配，即b = {[ω1，ω2]∈A12| r1•ω1 +r2•ω2= 0}。 ω2只有ω1由ω2唯一确定，并且[ω1，ωt2] t满足系统定律。 ω1= 0} = {0} 。环上的一维系统19 1.3对环的行为方法已成功地应用于该框架问题中的某些领域。 ，有效地处理了有关卷积法规和最小格子[FIT95]的灾难性问题[KUI01，KP04，此外，KVDHO01，KW97，RSY96。 kppr06]，一个相关的主题是环上的卷积代码，这是线性的，在基础环上进行的时间不变的行为。结构。 ，KP08B，KWP05]。 m。与戒指的系统相关，我们假设素数p的信号设置a = {ω：n→zpr}，我们认为独家线性和s-invariant系统。当s•ω（t）=ω（t+ 1）。尺寸案例）。圈ZM是准杂种，即，从代数的角度来看，noetherian和nodementive。 D不再是PID。 B1，B2通过R1∈Dg1×Q和R2∈Dg2×Q给出B1 b2 b2⇔X∈Dg2×G1：R2 = XR1，但与两个临界场相反，相当于两个。抽象线性系统B1，B2不等于是否存在满足等价右侧的单模型矩阵（1.7）的要求（1.7）。正如下面指出的完整排名表示。 S 3（S -1）]和R2 = [S + S 3]
setting of this section, we have to use a more algebraic definition based on the fact that controllability coincides with parametrizability for many important system classes. We call a linear abstract system controllable if and only if it admits an image representation, that is, there exists L ∈ Dq×l such that B = {ω ∈ A | ∃` ∈ A : ω = L • `}. In Section 1.3, 1.4 we will point out for particular signal classes how this definition is linked with the proposed interpretation. The fundamental principle offers a direct characterization of controllability: B is controllable if and only if im(·R) = ker(·L) for some L. (1.6) Then one calls R a left syzygy matrix. Recall that by assumption, D is a domain. Then controllability implies that the associated system module is torsion-free. This can be easily checked. Let 0 6= d ∈ D and x ∈ D1×q such that d[x] = 0, that is, dx ∈ im(·R). Then by (1.6) dxL = 0 and since D is a domain, x ∈ ker(·L) = im(·R), that is, [x] = 0. One can show that every finitely generated torsion-free module over a Noetherian domain can be embedded into a finitely generated free module. This permits the following characterization. Theorem 1.2.9 The following claims are equivalent: 1. B is controllable. 2. M is torsion-free. 3. R is a left syzygy matrix. Proof: Referring to the previous observations, it is sufficient to show that the second item yields the third. Let M be torsion-free. Then there exists an embedding ι : M→D1×l. Define π : D1×q →M, x 7→ [x]. Then D1×g ·R −→ D1×q ι◦π −→ D1×l is exact. Defining L as the matrix associated to ι ◦ π shows that R is a left syzygy matrix. Relying on certain structure properties of D, it is possible to decompose B into a controllable and autonomous subsystem. In Section 1.4, we point out how to obtain such a decomposition for one-dimensional time-varying systems. Observability Suppose R = [R1, R2] and ω = [ω T 1 , ω T 2 ] T to be partitioned accordingly, that is, B = {[ω 1 , ω 2 ] ∈ A12 | R1 • ω1 +R2 • ω2 = 0}. Then ω1 is called observable from ω2 if and only if ω1 is uniquely determined by ω2 and the fact that [ω 1 , ω T 2 ] T satisfies the system law. That is, ω1 is observable from ω2 if and only if B1 := {ω1 ∈ A1 | R1 • ω1 = 0} = {0}. Due Theorem 1.2.3, this is equivalent to D1R1 = B⊥ 1 = D1×q1 . Summing up, we obtain that ω1 is observable from ω2 if and only if R1 is left invertible. 1.3. ONE-DIMENSIONAL SYSTEMS OVER RINGS 19 1.3 One-dimensional systems over rings The behavioral approach to system theory has been successfully applied to some areas in communication. In this framework problems like the decoding of Reed-Solomon block codes over fields [BF01, LO08], catastrophicity issues on convolutional codes over fields, and the construction of minimal trellis [Fit95] are handled effectively [Kui01, KP04, KvDHO01, KW97, RSY96]. Moreover, interpolation questions can be tackled with the help of the so-called most powerful unfalsified model, see Section 1.6. The interest in systems over rings stems mainly from the applications in communication theory. As outlined in [KPPR06], one relevant topic is convolutional codes over rings, which are linear, time-invariant behaviors over the underlying ring. Here the ring structure is better suited for phase modulation than the field structure. Further [HKC94] stresses the importance of codes over Z4. The impact of these lies in the connection to certain efficient nonlinear binary codes under the Gray map. Beside, the communications literature offers many results for sequences over finite rings [BHK92, US00, KP08b, KWP05]. Thus there are several aspects that motivate to extend the well established theory of one-dimensional systems over fields to those over the rings Zm = Z/mZ for a integer m. In connection to systems over rings we assume the signal set A := {ω : N→ Zpr} for a prime number p and we consider exclusively linear and s-invariant systems. Recall that s denotes the backward shift, acting on A as s • ω(t) = ω(t+ 1). Let D denote Zpr [s]. In [LLO04] it is shown that the D-module A is an injective cogenerator (in fact [LLO04] even considers the multi-dimensional case). This result relies on the fact that the rings Zm are Quasi-Frobenius, that is, Noetherian and self-injective. Kernel representations From the algebraic point of view, the main difficulties that arise going from the field case to the ring case is the existence of zero-divisors and the fact that D is no longer a PID. The injective cogenerator property permits to relate the kernel representations of related linear abstract systems. Recall that due to Theorem 1.2.3, we obtain for two linear abstract systems B1,B2 given via R1 ∈ Dg1×q and R2 ∈ Dg2×q that B1 ⊆ B2 ⇔ ∃X ∈ Dg2×g1 : R2 = XR1. (1.7) But in contrast to the case of a coefficient field, the equality of two abstract linear systems B1,B2 is not equivalent to the requirement that there exists a unimodular matrixX satisfying the right hand side of equivalence (1.7). This is due to the fact that behaviors over rings (rather than fields) need not have full row rank representations, as will be pointed out below. Let us emphasize this effect by [KPPR06, Example 3.1]. Suppose p = 3, r = 2 and B1,B2 to be given via the kernel representation matrices R1 = [ s + s 3(s− 1) ] and R2 = [ s + s 3 ] . 20 CHAPTER