An intrinsical description of group codes

A (left) group code of length n is a linear code which is the image of a (left) ideal of a group algebra via an isomorphism which maps G to the standard basis of . Many classical linear codes have been shown to be group codes. In this paper we obtain a criterion to decide when a linear code is a group code in terms of its intrinsical properties in the ambient space , which does not assume an “a priori” group algebra structure on . As an application we provide a family of groups (including metacyclic groups) for which every two-sided group code is an abelian group code. It is well known that Reed–Solomon codes are cyclic and its parity check extensions are elementary abelian group codes. These two classes of codes are included in the class of Cauchy codes. Using our criterion we classify the Cauchy codes of some lengths which are left group codes and the possible group code structures on these codes. Research supported by D.G.I. of Spain and Fundación Séneca of Murcia.     

Entropy-based evaluation function in a multi-objective approach for the investigation of the genetic code robustness

The genetic code is the interface between the genetic information stored in DNA molecules and the proteins. Considering the hypothesis that the genetic code evolved to its current structure, some researches use optimization algorithms to find hypothetical codes to be compared to the canonical genetic code. For this purpose, a function with only one objective is employed to evaluate the codes, generally a function based on the robustness of the code against mutations. Very few random codes are better than the canonical genetic code when the evaluation function based on robustness is considered. However, most codons are associated with a few amino acids in the best hypothetical codes when only robustness is employed to evaluate the codes, what makes hard to believe that the genetic code evolved based on only one objective, i.e., the robustness against mutations. In this way, we propose here to use entropy as a second objective for the evaluation of the codes. We propose a Pareto approach to deal with both objectives. The results indicate that the Pareto approach generates codes closer to the canonical genetic code when compared to the codes generated by the approach with only one objective employed in the literature.     

On the minimum distance graph of an extended Preparata code

The minimum distance graph of an extended Preparata code P(m) has vertices corresponding to codewords and edges corresponding to pairs of codewords that are distance 6 apart. The clique structure of this graph is investigated and it is established that the minimum distance graphs of two extended Preparata codes are isomorphic if and only if the codes are equivalent.     

There exist non‐isomorphic STS(19) with equivalent point codes

The rows of a point by block incidence matrix of a design can be used to generate a code, the point code of the design. It is known that binary point codes of non‐isomorphic Steiner triple systems of order hr STS(v), are inequivalent when v ≤ 15, but whether this also holds for higher orders has been open. In the current paper, an example of two non‐isomorphic STS(19) with equivalent point codes is presented. © 2004 Wiley Periodicals, Inc.     

Perfect codes as isomorphic spaces

Linear equivalence between perfect codes is defined. This definition gives the concept of general perfect 1-error correcting binary codes. These are defined as 1-error correcting perfect binary codes, with the difference that the set of errors is not the set of weight one words, instead any set with cardinality n and full rank is allowed. The side class structure defines the restrictions on the subspace of any general 1-error correcting perfect binary code. Every linear equivalence class will contain all codes with the same length, rank and dimension of kernel and all codes in the linear equivalence class will have isomorphic side class structures.     

On the classification of perfect codes: side class structures

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C′ are linearly equivalent if there exists a non-singular matrix A such that AC = C′ where C and C′ are matrices with the code words of C and C′ as columns. Hessler proved that the perfect codes C and C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.     

On enumeration of nonequivalent perfect binary codes of length 15 and rank 15

All nonequivalent perfect binary codes of length 15 and rank 15 are constructed that are obtained from the Hamming code H ¹⁵ by translating its disjoint components. Also, the main invariants of this class of codes are determined such as the ranks, dimensions of kernels, and orders of automorphism groups.     

On extremely transitive extended perfect codes

We prove that, for every n = 2 ^k with k ≥ 4, there exist nonequivalent extremely transitive extended perfect codes. A transitive extended perfect code we call extremely transitive if the perfect code obtained from this code by puncturing any coordinate position is not transitive. The classification is given for all extended perfect codes of length 16.     

亚循环的Capable p-群

给定了一个群G,若存在另外的一个群H,能够使得H/Z(H)≌G,则称G是capable群.对cable群进行研究在p-群分类问题的研究中起着相当重要的作用.完全决定了亚循环的capable p-群G.     

New uniqueness proofs for the (5, 8, 24), (5, 6, 12) and related Steiner systems

New elementary proofs of the uniqueness of certain Steiner systems using coding theory are presented. In the process some of the codes involved are shown to be unique.The uniqueness proof for the (5, 8, 24) Steiner system is due to John Conway. The blocks of the system are used to generate a length 24 binary code. Any two such codes are then shown to be equivalent up to a permutation of the coordinates. This code turns out to be the extended Golay code.In the uniqueness proof for the (4, 7, 23) system, the blocks generate a length 23 code which is extended to a length 24 code. The minimum weight vectors of this larger code hold a (5, 8, 24) Steiner system. This result together with the previous one completes the proof. At this point it is also possible to conclude that the codes involved are unique and hence equivalent to the binary perfect Golay code and its extension.Continuing with the uniqueness result for the (3, 6, 22) Steiner system, the blocks generate a length 22 code which is extended to the same length 24 code by the addition of two coordinates and one additional vector. This extension ultimately requires the computation of the coset weight distribution of the length 22 code, a result heretofore unknown. The complete coset weight distribution for a specific (22, 11, 6) self-dual code is computed using the CAMAC computer system.The (5, 6, 12) and (4, 5, 11) Steiner systems are treated differently. It is shown that each system is completely determined by the choice of six blocks which may be assumed to lie in any such design. These six blocks in fact form a basis for length 12 (and 11) ternary codes corresponding to the two systems and may be generated by an algorithm independent of the designs. This algorithm is presented and the minimum weight vectors of the resulting codes, the perfect ternary Golay code and its extension, are calculated by the CAMAC system.     

