Connections between linear systems and convolutional codes

The article reviews different definitions for a convolutional code which can be found in the literature. The algebraic differences between the definitions are worked out in detail. It is shown that bi-infinite support systems are dual to finite-support systems under Pontryagin duality. In this duality the dual of a controllable system is observable and vice versa. Uncontrollability can occur only if there are bi-infinite support trajectories in the behavior, so finite and half-infinite-support systems must be controllable. Unobservability can occur only if there are finite support trajectories in the behavior, so bi-infinite and half-infinite-support systems must be observable. It is shown that the different definitions for convolutional codes are equivalent if one restricts attention to controllable and observable codes.

Related papers:

title: A linear algebra approach to minimal convolutional encoders
abstract: The authors review the work of G.D. Forney, Jr., on the algebraic structure of convolutional encoders upon which some new results regarding minimal convolutional encoders rest. An example is given of a basic convolutional encoding matrix whose number of abstract states is minimal over all equivalent encoding matrices. However, this encoding matrix can be realized with a minimal number of memory elements neither in controller canonical form nor in observer canonical form. Thus, this encoding matrix is not minimal according to Forney's definition of a minimal encoder. To resolve this difficulty, the following three minimality criteria are introduced: minimal-basic encoding matrix, minimal encoding matrix, and minimal encoder. It is shown that all minimal-basic encoding matrices are minimal and that there exist minimal encoding matrices that are not minimal-basic. Several equivalent conditions are given for an encoding matrix to be minimal. It is proven that the constraint lengths of two equivalent minimal-basic encoding matrices are equal one by one up to a rearrangement. All results are proven using only elementary linear algebra.

title: Fundamentals of Convolutional Coding
abstract: From the Publisher: 
Convolutional codes, among the main error control codes, are routinely used in applications for mobile telephony, satellite communications, and voice-band modems. Written by two leading authorities in coding and information theory, this book brings you a clear and comprehensive discussion of the basic principles underlying convolutional coding. This book can be used as a textbook for graduate-level electrical engineering students. It will be of key interest to researchers and engineers of wireless and mobile communication, satellite communication, and data communication.

title: Error control coding - fundamentals and applications
abstract: 1. Coding for Reliable Digital Transmission and Storage. 2.  Linear Block Codes. 4. Important Linear Block Codes. 5. Cyclic Codes. 6. Binary BCH Codes. 7.  Trellises for Linear Block Codes. 10. Based Soft-Decision Decoding Algorithms for Linear Block Codes. 11. Convolutional Codes. 12. Trellis-Based Decoding Algorithms for Convolutional Codes. 13. Sequential and Threshold Decoding of Convolutional Codes. 14. Trellis-Based Soft-Decision Algorithms for Linear Block Codes. 15. Concatenated Coding, Code Decomposition ad Multistage Decoding. 16. Turbo Coding. 17. Low Density Parity Check Codes. 18. Trellis Coded Modulation. 19. Block Coded Modulation. 20. Burst-Error-Correcting Codes. 21. Automatic-Repeat-Request Strategies.

title: Convolutional Codes: An Algebraic Approach
abstract: From the Publisher: 
This monograph develops an algebraic approach that can be used to construct convolutional codes that are efficient in both classical and nonclassical situations. 
Coding theory, which is an offshoot of the field of probabilistic information theory, falls into two parts: block codes and convolutional codes. Block codes have lent themselves to easy and efficient construction by the use of certain algebraic tools, but rarely have those tools been of any use in constructing convolutional codes. These are generally constructed by methods of computer search. 
Convolutional Codes makes a significant contribution to the field of coding theory by presenting an original construction scheme for convolutional codes that makes them more powerful and easier to analyze than codes generated by the more usual method of computer search. The algebraic approach, Piret points out, is used not because of itself, but for its efficiency in constructing and analyzing convolutional codes having good and various error correcting capabilities. 
Philippe Piret is a member of the Philips Research Laboratory in Brussels.

