Fault diagnosis and diagnosability in multiprocessor systems

Abstract

The use of error-control coding in information transmission systems and data storage systems is increasing rapidly. The primary aim of coding theorists has been to find “good codes” with “reasonably simple” decoding methods. Towards this end, classes of codes like linear codes, cyclic codes, etc., have been investigated, where the “structure” of the code has been used to simplify decoding algorithms and to find good codes. An alternative approach has been to find the automorphism group of a good error-correcting code. Renewed interest in codes over rings was due to Hammons et al. [46], who found that certain optimal nonlinear binary codes are binary images of certain linear codes over rings under the Gray map. Recently, various aspects of coding and cryptography are dealt with in the general setting of Galois rings instead of finite fields [13, 2, 34, 17, 22, 5]. In view of this, in this thesis the codes we discuss are over Galois rings. In this thesis, we have studied the structure of some linear codes over Galois rings using a transform approach. We study two classes of linear codes invariant under certain monomials. This thesis consists of two parts. (I) The first part is concerned with a class of abelian error-correcting codes which are closed under two additional permutations. We study abelian codes over Galois rings having the additional structure of being closed under the following two permutations: (i) permutation effected by multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions, and (ii) shifting the coordinates by t positions. A code is t-quasi cyclic (t-QC) if t is the smallest integer such that cyclic shift of a codeword by t positions gives another codeword. We call the abelian codes closed under the first permutation Unit-invariant abelian codes, and those closed under the second Quasi-Cyclic Abelian (QGA) codes. Using a Generalized Discrete Fourier Transform (GDFT) defined over an appropriate extension of the Galois ring, we show that Unit-invariant abelian and QGA codes can be easily characterized in the transform domain. For t = 1, QGA codes coincide with those that are cyclic as well as abelian. Also, we show that the dual of a Unit-invariant t-QGA code is also a Unit-invariant t-QGA code. The number of such codes for a specified size is obtained for all possible values of t. Unit-invariant abelian (hence Unit-invariant cyclic) and t-QGA codes over Galois field F?? and over the integer residue rings are obtainable as special cases. (II) In the second part, we study a generalization of abelian code called the multi-dimensional constacyclic (MC) code. Analogous to the first part, we develop a Constacyclic DFT (CDFT) to characterize these codes and then study the characterization of MC codes closed under two additional monomials. Similar to the abelian codes, results on enumeration and dual codes are obtained for MC codes closed under these monomials.