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     

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.     

光通信系统中一种新颖的级联码型

基于级联码对光通信系统中级联码特性和ITU-T G.975.1中两种超强前向纠错(SFEC)码型进行分析和研究后,提出了一种新颖的RS(255,239) BCH(1023,963)级联码型.仿真表明,该码型与ITU-T G.975.1中RS(255,239) CSOC(k0/n0=6/7,J=8)码相比较,具有更低的冗余度和更好的纠错性能,并且在经过三次迭代且误码率(BER)为10-12时其净编码增益(NCG)比ITU-T G.975.1中RS(255,239) CSOC(k0/n0=6/7,J=8)码和BCH(3860,3824) BCH(2040,1930)码要分别大0.60 dB和0.57 dB.因而,它更适用于超长距离、超大容量和超高速的光通信系统中,并可以作为SFEC码的一种候选码型.     

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.     

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.     

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 [ ?P ^tr¦I]. 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.     

线性隐写码的性质与构造

本文从隐写术的安全性需求出发抽象出一个新的编码问题,称之为隐写码。利用线性空间的直和分解得到了一种线性隐写码的构造方法。通过引入线性空间t阶维数的概念将线性隐写码问题转化成了一个代数问题,从而得到了线性隐写码长度的上界,并由此定义了最大长度可嵌入码。证明了线性最大长度可嵌入码与线性完备纠错码有1-1对应关系。     

On the dimension of Goppa codes

A lower bound for the dimension of geometric BCH codes (i.e. subfield subcodes of Goppa codes) has been given by M. Wirtz [7]. We prove that this bound is actually exact for small enough divisorG.     

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     

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.     

Generating visually appealing QR codes using colour image embedding

Quick Response (QR) codes have become very popular in current scenario. Being machine readable, they appear like blocks of random black and white noise. With their increasing use in marketing material, many attempts have been made to make them visually appealing by embedding images and logos. We propose a colour image embedding method that uses circular modules to reduce the block-like appearance of the code. The luminance of the image pixels corresponding to the centric and surrounding regions of a circular code module is modified in such a way that they blend into the code with least visual distortion, and the resultant code demonstrates high degree of decoding robustness. The results of experiments to assess the visual appeal of the resultant codes, and their tolerance to noise and blur indicate that the visually appealing codes have decodability comparable to the original QR codes, thus justifying the attempt to embed image in an otherwise non-appealing QR code. The codes generated by the proposed method and three other state-of-the art methods are compared for visual appeal and decoding robustness. The results of the comparison indicate that the codes generated by the proposed method have visual appeal best amongst the codes generated by other state-of-the art methods. In terms of tolerance to noise and blur, they are the best amongst the codes which have comparable visual appeal, and second best amongst all.     

On the Concatenated Structure of a Linear Code

We address here the problem of finding a concatenated structure in a linear code ? given by its generating matrix, that is, if ? is equivalent to the concatenation of an inner code B ₀ and an outer code E ₀, then find two codes B and E such that their concatenation is equivalent to ?. If the concatenated structure exists and is non trivial (i.e. the inner code B is non trivial), the dual distance of ? is equal to the dual distance of B. If this dual distance is small enough to allow the computation of many small weight words in the dual of ?, it is possible to recover first an inner code B, then an outer code E whose concatenation is equivalent to ?. These two codes are equivalent respectively to the original inner and outer codes B ₀ and E ₀.     

A Propagation Rule for Linear Codes

We establish a general theorem which, given an arbitrary linear code, generates a family of linear codes of larger lengths and higher dimensions. The proof is based on a representation of the given linear code as a (generalized) algebraic-geometry code. Examples yielding many optimal linear codes document the power of this theorem. Received: July 5, 1999     

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     

Minimum distance of relative Reed–Muller codes

We describe a construction of error-correcting codes on a fibration over a curve defined over a finite field, which may be considered as a relative version of the classical Reed–Muller code. In the case of complete intersections in a projective bundle, we give an explicit lower bound for the minimum distance.     

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.     

Rotational invariance of two-level group codes over dihedral and dicyclic groups

Phase-rotational invariance properties for two-level constructed, (using a binary code and a code over a residue class integer ring as component codes) Euclidean space codes (signal sets) in two and four dimensions are discussed. The label codes are group codes over dihedral and dicyclic groups respectively. A set of necessary and sufficient conditions on the component codes is obtained for the resulting signal sets to be rotationally invariant to several phase angles.     

Defect and Transient Fault-Tolerant System Design for Hybrid CMOS/Nanodevice Digital Memories

Targeting on the future fault-prone hybrid CMOS/nanodevice digital memories, this paper presents two fault-tolerance design approaches that integrally address the tolerance for defects and transient faults. These two approaches share several key features, including the use of a group of Bose-Chaudhuri-Hocquenghem (BCH) codes for both defect tolerance and transient fault tolerance, and integration of BCH code selection and dynamic logical-to-physical address mapping. The first approach is straightforward and easy to implement but suffers from a rapid drop of achievable storage capacity as defect densities and/or transient fault rates increase, while the second approach can achieve much higher storage capacity under high defect densities and/or transient fault rates at the cost of higher implementation complexity and longer memory access latency. Based on extensive computer simulations and BCH decoder circuit design, we have demonstrated the effectiveness of the presented approaches under a wide range of defect densities and transient fault rates, while taking into account of the fault-tolerance storage overhead and BCH decoder implementation cost in CMOS domain     

Construction of Improved Geometric Goppa Codes from Klein Curves and Klein-like Curves

Linear error-correcting codes, especially Reed-Solomon codes, find applications in communication and computer memory systems, to enhance their reliability and data integrity. In this paper, we present Improved Geometric Goppa (IGG) codes, a new class of error-correcting codes, based on the principles of algebraic-geometry. We also give a reasonably low complexity procedure for the construction of these IGG codes from Klein curves and Klein-like curves, in plane and high-dimensional spaces. These codes have good code parameters like minimum distance rate and information rate, and have the potential to replace the conventional Reed-Solomon codes in most practical applications. Based on the approach discussed in this paper, it might be possible to construct a class of codes whose performance exceeds the Gilbert-Varshamov bound. Received: November 14, 1995; revised version: November 22, 1999