Binary Arithmetic and Combinational Logic

Introduction

Combinational Logic is a type of digital logic implemented using Boolean circuits where the output depends only on the present input values.

It does not require memory to store previous data.

In a combinational circuit:

Present Input → Logic Circuit → Present Output

Combinational Logic

Combinational logic circuits produce outputs purely according to the current input combination.

They do not store past input values.

Common combinational circuits include:

• Adders
• Subtractors
• Code Converters
• Decoders
• Encoders
• Multiplexers
• De-multiplexers

Adder

An Adder is a combinational circuit used to perform the addition of binary numbers.

Adders are widely used in:

• Digital circuits
• Arithmetic circuits
• CPUs
• Other digital systems

The notes discuss two types of adders:

1. Half Adder
2. Full Adder

1. Half Adder

A Half Adder is a combinational circuit used to add two binary bits.

It has:

• Two inputs
• Two outputs

The outputs are:

• Sum
• Carry

The Sum is generated using an XOR gate.

The Carry is generated using an AND gate.

Figure: Add Half Adder block diagram here.

Half Adder Truth Table

A	B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

K-Map for Sum of Half Adder

The expression for Sum is:

S = A·B̅ + A̅·B

This is equivalent to the XOR operation.

K-Map for Carry of Half Adder

The expression for Carry is:

C = A·B

2. Full Adder

A Full Adder is a combinational circuit that adds three binary digits.

It takes:

• Two binary input bits
• One carry input

It produces:

• Sum
• Carry

A Full Adder is an important component of binary arithmetic circuits and is commonly used in CPUs and other digital systems.

Full Adder Truth Table

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

Figure: Add Full Adder circuit diagram here.

K-Map for Full Adder Sum

According to the provided notes:

S = AB̅C̅ + A̅B̅C + ABC + A̅B̅C̅

Figure: Add K-Map for Full Adder Sum here.

K-Map for Full Adder Carry

According to the notes:

CA = AC + BC + AB

Figure: Add K-Map for Full Adder Carry here.

Subtractor

A Subtractor is a combinational circuit used to perform subtraction of binary numbers.

The notes discuss:

1. Half Subtractor
2. Full Subtractor

Half Subtractor

A Half Subtractor is a digital circuit used to subtract two binary digits.

It produces:

• Difference
• Borrow

Figure: Add Half Subtractor block diagram here.

Half Subtractor Truth Table

X	Y	Borrow (B)	Difference (D)
0	0	0	0
0	1	1	1
1	0	0	1
1	1	0	0

Figure: Add Half Subtractor circuit diagram here.

Full Subtractor

A Full Subtractor is a digital circuit used to subtract binary numbers while taking into account the borrow from the previous subtraction.

It generally uses:

• Two binary inputs
• One borrow input

It produces:

• Difference
• Borrow output

Figure: Add Full Subtractor block diagram here.

Figure: Add Full Subtractor truth table here.

Figure: Add Full Subtractor circuit diagram here.

K-Map for Difference and Borrow

The source includes K-Map sections for the Difference and Borrow outputs.

Figure: Add Full Subtractor K-Maps here.

Code Converters

Code Converters are digital circuits used to convert one digital code into another.

They are needed because the code generated by one system may not be compatible with another system.

Therefore, code converters can act as a bridge between different digital systems.

The notes discuss:

1. BCD to Excess-3 Code Conversion
2. Binary to Gray Code Conversion

BCD to Excess-3 Code Conversion

Excess-3 Code is an important 4-bit code sometimes used with Binary-Coded Decimal (BCD) numbers.

To convert a decimal digit into Excess-3:

1. Add 3 to the decimal digit.
2. Convert the resulting value into its 4-bit binary form.

BCD to Excess-3 Conversion Table

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 notes provide the following 4-bit Binary-to-Gray conversion table.

Decimal	4-Bit Binary Code (ABCD)	4-Bit Gray Code (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

Figure: Add Binary-to-Gray Code Converter circuit diagram here.

Decoder

A Decoder is a combinational logic circuit that accepts a binary input and activates a particular output line according to the input code.

Working of Decoder

A decoder operates in the following way:

1. Input

The decoder accepts binary inputs.

For example, a 2-to-4 Decoder takes a 2-bit binary input.

Possible input combinations are:

• 00
• 01
• 10
• 11

2. Decoding

Each binary input combination corresponds to a particular output line.

In a 2-to-4 decoder, the four input combinations activate four different output lines.

3. Output

Only one output line is normally active at a time according to the input code.

The active output is generally:

Logic 1

while the remaining outputs stay:

Logic 0

Applications of Decoder

Decoders are commonly used for:

• Address decoding in memory systems
• Selecting devices
• Microcontroller operations
• Display control
• Multiplexer control
• Converting coded information into useful signals

2-to-4 Decoder

A 2-to-4 Decoder uses:

• 2 input lines
• 4 output lines

Figure: Add 2-to-4 Decoder block diagram here.

Figure: Add 2-to-4 Decoder truth table here.

Figure: Add 2-to-4 Decoder logical circuit diagram here.

3-to-8 Decoder

A 3-to-8 Decoder has:

Inputs

• S0
• S1
• S2

Outputs

• D0
• D1
• D2
• D3
• D4
• D5
• D6
• D7

It also includes a single enable line:

E

Figure: Add 3-to-8 Decoder block diagram here.

3-to-8 Decoder Truth Table

According to the provided notes:

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

Figure: Add 3-to-8 Decoder logical circuit diagram here.

Encoder

An Encoder is a digital circuit that converts a set of inputs into a coded representation, usually in binary form.

The inputs may represent:

• Binary digits
• Decimal digits
• Other information

The output is generally a binary code representing the active input.

Types of Encoder

Examples include:

• Binary Encoder
• Gray Code Encoder
• Priority Encoder

Applications of Encoder

Encoders are used for:

• Multiplexing
• Code conversion
• Address encoding
• Computer arithmetic
• Control units
• Instruction encoding

Characteristics of Encoder

According to the notes:

1. Encoder performs the reverse operation of a decoder.
2. It has 2ᵐ input lines and m output lines.
3. The output corresponds to the active input line.
4. It encodes information from multiple input lines into an n-bit code.

4-to-2 Encoder

A 4-to-2 Encoder has:

Inputs

• Y0
• Y1
• Y2
• Y3

Outputs

• A0
• A1

Only one input line is activated at a time to obtain the corresponding binary code at the output.

Figure: Add 4-to-2 Encoder block diagram here.

4-to-2 Encoder Truth Table

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

Logical Expressions of 4-to-2 Encoder

According to the notes:

A1 = Y3 + Y2

A0 = Y3 + Y1

Figure: Add 4-to-2 Encoder logical circuit diagram here.

Limitation of Encoder

According to the notes:

Only one input can be active at a time.

The source states that an advanced encoder can be used as a solution to this limitation.

Priority Encoder

A Priority Encoder assigns priority to input lines so that when multiple inputs are active, the input with the highest priority determines the output.

The source section also contains an explanation of parity encoding, where an additional parity bit is used to detect transmission errors.

Parity Encoder

According to the provided notes, a parity encoder adds an extra bit called a Parity Bit to transmitted data.

The parity bit may be set to 0 or 1 so that the total number of 1s becomes either:

• Even
• Odd

There are two types:

1. Even Parity
2. Odd Parity

Even Parity

The total number of 1s in the data including the parity bit is even.

Odd Parity

The total number of 1s in the data including the parity bit is odd.

Parity encoding is a simple error-detection method.

According to the notes, it cannot:

• Detect every possible error
• Correct errors that have already occurred

More advanced techniques mentioned include:

• CRC – Cyclic Redundancy Check
• ECC – Error Correcting Code

4-to-2 Line Priority Encoder

The notes state:

• X represents a Don’t Care condition.
• Y3 has the highest priority.
• Y0 has the lowest priority.

Logical Expressions

According to the source:

A1 = Y3 + Y2′

A0 = Y3 + Y2′·Y1

The source later also shows:

A0 = Y3 + Y2′·Y1

and:

A1 = Y2 + Y3

4-to-2 Priority Encoder Truth Table

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

Figure: Add 4-to-2 Priority Encoder logical circuit diagram here.

The source also mentions a V signal indicating a valid encoder input.

8-to-3 Line Encoder

An 8-to-3 Encoder encodes eight input lines into three output bits.

Figure: Add 8-to-3 Encoder block diagram here.

Logical Expressions of 8-to-3 Encoder

According to the notes:

A2 = Y4 + Y5 + Y6 + Y7

A1 = Y2 + Y3 + Y6 + Y7

A0 = Y7 + Y5 + Y3 + Y1

Figure: Add 8-to-3 Encoder truth table here.

Figure: Add logical circuit diagram here.

Multiplexer and De-multiplexer

Multiplexers (MUX) and De-multiplexers (DEMUX) are digital circuits used to select and distribute signals in digital systems.

Multiplexer

A Multiplexer (MUX) takes multiple input signals and selects one of them to be sent to a single output.

The selection is controlled by selection lines.

A multiplexer can be considered a digital switch that selects one input line at a time.

De-multiplexer

A De-multiplexer (DEMUX) performs the reverse operation of a multiplexer.

It takes:

• One input

and distributes it to:

• One of several outputs

The required output is selected using selection lines.

MUX and DEMUX are often used together because communication systems can be bidirectional.

Multiplexer or Data Selector

A Multiplexer is a combinational circuit having:

2ⁿ input lines and one output line

It is therefore a:

Multiple-input, Single-output circuit

According to the values of the selection lines, one input is connected to the output.

A multiplexer generally has:

• N selection lines
• 2ⁿ input lines
• One output

A multiplexer is also called a MUX.

An example is a multi-position switch.

According to the notes:

Number of Selection Lines (S) = log₂ M

Where:

M = Number of Inputs

2 × 1 Multiplexer

A 2 × 1 Multiplexer contains:

• Two inputs: A0 and A1
• One selection line: S0
• One output: Y

The selection line determines which input is connected to the output.

2 × 1 Multiplexer Truth Table

S0	Selected Input	Output
0	A0	A0
1	A1	A1

Figure: Add 2 × 1 MUX block diagram here.

Logical Expression of 2 × 1 MUX

Y = S0′·A0 + S0·A1

Figure: Add 2 × 1 MUX logical circuit diagram here.

4 × 1 Multiplexer

A 4 × 1 Multiplexer has:

• Four inputs: A0, A1, A2, A3
• Two selection lines: S0 and S1
• One output: Y

4 × 1 Multiplexer Selection

S1	S0	Selected Input
0	0	A0
0	1	A1
1	0	A2
1	1	A3

Figure: Add 4 × 1 MUX block diagram here.

Logical Expression of 4 × 1 MUX

According to the notes:

Y = S1′S0′A0 + S1′S0A1 + S1S0′A2 + S1S0A3

Figure: Add 4 × 1 MUX logical circuit diagram here.

8 × 1 Multiplexer

An 8 × 1 Multiplexer contains:

Eight Inputs

• A0
• A1
• A2
• A3
• A4
• A5
• A6
• A7

Three Selection Lines

• S0
• S1
• S2

One Output

• Y

Figure: Add 8 × 1 MUX block diagram here.

8 × 1 Multiplexer Truth Table

S2	S1	S0	Output
0	0	0	A0
0	0	1	A1
0	1	0	A2
0	1	1	A3
1	0	0	A4
1	0	1	A5
1	1	0	A6
1	1	1	A7

Figure: Add 8 × 1 MUX logical circuit diagram here.

1 × 2 De-multiplexer

A 1 × 2 De-multiplexer contains:

• One input: A
• One selection line: S0
• Two outputs: Y0 and Y1

Figure: Add 1 × 2 De-MUX block diagram here.

1 × 2 De-MUX Truth Table

S0	Y1	Y0
0	0	A
1	A	0

Logical Expressions

Y0 = S0′·A

Y1 = S0·A

Figure: Add 1 × 2 De-MUX circuit diagram here.

1 × 4 De-multiplexer

A 1 × 4 De-multiplexer contains:

• One input: A
• Four outputs: Y0, Y1, Y2 and Y3
• Two selection lines: S0 and S1

1 × 4 De-MUX Truth Table

The source provides the following rows:

S1	S0	Y3	Y2	Y1	Y0
0	0	0	0	0	A
0	1	0	0	A	0
1	1	A	0	0	0

The uploaded material does not contain the S1 = 1, S0 = 0 row.

Figure: Add 1 × 4 De-MUX block diagram here.

Figure: Add 1 × 4 De-MUX circuit diagram here.

1 × 8 De-multiplexer

A 1 × 8 De-multiplexer distributes one input among eight outputs using three selection lines.

Figure: Add 1 × 8 De-MUX block diagram here.

Logical Expressions of 1 × 8 De-MUX

According to the provided notes:

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

The final expression above is reproduced from the uploaded source.

1 × 8 De-MUX Truth Table

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

Figure: Add 1 × 8 De-MUX circuit diagram here.