Subject: COA

Subject code: 205

1. Basic Laws of Boolean Algebra
Boolean Algebra, introduced by George Boole, is a mathematical system used to analyze and
simplify digital circuits. It deals with binary variables and logical operations. In Boolean algebra,
variables have only two possible values — 0 (false) and 1 (true). The operations are similar to
arithmetic operations but are defined differently for logical reasoning.

Basic Laws:

1. Commutative Law:
o A+B=B+A
o A·B=B·A
These laws state that the order of variables does not affect the result in OR or
AND operations.
2. Associative Law:
o (A + B) + C = A + (B + C)
o (A · B) · C = A · (B · C)
The grouping of variables does not affect the output.
3. Distributive Law:
o A · (B + C) = A·B + A·C
o A + (B · C) = (A + B) · (A + C)
These allow expansion and factoring in Boolean expressions.
4. Identity Law:
o A+0=A
o A·1=A
Combining with neutral elements does not change the value.
5. Null Law:
o A+1=1
o A·0=0
Defines interaction with dominant elements.
6. Idempotent Law:
o A+A=A
o A·A=A
7. Complement Law:
o A + A’ = 1
o A · A’ = 0
8. Double Negation Law:
o (A’)’ = A
Importance:

These laws simplify complex Boolean expressions, which reduces the number of logic gates
required in circuit design. Simplification helps optimize power usage, speed, and cost in digital
systems like computers, processors, and control systems.

2. Logic Gates
Logic gates are electronic circuits that perform Boolean operations on one or more input signals
to produce an output. They are the fundamental building blocks of digital electronics.

Types of Logic Gates:

1. AND Gate:
Output is 1 only when all inputs are 1.
Boolean Expression: Y = A·B
2. OR Gate:
Output is 1 if any input is 1.
Expression: Y = A + B
3. NOT Gate (Inverter):
It inverts the input; if input = 1, output = 0.
Expression: Y = A’
4. NAND Gate:
It’s the negation of AND.
Expression: Y = (A·B)’
5. NOR Gate:
It’s the negation of OR.
Expression: Y = (A + B)’
6. XOR Gate (Exclusive OR):

Expression: Y = A ⊕ B
Output is 1 when inputs differ.

7. XNOR Gate (Exclusive NOR):

Expression: Y = (A ⊕ B)’
Output is 1 when inputs are the same.

Application:

Logic gates are used in arithmetic circuits, data processing, and decision-making logic within
microprocessors, memory devices, and control systems. Modern computers use millions of gates
in integrated circuits (ICs).
3. Simplification of Boolean Equations using K-Maps (SOP
& POS) and Don’t Care Conditions
Karnaugh Map (K-Map):

A K-map is a graphical method used to simplify Boolean expressions. It minimizes the number
of logic gates required by grouping adjacent 1’s (for SOP) or 0’s (for POS).

● SOP (Sum of Products): Combine adjacent 1s in K-map.

● POS (Product of Sums): Combine adjacent 0s in K-map.

Steps for SOP Simplification:

1. Plot 1s in K-map for each minterm.

2. Group adjacent 1s in powers of 2 (1, 2, 4, 8, etc.).
3. Write the simplified product terms.
4. Add all terms using OR (+) operation.

Steps for POS Simplification:

1. Plot 0s in K-map for each maxterm.

2. Group adjacent 0s in powers of 2.
3. Write the simplified sum terms.
4. Multiply all terms using AND (·) operation.

Don’t Care Conditions:

These represent input combinations that never occur or whose output doesn’t matter. They are
marked as “X” in K-map and can be used to form larger groups for further simplification.

Advantages:

● Reduces circuit complexity.

● Improves performance.
● Simplifies manual simplification without algebraic manipulation.
4. Arithmetic Circuits: Adder, Subtractor, Parallel Binary
Adder/Subtractor
Arithmetic circuits perform binary addition and subtraction using logic gates.

Half Adder:

Performs addition of two single-bit binary numbers.

Sum = A ⊕ B
● Inputs: A, B
●
● Carry = A · B

Full Adder:

Adds three inputs (A, B, Carry-in).

● Sum = A ⊕ B ⊕ Cin
● Carry = AB + BCin + ACin

