Numbers with Different Base (Number System)

Decimal (base 10)	Binary (base 2)	Octal (base 8)	Hexadecimal (base 16)
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17	0 1 2 3 4 5 6 7 8 9 A B C D E F

Complements

Complements are used in digital computers for simplifying the subtraction operation and for logical manipulations. There are two types of complements for each base-r system: (1) the r’s complement and (2) the (r-1)’s complement. When the value of the base is substituted, the two types receive the names 2’s and 1’s complement for binary numbers, or 10’s and 9’s complement for decimal numbers:

The r’s Complement:

Given a positive number N in base r with an integer part of n digits, the r’s complement of N is defined as rⁿ-N for N≠0 and 0 for N=0. The following numerical example will help clarify the definition.

The 10’s complement of (52520)₁₀ is 10⁵ – 52520 = 47480.

The number of digits in the number is n = 5.

The 10’s complement of (0.3267)₁₀ is 1 – 0.3267 = 0.6733.

No integer part, so 10ⁿ = 10⁰ = 1.

The 10’s complement of (25.639)₁₀ is 10² – 25.639 = 74.361.

The 2’s complement of (101100)₂ is (2⁶)₁₀ – (101100)₂ = (1000000 – 101100)₂ = 010100.

The 2’s complement of (0.0110)₂ is (1 – 0.0110)₂ = 0.1010.

The (r – 1)’s Complement:

Given a positive number N in base r with an integer part of n digits and a fraction part of m digits, the (r – 1)’s complement of N is defined as rⁿ – r^-m – N. Some numerical examples follow:

The 9’s complement of (52520)₁₀ is (10⁵ – 1 – 52520) = 99999 – 52520 = 47479.

No fraction part, so 10^-m = 10⁰ = 1.

The 9’s complement of (0.3267)₁₀ is (1 – 10^-4 – 0.3267) = 0.9999 – 0.3267 = 0.6732.

No integer part, so 10ⁿ = 10⁰ = 1.

The 9’s complement of (25.639)₁₀ is (10² – 10^-3 – 25.639) = 99.999 – 25.639 = 74.360.

The 1’s complement of (101100)₂ is (2⁶ – 1)₁₀ – (101100)₂ = (111111 – 101100)₂ = 010011.

The 1’s complement of (0.0110)₂ is (1 – 2^-4)₁₀ – (0.0110)₂ = (0.1111 – 0.0110)₂ = 0.1001.

Postulates and Theorems of Boolean Algebra

Postulate 2 Postulate 5 Theorem 1 Theorem 2 Theorem 3, involution Postulate 3, commutative Theorem 4, associative Postulate 4, distributive Theorem 5, DeMorgan Theorem 6, absorption

x + 0 = x x + x’ = 1 x + x = x x + 1 = 1 (x’)’ = x x + y = y + x x + (y + z) = (x + y) + z x (y + z) = xy + xz (x + y)’ = x’y’ x + xy = x

x . 1 = x x . x’ = 0 x . x = x x . 0 = 0 xy =yx x(yz) = (xy)z x + yz = (x + y)(x + z) (xy)’ = x’ + y’ x(x + y) = x

Minterms and Maxterms for three Binary Variables

Minterms			Maxterms
x y z	Term	Designation	Term	Designation
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	x’ y’ z’ x’ y’ z x’ y z’ x’ y z x y’ z’ x y’ z x y z’ x y z	m0 m1 m2 m3 m4 m5 m6 m7	x + y + z x + y + z’ x + y’+ z x + y’+ z’ x’+ y + z x’+ y + z’ x’+ y’+ z x’+ y’+ z’	M0 M1 M2 M3 M4 M5 M6 M7

Karnaugh Map (K Map)

A Karnaugh map provides a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted variables. The Karnaugh map can also be described as a special arrangement of a truth table.

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.

The values inside the squares are copied from the output column of the truth table, therefore there is one square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two input variable. A is along the top and B is down the left hand side. The diagram below explains this:

The values around the edge of the map can be thought of as coordinates. So as an example, the square on the top right hand corner of the map in the above diagram has coordinates A=1 and B=0. This square corresponds to the row in the truth table where A=1 and B=0 and F=1. Note that the value in the F column represents a particular function to which the Karnaugh map corresponds.

Universal Gate

Universal Gates:

A universal gate is a gate which can implement any Boolean function without need to use any other gate type.

The NAND and NOR gates are universal gates.

In practice, this is advantageous since NAND and NOR gates are economical and easier to fabricate and are the basic gates used in all IC digital logic families.

In fact, an AND gate is typically implemented as a NAND gate followed by an inverter not the other way around.

