LDPC codes from Singer cycles

The main goal of coding theory is to devise efficient systems to exploit the full capacity of a communication channel, thus achieving an arbitrarily small error probability. Low Density Parity Check (LDPC) codes are a family of block codes-characterised by admitting a sparse parity check matrix-with good correction capabilities. In the present paper the orbits of subspaces of a finite projective space under the action of a Singer cycle are investigated. The incidence matrix associated to each of these structures yields an LDPC code in a natural manner.     

Symmetric disjunctive list-decoding codes

In this work, we consider symmetric disjunctive list-decoding (SLD) codes, which are a class of binary codes based on a symmetric disjunctive sum (SDS) of binary symbols. By definition, the SDS takes values from the ternary alphabet \(\{0, 1, *\}\), where the symbol \(*\) denotes “erasure”. Namely: SDS is equal to 0 (1) if all its binary symbols are equal to 0 (1), otherwise SDS is equal to \(*\). The main purpose of this work is to obtain bounds on the rate of these codes.     

LDPC codes from the Hermitian curve

In this paper, we study the code which has as parity check matrix the incidence matrix of the design of the Hermitian curve and its (q + 1)-secants. This code is known to have good performance with an iterative decoding algorithm, as shown by Johnson and Weller in (Proceedings at the ICEE Globe com conference, Sanfrancisco, CA, 2003). We shall prove that has a double cyclic structure and that by shortening in a suitable way it is possible to obtain new codes which have higher code-rate. We shall also present a simple way to constructing the matrix via a geometric approach.      

Construction of LDPC convolutional codes via difference triangle sets

Designs, Codes and Cryptography - In this paper, a construction of $$(n,k,\delta )$$ LDPC convolutional codes over arbitrary finite fields, which generalizes the work of Robinson and Bernstein and...     

High-rate LDPC codes from partially balanced incomplete block designs

Journal of Algebraic Combinatorics - This paper presents a combinatorial construction of low-density parity-check (LDPC) codes from partially balanced incomplete block designs. Since...     

Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for ‘symmetric’ coalition strategies. For binary alphabets and a false accusation probability , a code length of symbols is provably sufficient, for large c ₀, to withstand collusion attacks of up to c ₀ colluders. This improves Tardos’ construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c ₀, we show that even a code length of is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35% is achievable for q = 3 and 80% for q = 10.      

LDPC codes generated by conics in the classical projective plane

We construct various classes of low-density parity-check codes using point-line incidence structures in the classical projective plane PG(2,q). Each incidence structure is based on the various classes of points and lines created by the geometry of a conic in the plane. For each class, we prove various properties about dimension and minimum distance. Some arguments involve the geometry of two conics in the plane. As a result, we prove, under mild conditions, the existence of two conics, one entirely internal or external to the other. We conclude with some simulation data to exhibit the effectiveness of our codes.     

Quasi-cyclic codes as cyclic codes over a family of local rings

We give an algebraic structure for a large family of binary quasi-cyclic codes. We construct a family of commutative rings and a canonical Gray map such that cyclic codes over this family of rings produce quasi-cyclic codes of arbitrary index in the Hamming space via the Gray map. We use the Gray map to produce optimal linear codes that are quasi-cyclic.     

Small weight codewords in the LDPC codes arising from linear representations of geometries

In this article, we investigate the minimum distance and small weight codewords of the LDPC codes of linear representations, using only geometrical methods. First, we present a new lower bound on the minimum distance and we present a number of cases in which this lower bound is sharp. Then we take a closer look at the cases and with a hyperoval, hence q even, and characterize codewords of small weight. When investigating the small weight codewords of , we deal with the case of a regular hyperoval, that is, a conic and its nucleus, separately, since in this case, we have a larger upper bound on the weight for which the results are valid. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 1–24, 2009     

Symmetric semisimple modules of group algebras over finite fields and self-dual permutation codes

A module of a finite group over a finite field with a symmetric non-degenerate bilinear form which is invariant by the group action is called a symmetric module. In this paper, a characterization of indecomposable orthogonal decompositions of symmetric semisimple modules and a criterion for the hyperbolic symmetric modules are obtained, and some applications to the self-dual permutation codes are shown.     

Edge local complementation and equivalence of binary linear codes

Orbits of graphs under the operation edge local complementation (ELC) are defined. We show that the ELC orbit of a bipartite graph corresponds to the equivalence class of a binary linear code. The information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. By extending earlier results on local complementation (LC) orbits, we classify the ELC orbits of all graphs on up to 12 vertices. We also give a new method for classifying binary linear codes, with running time comparable to the best known algorithm.     

Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles

We find lower bounds on the minimum distance and characterize codewords of small weight in low-density parity check (LDPC) codes defined by (dual) classical generalized quadrangles. We analyze the geometry of the non-singular parabolic quadric in PG(4,q) to find information about the LDPC codes defined by Q (4,q), and . For , and , we are able to describe small weight codewords geometrically. For , q odd, and for , we improve the best known lower bounds on the minimum distance, again only using geometric arguments. Similar results are also presented for the LDPC codes LU(3,q) given in [Kim, (2004) IEEE Trans. Inform. Theory, Vol. 50: 2378–2388]     

Symmetric Jacobian for local Lyapunov exponents and Lyapunov stability analysis revisited

The stability analysis introduced by Lyapunov and extended by Oseledec provides an excellent tool to describe the character of nonlinear n-dimensional flows by n global exponents if these flows are stationary in time. However, here we discuss two shortcomings: (a) the local exponents fail to indicate the origin of instability where trajectories start to diverge. Instead, their time evolution contains a much stronger chaos than the trajectories, which is only eliminated by integrating over a long time. Therefore, shorter time intervals cannot be characterized correctly, which would be essential to analyse changes of chaotic character as in transients. (b) Although Oseledec uses an n dimensional sphere around a point x to be transformed into an n dimensional ellipse in first order, this local ellipse has not yet been evaluated. The aim of this contribution is to eliminate these two shortcomings. Problem (a) disappears if the Oseledec method is replaced by a frame with a ‘constraint’ as performed by Rateitschak and Klages (RK) [Rateitschak K, Klages R, Lyapunov instability for a periodic Lorentz gas thermostated by deterministic scattering. Phys Rev E 2002;65:036209/1–11]. The reasons why this method is better will be illustrated by comparing different systems. In order to analyze shorter time intervals, integrals between consecutive Poincaré points will be evaluated. The local problem (b) will be solved analytically by introducing the ‘symmetric Jacobian for local Lyapunov exponents’ and its orthogonal submatrix, which enable to search in the full phase space for extreme local separation exponents. These are close to the RK exponents but need no time integration of the RK frame. Finally, four sets of local exponents are compared: Oseledec frame, RK frame, symmetric Jacobian for local Lyapunov exponents and its orthogonal submatrix.     

Irreducibility testing over local fields

The purpose of this paper is to describe a method to determine whether a bivariate polynomial with rational coefficients is irreducible when regarded as an element in , the ring of polynomials with coefficients from the field of Laurent series in with rational coefficients. This is achieved by computing certain associated Puiseux expansions, and as a result, a polynomial-time complexity bound for the number of bit operations required to perform this irreducibility test is computed.

     

On quantum stabilizer codes derived from local Frobenius rings

In this paper we consider stabilizer codes over local Frobenius rings. Firstly, we study the relative minimum distances of a stabilizer code and its reduction onto the residue field. We show that for various scenarios, a free stabilizer code over the ring does not underperform the according stabilizer code over the field. This leads us to conjecture that the same is true for all free stabilizer codes. Secondly, we focus on the isometries of stabilizer codes. We present some preliminary results and introduce some interesting open problems.     

Symmetric powers of complete modules over a two-dimensional regular local ring

Let be a two-dimensional regular local ring with infinite residue field. For a finitely generated, torsion-free -module , write for the th symmetric power of , mod torsion. We study the modules , , when is complete (i.e., integrally closed). In particular, we show that , for any minimal reduction and that the ring is Cohen-Macaulay.

     

Algebraic-geometry codes, one-point codes, and evaluation codes

One-point codes are those algebraic-geometry codes for which the associated divisor is a non-negative multiple of a single point. Evaluation codes were defined in order to give an algebraic generalization of both one-point algebraic-geometry codes and Reed–Muller codes. Given an -algebra A, an order function on A and given a surjective -morphism of algebras , the ith evaluation code with respect to is defined as the code . In this work it is shown that under a certain hypothesis on the -algebra A, not only any evaluation code is a one-point code, but any sequence of evaluation codes is a sequence of one-point codes. This hypothesis on A is that its field of fractions is a function field over and that A is integrally closed. Moreover, we see that a sequence of algebraic-geometry codes G _i with associated divisors is the sequence of evaluation codes associated to some -algebra A, some order function and some surjective morphism with if and only if it is a sequence of one-point codes.