Half Subtractor:

Performs subtraction of two bits (A − B).

● Difference = A ⊕ B
● Borrow = A’ · B

Full Subtractor:

Handles three inputs (A, B, Borrow-in).

Difference = A ⊕ B ⊕ Bin
Borrow = A’B + Bin(A’ ⊕ B)
●
●

Parallel Binary Adder/Subtractor:

● Adds or subtracts multi-bit numbers using cascaded full adders.

● A control signal determines operation:
o When control = 0 → addition
o When control = 1 → subtraction (by taking 2’s complement of the subtrahend)

This is the basis for Arithmetic Logic Units (ALUs) in CPUs, capable of performing multiple
arithmetic operations efficiently.
1. Multiplexers, De-Multiplexers, Decoders, and Encoders
Multiplexer (MUX):

A Multiplexer (MUX) is a digital device that selects one input from multiple data inputs and
forwards it to a single output line based on the values of selection lines. It acts as a data selector.

● Example: A 4-to-1 MUX has 4 input lines (I₀–I₃), 2 selection lines (S₀, S₁), and 1
output (Y).
● Working Principle: The output corresponds to the selected input based on the binary
value of the selection lines.
o Y = S₁'S₀'I₀ + S₁'S₀I₁ + S₁S₀'I₂ + S₁S₀I₃
● Applications: Data routing, communication systems, control unit design, and ALUs.

De-Multiplexer (DEMUX):

A De-Multiplexer performs the reverse function of a multiplexer. It takes a single input and
routes it to one of many output lines based on the selection inputs.

● Example: A 1-to-4 DEMUX has 1 input (D), 2 selection lines (S₀, S₁), and 4 outputs
(Y₀–Y₃).
o Y₀ = D·S₁'·S₀'
o Y₁ = D·S₁'·S₀
o Y₂ = D·S₁·S₀'
o Y₃ = D·S₁·S₀
● Applications: Serial-to-parallel data conversion, signal distribution, and digital
communication.

Decoder:

A Decoder converts binary information from n input lines to a maximum of 2ⁿ unique

output lines. Each output line represents a unique combination of the inputs.

● Example: A 3-to-8 decoder has 3 inputs and 8 outputs.

● Working: Each output is activated for one input combination.
o Y₀ = A'B'C', Y₁ = A'B'C, … Y₇ = ABC
● Applications: Address decoding in memory units, seven-segment displays, and
microprocessors.

Encoder:

An Encoder is the reverse of a decoder — it converts 2ⁿ input lines into n output lines by
encoding the active input.

● Example: An 8-to-3 encoder converts 8 inputs into 3-bit binary code.

 ● Working: If input D₅ is active, output = 101.
● Applications: Priority encoders in interrupt handling, data compression, and keyboard
circuits.

2. Flip-Flops: S-R, D, J-K, T, Clocked, Race Around,

Master-Slave, and Applications
Flip-flops are bistable memory elements that store one bit of data. They change state based on
input signals and a clock pulse. They are the fundamental building blocks of sequential logic
circuits.

1. S-R Flip-Flop (Set-Reset):

● Inputs: S (Set), R (Reset)

● Output: Q, Q'
● Function:
o S = 1, R = 0 → Q = 1 (Set)
o S = 0, R = 1 → Q = 0 (Reset)
o S = 0, R = 0 → No change
o S = 1, R = 1 → Invalid (both high)

2. D Flip-Flop (Data or Delay):

● Single Input: D
● Function: Transfers input D to output Q on clock edge.
o Q(next) = D
● Use: Data storage and synchronization.

3. J-K Flip-Flop:

● Improvement over S-R (avoids invalid state).

● Function Table:
o J=0, K=0 → No change
o J=0, K=1 → Reset
o J=1, K=0 → Set
o J=1, K=1 → Toggle

4. T Flip-Flop (Toggle):

● Derived from J-K by connecting J and K together.

o T=0 → No change
o T=1 → Toggle (complement Q)
 ● Used in: Counters and control circuits.

5. Clocked Flip-Flop:

● Operates only on clock edges (rising or falling).

● The clock synchronizes all flip-flops in a system, ensuring predictable operation.

6. Race Around Condition:

● Occurs in J-K Flip-Flop when J=K=1 and the clock pulse is long.
● Output toggles rapidly within one clock pulse, leading to unpredictable results.
● Solution: Use edge-triggered or master-slave flip-flops.

7. Master-Slave Flip-Flop:

● Consists of two J-K flip-flops connected in series.

o Master is triggered by the clock’s positive edge.
o Slave is triggered by the negative edge.
● Eliminates race around condition.

8. Realisation of One Flip-Flop Using Another:

● T Flip-Flop from J-K: Connect J = K = T.

T Flip-Flop from D: D = T ⊕ Q.
● D Flip-Flop from J-K: J = D, K = D'.
●
This allows circuit designers to use available components efficiently.

9. Applications of Flip-Flops:

1. Latch:
o Simple storage element (unclocked).
o Holds data as long as enable signal is active.
2. Registers:
o A collection of flip-flops used to store multiple bits.
o Types: Shift Registers (serial-to-parallel, parallel-to-serial).
3. Counters:
o Sequence of flip-flops connected to count clock pulses.
o Types: Ripple Counter, Synchronous Counter, Up/Down Counter.

Flip-flops form the core of memory elements, control systems, digital clocks, and CPUs —
making them essential for all digital design architectures.
1. Register Transfer
A register transfer refers to the movement of binary data from one register to another within a
computer system. Registers are small, high-speed storage elements located inside the CPU used
to hold temporary data and instructions during processing. A register transfer operation is
typically represented in symbolic form as:
R₂ ← R₁
This means that the contents of register R₁ are transferred into R₂.

Control Function:
Transfers occur only when a specific control signal is activated, represented as:
P: R₂ ← R₁,
which means the transfer takes place only when the control variable P = 1.

Parallel Transfer:
In most systems, all bits are transferred simultaneously via parallel connections, which allows for
faster operation.

Hardware Implementation:
Register transfers are carried out through digital circuits that include multiplexers, control logic,
and bus systems. Control signals are generated by the control unit, ensuring proper sequencing
of data movements between registers.

Applications:
Register transfers are fundamental to CPU operations such as fetching instructions, performing
arithmetic operations, and transferring intermediate results.

2. Bus and Memory Transfer

A bus is a communication pathway through which data, addresses, and control signals are
transmitted between components such as the CPU, memory, and I/O devices.

Bus Structure:
● Data Bus: Carries data between processor, memory, and peripherals.
● Address Bus: Carries memory addresses from the CPU to memory or I/O devices.
● Control Bus: Carries control signals (read/write, interrupt, clock).

Bus Transfer:
When multiple registers are interconnected via a common bus, any register can place its data
onto the bus using a multiplexer or tri-state buffers, while other registers can read data from the
bus.

Memory Transfer:
● Read Operation: Data is transferred from memory to CPU.
o Performed when Read Control = 1.

● Write Operation: Data is transferred from CPU to memory.

o Performed when Write Control = 1.

The address of the memory location is placed on the address bus, and the control bus signals
specify whether the operation is read or write.

Advantages of Bus System:

● Reduces circuit complexity
● Increases flexibility for communication among components
● Efficient utilization of data pathways

3. Registers and Micro-operations

Registers:
A register is a high-speed storage unit capable of holding binary data. Each register is composed
of flip-flops (each flip-flop stores one bit).
Registers are used for data storage, address storage, instruction storage, and intermediate
computation.

Types of Registers:
1. Data Register (DR): Holds data fetched from memory.

2. Address Register (AR): Holds memory address for data access.

3. Program Counter (PC): Points to the next instruction to be executed.

4. Instruction Register (IR): Holds the current instruction.

5. Accumulator (AC): Holds intermediate arithmetic results.

Micro-operations:
Micro-operations are elementary operations performed on data stored in registers. They represent
the smallest operations within a CPU’s instruction execution.
Types of Micro-operations:
1. Register Transfer Micro-operation: Moving data between registers.
Example: R₂ ← R₁
2. Arithmetic Micro-operation: Performing arithmetic operations.
Example: R₃ ← R₁ + R₂
3. Logic Micro-operation: Performing logical operations like AND, OR, XOR.
Example: R₁ ← R₁ AND R₂
4. Shift Micro-operation: Shifting bits left or right.
Example: R₁ ← shl(R₁)
Micro-operations are triggered by clock pulses and controlled by the control unit, forming the
foundation for instruction execution.
4. Basic Computer Organization and Design
Computer organization describes the operational structure of a digital computer and how its
components work together to execute instructions.

