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) = LQ + 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[0];

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[7];

Y = Y<<1;

if (C) Done = 1;

end

end

if (C) MV = 1;

end

To determine the datapath requirements, I dont 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 dont 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;

Ready = 1;

@(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})

2b00: state = `SHY;

2b01: state = `START;

2b10: state = `ADD;

2b11: state = `LSTADD;

endcase

end

`ADD: begin

EY = 1;

LR = 1;

P[3:0] = `ADD;

@(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

`LSTADD:begin

EY = 1;

LR = 1;

P[3:0] = `ADD;

@(posedge clock);

if (C) state = `OVR;

else state = `START;

end

`OVR: begin

ED = 1;

LX = 1;

LR = 1;

P[3:0] = `PASS;

Ready = 1;

@(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

ADD: S4=1

SHY: S5=1

LSTADD: s6=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+ = S4CZ + S5CZ

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

ADD: 1011

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