NAND, Gates, Mux

Mux related:

                       Using Mux to design gates






















Using NAND gates to design other gates

Setup time, Hold time, clk skew, clk jitter, Metastability (Updating)

One method of clk generation

1) Setup time

2) Hold time

Device Switching is fastest at low temperatures.
The timing analysis are done at extreme corners to ensure that they meet the timing specs.
a. Fastest case: Fast N and Fast P transistors, High Vdd, Low Temperature
b. Slowest Case: Slow N and Slow P transistors, low Vdd, High Temperature

This isn't necessarily true in all cases. In some process technologies there is a phenomenon called temperature inversion.
3) Clock Skew
Skew is the difference in arrival of clock at two consecutive pins of a sequential element is called skew. Clock skew is the variation at arrival time of clock at destination points in the clock network. The difference in the arrival of clock signal at the clock pin of different flops.

If capture clock comes late than launch clock then it is called positive skew. When data and clock are routed in same direction then it is Positive skew.

Positive skew can lead to hold violation.

Positive skew improves setup time.

link

4) Clock Jitter
Introduction
Jitter is the timing variations of a set of signal edges from their ideal values. Jitters in clock
signals are typically caused by noise or other disturbances in the system. Contributing factors
include thermal noise, power supply variations, loading conditions, device noise, and
interference coupled from nearby circuits.

Types of Jitter
Jitter can be measured in a number of ways; the following are the major types of jitter:
• Period Jitter
• Cycle to Cycle Period Jitter
• Long Term Jitter
• Phase Jitter
• Time Interval Error (TIE)

5) Comparison of Clock skew and Clock jitter

Clock skewThe deterministic (knowable) difference in clock arrival times at each flip-flop
Caused mainly  by imperfect balancing of clock tree/mesh
Can be deliberately introduced using delay blocks in order  to time-borrow
Accounted for in STA by calculating the clock arrival times at each flip-flop

Clock jitterThe random (unknowable, except distribution s) difference in clock arrival times at each flip-flop Caused by on-die process, Vdd, temperature variation, PLL jitter, crosstalk, Static timing analysis (STA) accuracy, layout parameter extraction (LPE) accuracyAccounted for in STA by subtracting (~3 s) from the cycle time in long path analysis, and adding to receiving clock arrival time in race analysis

Jitter is always bad, skew can be helpful or harmful.

Clock uncertainty D º skew ± jitter

6) Clock gating

Gated clocks

Clock signals that are passed through some gate other than buffer and inverters are called gated clocks. These clock signals will be under the control of gated logic. Clock gating is used to turn off clock to some sections of design to save power. Click here to read more about clock gating.

Click here for more details

7） Hazard

Some VLSI questions and anwsers

1）Why NMOS technology is preferred more than PMOS technology?
N- channel transistors has greater switching speed when compared to PMOS transistors.

2）What is Channel-length modulation?

The current between drain and source terminals is constant and independent of the applied voltage over the terminals. This is not entirely correct. The effective length of the conductive channel is actually modulated by the applied VDS, increasing VDS causes the depletion region at the drain junction to grow, reducing the length of the effective channel. Therefore I_D' = I_D *(1+LAMBDA*V_DS); Lambda is the channel length modulation and is generally proportional to the inverse of the channel length. Channel length modulation is more pronounced in short channel devices. Also, Short channel devices are prone to velocity saturation.Velocity saturation occurs when the horizontal component of the E-field (along the channel) reaches a critical value. At this point the carriers collide.

3）What is Latch – up?

Latch up is a condition in which the parasitic components give rise to the establishment of low resistance conducting paths between VDD and VSS with disastrous results. Careful control during fabrication is necessary to avoid this problem.

4） How do you prevent latch up problem?
Latch up problem can be reduced by reducing the gain of parasitic transistors and resistors. It can be prevented in 2 ways
• Latch up resistant CMOS program
• Layout technique
The various lay out techniques are
Internal latch up prevention technique
I/O latch up prevention technique.

5）What is Stick Diagram? It is used to convey information through the use of color code. Also it is the cartoon of a chip layout.

What are the uses of Stick diagram? It can be drawn much easier and faster than a complex layout. These are especially important tools for layout built from large cells.

Give the various color coding used in stick diagram? Green – n-diffusion；Red- polysilicon；Blue –metal；Yellow- implant；Black-contact areas.

6）Define Threshold voltage in CMOS?
The Threshold voltage, VT for a MOS transistor can be defined as the voltage applied between the gate and the source of the MOS transistor below which the drain to source current, IDS effectively drops to zero.

7) What is Body effect?
The threshold volatge VT is not a constant w. r. to the voltage difference between the substrate and the source of MOS transistor. This effect is called substrate-bias effect or body effect.

8) Compare nMOS and pMOS devices

                                   nMOS                                                                       pMOS
A section of p-type separating 2 n-type silicon          A section of n-type separating 2 p type silicon
Turns ON with the gate at logic 1                               Turns ON with the gate at logic 0
Majority carriers are electrons                                    Majority carriers are holes
Good transmission of logic 0                                       Good transmission of logic 1

9) What is meant by a transmission gate?
A transmission gate consists of an n-channel transistor and p-channel transistor with separate gates and common source and drain. 

10) Define Rise time and fall time
Rise time, tr is the time taken for a waveform to rise from 10% to 90% of its steady-state value.

Fall time, tf is the time taken for a waveform to fall from 90% to 10% of its steady-state value.

11) Define Delay time
Delay time, td is the time difference between input transition (50%) and the 50% output
level. This is the time taken for a logic transition to pass from input to output.

12) Define Noise Margin

The parameter which gives the quantitative measure of how stable the inputs are with respect to coupled electromagnetic signal interference.
NML = Vil-Vol
NMH = Voh-Vih

13) What is a task in verilog, AND difference between task and funtion?

A task is like a procedure, it provides the ability to execute common pieces of code from several different places in a description;

Functions always return a single value. with in a function, no event, delay or timing control statements are permitted, at least one input argument and they cannot have output or inout arguments. Functions is unable to enable a task however it can enable other functions. Tasks don’t return a value, but can pass multiple values through output and inout arguments.Tasks can enable a function as well as other versions of tasks.

14) Mention few data types in Verilog

Nets, registers, vectors, numbers and arrays

15) Mention the four key words used for looping in verilog

while, for, repeat, forever

16) Specify the operator which have highest and lowest precedence.

Unary operator – highest precedence
Conditional operator – lowest precedence

17) Give the examples  for Procedural statement and control flow.
Loop statement , Wait statement, Conditional statement, Case statement

18) Blocking and non-blocking statements differ in executing the statements . How?

They are two types of procedural assignments. Blocking statements are executed in the order in which they are specified in a sequential block. “= “is the operator used to specify blocking assignments. Blocking assignment executes sequentially and usually use Blocking statement for combinational logic. evaluation and assignment are immediately.

Non blocking statements allow scheduling of assignments without blocking execution of the statement that follow in a sequential block. “<=” is the operator used to specify non blocking assignment. For non-blocking assignment, the right hand side statement is evaluated and stored first then been assigned to the left hand side. assignment is postponed until rhs evaluations are done.
Using two ways to swap the content of two registers:
always@(posedge clk) begin                                     always@(posedge clk) begin
    temp=b;                                                                       a<=b;                  
    b = a;                                                                            b<=a;    
    a = temp;                                                              end
end

19) What are the various modeling used in Verilog?
1. Gate-level modeling
2. Data-flow modeling
3. Switch-level modeling
4. Behavioral modeling

20) What is the structural gate-level modeling?
Structural modeling describes a digital logic networks in terms of the components that make up the system. Gate-level modeling is based on using primitive logic gates and specifying how they are wired together.

21) What is Switch-level modeling?
Verilog allows switch-level modeling that is based on the behavior of MOSFETs.Digital circuits at the MOS-transistor level are described using the MOSFET switches.

22) Give the two blocks in behavioral modeling.
1. An initial block executes once in the simulation and is used to set up
initial conditions and step-by-step data flow
2. An always block executes in a loop and repeats during the simulation.

23) Value levels Condition in hardware circuits
Verilog supports four levels for the values needed to describe hardware referred to as value sets.

0 Logic zero, false condition
1 Logic one, true condition
X Unknown logic value
Z High impedance, floating state

24) Different bitwise operators. Operator symbol Operation performed Number of operands
~ Bitwise negation One
& Bitwise and Two
| Bitwise or Two
^ Bitwise xor Two
^~ or ~^ Bitwise xnor Two
~& Bitwise nand Two
~| Bitwise nor Two

24) Different arithmetic operators. Operator symbol Operation performed Number of operands
* Multiply Two
/ Divide Two
+ Add Two
- Subtract Two
% Modulus Two
** Power (exponent) Two

25) What are the types of conditional statements?
1. No else statement
Syntax : if ( [expression] ) true – statement;
2. One else statement
Syntax : if ( [expression] ) true – statement;
else false-statement;
3. Nested if-else-if
Syntax : if ( [expression1] ) true statement 1;
else if ( [expression2] ) true-statement 2;
else if ( [expression3] ) true-statement 3;
else default-statement;
The [expression] is evaluated. If it is true (1 or a non-zero value) true-statement is
executed. If it is false (zero) or ambiguous (x), the false-statement is executed.

26) What is meant by continuous assignment statement in verilog HDL?

[LEETCODE] Sort Colors

[LEETCODE] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

思路:

定义一个red指针在最左，一个blue指针在最右。

一个变量从0开始向blue指针扫描：

遇到red(0)  就跟red 指针对换，red 指向下一个，扫描变量指向下一个；

遇到blue(2)就跟blue指针对换，blue指向前一个，扫描变量不动，因为需要判断被换了的值。

代码:

An one-pass algorithm using only constant space

    void sortColors(int A[], int n) {

        int red  =0  ;

        int blue =n-1;

        int i=0;

        while(i<blue+1){

            if(A[i] == 0){

                std::swap(A[red], A[i]);

                red++;

                i++;

                continue;

            }

            if(A[i] == 2){

                std::swap(A[blue],A[i]);

                blue--;

                continue;

            }

            i++;

        }

    }

Linux Learning

Basic commands

Basic command

Go back to previous directory: cd ../  or cd../../  and so on

TCP/IP Learning (Updating)

1. TCP 3-way Handshake (SYC, SYC-ACK, ACK)
Link to the detailed analysis

Power Consumption (Updating)

Two components determine the power consumption in a CMOS circuit:

1. Static power consumption: input not switching

•       sub-threshold current;
•       gate leakage

      P_s = V_cc* I_cc

2. Dynamic power consumption: input switching

•       short circuit. current from V_dd to GND
•       switching circuit. charge or discharge output capacitance. P=Cout * V_cc^2

Counter and Divider

Asynchronous Counter
Asynchronous counters, also known as ripple counters, are not clocked by a common pulse and hence every flip-flop in the counter changes at different times. The flip-flops in an asynchronous counter is usually clocked by the output pulse of the preceding flip-flop. The first flip-flop is clocked by an external event. A synchronous counter however, has an internal clock, and the external event is used to produce a pulse which is synchronized with this internal clock. The diagram of an ripple counter is shown below.
Verilog Code and Test Bench

Synchronous Counter
Following is one kind of synchronous counter

Comparison

Advantages:

Asynchronous counter requires less circuitry and is easier to construct.

    Disadvantages:

   1) The asynchronous counter is slow. In a synchronous counter, all the flip-flops will change states simultaneously while for an asynchronous counter, the propagation delays of the flip-flops add together to produce the overall delay. Hence, the more bits or number of flip-flops in an asynchronous counter, the slower it will be.

   2) Secondly, there are certain "risks" when using an asynchronous counter. In a complex system, many state changes occur on each clock edge and some ICs respond faster than others. If an external event is allowed to affect a system whenever it occurs (unsynchronized), there is a small chance that it will occur near a clock transition, after some IC's have responded, but before others have. This intermingling of transitions often causes erroneous operations. And the worse this is that these problems are difficult to foresee and test for because of the random time difference between the events.

Divide by three                                                                  Verilog code for divide by 3 any duty

Module divide3(input clk, input rst, output out);

    Parameter s0 = 2'00; s1=2'01; s2 = 2'10;

    reg[1:0] state, nextstate;

    always@(posedge clk) begin

        if(rst) state<= s0;

        else state<= nextstate;

    end

    always@(*) begin

        case(state):

                s0: nextstate = s1;

                s1: nextstate = s2;

                s2: nextstate = s0;

                default: nextstate = s2;

        endcase

    end

assign out = (state==s0);

end module
Another Verilog Code for divide by 3 with 50% duty cycle

RTL Code ----- Fibonacci Sequence

Write the Fibonacci Sequence using Verilog HDL:

module fib(input clock, input rst, input [5:0] n, output reg ready, output [31:0] value)

reg [31:0] previous, current;

reg [5:0] counter;




// Reset the circuit

always @(posedge clk)

if(rst) begin

previous <= 32'd0;

current <= 32'd1;

counter <= 32'd0;

end



// Compute next Fibonacci number

always @(posedge clock)

begin

// Increment current index

counter <= counter + 1;



// Efficient adders are automatically inferred

current <= current + previous;

previous <= current;



if (counter == n)

ready <= 1;

end



// Read the value of the nth fibonacci number from the internal register

assign value = current;



endmodule

RAM (Especially SRAM) (Updating)

SRAM

Suppose the drain of M1 is called point A; the drain of M5 is called point B.

Read: Both bitlines start at Vdd (Precharged), cell pulls one down;
Suppose now A=VDD, B=GND;
M1 and M4 are cut off;
1) M2 and M3 are both pulling up, there would be no sizing constrains;
2) M5 is in triode and is pulling down, M6 is in saturation and is pulling up;
3) M5 must win to avoid flipping the cell.

Write: One bitline is pulled low, low bitline value overpowers cell;
Suppose still now A=VDD, B=GND; bitline is pulled down to GND, bitline_bar stays at high
M1 and M4 are cut off;
(1) Write a low:   M2 and M3 are both in triode, M2 must overwrite M4;
(2) Write a hight: M5 is in triode, M6 is in saturation, M6 must overwrite M1, this condition is contradict with the condition in READ mode.

DRAM

MOS Transistors

NMOS Transistor
CMOS





P-N Junction：
forward bias: p->n
reverse bias : n->p

for NMOS: Vsb > 0 RBB, Vth increase
for PMOS:  Vsb > 0 FBB,

Left Graph shows the Current equations at drain of a NMOS in different regions: subthreshold region, linear region, saturation region and velocity-saturation.

1) r_d in the equation of I_D in the subthreshold region is the DIBL factor and also the body effect.

2) K' = u*C_ox

3) (1+lamda*V_ds) is channel modulation

FIFO and LIFO(Updating)

FIFO

1)SYNCHRONOUS and ASYNCHRONOUS;
   If read and write clock domains are governed by same clock signal, whether one clock signal or two clock signals, the FIFO is said to be SYNCHRONOUS;
   If read and write clock domains are not governed by clock signals FIFO is said to be ASYNCHRONOUS. 

2) Here is an example of Implement FIFI using Verilog

3) FIFO Depth Calculation

Traffic Light(Updating)

1) The simple traffic light in a two way road.
     So there are two traffic lights 1 and 2 and each has green 1 and red 0;
                                                T1    T2
                                        S0     0       0
                                        S1     1       0
                                        S2     0       1
   促使state转变的：
1）input （not clock）
2）next clock edge

Delay in the graph is the key in the problem. In this case, we can generate another input signal as input.


2) A more complex traffic light

Multiprocessor cache coherence

Informally, we could say a memory system is coherent if any read of a data item returns the most recently written value of that data item.

The protocols to maintain coherence for multiple processors are called cache coherence protocols. key to implementing a cache coherence protocol is tracking the state of any sharing of a data block.

私有数据被单个处理器使用，而共享数据被多个处理器使用，当共享数据装载到cache中时，会有多个cache中形成副本。

两类协议：
1）目录式：把物理存储器的共享状态存放在一个地点，成为目录。
2）监听式：每个含有物理存储器中书记块副本的cache还要保留该数据块共享状态的副本，但是并不集中的保存状态，cache通常可以通过广播没接访问，所有的cache控制器对总线进行监视或监听，来确定它们是否含有总线或交换机上请求的数据块的副本。

Latch and Flip-Flop Design

Latch
Function: Data will be transferred as long as the clk is at positive high.

Graph 1) is the basic MUX-based Latch

Graph 2) has an additional keeper .
    The feedback inverter should be smaller to enable faster propagation of D

Graph 3) is the back-driving version.
    Also called TG-Latch
    Clk=1: D is transferred to A and then Q;
    Clk=0: D can't be propagate, old value is stored at A;
    No write conflict;
    The inverter at D is used for input noice protection.

Graph 4) used when the output is driven to noisy circuits.

Graph 1) to 4) are all static Latch.

Graph 5) is Dynamic Latch.

Take a look the waveform of clk, D and Q, the setup/hold time is w.r.t. the closing CLK edge!











Flip-Flop
Function: Data will be transferred at only one or both of the clk edges.

Graph 1) a pair of back to back latches, note the fi and fi_bar in the first graph should be exchanged.

Graph 2) The Master-Slave Latch Pair(MS Flip-Flop).
    Clk=0: master passes D to S;
    Clk=1: slave passes S to Q;
    D arrives just before clk: 0->1

Graph 3) The block representation of the pulse triggered Latch. (Need to be better analyzed)

Graph 4)The waveform of a flip-flop. The setup and hold time are all w.r.t. the rising edge if it is a posedge triggered flip-flop.



















Important Knowledge
Two ways are usually used to build storage elements:
1) using positive feedback to keep the value;
2) using capacitance to dynamically store the value;
    Adv  : faster
    Disad: less robust, sensitive to noise, particularly charge injection and charge sharing;
(Need to know what is charge sharing)

Reference: Course Notes

[LEETCODE] Binary Tree Postorder Traversal

[LEETCODE] Binary Tree Postorder Traversal 

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [3,2,1].

思路：

Postorder: 左右中。

注意点：

1. Recursive method iterate 条件先判断root 是否存在.

2. 对于Non-recursive method. 用两个vector，vector1存树上的node，vector2存值;
    1) 开始的判断root是否为NULL 不要忘了，且在vector1中存入root;
    2) 循环结束条件为vector1为空; 循环内容是，存node值到vector2，存node的左右（先左后右）node到vector1
    3) vector2存的顺序是反的，所以最后用一个reverse()函数

[LEETCODE]Evaluate Reverse Polish Notation

[LEETCODE] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

思路：

不是运算符的时候入栈，遇到运算符的时候出栈两个数字，计算新的值然后再入栈。

注意点：

1. string to integer 的处理， 使用函数 stoi();

2. 最后的结果是栈的最上面一个数。

3. 注意先出栈的是算式右边的数字，后出栈的是左边的，搞错了的话运算除法分母为0就错了

[LEETCODE] Length of Last Word

[LEETCODE]  Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0.

A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

思路:

最后一个单词的2种情况：

1， *hello; 2， *hello* ; *代表空格，可以为一个也可以为多个;
从前向后扫描，遇到空格就计算当前单词的长度，然后移动指针到下一个不是空格的地方继续计算，如果是情况1，指针移动到最后的‘\0’ 时，长度还未计算，所以循环结束之后再计算一次长度。

[LEETCODE] Integer to Roman

[LEETCODE] Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

思路:
Following is how integer is represented as Roman. 

当数字为1 和 5 的10 或10次方倍数时，罗马数字改变，小于1-3时为1的重复，4为在5左边添加1， 6-8 为在5的右边添加1，9为在新1的左边加旧1.

注意:

1. char name[number] = {" ", " ", " "} char数组的赋值
2. string result的用法：
    1) result.append(个数，char); 个数一定要有，最小为1；
    2) result.push_back(char/string); 一次只push一个进去.