QPlus: computer package for coding theory research and education

A shared computer tool QPlus for studying coding theory studying is presented. The system offers computations over Z _q ={0, 1, …, q?1} (q<256) and includes modular arithmetic, elementary number theory, vectors and matrices arithmetic and an environment for research on q-ary codes – linear, constant-weight and equidistant codes. QPlus includes a DLL library package that implements coding theory algorithms. We explore the problem of finding bounds on the size of q-ary codes by computer methods. Some examples for optimal equidistant codes and constant-weight equidistant codes that have been constructed by computer methods developed in QPlus are described. We also research some optimal linear codes.     

On the Performance of Permutation Codes for Multi-User Communication

Permutation coding for multi-user communication schemes that originate from the Fast Frequency Hopping/Multiple Frequency Shift Keying modulation is investigated. Each sender is either passive or sends some signal formed as the concatenation of M elementary signals having M different specified frequencies. There is also a jammer, who can introduce disturbances. A single disturbance is either sending the signal that contains all M frequencies at a certain time instant or sending some elementary signal at all time instants. Each receiver receives a vector of M sets, where a set at each time instant contains a fixed frequency if and only if the corresponding elementary signal was sent by either some sender or the jammer. The task of the receiver is to uniquely decode the message of his sender. We present regular constructions of permutation codes for this scheme given the following parameters: the number of frequencies, number of pairs (sender, receiver), number of messages per sender, and maximum number of disturbances of the jammer.     

Bi-catenation and shuffle product of languages

The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages A andB is the set . A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respective to these two operations are studied. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both and , , are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and . For the shuffle product case, surprisingly is a regular language, where a is a letter of the alphabet X. Received: 22 September 1997 / 7 January 1998     

Random Matrices and Codes for the Erasure Channel

The design of erasure correcting codes and their decoding algorithms is now at the point where capacity achieving codes are available with decoding algorithms that have complexity that is linear in the number of information symbols. One aspect of these codes is that the overhead (number of coded symbols beyond the number of information symbols required to achieve decoding completion with high probability) is linear in k. This work considers a new class of random codes which have the following advantages: (i) the overhead is constant (in the range of 5 to 10), independent of the number of data symbols being encoded (ii) the probability of completing decoding for such an overhead is essentially one (iii) the codes are effective for a number of information symbols as low as a few tens (iv) the only probability distribution required is the uniform distribution. The price for these properties is that the decoding complexity is greater, on the order of k ^3/2. However, for the lower values of k where these codes are of particular interest, this increase in complexity might be outweighed by their advantages. The parity check matrices of these codes are chosen at random as windowed matrices, i.e. for each column an initial starting position of a window of length w is chosen and the succeeding w positions are chosen at random as zero or one. It can be shown that it is necessary that w=O(k ^1/2) for the probabilistic matrix rank properties to behave as a non-windowed random matrix. The sufficiency of the condition has so far been established by extensive simulation, although other arguments strongly support this conclusion. The properties of the codes described depend heavily on the rank properties of random matrices over finite fields. Known results on such matrices are briefly reviewed and several conjectures needed in the discussion of the code properties, are stated. The likelihood of the validity of the conjectures is supported through extensive experimentation. Mathematical proof of the conjectures would be of great value for their own interest as well of the particular coding application described here.     

Systematic construction of optimal linear recurrent codes for burst error correction

A method is presented for the construction of binary linear burst error correcting recurrent codes of type B2, viz. those codes which correct any burst of lengthl=rb or less provided it is confined amongr successive blocks of lengthb. The proposed codes are optimal in the sense they meet the lower bound obtained by Wyner and Ash, and are constructed through a particular bordering of the characteristic matrices of analogous codes of shorter block length. Finally, existing linear recurrent codes are compared for efficiency. Lavoro eseguito nell’ambito dell’Università di Roma.     

Formalisation and implementation aspects of K-ary (malicious) codes

This paper presents a new class of (malicious) codes denoted k-ary codes. Instead of containing the whole instructions composing the program’s action, this type of codes is composed of k distinct parts which constitute a partition of the entire code. Each of these parts contains only a subset of the instructions. When considered alone (e.g. by an antivirus) every part cannot be distinguished from a normal uninfected program while their respective action combined according to different possible modes results in the offensive behaviour. In this paper, we presents a formalisation of this type of codes by means of Boolean functions and give their detailed taxonomy. We first show that classical malware are just a particular instance of this general model then we specifically address the case of k-ary codes. We give some complexity results about their detection based on the interaction between the different parts. As a general result, the detection is proved to be NP-complete.     

Encoder and Distance Properties of Woven Convolutional Codes with One Tailbiting Component Code

Woven convolutional codes with one tailbiting component code are studied and their generator matrices are given. It is shown that, if the constituent encoders are identical, a woven convolutional encoder with an outer convolutional warp and one inner tailbiting encoder (WIT) generates the same code as a woven convolutional encoder with one outer tailbiting encoder and an inner convolutional warp (WOT). However, for rate R _tb < 1 tailbiting encoders, the WOT cannot be an encoder realization with a minimum number of delay elements. Lower bounds on the free distance and active distances of woven convolutional codes with a tailbiting component code are given. These bounds are equal to those for woven codes consisting exclusively of unterminated convolutional codes. However, for woven convolutional codes with one tailbiting component code, the conditions for the bounds to hold are less strict.     

Bounds on the minimum code distance for nonbinary codes based on bipartite graphs

The minimum distance of codes on bipartite graphs (BG codes) over GF(q) is studied. A new upper bound on the minimum distance of BG codes is derived. The bound is shown to lie below the Gilbert-Varshamov bound when q ≤ 32. Since the codes based on bipartite expander graphs (BEG codes) are a special case of BG codes and the resulting bound is valid for any BG code, it is also valid for BEG codes. Thus, nonbinary (q ≤ 32) BG codes are worse than the best known linear codes. This is the key result of the work. We also obtain a lower bound on the minimum distance of BG codes with a Reed-Solomon constituent code and a lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed-Solomon constituent code. The bound for LDPC codes is very close to the Gilbert-Varshamov bound and lies above the upper bound for BG codes.     

A computer program for analyses of vital statistics-based occupational mortality data

Routinely collected vital statistics mortality data (death certificate data) on occupation and industry are useful for (1) generating hypotheses about potential occupational hazards and (2) identifying occupational mortality differentials possibly associated with socioeconomic and life-style factors. This paper presents a Fortran program that analyzes occupational mortality using vital statistics and census data. The user can form any desired grouping of age, race, occupation (or industry), and cause of death codes for analysis. The program also allows stratification on social class or other user-defined correlates of occupation such as smoking behavior. Furthermore, program output can be used for Poisson regression analysis of mortality rates.     

On ℤ2ℤ2[u]-additive codes

In this paper, a new class of additive codes which is referred to as ?₂ ?₂[u]-additive codes is introduced. This is a generalization towards another direction of recently introduced ?₂ ?₄-additive codes [J. Borges, C. Fernández-Córdoba, J. Pujol, J. Rif´a, and M. Villanueva, ?₂ ?₄-linear codes: Generator matrices and duality, Designs Codes Cryptogr. 54(2) (2010), pp. 167–179]. ?₂ ?₄-additive codes have shown to provide a promising class of codes with their algebraic structure and applications such as steganography. The standard generator matrices are established and by introducing orthogonality the parity-check matrices are also obtained. A MacWilliams-type identity that relates the weight enumerator of a code with its dual is proved. Furthermore, a Gray map that maps these codes to binary codes is defined and some examples of optimal codes which are the binary Gray images of ?₂ ?₂[u]-additive codes are presented.     

Analytic classification of plane branches up to multiplicity 4

