I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the Binary Reflected Gray Code and the Recursive Partition Gray Code), but I need to be able to construct one given any two strings as described above. Is there a way to do this? Or a result that guarantees that this is possible? I am almost certain it is, but haven't been able to find anything.
Asked By : user340082710
Answered By : D.W.
Yes. It's always possible, if $s,t$ are at hamming distance one from each other. Let $s,t$ be your two strings at distance one from each other. Then there exists a Gray code sequence where they are adjacent in the Gray code sequence, say $s$ appears right before $t$. Now you immediately obtain a valid solution. Find where $t$ appears in the Gray code sequence, and start going through strings in the Gray code sequence until you get back to $s$. This will have the property you want, as a Gray code sequence is a cyclic sequence where every adjacent pair of strings has hamming distance one.
How do you find that Gray code sequence? There are many possible methods, but here's one easy one. Note that if you have a mapping $f$ on strings that permutes the order of the bits, and you apply $f$ to each element of a Gray code sequence, you obtain another Gray code sequence. The same is true for a mapping $g(x)=x\oplus c$ that xors the input with a constant string $c$. These two facts are enough. Start with any Gray code sequence of your choice; let its first two strings be $a,b$. Let $s,t$ be your two strings that have Hamming distance one. Now you can choose $f,g$ so that $g(f(a))=s$ and $g(f(b))=t$ (namely, choose $f$ to move the bit position where $s,t$ differ to the bit position where $a,b$ differ; and then choose $g(x)=f(a) \oplus s$). This choice of $f,g$ induces a new Gray code sequence: you start with your original Gray code sequence, and apply $f$ to each element of it, then apply $g$ to the result of it. The result is a new Gray code sequence whose first two elements are $s,t$. Thus, if you can iterate through the original Gray code sequence, you now have an easy way to iterate through the new Gray code sequence: you just start iterating at its 3rd element, skipping its first two elements (which will be $s,t$).
The requirement that $s,t$ have Hamming distance one is critical, as otherwise there is a trivial counterexample. Consider 2-bit strings. Suppose the two strings you already have are 00 and 11. Then you want to visit the two strings 01 and 10. However, it doesn't matter what order you visit them in: you won't obtain a solution of the form you want. In particular, there are only two possible sequences (01,10 or 10,01), and neither one has the hamming-distance-one property you wanted.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41231
0 comments:
Post a Comment
Let us know your responses and feedback