title: Symbolic Dynamics and Convolutional Codes
abstract: Convolutional codes and their encoders are examined in a symbolic dynamics setting. Two previously unrelated areas of dynamics are used. The first is the Adler-Coppersmith-Hassner formulation of the finite memory channel coding problem. The second is the Kitchens-Schmidt use of algebraic duality to define and examine algebraic dynamical systems. Convolutional codes and their encoders are seen as lying in the intersection of these two areas. Codes, encoders, memory, distances and other invariants are examined in this framework.

title: An Introduction to Symbolic Dynamics and Coding
abstract: From the Publisher: 
Although it originated as a method to study general dynamical systems, symbolic dynamics is useful in coding for data storage and transmission as well as in linear algebra. Requiring only a undergraduate knowledge of linear algebra, this first general textbook includes over 500 exercises.

title: \constrained Systems and Coding for Recording Channels," to Appear as Book Chapter in Handbook for Coding Theory, Symbolic Dynamics to Coding, Automata and System Theory 8. Symbolic Dynamics and System Theory
abstract: Algorithms for sliding block codes | an application of symbolic dynamics to information theory,  x)j (?) (w; x)j 0;1) 2 B s. The external behavior of a state realization is the system (Z; W; B) where B = fw : (w; x) 2 B s for some xg. The state realization may be regarded as a presentation of its external behavior, with the elements of X as states. A state realization of a system is closely related to a presentation of a sooc shift; in fact, any labeled graph may be regarded as a state realization. A realization of an external behavior is minimal if (roughly speaking) no other realization of the same external behavior can be obtained by \merging" states 47]. Willems characterized the time-invariant systems with unique minimal realization, using the notion of futures F(xj (?) that we described in Section 4. We state this in Theorem 8.1 below. The past induced canonical realization of a time-invariant system (Z; W; B) is the state realization p = Likewise there is the notion of future induced canonical realization. Theorem 8.1 (Willems 47], and references therein). A time-invariant system has a unique minimal realization if and only if its future induced and past induced canonical realizations are equivalent in the sense that there is a bijection from states of one realization to states of the other that transforms one realization to the other. The unique minimal realization is the past induced canonical realization. Note how similar this result is to the characterization of irreducible sooc shifts with unique I-minimal presentation (Theorem 4.2 (1 , 2)). The Dictionary gives many concepts in system theory which are closely related to concepts in symbolic dynamics. For instance, an input-state-output system is deened to be a state realization (Z; U Y; X; B) subject to certain natural restrictions (see Deenition VI-1 in the Dictionary). Here, U; Y; and X play the role of input, output and state. Such systems are closely related to nite equivalences in symbolic dynamics and transducers in automata theory (as discussed in Section 7). Also, the notions of observability (Deenitions II-3 and II-4) are very similar to the idea of shift of nite type, and the notions of controllability (Deenitions II-7 and II-8) are very similar to the idea of irreducibility for sooc shifts; see the remarks in the Dictionary. We have given an introduction to …

title: From time series to linear system - Part I. Finite dimensional linear time invariant systems
abstract: In the first part of this paper the definition of a dynamical system as simply consisting of a family of time series will be developed. In this context the notions of linearity, time invariance, and finite dimensionality will be introduced. It will be shown that a given family of time series may be represented by a system of (AR) equations: Riw(t + l) + Rl − 1w(t + l − 1) + … + R0w(t) = 0, or, equivalently, by a finite dimensional linear time invariant system: x(t + 1) = Ax(t) + Bu(t); y(t) = Cx(t) + Du(t); w = (u, y), if and only if this family is linear, shift invariant and complete (or, as is equivalent, closed in the topology of pointwise convergence). This yields a very high level and elegant set of axioms which characterize these familiar objects. It is emphasized, however, that no a priori choice is made as to which components of w are inputs and which are outputs. Such a separation always exists in any specific linear time invariant model. Starting from these definitions, the structural indices of such systems are introduced and it is shown how an (AR) representation of a system having a given behaviour can be constructed. These results will be used in a modelling context in Part II of the paper.

title: Models for Dynamics
abstract: The purpose of this paper is to give a tutorial exposition of what we consider to be the basic mathematical concepts in the theory of dynamical systems.

