Updated 2011-12-15 10:11:54 by dkf

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 convertor]s (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
}```