Likewise, an OR gate is typically implemented as a NOR gate followed by an inverter not the other way around.

NAND Gate is a Universal Gate:

To prove that any Boolean function can be implemented using only NAND gates, we will show that the AND, OR, and NOT operations can be performed using only these gates.

NOR Gate is a Universal Gate:

To prove that any Boolean function can be implemented using only NOR gates, we will show that the AND, OR, and NOT operations can be performed using only these gates.

Adder

Half adder:

A half adder is a logical circuit that performs an addition operation on two one-bit binary numbers often written as A and B. The half adder output is a sum of the two inputs usually represented with the signals C_out and S where sum=2*Cout+S. Following is the logic table for a half adder:

Inputs		Outputs
A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Example half adder circuit diagram

As an example, a Half Adder can be built with an XOR gate and an AND gate.

              ___________

     A ------|           |

             |   Half    |----- S=A(+)B

             |   Adder   |

             |           |----- C=A.B

     B ------|___________|

Full adder:

Schematic symbol for a 1-bit full adder with C_in and C_out drawn on sides of block to emphasize their use in a multi-bit adder.

A full adder is a logical circuit that performs an addition operation on three one-bit binary numbers often written as A, B, and C_in. The full adder produces a two-bit output sum typically represented with the signals C_out and S where sum=2*Cout+S. The full adder's truth table is:

Inputs			Outputs
A	B	Ci	Co	S
0	0	0	0	0
1	0	0	0	1
0	1	0	0	1
1	1	0	1	0
0	0	1	0	1
1	0	1	1	0
0	1	1	1	0
1	1	1	1	1

A full adder can be implemented in many different ways such as with a custom transistor-level circuit or composed of other gates. One example implementation is with S=(A(+)B)(+)Cin and Cout=(A.B)+(Cin.(A(+)B)).

Example full adder circuit diagram
Inputs: {A, B, Cin} → Outputs: {S, Cout}

Example full adder circuit diagram using only NAND and XOR gates
Inputs: {A, B, Cin} → Outputs: {S, Cout}

In this implementation, the final OR gate before the carry-out output may be replaced by an XOR gate without altering the resulting logic. Using only two types of gates is convenient if the circuit is being implemented using simple IC chips which contain only one gate type per chip.

A full adder can be constructed from two half adders by connecting A and B to the input of one half adder, connecting the sum from that to an input to the second adder, connecting C_i to the other input and OR the two carry outputs. Equivalently, S could be made the three-bit XOR of A, B, and C_i, and C_o could be made the three-bit majority function of A, B, and C_i.

Digital IC Terminology

Current and voltage Parameters:

· V_IH(min)-High Level Input Voltage: The minimum voltage level required for a logical 1 at an input. Any voltage below this level will not be accepted as a HIGH by the logic circuit.

· V_IL(max)-Low Level Input Voltage: The maximum voltage level required for a logical 0 at an input. Any voltage above this level will not be accepted as a LOW by the logic circuit.

· V_OH(min)-High Level Output Voltage: The minimum voltage level at a logic circuit output in the logical 1 state under defined load conditions.

· V_OL(max)-Low Level Output Voltage: The maximum voltage level at a logic circuit output in the logical 0 state under defined load conditions.

· I_IH(min)-High Level Input Current: The current that flows into an input when a specified high level voltage is applied to that input.

· I_IL(max)-Low Level Input Current: The current that flows into an input when a specified low level voltage is applied to that input.

· I_OH(min)-High Level Output Current: The current that flows from an output in the logical 1 state under specified load conditions.

· I_OL(max)-Low Level Output Current: The current that flows from an output in the logical 0 state under specified load conditions.

The high state noise margin V_NH is defined as

V_NH=V_IH(min)-V_OH(min)

The low state noise margin V_NL is defined as

V_NL=V_IL(max)-V_OL(max)

Carry Propagation

The addition of two binary numbers in parallel implies that all the bits of the angend and addend are available for computation at the same time.

As in any combinational ckt, the signal must propagate through the gates before the correct output sum is available in the output terminals.

A binary parallel adder is a digital function that produces the arithmetic sum of two binary numbers in parallel. It consists of full adders connected in cascade, with the output carry from one full adder connected to the input carry of the next full adder.

Figure shows the interconnection of 4 full adder (FA) ckts to provide a 4 - bit binary parallel adder. The augend bits of A and the addend bits of B are designated by subscript numbers from right to left, with subscript 1 denoting the low order bit. The carries are connected in a chain through the full adders. The input carry to the adder is C₁ and the output carry is C₅. The S outputs generate the required sum bits. When the 4 bit full adder ckt is enclosed within an IC package, it has four terminals for the augend bits, four terminals for the addend bits, four terminals for the sum bits, and two terminals for the input and output carries.