title: Paradigms and puzzles in the theory of dynamical systems
abstract: A self-contained exposition is given of an approach to mathematical models, in particular, to the theory of dynamical systems. The basic ingredients form a triptych, with the behavior of a system in the center, and behavioral equations with latent variables as side panels. The author discusses a variety of representation and parametrization problems, in particular, questions related to input/output and state models. The proposed concept of a dynamical system leads to a new view of the notions of controllability and observability, and of the interconnection of systems, in particular, to what constitutes a feedback control law. The final issue addressed is that of system identification. It is argued that exact system identification leads to the question of computing the most powerful unfalsified model.

title: On 2D finite support convolutional codes: An algebraic approach
abstract: Two-dimensional (2D) finite codes are defined as families of compact support sequences indexed in Z × Z and taking values in Fn, F a Galois field. Several properties of encoders, decoders and syndrome decoders are discussed under different hypotheses on the code structure, and related to the injectivity and primeness of the corresponding polynomial matrices in two variables. Dual codes are finally introduced as families of parity checks on a given modular code, and related to the standard theory of 2D behaviors.

title: Multidimensional Systems with Finite Support Behaviors: Signal Structure, Generation, and Detection
abstract: The main features of finite multidimensional behaviors are introduced as properties of the trajectories supports and connected with the polynomial matrices adopted for their description. 
Observability and local detectability are shown to be equivalent to the kernel representation of a behavior via some parity check matrix HT. The main properties of locally undetectable behaviors as well as their connections with the notion of constrained variables are investigated, and a general representation result for finite support behaviors is derived. 
The input-output representation via generator matrices is finally discussed, and some connections between matrix primeness and the constraints every trajectory imposes on the support of the corresponding input are analyzed.

title: On behaviors and convolutional codes
abstract: It is well known that a convolutional code is essentially a linear system defined over a finite field. In this paper we elaborate on this connection. We define a convolutional code as the dual of a complete linear behavior in the sense of Willems (1979). Using ideas from systems theory, we describe a set of generalized first-order descriptions for convolutional codes. As an application of these ideas, we present a new algebraic construction for convolutional codes.

title: Automata, languages, and machines. A
abstract: The 80 revised papers presented together with two keynote contributions and four invited papers were carefully reviewed and sele... The study of formal languages and automata has proved to be a source of much interest and discussion amongst mathematicians in recent times. This book, written by Professor Ian Chiswell, attempts to provide a comprehensive textbook for undergraduate and postgraduate mathematicians with an interest i...

title: Minimal Syndrome Formers for Group Codes
abstract: Given a controllable group code, it has been shown by Forney (1970, 1973), Trott, and Loeliger (1994) that it is possible to construct a canonical encoder whose state space coincides with the canonical state space of the code, that is the essential element determining the minimal trellis of the code. The construction of such an encoder is based on the concept of controllability granule. In this paper the construction of a syndrome former for an observable group code is proposed. This syndrome former exhibits analogous properties of the above mentioned canonical encoder and, in particular, its state space coincides with the canonical state space of the code. The proposed construction is based on the concept of observability granule, introduced by Forney and Trott (1993), which dualizes the concept of controllability granule. Similarly to what happens for the encoders, each observability granule produces a map and all these maps together provide the syndrome former. The main difference is that here, to achieve the right state-space dimension, the automata associated with these maps do not evolve independently from each other, but are coupled according to a triangular structure.

title: The dynamics of group codes: Dual abelian group codes and systems
abstract: Fundamental results concerning the dynamics of abelian group codes (behaviors) and their duals are developed. Duals of sequence spaces over locally compact abelian (LCA) groups may be defined via Pontryagin duality; dual group codes are orthogonal subgroups of dual sequence spaces. The dual of a complete code or system is finite, and the dual of a Laurent code or system is (anti-)Laurent. If C and C/sup /spl perp// are dual codes, then the state spaces of C act as the character groups of the state spaces of C/sup /spl perp//. The controllability properties of C are the observability properties of C/sup /spl perp//. In particular, C is (strongly) controllable if and only if C/sup /spl perp// is (strongly) observable, and the controller memory of C is the observer memory of C/sup /spl perp//. The controller granules of C act as the character groups of the observer granules of C/sup /spl perp//. Examples of minimal observer-form encoder and syndrome-former constructions are given. Finally, every observer granule of C is an "end-around" controller granule of C.

