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