Binary Coded Decimal (BCD) Adder

Consider the arithmetic addition of two decimal digits in BCD together with a possible carry from a previous stage.

Each input digit does not exceed 9, the output sum cannot be greater than 9+9+1=19.

This adder will from the sum in binary and produce a result which may range from 0 to 19.

We found the derivation of a BCD adder, when the binary sum is equal to or less than 1001, the corresponding BCD number is identical.

When the binary sum is greater then 1001, the addition of binary 6(0110) to the binary sum converts it to the correct BCD representation and also produces an output carry as required.

An output carry can be expressed by the Boolean function: C=K+Z₈Z₄+Z₈Z₂: When C=1, it is necessary to add 0110 to the binary sum and provide an output carry for the next stage.

A decimal parallel adder that adds n decimal digits needs n BCD adder stages. The output carry one stage must be connected to the input carry of the next higher order stage.

Magnitude Comparator

A magnitude comparator is a combinational ckt that compares two numbers, A and B, and determines their relative magnitudes.

The outcomes of the comparison is specified by three binary variables that indicate whether A>B, A=B or A

Consider two numbers A and B, with four digits each A=A₃A₂A₁A₀ and B=B₃B₂B₁B₀

The equivalence function: xi=AiBi+A’iB’i as i=0,1,2,3,….

If (A=B)=x₃x₂x₁x₀

(A>B)=A₃B’₃+x₃A₂B’₂+x₃x₂A₁B’₁+x₃x₂x₁A₀B’₀

