Quotients of Gaussian graphs and their application to perfect codes

A graph-based model of perfect two-dimensional codes is presented in this work. This model facilitates the study of the metric properties of the codes. Signal spaces are modeled by means of Cayley graphs defined over the Gaussian integers and denoted as Gaussian graphs. Codewords of perfect codes will be represented by vertices of a quotient graph of the Gaussian graph in which the signal space has been defined. It will be shown that any quotient graph of a Gaussian graph is indeed a Gaussian graph. This makes it possible to apply previously known properties of Gaussian graphs to the analysis of perfect codes. To illustrate the modeling power of this graph-based tool, perfect Lee codes will be analyzed in terms of Gaussian graphs and their quotients.     

Addition patterns, codes and contact graphs for fullerene derivatives

The mathematical concept of the d-code and its associated contact graph give a model for sterically constrained addition patterns in fullerene derivatives C60Xm and C70Xm. In combination with simple electronic arguments, the stoichiometries, symmetries, and location of addends can be predicted, yielding a small number of candidates for further study. For example, sterically and optimal solutions C60Xm with pairwise separation of d bonds between addends are found at m(d) = 24(2), 12(3), 6(4,5), 2(6 to 9). The solution for C60X24 is unique, and the model selects 12 candidates for C60X12 from a starting set of 11661527060 possibilities.     

MDS codes in Doob graphs

The Doob graph D(m, n), where m > 0, is a Cartesian product of m copies of the Shrikhande graph and n copies of the complete graph K ₄ on four vertices. The Doob graph D(m, n) is a distance-regular graph with the same parameters as the Hamming graph H(2m + n, 4). We give a characterization of MDS codes in Doob graphs D(m, n) with code distance at least 3. Up to equivalence, there are m ³/36+7m ²/24+11m/12+1?(m mod 2)/8?(m mod 3)/9 MDS codes with code distance 2m + n in D(m, n), two codes with distance 3 in each of D(2, 0) and D(2, 1) and with distance 4 in D(2, 1), and one code with distance 3 in each of D(1, 2) and D(1, 3) and with distance 4 in each of D(1, 3) and D(2, 2).     

A comparison of approaches for finding minimum identifying codes on graphs

In order to formulate mathematical conjectures likely to be true, a number of base cases must be determined. However, many combinatorial problems are NP-hard and the computational complexity makes this research approach difficult using a standard brute force approach on a typical computer. One sample problem explored is that of finding a minimum identifying code. To work around the computational issues, a variety of methods are explored and consist of a parallel computing approach using MATLAB, an adiabatic quantum optimization approach using a D-Wave quantum annealing processor, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers. Each of these methods requires the problem to be formulated in a unique manner. In this paper, we address the challenges of computing solutions to this NP-hard problem with respect to each of these methods.     

A new approach to constructing CSS codes based on factor graphs

A novel, practical and convenient approach to constructing Calderbank-Shor-Steane (CSS) codes based on factor graphs is presented in this paper. Our proposed method is applied to solve two problems associated with constructing CCS codes. One is judging whether a code is a weakly self-dual code or not, the other is finding the generator matrix and parity-check matrix of a weakly self-dual code. The novelty, practicality and convenience of the approach are shown as follows. First, the approach is a hitherto unexplored one to constructing CSS codes. Second, the judgment of a weakly self-dual code is entirely based on factor graphs. Namely, we consider a code a weakly self-dual one when the Tanner graph or convolutional factor graph of its dual code can be obtained by that of its own via our proposed transform T_R→L. Finally, we can obtain the generator matrix and parity-check matrix of a weakly self-dual code via factor graphs other than conventional algebra methods, which allow us avoid matrix computation to get them. An example is given to show how to construct quantum CSS code based on factor graphs. The method can be extended to other CSS codes.     

On numerically decipherable codes and their homophonic partitions

We investigate the homophonic partitions of numerically decipherable (ND) codes in relationship with the notion of multivalued encodings. Moreover, we present a new class of codes, the class of homophonically decipherable (HD) codes, studying their Kraft-McMillan sum.     

Aspect graphs and their use in object recognition

Previous researchers have described several different approaches to 3-D object recognition based on using an iterative technique to control the matching of features from the 2-D projection of a 3-D model to observed image features. The major problem encountered with such approaches is how to automatically choose starting parameter estimates in a manner which both avoids recognition errors due to local minima and is still reasonably efficient. This paper investigates the use of theaspect graph to address this problem. The basic idea is quite simple — an iterative solution is generated for each of a set of candidate aspects and the best of these is chosen as the recognized view. Two assumptions are required in order for this approach to be valid: (1) the iterative search for the correct candidate aspect must converge to the correct answer, and (2) the solution found for the correct aspect must be better than that found for any of the incorrect candidate aspects. In order to explore the validity of these assumptions, a simple aspect graph-based recognition system was implemented. Experiments were carried out using both real and simulated data. The results indicate that the underlying assumptions are generally valid, and that this approach has advantages over previous techniques which incorporated an iterative search.This work was supported by Air Force Office of Scientific Research grants AFOSR-87-0316 and AFOSR-89-0036 and by National Science Foundation grants IRI-8817776.An earlier version of this paper was presented at the IEEE 1988 International Conference on Computer Vision, Tarpon Springs, Florida.     

On State-dependent dynamic graphs and their controllability properties

We consider distributed dynamic systems operating over a graph or a network. The geometry of the network is assumed to be a function of the underling system's states-giving it a unique dynamic character. Certain aspects of the resulting abstract structure, having a mixture of combinatorial and system theoretic features, are then studied. In this venue, we will explore an interplay between notions from extremal graph theory and system theory by considering a controllability framework for such state-dependent dynamic graphs.     

