Spring term GATEWAY exercise

Spring term GATEWAY exercise

The aim of the exercise

This is primarily a digital design exercise. Verilog is the tool you will use to explore and test your design ideas - but the real effort is in creating a digital architecture.

The design exercise

You are going to implement a "Tower of Hanoi" move generator.

This game is well-known and so the web has many references. The origin of the problem is described here and its inventor is described here - and you can play the game here . In the emacs-based editor, you can watch a game run by typing: ESC x hanoi RETURN to run it with the default number of rings or ESC 5 ESC x hanoi RETURN to run it with, for example, 5 rings; students in the GateWay laboratory will find an entry for Hanoi under the Verilog menu in their editor.

In brief, this is a classical problem used to illustrate recursive programming techniques - however, a paper has recently been published by Chedid and Mogi[1] which shows how the algorithm may be converted to a simple iterative form which, in turn, seems to underpin a digital architecture for generating the sequence of moves. The iterative algorithm is reproduced below from [1] (in a sort of pseudo-Pascal) for information: 

        { Move stack from peg 1 to peg 3 }
        Procedure ITERATIVE_HANOI:
        Let FromPeg, ToPeg be array [1 ... n] of 1 ... 3;

        Set FromPeg to {1, 1, 1, 1, ... 1}
        If n is odd then
             Set ToPeg to {3, 2, 3, 2, ... 3}
        Else
             Set ToPeg to {2, 3, 2, 3, ... 3}

        For i := 1 to (2^(n-1)) do
             begin
             Find the largest d (1 <= d <= n) such that i mod 2^(d-1) = 0
             Move disk d from peg FromPeg[d] to peg ToPeg[d];

             case[FromPeg[d], ToPeg[d]] of
                  [1,2] FromPeg[d] := 2 ToPeg[d] := 3;
                  [2,1] FromPeg[d] := 1 ToPeg[d] := 3;
                  [1,3] FromPeg[d] := 3 ToPeg[d] := 2;
                  [3,1] FromPeg[d] := 1 ToPeg[d] := 2;
                  [2,3] FromPeg[d] := 3 ToPeg[d] := 1;
                  [3,2] FromPeg[d] := 2 ToPeg[d] := 1;
             end; {case}
        end; {for}
        end; {procedure}

Your task

Your task is to design a digital circuit (down to gate-level: booleans and a purely synchronous Dtype) which generates the moves for a 5 disc Tower of Hanoi game. You may, if you wish, discuss/consider how this design could be adapted for different numbers of discs - but the main thrust of your work should be for the number 5.

Your deliverable

There are two deliverables:

  1. A report in the mandated format detailing your digital design
  2. The Verilog code which generates the move sequence

Please note: the latter will be marked for the design method, the clarity of the code and the excellence of the digital design.

Hints

I have a solution - and in creating my solution I did certain things which helped me. Your solution may be different from mine and so these hints may not apply to you but, for what they are worth, here they are:

  1. I worked directly from the algorithm in the paper - it was the existance of an iterative (i.e. a series of sequential steps) which made this all manageable for me
  2. for minimisation of combinatorial logic, I got surprisingly good results using Karnaugh maps "with unknowns".
  3. I ended up using tri-states for the main outputs (see the on-line manual under data types)
  4. I did not worry about producing the "disk-number" output since it is redundant (you always move the top disc off the "from" peg). However, it became a simple matter to add circuits later to produce it if required.

Concluding remark

Good luck - and HAPPY NEW YEAR

References

  1. F B Chedid and T Mogi, "A simple iterative algoithm for the Towers of Hanoi problem", IEEE Trans Education , vol. 39, no. 2, pp. 274-275, May 1996.