Characterizations of pseudo-codewords of (low-density) parity-check codes

An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph.     

Codes with girth 8 Tanner graph representation

Since short cycles are (empirically) detrimental to message passing, determining the girth of a given code is of interest in coding theory. Halford et al. studied codes which do not have a 4-cycle-free Tanner graph representation. It is natural to then ask which codes must have girth 8. In this paper, a new necessary condition is derived for codes to have girth 8. Halford et al. made statements about the girth of high rate well known codes but the girth of lower rate codes remain open. In this work, we investigate girth of low rate Reed–Muller, BCH and Reed–Solomon codes.     

Regular LDPC Codes from Semipartial Geometries

By considering a class of combinatorial structures, known as semipartial geometries, we define a class of low-density parity-check (LDPC) codes. We derive bounds on minimum distance, rank and girth for the codes from semipartial geometries, and present constructions and performance results for the classes of semipartial geometries which have not previously been proposed for use with iterative decoding.     

低密度奇偶校验码的构造

低密度奇偶校验码(LDPC)最早是由Gallager于1962年提出.它们是线性分组码,其比特错误率极大地接近香农界.1995年Mackay和Neal发掘了LDPC码的新应用后,LDPC码引起了人们的广泛关注.本文利用组合结构给出一些新的LDPC码:利用可分组设计构造一类Tanner图中不含四长圈的正则LDPC码.     

Systems theoretic questions in coding theory

A central theme of current research in coding theory are low density parity-check (LDPC) codes and more generally codes defined via graphs. There exist various decoding algorithms which work in a decentralized manner and which can be viewed as discrete dynamical systems. In this talk, we explain these algorithms from a systems theoretic point of view. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Three-dimensional cyclic Fire codes

Three-dimensional cyclic array codes over F _q that can correct single three-dimensional bursts (or clusters) of errors are considered. The class cyclic three-dimensional burst-error-correcting array codes, called three-dimensional Fire codes, is constructed. Several important properties such as the burst-error-correcting capability and the positions of the parity-check symbols are presented. Also, encoding and decoding algorithms are given.     

基于平均树值的无圈图博弈有效解

本文对无圈图博弈进行了研究,考虑了大联盟收益不小于各分支收益之和的情况。通过引入剩余公平分配性质,也就是任意两个分支联盟的平均支付变化相等,给出了一个基于平均树值的无圈图博弈有效解。同时,结合有效性和分支公平性对该有效解进行了刻画。特别地,若无圈图博弈满足超可加性时,证明了该有效解一定是核中的元素,说明此时的解是稳定的。最后,通过一案例分析了该有效解的特点,即越大的分支分得的剩余越多,并且关键参与者,也就是具有较大度的参与者可获得相对多的支付。     

The strong perfect graph conjecture holds for diamonded odd cycle-free graphs

In this paper, we show that the strong perfect graph conjecture holds for a new class of graphs which we call diamonded odd cycle-free graphs. The class of diamonded odd cycle-free graphs contains the classes of threshold graphs and K₄\e-free graphs.     

Construction of some countable 1-arc-transitive bipartite graphs

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.     

A generalization of Lee codes

Motivated by a problem in computer architecture we introduce a notion of the perfect distance-dominating set (PDDS) in a graph. PDDSs constitute a generalization of perfect Lee codes, diameter perfect codes, as well as other codes and dominating sets. In this paper we initiate a systematic study of PDDSs. PDDSs related to the application will be constructed and the non-existence of some PDDSs will be shown. In addition, an extension of the long-standing Golomb–Welch conjecture, in terms of PDDS, will be stated. We note that all constructed PDDSs are lattice-like which is a very important feature from the practical point of view as in this case decoding algorithms tend to be much simpler.     

Parameterized fairness axioms on cycle-free graph games

We study cooperative transferable utility games with a communication structure represented by an undirected graph, i.e., a group of players can cooperate only if they are connected on the graph. This type of games is called graph games and the best-known solution for them is the Myerson value, which is characterized by the component efficiency axiom and the fairness axiom. Recently the average tree solution has been proposed on cycle-free graph games, and shown to be characterized by the component efficiency axiom and the component fairness axiom. We propose e{\epsilon} -parameterized fairness axiom on cycle-free graph games that incorporates the preceding fairness axioms, and show the existence and the uniqueness of the solution. We then discuss a relationship between the existing and our proposed solutions by a numerical example.     

基于图对策的收益分配

基于具有交流结构的合作对策,即图对策,对平均树解拓展形式的特征进行刻画,提出此解满足可加性公理。进一步地,分析了对于无圈图对策此解是分支有效的。并且当连通分支中两个局中人相关联的边删掉后,此连通分支的收益变化情况可用平均树解表示。这一性质是Shapley值和Myerson值所不具有的。最后,我们给出了模糊联盟图对策中模糊平均树解的可加性和分支有效性。     

模糊联盟合作对策的平均树解

给出图对策中平均树解的拓展形式, 证明其是满足分支有效性和分支公平性的唯一解. 针对具有模糊联盟的图对策, 提出了一种模糊分配, 即模糊平均树解. 当模糊联盟图对策为完全图对策时, 模糊平均树解等于模糊Shapley值. 最后, 讨论了模糊平均树解与模糊联盟核心之间的关系, 并进行了实例论证.     

On generator and parity-check polynomial matrices of generalized quasi-cyclic codes

Generalized quasi-cyclic (GQC) codes have been investigated as well as quasi-cyclic (QC) codes, e.g., on the construction of efficient low-density parity-check codes. While QC codes have the same length of cyclic intervals, GQC codes have different lengths of cyclic intervals. Similarly to QC codes, each GQC code can be described by an upper triangular generator polynomial matrix, from which the systematic encoder is constructed. In this paper, a complete theory of generator polynomial matrices of GQC codes, including a relation formula between generator polynomial matrices and parity-check polynomial matrices through their equations, is provided. This relation generalizes those of cyclic codes and QC codes. While the previous researches on GQC codes are mainly concerned with 1-generator case or linear algebraic approach, our argument covers the general case and shows the complete analogy of QC case. We do not use Gröbner basis theory explicitly in order that all arguments of this paper are self-contained. Numerical examples are attached to the dual procedure that extracts one from each other. Finally, we provide an efficient algorithm which calculates all generator polynomial matrices with given cyclic intervals.     

Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

On the Cyclicity of Goppa Codes,Parity-Check Subcodes of Goppa Codes,and Extended Goppa Codes

Classical Goppa codes are a special case of Alternant codes. First we prove that the parity-check subcodes of Goppa codes and the extended Goppa codes are both Alternant codes. Before this paper, all known cyclic Goppa codes were some particular BCH codes. Many families of Goppa codes with a cyclic extension have been found. All these cyclic codes are in fact Alternant codes associated to a cyclic Generalized Reed–Solomon code. In (1989, J. Combin. Theory Ser. A 51, 205–220) H. Stichtenoth determined all cyclic extended Goppa codes with this property. In a recent paper (T. P. Berger, 1999, in “Finite Fields: Theory, Applications and Algorithms (R. Mullin and G. Mullen, Eds.), pp. 143–154, Amer. Math. Soc., Providence), we used some semi-linear transformations on GRS codes to construct cyclic Alternant codes that are not associated to cyclic GRS codes. In this paper, we use these results to construct cyclic Goppa codes that are not BCH codes, new families of Goppa codes with a cyclic extension, and some families of non-cyclic Goppa codes with a cyclic parity-check subcode.     

A characterization of cycle-free unit probe interval graphs

A graph is a probe interval graph (PIG) if its vertices can be partitioned into probes and nonprobes with an interval assigned to each vertex so that vertices are adjacent if and only if their corresponding intervals overlap and at least one of them is a probe. PIGs are a generalization of interval graphs introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. PIGs have been characterized in the cycle-free case by Sheng, and other miscellaneous results are given by McMorris, Wang, and Zhang. Johnson and Spinrad give a polynomial time recognition algorithm for when the partition of vertices into probes and nonprobes is given. The complexity for the general recognition problem is not known. Here, we restrict attention to the case where all intervals have the same length, that is, we study the unit probe interval graphs and characterize the cycle-free graphs that are unit probe interval graphs via a list of forbidden induced subgraphs.     

Harsanyi power solutions for graph-restricted games

We consider cooperative transferable utility games, or simply TU-games, with limited communication structure in which players can cooperate if and only if they are connected in the communication graph. Solutions for such graph games can be obtained by applying standard solutions to a modified or restricted game that takes account of the cooperation restrictions. We discuss Harsanyi solutions which distribute dividends such that the dividend shares of players in a coalition are based on power measures for nodes in corresponding communication graphs. We provide axiomatic characterizations of the Harsanyi power solutions on the class of cycle-free graph games and on the class of all graph games. Special attention is given to the Harsanyi degree solution which equals the Shapley value on the class of complete graph games and equals the position value on the class of cycle-free graph games. The Myerson value is the Harsanyi power solution that is based on the equal power measure. Finally, various applications are discussed.     

Some Combinatorial Aspects of Constructing Bipartite-Graph Codes

We propose geometrical methods for constructing square 01-matrices with the same number n of units in every row and column, and such that any two rows of the matrix contain at most one unit in common. These matrices are equivalent to n-regular bipartite graphs without 4-cycles, and therefore can be used for the construction of efficient bipartite-graph codes such that both the classes of its vertices are associated with local constraints. We significantly extend the region of parameters m, n for which there exist an n-regular bipartite graph with 2m vertices and without 4-cycles. In that way we essentially increase the region of lengths and rates of the corresponding bipartite-graph codes. Many new matrices are either circulant or consist of circulant submatrices: this provides code parity-check matrices consisting of circulant submatrices, and hence quasi-cyclic bipartite-graph codes with simple implementation.