title: Group Codes and Behaviors
abstract: The close connections between convolutional coding theory and linear system theory are well known. A convolutional encoder is simply a discrete-time linear time-invariant (LTI) system over a finite field, always finite-dimensional, in general multivariable. These connections were exploited in the 1970’s to develop an algebraic structure theory of convolutional codes [5], the key elements of which turned out later to be useful in linear system theory [6, 14].

title: Observability and extendability of finite support nD behaviors
abstract: In this contribution the local structure of finite support nD signals is analysed according to the behavioral approach. Observability and local detectability are introduced, and characterized in terms of polynomial matrix descriptions. The problem of extending into a legal trajectory a set of data that satisfies the parity checks on a suitable subset of Z/sup n/ is then considered and necessary and sufficient conditions for its solution provided. The main properties of locally undetectable behaviors and their connections with the notion of constrained variables are investigated. A general representation result for finite support behaviors is finally discussed.

title: Codes, automata, and continuous systems: Explicit interconnections
abstract: Close relationships are established between convolutional codes and zero-state automata and between cyclic codes and zero-input automata. Furthermore, techniques of automata theory and continuous system theory are used to elaborate on the coding problem; and approaches from coding and automata are used to establish and interpret typical structural conditions in continuous systems. The investigation incorporates basic coding concepts into the currently emerging common basis for automata and continuous systems, and it gives explicit examples of the resulting benefits accruing to each of these areas from the others.

title: Invertibility of linear time-invariant dynamical systems
abstract: The question of inverting linear time-invariant dynamical systems has been of interest to control engineers for many years. An example of the nonstate-variable approach and application of this concept is the very well known work of Bode and Shannon in 1950. With the integration of state-variable descriptions and techniques into systems problems, the question has recently reappeared in a somewhat more complicated guise. Basically, the problem of inverting such dynamical systems is to determine the existence of the inverse, its properties, and its construction in terms of the matrices which characterize its state description. The first general study of existence appears to be due indirectly to Brockett and Mesarovic in 1965, and the first general construction seems to have been proposed by Youla and Dorato in 1966. Neither of these works was intended to develop a substantial insight into the properties of the inverse. The present work introduces the concept of the inherent integration associated with a dynamical system, i.e., the number of integrations which no inverse dynamical system can remove unless ideal differentiators are introduced. The existence of the inverse is discussed in terms of a determination of the inherent integration, and the construction which realizes this minimum number of integrations is given. The existence tests introduced are at worst one-half as complex as that of Brockett and Mesarovic and the construction offers a substantial improvement in conceptual simplicity over that of Youla and Dorato. The results are made possible by recognizing an essential equivalence with an associated problem in real sequential circuits and appear to be applicable to related problems in sensitivity, estimation, and game theory.

title: Structural analysis of convolutional codes via dual codes
abstract: A linear correspondence is developed between the states of a rate- k/n convolutional encoder G and the states of a corresponding syndrome former H^T , where H is an encoder of the code dual to the code generated by G . This correspondence is used to find an expression for the number of all-zero paths of length \tau in the code trellis; the answer depends only on the constraint lengths of the dual code. A partial answer to the resynchronization problem also falls out of this development.

title: Convolutional codes I: Algebraic structure
abstract: A convolutional encoder is defined as any constant linear sequential circuit. The associated code is the set of all output sequences resulting from any set of input sequences beginning at any time. Encoders are called equivalent if they generate the same code. The invariant factor theorem is used to determine when a convolutional encoder has a feedback-free inverse, and the minimum delay of any inverse. All encoders are shown to be equivalent to minimal encoders, which are feedback-free encoders with feedback-free delay-free inverses, and which can be realized in the conventional manner with as few memory elements as any equivalent encoder, Minimal encoders are shown to be immune to catastrophic error propagation and, in fact, to lead in a certain sense to the shortest decoded error sequences possible per error event. In two appendices, we introduce dual codes and syndromes, and show that a minimal encoder for a dual code has exactly the complexity of the original encoder; we show that systematic encoders with feedback form a canonical class, and compare this class to the minimal class.

