Digital Logic - Programmable Logic Devices

Programmable Logic Devices (PLDs) are IC chips with internal logic gates connected by electronic fuses.
The fuses can be programmed to obtain different circuit configuration.

PLD(s) can be divide into 3 type of classes:-

        - Programmable Logic Array (PLA)
        - Field-Programmable Gate array
        - Programmable Array Logic

Programmable Logic Array (PLA)

-          a relatively small PLD that contains two levels of logic, where both levels are programmable

-           consider one of the most simplest device used in PLD

-          consist of regular arrangement of NOT, AND, and OR (gates)

         Each input have to pass through the NOT gates so that each input and it’s compliment are available                  
         to each AND gate. The output of each AND gate is available to each OR gate, and the output of each
         OR gate is the output of the chips

 a) Layout for 3-input and 2-output PLA

     b)  Programmed PLA

Field-Programmable Gate Array(FPGA)

The difficulty with increasing capacity of a strict SPLD architecture is that the structure of the programmable logic planes grows too quickly in size as the number of inputs is increased. The only feasible way to provide large capacity devices based on SPLD architectures is then to integrate multiple SPLDs onto a single chip and provide interconnect to programmably connect the SPLD blocks together. Most of the PLD product exist in the market are collectively referred to Complex PLDs (CPLDs) and the most important CPLD is FPGA

In FPGA contain an element called logic block. It is array of uncommitted circuit element.

The diagram above shows a simple logic block that consist of a D flip-flop, a 2-to-1 multiplexer, and a 16 bit lookup table. The lookup table is a memory that is consisting 16 1bit element, so that 4 lines input are required to select one of the 16 bits.

LIM ZERKIE 
 B031210127

Digital Logic - Boolean Algebra

A mathematical tool used in describing, analyzing, designing and implementing digital circuits. A Boolean algebra is the combinations of variables and operators. It has one or more inputs and produces an output in the range of 0 or 1. The complement of a variable is shown by a bar over the letter.

Boolean equation can be represented in two forms:

l  Boolean Addition (Sum-of-products(SOP)

It is equivalent to the OR operation.  A sum term is produced by an OR operation with no AND operations involved. A sum term is equal to 1 when one or more of the literals in the term are 1. A sum term is equal to 0 only if each of the literals is 0.

l  Boolean Multiplication (Product-of –sums(POS))

It is equivalent to the AND operation. A product term is produced by an AND operation with no OR operations involved. A sum term is equal to 1 if each of the literals in the term is 1. A sum term is equal to 0 when one or more of literals are 0.

Boolean Function

l  Binary variables/literals (complemented or not)

l  Binary operators : (＋→ OR) and ( · → AND)

l  Unary operator : ( ‘ → NO )

l  Equal sign

l  Parentheses

Example : F1(a,b,c)=ab’+abc’+b’(a’+c’)

   Table Basic Laws of Boolean Algebra

	AND Form	OR Form
Identity Law	A·1 = A	A+0 = A
Zero and One Law	A·0 = 0	A+1 = 1
Inverse Law	A·A’ = 0	A+A’ = 1
Idempotent Law	A·A = A	A+A = A
Commutative Law	A·B = B·A	A+B = B+A
Associative Law	A·(B·C) = (A·B) ·C	A+(B+C) = (A+B) + C
Distributive Law	A+(B·C) = (
	A(A+B) =A	A+A·B = A A+A’B = A+B
DeMorgan’s Law	(A·B)’ = A’+B’	(A+B)’= A’·B’
Double Complement Law	X=X

Other example Law of Boolean Algebra

Absorption Law derivation:

A+A·B = A·1+A·B                                                           A·(A+B)=(A+0)(A+B)

            = A·(1·B)                                                                            = A+(0·B)

            = A·1                                                                                   =A+0

            = A                                                                                      =A

A+A’B = (A+B’) ·(A+B)       A·(A’+B) = A·A’+A·B         A·B+A·B’ = A·(B+B’)         (A+B) ·(A+B’) = A+(B+B’)

            = 1·(A+B)                                 = 0+A·B                             = A·1                                           = A+0

            =A+B                                        =A·B                                  =A                                                =A

Karnaugh Maps

A Karnaugh map is two-dimensional truth-table.

Two inputs A and B can take on values of either 0 or 1, high or low, open or closed, True or False, as the case may be. There are 2² = 4 combinations of inputs producing an output. These four outputs may be observed on a lamp in the relay ladder logic, on a logic probe on the gate diagram. These outputs may be recorded in the truth table, or in the Karnaugh map. Look at the Karnaugh map as being a rearranged truth table. The Output of the Boolean equation may be computed by the laws of Boolean algebra and transfered to the truth table or Karnaugh map.

The Karnaugh map is organized so that we may see that commonality.

Rules of Simplification

1.  No zeros allowed.

2.  No diagonals.

3.  Only power of 2 number of cells in each group.

7.Wrap around allowed.

8.Fewest number of groups possible.

   Example to grouping the 1s

Example:

YU HONG SHENG   

B031210099

Arithmetics For Computers (Number System & Operations) - Floating Point Arithmetic

In floating point arithmetic, addition and subtraction are more complex than multiplication and division. This is because of the need for alignment. There are four basic phases of the algorithm for addition and subtraction:

1.       Check for zeros

2.       Align the significant.

3.       Add or subtract the significant.

4.       Normalize the result.

Example:

X = 0.3 x 10² = 30

Y = 0.2 x 10³ = 200

X + Y = (0.3 x 10^2-3 + 0.2) x 10³ = 0.23 x 10³ = 230

X - Y = (0.3 x 10^2-3 -0.2) x 10³ = (-0.17) x 10³ = -170

X x Y = (0.3 x 0.2) x 10^2-3 = 0.06 x 10⁵ = 6000

X + Y = (0.3 x 0.2) x 10^2-3 = 1.5 x 10^-1 = 0.15

Floating Point

l  We need a way to represent

-          Numbers with fractions, e.g. : 3.142

-          Very small numbers, e.g. : 0.0000001

-          Very large numbers, e.g. : 3.1428 x 10⁹

l  Representation:

-          sign, exponent, significant : (–1)^sign × significant × 2^exponent

-          more bits for significant gives more accuracy

-           more bits for exponent increases range

l  IEEE 754 floating point standard

-          single precision: 8 bit exponent, 23 bit significant

-          double precision: 11 bit exponent, 52 bit significant

IEEE 754 floating point standard

l  Leading “1” bit of significant is implicit

l   Exponent is “biased” to make sorting easier

-            all 0s is smallest exponent all 1s is largest

-             bias of 127 for single precision and 1023 for double precision  

-            summary: (–1)^sign × (1+significand) × 2^{exponent – bias}

l  Example:  

-            decimal: -.75 = -3/4 = -3/22 

-            binary: -.11 = -1.1 x 2-1

-             floating point: exponent = 126 = 01111110  

-            IEEE single precision: 10111111010000000000000000000000

IEEE 754 Standard

Representation of floating point numbers in IEEE 754 standard:

Magnitude of numbers that can be represented is in the range:

2^-126(1.0) to 2₁₂₇(2-2^-23)

This is approximately:

1.8 x 10^-38 to 3.40 x 10³⁸

Floating Point Complexities

l  In addition to overflow we can have “underflow” •

l  Accuracy can be a big problem

-            IEEE 754 keeps two extra bits, guard and round

-            four rounding modes

-            positive divided by zero yields “infinity”

-            zero divide by zero yields “not a number” 

-            other complexities

Floating Point Addition Example

e.g. : Add 9.999 x 101 and 1.610 x 10-1 assuming 4 decimal digits

1. Allign decimal point of number with smaller exponent

1.610 × 10^-1= 0.161 × 10⁰ = 0.0161 × 10¹

Shift smaller number to right

2. Add significant  

9.999 + 0.016 = 10.015 → SUM = 10.015 × 10¹

NOTE: One digit of precision lost during shifting. Also sum is not normalized

3. Shift sum to put it in normalized form 1.0015 × 10²

4. Since significant only has 4 digits, we need to round the sum

SUM = 1.002 × 10²

NOTE: normalization maybe needed again after rounding,

e.g, rounding 9.9999 you get 10.000

Accurate Arithmetic – Guard & Round bits •

l  IEEE 754 standard specifies the use of 2 extra bits on the right during intermediate calculations – Guard bit and Round bit 

l  Example: Add 2.56 × 10⁰ and 2.34 × 10² assuming 3 significant digits and without guard and round bits

2.56 × 100 = 0.0256 × 10²

2.34 x 0.02 = 2.36 × 10² 

l  With guard and round bits

2.34 x 0.0256 = 2.3656 × 10²

ROUND  → 2.37 × 10⁰

Infinity arithmetic

Infinity arithmetic is treated as the limiting case of real arithmetic, with the infinity values given the following interpretation:

-∞ < (every finite number) < +∞

With the exception of the special cases discussed subsequently, any arithmetic operation involving infinity yields the obvious result.

For Example:

5 + (+∞) = +∞                  5 ÷ (+∞)            = +0

5 - (+∞) = -∞                    (+∞) + (+∞)     = +∞

5 + (-∞) = -∞                    (-∞) + (+∞)      = -∞

5 - (-∞) = +∞                    (-∞) - (+∞)       = -∞

5 x (+∞) = +∞                   (+∞) - (-∞)       = +∞

Quiet And Signaling NaNs

Table Operations that Produce a Quiet NaN

      Yu  Hong Sheng 
B031210099  

Arithmetics For Computers (Number System & Operations) - Floating Point Representation

Floating Point Representation :  i)  very small numbers

                                                ii) very large numbers

Floating point has it’s own standard :

1         .       Define by IEEE Std.

2         .       Almost adopted globally

3         .       Contain of 2 representation :-

-          Single precisions

-          Double precisions

IEEE floating has it’s own format :

31   30                               23 22                                0

s

Exponent (E)

Fraction (F)

FORMULA is : X=(-1)^s * (1+ Fraction) * 2^{(exponent – bias)}

S can be 2 values 0 or 1

If 0 means is non negative

If 1 means is negative

The exponent  E  is the power 2 must be raised to in the scientific notation of number.

The exponent is biased with value 127 and the range is between “[(-126) – 127]”

For exponent    -  single : 8 bits
                        -  double : 11 bits

For fraction  -  single :  23 bits
                    -  double :  52 bits

Exponent is excess representation , also can be written as “actual exponent+bias”

-          This is to ensure the exponent is unsigned

-          In single : bias = 127

In double : bias = 1203

Normalized significand :-

•          The value is between  1.0 < significand <2.0
•          Always has a leading pre-binary-point 1 bit
•       Significand is FRACTION with “1“ restored.

LIM ZERKIE 
B031210127

Digital Logic - Combinational Circuits

1)Analysis of Combinational Circuits

Truth Table

Steps to create the truth table :

   Sample of combinational circuit

ⅰ. List all of the inputs found in the circuit, one input per column.

   

a	b	c	d

ⅱ.Next, list the output.

a	b	c	d	y

ⅲ.Enumerate all possible combinations of the input values. (For a circuit with n inputs,   

     there are 2ⁿ combinations)

a	b	c	d	y
0	0	0	0
0	0	0	1
0	0	1	0
0	1	0	0
1	0	0	0
1	1	0	0
0	1	1	0
0	0	1	1
1	0	0	1
0	1	0	1
1	0	1	0
1	1	1	0
1	1	0	1
1	0	1	1
0	1	1	1
1	1	1	1

ⅳ.Circuit annotated with the input values abcd = 1101.

                

ⅴ.Complete truth table for the circuit.

  

a	b	c	d	y
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	1	0	0	1
1	0	0	0	1
1	1	0	0	0
0	1	1	0	1
0	0	1	1	0
1	0	0	1	1
0	1	0	1	1
1	0	1	0	1
1	1	1	0	0
1	1	0	1	0
1	0	1	1	0
0	1	1	1	0
1	1	1	1	0

Boolean Function

ⅰ.Write down the Boolean logical expression at the output of each gate instead of  

     substituting actual values of 0’s and 1’s for the inputs.

ⅱ. From the diagram,we get the output y = (ab+cd)'.

ⅲ. Substitute all possible combinations of values for all of the variables in  

      the final equation, we should obtain the same truth table as before.

2) Synthesis of Combinational Circuits

- A reverse procedure of the analysis of combinational circuits

 ⅰ.Start with a description of the operation of the circuit.

 ⅱ. Derive either the truth table or the Boolean logical function that precisely describes   

        the operation of the circuit.

 ⅲ. Translate that into a circuit diagram.

3) Technology Mapping

- To reduce implementation cost and time to produce a digital circuit on an IC, off-the- 

  shelf semi-custom gate arrays is used.

- Many gate arrays are ICs that have only NAND gates or NOR gates built in them, but 

  their input and output connections are not yet connected.

- To use these gate arrays, connections between the gates should be specified.

- convert all AND, OR, and NOT gates in the circuit to use only NAND or NOR gates,  

  depending on what is available in the gate array.

- These NAND and NOR gates usually have the same number of fixed inputs.

- Any combinational circuit can be constructed with either only NAND gates or only   

  NOR gates to make clear when we look at how these gates are built at the transistor   

  level.

- The conversion of any given circuit to use only 2-input NAND or 2-input NOR gates   

  is possible by observing the following equalities which are obtained from the Boolean   

  algebra theorems.

4) Minimization of Combinational Circuits

   Karnaugh Maps (K-map)

- The K-map is a two-dimensional array of squares, each of which represents one 

  minterm in the Boolean function.

- Thus, the map for an n-variable function is an array with 2ⁿ squares.

- Labelling of two adjacent columns or rows differ in only one bit change but for the  

  third and fourth rows are always interchanged.

Using K-map to minimize a 4-variable function

1) To see how the adjacencies involving one common term can appear,suppose we   

    have the logic equation below:

                   F = A’BC’D’+ A’BCD’ + AB’C’D’+ AB’CD + 

                          ABCD’ +A’BC’D + AB’CD’ + A’B’CD

ⅰ.Since there are four variables in this equation, a four variable K-Map is   

     used.

ⅱ. Encircle the largest number of “ones” that are a power of two until all ones 

      are“covered”. This means 2, 4 or 8 terms.

ⅲ.The reduced product terms are now determined by observing the coverings. If the 

     variables under a covering do not change they will be in the final minimized equation,  

     else they are excluded.

     For example, under the shaded covering, the variables corresponding to A, B and C   

     do not change.Therefore that term becomes ABC. The horizontal covering at the   

     bottom has variables B, C and D do not change. Thus, that minimized term

     becomes BCD.

ⅳ.The minimized equation is now written out by summing the reduced product terms.  

     Thus the minimized equation becomes:

                        F = AB’D’ + B’CD + BCD’ + A’BC’

      

                                                                                                       KANG YI SHIN

B031210356