Improved Bounds for Quaternary Linear Codes of Dimension 6

In this paper, twenty new codes of dimension 6 are presented which give improved bounds on the maximum possible minimum distance of quaternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. A table of upper and lower bounds for d ⁴(n,6) is presented for n≤ 200. Received: 20 December 1996 / Accepted: 13 May 1997     

Methods of Observing and Correcting Errors in Data-Acquisition Storage and Transmission Systems

Data protection methods are compared for measurements systems, which are based on the use of error-correcting codes, which can correct errors of given multiplicity and observe the maximum number of uncorrectable errors.Translated from Izmeritel’naya Tekhnika, No. 3, pp. 3–6, March, 2005.     

Maximum Distance Separable Convolutional Codes

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. Received: December 10, 1998; revised version: May 14, 1999     

Toric Codes over Finite Fields

In this note, a class of error-correcting codes is associated to a toric variety defined over a finite field _q, analogous to the class of AG codes associated to a curve. For small q, many of these codes have parameters beating the Gilbert-Varshamov bound. In fact, using toric codes, we construct a (n,k,d)=(49,11,28) code over ₈, which is better than any other known code listed in Brouwers tables for that n, k and q. We give upper and lower bounds on the minimum distance. We conclude with a discussion of some decoding methods. Many examples are given throughout.     

Metacyclic error-correcting codes

Error-correcting codes which are ideals in group rings where the underlying group is metacyclic and non-abelian are examined. Such a groupG(M, N,R) is the extension of a finite cyclic group _M by a finite cyclic group _N and has a presentation of the form (S, T:S ^M =1,T ^N =1, T· S=S ^R ·T) where gcd(M, R)=1, R ^N =1 modM, R 1. Group rings that are semi-simple, i.e., where the characteristic of the field does not divide the order of the group, are considered. In all cases, the field of the group ring is of characteristic 2, and the order ofG is odd.Algebraic analysis of the structure of the group ring yields a unique direct sum decomposition ofFG(M, N, R) to minimal two-sided ideals (central codes). In every case, such codes are found to be combinatorically equivalent to abelian codes and of minimum distance that is not particularly desirable. Certain minimal central codes decompose to a direct sum ofN minimal left ideals (left codes). This direct sum is not unique. A technique to vary the decomposition is described. p]Metacyclic codes that are one-sided ideals were found to display higher minimum distances than abelian codes of comparable length and dimension. In several cases, codes were found which have minimum distances equal to that of the best known linear block codes of the same length and dimension.     

Divisibility properties and new bounds for cyclic codes and exponential sums in one and several variables

Serre has obtained sharp estimates for the number of rational points on an algebraic curve over a finite field. In this paper we supplement his technique with divisibility properties for exponential sums to derive new bounds for exponential sums in one and several variables. The new bounds give us an improvement on previous bounds for the minimum distance of the duals of BCH codes. The divisibility properties also imply the existence of gaps in the weight distribution of certain cyclic codes, and in particular gives us that BCH codes are divisible (in the sense of H. N. Ward).The results of this paper were presented in the IEEE International Symposium on Information Theory, Budapest, Hungary, July 1991.This work was partially supported by the Guastallo Fellowship and the Israeli Ministry of Science and Technology under Grant 5110431.This work was partially supported by the National Science Foundation (NSF) under Grants DMS-8711566 and DMS-8712742.This work was partially supported by NSF Grants RII-9014056, the Component IV of the EPSCoR of Puerto Rico Grant, and U.S. Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), of Cornell MSI. Contract DAAL03-91-C-0027.     

The Correction Capability of the Berlekamp–Massey–Sakata Algorithm with Majority Voting

Sakata’s generalization of the Berlekamp–Massey algorithm applies to a broad class of codes defined by an evaluation map on an order domain. In order to decode up to the minimum distance bound, Sakata’s algorithm must be combined with the majority voting algorithm of Feng, Rao and Duursma. This combined algorithm can often decode far more than (d _min −1)/2 errors, provided the errors are in general position. We give a precise characterization of the error correction capability of the combined algorithm. We also extend the concept behind Feng and Rao’s improved codes to decoding of errors in general position. The analysis leads to a new characterization of Arf numerical semigroups.     

Bounds on Minimum Distance for Linear Codes over GF(5)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d ₅(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 5]-code for given values of n and k. In this paper, forty four new linear codes over GF(5) are constructed and a table of d ₅(n, k) k≤ 8, n≤ 100 is presented.     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I∣P] is the generator matrix then the generator matrix of its dual code is The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields. Received March 7, 1995; revised version April 3, 1996     

Bounds on the minimum distance of the duals of extended BCH codes over\mathbb{F}_p

LetC be an extended cyclic code of lengthp ^m over . The border ofC is the set of minimal elements (according to a partial order on [0,p ^m –1]) of the complement of the defining-set ofC. We show that an affine-invariant code whose border consists of only one cyclotomic coset is the dual of an extended BCH code if, and only if, this border is the cyclotomic coset, sayF(t, i), ofp ^t –1–i, with 1 t m and 0 i < p–1. We then study such privileged codes. We first make precize which duals of extendedBCH codes they are. Next, we show that Weil's bound in this context gives an explicit formula; that is, the couple (t, i) fully determines the value of the Weil bound for the code with borderF(t, i). In the case where this value is negative, we use the Roos method to bound the minimum distance, greatly improving the BCH bound.     

Duadic Codes over F2 + uF2

Duadic codes over F ₂ + u F ₂ are introduced as abelian codes by their zeros. This is the function field analogue of duadic codes over Z ₄ introduced recently by Langevin and Solé. They produce binary self-dual codes via a suitable Gray map. Their binary images are themselves abelian, thus generalizing a result of van Lint for cyclic binary codes of even length. We classify them in modest lengths and exhibit interesting non-cyclic examples. Received: April 26, 2000; revised version: May 5, 2001     

A robust scheme for concurrent error diagnosis of MINs

Abstract

Two similar schemes for detecting and correcting errors as well as locating both permanent and temporary faults in multistage interconnection networks for multiprocessor systems are proposed. Depending on the design purpose, two systematic SEC‐DED‐AUED (single error correction‐double error detection‐all unidirectional errors detection) codes are chosen to meet the need of detecting all unidirectional errors which are prevalent in VLSI and to correct all single errors and some multiple errors. The results of encoding and error correcting may be checked by totally self‐checking checkers for Berger code if desired, and thus ensure the robust functioning of the encoder and corrector at the expense of more hardware redundancy. Locating the faulty spots can be done by analyzing the source and destination tags in the corrected packets. The result shows that the two proposed schemes improve the previous schemes at the expense of about 14% and 11% lower information rate for 64‐bit information.     

Redefining the impact assessment of buildings: an uncertainty-based approach to rating codes

Discrepancies between predicted and in-use building performance are well documented in impact assessments for buildings, such as rating codes. This is a consequence of uncertainties that undermine predictions, which include procedural errors, as well as users’ behaviour and technological change. Debate on impact assessment for buildings predominantly focuses on operational issues and does not question the deterministic model on which assessments are based as a potential, underlying cause of ineffectiveness. This article builds on a non-deterministic urban planning theory and the principles it outlines, which can help manage uncertain factors over time. A rating code model is proposed that merges its typical steps of assessment (i.e. classification, characterisation and valuation) with those principles, applied within the impact assessment of buildings. These are experimentation (of other criteria than those typically appraised), exploration (the process of identifying the long-term vulnerability of such criteria) and inquiry (iterating and critically evaluating the assessment over time).     

Two new decoding algorithms for Reed-Solomon codes

The subject of decoding Reed-Solomon codes is considered. By reformulating the Berlekamp and Welch key equation and introducing new versions of this key equation, two new decoding algorithms for Reed-Solomon codes will be presented. The two new decoding algorithms are significant for three reasons. Firstly the new equations and algorithms represent a novel approach to the extensively researched problem of decoding Reed-Solomon codes. Secondly the algorithms have algorithmic and implementation complexity comparable to existing decoding algorithms, and as such present a viable solution for decoding Reed-Solomon codes. Thirdly the new ideas presented suggest a direction for future research. The first algorithm uses the extended Euclidean algorithm and is very efficient for a systolic VLSI implementation. The second decoding algorithm presented is similar in nature to the original decoding algorithm of Peterson except that the syndromes do not need to be computed and the remainders are used directly. It has a regular structure and will be efficient for implementation only for correcting a small number of errors. A systolic design for computing the Lagrange interpolation of a polynomial, which is needed for the first decoding algorithm, is also presented.This research was supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Government of Canada     

