Step by Step Method to Design a Combinational Circuit

The Electronics engineers should know the steps to design a particular circuit. While we study, we directly study the properties of the electronic block and the circuit diagram of the corresponding block. We never think how had we landed up to that particular circuit diagram. For example when we talk about digital Multiplexer, Decoder or Counters; we directly find the block diagrams and the circuit diagrams of these modules. And we never think about the design process. So, in interviews, students fail to design a simple combinational logic. Though this post seems to be a simple one, and few may find nothing new is here; but I thought of posting this as it would help the newbies and also to them who wand to revisit the concept of designing a combinational circuit.

Steps to be Followed:

  1. Understand the problem statement (realize how the outputs of the circuit depend on the inputs to the circuit)

  2. Draw the Truth Table (Truth Table establishes the relationship between the outputs and inputs for all the possible input combinations)

  3. Derive the minimized Boolean Expressions for the outputs w.r.t. the inputs (You can use the K-Map method)

  4. From the Boolean expressions draw the logic circuit

In this post, we have considered a very simple problem to explain the above 4 steps:

Design Problem: Design a 3 input, 1 output digital logic circuit which will take all the octal digits (0, 1, … 7) as its input and produce the even parity bit for the corresponding octal digit.

Even Parity Generator

Even Parity Generator Block Diagram

Step 1: The circuit has 3 inputs (as the octal digits need 3 bits to be represented) where it would only take the octal digits. The output would generate the even parity bit for the corresponding input given. For example if the input is octal digit “2” i.e, in binary “010”; the generated parity bit would be “1”. Click here to understand the even/odd parity bit generation concept.

Step 2: Let’s draw the truth table for the design

A B C O
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1



 Step 3: Let’s draw the K-map for the above truth table and find the equivalent Boolean expression.

K-Map Even Parity Generator

K-Map for Even Parity Generator of Octal Digits

As we can see that there is no minimization possible; the final Boolean expression would be:

O = A’B’C + A’BC’ + AB’C’ +ABC

Step 4: Now as we have the Boolean Expression with us, we can draw the logic circuit for the same:

Even Parity Generator Circuit

Even Parity Generator Circuit

Hope you have learned a very basic design procedure. Stay tuned to VLSIFacts to get more updates like this.

SETUP Time and SETUP Violation in a Single D Latch

Setup and Hold time concept is one of the fundamental concepts that is very necessary for closing and analysing and timing margin. The analysis in digital domain, in Reg to Reg system is very popular but the root cause of Setup and Hold time is often not taken care of in the education system. This Post elaborates the cause of setup analysis in a single D latch taking the Transistor level schematic into account, also I will try to explain the points where Setup and Hold time is measured and why we do so and why we can not write it on any other points.

Fig.1 Displays a Transistor Level Diagram of a simple D-latch, D is the input and I1, I2 are the inverters in the data path of the latch, T1 is the forward path transmission gate and T2 is the feedback path transmission gate, while L_I_1 and L_I_2 are the cross coupled latch inverters. The latch is controlled by the signal CK.

Full_latch

Fig.1 A single D Latch

Fig.2 shows the CK signal used, the CLK_delay is the delay between the rising edge and the falling edge of the CK and CK_bar signal.

CLOCK_and_clock_bar

Fig.2 Clock signals used .

Setup Analysis

1. Setup time is the minimum time required for the data to get settled before the latching edge of the clock in this case it is the Rising edge.

2. The requirement of the setup time arises from the fact that the latching action is performed by the cross coupled inverters L_I_1 and L_I_2, the latch is a Bi-Stable which means that is is stable at two points either (0,1) or (1,0)., this implies that if the latch is at any between logic, it can go in either direction, so to have the safest of the operation the logic at point B should be same as the logic at point C. This means any change in data should propagate to point C before the latching action of the latch begins that is closing of the T2 and opening of T1.

3. Moreover as the first latching edge of the clock arrives in this case it is the rising edge, corresponding transistor of T1 begins switching off and T2 begins conducting, this causes the output to degrade and finally the latch is unable to sample the changed data and it latches the previous data only, which is a functionality failure.

Fig.3 and Fig.4 displays the simulation of setup violation in the D-latch , the blue line is the clock edge, the Red one is the data, which in multiple simulations is pushed near to the clock edge,and the green one is the output data which is inverted of the input data due to the circuit taken.

setup1

Fig.3 Setup Simulation and Violation (A)

setup2

Fig.4 Setup Simulation and Violation (B)

4. As it can be clearly seen that as we push the data towards the clock edge the output data degrades and finally it tries to reach the level 0 but reverts back to the logic 1 as the latching action of the latch overcomes the changed data which was not able to propagate to point C, and the previous data which was residing at C take over the change.

5. So going by this explanation one can say that if this clock is the same as external clock then at the basic explanation we can say that the for the surest of the operation setup time is the data delay which is from the point D to C and it is commonly denoted as MAX Data delay

