Chapter 10 This Done Each Clock Until Num shift divisor Reduced

Problem 10-27

The control unit of the modified machine has the STG shown below:

A new state, A_Rem, is added to the machine. In this state the controller uses

num_shift_divisor to adjust the remainder. A status signal (nsd_not_zero) from the

datapth unit reports whether num_shift_divisor is 0 or not. If not, a signal

module Prob_10_27_Divider #(parameter L_divn = 8, L_divr = 4)( // Choose L_divr <=

L_divn

output [L_divn -1: 0] quotient,

Prob_10_27_Control_Unit M0 (

Ready, Error, Load_words, Shift_dividend, Shift_divisor, Subtract, state_is_S_Adivr,

adjust_remainder,

Start, w1_is_0, w2_is_0, sign_bit, Max, MSB_divr, nsd_not_zero,

clock, reset

);

module Prob_10_27_Control_Unit (

output Ready, Error, output reg Load_words, Shift_dividend, Shift_divisor, Subtract,

output state_is_S_Adivr, output reg adjust_remainder,

input Start, w1_is_0, w2_is_0, sign_bit, Max, MSB_divr, nsd_not_zero,

clock, reset

);

parameter S_idle = 0, S_Adivr = 1, S_Adivn = 2, S_div = 3, S_Err = 4, S_A_Rem = 5,

L_state = 3;

reg [L_state -1: 0] state, next_state;

assign Ready =((state == S_idle) && !reset);

assign Error = (state == S_Err);

assign state_is_S_Adivr = (state == S_Adivr);

0: if (!sign_bit) begin

next_state = S_Adivr; Shift_divisor = 1; // can shift divisor

end

else if (sign_bit) begin

next_state = S_Adivn; // cannot shift divisor

end

1: next_state = S_div;

endcase

S_A_Rem: if (nsd_not_zero) begin

next_state = S_A_Rem;

adjust_remainder = 1;

end

else next_state = S_idle;

default: next_state = S_Err;

endcase

end

endmodule

module Prob_10_27_Datapath_Unit #(parameter L_divn = 8, L_divr = 4, L_cnt = 4)(

// Choose L_divr <= L_divn

);

parameter Max_cnt = L_divn-L_divr;

reg [L_divn: 0] dividend; // Extended dividend

reg [L_divr -1: 0] divisor;

reg [L_cnt -1: 0] num_shift_dividend, num_shift_divisor;

// Shift the remainder to compensate for alignment shifts:

// Revise for synthesis:

// assign remainder = (dividend[L_divn -1: L_divn -L_divr] ) >> num_shift_divisor;

end

else begin

if (Load_words) begin

dividend <= word1;

divisor <= word2;

quotient <= 0;

num_shift_dividend <= 0;

num_shift_divisor <= 0;

end

if (Shift_divisor) begin

divisor <= (divisor << 1);

num_shift_divisor <= num_shift_divisor + 1;

end

if (adjust_remainder) begin

num_shift_divisor <= num_shift_divisor-1;

remainder <= ((dividend[L_divn -1: L_divn -L_divr] ) >> 1);

end

else remainder <= dividend[L_divn -1: L_divn -L_divr];

end

endmodule

module Prob_10_27_test_Divider ();

parameter reset_offset = 45;

parameter reset_toggle = 5;

parameter reset_duration = 20;

Prob_10_27_Divider M0(

.quotient(quotient),

.remainder(remainder),

.Ready(Ready),

.Error(Div_zero),

.word1(word1),

.word2(word2),

.Start(Start),

.clock(clock),

.reset(reset)

);

initial #max_time $finish;

initial begin clock = 0; forever #half_cycle clock = ~clock; end

*/

initial begin // Test for recovery from error state on reset and running reset

#reset_offset reset = 1; #reset_toggle Start = 1; #reset_toggle reset = 0;

word1 = 0;

word2 = 1;

A sample of simulation results is shown below. Note, if Mentor Graphics ModelSim is

being used, be sure to select the radix of the numerical values carefully. Certain values

must be in binary format. This (learning) exercise is left to the student.

Problem 10-28

The block diagram for the self-aligning divider described in Example 10.16 is shown

below

The STG diagram below includes Mealy signals to launch shifting and subtacting

coincident with transitions entering and leaving S_Adivn. The machine is to be modified

so that shifting and subtracting occur in the same state, i.e., at the same clock edge.

Problem 10-35

An attempt to divide by 1 can be detected with the machine in S_idle, as shown in the

STG below. The new signal, w2_is_1, is generated by the controller and causes divisor

and dividend to load as before, but also assigns word1 to the quotient.

reset

Start && (word2 == 0)

S_idle

/Ready

S_Err

Error

Start && (word1 == 0) && (word2 != 0)

/ Load_words

Note: Assert Load_words to flush residual

value of quotient

Start && (word1 != 0) && (word2 == 1)