title: Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems
abstract: A minimal basis of a vector space V of n-tuples of rational functions is defined as a polynomial basis such that the sum of the degrees of the basis n-tuples is minimum. Conditions for a matrix G to represent a minimal basis are derived. By imposing additional conditions on G we arrive at a minimal basis for V that is unique. We show how minimal bases can be used to factor a transfer function matrix G in the form $G = ND^{ - 1} $, where N and D are polynomial matrices that display the controllability indices of G and its controller canonical realization. Transfer function matrices G solving equations of the form $PG = Q$ are also obtained by this method; applications to the problem of finding minimal order inverse systems are given. Previous applications to convolutional coding theory are noted. This range of applications suggests that minimal basis ideas will be useful throughout the theory of multivariable linear systems. A restatement of these ideas in the language of valuation theory is given in an Ap...

title: Subspaces of GF(q)^w and Convolutional Codes
abstract: The present paper is a self-contained treatment of subspaces of the space GF(q)ω of all semi-infinite strings over GF(q). Some necessary and sufficient conditions which characterize those subspaces of GF(q)ω are derived which are convolutional codes, and the classes of subspaces defined by one or more of them are investigated. Moreover structural parameters of convolutional codes such as block length, rate, delay, and constraint length are considered as parameters of subspaces rather than parameters of an encoding device. As a conclusion it is obtained that for error-control purposes none of the investigated superclasses of the class of convolutional codes is better suited than the class of convolutional codes itself.