6. Different measurement standards calculate Setup time differently, some industry parameters measure it like the minimum time before the edge of the clock for which gets output degradation is up to 5% of the relaxed value.

For the basic understanding and explanation we can conclude that for the surety of the operation the data should reach the point C before the latching just kicks in, and this delay is the SETUP time of the latch as if some one violates it, the output data will start degrading, now its on the design requirement, that up to which extent degradation is allowed.

I hope this will suffice your queries, Keep following for the some more posts on Setup and Hold. Please post your queries in the comments or start a thread in the discussion forum.

Synthesis and Functioning of Blocking and Non-Blocking Assignments.

Here are some examples on blocking and non-blocking assignments in Verilog, that can be really useful for the budding design Engineers. First let us discuss the features of these assignments.

  1. They are procedural assignments always used in a procedural block like initial or always.
  2. In BA (Blocking assignment) RHS of the assignment is assigned immediately to the LHS in the active region of the scheduler, that is to understand we can say the assignment is immediate and it does not wait for the procedural block to end. While in NBA (Non-Blocking Assignments) the RHS is calculated first, then it is assigned to the LHS much later in the scheduler, that is to understand after the completion of procedural block (initial or always). Other wise we can say that they get executed in the NBA part of the scheduler which is second last in the sequence after Active and Inactive. .
  3. In BA, assignments are done in the sequence in which they are written, In NBA all the RHS are calculated and stored in the temporary memory of the compiler and then are assigned to the LHS, at the same time, that is there is no set order of assigning, it depends on the compiler.

The following example illustrates the Blocking Assignment

initial 
begin
   a=1;
   b=0;
   y=1; // at 0 simulation time y gets value '1'.
   #5 y=a&b; // at 5 time units y gets updated to a&b, i.e. 1&0=0
   z=y; // at 5 time units z gets updated to y value, i.e. '0'
   #5 temp=a; // temp gets the value of a, i.e. '1' at 10 time units
end

Wave forms for the above example
BAThe following example illustrates the Non-Blocking Assignment

initial 
begin
   a=1;// Use of blocking assignments to initialize 
       // Blocking and non-blocking assignments can not be used together in a single
       // procedural block from the synthesis point of view. 
       // It is used here for initializing purpose.
   b=0; 
   y<=1; // At 0 simulation time y gets 1.
   y<=#5 a&b; // at 5 time units y gets updated
   z<=y; // z has only 'X' as value it does not get updated as reg initializes 
         // to X and it does take the previous value of y which is X not 1 as y has a NBA on it.
   #5 temp<=a; // temp gets the value at 5 time units executes at 5 only as above delay is propagation delay
 // with NBA.
end

Wave forms for the above example
NBA

Example (a) Synthesis view of four bit shift reg.

module shiftreg_4bit(dout,clk,rst,din);
 input clk,rst,din;
 output reg dout;
 reg a,b,c;
 always @ (posedge clk or posedge rst)
  begin
  if (rst)
   begin
   dout<=0;
   a<=0;
   b<=0;
   c<=0;
   end
  else
   begin
   a<=din;  // Non-Blocking assignments here will hold the previous value and assign on the clock edge,         
   b<=a;   // implementing four registers as in conventional shift register.
   c<=b;
   dout<=c;
  end
  end
endmodule

4bit_shftreg

but if changed into Blocking Assignments.

 begin
  a=din;
  b=a;
  c=b; // Now blocking assignments will immediately update their values and will collapse into a wire
  dout=c; //resulting in a single flip flop.
 end

collapse_sr

Example (b) Example for scheduling.

module clk_ba_nba();
reg clk;
initial
 clk<=1;
always @ (clk)
 #5 clk<=~clk; // NBA on clk update after the event, accounted as a change for always block, clock toggles
endmodule

clock_toggle

but if changed assignments to Blocking Assignments

module clk_ba_nba();
reg clk;
initial
 clk=1;
always @ (clk)
 #5 clk=~clk; // Clk gets updated in the active region, change not accounted, clock does not toggle.
endmodule

clk_not_tgle

P.S Whenever you want to implement a fast event independent circuit like combinational circuits where the present value gets updated immediately, Use blocking assignments and whenever there are assignments that to be made together after an event use NBA, usually in sequential circuits.

Digital Design Methodologies

—There are two basic types of digital design methodologies:

  1. top-down design methodology
  2. bottom-up design methodology.

top-down Design Methodology

—In a top-down design methodology, we define the top-level block and identify the sub-blocks necessary to build the top-level block. We further subdivide the sub-blocks until we come to leaf cells, which are the cells that cannot further be divided.

top-down

bottom-up Design Methodology

—In a bottom-up design methodology, we first identify the building blocks that are available to us. We build bigger cells, using these building blocks. These cells are then used for higher-level blocks until we build the top-level block in the design.

