This article covers two subjects together, Digital Logic Design and Computer Organization, because they build on each other: logic gates lead to registers and arithmetic units, which lead to a processor, memory and I/O. All five units, following the JNTUK syllabus.
Unit I: Data representation and digital logic
Number systems. Computers work in binary (base 2). Octal (base 8) and hexadecimal (base 16) are shorthand: one octal digit is 3 bits and one hex digit is 4 bits. Example: 156 = 1001 1100₂ = 9C₁₆.
Signed numbers. Of the three schemes (sign-magnitude, one’s complement and two’s complement), every modern computer uses two’s complement: invert the bits and add 1. It has a single zero, and the same adder handles both addition and subtraction. An n-bit number ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1, so −128 to 127 for 8 bits.
Floating point (IEEE 754). A real number is stored as sign × 1.fraction × 2^exponent. Single precision uses 1 sign bit, 8 exponent bits (bias 127) and 23 fraction bits; double precision uses 11 and 52. Some decimals, such as 0.1, have no exact binary form.
Codes. BCD stores each decimal digit in 4 bits. Gray code changes one bit between consecutive values. ASCII and Unicode (UTF-8) represent text. Parity bits detect single-bit errors.
Logic gates. The basic gates are AND, OR, NOT, NAND, NOR, XOR and XNOR. NAND and NOR are universal: any circuit can be built from either one alone.
Boolean algebra and K-maps. Laws such as De Morgan’s, (AB)′ = A′ + B′, simplify expressions, and fewer terms mean fewer gates. A Karnaugh map arranges minterms in Gray-code order, so that grouping adjacent 1s (in groups of 1, 2, 4 or 8) removes variables.
Combinational circuits. Their output depends only on the current input; they have no memory.
- Half adder: S = A ⊕ B, C = AB.
- Full adder: S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B).
- Decoder: n inputs select one of 2ⁿ outputs, used for address and opcode decoding.
- Multiplexer: select lines choose one of several inputs.
- Encoder and priority encoder: the reverse of a decoder.
Today:
0.1 + 0.2 = 0.30000000000000004in most languages is IEEE 754 at work, which is why money belongs in integers orDECIMAL, notfloat. Hex is everywhere: Git hashes, MAC addresses, image digests.
Unit II: Sequential circuits and computer basics
Sequential circuits have memory: their output depends on the input and on the stored state. Synchronous circuits change state only on a clock edge.
Flip-flops store one bit and change only at a clock edge. (A latch responds as long as it is enabled.)
| Type | Behaviour | Equation |
|---|---|---|
| SR | Set, reset; S = R = 1 not allowed | Q⁺ = S + R′Q |
| JK | Like SR, but J = K = 1 toggles | Q⁺ = JQ′ + K′Q |
| D | Output follows D | Q⁺ = D |
| T | Toggles when T = 1 | Q⁺ = T ⊕ Q |
The race-around problem of a JK flip-flop is fixed by a master-slave or edge-triggered design.
Registers and shift registers. A register is a group of flip-flops holding a word. A shift register moves bits left or right; the SISO, SIPO, PISO and PIPO types differ in serial or parallel input and output. A left shift multiplies by 2.
Counters.
- Ripple (asynchronous) counters: each flip-flop clocks the next. Simple, but slow and glitchy.
- Synchronous counters: all flip-flops share the clock, so the outputs change together.
- Ring counter: n states.
- Johnson counter: 2n states.
Functional units. Every computer has five: input, memory, ALU, control unit and output. The ALU, the control unit and the registers together form the CPU.
flowchart TB
IN[Input] ==> MEM[Memory]
MEM <==> CPU[CPU<br/>ALU, control unit, registers]
MEM ==> OUT[Output]
classDef core fill:#0f766e,stroke:#064e4a,stroke-width:2px,color:#ffffff
classDef data fill:#e3f2fd,stroke:#1565c0,stroke-width:1.5px,color:#1d1c1a
class CPU core
class IN,MEM,OUT data
The instruction cycle uses four key registers: PC (address of the next instruction), IR (the current instruction), MAR (the memory address) and MDR (the memory data).
- Fetch: MAR ← PC; read memory into MDR; IR ← MDR; PC ← PC + 4.
- Decode the instruction.
- Execute it, then repeat.
Buses are shared wires for address, data and control. A single bus is cheap but allows only one transfer at a time.
Performance: T = (N × S) / R, where N is the number of instructions executed, S the average cycles per instruction (CPI) and R the clock rate. Clock speed alone does not decide speed.
Multiprocessors share memory, like a multi-core CPU. Multicomputers pass messages, like a cluster.
Von Neumann architecture. Programs and data sit in the same memory (the stored program idea). Its weakness is the von Neumann bottleneck: a single path to slow memory. Caches are the cure.
Today: a cloud vCPU is usually one hardware thread, and two may share a core. A Kubernetes cluster is a multicomputer. Newer CPUs at the same GHz are faster because their CPI is lower.
Unit III: Arithmetic and the processing unit
Addition and subtraction. In two’s complement, A − B = A + (two’s complement of B). Overflow happens when two operands of the same sign give a result of the opposite sign.
Fast adders. A ripple-carry adder waits for each carry in turn. A carry-lookahead adder computes all carries at once from:
- Generate: Gᵢ = xᵢyᵢ
- Propagate: Pᵢ = xᵢ + yᵢ
- Carry: cᵢ₊₁ = Gᵢ + Pᵢcᵢ
Multiplication.
- Unsigned numbers: shift and add.
- Signed numbers: Booth’s algorithm. It looks at each multiplier bit and the bit to its right:
| Bit pair | Action |
|---|---|
| 1 0 | Subtract M |
| 0 1 | Add M |
| 0 0 or 1 1 | Do nothing |
After each step, it shifts right arithmetically. This skips runs of 1s. Bit-pair recoding and carry-save adders make multiplication faster still.
Division. Restoring division shifts, subtracts the divisor, and restores (adds back) if the result goes negative. Non-restoring division skips the restore step. Division is the slowest integer operation.
Floating-point operations.
- Addition: align the exponents, add the mantissas, normalise, round.
- Multiplication: add the exponents, multiply the mantissas.
Instruction execution. An instruction runs as a sequence of register transfers. In a single-bus CPU, temporary registers Y and Z feed the ALU, and each step moves one value. A three-bus CPU moves two operands and a result per step, so it is faster.
Control unit.
| Hardwired | Microprogrammed |
|---|---|
| Control signals come from logic gates | Control signals are stored as microinstructions in a control store |
| Fast but hard to change | Slower but flexible |
| Used by RISC processors (ARM, RISC-V) | Used for complex (CISC) instructions |
Today: after Spectre and Meltdown (2018), Intel and AMD shipped microcode updates. That was possible because of microprogrammed control. On Linux they come in the
intel-microcodeandamd64-microcodepackages.
Unit IV: Memory
Basics. Memory is byte-addressable: a k-bit address reaches 2ᵏ locations. Little-endian (x86) stores the low byte first; big-endian (network byte order) stores the high byte first.
RAM types.
- SRAM: a latch of six transistors per bit. Fast and costly, used for caches.
- DRAM: one transistor and one capacitor per bit. Dense and cheap, but it must be refreshed. Used for main memory.
- DDR SDRAM: transfers data on both clock edges.
ROM family (non-volatile): ROM, PROM, EPROM (erased with UV light), EEPROM and flash. Flash is used in SSDs and firmware.
Memory hierarchy. Each level down is bigger, slower and cheaper.
flowchart TB
R[Registers] ==> L1[L1 cache · about 1 ns] ==> L2[L2 and L3 cache] ==> M[Main memory · about 100 ns] ==> S[SSD and disk · micro to milliseconds]
classDef fast fill:#0f766e,stroke:#064e4a,stroke-width:2px,color:#ffffff
classDef slow fill:#fff3e0,stroke:#e65100,stroke-width:1.5px,color:#1d1c1a
class R,L1,L2 fast
class M,S slow
It works because of locality: recently used data (temporal locality) and nearby data (spatial locality) are likely to be used again soon.
Cache. On a hit, data comes from the cache; on a miss, a whole block is loaded from memory.
| Mapping | Where a memory block can go | Trade-off |
|---|---|---|
| Direct | Exactly one cache line | Simple, but suffers conflict misses |
| Associative | Any cache line | Best hit rate, but costly |
| Set-associative | Any line within one set | The practical compromise |
- Replacement policies: LRU, FIFO or random.
- Write policies: write-through updates memory too; write-back updates memory only when the block is evicted (marked by a dirty bit).
- Average access time = h × C + (1 − h) × M. With C = 1 ns, M = 100 ns and h = 95%, this gives about 6 ns; at h = 99%, about 2 ns. Small changes in hit rate matter a lot.
Virtual memory.
- Each program sees its own large address space, split into pages (typically 4 KB).
- The MMU translates addresses using a page table.
- The TLB caches recent translations.
- A missing page causes a page fault, and the OS loads the page from disk.
- The hardware also enforces protection and user/kernel modes.
Secondary storage. For a hard disk, access time = seek + rotational latency + transfer, which comes to milliseconds. SSDs use flash, with no moving parts, so they need no seek and take microseconds.
Today: databases are fast when their data fits in RAM, because of the cache hit rate. A container that exceeds its memory limit is OOMKilled. Linux huge pages reduce TLB misses.
Unit V: Input/output
Accessing devices.
- Memory-mapped I/O: device registers use normal memory addresses.
- I/O-mapped I/O: special instructions, such as
INandOUTon x86. - Polling: the CPU loops checking status. It is simple but wastes time.
Interrupts.
- The device raises an IRQ.
- The CPU finishes the current instruction and saves the PC and status.
- It runs the interrupt service routine (ISR).
- It restores its state and resumes.
Interrupts can be enabled or disabled.
Handling many devices.
- Identifying the device: polling, or vectored interrupts (the device sends an ID that indexes a vector table).
- Ordering: priority levels, or a daisy chain (priority by position).
- Exceptions use the same mechanism for errors, page faults, debugging (trace, breakpoints) and system calls.
- Processor examples: ARM has IRQ and FIQ (fast interrupt) modes; x86 has 256 vectors and an interrupt descriptor table.
DMA (Direct Memory Access). The CPU gives the DMA controller a start address, a word count and a direction. The controller moves the whole block between the device and memory, and interrupts once at the end. It works either by cycle stealing (one bus cycle at a time) or in burst mode (a whole block at once).
Bus arbitration decides who gets the bus. In centralised arbitration, an arbiter uses Bus Request, Bus Grant and Bus Busy signals. In distributed arbitration, the devices compete by ID.
Bus timing. A synchronous bus uses a common clock: simple and fast. An asynchronous bus uses a handshake (Master-ready and Slave-ready), which adapts to any device speed.
Interfaces.
- Parallel: many bits at once, but suffers skew at high speed.
- Serial: one bit at a time; a UART adds start and stop bits.
Standard interfaces.
- PCI: shared parallel bus.
- PCIe: point-to-point serial lanes, now the main expansion bus.
- SCSI / SAS: server storage.
- SATA: consumer disks, up to 6 Gb/s.
- USB: a host-controlled tree of hubs, hot-pluggable, and also supplies power.
Today: NVMe SSDs are DMA over PCIe, which is why they far outrun SATA. Cloud disks on AWS Nitro instances appear as NVMe devices.
cat /proc/interruptsshows interrupts per CPU core. Every system call is a trap into the kernel.
One-page recap
| Unit | Key ideas |
|---|---|
| I | Binary and hex, two’s complement, IEEE 754, gates, NAND/NOR universal, K-maps, adders, MUX and decoders |
| II | Flip-flops (SR, JK, D, T), registers, counters, five functional units, PC/IR/MAR/MDR, buses, T = N×S/R, von Neumann |
| III | Overflow, carry lookahead, Booth’s algorithm, restoring division, floating-point steps, bus organisation, hardwired versus microprogrammed control |
| IV | SRAM/DRAM/ROM, memory hierarchy, locality, cache mapping, replacement and write policies, virtual memory, TLB, page faults, disks and SSDs |
| V | Memory-mapped I/O, polling, interrupts, vectored and daisy-chain priority, exceptions, DMA, bus arbitration, sync/async buses, PCIe and USB |
Textbooks, if you want to go deeper:
- Hamacher et al., Computer Organization and Embedded Systems
- Morris Mano, Digital Design
- Patterson and Hennessy, Computer Organization and Design
Next in Engineering Revisited: Database Management Systems.
Written by Claude, Anthropic’s AI assistant, as part of Engineering Revisited, a quick refresher of the B.Tech subjects one at a time.