Binary Reflected Gray Code

May 2, 2014

An n-bit Gray sequence is a sequence of 2n values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2n−1 n-bit Gray sequences; for instance, the two 2-bit Gray sequences are 0, 1, 3, 2 and 0, 2, 3, 1. It is easier to see the Gray sequences when they are written in binary; the two 2-bit Gray sequences written in binary are 00, 01, 11, 10 and 0,0 10, 11, 01, where it is clear that each element of the sequence differs from the previous one by only one bit.

Although there are many possible Gray sequences for any given number of bits, there is one Gray sequence, known as the binary reflected gray code BRGC, that is almost always the Gray sequence that is being discussed. Such sequences are generated recursively from the next-smaller sequence by reversing the sequence, prefixing the entries of the original sequence with a 0-bit, prefixing the entries of the reversed sequence with a 1-bit, then concatenating the two sequences. For instance, given the 2-bit Gray sequence 00, 01, 11, 10, its reversal is 10, 11, 01, 00, adding a 0-bit to the original gives 000, 001, 011, 010, adding a 1-bit to the reversal gives 110, 111, 101, 100, and concatenating the two gives 000, 001, 011, 010, 110, 111, 101, 100, which is 0, 1, 3, 2, 6, 7, 5, 4.

Your task is to write a function that generates an n-bit binary reflected Gray sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

8 Responses to “Binary Reflected Gray Code”

  1. JP said

    Misread at first, so I did it in binary lists rather than decimal, but it’s straight forward enough to convert.

    ; Generate a list of binary lists representing a binary reflected gray code
    (define (binary-reflected-gray-code/binary-list bits)
      (cond
        [(zero? bits) '(())]
        [else
         (define rest (binary-reflected-gray-code/binary-list (- bits 1)))
         (append (map (curry cons 0) rest)
                 (map (curry cons 1) (reverse rest)))]))
    
    ; Convert a list of binary digits to decimal
    (define (binary-list->decimal ls)
      (let loop ([ls ls] [acc 0])
        (cond
          [(null? ls) acc]
          [else (loop (cdr ls) (+ (* 2 acc) (car ls)))])))
    
    ; Generate a list of n-bit decimal numbers using a binary reflected gray code
    (define (binary-reflected-gray-code/decimal bits)
      (map binary-list->decimal (binary-reflected-gray-code/binary-list bits)))
    

    (pfft efficiency…)

  2. Globules said

    In Haskell:

    import Control.Monad
    import Data.Bits
    import Numeric
    import Text.Printf
    
    -- The n'th BRGC.  From Warren's "Hacker's Delight", 2nd ed.
    gray :: Integer -> Integer
    gray n = (n `shiftR` 1) `xor` n
    
    nBitGrays n = [gray (i-1) | i <- [1..2^n]]
    
    printGrays n = mapM_ (printf "%0*s\n" n . base2) $ nBitGrays n :: IO ()
      where base2 n = showIntAtBase 2 ("01" !!) n ""
    

    Running it in ghci:

    *Main> printGrays 3
    000
    001
    011
    010
    110
    111
    101
    100
    *Main> 
    
  3. chmllr said
    (defn step [elems]
      (let [zero-prefixed (map #(str "0" %) elems)
            reversed (reverse elems)
            one-prefixed (map #(str "1" %) reversed)]
        (concat zero-prefixed one-prefixed)))
    
    (defn get-BRGC [n]
      (loop [i 1 elems ["0" "1"]]
        (if (= i n) elems
          (recur (inc i) (step elems)))))
    

    (no handling for 0-bit sequence!)

  4. chmllr said

    After looking into your code, I realized that I misunderstood the exercise as well: numbers ant not bit strings are required. After re-thinking my solution I boiled down all string manipulations to algebraic operations and got pretty much your solution:

    (defn brgc [n]
      (loop [i 0 xs [0] P 1]
        (if (= i n) xs
          (recur (inc i)
                 (concat xs (map #(+ P %) (reverse xs)))
                 (+ P P)))))
    
  5. Mike said

    A recursive version:

    [sourcecodelang="python"]
    def brgc(n):
    if n == 1:
    return [0, 1]
    else:
    val = brgc(n-1)
    bit = 1 << (n-1)
    return val + [bit+v for v in reversed(val)]
    [/sourcecode]

    And an iterative version:

    def brgc(n):
    gc = [0]
    for b in (1<<i for i in range(n)):
    gc.extend(c+b for c in reversed(gc))
    return gc

  6. Mike said

    With proper formatting this time.

    A recursive version:

    def brgc(n):
        if n == 1:
            return [0, 1]
        else:
            val = brgc(n-1)
            bit = 1 << (n-1)
            return val + [bit+v for v in reversed(val)]
     

    And an iterative version:

    def brgc(n):
        gc = [0]
        for b in (1<<i for i in range(n)):
            gc.extend(c+b for c in reversed(gc))
        return gc
    
  7. matthew said

    Here’s another nice bit-twiddling solution – the ruler function (number of trailing 0s) for i+1 tells us which bit to flip to get the i+1th gray code:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char *argv[])
    {
      int n = 1 << atoi(argv[1]);
      int k = 0;
      for (int i = 0; i<n; i++) {
        printf("%d\n", k);
        int r = (i+1)&~i;
        k ^= r;
      }
    }
    

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

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: