Perfect codes for metrics induced by circulant graphs

被引：45

作者：

Martinez, Cannen ^{[1
]}

Beivide, Ramon

Gabidulin, Emst

机构：

[1] Univ Cantabria, Dept Elect & Comp, E-39005 Santander, Spain

[2] Moscow Inst Phys & Technol, Dolgoprudnyi 141700, Russia

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2007年 / 53卷 / 09期

关键词：

circulant graphs; Gaussian integers; perfect codes; quadrature amplitude modulation (QAM) constellations;

D O I：

10.1109/TIT.2007.903126

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

An algebraic methodology for defining new metrics over two-dimensional signal spaces is presented in this work. We have mainly considered quadrature amplitude modulation (QAM) constellations which have previously been modeled by quotient rings of Gaussian integers. The metric over these constellations, based on the distance concept in circulant graphs, is one of the main contributions of this work. A detailed analysis of some degree-four circulant graphs has allowed us to detail the weight distribution for these signal spaces. A new family of perfect codes over Gaussian integers will be defined and characterized by providing a solution to the perfect t-dominating set problem over the circulant graphs presented. Finally, we will show how this new metric can be extended to other signal sets by considering hexagonal constellations and circulant graphs of degree six.

引用

页码：3042 / 3052

页数：11

共 20 条

[1] OPTIMAL DISTANCE NETWORKS OF LOW DEGREE FOR PARALLEL COMPUTERS
BEIVIDE, R
HERRADA, E
BALCAZAR, JL
ARRUABARRENA, A
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (10) : 1109 - 1124
[2] Beivide R., 1987, P 14 ANN INT S COMP, DOI [10.1145/30350.30369, DOI 10.1145/30350.30369]
[3] Berlekamp E. R., 1984, ALGEBRAIC CODING THE
[4] BERMOND JC, 1985, P 3 INT C COMB MATH, P1
[5] RELIABLE CIRCULANT NETWORKS WITH MINIMUM TRANSMISSION DELAY
BOESCH, FT
WANG, JF
[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1985, 32 (12): : 1286 - 1291
[6] LEE DISTANCE AND TOPOLOGICAL PROPERTIES OF K-ARY N-CUBES
BOSE, B
BROEG, B
KWON, Y
ASHIR, Y
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (08) : 1021 - 1030
[7] Graphs, tessellations, and perfect codes on flat tori
Costa, SIR
Muniz, M
Agustini, E
Palazzo, R
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (10) : 2363 - 2377
[8] FIOL MA, 1987, IEEE T COMPUT, V36, P702, DOI 10.1109/TC.1987.1676963
[9] GABIDULIN E, 2005, P 8 INT S COMM THEOR
[10] PERFECT CODES IN LEE METRIC AND PACKING OF POLYOMINOES
GOLOMB, SW
WELCH, LR
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1970, 18 (02) : 302 - +

← 1 2 →