Translate page

Wednesday, December 25, 2013

DIGITAL BASIC - 1.5 : Multiplexer (MUX)



Index Chapter1 Chapter2 Chapter3 Chapter4
Digital
Background
Semiconductor Background CMOS
Processing


1.1 1.2 1.3a 1.3b 1.4 1.5 1.6
Number
System
Digital
Arithmetic
Logic
Gates
Logic
Gates
Combinational
Circuits
Multiplex
(MUX)


De-Multiplexer:
  • Receives information on a single line and transmits that information on one of 2n possible output lines.
  • The selection of specific output line is controlled by the bit values of ‘n’ selection lines.
Multiplexer:
  • Multiplexing means transmitting a large number of information units over a smaller number of channels lines.
  • A digital multiplexer is a combinational circuit that selects binary information from one of many inputs lines and directs it in a signal output line.
  • The selection of a particular line is controlled by a set of selection lines.
  • Normally, there are 2n input lines and ‘n’ selection lines whose bit combinations determine which input is selected.”
  • Multiplexers can be used for the implementation of Boolean functions, combinational circuits. They can also used for parallel to serial conversion.
  • Multiplexer is also called data selector or universal circuit.
  • It is used for connection two or more sources to a single destination among computer units and it is useful for constructing a common bus system







Important Points:
To implement 2n :1 MUX by using 2:1 MUX, the total number or 2:1 MUX required is 2n-1

Given MUX
To be implemented
MUX
Required
No of MUX
4 : 1
16 : 1
4+1=5
4 : 1
64 : 1
16+4+1=21
8 : 1
64 : 1
8+1 =9
8 : 1
256 : 1
32+4+1=37

Implementation of Higher Order MUX using Lower Order MUX:
4:1 MUX by 2:1 MUX

Total number of 2: 1 MUX = 3

MUX as a universal logic gate

Gate Type
Implemented by MUX  + Equation
Buffer
Y=output = A

NOT/Inverter
Y=A’

AND
Y=A.B

OR
Y=A+B

NOR
Y=(A+B)’

NAND
Y=(A.B)’

XOR


XNOR



Implementation of Boolean function using Multiplexer:
The Boolean function may be implemented in 2n to 1 multiplexer.
  • If we have a Boolean function of n variables, we take n-1 of these variables and connect them to the selection lines of a multiplexer (let’s say these are “select variables”).
  • The remaining single variable (MSB variable) of the function is used for the inputs of the multiplexer (let’s say these are “input variable”).
  • Now form the implementation table
    • First row lists all those minterms where “input variable” is complemented (say 0).
    • Second row lists all those minterms where “input variable” is in its normal form (say 1).
  • The minterms are circled as per the given Boolean function. Now use the following steps to find out final multiplexer inputs.
    • If the 2 minterms in a column are not circled, 0 is placed to the corresponding multiplexer inputs.
    • If the 2 minterms in a column are circled, 1 is placed to the corresponding multiplexer inputs.
    • If the minterms in the second row is circled and the first row is not circled, apply second row of variable to the corresponding multiplexer inputs.
    • If the minterms in the first row is circled and not the second row, apply first row of the variable to the corresponding multiplexer inputs.
Example:  Implementation of given function using 8 to 1 multiplexer
F(A,B,C,D) = Æ© (1,3,4,11,12,13,14,15)
Solution.
  • Total number of variable n = 4 (A,B,C,D)
  • Number of select lines:  n-1= 3 (B, C, D)
  • The given function has 4 variable, so 16 possible minterms (0 – 15) are entered in the implementation table.
  • All the minterms are divided into 2 groups
    • The first group (0-7) minterms  are entered in the first row  (Variable A =0)
    • The second group (8–15) minterms are entered in the second row (Variable A= 1)
  • Circle the minterm number as per function, which you have to implement (in this case it’s 1,3,4,11,12,13,14,15)
  • Find out the multiplexer input as per above given steps.








Implementation Table

Given multiplexer is 8:1
Logic diagram

Example
Implement the following Boolean function using 8 : 1 MUX
F(A,B,C,D) = Æ© m(0,1,2,4,6,9,12,14)
Solution.
Select lines are B, C and D

Follow all the steps as per above points.


Example
Implement the following Boolean function with 8 : 1 multiplexer
F(A,B,C,D) = ∏M (0,3,5,6,8,9,10,12,14)

Solution
The given maxterms are inverted to obtain minterms. From the minterms, we can implement the above Boolean function by using 8 : 1 multiplexer. Select lines are B, C and D, the input variable is A.
F(A,B,C,D) = Æ© m(1,2,4,7,11,13,15)


Example  
Implement the following Boolean function with 8 : 1 multiplexer
F(A,B,C,D) = Æ© m (0,2,6,10,11,12,13) + Æ© d(3,8,14)
Solution.
The Boolean function has three don’t care conditions which can be treated as either 0’s or 1’s. In this example don’t care condition is consider as 1.




Thursday, December 19, 2013

DIGITAL BASIC - 1.4 : Combinational Circuits


Introduction



Index Chapter1 Chapter2 Chapter3 Chapter4
Digital
Background
Semiconductor Background CMOS
Processing


1.1 1.2 1.3a 1.3b 1.4 1.5 1.6
Number
System
Digital
Arithmetic
Logic
Gates
Logic
Gates
Combinational
Circuits
Multiplex
(MUX)

Digital circuits are of two types:
  • Combinational Circuits (also known as Time-Independent Logic)
    • Combinational digital circuits are those circuits where output is function of present input only.
  • Sequential Circuits
    • Output depends not only on the present input but also on the history of the input

Let’s discuss these circuits in a comparison table format.

Combinational Circuits
Sequential Circuits
No Memory (No memory unit required)
Has Memory (Memory unit require)
Output is function of Present input.
Output = Æ’(In)
Output is function of present + previous inputs.
Output = Æ’(In, previous In)
For designing Basic gates (AND,OR,NOT) or Universal gates (NAND,NOR) are used
Used to construct finite state machines, a basic building block in all digital circuitry, as well as memory circuits and other devices.
Examples of combinational digital circuits are:
 Half Adder, Full Adder, Half subtractor, Full subtractor, Code converter, Decoder, Multiplexer, De-multiplexer, Encoder, ROM etc
Examples for sequential digital circuits are:
Registers, Shift register, Counters etc.
The construction of combinational logic is generally done using one of two methods:
  • A sum of products (SOP)
  •  A product of sums (POS)

The construction of Sequential logic is generally done using State tables.


Faster because the delay between the input and output  is due to the propagation delay of the gates only
Slower then the combinational  circuits
Easy to design
Compartively harder to design

Classification of Combinational logic Circuits:

  • Arithmetic and logical functions
    •  Adders
    • Subtractors
    • Comparitors
    • PLDs
  •  Data transmission
    • Multiplexers
    • Demultiplexers
    • Decoders
    • Encoders
  • Code Converters
    • Binary Converter
    • BCD converter
    • 7-segment display

Classification of Sequential Circuits

  • Synchronous Circuits
  •  Asynchronous Circuits


Synchronous Sequential Circuits
Asynchronous Sequential circuits
Memory Elements are clocked flipflop
Memory elements are either unclocked Flipflops or time delay elements
The change in the input signal can effects memory elements upon activation of clock signal
The change in the input signal can effects the memory elements at any instant of time.
Maximum operating speed of the clock depends on the time delay involved
Because of the absence of clock, Asynchronous circuits can operate faster than the Synchronous Circuits.
Easy to design
More difficult to design
the state of the device changes only at discrete times in response to a clock signal
circuits the state of the device can change at any time in response to changing inputs


Combinational Circuits:

Let’s discuss few of the combinational circuit’s details (like Block diagram, Circuit Diagram and Truth table). I am not discussing in detail about the circuit diagram here because these are very straight forward.  In few cases, if you have any confusion, you can refer any basic electronics books. Or you can use K-map to figure out the equations which is mentioned either in block-diagram or circuit diagram.

Circuit
name
Block diagram
Circuit Diagram
Truth table
Half Adder




A
B
S
C
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1

Full Adder


A,B
Cin
S, Cout
0,0
0
0, 0
0,0
1
1, 0
0,1
0
1, 0
0,1
1
0, 1
1,0
0
1, 0
1,0
1
0, 1
1,1
0
0, 1
1,1
1
1, 1

Half Subtractor
A
B
B0
D
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0

Decoder
(Active high)
AB
0D1D2D3
00
1000
01
0100
10
0010
11
0001

Decoder (Active low)
XY
0D1D2D3
00
0111
01
1011
10
1101
11
1110

De-Multiplexer


E
A
B
D0D1D2D3
1
X
X
0000
0
0
0
1000
0
0
1
0100
0
1
0
0010
0
1
1
0001


Multiplexer


S1
S0
Y
0
0
I0
0
1
I1
1
0
I2
1
1
I3



Important points:

  • Half adder can be converted into Half Subtractor with an additional inverter.
  • Full adder can be implemented by using two half adders and an OR gate.
  • Full subtractor can be implemented by using two half- subtractors and an OR gate.
  • Full adder can be converted into full subtractor with an additional inverter.
  • Full adder are of 2 type
    • Ripple carry adder.
    • Carry Look- Ahead adder
  • Four bit binary parallel adder can be constructed by using
    • 3 full adders and 1 half adder or
    • 4 full adders with input carry for least significant bit full adder is zero.


4 Bit FA: Using 4 full Adder (LSB FA's carry bit =0)

4 Bit FA: 3 Full Adder + 1 Half Adder

Important points:

  • Decoder
    • Converts binary information from ‘n’ input lines to a maximum of 2n unique output lines.
    • E.g. 2x4 line Decoder (it is also called one four line decoder)
    • Active high output type of decoders are constructed with AND gates.
    • Active low output type of decoders are constructed with NAND gates.
    • 3 to 8 line decoder is also called Binary-to-Octal decoder or converter. It is also called 1of 8 decoder, because only one of the 8 outputs is active at a time.
    • Decoders are widely used in the memory system of computer, where they respond to the address code input from the CPU to activate the memory storage location specified by the address code.

In the next part of the combinational circuits we will discuss about the MUX with few examples in detail. The reason, I am discussing MUX separately because it has several important things which usually asked in the interview. Also it's very important from VLSI designing point of view.

Must Read Article

Related Posts Plugin for WordPress, Blogger...