Search

In a previous paper, the second and third named authors introduced the concept of the complete cycle index and discussed a relation with the complete weight enumerator in coding theory. In this paper, we introduce the concept of the complete joint cycle index and the average complete joint cycle index, and discuss a relation with the complete joint weight enumerator and the average complete joint weight enumerator, respectively, in coding theory. Moreover, the notion of the average intersection numbers is given, and we discuss a relation with the average intersection numbers in coding theory. [ABSTRACT FROM AUTHOR]

In this paper, we study codes where the alphabet is a finite Frobenius bimodule over a finite ring. We discuss the extension property for various weight functions. Employing an entirely character-theoretic approach and a duality theory for partitions on Frobenius bimodules, we derive alternative proofs for the facts that the Hamming weight and the homogeneous weight satisfy the extension property. We also use the same techniques to derive the extension property for other weights, such as the Rosenbloom-Tsfasman weight. [ABSTRACT FROM AUTHOR]

Compressed sensing is a sparse sampling theory. Compared with the Nyquist-Shannon sampling theory, in compressed sensing one could reconstruct a sparse signal from a few linear and non-adaptive measurements. How to construct a good sensing matrix which captures the full information of a sparse signal is an important problem in compressed sensing. In this paper, we present a new deterministic construction using a linear or nonlinear code, which is a generalization of DeVore's construction and Li et al.'s construction. By choosing some appropriate linear codes or nonlinear codes, we will construct some good binary sensing matrices which are superior to DeVore's ones and Li et al.'s ones. [ABSTRACT FROM AUTHOR]

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C* generated by C satisfies if z, implies (or z, implies ). We show that a finite insertable code is a full uniform code. On the other hand there are many finite extractable codes which are not full uniform codes. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and -codes, and refer to the extractability of them. [ABSTRACT FROM AUTHOR]

Permutation decoding method developed by MacWilliams and described in [Permutation decoding of systematic codes, Bell Syst. Tech. J. 43 (1964) 485-505] is a decoding technique that uses a subset of the automorphism group of the code called a PD-set. The complexity of the permutation decoding algorithm depends on the size of the PD-set and finding a minimal PD-set for an error correcting code is a hard problem. In this paper we examine binary codes from the complete-multipartite graph and find PD-sets for all values of and . Further we show that these PD-sets are minimal when is odd and . [ABSTRACT FROM AUTHOR]

In a paper concerning the relationship between coding theory and factorization theory Restivo, Salemi, and Sportelli made a conjecture that if subsets possess certain properties then they cannot form a factorization of a finite cyclic group. In this note it is shown that in fact such factorizations do exist. [ABSTRACT FROM AUTHOR]

There is a special local ring E of order 4 , without identity for the multiplication, defined by E = 〈 a , b | 2 a = 2 b = 0 , a 2 = a , b 2 = b , a b = a , b a = b 〉. We study the algebraic structure of linear codes over that non-commutative local ring, in particular their residue and torsion codes. We introduce the notion of quasi self-dual codes over E , and Type IV codes, that is quasi self-dual codes whose all codewords have even Hamming weight. We study the weight enumerators of these codes by means of invariant theory, and classify them in short lengths. [ABSTRACT FROM AUTHOR]

The k -prefix-free, k -suffix-free and k -infix-free languages generalize the prefix-free, suffix-free and infix-free languages by allowing marginal errors. For example, a string x in a k -prefix-free language L can be a prefix of up to k different strings in L. We also define finitely prefix-free languages in which a string x can be a prefix of finitely many strings. We present efficient algorithms that determine whether or not a given regular language is k -prefix-free, k -suffix-free or k -infix-free, and analyze the time complexity of the algorithms. We establish undecidability results for deciding these properties for (linear) context-free languages. [ABSTRACT FROM AUTHOR]

A two-dimensional code of pictures is defined as a set X ⊆ Σ** such that any picture over Σ is tilable in at most one way with pictures in X. It is proved that in general it is undecidable whether a finite set of picture is a code. The subclass of prefix codes is introduced and it is proved that it is decidable whether a finite set of pictures is a prefix code. Further a polynomial time decoding algorithm for finite prefix codes is given. Maximality and completeness of finite prefix codes are studied. [ABSTRACT FROM AUTHOR]

The action of the Bernstein operators on Schur functions was given in terms of codes by Carrell and Goulden (2011) and extended to the analog in Schur Q-functions in our previous work. We define a new combinatorial model of extended codes and show that both of these results follow from a natural combinatorial relation induced on codes. The new algebraic structure provides a natural setting for Schur functions indexed by compositions. [ABSTRACT FROM AUTHOR]

The branch of coding theory that is based on formal languages has produced several methods for defining code properties, including word relations, dependence systems, implicational conditions, trajectories, and language inequations. Of those, the latter three can be viewed as formal methods in the sense that a certain formal expression can be used to denote a code property. Here we present a formal method which is based on transducers. Each transducer of a certain type defines/describes a desired code property. The method provides simple and uniform decision procedures for the basic questions of property satisfaction and maximality for regular languages. Our work includes statements about the hardness of deciding some of the problems involved. It turns out that maximality can be hard to decide even for "classical" code properties of finite languages. We also present an initial implementation of a LAnguage SERver capable of deciding the satisfaction problem for a given transducer code property and regular language. [ABSTRACT FROM AUTHOR]