On locally invertible encoders and multidimensional convolutional codes

by 1976- Lobo, Ruben Gerald

LOBO, RUBEN GERALD. On Locally Invertible Encoders and Multidimensional Convolutional Codes. (Under the direction of Dr. Mladen A. Vouk and Dr. Donald L. Bitzer). Multidimensional (m-D) convolutional codes generalize the well known notion of a 1-D convolutional code defined over a univariate polynomial ring with coefficients in a finite field to multivariate polynomial rings. The more complicated structure of a multivariate polynomial ring when compared to a univariate one, however, makes the generalization nontrivial. While 1-D convolutional codes have been thoroughly understood and have wide applications in communication systems, the theory of m-D convolutional codes is still in its infancy, and these codes lack unified notation and practical implementation. This dissertation develops a sequence space approach for realizing m-D convolutional codes. While most of the existing research is focused on algebraic aspects, fundamental issues regarding practical implementation that are well developed and fairly straightforward in the 1-D case have remained undefined for m-D convolutional codes. In this dissertation we address some of these issues. We define a new notion of sequence space ordering and show that certain multivariate polynomial matrices which we call as locally invertible encoders, when transformed to the sequence space domain, have an invertible subsequence map between their input and output sequences. This subsequence map has a well defined structure that allows for the explicit construction of locally invertible encoders by performing elementary operations on the ground field without the use of any polynomial operations. We use the invertible subsequence map to introduce a novel method to encode and invert multidimensional sequences. We show that locally invertible encoders have good structural properties which make them a natural choice to generate multidimensional convolutional codes. On Locally Invertible Encoders and Multidimensional Convolutional Codes by Ruben Gerald Lobo A dissertation submitted to the Graduate Faculty of North Carolina State University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Computer Engineering Raleigh 2006 Approved By: Dr. Ernest Stitzinger Dr. Brian L. Hughes Dr. Alexandra Duel-Hallen Dr. Mladen A. Vouk Co-chair of Advisory Committee Dr. Donald L. Bitzer Co-chair of Advisory Committee ii This dissertation and the work that went into it is lovingly dedicated to my mother, Severine Lobo, who has sacrificed so much and worked so hard to give me a better life. iii Biography Ruben Lobo was born in Mangalore, India on May 24, 1976. He attended St. Aloysius College in his hometown where he received his elementary and secondary education. Ruben holds a Bachelor of Engineering degree in Electronics and Communication, awarded in 1998, from the Manipal Institute of Technology, Manipal, India. His interest in computer networks led him to North Carolina State University in August 2000, where he obtained his Master of Science degree in Computer Engineering in May 2002. His graduate advisor Dr. Mladen Vouk introduced him to Dr. Donald Bitzer who inspired him to pursue a doctoral degree. He is currently a doctoral candidate in the Department of Electrical and Computer Engineering, North Carolina State University. He has undertaken his doctoral research under the guidance of Dr. Mladen Vouk and Dr. Donald Bitzer. iv