Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 238

6.1 Straight-Line Programs
Straight-line programs (SLP) are defined in Section 2.2 . Each SLP step is an input, compu-
tation, or output step. The notation ( s READ x ) indicates that the s th step is an input step on
which the value x is read. The notation ( s OUTPUT i ) indicates that the result of the i th step
is to be provided as output. Finally, the notation ( s OP i ... k ) indicates that the s th step
computes the value of the operator OP on the results generated at steps i , ... , k .Werequire
that s>i , ... , k so that the result produced at step s depends only on the results produced
at earlier steps. In this chapter we consider SLPs in which the inputs and operators have values
over a set

A

that is generally not binary. Thus, the circuits considered here are generally not
logic circuits. The basis Ω for an SLP is the set of operators it uses. A circuit is the graph of a
straight-line program. By its nature this graph is directed and acyclic.
An example of a straight-line program that computes the fast Fourier transform (FFT)
on four inputs is given below. (The FFT is introduced in Section 6.7.3 .) Here the function
f + , α ( a , b ) = a + bα where α isapowerofaconstant ω that is a principal n th root of unity of
a commutative ring

R

.(SeeSection 6.7.1 .) The arguments a and b are variables with values

R

in .

( 1 READ a 0 )
( 2 READ a 2 )
( 3 READ a 1 )
( 4 READ a 3 )
( 5

( 7 f + , ω 0 34 )

( 8 f + , ω 2 34 )

( 9 f + , ω 0 57 )

( 10 f + , ω 1 68 )

f + , ω 0 12 ) ( 11 f + , ω 2 57 )

( 6 f + , ω 2 12 ) ( 12 f + , ω 3 68 )

The graph of the above SLP is the familiar FFT butterfly graph shown in Fig. 6.1 .As-
signment statements are associated with vertices of in-degree zero and operator statements are
associated with other vertices. We attach the name of the operator or variable associated with
each step to the corresponding vertex in the graph. We often suppress the unique indices of
vertices, although they are retained in Fig. 6.1 .

9 10 11 12

f + , ω 0 f + , ω 1 f + , ω 2 f + , ω 3

5 6 7 8

f + , ω 0 f + , ω 2 f + , ω 0 f + , ω 2

1 2 3 4

a 0 a 2 a 1 a 3

Figure 6.1 The FFT butterfly graph on four inputs.