[an error occurred while processing this directive]

MW 10-11:30am
MIT - 9-057

Course
Information [an error occurred while processing this directive]
· Overview [an error occurred while processing this directive]
· Calendar [an error occurred while processing this directive]
· Contact [an error occurred while processing this directive]
· Class List [an error occurred while processing this directive]
· Signup

Course
Materials [an error occurred while processing this directive]
· Papers/Handouts [an error occurred while processing this directive]
· Problems [an error occurred while processing this directive]
· Brainteasers
· Online Video

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 B₁ is directly below pin A₂, pin B₂ is below pin A₃, 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 Monday, 02-Feb-2004 21:57:48 EST

[an error occurred while processing this directive]