Here, we use Wolfram's definition for numbered Boolean functions of a (usually small) input space. We define the i-th Boolean function of a m-bit input space as follows:
f(i) = sum^{k-1}_{j=0} 2^j * alpha_j (Equation 1)where the alpha_i are the digits of the juxtaposed binary representation of i, and k=2^m. The resulting Boolean function is evaluated as a lookup operation to access a particular alpha. Since any m-bit pattern falls in the binary range [0,k], we are really just saying that when we evaluate fi at u (where u is a decimal representation of the binary input space over [0,k]), we are simply looking up alpha_u. So, using three-digit Boolean functions as an example, the function AND is 128, because the binary representation of 128 is 1000000, and
f_i = 128 = 2^0*0 + 2^1*0 + 2^2*0 + 2^3*0 + 2^4*0 + 2^5*0 + 2^6*0 + 2^7*1
We can define BoolN as the accessor function simply as
BoolN(f_i,u) = alpha_u (Equation 2)
We can use the list manipulation properties of TCL to conveniently manipulate Boolean functions using this scheme. We first define a procedure binVal, which simply converts a decimal number to a broken-out list of binary digits (bits). The length of the binary list must also be specified.
# Returns a binary representation of a
# decimal number, where the binary number
# is a string of space-delimited ones and
# zeroes, running from left to right. The
# size of the output string is specified as
# second argument.
#
# ex. binVal 33 8 -> "0 0 1 0 0 0 0 1"
#
proc binVal { n m } {
set temp $n
set result { }
for {set i [expr $m-1] } { $i >=0 } { incr i -1 } {
set base [expr int(pow(2,$i)) ]
if [ expr $temp - $base >= 0 ] {
set temp [ expr $temp - $base ]
lappend result "1"
} else {
lappend result "0"
}
}
return $result
}So, the test example in the comments section should produce the expected result
% binVal 33 8
0 0 1 0 0 0 0 1
This simple routine does no error checking, so if the specified list length is too short (too long is just fine), then the result is erroneous but no warning is issued.
% binVal 33 3
1 1 1
The version of binVal in which the digit order is mirrored could be useful. The name of this routine is simply binValRev
# Returns a binary representation of a
# decimal number, where the binary number
# is a string of space-delimited ones and
# zeroes, running from RIGHT-to-LEFT. The
# size of the output string is specified as
# second argument.
#
# ex. binValRev 33 8 -> "1 0 0 0 1 0 0"
#
proc binValRev { n m } {
set temp $n
set result { }
for {set i [expr $m-1] } { $i >=0 } { incr i -1 } {
set base [expr int(pow(2,$i)) ]
if [ expr $temp - $base >= 0 ] {
set temp [ expr $temp - $base ]
set result [ linsert $result 0 "1"]
} else {
set result [ linsert $result 0 "0"]
}
}
return $result
}The inverse version of these procedures are simply named binCon and binConRev. Unlike binVal (binValRev), these procedures do not employ explicit length in their calling arguments.
# Returns a decimal representation of a space-
# delimited left-to-right string of ones and
# zeroes. Argument 'x' is in TCL list form
#
# ex. binCon "1 0 1 1" -> 11
#
proc binCon { x } {
set result 0
set len [ llength $x ]
set base [expr int(pow(2,$len-1)) ]
foreach member $x {
if { $member == "1" } {
set result [ expr $result + $base ]
}
set base [ expr $base / 2 ]
}
return $result
}
# Returns a decimal representation of a space-
# delimited RIGHT-to-LEFT string of ones and
# zeroes. Argument 'x' is in TCL list form
#
# ex. binConRev "1 0 1 1" -> 13
#
proc binConRev { x } {
set base 1
set result 0
foreach member $x {
if { $member == "1" } {
set result [ expr $result + $base ]
}
set base [ expr $base + $base ]
}
return $result
}This set of procedures allow the definition of a compact procedure to implement Equation 2:
proc boolN {fnum xLis} {
set n [llength $xLis]
lindex [binValRev $fnum [expr int(pow(2,$n))]] [binCon $xLis]
}So, we can evaluate the 3-input AND function (3AND) as
% boolN 128 "1 1 1"
1
To verify correctness, we can generate all values (minterms) of three-inputs:
foreach i "0 1" {
foreach j "0 1" {
foreach k "0 1" {
puts "$i$j$k [boolN 128 "$i $j $k"]"
}
}
}
000 0
001 0
010 0
011 0
100 0
101 0
110 0
111 1This also works for smaller input spaces (this is the result for 2AND)
foreach i "0 1" {
foreach j "0 1" {
puts "$i$j [boolNR 8 "$i $j"]"
}
}
00 0
01 0
10 0
11 1and larger input spaces (4AND)
foreach i "0 1" {
foreach j "0 1" {
foreach k "0 1" {
foreach m "0 1" {
puts "$i$j$k$m [boolN [expr pow(2,15)] "$i $j $k $m"]"
}
}
}
}
0000 0
0001 0
0010 0
0011 0
0100 0
0101 0
0110 0
0111 0
1000 0
1001 0
1010 0
1011 0
1100 0
1101 0
1110 0
1111 1We can do more powerful things compactly, such as verifying all valuations of all functions of 2-inputs:
for {set u 0} {$u < 16} {incr u} {
foreach i "0 1" {
foreach j "0 1" {
puts -nonewline [boolN $u "$i $j" ]
}
};
puts ""
}
0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111This output simply looks like a bit-reversed count of Boolean numbers from 0 to 15, but in fact represents the evaluation of all possible 2-input functions for all input combinations. There are of course only 2^2^2 = 16 functions of 2 variables, and only four input combinations of 2-inputs (00,01,10, and 11).
The three and four-input versions of this code are straightforward:
for {set u 0} {$u < 255} {incr u} {
foreach i "0 1" {
foreach j "0 1" {
foreach k "0 1" {
puts -nonewline [boolN $u "$i $j $k" ]
}
}
}
puts ""
}will perform all eight three-input evaluations of all 255 functions of three input variables for example, for a total of 1,024 evaluations. The five-input version is just as easy to compose as a single line of TCL code
for {set u 0} {$u < [expr pow(2,32)] } {incr u} {
foreach i "0 1" {
foreach j "0 1" {
foreach k "0 1" {
foreach m "0 1" {
foreach n "0 1" {
puts -nonewline [boolN $u "$i $j $k $m $n" ]
}
}
}
}
}
puts ""
}Don't try this example for real, as it will perform 2^5=32 evaluations on all ~4 billion functions of five input variables, which might take a week or two on a fast machine. By the time the six-input case completes, the sun may well be extinguished and life as we know it non-existent, so know one will be around to care or comment.
Why is this / might this be useful?
The main application of these routines is in experimental Boolean synthesis, in which we look for alternative ways to decompose and represent complex functions. In field programmable gate arrays, Boolean synthesis is routinely performed to take apart and re-represent complex VHDL or Verilog code in terms of many primitive functions. Primarily, this involves binary decision diagrams and/or Boolean division manipulations to identify compact ways to implement the equivalent circuit forms of the code.
Another application of these routines is in the implementation of cellular automata (CA), which was Stephen Wolfram's primary interest. A full explanation of CA is beyond the scope of this note (see the reference), but it is simple to think of it as a line of points (the 1-D case), each having a value of 0 or 1. The values change at each time, and they change according to a rule, which is nothing more than a Boolean function. Wolfram used Equation 1 as a shorthand to permit the exhaustive study of CA structures. We can describe a simple set of procedures to recreate his early CA structures. We call these 'elementary CA', because they only employ three-input functions, of which there are 255 possibilities.
To do this, it is only necessary to create a binary array and apply a simple Boolean function at each point in the array, using the left and right neighbors to supply the other two inputs of a three input function. Together the three inputs are evaluated as one of 255 functions, and a next value is computed for this point. This exercise is repeated down the line until each point in the array is computed with an identical array of new 'next values'. After this, the original array is replaced. This cycle can be repeated forever if one desires, and Wolfram did discover many wonderful patterns.
Here, we define an initialization routine and a stepping routine for examining the CA interactively on a TCL console
# This implements a simple inline 1D-CA stripchart
# two routines required cAInit and cAStep
proc cAInit { x } {
global ca len
for {set i 0} {$i < [set len [llength $x]] } {incr i} {
set ca($i) [lindex $x $i]
}
set ca(-1) 0
set ca($len) 0
return ""
}
proc cAStep { f n } {
global ca len
for {set u 0} {$u < $n} {incr u} {
set x ""
for {set i 0 } {$i < $len} {} {
set v($i) [boolN $f "$ca([expr $i-1]) /
$ca($i) $ca([incr i])"]
}
for {set i 0 } {$i < $len} {incr i} {
set ca($i) $v($i)
if {$ca($i) == 1} {
lappend x $ca($i)
} else {
lappend x "."
}
}
puts $x
}
return ""
}Starting a CA structure involves calling cAInit with a string of ones and zeros. It is useful to begin with a single string of zeros having a single seed 1 in the center
cAInit "0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
From here, one simply calls cAStep with two arguments. The first argument is a function number specifying any three-input Boolean function, as discussed before. The second argument is the number of cycles to advance the CA structure. A line of output is produced for each cycle, representing the evolution of the CA after the many local evaluations. For visualization, the 0's are replaced by periods.
Here is an example for rule number (Boolean function number) 150, which corresponds to the application of exclusive OR at each point in the array. This example is run for 100 steps:
cAStep 150 10
. 1 1 . 1 1 . . . 1 1 . 1 1 . 1 1 . 1 1 . . . 1 1 . 1 1 .
1 . . . . . 1 . 1 . . . . . . . . . . . 1 . 1 . . . . . 1
1 1 . . . 1 1 . 1 1 . . . . . . . . . 1 1 . 1 1 . . . 1 1
. . 1 . 1 . . . . . 1 . . . . . . . 1 . . . . . 1 . 1 . .
. 1 1 . 1 1 . . . 1 1 1 . . . . . 1 1 1 . . . 1 1 . 1 1 .
1 . . . . . 1 . 1 . 1 . 1 . . . 1 . 1 . 1 . 1 . . . . . 1
1 1 . . . 1 1 . 1 . 1 . 1 1 . 1 1 . 1 . 1 . 1 1 . . . 1 1
. . 1 . 1 . . . 1 . 1 . . . . . . . 1 . 1 . . . 1 . 1 . .
. 1 1 . 1 1 . 1 1 . 1 1 . . . . . 1 1 . 1 1 . 1 1 . 1 1 .
Here is a more extended evaluation using rule 110, which Wolfram later proved (in A New Kind of Science) to be capable of 'Turing-complete' computation:
cAInit "0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
cAStep 110 25
. . . . . . . . . . . . . 1 1 . . . . . . . . . . . . . .
. . . . . . . . . . . . 1 1 1 . . . . . . . . . . . . . .
. . . . . . . . . . . 1 1 . 1 . . . . . . . . . . . . . .
. . . . . . . . . . 1 1 1 1 1 . . . . . . . . . . . . . .
. . . . . . . . . 1 1 . . . 1 . . . . . . . . . . . . . .
. . . . . . . . 1 1 1 . . 1 1 . . . . . . . . . . . . . .
. . . . . . . 1 1 . 1 . 1 1 1 . . . . . . . . . . . . . .
. . . . . . 1 1 1 1 1 1 1 . 1 . . . . . . . . . . . . . .
. . . . . 1 1 . . . . . 1 1 1 . . . . . . . . . . . . . .
. . . . 1 1 1 . . . . 1 1 . 1 . . . . . . . . . . . . . .
. . . 1 1 . 1 . . . 1 1 1 1 1 . . . . . . . . . . . . . .
. . 1 1 1 1 1 . . 1 1 . . . 1 . . . . . . . . . . . . . .
. 1 1 . . . 1 . 1 1 1 . . 1 1 . . . . . . . . . . . . . .
1 1 1 . . 1 1 1 1 . 1 . 1 1 1 . . . . . . . . . . . . . .
1 . 1 . 1 1 . . 1 1 1 1 1 . 1 . . . . . . . . . . . . . .
1 1 1 1 1 1 . 1 1 . . . 1 1 1 . . . . . . . . . . . . . .
1 . . . . 1 1 1 1 . . 1 1 . 1 . . . . . . . . . . . . . .
1 . . . 1 1 . . 1 . 1 1 1 1 1 . . . . . . . . . . . . . .
1 . . 1 1 1 . 1 1 1 1 . . . 1 . . . . . . . . . . . . . .
1 . 1 1 . 1 1 1 . . 1 . . 1 1 . . . . . . . . . . . . . .
1 1 1 1 1 1 . 1 . 1 1 . 1 1 1 . . . . . . . . . . . . . .
1 . . . . 1 1 1 1 1 1 1 1 . 1 . . . . . . . . . . . . . .
1 . . . 1 1 . . . . . . 1 1 1 . . . . . . . . . . . . . .
1 . . 1 1 1 . . . . . 1 1 . 1 . . . . . . . . . . . . . .
1 . 1 1 . 1 . . . . 1 1 1 1 1 . . . . . . . . . . . . . .
This really only scratches the surface of an immensely fascinating subject. The reader should really check out Wolfram's work for more details. This is easy now since Wolfram posted the entire (!) book at his website
http://www.stephenwolfram.com
. (Since it's well over 1,000 pages, it is still easier to just buy the book if you want to read the whole thing.)
Discussion edit
SMH 2005-04-13: attempted some repair work on mangled single quotes
See also edit
