//
you're reading...
Uncategorized

Generating Gray Codes and deBruijn Sequences

Screen Shot 2015-03-31 at 8.13.16 AM

 

Gray Codes

Gray codes are min-change sequences of bit-strings where each successive string is obtained by making a single bit change. The Binary Reflected Gray Code is obtained by changing bits according to the same sequence as the solution to the Towers of Hanoi. BRGC can also be obtained recursively by reversing the code generated in each successive sequence while adding or prepending 0 to first half and prepending 1 on second half.

http://pastebin.com/Mg1uPpgm

(defn towers [n]
  (cond
   (= n 1 ) (list  1)
   :else
   (concat (towers (dec n)) (list n) (towers (dec n)))))

(defn gray [n]
  (cond
   (= n 1) '((0) (1))
   :else   (let [first  (map (fn[s] (cons 0 s)) (gray (dec n)))
                 second (map (fn[s] (cons 1 s)) (reverse (gray (dec n))))]
                (concat first second))))
(gray 3)

(defn rank 
    (cond
        (empty? code) 0
        :else  (cond  (= 0 (first code ))   (rank (rest code))
                      :else  (dec  (-  (Math/pow 2 (count code))  (rank 

(rank '( 1 1 0))
#=> 4

DeBruin Sequences of order-n is string of 2^n-bits so that every n-bit string can be located as a substring (allowing wrap around). There are 2^(2^(n-1)-n) different sequences with this property.

More generally, a k-ary De Bruijn sequence B(kn) of order n, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in appears as a sequence of consecutive characters exactly once.

Each B(kn) has length kn.

There are \dfrac{\left(k!\right)^{k^{n-1}}}{k^n} distinct De Bruijn sequences B(kn).

 

The De Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional De Bruijn graph over k symbols (or equivalently, a Eulerian cycle of a (n − 1)-dimensional De Bruijn graph).

320px-De_bruijn_graph-for_binary_sequence_of_order_4.svg

 

Code for Generating Debruijn Sequences

def comp(a):
    return str(1-int(a))

from operator import xor        

def xor_reduce(x):
    #in string --> out bool
    return reduce(xor, map(int, x))

def xor_iscan(x):
    return ''.join(str(xor_reduce(x[:i]))
                   for i in range(1, len(x)+1))

def nextDeB(w, i, k):
      C = xor_iscan(w);
      Cbar ="".join(comp(a) for a in  C)
      part1 = C[: i - k]
      part2 = Cbar[i - 1 + k:]
      part3 = Cbar[: i - 1 + k]
      part4 = C[i - k:]
      return part1 + part2 + part3 + part4

def GenDeB (x):
    if len(x) == 0:
      return "1100"
    elif len(x) == 1:
        if x[0] == '0':
            return "10111000"
        else:
            return "11101000"
    else:
        return nextDeB(GenDeB(x[:-1]), 2**len(x)+(-1)**int(x[-2]), int(x[-1]))

print GenDeB('10001010011')

The call GenDeB('10001010011') produces a string (image at the top) of an order-13 debruijn sequence of length 8192 = 2^13. The function GenDeB will produce 2^11 such sequences one for each 11-bit string used as argument.

Another method to generate deBruijn Sequences
A simple method to remember is called "prefer 1s". The idea is that you start with all 0s then always prefer to append 1, but if it leads to a redundancy in the sequence you opt instead for a 0. Hence, consider the following prefer 1 sequence 00011101 - this is a deBruin sequence.

def prefer1(n):
    myd=set()
    state=0
    while True:
        trans= (2*state +1) % (1<<n)
        if trans not in myd:
            myd.add(trans)
            yield '1'
        else:
            trans-=1
            yield '0'
        state= trans
        if state==0:
                break

for i in prefer1(4):
        print i,
#=>1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0

# to eliminate spaces we have the following
import sys
for i in prefer1(6):
       sys.stdout.write(i)
#=>1111110111100111010111000110110100110010110000101010001001000000

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: