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
}