bottom-up


Read Four Different Coding Styles of Verilog Language


—Typically, a combination of top-down and bottom-up flows is used. —Design architects define the specifications of the top-level block. Logic designers decide how the design should be structured by breaking up the functionality into blocks and sub-blocks. —At the same time, Circuit designers are designing optimized circuits for leaf-level cells. They build higher-level cells by using these leaf cells. —The flow meets at an intermediate point where the switch-level circuit designers have created a library of leaf cells by using switches, and the logic level designers have designed from top-down until all modules are defined in terms of leaf cells.

For example; A low leakage 4-bit parallel adder is to be designed. The logic designers would break the 4-bit parallel adder to four 1-bit full adders. Each full adder would be broken into two half adders and an OR gate. Each half adder would again be divided into one XOR gate and one AND gate. At the same time the Circuit designer would design the optimized low leakage logic gates: AND, OR and XOR from the transistor / Switch level.

Reference: Verilog HDL, A guide to Digital Design and Synthesis; Samir Palnitkar

State Equivalence & Minimization Part – 2

The states which are equivalent, are redundant. Because by looking at the output, we can not even figure out in which state the machine is in. So, if there are two equivalent states then there is no point of using both the states. We can merge both the states and can use only one state.

Steps for State Machine Minimization

  • Identify equivalent states
  • Replace equivalent states by one state.

Theorem for State Equivalence

Two states Si and Sj are k+1 equivalent if and only if

  • They are k-equivalent
  • And their next states for all inputs are k-equivalent

If we have a set of states which are k-equivalent, then a subset of these, which may include all of them or none of them are only going to be k+1 equivalent. There can not be another state coming in, which is not k-equivalent and that is k+1-equivalent.

So as we increase the “k”, set of distinguishable states grows and set of equivalent states reduces.

Minimization Steps

  • Consider all states to be 0-equivalent
  • Identify 1-equivalent partition P1 based on outputs
  • Identify i+1 equivalent partition Pi+1 based on Pi until (Pi+1 = Pi)
  • Replace each set of states in a Pi class by a single state and define the state transitions accordingly

Procedure

  • For generating P1 we have to look for outputs
  • For generating P2, P3, P4 and so on we have to look whether the two states belong to the same equivalent class as far as Pi is concerned and whether the next states for any input belong to the same class or not. If they belong to the same class then they will be Pi+1 equivalent.
  • So for this procedure we only have to bother about next state transition and we don’t have to bother about output. We will keep on generating this until Pi+1 = Pi (i.e, at some stage if we are not able to get any more states to be distinguishable). This is because if Pi+1 = Pi then Pi+2 = Pi+1. So, there is no point of moving further
  • Once this condition reach, then replace each set of states in a Pi class by a state and define state transitions accordingly

All the members in a class of Pi partition are i-equivalent.

If the initial state diagram does not have any redundancy, all the states will become a class in itself and the partition will contain as many number classes as the number of states.

Let’s consider an example of Machine M1 representing the following state table

PS NS, z
x=0 x=1
A E,0 D,1
B F,0 D,0
C E,0 B,1
D F,0 B,0
E C,0 F,1
F B,0 C,0

Now the State partitions for the above state table will be as follows:

Symbol Partition
P0 (A B C D E F)
P1 (A C E) (B D F)
P2 (A C E) (B D) (F)
P3 (A C) (E) (B D) (F)
P4 (A C) (E) (B D) (F)

The above state partition shows the states “A” and “C” are equivalent and states”B” and “D” are equivalent. So we can merge state “A” and “C” to one state, similarly state “B” and “D” can be merged.

Let’s discuss some of the class divisions from partition P1 to P2 for better understanding:

P1 to P2

The set of states which lie under P1, form 1-equivalent class. That means all the states in one class/set are 1-equivalent. This shows A, C and E are 1-equivalent and similarly B, D and F are 1-equivalent.

Now while trying to creating the P2 partition;

  • For A and C, and for the input x=0; next states are same, that is E and E respectively. For input x=1; next states are D and B. As D and B lie in same class, we can conclude that A and C are 2-equivalents.
  • For A and E, and for the input x=0; next states are E and C respectively, which lie in the same class. For input x=1; next states are D and F, which again lie in the same class. So, we can conclude that A and E are 2-equivalents.
  • For B and F, and for the input x=0; next states are F and B respectively, which lie in the same class. For input x=1; next states are D and C, which do not lie in the same class. So, we can conclude that B and F are not 2-equivalent but 2-distinguishable. So we can see in partition P2, B lies in a different set and F lies in a different set.

You can analyze all other state combinations and find out the above partition table. if any doubt please drop a comment at the below section.

Read State Equivalence & Minimization Part – 3, to see how a state transition diagram gets minimized using the above minimization method.