Gray code

Eric Amundsen

A gray code is a way to order numbers such that only one bit changes per increment. For instance, a 3 bit gray code :

 0 - 000
 1 - 001
 3 - 011
 2 - 010
 6 - 110
 7 - 111
 5 - 101
 4 - 100

This type of code is often used when designing analog to digital convertors (ADC). I developed this piece of code in order to map the output of an ADC to regular binary for post-processing.


        ###############################################################################
        # 
        #        proc grayCodeServer
        # 
        #         Description
        #         Use the following equation to generate an n bit gray code.
        #         
        #               / 0
        #         G1 = <
        #               \ 1
        # 
        #               /0 . Gn-1
        #         Gn = <
        #               \ 1 . reverse(Gn-1)
        # 
        #         where the . operator denotes concatenation, and the reverse function is
        #         simply denotes the Gray code in revers (i.e. G1 = (0, 1);
        #         reverse(G1) = (1, 0)).
        # 
        #         Arguments
        #        numBits - the number of bits.  The list returned is 2^numBits long
        # 
        #         Return value
        #        A list, where the value at the index of the list is the gray code value
        #        for that index value
        # 
        ###############################################################################
        proc grayCodeServer {numBits} {
                # return a list 2^numBits long, where [lindex grayValue $list] will
                # correspond to the decimal equivalent

                # Initialize the previous Gray code to a 1 bit code (0, 1).
                set grayCodeMinus1 [list 0 1]

                # Set the Gray code equal to a 1 bit Gray code.  If the numBits passed in
                # is greater than 1, then this will get expanded properly, but the first
                # half of the next Gray code is always the same as the previous Gray code.
                set grayCode $grayCodeMinus1

                # Loop through to the number of bits passed in, each time building the
                # Gray code from the previous Gray code according to the function
                # outlined above.:
                for {set j 1} {$j < $numBits} {incr j} {

                        # The first half of the list is already valid from the previous pass
                        # through this loop.
                        # Keep a counting for going through the previous Gray code in
                        # reverse.
                        for        {set k [expr {[llength $grayCodeMinus1] - 1}]}        \
                                {$k >= 0}        \
                                {incr k -1} {

                                # Shift 1 the number of bits that we're currently building the
                                # Gray code for, and OR this with the reverse of the previous
                                # Gray code.
                                lappend grayCode [expr {(1 << $j) | [lindex $grayCodeMinus1 $k]}]

                        }

                        # Make the previous gray code equal to the new one.
                        set grayCodeMinus1 $grayCode
                }

                return $grayCode
        }

        # demo code
        if 0 {
                for {set j 1} {$j <= 8} {incr j} {
                        puts "$j bit gray code : "
                        foreach v [grayCodeServer $j] {
                                puts [format "%0.2X" $v]
                        }
                }
        }

DKF: Here's a more functional version, through the use of a helper based on lmap and some ideas relating to currying:

proc map {lambda args} {
    set result {}
    foreach item [lindex $args end] {
        lappend result [apply $lambda {*}[lrange $args 0 end-1] $item]
    }
    return $result
}
proc grayCode bits {
    set code {0 1}
    set append {{bit item} {append item $bit}}
    for {set i 1} {$i < $bits} {incr i} {
        set code [concat [map $append 0 $code] [map $append 1 [lreverse $code]]]
    }
    return $code
}