Instruction Codes:
An instruction code is a binary pattern that specifies an operation to be performed by the
computer.
Each instruction consists of:
● Opcode (Operation Code): Specifies the operation (e.g., ADD, SUB).
● Operand: Specifies the data or the memory address.
Example:
Instruction = [Opcode | Operand]

Computer Registers:
Essential registers in a basic computer include:
● Program Counter (PC): Holds address of next instruction.
● Instruction Register (IR): Holds the current instruction.
● Accumulator (AC): Temporarily stores results.
● Memory Address Register (MAR): Holds address of data to be accessed.
● Memory Data Register (MDR): Holds data fetched or to be written.

Instruction Cycle:
The instruction cycle is the sequence of operations performed to execute an instruction:
1. Fetch: Get the instruction from memory.

2. Decode: Interpret the instruction.

3. Execute: Perform the specified operation.

4. Store (if required): Save the result back to memory.

General Register Organization:
Multiple general-purpose registers are used to increase processing efficiency. A control word
defines which registers participate in a given operation. The ALU performs arithmetic and
logical operations under control unit supervision.

Stack Organization:
A stack is a storage structure organized in LIFO (Last-In, First-Out) manner.
● Push: Insert an element.
● Pop: Remove the top element.
Used in subroutine calls, interrupt handling, and expression evaluation.

Instruction Formats:
Instruction format defines how the bits of an instruction are divided into opcode and operand
fields.
● Zero Address: Implied addressing (e.g., stack-based).
● One Address: Uses accumulator.
● Two Address: Uses two operands.
● Three Address: Uses three registers or memory references.

Addressing Modes:
Addressing mode specifies how to interpret the operand part of an instruction.
Common modes:
1. Immediate: Operand is directly in the instruction.

2. Direct: Address field gives memory location.

3. Indirect: Address field points to another address.

4. Register: Operand is in a register.

5. Register Indirect: Register contains the address of operand.

6. Relative: Effective address = PC + offset.

Addressing modes increase the flexibility and efficiency of instruction execution.

1. Peripheral Devices, Input-Output Interfaces,

Asynchronous Data Transfer, Modes of Transfer, Priority
Interrupt, and DMA
Peripheral Devices:
Peripheral devices are external hardware components connected to a computer to perform input,
output, and storage functions. They are not part of the CPU or main memory but communicate
with them through input-output interfaces.
Types of Peripheral Devices:
1. Input Devices: Used to enter data into the system.
Examples: Keyboard, Mouse, Scanner, Microphone.
2. Output Devices: Display or produce the result of computation.
Examples: Monitor, Printer, Speakers.
3. Storage Devices: Used for long-term data storage.
Examples: Hard Drive, Pen Drive, Optical Disk.
Peripheral devices interact with the CPU through control signals, data lines, and I/O ports.

Input-Output Interfaces:
An I/O Interface acts as a bridge between the CPU and peripheral devices, ensuring proper
communication. Since peripherals operate at different speeds and formats compared to the CPU,
an interface manages synchronization, control, and data conversion.
Functions:
● Data buffering between CPU and peripherals
● Control signal generation
● Address decoding and device selection
● Data format conversion (serial ↔ parallel)
I/O interfaces can be:
● Programmed I/O (CPU-controlled)
● Interrupt-driven I/O (CPU interrupted by device)
● DMA (Direct Memory Access) (device transfers data directly to memory)
Asynchronous Data Transfer:
In asynchronous data transfer, there is no common clock signal between sender and receiver.
Data is transmitted using control signals like “Ready” and “Acknowledge” to ensure
synchronization.
Types:
1. Strobe Control: A strobe signal indicates when data is valid.

2. Handshake Control: Both sender and receiver exchange readiness signals, ensuring safe
data transfer.
Used in communication systems where devices operate at different speeds.

