Technical Report
 

Perfect codes, NP-completeness, and Towers of Hanoi graphs

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/technical_reports/cf95jc74q

Descriptions

Attribute NameValues
Creator
Abstract
  • The set of codewords for a standard error-correcting code can be viewed as subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. A code is a perfect-error-correcting code if no two codewords are adjacent and every non-codeword is adjacent to exactly one codeword. Since such a code can be described using only vertices and adjacency, the de finition applies to general graphs rather than only to hypercubes. How does one decide if a graph can support a perfect 1-error-correcting code? The obvious way to show that such a code exists is to display the code. On the other hand, it seems difficult to show that a graph does not support such a code. We show that this intuition is correct by showing that to determine if a graph has a perfect 1-error-correcting code is an NP-complete problem. The proof is by reduction from 3-SAT. To show that perfect codes in graphs is not vacuous, we give an in nite family of graphs so that each graph in the family has a perfect 1-error-correcting code. Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a confi guration of the puzzle and two vertices are adjacent when they are one legal move apart. We give a recursive construction which determines which vertices are codewords. There is a natural correspondence between the hypercube vertices and the binary strings, and there is a natural correspondence between Tower of Hanoi con guration and ternary strings. Our recursive construction also speci es which ternary strings are codewords. We characterize the codewords as the set of ternary strings with an even number of 1's and an even number of 2's. As part of this characterization, we show that there is essentially one perfect 1-error-correcting code for each n. There is a unique code when n is even, but the code is only unique up to a permutation of 0, 1, and 2 when n is odd. We show that error-correction can be accomplished by a nite state machine which passes over the ternary string twice, and that this machine is xed independent of the length of the string. Encoding and decoding are the mappings between integers and codewords, and vice-versa. While algorithms for such mappings can be derived directly from the recursive construction, we show that encoding/decoding can be carried out by multiplication/division by 4 and error-correction. So error-correction, encoding, and decoding can all be done in time θ(n) for code strings of length n in these codes.
Resource Type
Date Available
Date Issued
Series
Subject
Rights Statement
Funding Statement (additional comments about funding)
  • Supported in part by NSF Grant DMS 93-00-281.
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

Items

Thumbnail Title Date Uploaded Visibility Actions
file details Perfect_codes_NP_completeness_and_towers_of_Hanoi_graphs.pdf 2017-07-18 Public Download