The power graph of a finite group

The power graph of a group is the graph whose vertex set is the group, two elements being adjacent if one is a power of the other. We observe that non-isomorphic finite groups may have isomorphic power graphs, but that finite abelian groups with isomorphic power graphs must be isomorphic. We conjecture that two finite groups with isomorphic power graphs have the same number of elements of each order. We also show that the only finite group whose automorphism group is the same as that of its power graph is the Klein group of order 4.     

On the classification and enumeration of self-dual codes

A complete classification is given of all [22, 11] and [24, 12] binary self-dual codes. For each code we give the order of its group, the number of codes equivalent to it, and its weight distribution. There is a unique [24, 12, 6] self-dual code. Several theorems on the enumeration of self-dual codes are used, including formulas for the number of such codes with minimum distance ? 4, and for the sum of the weight enumerators of all such codes of length n. Selforthogonal codes which are generated by code words of weight 4 are completely characterized.     

Generalized Gabidulin codes over fields of any characteristic

We generalize Gabidulin codes to a large family of fields, non necessarily finite, possibly with characteristic zero. We consider a general field extension and any automorphism in the Galois group of the extension. This setting enables one to give several definitions of metrics related to the rank-metric, yet potentially different. We provide sufficient conditions on the given automorphism to ensure that the associated rank metrics are indeed all equal and proper, in coherence with the usual definition from linearized polynomials over finite fields. Under these conditions, we generalize the notion of Gabidulin codes. We also present an algorithm for decoding errors and erasures, whose complexity is given in terms of arithmetic operations. Over infinite fields the notion of code alphabet is essential, and more issues appear that in the finite field case. We first focus on codes over integer rings and study their associated decoding problem. But even if the code alphabet is small, we have to deal with the growth of intermediate values. A classical solution to this problem is to perform the computations modulo a prime ideal. For this, we need study the reduction of generalized Gabidulin codes modulo an ideal. We show that the codes obtained by reduction are the classical Gabidulin codes over finite fields. As a consequence, under some conditions, decoding generalized Gabidulin codes over integer rings can be reduced to decoding Gabidulin codes over a finite field.     

Topological rigidity of linear cellular automaton shifts

We prove that topologically isomorphic linear cellular automaton shifts are algebraically isomorphic. Using this, we show that two distinct such shifts cannot be isomorphic. We conclude that the automorphism group of a linear cellular automaton shift is a finitely generated abelian group.     

Nets and their codes

A finitek-net of ordern is an incidence structure ofnk lines andn ² points, with any two lines either meeting once or being parallel, havingk parallel classes ofn lines each, and havingn points on each line. Finite nets are important to the study of finite planes and Latin squares.In this paper finite nets will be studied using the following linear codes: the row space of the incidence vectors of lines, the intersection of this code with its orthogonal, the code generated by differences of parallel lines, and the orthogonal to these codes. Using these codes we are able to recast the Moorhouse conjecture in terms of subcodes of the codes he uses, determine coding-theoretic reasons for a net's being maximal, and generalize a theorem of Assmus and Key which uses codes to classify finite planes of prime order.     

State Spaces of Convolutional Codes

There are various definitions of convolutional codes and each definition leads to a definition of code state space. In the usual definition of a convolutional code generated by a rational encoding matrix input sequences can be any Laurent series. It is proved that restricting input sequences to be rational functions or restricting output sequences to be finite do not change the code state space, and that restricting both input and output sequences to be finite may change the code state space.     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

Frattini子群是无限循环群的有限生成幂零群

完整地确定了Frattini子群是无限循环群的有限生成幂零群的结构,证明了下面的定理.设G是有限生成幂零群,则G的Frattini子群是无限循环群当且仅当G可以分解为G=S×F×T,其中F是秩为s的自由Abel群,T=Z_m_1⊕Zm_2⊕…⊕Z_m_u,m_1,m_2,…,m_u都是大于1的没有平方因子的自然数,m_1|m_2|…|m_u,■式中d_1,d_2,…,d_r都是正整数,d_1|d_2|…|d_r.进一步,(d_1,d2,…,d_r;s;m_1…,m_2,…,m_u)是群G的同构不变量,即若群H也是Frattini子群是无限循环群的有限生成幂零群,那么G同构于H的充要条件是它们有相同的不变量.     

On the enumeration of self-dual codes

We give the complete classification of all binary, self-dual, doubly-even (32, 16) codes. There are 85 non-equivalent, self-dual, doubly-even (32, 16) codes. Five of these have minimum weight 8, namely, a quadratic residue code and a Reed-Muller code, and three new codes. A set of generators is given for a code in each equivalence class together with its entire weight distribution and the order of its entire group with other information facilitating the computation of permutation generators. From this list it is possible to identify all self-dual codes of length less than 32 and the numbers of these are included.     

On the computational utility of posynomial geometric programming solution methods

Ten codes or code variants were used to solve the five equivalent posynomial GP problem formulations. Four of these codes were general NLP codes; six were specialized GP codes. A total of forty-two test problems was solved with up to twenty randomly generated starting points per problem. The convex primal formulation is shown to be intrinsically easiest to solve. The general purpose GRG code called OPT appears to be the most efficient code for GP problem solution. The reputed superiority of the specialized GP codes GGP and GPKTC appears to be largely due to the fact that these codes solve the convex primal formulation. The dual approaches are only likely to be competitive for small degree of difficulty, tightly constrained problems.