Problem 4 Solution

Part A.  8 Bit Register Design

The 8 bit register is just a state machine like any other.  In fact, we can think of it as 8 identical two-state state machines running in parallel. The state table for each bit is:

 Data L Q Q+ D 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 D(Data,L,Q) = L’Q + Ldata which is just a 2:1 mux controlled by L.  After adding the necessary tri-state buffer to the output we have a single bit load controlled tri-stated register.  Below is my DW implementation of the one-byte version. Part B. Datapath Design

To figure out the datapath, I first need to know the algorithm that it will have to support. Here is the shift and add algorithm. Notice that the cycle-by-cycle timing of this behavioral verilog model is only accurate for the external interface. The rest is written as pure algorithm. I will use this model to determine my datapath requirements.

Behavioral Verilog

always begin

Done = 0; Ready = 1;

@(posedge clock) X = D; Ready = 0; MV = 0;

@(posedge clock) Y = D;

R = 0;

while (!Done) begin

C = X;

X = X>>1;

Z = (X == 0);

if (Z) Done = 1;

if (C) begin

{C,R} = R + Y;

Z = (R == 0);

if (C || Z) Done = 1;

end

if (!Done) begin

C = Y;

Y = Y<<1;

if (C) Done = 1;

end

end

if (C) MV = 1;

end

To determine the datapath requirements, I don’t need to worry too much about sequencing, I just need a list of raw datapath register transfer operations that must be supported. Here they are:

X ß D

Y ß D

R ß 0   // note that I can do this using ALU operations such as (R ß X xor R) if X and R contain the same data.

R ß R + Y    setting C and Z

X ß X >> 1  setting C and Z

Y ß Y << 1  setting C and Z

Supposing I want to design the minimal datapath to support these operations, I will assume that I have only 1 ALU, and three Registers, X, Y, R.  By looking at the list, I see that I will need X and Y on the left since they both participate in unary operations (shifting). R is only involved in binary operations so it can be on the right. Furthermore, X and Y are never involved in a binary operation so I don’t need either one on the left. Finally, I see that I can use the existing paths to move D into either X or Y by passing it through the ALU. My DW implementation is shown below. Notice that I have added inverters on the OD control points so that I can use positive logic when designing my controller. In my state machine, the output controls are called EX,EY,ED instead. I should have renamed them on my registers as well to avoid confusion.  The control points are:

ED,EX,EY  :  Enable D,X,Y outputs respectively.

LX,LY,LR  :  Load X,Y,R registers respectively.

P[3..0]         :  Opcode for ALU Part C. Controller Design

I now have to determine the sequence of operations needed to implement the algorithm on my datapath. According to the timing diagram, I need to read X in the same cycle that I assert the Ready output. Starting from there I get the following state diagram. The Verilog version is shown below. always begin case (state)

`START:   begin

ED = 1;

LX = 1;

LR = 1;

P[3:0] = `PASS;

@(posedge clock) state = `GETY;

end

`GETY:    begin

ED = 1;

LY = 1;

P[3:0] = `PASS;

@(posedge clock) state = `CLR;

end

`CLR:      begin

EX = 1;

ER = 1;

P[3:0] = `XOR;

LR = 1;

@(posedge clock) state = `SHX;

end

`SHX:      begin

LX = 1;

EX = 1;

P[3:0] = `SHR;

@(posedge clock) case ({C,Z})

2’b00: state = `SHY;

2’b01: state = `START;

endcase

end

EY = 1;

LR  = 1;

@(posedge clock);

if (C) state = `OVR;

else if (Z) state = `START;

else state = `SHY;

end

`SHY:     begin

LY = 1;

EY = 1;

P[3:0] = `SHL;

@(posedge clock);

if (C) state  = `OVR;

else state = `SHX;

end

EY = 1;

LR  = 1;

@(posedge clock);

if (C) state = `OVR;

else state = `START;

end

`OVR:      begin

ED = 1;

LX = 1;

LR = 1;

P[3:0] = `PASS;

@(posedge clock) state = `GETY;

end

# Implementation of the Controller

To keep the implementation simple, I have decided to use a one-hot encoding. There will be a single state bit for each state in the state diagram. Only one bit can be on in each state.

Here is the state ecoding:

START: S0=1  (00000001)

GETY: S1=1    (00000010)

CLR: S2=1

SHX: S3=1

SHY: S5=1

SHY: S7=1

Because I am using 1-hot encoding, I can read the next state logic and output logic directly from the state diagram.

Next State Logic:

S0+ = S3ZC’ + S6C’ + S4ZC’

S1+ = S0 + S7

S2+ = S1

S3+ = S2 + S5C’

S4+ = S3CZ’

S5+ = S4C’Z’ + S5C’Z’

S6  = S3CZ

S7  = (S4+S6+S5)C

Output Logic

ED = S0 + S7 + S1

EX = S3

EY = S 4 + S6 + S5

LX = S0 + S7 + S3

LY = S1 + S5

LR = S0 + S7 + S6 + S4

Opcodes are:

XOR: 0110

PASS: 0100

SHR:   0011

SHL:   0010

P3 true when ADD:  P3 = S6 + S4

P2 true when XOR or PASS: P2 = S0 + S1 + S7 + S2 + S4

P1 true when not PASS: P1 = P2’+S2

P0 true when ADD or SHR:  S4 + S6 + S3

Here is the DW implementation of the Controller: Here is the DW implementation of the entire system 