Binary Reflected Gray Code

May 2, 2014

This is a simple recursion on sequences represented as lists, with the sequence (0) as the recursive base:

(define (gray n)
  (define (add x) (lambda (y) (+ x y)))
  (let loop ((n n) (g 1) (gs (list 0)))
    (if (zero? n) gs
      (loop (- n 1) (+ g g)
            (append gs (map (add g) (reverse gs)))))))

The magic is in the last line. The next-smaller sequence is in variable gs, which is reversed, then the next-larger power-of-two, which is accumulated in variable g, is added to each item of the reversed sequence, and finally the two lists are appended. The add function is a curried form of addition. Here are the first several Gray sequences:

> (gray 0)
(0)
> (gray 1)
(0 1)
> (gray 2)
(0 1 3 2)
> (gray 3)
(0 1 3 2 6 7 5 4)
> (gray 4)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8)
> (gray 5)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
 28 20 21 23 22 18 19 17 16)
> (gray 6)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63
 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33
 32)
> (gray 7)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63
 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33
 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105
 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115
 113 112 80 81 83 82 86 87 85 84 92 93 95 94 90 91 89 88 72
 73 75 74 78 79 77 76 68 69 71 70 66 67 65 64)

Since the n-bit Gray sequence is embedded in the first half of the n+1-bit Gray sequence, it makes sense to talk about the kth element of the binary reflected Gray sequence, irrespective of the bit length. The kth element of the Gray sequence is k ⊕ ⌊k / 2⌋,where ⊕ is the logical xor operator, which can be expressed simply in C as (k >> 1) ^ k. Thus, here is another way to write the n-bit gray sequence:

(define (nth-gray n) (bitwise-xor n (ash n -1)))

(define (gray n)
  (do ((k 0 (+ k 1)) (gs (list) (cons (nth-gray k) gs)))
      ((= k (expt 2 n)) (reverse gs))))

> (nth-gray 0)
0
> (nth-gray 1)
1
> (nth-gray 2)
3
> (nth-gray 3)
2
> (nth-gray 4)
6
> (nth-gray 5)
7
> (nth-gray 6)
5
> (nth-gray 7)
4

You can run the program at http://programmingpraxis.codepad.org/ndutMKZE.

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 615 other followers

%d bloggers like this: