上海交通大学学报：英文版

Self-dual Codes Defined on Factor Graphs

汪辉松, 汪隽, Qun Du, 曾贵华

Published Jan 1, 2007• 0 citations

Abstract

A definition of a self-dual code on graph and a procedure based on factor graphs to judge a self-dual code were presented. Three contributions of this paper were described as follows. To begin with, transform T_ R→L were defined, which was the basis of self-dual codes defined on graphs and played a key role in the paper. The second were that a self-dual code could be defined on factor graph, which was much different from conventional algebraic method. The third was that a factor graph approach to judge a self-dual code was illustrated, which took advantage of duality properties of factor graphs and our proposed transform T_ R→L to offer a convenient and geometrically intuitive process to judge a self-dual code.

Related papers

On Factor Graphs and the Fourier Transform

Yongyi Mao, Frank R. Kschischang

We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to "syndrome realizations" of codes, just as multiplicative factor graphs with auxiliary variables give rise to "state realizations." We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient. We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case.

IEEE Transactions on Information TheoryApr 25, 200544 citations

Low Complexity Tail-Biting Trellises for Some Extremal Self-Dual Codes

Grégory Olocco, Ayoub Otmani

We obtain low complexity tail-biting trellises for some extremal self-dual codes for various lengths and fields such as the [12,6,6] ternary Golay code and a [24,12,8] Hermitian self-dual code over GF(4). These codes are obtained from a particular family of cyclic Tanner graphs called necklace factor graphs.

Sep 8, 20020 citations

The Quantum States of a Graph

Mohd Arif Raza, Adel N. Alahmadi, Widyan Basaffar +6 more

Quantum codes are crucial building blocks of quantum computers. With a self-dual quantum code is attached, canonically, a unique stabilised quantum state. Improving on a previous publication, we show how to determine the coefficients on the basis of kets in these states. Two important ingredients of the proof are algebraic graph theory and quadratic forms. The Arf invariant, in particular, plays a significant role.

MathematicsMay 16, 20231 citation

On the classification of Hermitian self-dual additive codes over GF(9)

Lars Eirik Danielsen

Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of length 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of length 11 and 12. There are 56,005,876 (11,3^11,5) codes and 6493 (12,3^12,6) codes. We also find the smallest codes with trivial automorphism group.

arXiv:1106.2428Jun 13, 20110 citations

On Self-Dual Quantum Codes, Graphs, and Boolean Functions

Lars Eirik Danielsen

A short introduction to quantum error correction is given, and it is shown that zero-dimensional quantum codes can be represented as self-dual additive codes over GF(4) and also as graphs. We show that graphs representing several such codes with high minimum distance can be described as nested regular graphs having minimum regular vertex degree and containing long cycles. Two graphs correspond to equivalent quantum codes if they are related by a sequence of local complementations. We use this operation to generate orbits of graphs, and thus classify all inequivalent self-dual additive codes over GF(4) of length up to 12, where previously only all codes of length up to 9 were known. We show that these codes can be interpreted as quadratic Boolean functions, and we define non-quadratic quantum codes, corresponding to Boolean functions of higher degree. We look at various cryptographic properties of Boolean functions, in particular the propagation criteria. The new aperiodic propagation criterion (APC) and the APC distance are then defined. We show that the distance of a zero-dimensional quantum code is equal to the APC distance of the corresponding Boolean function. Orbits of Boolean functions with respect to the {I,H,N}^n transform set are generated. We also study the peak-to-average power ratio with respect to the {I,H,N}^n transform set (PAR_IHN), and prove that PAR_IHN of a quadratic Boolean function is related to the size of the maximum independent set over the corresponding orbit of graphs. A construction technique for non-quadratic Boolean functions with low PAR_IHN is proposed. It is finally shown that both PAR_IHN and APC distance can be interpreted as partial entanglement measures.

arXiv:quant-ph/0503236Mar 31, 200530 citations

On Connections Between Graphs, Codes, Quantum States, and Boolean Functions

Lars Eirik Danielsen

We study objects that can be represented as graphs, error-correcting codes, quantum states, or Boolean functions. It is known that self-dual additive codes, which can also be interpreted as quantum states, can be represented as graphs, and that two codes are equivalent when the corresponding graphs are equivalent with respect to local complementation (LC). We give classifications of such codes. Circulant graph codes are introduced, and it is shown that some of these codes have highly regular graph representations. We show that the orbit of a bipartite graph under edge local complementation (ELC) corresponds to the equivalence class of a binary linear code. We classify ELC orbits, give a new method for classifying binary linear codes, and show that the information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. Self-dual additive codes over GF(4) can also be interpreted as quadratic Boolean functions. In this context we define PARIHN, peak-to-average power ratio with respect to the {I, H, N}n transform, and prove that PARIHN equals the size of the maximum independent set over the associated LC orbit of graphs. We define the aperiodic propagation criteria (APC) of a Boolean function, and show that it is related to the minimum distance of a self-dual additive code over GF(4), and to the degree of entanglement in the associated quantum state. We give a generalization to non-quadratic Boolean functions, and relate APC to known cryptographic criteria. Interlace polynomials encode many properties of the LC and ELC orbits of a graph. We enumerate interlace polynomials and circle graphs, show that there exist non-unimodal interlace polynomials, and relate properties of interlace polynomials to properties of codes and quantum states. We define self-dual bent functions, and provide constructions and classifications.

May 28, 20083 citations