Chapter 4
Binary arithmetic and combinational logic
Introduction
Combination logic is a type of digital logic which is implemented by Boolean Circuit where the output is a pure function of the present input only.
Combinational logic
It requires no memory to store data. Combinational logic is a type of digital logic which is implemented by Boolean circuit, where the output is a pure function of the present input only.
Adder:
An adder is a combinational circuit that perform addition of binary numbers. It can be simple half adder and complex full adder. Adder is widely used in digital circuit including arithmetic circuit.
i) Half Adder
It’s an combinational circuit that performs addition of two bits circuit is made to provide two input and take two output. It adds 2 bit number to produces sum and carry. The sum is generated by X-OR gate and carry is generated by AND gate.
Fig: Half Adder
fig: Half Adder Truth Table
- K-MAP for sum of Half Adder
:- S =A.B̅ + A̅.B
- K-MAP for Half Adder Carry
C=A.B
- ii) Full Adder
It is a circuit that adds three binary digits, two from input and one from carry input. It generates sum and carry bit as output. It’s a fundamental component in binary arithmetic circuits, commonly used in CPUs and other digital system.
| Input | Output | |||
| A | B | C | Sum | Carry |
| 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 |
Fig: Full Adder Truth Table
Fig: circuit diagram of Full Adder
K-MAP For Sum
:- S = AB̅C̅ + A̅B̅C + ABC + A̅B̅C̅
K-MAP For Carry
:- CA = AC + BC + AB
Subtractor
Subtractor is a Combinational circuit that Performs Subtraction of binary numbers.
Half Subtractor
A Half Subtractor is a digital circuit that performs Subtraction of two binary digits.
Fig : Block diagram of Half Subtraction
| X | Y | B | D |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
Truth Table: Half Subtractor
Fig: circuit diagram of Half Subtractor
Full Subtractor
AFullSubtractoris a digital circuit that performs the subtraction of two binary numbers, taking in to account the borrow from the previous subtraction.
Fig : Block diagram of Full Subtractor
Truth Table: Full Subtractor
Fig : Circuit Diagram of Full Subtractor
K-MAP For Difference and Borrow
Code Converters
Code converters are digital circuits that are used to convert one code into another code. It is necessary, as the code generated from one system may not be compatible to other. At time code converters are the bridge between the two different system.
BCD to Excess-3 code conversion
The Excess 3 code is an important 4-bit code, sometime used with binary-coded decimal (BCD) number. To convert any decimal number into its excess 3 from add 3 each decimal digit, and then convert the sum to a BCD-number.
| Decimal | BCD
ABCD |
Excess-3
WXYZ |
| 0 | 0000 | 0011 |
| 1 | 0001 | 0100 |
| 2 | 0010 | 0101 |
| 3 | 0011 | 0110 |
| 4 | 0100 | 0111 |
| 5 | 0101 | 1000 |
| 6 | 0110 | 1001 |
| 7 | 0111 | 1010 |
| 8 | 1000 | 1011 |
| 9 | 1001 | 1100 |
Binary to Gray code Conversion
The 4-bit binary to Gray code conversion table is an follows:
| Decimal Number | 4-bit Binary code | 4-bit Gray code |
| ABCD | G3G2G1G0 | |
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
| 8 | 1000 | 1100 |
| 9 | 1001 | 1101 |
| 10 | 1010 | 1111 |
| 11 | 1011 | 1110 |
| 12 | 1100 | 1010 |
| 13 | 1101 | 1011 |
| 14 | 1110 | 1001 |
| 15 | 1111 | 1000 |
Fig: Circuit diagram for binary to Gray code converter
Decoder
In digital electronics, a decoder is a combinational logic circuit that takes binary input and activates one specific output line based on the input code.
Here’s how it works:
1) Input:The decoder takes binary inputs, typically in the form of a binary number. For example, a 2-to-4 line decoder takes a 2-bit binary input, allowing for four possible combinations (00, 01, 10, 11).
2) Decoding:Each combination of inputs corresponds to a specific output line. For instance, in a 2-to-4 line decoder, each of the four possible input combinations (00, 01, 10, 11) will activate a different output line.
3)Output:Only one of the output lines is active at a time, depending on the input code. The active output line is typically set to a high(1) logic , while the other output lines remain at a logic low (0).
Decoders are commonly used in digital systems for various purposes, such as address decoding in memory systems, selecting specific devices or functions in a microcontroller, and controlling displays or multiplexers. They play a crucial role in converting coded information into actionable signals or commands within digital circuits.
2-4 Decoder
Fig : Block Diagram of 2 to 4 Decoder
Truth Tableof 2 to 4 Decoder
Fig : Logical circuit diagram of 2 to 4 decoder
3 to 8 Decoder
Three inputs- S0, S1 and S2
Eight Outputs- D0, D1, D2, D3, D4, D5, D6, D7
Single enable line-E
The logical expression of the term D0, D1, D 2, D 3, D 4, D 5,D 6, and D 7
Fig : Block Diagram of 3 to 8 Decoder
Truth table
| Inputs | Outputs | ||||||||||
| S0 | S1 | S2 | E | D0 | D1 | D2 | D3 | D4 | D5 | D6 | D7 |
| x | x | x | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Fig : Logical circuit diagram of 3 to 8 decoder
Encoder
An encoder is a digital circuit that converts a set of inputs into a coded representation, usually in binary from. The inputs can be binary digitals or decimal digits, and the output is a binary code that represents the input pattern.
There are different types of encoders, including binary encoders, gray code encoders, and priority encoders. Encoders are used in digital systems for multiplexing, code conversion, and address encoding. They are also used in computer arithmetic and control units for instruction encoder.
Characteristics of Encoder:
- Reverse operation of decoder.
- Has 2^m input lines and m output lines.
- The output is correspondence to the input line.
- Encoder the information from 2^n input into an n-bit code.
4 to 2 Encoder
- Four inputs, i.e., Y0, Y1, Y2, and Y3, and two output, i.e., A0 and A1 .
- One input-line is set to true at a time to get the respective binary code in the output side.
Fig : Block diagram of 4 to 2Encoder
Truth Table for 4 to 2 Encoder
| Inputs | Outputs | ||||
| Y3 | Y2 | Y1 | Y0 | A1 | A0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
The logical expression of term A0 and A1 is follows:
A1=Y3 + Y2
A0=Y3 + Y1
Fig : Logical circuit diagram of 4 to 2Encoder
Limitation :only one input can be active at a time.
Solution :use parity encoder.
Priority Encoder
A parity Encoder is a type of encoder that add on extra bit, called the parity bit, to the data being transmitted to ensure the accuracy of the data. The parity bit is set to either 0 or 1, such that the total number of 1s in the data plus the parity bit is either even or odd.
There are two type of parity encoder: even parity and odd parity. In event parity, the number of 1s in the data plus the parity bit is always even, while in odd parity, the number of 1s in the data plus the parity bit is always odd.
Parity encoding is a simple method for detecting error in data transmission, but it cannot detect all errors or correct errors that have occurred. More advanced error detection and correction techniques, such as cyclic redundancy check (CRC) and error correcting code(ECC), are used in applications that require higher levels of accuracy.
4 to 2 line priority Encoder
- The X’s designations don’t care condition.
- The Y3 has high and Y0 has low priority.
- The logical expression of the term A0 and A1 can be found using K map as:
A1= Y3 + Y 2’ A0= Y3 + Y2’.Y1
Truth Table for 4 to 2 priority Encoder
| Inputs | Outputs | ||||
| Y3 | Y2 | Y1 | Y0 | A1 | A0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | X | 0 | 1 |
| 0 | 1 | X | X | 1 | 0 |
| 1 | X | X | X | 1 | 1 |
A0=Y3 + Y2’.Y1
A1=Y2 + Y3
Fig : Logical Circuit diagram of 4 to 2 priority Encoder
Here, v indicates the valid input to encoder
8 to 3 line Encoder
Fig : Block diagram of 8 to 3 Encoder
The logical expression of the term A0, A1, and A2 are as follows:
A2 = Y4 + Y5 + Y6 + Y7
A1 =Y2 + Y3 + Y6 + Y7
A0 = Y7 + Y5 + Y3 + Y1
Truth table for 8 to 3 Encoder
Fig : Logical circuit diagram of 3 to 8 Encoder
Multiplexer and De-multiplexers
Multiplexers (MUX) and De-multiplexers (DEMUX) are digital circuits that are used to select and distribute signals in digital system.
A MUX is a device take in multiple inputand selects one of them to be transmitted as the output, based on a selection line. It can be thought of as a switch that selects one input line to be connected to the output.
A DEMUX, on the other hand, take a single input and routes it to one of several outputs, based on the value of the selection lines. It can be thought of as the reverse operation of a MUX, distributing the input single to multiple output line.
Multiplexer/Data selector
- A combinational circuit that has 2n input lines and a single output line.
- Simply, multi-input and single-output combinational circuit.
- on the basic of the value of the selection lines, one of these data inputs will be connected to the output.
- N selection lines and 2n input lines.
- A multiplexer is also treated as mux.
- De-multiplexer is a circuit that performs function exactly reverse of multiplexer.
- Generally, both used together, because communication systems are bi-derectional.
- Example: multi-position switch
- In Digital application it is called digital multiplexer.
- Number of selection line(S) =lig2M, where M= no of inputs.
N selection/control input
2 X 1 Multiplexer
- Only two inputs, i.e., A0 and A1, 1 selection line, i.e., S0 and single outputs, I.e., Y.
- On the basis of selection S0 the input is selected one at a time.
Truth Table
| Input | Selection | Output | |
| A1 | A0 | S0 | Y |
| – | A0 | 0 | A0 |
| A1 | – | 1 | A1 |
Fig: Block diagram of 2 x 1 MUX
The logical expression of the term Y is as follows:
Y=S0’.A0 + S0. A1
Fig: Local circuit diagram of 2 x 1 MUX
4 x 1 multiplexer
- Four inputs, i.E. A0, A1, A2, and A3.
- Selection lines, i.E.,S0 and S1.
- Single output i.E., Y.
Truth Table
| Inputs | Selection | Output | ||||
| A3 | A2 | A1 | A0 | S1 | S0 | A0 |
| – | – | – | A0 | 0 | 0 | A1 |
| – | – | A1 | – | 0 | 1 | A2 |
| – | A2 | – | – | 1 | 0 | A3 |
| A3 | – | – | – | 1 | 1 | A4 |
Fig: Block diagram of 4 x 1 MUX
The logical expression of them Y is as follows:
Y=S1’ S0’ A0 + S1’S0A1+ S1S0’A2 + S1 S0 A3
Fig: Logical circuit diagram of 4 x 1 MUX
8 to 1 Multiplexer
- Eight inputs, i.e., A0, A1, A2, A3, A4, A5, A6, and A7
- 3 selection lines, i.e., S0, S1 and S2
- Single output, i.e., Y.
Fig: Block diagram of 8 x 1 MUX
Truth Table for 8 x 1
| INPUTS | Selector | Output | |||||||||
| A7 | A6 | A5 | A4 | A3 | A2 | A1 | A0 | S2 | S1 | S0 | Y |
| – | – | – | – | – | – | – | A0 | 0 | 0 | 0 | A0 |
| – | – | – | – | – | – | A1 | – | 0 | 0 | 1 | A1 |
| – | – | – | – | – | A2 | – | – | 0 | 1 | 0 | A2 |
| – | – | – | – | A3 | – | – | – | 0 | 1 | 1 | A3 |
| – | – | – | A4 | – | – | – | – | 1 | 0 | 0 | A4 |
| – | – | A5 | – | – | – | – | – | 1 | 0 | 1 | A5 |
| – | A6 | – | – | – | – | – | – | 1 | 1 | 0 | A6 |
| A7 | – | – | – | – | – | – | – | 1 | 1 | 1 | A7 |
Fig: Logical circuit diagram of 8 x 1 MUX
1 x 2 De-multiplexer
- Only two outputs, i.e., Y0, and Y1 1 selection lies, i.e.,S0 and
- Single input, i.e., A.
Fig: Block diagram of 1 x 2 De- MUX
Truth Table for 1 x 2 De-MUX
| INPUTS | OUTPUT | |
| S0 | Y1 | Y0 |
| 0 | 0 | A |
| 1 | A | 0 |
The logical expression of the term Y is as follows:
Y0=S0’. A
Y1=S0. A
Fig: Circuit diagram of 1 x 2 De-MUX
1 x 4 De-Multipexer
- Single input, i.e., A
- Four outputs, i.e., Y0, Y1, Y2, and Y3
- 2 selection lines, i.e., S0 and S1
Truth Table for 1 x 4 De-MUX
| INPUTS | OUTPUT | ||||
| S1 | S0 | Y3 | Y2 | Y1 | Y0 |
| 0 | 0 | 0 | 0 | 0 | A |
| 0 | 1 | 0 | 0 | A | 0 |
| 1 | 1 | A | 0 | 0 | 0 |
Fig: Block diagram of 1 x 4 De-MUX
Fig: Circuit diagram of 1 x 4 De-MUX
1 x 8 De-multiplexer
Fig: Block diagram of 1 x 8 De-MUX
The logical expression of the term Y is as follows:
Y0= S0’.S1’.S2’.A
Y1=S0.S1’.S2’.A
Y2= S0’.S1.S2’.A
Y3= S0.S1.S2’.A
Y4= S0’.S1’.S2.A
Y5= S0.S1’.S2.A
Y6= S0’.S1.S2.A
Y7= S0.S1.S3.A
Truth Table for 1 x 8 De-MUX
| INPUTS | OUTPUT | |||||||||
| S2 | S1 | S0 | Y7 | Y6 | Y5 | Y4 | Y3 | Y2 | Y1 | Y0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | A |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | A | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | A | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | A | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | A | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | A | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | A | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Fig: Circuit diagram if 1 x 8 De-MUX