Generating error-correcting codes based on tower of Hanoi configuration graphs
Nadav Voloch, Elazar Birnbaum, Amir Sapir · 2014
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.