We perform the analytic classification of plane branches of multiplicity less than or equal to four. This is achieved by computing a Standard Basis for the modules of Kähler differentials of such branches by means of the algorithm developed in [Hefez, A., Hernandes, M.E., 2007a. Standard bases for local rings of branches and their module of differentials. J. Symbolic Comput. 42, 178–191] and then applying the classification method for plane branches given in [Hefez, A., Hernandes, M.E., 2007b. The analytic classification of plane branches. arXiv:0707.4502].     

How to Recognize Zero

An elementary point is a point in complexnspace, which is an isolated, nonsingular solution ofnequations innvariables, each equation being either of the formp = 0, wherepis a polynomial in [x₁,…,x_n], or of the formx_j − e^x_i = 0. An elementary number is the polynomial image of an elementary point. In this article a semi algorithm is given to decide whether or not a given elementary number is zero. It is proved that this semi algorithm is an algorithm, i.e. that it always terminates, unless it is given a problem containing a counterexample to Schanuel’s conjecture.     

On (Partial) unit memory codes based on Gabidulin codes

(Partial) unit memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, extended row rank distance, and its slope are defined analogous to the extended row distance in the Hamming metric. Upper bounds for the free rank distance and slope of (P)UM codes in the sum rank metric are derived, and an explicit construction of (P)UM codes based on Gabidulin codes is given.     

Woven convolutional graph codes with large free distances

Constructions of woven graph codes based on constituent convolutional codes are studied, and examples of woven convolutional graph codes are presented. Existence of codes satisfying the Costello lower bound on the free distance within a random ensemble of woven graph codes based on s-partite, s-uniform hypergraphs is shown, where s depends only on the code rate. Simulation results for Viterbi decoding of woven graph codes are presented and discussed.     

Involution codes: with application to DNA coded languages

For an involution θ : Σ^* → Σ^* over a finite alphabet Σ we consider involution codes: θ-infix, θ-comma-free, θ-k -codes and θ-subword-k-codes. These codes arise from questions on DNA strand design. We investigate conditions under which both X and X⁺ are same type of involution codes. General methods for generating such involution codes are given. The information capacity of these codes show to be optimized in most cases. A specific set of these codes was chosen for experimental testing and the results of these experiments are presented.     

Basic principles of mechanical theorem proving in elementary geometries

At the end of 1976 and the beginning of 1977, the author discovered a mechanical method for proving theorems in elementary geometries. This method can be applied to various unordered elementary geometries satisfying the Pascalian Axiom, or to theorems not involving the concept of ‘order’ (e.g., thatc is ‘between’a andb) in various elementary geometries. In Section 4 we give the detailed proofs of the basic principles underlying this method. In Sections 2 and 3 we present the theory of well-ordering of polynomials and a constructive theory of algebraic varieties. Our method is based on these theories, both of which are based on the work of J. F. Ritt. In Section 5 we use Morley's theorem and the Pascal-conic theorem discovered by the author to illustrate the computer implementation of the method.     

Interpolants for Runge-Kutta pairs of order four and five

Interpolants locally of the fifth and sixth orders are constructed by means of the boot-strapping method of Enright et al. for the Runge-Kutta pairs (globally) of the fourth and fifth orders of Dormand and Prince DP(4,5)6M, 7M, 7C and 7S. The asymptotic errors in the interpolants are found to be bounded, in the uniform norm in the space of elementary differentials, by the error in the discrete solution. Numerical results corroborate these asymptotic bounds at working step sizes.     

On constructing disjoint linear codes

To produce a highly nonlinear resilient function, the disjoint linear codes were originally proposed by Johansson and Pasalic in IEEE Trans. Inform. Theory, 2003, 49(2): 494–501. In this paper, an effective method for finding a set of such disjoint linear codes is presented. When n ⩾ 2k, we can find a set of [n,k]disjoint linear codes with cardinality 2^n-k +⌊(n-k)/k⌊; When n < 2k, no set of disjoint linear codes exists with cardinality at least 2. We also describe a result on constructing a set of [n, k] disjoint linear codes with minimum distance at least some fixed positive integer.