title: Solution modules and system equivalence
abstract: In this paper we consider a system as a relation between input, internal variables and output. This relation is given by the solution space of the system's equations. For time invariant linear systems in differential operator representation the solution space carries a K[s]-module structure defined by the ordinary differential operator. This algebraic structure is exploited systematically to develop a self-contained theory of strict system equivalence in time domain. The module of free motions is considered as space of initial conditions. An algebraic characterization of systems having the same solution space is presented. System homomorphisms are defined as special K[s] homomorphisms between the solution modules. Two systems are called system-equivalent, if there exists a system-isomorphism between their solution spaces. It turns out that, this concept coincides with Rosenbrock's concept of strict. system equivalence. It. is shown that further concepts and results of linear system theory (constr...

title: Generalized Hermite Matrices and Complete Invariants of Strict System Equivalence
abstract: A complete list of invariants for reachable system matrices \[ \Sigma (s) = \left[ {\begin{array}{*{20}c} {P(s)} & { - Q(s)} \\ {V(s)} & {W(s)} \\ \end{array} } \right] \]with respect to strict system equivalence (s.s.e.) is determined by polynomial methods. The polynomial input-output pairs $(u,y)$ for which there exists a polynomial vector z such that $Pz = Qu$ and $y = Vz + Wu$ form a $K[s]$-module $\mu (\Sigma )$. It is shown that the unique basis matrix of $\mu (\Sigma )$ in Hermite form yields a complete set of discrete (“Hermite indices”) (resp. continuous) invariants of s.s.e. The Hermite invariants are characterized in state space terms, and a realization of $\Sigma (s)$ in Hermite canonical form is presented. Nice orders and generalized Hermite forms are introduced in order to develop a framework that encompasses Hermite invariants and Kronecker invariants. Hermite’s theorem is generalized to these matrices. Finally, nice orders are used to single out unique representatives among all minimal bas...

title: Multidimensional constant linear systems
abstract: A continuous resp. discrete r-dimensional (r≥1) system is the solution space of a system of linear partial differential resp. difference equations with constant coefficients for a vector of functions or distributions in r variables resp. of r-fold indexed sequences. Although such linear systems, both multidimensional and multivariable, have been used and studied in analysis and algebra for a long time, for instance by Ehrenpreis et al. thirty years ago, these systems have only recently been recognized as objects of special significance for system theory and for technical applications. Their introduction in this context in the discrete one-dimensional (r=1) case is due to J. C. Willems. The main duality theorem of this paper establishes a categorical duality between these multidimensional systems and finitely generated modules over the polynomial algebra in r indeterminates by making use of deep results in the areas of partial differential equations, several complex variables and algebra. This duality theorem makes many notions and theorems from algebra available for system theoretic considerations. This strategy is pursued here in several directions and is similar to the use of polynomial algebra in the standard one-dimensional theory, but mathematically more difficult. The following subjects are treated: input-output structures of systems and their transfer matrix, signal flow spaces and graphs of systems and block diagrams, transfer equivalence and (minimal) realizations, controllability and observability, rank singularities and their connection with the integral respresentation theorem, invertible systems, the constructive solution of the Cauchy problem and convolutional transfer operators for discrete systems. Several constructions on the basis of the Gröbner basis algorithms are executed. The connections with other approaches to multidimensional systems are established as far as possible (to the author).

title: Controllability, observability, and duality in behavioral group systems
abstract: Fundamental results concerning abelian group systems and their duals are developed. Duals of sequence spaces over locally compact abelian groups are defined via Pontryagin duality; dual group systems are orthogonal subgroups of dual sequence spaces. If C and C/sup /spl perp// are dual systems then the state spaces of C are isomorphic to the character groups of the state spaces of C/sup /spl perp//. Further, the controllability properties of C are equal to the observability properties of C/sup /spl perp//.

title: Convolutional codes over groups
abstract: The basic algebraic structure theory of convolutional codes and their trellises is developed simultaneously for codes over groups, rings, and fields. The first part, which covers fundamental notions such as minimality and observability, is semi-tutorial in that most definitions are already standard (within the modern behavioral theory), as are some of the formally stated results. However, some of the pivotal results-emphasizing the role of observability as the basic well-behavedness condition for codes-are new, and several previous results are given simplified proofs. The usefulness of the behavioral approach even for convolutional codes over fields is demonstrated by a new minimality test for encoders as well as by the straightforward derivation of some known minimality criteria for generator matrices from the basic minimality criteria for group trellises. The second part of the paper deals with issues that are specific to codes over rings and groups. The main result is a concise characterization-the first such-of those groups that can appear as the branch group of any group trellis. It is further shown how such groups are "presented" by shift registers. A new large class of noncommutative convolutional codes is also given.

title: Algebraic system theory: an analyst's point of view
abstract: A systematic development of the realization theory of finite dimensional constant linear systems is presented which synthesizes the various currently available approaches. Based on representation theorems for submodules and quotient modules of spaces of polynomial matrices and vectors, this paper combines the abstract algebraic ideas centering around module theory, the use of coprime factorizations of rational transfer functions and state space equations into a unified theory.

title: A Polynomial Approach to Linear Algebra
abstract: Preliminaries.- Linear Spaces.- Determinants.- Linear Transformations.- The Shift Operator.- Structure Theory of Linear Transformations.- Inner Product Spaces.- Quadratic Forms.- Stability.- Elements of System Theory.- Hankel Norm Approximation.

title: Linear Feedback—An Algebraic Approach
abstract: The algebraic theory of linear input–output maps is reexamined with the objective of accomodating the concept of (state) feedback in this theory. The concepts of extended and restricted linear i/o maps (and linear i/s maps) are introduced and investigated. It is shown how “fraction representations” of transfer matrices arise naturally in this new theoretical framework.Conditions are given for when the change caused to a linear input-output map by an (open loop) “cascade compensator” can also be accomplished by utilization of (closed loop) state feedback. In particular, it is shown that the change caused to a linear input-output map by cascading (composing) it with an input space isomorphism, can also be effected by feedback, provided the input space isomorphism in “bicausal”, i.e. it does not change the causal structure of the input-output map. Further detailed characterizations of feedback are also given especially in connection with the newly introduced concepts of degree chain and degree list.

title: First order representations of linear systems
abstract: Part 1 Rational matrices and rational vector spaces: algebraic preliminaries Euclidean domains of rational functions pole/zero structure of a rational matrix Wiener-Hopf structure of a rational matrix minimal basis of a rational vector space preliminary results for matrix pencils. Part 2 Representations of linear time-invariant systems: dynamical systems AR representations ARMA representations first-order representations systems with split external variables. Part 3 Minimality and transformation groups: minimality of a P representation minimality of a D representation minimality of a DZ representation minimality of a DP representation transformation groups. Part 4 Realization in minimal first-order form: realization in pencil form - the abstract procedure the pencil realization in terms of a discrete-time behaviour choosing bases connections with the Fuhrmann realization. Part 5 Structural invariants: observability indices controllability indices the input-output structure.

title: Realization of autoregressive equations in pencil and descriptor form
abstract: A linear system described by autoregressive equations with a given input/output structure cannot be transformed to standard state-space form if the implied input/output relation is nonproper. Instead, a realization in descriptor form must be used. In this paper, it is shown how to obtain minimal descriptor realizations from autoregressive equations without separating finite and infinite frequencies, and without going through a reduction process. External equivalence is used, so that even situations in which there is no transfer matrix can be considered. The approach is based on the so-called pencil representation of linear systems, and it is shown that there is a natural realization of autoregressive equations in pencil form. In this way, the link between the realization theories of Willems and Fuhrmann can also be clarified.

title: Realization by inspection
abstract: We investigate which first-order representations can be obtained from high-order representations of linear systems "by inspection", that is, just by rearrangement of the data. Under quite weak conditions it is possible to obtain minimal realizations in the so-called pencil form; under stronger conditions one can obtain minimal realizations in standard state-space form by inspection. The development is based on a reformulation of the realization problem as a problem of finding a complete set of basis vectors for the nullspace of a given constant matrix. Since no numerical computation is needed, the realization method in particular is suitable for situations in which some of the coefficients are symbolic rather than numerical.

title: Polynomial weights and code constructions
abstract: For any nonzero element c of a general finite field GF(q) , it is shown that the polynomials (x - c)^i, i = 0,1,2,\cdots , have the "weight-retaining" property that any linear combination of these polynomials with coefficients in GF(q) has Hamming weight at least as great as that of the minimum degree polynomial included. This fundamental property is then used as the key to a variety of code constructions including 1) a simplified derivation of the binary Reed-Muller codes and, for any prime p greater than 2, a new extensive class of p -ary "Reed-Muller codes," 2) a new class of "repeated-root" cyclic codes that are subcodes of the binary Reed-Muller codes and can be very simply instrumented, 3) a new class of constacyclic codes that are subcodes of the p -ary "Reed-Muller codes," 4) two new classes of binary convolutional codes with large "free distance" derived from known binary cyclic codes, 5) two new classes of long constraint length binary convolutional codes derived from 2^r -ary Reed-Solomon codes, and 6) a new class of q -ary "repeated-root" constacyclic codes with an algebraic decoding algorithm.

title: Duality in polynomial models with some applications to geometric control theory : (preprint)
abstract: Duality is studied in the context of polynomial models for linear systems. The output injection group, the dual of the feedback group, is studied and a polynomial characterization of ( C, A )-invariant subspaces as well as of the maximal reachability subspaces contained in ker C is given.

title: A smooth compactification of the space of transfer functions with fixed McMillan degree
abstract: It is a classical result of Clark that the space of all proper or strictly properp ×m transfer functions of a fixed McMillan degreed has, in a natural way, the structure of a noncompact, smooth manifold. There is a natural embedding of this space into the set of allp × (m+p) autoregressive systems of degree at mostd. Extending the topology in a natural way we will show that this enlarged topological space is compact. Finally we describe a homogenization process which produces a smooth compactification.

title: A general realization theory for higher-order linear differential equations
abstract: In this note we show that the geometric quotient, under a natural group action, of the generalized state space systems recently considered by Schumacher, Kuijper and Geerts is algebraically isomorphic to the space of a homogeneous autoregressive system. This result essentially follows from work of Stromme published earlier in the algebraic geometry literature. In particular, these generalized state space systems represent a realization of the space of homogeneous autoregressive systems.

title: Maximum Distance Separable Convolutional Codes
abstract: A maximum distance separable (MDS) block code is a linear code whose distance is maximal among all linear block codes of rate k/n. It is well known that MDS block codes do exist if the field size is more than n. In this paper we generalize this concept to the class of convolutional codes of a fixed rate k/n and a fixed code degree δ. In order to achieve this result we will introduce a natural upper bound for the free distance generalizing the Singleton bound. The main result of the paper shows that this upper bound can be achieved in all cases if one allows sufficiently many field elements.