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
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+ = 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
