6.896 BRAINTEASER #1
Figure 1
Figure 2
Figure 1 shows a sequential circuit in which circles represent
combinational elements with the specified propagation delays and
rectangles represent clocked registers. With each clock tick, the
circuit accepts one input value and produces one output value. The
clock period of the circuit is defined as the longest path of
combinational rippling (accumulated propagation delay on any path
between registers), which is 3+7+7+7=24.
Figure 2 shows an improved circuit with clock period 17. The new
circuit has the same structure as the original one, except that
registers are located in different places. The new circuit performs
essentially the same function as the original one (there may be a
difference in initialization), which can be seen as follows. Every
input to the shaded subcircuit arrives one clock tick earlier in the
new circuit compared with the old. Therefore, the computation
performed by the shaded subcircuit completes one clock tick earlier
in the new circuit. Thus, by delaying the output of the shaded
subcircuit by one clock tick, as is done by the relocated register,
the remainder of the circuit sees no difference. The new circuit,
however, has a clock period of only 3+7+7=17.
What is the minimum clock period that can be obtained by relocating
registers in the circuit while still preserving its function? One
restriction: to preserve the integrity of the interface, you cannot
move the register on the input.
6.896 BRAINTEASER #2
Figure 1
Figure 1 shows a single-layer circuit board containing two modules A
and B, each of which has n connecting points, or pins.
Each pin on module A must be connected to the corresponding pin on
module B using a wire. Wires must run along the underlying grid,
but no two wires may use the same grid point or segment.
The modules can move vertically (up and down), but not horizontally
(left or right). Since the two modules are offset horizontally (pin
B1 is directly below pin A2, pin
B2 is below pin A3,
etc.), the routing problem is impossible if the modules are placed too
close together vertically. What is the minimum vertical separation
that can be obtained between A and B so that all n wires can be
routed?
6.896 BRAINTEASER #3
Figure 1
A firing squad has been formed as a one-dimensional array of n
soldiers, as shown in Figure 1. Each soldier is a finite automaton
whose next state is dependent only on its current state and the
current states of its two neighbors. There is no global
communication, but the state transitions of the soldiers are
synchronized by a global clock. The goal is for all the soldiers to
shoot their guns at the same time.
All the soldiers begin in the same quiescent state, and all
soldiers are identical, except for first and last soldiers. The last
soldier knows he or she is the last soldier. The first soldier is the
general, who, at the start of the computation, enters the
fire-when-ready state. The goal is for all soldiers to enter
the shoot state on exactly the same clock tick.
Give a design for the soldier automaton so that all soldiers fire at
the same time.
This document last modified