/ Divr_is_1

module Divider_Prob_10_35 #(parameter L_divn = 8, L_divr = 4)( // Choose L_divr <=

L_divn

output [L_divn -1: 0] quotient,

output [L_divn -1: 0] remainder,

output Ready, Error,

word2, // Datapath for divisor

Load_words, W2_is_1, Shift_dividend, Shift_divisor, Subtract, state_is_S_Adivr,

clock, reset

);

endmodule

module Control_Unit (

always @ (posedge clock, posedge reset)

if (reset) state <= S_idle; else state <= next_state;

always @ (state, Start, w1_is_0, w2_is_0, sign_bit, Max, MSB_divr) begin

Load_words = 0; Shift_dividend = 0; Shift_divisor = 0; Subtract = 0; next_state = S_idle;

case (state)

S_idle: case (Start)

0: next_state = S_idle;

1: if (w2_is_0) next_state = S_Err;

else if (!w1_is_0) begin next_state = S_Adivr; Load_words = 1; end

else next_state = S_idle;

S_Adivn: case ({Max, sign_bit})

2’b00: next_state = S_div;

2’b01: begin next_state = S_Adivn; Shift_dividend = 1; end

2’b10: begin next_state = S_idle; Subtract = 1; end

2’b11: next_state = S_idle;

endcase

default: next_state = S_Err;

endcase

end

endmodule

module Datapath_Unit #(parameter L_divn = 8, L_divr = 4, L_cnt = 4)(

);

parameter Max_cnt = L_divn-L_divr;

reg [L_divn: 0] dividend; // Extended dividend

reg [L_divr -1: 0] divisor;

reg [L_cnt -1: 0] num_shift_dividend, num_shift_divisor;

assign MSB_divr = divisor[L_divr -1];

assign w1_is_0 = !(|word1);

assign w2_is_0 = !(|word2);

assign w2_is_1 = (word2 == 1);

assign Max = (num_shift_dividend == Max_cnt + num_shift_divisor );

always @ (posedge clock, posedge reset) // Register/Datapath operations

if (reset) begin

divisor <= 0; dividend <= 0; quotient <= 0; num_shift_dividend <= 0; num_shift_divisor <= 0;

end

else begin

if (w2_is_1) begin

dividend <= word1;

num_shift_divisor <= num_shift_divisor + 1;

end

module test_Divider_STG_1 ();

parameter L_divn = 8;

parameter L_divr = 4;

parameter word_1_max = 255;

parameter word_2_delay = 20;

wire [L_divn -1: 0] quotient;

wire [L_divn-1: 0] remainder;

initial #max_time $finish;

initial begin clock = 0; forever #half_cycle clock = ~clock; end

initial begin expected_quotient = 0; expected_remainder

assign rem_error = (!reset && Ready) ? |(expected_remainder ^ remainder): 0;

initial begin // Test for divide by zero detection

#2 reset = 1;

#15 reset = 0; Start = 0;

#10 Start = 1; #5 Start = 0;

end

initial begin // Exhaustive patterns

#delay_for_exhaustive_patterns

word1 = word_1_min; while (word1 <= word_1_max) begin

Problem 10-38

Divider_STG_0 consists of a controller and a datapath unit. The controller is

implemented as a conventional finite state machine having a level-sensitive cyclic

Divider_STG_0_sub differs from Divider_STG_0 in that it uses the sign bit from twos

complement subtraction to reveal the relative magnitude of the dividend and the divisor,

instead of using a comparator. This machine is synthesizable.

Divider_STG_1 consists of a controller and a datapath unit. The controller is

implemented as a conventional finite state machine having a level-sensitive cyclic

behavior describing the output and the next state, and a cyclic behavior describing the

state transitions. The datapath unit has a single edge-sensitive behavior governing register

Divider_RR_STG is not synthesizable. It uses num_shift_divisor to make a non-static

reference to bits of dividend to make a final adjustment to the remainder to correct for its

Problem 10-39

The longest path through the array passes through 10 cells. It is not unique. The figure

below shows one configuration of the cutset, I/O registers, and the internal pipleine

By reconfiguring the cutset we obtain a balanced pipeline, with a longest path through

only five adders:

S00

A1

S02

S03

B0

A3A2A0

0

C00

C01

C02

S01

C03

Problem 10-40

The longest path through the array passes through 14 cells and is not unique. One such

path is illustrated by the darkened cells. The figure below shows the cutset, I/O registers,

and internal pipeline registers for a balanced 4×8 pipelined multiplier. The longest path

through each section of the structure passes through 7 adders.

S00

A1

S02

S03

A3A2A0

0

C00

C01

C02

S01

C03

S04

A5

S06

S07

A7A6A4

C04

C05

C06

S05

C07

B0

Problem 10-41

Reservation Table (See Fig. 10-14):

Problem 10-42

Reservation table: