Combinational Logic Design: Binary Codes

• Foundations of Computer Architecture and System Design is the name of this school of Computer Engineering and Technology course.
• Unit IV focuses on Combinational Logic Design.

Combinational Logic Design: Syllabus

• Covers weighted and non-weighted codes, code conversion and arithmetic circuits.
• Arithmetic circuits include half adders, full adders, half subtractors, full subtractors, parallel adders, and look-ahead carry generators.
• The topic also explores multiplexers, de-multiplexers, and decoders, along with implementing Boolean Functions using multiplexers and decoders.

Classification of Binary Codes

• Broadly categorized into weighted and non-weighted codes.

Weighted Codes

• Binary, BCD code examples.
• Obey the position weighting principle.
• States that a number's position signifies a typical weight.
• Each digit or symbol position has a specific weight.
• In weighted code, each decimal digit is expressed by 4 bits, each with a weight of 8, 4, 2, 1.

Binary Code

• Binary code uses only two bits: '0' and '1'.
• Has weights of 8-4-2-1 for every number.

BCD Code

• BCD Code is a form of binary encoding.
• Each digit in a decimal number is represented in the form of bits.
• Preferred encoding is usually 4-bit, but can be done in 8-bit
• The code converts decimal numbers into binary numbers efficiently.

Non-Weighted Codes

• Gray code, Excess-3 Code examples.
• Does not assign a weight to each digit position.

Excess-3 Code

• Also referred to as XS-3 code.
• Used to represent decimal numbers.
• Involves adding 3 to each decimal digit, with each digit of the decimal number as four-bit binary.

Gray Code

• Does not have specific weights allocated to bit positions.
• Only one bit alters each time the decimal number increments.
• Also referred to as a unit distance code.

Gray Code-Reflection Method

• Method for encoding numbers in a way that only one bit changes between successive numbers.

Binary to Gray code conversion

• A method of converting a binary number into its equivalent Gray code representation.

Gray to Binary code conversion

• Opposite to Binary to Gray code, this converts a Gray code number into Binary.

Applications of Gray Code

• Used in Kmaps
• Used in shaft encoders.

Various Binary Codes

• Table displaying Decimal Number equivalents for Binary, BCD, Excess-3, and Gray codes.

Half Adder

• Used to add single bits.
• Logic circuit used for the addition of two 1-bit numbers,
• Similar to binary addition.

Half Adder: Truth Table

• Inputs A and B produce Sum (S) and Carry (C) outputs.
• S = ĀB + A
• B = A⊕B
• C = AB

Half Subtractor

• Produces a difference bit, and a borrow-out bit when subtracting single-bit binary B from A.
• Operation is called half subtraction.

Half Subtractor: Truth Table

• Inputs:A, B ; Outputs: Diff, Borrow
• D(A,B) = Σ (1,2)
• D = A'B + AB'
• D = A⊕B
• Borrow(A,B) = Σ (1)
• Borrow = A'B

Half Adder USING 4:1 MUX

• Multiplexer equation Y = SoS1A + SoS1B + SoS1C + SoS1D

Full Adder

• Designed since a half adder has only 2 inputs and cannot add carry from lower order bits.
• Has a third input terminal for adding bits in the An, Bn, and Cn-1 places.
• The circuit is used to perform multi-bit addition.

Full Adder Truth Table

• Inputs are An, Bn, and Cn-1, respectively.
• Outputs are sum Sn, and carry Cn.
• S = ∑m(1,2,4,7)
• C = ∑m(3,5,6,7)
• S = A'B'C + A'BC' + AB'C' + ABC
• S = A ⊕ B ⊕ C
• C = AC + BC + AB
• C = C(A+B) + AB

Full Adder Circuit (Sum & Carry) using Gates

• Sum: S = A'B'Cin + A'BCin' + AB'Cin' + ABCin
• S = A ⊕ B ⊕ Cin
• Carry: Cout = B.Cin + A.B + A.Cin

Full Subtractor

• Subtracts two single-bit binary values, Y, B-in, from X, producing a difference D and borrow out B-out.

Full Subtractor Truth Table

• Inputs: X, Y, B-in
  • D = X'Y'(B-in) + XY'(B-in)' + XY'(B-in)' + XY(B-in)
  • D = X ⊕Y (B-in)
• Borrow out: B-out = X'Y + X'(B-in) + Y(B-in)

Full Subtractor Circuit Using AND-OR

• Logic gate diagram for a full subtractor circuit

Full Adder using two Half adders

• An alternate method of creating a full adder.

Parallel Adder

• Consisting of n full adders.
• Used to add n-bit binary numbers.
• Output: n sum bits and one carry bit.
• The CO of one full adder connects to the CI of the next full adder.

Serial Adder

• Adds binary numbers.
• Capable of forming sum and carry outputs for addend and augend words of greater than one bit in length.

Comparison of Parallel and Serial Adder

• Parallel Adders are faster, uses registers with parallel load capacity, and # of full adder circuits is equal to the number of bits in the adder.
• Serial Adders are slower, uses shift registers, and require 1 full adder circuit.

Structure of Parallel Adder

• A cascade of full adders.
• The number of full adders depends on the number of bits in the binary digits to be added.
• Types include one-bit, two-bit, and four-bit parallel adders.

Types of Parallel Adders

• Demonstrating component layout and circuitry diagram for One, Two, and Four Bit Parallel Adders.

Working of Parallel Adder

• The full adder FA1 adds A1 and B1 with the carry C1, generating sum S1, and carry C2 connected to the next adder.
• FA2 uses carry bit C2 to add input bits A2 and B2, generates the sum S2.
• Process continues until the last full adder, which uses the carry bit Cn to add input and generate the output’s last bit, along with the last carry bit Cout.

Advantages & Disadvantages of Parallel Adder

• Advantage: Faster addition and output is in parallel form.
• Disadvantage: Each adder has to wait for generated carry from the previous adder in chain, propagation delay.

Carry Look-ahead Adder

• Full adder circuit uses two half adder circuits.
• Reduces the dependency of the next stage carry on the previous stage carry.
• G₁ = A
• B₁
• where G is called carry generator
• P₁ = A; ⊕ B;
• where P is called carry propagator

More on Carry Look-ahead Adder

• Reduces propagation delays.
• Requires more complex hardware.

Carry Look-ahead Adder, advanced

• Eliminates dependency on previous carries by only being dependent on the A and B inputs.

Multiplexer and Demultiplexer

Communication System

• Block diagram showing Multiplexer(Data Selector) at the Transmitting end and Demultiplexer(Data Distributor) at Receiving end through a Channel.

Multiplexer

• Data selector, many to one circuit.

Multiplexer: Advantages

• Reduces the number of wires, reduces circuit complexity & cost, and minimizes the IC package count.
• Types: 2:1 MUX, 4:1 MUX, 8:1 MUX, 16:1 MUX

2:1 Multiplexer

• Relation between selector and Inputs n=2^m
  • Where, n = no. of inputs
  • m = no. of select lines
  • Y = E.S'.IO + E.S.I1 or Y = E (S'.IO + S.I1)
  • m=log2n

2:1 Multiplexer Circuit

• Gate level circuit diagram of 2:1 Multiplexer
• Y = E.S'.IO + E.S.I1
• Y = E (S'.IO + S.I1)

4:1 Multiplexer

• Y = S1'.S0'.I0 + S1'.S0.I1 + S1.S0'.I2 + S1.S0.I3

4:1 Multiplexer

• Gate level circuit diagram of 4:1 Multiplexer

IC 74153 Dual 4:1 Multiplexer

• A dual 4-to-1 multiplexer integrated circuit (IC)
• Contains two independent 4-to-1 multiplexers within a single package.

Implementing Logic expressions using Multiplexers

• Multiplexers can implement Boolean expressions
• Decide the mux type by the number of variables
• Connect the inputs corresponding to given minterms to logic 1
• Connect remaining inputs to ground (logic 0)
• Connect input variables (A, B, C....) as selection lines

Implementation of Logic Expressions using Multiplexers

• The boolean expression F(A, B, C) = ∑ m(2, 3, 6, 7) using a multiplexer will require 3 selection lines since it has 3 variables.

Multiplexer Tree

• Achieved through stacking multiplexers, or trees.
• Allows larger input needs with the help of enable/strobe inputs

MUX Tree

• Implement 4:1 Using 2:1

Active low and Active high enable for MUX Tree

• Circuit diagram

Implementation of 3 variable SOP expression using 4x1 MUX (Reduction Method)

• The B and C variables can be connected with the S1 and S0 select lines, but a reduction method is needed to connect the third variable A.

Applications of Multiplexers

• Data Routing: Route data to a particular destination from one of several sources.
• Logic Function Generator: Generate a logical expression with a multiplexer, reducing required logic gates or integrated circuits.
• Parallel to Serial Conversion: Convert parallel data to serial data, to reduce number of parallel buses.

De-multiplexer

• The process of obtaining information from one input, and transmitting the same to one of many outputs.
• Works opposite to multiplexing.
• Combinational logic circuit that receives information on a single input line.
• Transmits the same information over one of 'n' possible output lines.

More on De-multiplexer

• Computer system data output, printer.

1:2 Demultiplexer

• Yo=So'.A and Y₁=So. A

1:4 Demultiplexer

• Y0=E.S1'.S0'.Din ,Y1=E.S1'.S0.Din, Y2 = E.S1.S0'.Din, and Y3 = E.S1.S0.Din

Implement the 1:4 Demultiplexer Circuit

• Logic gate diagram for a 1:4 Demultiplexer

Implement the function using 1:8 Demultiplexer

• Logic gate diagram for a 1:8 Demultiplexer

Applications of DEMUX (De-Multiplexers)

• Selecting different IO devices, or banks of memory
• Synchronous data transmission, implementation of boolean functions, data aquisition, and circuit design.
• Security monitoring systems that select a particular surveillance camera at a time

Encoders and Decoders

• Encoders change binary information into output lines
• Encoders accept alphabetic characters and decimal numbers for input, and produces coded output representation
• Binary information is passed in the form of input lines, where output defines the N-bit code for the information

Applications of Encoders

• Translate from numbers or characters to coded format, or from decimal to binary

Decoder

• The reverse operation to an Encoder
• Special case of a demultiplexer without the input line
• Looks at inputs to determine output, which then corresponds to the activated number.

General Decoder Diagram

• Consisting of input N and output M lines.
• There are 2*N possible input combinations from A0 to (A sub N-1)
• For each combination of inputs, there is one output high (1), and the rest are low (0)
• Available as dual N-to-M decoders or single N-to-M decoder ICs

Full Adder Implementation using Decoder

• A, B, and C for the inputs and carry respectively, where the Sum, and Carry outputs follow truth tables
• S output =∑ 1, 2, 4, 7
• Cin output =∑ 3, 5, 6, 7

More On Full Adder using Decoder

• With active high output decoder -Logic gate components