Modes of Transfer:
1. Programmed I/O:
CPU manually checks device status and transfers data. Simple but inefficient since CPU
remains busy.
2. Interrupt-Driven I/O:
Device sends an interrupt signal to CPU when ready. CPU can perform other tasks until
interrupted. Improves efficiency.
3. Direct Memory Access (DMA):
Peripheral devices transfer data directly to or from memory without CPU involvement,
freeing CPU for other operations.

Priority Interrupt:
When multiple devices request CPU attention simultaneously, a priority interrupt system
determines which device gets serviced first.
Types:
● Software Priority: Determined by program.
● Hardware Priority: Determined by circuitry (e.g., daisy chaining, polling).
This ensures efficient interrupt handling and system stability.

Direct Memory Access (DMA):

DMA allows peripherals to transfer data directly to main memory without CPU intervention.
 ● A DMA Controller manages data transfer, memory address, and control signals.
● Operation:
1. CPU initializes DMA.

2. DMA transfers data directly between I/O device and memory.

3. DMA sends an interrupt to CPU when done.

Advantages:
● Faster data transfer
● Reduced CPU workload
● Used in disk operations, multimedia devices, and high-speed I/O systems

2. Memory Organization: Main Memory, Auxiliary

Memory, Associative Memory, Cache Memory, and Virtual
Memory
Main Memory:
Main memory (Primary memory) is the immediate accessible storage directly connected to the
CPU. It temporarily holds data and instructions needed for processing.
Types:
1. RAM (Random Access Memory):

o Volatile memory used for temporary data.

o Two types: Static RAM (SRAM) and Dynamic RAM (DRAM).

2. ROM (Read Only Memory):

o Non-volatile, used to store firmware and boot programs.

Characteristics:
● Fast access time
● Limited capacity
● Directly addressable by the CPU
Auxiliary Memory:
Also known as secondary storage, it provides long-term data storage.
Examples: Hard disks, SSDs, CDs, DVDs, Magnetic tapes.
Features:
● Non-volatile (retains data without power)
● Larger capacity but slower access time
● Data must be transferred to main memory before CPU can use it
Auxiliary memory is used to store OS, applications, and large datasets.

Associative Memory (Content Addressable Memory - CAM):

Associative Memory allows data retrieval based on content rather than address.
● Each memory word is accessed by matching data patterns.
● It compares input data with stored data simultaneously.
● Used in cache searching, translation lookaside buffers (TLB), and networking.
Example:
If you search for a specific key, the system retrieves the address automatically instead of
referencing an address location.
Advantages:
● Parallel searching
● High speed in lookup operations
Applications:
● Database indexing
● CPU cache mapping
● Memory management systems

Cache Memory:
Cache memory is a small, high-speed memory located between the CPU and main memory. It
stores frequently accessed data to reduce average access time.
Working Principle:
When the CPU requests data:
● If found in cache → Cache Hit (fast access)
● If not found → Cache Miss (data fetched from main memory and stored in cache)
Types:
● Level 1 (L1): Closest to CPU, fastest but smallest.
● Level 2 (L2): Larger and slightly slower.
● Level 3 (L3): Shared among cores in multi-core CPUs.
Mapping Techniques:
1. Direct Mapping

2. Associative Mapping

3. Set-Associative Mapping

Cache memory improves performance by reducing data access latency.

Virtual Memory:
Virtual Memory is a memory management technique that gives the illusion of a large main
memory by using a portion of the hard disk as an extension of RAM.
Working:
When the main memory is full, inactive pages are moved to disk storage (called paging). When
required again, they are brought back into RAM (page swapping).
Advantages:
● Enables multitasking and large program execution
● Increases memory utilization
● Provides memory protection and process isolation
Disadvantages:
● Slower than physical RAM
● Increases disk I/O
Virtual memory is managed by the Operating System using page tables and memory mapping
hardware (MMU).
✅ Summary Table:
Memory Type Speed Volatility Function

Temporary storage for active

Main Memory Fast Volatile
data

Non-
Auxiliary Memory Slow Long-term data storage
volatile

Associative
Very Fast Volatile Content-based search
Memory

Cache Memory Very Fast Volatile Stores frequently used data

Slow (Disk- Non-

Virtual Memory Extends RAM capacity
based) volatile