Optimal Formally Self-Dual Codes over ?5 and ?7

In this paper, we study optimal formally self-dual codes over ?₅ and ?₇. We determine the highest possible minimum weight for such codes up to length 24. We also construct formally self-dual codes with highest minimum weight, some of which have the highest minimum weight among all known linear codes of corresponding length and dimension. In particular, the first known [14, 7, 7] code over ?₇ is presented. We show that there exist formally self-dual codes which have higher minimum weights than any comparable self-dual codes. Received: May 18, 1998; revised version: September 4, 1999     

The Minimal Generator Matrix of a Vector Space

The atomic vectors of a finitely generated vector space C over a field F are characterized for C a subspace of the product vector space ? = ∏ _{i =1} ⁿ ? _i over F. For finite fields, the minimal trellis diagram for mixed-codes is determined, and this provides the L-section minimal trellis diagram for linear codes. As an example, an extremely simple yet comprehensive analysis of the trellis structure of Reed-Muller codes is given. In particular, a trellis oriented generator matrix for the 2 ^l -section minimal trellis diagram of a Reed-Muller code is presented. Received: February 27, 1997; revised version: May 6, 1999     

Concatenated coded modulation techniques and orthogonal space-time block codes in the presence of fading channel estimation errors

Performance of coding and modulation systems in fading channels is usually analysed under the assumption that the receiver has perfect knowledge of channel condition. However, various shortcomings in practical channel estimation techniques lead to imperfections, resulting in channel estimation errors. The authors analyse a practical coding and modulation scheme for multiple-antenna systems considering channel estimation errors. The novelty of this study resides in providing error probability bounds for concatenated trellis coded modulation (TCM) or bit-interleaved coded modulation (BICM) schemes with orthogonal space--time block codes (OSTBC) under imperfect channel estimation assumption. Moreover, our analytical results quantify the performance degradation associated with various levels of channel estimation error variance. The authors also show that if channel estimation quality does not improve sufficiently with SNR, there would be error floor in performance, such that the coded system could get outperformed by a system with differential signalling that requires no channel estimation. Simulation results are presented, which confirm the validity of the analytical results.     

On a signal processing algorithms based class of linear codes

In this work, the correspondence between linear (n,k,d) codes and aperiodic convolution algorithms for computing a system ofk bilinear forms over GF(p^m) is explored. A number of properties are established for the linear codes that can be obtained from a computational procedure of this type. A particular bilinear form is considered and a class of linear codes over GF(2^m) is derived with varyingk andd parameters. The code lengthn is equal to the multiplicative complexity of the computation of an aperiodic convolution and an efficient computation thereof leads to the shortest codes possible using this approach, many of which are optimal or near-optimal. A new decoding procedure for this class of linear codes is presented which exploits the block structure of the generator matrix of the codes. Several interesting observations are made on the nature of the codes obtained as a result of such computations. Such a computation of bilinear forms can be generalized to include other bilinear forms and the related classes of codes.     

Transform domain characterization of cyclic codes overZ m

Cyclic codes with symbols from a residue class integer ringZ _m are characterized in terms of the discrete Fourier transform (DFT) of codewords defined over an appropriate extension ring ofZ _m . It is shown that a cyclic code of length n overZ _m ,n relatively prime tom, consists ofn-tuples overZ _m having a specified set of DFT coefficients from the elements of an ideal of a subring of the extension ring. Whenm is equal to a product of distinct primes every cyclic code overZ _m has an idempotent generator and it is shown that the idempotent generators can be easily identified in the transform domain. The dual code pairs overZ _m are characterized in the transform domain for cyclic codes. Necessary and sufficient conditions for the existence of self-dual codes overZ _m are obtained and nonexistence of self-dual codes for certain values ofm is proved.     

A generalization of justesen codes

Abstract

By using alternant codes as outer codes in the concatenated structure for Justesen codes, a generalization of Justesen codes which completely meets the Zyablov bound is constructed. For this class of codes, the inner codes are explicitly defined while the outer codes are not.