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

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

2’b00:
state = `SHY;

2’b01:
state = `START;

2’b10:
state = `ADD;

2’b11:
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

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^{+} = 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

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