A class of quantum low-density parity check codes by combining seed graphs

This paper proposes a new construction of quantum low-density parity check (LDPC) codes that belong to the class of general stabilizer (non-CSS) codes. The method constructs a binary check matrix $A=(A_{1}|A_{2})$ associated with the stabilizer generators of a quantum LDPC code. The binary check matrix is obtained from a large bipartite graph built by combining several small bipartite graphs called seed graphs. Computer simulation results show that the proposed code has similar or better performance than other quantum LDPC codes, and can be improved by exploiting the degenerate effect of quantum error-correcting codes.     

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.     

Classes of quantum codes derived from self-dual orientable embeddings of complete multipartite graphs

Quantum Information Processing - Semi-quantum protocols that allow some of the users to remain classical are proposed for a large class of problems associated with secure communication and secure...     

Multiple level orthogonal codes and their application in MC-CDMA systems

This paper proposes the use of multiple level orthogonal (MLO) codes in multicarrier CDMA (MC-CDMA) systems. It is extremely challenging to improve system error probability performance of MC-CDMA systems with binary spreading codes in multi-user conditions, since attainable-diversity performance is severely degraged by multi-user interference (MUI) in frequency-selective fading channel conditions, even with the use of optimum multi-user detection (MUD) methods. MLO codes are shown to improve system error probability performance in heavily-loaded or fully-loaded systems, in comparison to binary codes. Some widely used MLO code generation methods are summarized, and a new generation method is also provided. The performance advantage of MLO codes over binary codes is analyzed by treating the spreading process in MC-CDMA as a coding process and via analysis of pair-wise sequence error probability. Rules for choosing desirable MLO codes for multi-user MC-CDMA are also given. Numerical results show that MLO codes can provide a substantial performance improvement in fully-loaded systems. For example, for a K = 4 user system with spreading gain L = 4, our system can obtain a diversity order of 3, whereas the binary code system diversity order is only slightly larger than 1. The MLO code application provides a new way to compensate for multi-user interference (MUI) and makes MC-CDMA more attractive for future high data-rate transmission systems.     

Prefix codes,trees, and automata

We investigate the relations between the tree representation of a prefix code C, its patterns, the minimal automaton

which recognizes $\text{C}{}^1$, and the homomorphic images of the underlying algebra of

. These relations provide us with an appealing formulation which allows us to state (and eventually solve) some problems concerning the structure of prefix codes and therefore the structure of trees.     

Global view on reactivity: switch graphs and their logics

The notion of reactive graph generalises the one of graph by allowing the base accessibility relation to change when its edges are traversed. Can we represent these more general structures using points and arrows? We prove this can be done by introducing higher order arrows: the switches. The possibility of expressing the dependency of the future states of the accessibility relation on individual transitions by the use of higher-order relations, that is, coding meta-relational concepts by means of relations, strongly suggests the use of modal languages to reason directly about these structures. We introduce a hybrid modal logic for this purpose and prove its completeness.     

Recognition of shapes by editing their shock graphs

This paper presents a novel framework for the recognition of objects based on their silhouettes. The main idea is to measure the distance between two shapes as the minimum extent of deformation necessary for one shape to match the other. Since the space of deformations is very high-dimensional, three steps are taken to make the search practical: 1) define an equivalence class for shapes based on shock-graph topology, 2) define an equivalence class for deformation paths based on shock-graph transitions, and 3) avoid complexity-increasing deformation paths by moving toward shock-graph degeneracy. Despite these steps, which tremendously reduce the search requirement, there still remain numerous deformation paths to consider. To that end, we employ an edit-distance algorithm for shock graphs that finds the optimal deformation path in polynomial time. The proposed approach gives intuitive correspondences for a variety of shapes and is robust in the presence of a wide range of visual transformations. The recognition rates on two distinct databases of 99 and 216 shapes each indicate highly successful within category matches (100 percent in top three matches), which render the framework potentially usable in a range of shape-based recognition applications.     

Coverings,centered codes,and combinatorial steganography

It is shown that steganography with a given distortion criteria, which we call combinatorial steganography, is equivalent to coverings of Hamming spaces or to so-called centered error-correcting codes, depending on whether an opponent is passive or active, respectively. A construction of centered error-correcting codes based on Reed-Solomon and algebraic geometry codes is proposed.     

Some remarks on Kähler differentials and ordinary differentials in nonlinear control theory

In the algebraic approach to nonlinear control systems two similar notions, namely Kähler differentials and the formal vector space of differential one-forms having the properties of ordinary differentials, are frequently used to study the systems. This technical note explains that the formal vector space of differential one-forms is isomorphic to a quotient space (module) of Kähler differentials. These two modules coincide when they are modules over a ring of linear differential operators over the field of algebraic functions. Some remarks and examples demonstrating when the use of Kähler differentials might not be appropriate are included.     

Generative languages,codes and parallel processing

A special class of context-sensitive generative languages (CSGLs) that can be used as an indexation in parallel computing is described. The languages are recursively generated, and the algorithm for interprocesses communication is based on the positive resolution of the post correspondence problem (PCP) within CSGLs. This fact follows from the main result that a constructed CSGL has a complete set of production rules, i.e. no new rule can be added to the set without destroying the integrity of the CSGL.     

量子纠错码[[7,1,4]]_p(p>3)存在性的图论构造方法

利用由Schingemann和Werner两人提出的构造量子纠错码的图论方法,证明了量子纠错码[[7,1,4]]p(p>3)的存在性。