(A₃B₃+x₃A’₂B₂+x₃x₂A’₁B₁+x₃x₂x₁A’₀B₀

Decoder

A decoder is a combinational ckt that converts binary information from n input lines to a maximum of 2ⁿ unique output lines.

If the n-bit decoded information has unused or don’t care combinations, the decoder output will have less than 2ⁿ outputs.

Encoder

An encoder is a digital function that produces a reverse operation from that of a decoder. An encoder has 2ⁿ(or less) input lines and n output lines. The output lines generate the binary code for the 2ⁿ input variables.

We found from truth table x=D4+D5+D6+D7; y=D2+D3+D6+D7; z=D1+D3+D5+D7

D₀ is not connected to any OR gate; the binary output must be all 0’s in this case.

The ckt has 8 inputs and could have 2⁸=256 possible input combinations. Only 8 of these combinations have any meaning. The other inputs combinations are don’t care conditions.

Multiplexer

Multiplexing means transmitting a large number of information units over a smaller number of channels or lines. A digital multiplexer is a combinational ckt that selects binary information from one of many input lines and directs it to a single output line. The selection of a particular input line is controlled by a set of a selection lines. There are 2n input lines and n selection lines whose bit combinations determine which input is selected.

A in decoders, multiplexer ICs may have an enable input to control the operation of the unit. When the enable input is in a given binary state, the outputs are disabled, and when it is in the other state (the enable state), the ckt functions as a normal multiplexer. The enable input can be used to expand two or more multiplexer ICs to a digital multiplexer with a larger number of inputs.

Demultiplxer

· A decoder with an enable input can function as a demultiplexer. A demultiplexer is a ckt that receives information on a single line and transmits this information on one of 2n possible output lines.

· A decoder with an enable input is referred to as a demultiplexer. It is the enable input that makes the ckt a demultiplexer.

· If E is 0 then one demultiplexer is enabled and the other is disabled and for E is 1 then vice-versa.

Read Only Memory (ROM)

· A ROM is a device that includes both the decoder and the OR gates with in a single IC package.

· Block diagram shows, n inputs lines, each bit is called an address and m output lines, each bit is called a word.

· The ROM is very often used to implement a complex combinational ckt in one IC package.

· A ROM is essentially a memory device in which a fixed set of binary information is stored.

· ROMs have many important applications in the design of digital computer systems.

Programmable Logic Array (PLA)

· PLA is similar to a ROM in concept, but the PLA does not provide full decoding of the variables and does not generate all the minterms as in the ROM. In PLA, the decoder is replaced by a group of AND gates.
· PLA consists of n inputs, m (OR gate) outputs, K (AND gate) product terms and m sum terms.
· The PAL is the opposite of the ROM, having a programmable set of ANDs combined with fixed ORs.
· Compared to a ROM and a PAL, a PLA is the most flexible having a programmable set of ANDs combined with a programmable set of ORs.

Advantages:

o A PLA can have large N and M permitting implementation of equations that are impractical for a ROM (because of the number of inputs, N, required

o A PLA has all of its product terms connectable to all outputs, overcoming the problem of the limited inputs to the PAL Ors

o Some PLAs have outputs that can be complemented, adding POS functions

Disadvantages:

o Often, the product term count limits the application of a PLA.

o Two-level multiple-output optimization is required to reduce the number of product terms in an implementation, helping to fit it into a PLA.

o Multi-level circuit capability available in PAL not available in PLA. PLA requires external connections to do multi-level circuits.

3-input, 3-output PLA with 4 product terms.

The IC Digital Logic Families

The IC Digital Logic Families:

· RTL-Resistor-Transistor Logic.

· DTL-Diode-Transistor Logic.

· I2L-Integrated-Injection Logic.

· TTL-Transistor-Transistor Logic.

· ECL-Emitter-Coupled Logic.

· MOS-Metal-Oxide Semi-conductor.

· CMOS-Complementary Metal-Oxide Semi-conductor.

Advantage of CMOS:

· Ckt is must simpler.

· Easy to fabricate.

· Faster.

· Power consumption is low.

· Comparatively cheeper.

Disadvantage of CMOS is the logic is always invert.

Flip Flop

"Flip-flop" is the common name given to two-state devices which offer basic memory for sequential logic operations. Flip-flops are heavily used for digital data storage and transfer and are commonly used in banks called "registers" for the storage of binary numerical data.

RS (Reset-Set) flip-flop:

The fundamental latch is the simple RS flip-flop (also commonly known as SR flip-flop), where R and S stand for reset and set, respectively. It can be constructed from a pair of cross-coupled NAND or NOR logic gates. The stored bit is present on the output marked Q.

Normally, in storage mode, the R and S inputs are both low, and feedback maintains the Q and Q outputs in a constant state, with Q the complement of Q. If S is pulsed high while R is held low, then the Q output is forced high, and stays high even after S returns low; similarly, if R is pulsed high while S is held low, then the Q output is forced low, and stays low even after R returns low.

The next-state equation of the RS flip-flop is

where Q is the current state. Q_next becomes Q (the stored value) at clock edge.

RS Flip-Flop operation (BUILT WITH NOR GATES)
Characteristic table			Excitation table
S	R	Action	Q(t)	Q(t+1)	S	R	Action
0	0	Keep state	0	0	0	X	No change
0	1	Q = 0	1	0	0	1	reset
1	0	Q = 1	0	1	1	0	set
1	1	Race Condition	1	1	X	0	No Change

The D Flip-Flop

The D flip-flop tracks the input, making transitions with match those of the input D. The D stands for "data"; this flip-flop stores the value that is on the data line. It can be thought of as a basic memory cell. A D flip-flop can be made from a set/reset flip-flop by tying the set to the reset through an inverter. The result may be clocked.

Clocked D Flip-Flop:

Clocked D Flip-Flop:A D flip-flop constructed from a NAND-latch .

D Flip-Flop from NAND Latch:

The output Q will track the input D so long as the flip-flop remains enabled.

Ouput: Clocked D Flip-Flop:

The D flip-flop tries to follow the input D but cannot make the required transitions unless it is enabled by the clock. Note that if the clock is low when a transition in D occurs, the tracking transiton in Q occurs at the next upward transition of the clock.

J-K Flip-Flop

The J-K flip-flop is the most versatile of the basic flip-flops. It has the input- following character of the clocked D flip-flop but has two inputs,traditionally labeled J and K. If J and K are different then the output Q takes the value of J at the next clock edge.

If J and K are both low then no change occurs. If J and K are both high at the clock edge then the output will toggle from one state to the other. It can perform the functions of the set/reset flip-flop and has the advantage that there are no ambiguous states. It can also act as a T flip-flop to accomplish toggling action if J and K are tied together. This toggle application finds extensive use in binary counters.

J-K Flip-Flop Structure:

A simplified version of the versatile J-K flip-flop. Note that the outputs feed back to the enabling NAND gates. This is what gives the toggling action when J=K=1.

Switching : J-K Flip-Flop:

The positive going transition (PGT) of the clock enables the switching of the output Q. The "enable" condition does not persist through the entire positive phase of the clock. The J & K inputs alone cannot cause a transition, but their values at the time of the PGT determine the output according to the truth table. This is an application of the versatile J-K flip-flop.

T Flip Flops

T Flip Flops Logic Gate Diagram and Outputs:

The T or "toggle" flip-flop changes its output on each clock edge, giving an output which is half the frequency of the signal to the T input.








It is useful for constructing binary counters, frequency dividers, and general binary addition devices. It can be made from a J-K flip-flop by tying both of its inputs high.

Construction of T flip-flop from a J-K flip-flop.