Generating Error-Correcting Codes based on Tower of Hanoi Configuration Graphs

被引:0
作者
Voloch, Nadav [1 ]
Birnbaum, Elazar [1 ]
Sapir, Amir [2 ]
机构
[1] Open Univ, Dept Comp Sci, Raanana, Israel
[2] Sapir Acad Coll, Dept Comp Sci, Shaar Hanegev, Israel
来源
2014 IEEE 28TH CONVENTION OF ELECTRICAL & ELECTRONICS ENGINEERS IN ISRAEL (IEEEI) | 2014年
关键词
Error Correcting Codes; Non-Linear Codes; Codes on Graphs; Dominating set; Tower of Hanoi;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
There are several researches that base codes on graphs. Some of them in particular present a code based on graphs, choosing a subset of the vertices as representing the code, and considering it, to a certain extent, as a minimal dominating set. If an error occurs, the string received corresponds to a vertex that is adjacent to precisely one code-word. The decision taken by the above-mentioned scheme does not adhere to the Hamming distance. In this research we have devised an 'inflating' algorithm for the graph for specific string lengths, which remedies this problem. Furthermore, we have established a lower bound on the length of the inflation. Correcting an erroneous word now amounts to a local search among its neighbors, assuming we have a suitable data structure to represent the graph, and the ability to reach the vertex corresponding to that word quickly.
引用
收藏
页数:4
相关论文
共 50 条
[41]   On error-correcting fingerprinting codes for use with watermarking [J].
Hans Georg Schaathun .
Multimedia Systems, 2008, 13 :331-344
[42]   Introduction to Quantum Deletion Error-Correcting Codes [J].
Hagiwara, Manabu .
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2025, E108A (03) :363-375
[43]   Influences of some families of error-correcting codes [J].
Egan, Hailey ;
Legrow, Jason T. ;
Matthews, Gretchen L. ;
Suliga, Jeff .
INVOLVE, A JOURNAL OF MATHEMATICS, 2025, 18 (02) :329-349
[44]   On the cardinality of systematic authentication codes via error-correcting codes [J].
Kabatianskii, GA ;
Smeets, B ;
Johansson, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1996, 42 (02) :566-578
[45]   Binary Error-Correcting Codes with Minimal Noiseless Feedback [J].
Gupta, Meghal ;
Guruswami, Venkatesan ;
Zhang, Rachel Yun .
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, :1475-1487
[46]   Recent results on ring constructions for error-correcting codes [J].
Alfaro, R ;
Kelarev, A .
ALGEBRAIC STRUCTURES AND THEIR REPRESENTATIONS, 2005, 376 :1-12
[47]   CHARACTER SUM CONSTRUCTIONS OF CONSTRAINED ERROR-CORRECTING CODES [J].
LITSYN, S ;
TIETAVAINEN, A .
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 1994, 5 (01) :45-51
[48]   Genetic design of linear block error-correcting codes [J].
Barbieri, Alan ;
Cagnoni, Stefano ;
Colavolpe, Giulio .
Biological and Artificial Intelligence Environments, 2005, :107-116
[49]   LATTICES FROM ABELIAN EXTENSIONS AND ERROR-CORRECTING CODES [J].
Interlando, J. Carmelo ;
da Nobrega Neto, Trajano Pires ;
Lopes Nunes, Jose Valter ;
Dantas Lopes, Jose Othon .
ROCKY MOUNTAIN JOURNAL OF MATHEMATICS, 2021, 51 (03) :903-920
[50]   Gallager error-correcting codes for binary asymmetric channels [J].
Neri, I. ;
Skantzos, N. S. ;
Bolle, D. .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,