Digital Signal Processing in Signal Transmission and Reception

Introduction. Digital Signal Processing (DSP) is the manipulation of signals that have been converted into digital form, using algorithms (filters, transforms, adaptive processors) implemented on DSP chips, FPGAs or software. In a modern communication system the baseband and much of the intermediate-frequency processing is done in DSP, which makes transmission and reception more reliable, spectrally efficient and flexible than pure analog processing.

Block diagram of a DSP-based communication system

   ┌────────┐  ┌─────┐  ┌────────────────────┐  ┌─────┐  ┌──────────┐  ┌────────┐
   │ Source │─▶│ ADC │─▶│   DSP  (Tx side)   │─▶│ DAC │─▶│ RF front │─▶│Antenna │
   └────────┘  └─────┘  │ • source coding    │  └─────┘  │ end + PA │  └───┬────┘
                        │ • FEC, interleaving│           └──────────┘      │
                        │ • modulation (QAM) │                                 │
                        │ • pulse shaping    │                                 ▼
                        │ • up-conversion    │                        ┌─────────────────┐
                        └────────────────────┘                        │    CHANNEL      │
                                                                      │ noise, fading,  │
                                                                      │ multipath (ISI) │
                                                                      └────────┬────────┘
                                                                               │
   ┌────────┐  ┌─────┐  ┌────────────────────┐  ┌─────┐  ┌──────────┐  ┌───────▼─┐
   │ Sink   │◀─│ DAC │◀─│   DSP  (Rx side)   │◀─│ ADC │◀─│ RF front │◀─│ Antenna │
   └────────┘  └─────┘  │ • matched filter   │  └─────┘  │ end + LNA│  └─────────┘
                        │ • equalizer, sync  │           └──────────┘
                        │ • demod, FEC decode│
                        └────────────────────┘

Improvement in transmission

1. Source coding (compression): speech/image data is compressed (e.g. ADPCM, MPEG) so that less bandwidth is needed for the same information.
2. Channel coding (FEC): convolutional, turbo and LDPC codes add controlled redundancy; at the receiver the decoder gives a coding gain of several dB, i.e. the same BER is achieved at lower transmit power.
3. Digital modulation: QPSK, M–QAM and OFDM (via IFFT/FFT) pack more bits per hertz, raising spectral efficiency.
4. Pulse shaping: raised-cosine / root-raised-cosine FIR filters band-limit the signal and eliminate inter-symbol interference (ISI) while meeting the spectral mask.
5. Adaptive techniques: adaptive modulation and coding, adaptive pre-distortion for power-amplifier linearisation, and transmit beam-forming in MIMO systems.
6. Security and flexibility: encryption, scrambling and format changes are done in software — no hardware redesign.

Improvement in reception

1. Matched filtering / correlation: maximises the SNR at the sampling instant, giving the lowest probability of error.
2. Adaptive equalisation (LMS, RLS, DFE): cancels the ISI caused by multipath fading, so high-rate data survives a dispersive channel.
3. Synchronisation: digital timing recovery and carrier/phase recovery (PLL, Costas loop) keep the sampling instant and phase locked.
4. Optimum detection and decoding: MLSE/Viterbi detection and iterative FEC decoding correct errors, improving BER by orders of magnitude.
5. Diversity combining: maximal-ratio combining of signals from several antennas/branches, and rake reception in CDMA, exploit multipath instead of being harmed by it.
6. Interference and noise rejection: sharp digital FIR/IIR filters, notch filters and adaptive cancellers remove adjacent-channel interference and hum; AGC in DSP keeps the level constant.

Conclusion

DSP improves transmission by compressing, coding, shaping and adaptively modulating the signal, and improves reception by matched filtering, equalising, synchronising and error-correcting it. The net result is higher capacity, lower bit-error rate, better power and bandwidth efficiency, and a system that can be upgraded or reconfigured purely by changing software — the basis of today's software-defined radio and 4G/5G systems.

(a) Knowledge representation — Knowledge representation (KR) is the branch of artificial intelligence concerned with how facts, beliefs, rules and relationships about the world are stored in a form that a computer can use to reason with. A good KR scheme should be representational (able to capture the required knowledge), inferential (support drawing new conclusions), and computationally efficient. In expert systems and intelligent agents, KR forms the bridge between the real-world problem and the reasoning engine that solves it.

(b) Different knowledge representation techniques

1. Logical representation — Knowledge is written in formal logic.

   • Propositional logic: facts are simple true/false propositions combined with AND, OR, NOT, IMPLIES. Simple but cannot express objects or relations.
   • First-order predicate logic (FOL): uses objects, predicates, functions and quantifiers (∀, ∃), e.g. ∀x (Engineer(x) → Skilled(x)). Very expressive and has formal inference (resolution, unification), but undecidable in the general case and computationally heavy.

2. Semantic networks — Knowledge is a graph of nodes (objects/concepts) connected by labelled, usually hierarchical, arcs (is-a, has-part, instance-of). Example: Sparrow —is-a→ Bird —has→ Wings. Inference is by inheritance and graph traversal. Intuitive and easy to visualise, but lacks formal semantics and becomes unwieldy for large domains.

3. Frames — A frame is a record-like structure representing a stereotyped object or situation, with slots (attributes) and fillers (values), supporting default values and inheritance from parent frames. Example: a Car frame with slots wheels = 4, engine, colour. Good for structured, prototypical knowledge; weak for procedural or uncertain knowledge.

4. Production rules — Knowledge is a set of IF–THEN rules held in a rule base, with a working memory of facts and an inference engine doing forward or backward chaining. Example: IF temperature > 40 °C AND coolant low THEN engine overheating. This is the classic basis of expert systems (MYCIN, DENDRAL); modular and easy to update, but rule bases become hard to manage and can suffer from conflicts and inefficiency.

5. Scripts and conceptual dependency — A script is a stereotyped sequence of events for a familiar situation (e.g. visiting a restaurant: enter → order → eat → pay), used for natural-language understanding. Conceptual dependency represents meaning as primitive acts (ATRANS, PTRANS, MTRANS) independent of the words used.

6. Description logic and ontologies — A decidable fragment of FOL used for terminological knowledge; forms the basis of the Semantic Web (OWL, RDF) and modern knowledge graphs. It gives well-defined reasoning (subsumption, classification) at the cost of limited expressiveness.

7. Logic programming and Prolog — FOL clauses in Horn-clause form, executed by resolution and backtracking; combines declarative knowledge with a built-in inference mechanism.

8. Structured/uncertain representations — Semantic nets extended with certainty factors or Bayesian networks handle uncertain and probabilistic knowledge; fuzzy logic handles vagueness; case-based reasoning stores past cases and adapts solutions.

Comparison and choice: Logical representations give rigour and expressiveness but poor tractability; network/frame/script schemes give natural structure and fast inheritance but weak semantics; production rules give modularity and explainability but poor scalability; description logic and Bayesian networks give decidability and probabilistic reasoning respectively. In practice a hybrid scheme is used — e.g. frames or ontologies for declarative domain knowledge plus production rules for inference — so that the representation matches the nature of the knowledge and the reasoning required.

1. What is DMA? (1 mark)

Direct Memory Access (DMA) is a data-transfer technique in which an I/O device transfers data directly to or from main memory without the continuous involvement of the CPU. A dedicated hardware unit called the DMA controller (DMAC) is given the starting memory address, the word count and the direction of transfer; it then takes control of the system bus and moves the data itself. The CPU only initiates the transfer and is interrupted once at the end (on completion), instead of being interrupted for every byte or word.

---

2. Internal components and registers of a standard DMA controller (3 marks)

A standard DMAC (e.g. Intel 8237) contains the following functional blocks:

(a) Registers

(b) Control and logic units

• Bus arbitration logic — generates the Bus Request (BR/HOLD) signal to the CPU and receives the Bus Grant (BG/HLDA) signal, thereby taking over the address, data and control buses.
• DMA request/acknowledge logic — receives DRQ (DMA request) from the device and returns DACK (DMA acknowledge).
• Channel selector / priority encoder — selects which channel gets the bus when several requests arrive simultaneously.
• Address incrementer/decrementer and counters — update MAR and WCR automatically.
• Interrupt logic — sends the completion interrupt to the CPU.
• Internal address/data bus — connects all the above registers and units.

---

3. Burst Mode vs Cycle Stealing Mode (3 marks)

A third, related mode is Transparent DMA, in which the DMAC uses only those bus cycles in which the CPU is not using the bus (e.g. during internal ALU operations), so the CPU is not slowed at all — but it needs very fast logic and is the slowest in throughput.

---

4. How DMA improves efficiency over interrupt-driven I/O (3 marks)

In interrupt-driven I/O, the CPU must be interrupted for every single byte/word:

1. The device raises an interrupt.
2. The CPU saves the program counter and register context.
3. The ISR reads the device status register, checks for errors.
4. The ISR reads/writes the data register and stores/loads the word in memory.
5. The CPU restores the context and resumes the interrupted program.

This costs roughly 20–50 instructions per word, and the CPU is unavailable for useful computation during each ISR.

With DMA, the CPU executes only a short initialisation routine — load MAR, load WCR, set the control register, enable the channel — and then continues executing its own program. The DMAC performs the entire block transfer on the bus, and the CPU is interrupted only once, when the word count reaches zero.

Illustration. Suppose a 1 KB block (1024 bytes) is to be transferred from a disk to memory, and an ISR takes about 40 instructions per byte:

• Interrupt-driven I/O: $1024 \times 40 = 40{,}960$ instructions ≈ 41 ms of CPU time at 1 MIPS, plus 1024 context switches.
• DMA: about 40 instructions for initialisation + 40 for the completion ISR ≈ 80 instructions ≈ 0.08 ms of CPU time, and only one interrupt.

So the CPU overhead falls from about 41 ms to about 0.08 ms — a saving of roughly 99.8 % of CPU time for that transfer. The CPU is thus freed to execute other programs while the I/O proceeds in parallel, giving higher throughput, better CPU utilisation, and much lower interrupt-handling overhead. The only cost is the extra hardware of the DMAC and the fact that the DMAC and CPU contend for the same memory bus (cycle stealing) or the CPU is temporarily halted (burst mode).

Systolic Arrays in High-Performance Parallel Processing

1. Contribution to High-Performance Parallel Processing

A systolic array is a regular, homogeneous network of simple processing elements (PEs) in which data is rhythmically pumped from PE to PE in lockstep with a global clock — analogous to the rhythmic pumping of blood by the heart (hence "systolic"). Each PE performs a simple multiply-accumulate (MAC) operation, stores a partial result, and passes data to its neighbour on each clock cycle.

How it delivers high performance:

• Massive parallelism with local communication: Hundreds to thousands of PEs operate simultaneously, and each PE communicates only with its nearest neighbours. This keeps wire lengths short, reduces capacitive load, and allows very high clock frequencies.
• Regular and modular structure: The array is built from identical cells, so it scales easily — adding more PEs increases throughput almost linearly for suitably mapped algorithms.
• Pipelining and data reuse: Inputs are broadcast diagonally and weights are held stationary (or vice versa), so each data element is reused many times before leaving the array. This drastically reduces memory bandwidth demand — the classic bottleneck of von Neumann machines.
• High throughput per unit area/power: Because control is distributed and simple (no complex instruction fetch/decode per PE), the silicon area and energy per operation are very low. Google's TPU, for example, uses a 256×256 systolic MAC array for neural network inference.
• Regular data flow matches regular algorithms: Matrix multiplication, convolution, FIR/IIR filtering, correlation, and dynamic programming all map naturally onto 1-D or 2-D systolic arrays.

Illustrative example — matrix multiplication: For C = A × B with n×n matrices, a 2-D systolic array of n×n PEs computes the product in O(n) time instead of O(n³) on a sequential processor, with each PE doing only one MAC per cycle. The speed-up is O(n²) in the ideal case.

2. Architectural Advantages

3. Limitations

• Algorithm dependence: Only algorithms with regular, repetitive data-flow patterns map efficiently. Irregular or data-dependent computations (sparse matrices, graph algorithms, branch-heavy code) map poorly.
• Rigid data flow: The fixed systolic schedule cannot adapt to varying problem sizes or irregular workloads; utilization drops when the array is not fully fed.
• I/O bandwidth bottleneck: Although internal reuse is high, getting data into and out of the array at the required rate is often the limiting factor.
• Synchronization overhead: Global clocking across a large array causes clock-skew and power-distribution problems; asynchronous or globally-asynchronous locally-synchronous (GALS) designs add complexity.
• Limited flexibility: A systolic array is essentially a fixed-function accelerator; it cannot run general-purpose code without host support.
• Fault propagation: A single faulty PE can corrupt results flowing through it unless redundancy or reconfiguration is provided.
• Design effort: Mapping an algorithm onto a systolic array and deriving the correct timing/skewing is non-trivial.

4. Analysis in the Modern Context

In modern parallel processing — dominated by multicore CPUs, GPUs, and AI accelerators — the systolic array has seen a strong revival:

• AI/ML acceleration: Tensor Processing Units (TPUs), Huawei's Ascend, and many edge-AI chips use systolic MAC arrays because deep-learning inference is dominated by dense matrix multiplication — an ideal systolic workload. This gives very high TOPS/W, which is critical for data-centre and mobile deployment.
• Comparison with GPUs: GPUs offer greater flexibility (SIMT programming, irregular parallelism) but pay for it with more complex control and higher memory bandwidth demand. Systolic arrays trade flexibility for efficiency — better when the workload is regular and fixed.
• Hybrid trend: Modern designs combine systolic arrays as specialized accelerators with general-purpose cores (e.g., CPU + TPU/NPU), using the systolic unit only for the dense-compute kernel. This "heterogeneous computing" model mitigates the flexibility limitation.
• Scaling limits: As feature sizes shrink, interconnect delay and clock distribution dominate; this favours the short, local links of systolic arrays but also pushes designs toward 3-D stacking and GALS clocking.

Conclusion: Systolic arrays contribute to high-performance parallel processing by exploiting massive, regular, locally-connected parallelism with high data reuse and low control overhead, giving excellent throughput and energy efficiency for dense, regular computations such as matrix multiplication and convolution. Their architectural advantages — modularity, scalability, and efficiency — make them highly relevant in the AI-accelerator era. However, their rigidity, I/O bottleneck, and poor fit for irregular workloads limit them to specialized roles. The modern trend is therefore not to replace general-purpose processors but to integrate systolic arrays as efficient domain-specific accelerators within heterogeneous systems.

Q1. Role of Programmable Logic Devices (PLDs) in Embedded Systems and Modern Digital System Design

1. Introduction

A Programmable Logic Device (PLD) is an integrated circuit whose digital logic function is not fixed at manufacture but is configured (programmed) by the designer. The family includes PROM, PLA, PAL, GAL, CPLD and FPGA. Because the same silicon can implement many different logic functions, PLDs bridge the gap between discrete logic gates and full-custom ASICs.

2. Types of PLDs (brief)

3. Role in Embedded Systems

1. Glue logic replacement — Address decoding, chip-select generation, bus interfacing between CPU, memory and peripherals is implemented in a single CPLD instead of dozens of 74-series ICs. This reduces board area, power and part count.
2. Custom peripheral/co-processor — Functions not present in the microcontroller (PWM generators, quadrature encoders, CRC engines, UARTs, timers) are built in the FPGA fabric and attached to the CPU bus.
3. Hardware acceleration — DSP filters (FIR/IIR), FFT, image and video pipelines run in parallel hardware, giving real-time performance that a software loop cannot achieve.
4. Reconfigurability / field upgrade — SRAM-based FPGAs allow the same hardware to be re-programmed after deployment; a product can gain new features by a firmware download without a board respin.
5. Rapid prototyping and low-volume production — No NRE mask cost and no long fabrication lead time; design changes take minutes.
6. System-on-Programmable-Chip (SoPC) — Soft-core processors (e.g., MicroBlaze, Nios II) plus peripherals on one FPGA, giving a complete embedded system on a single chip.
7. Safety and redundancy — Partial reconfiguration and dual-redundant logic blocks are used in aerospace, automotive and telecom line cards.

4. Role in Modern Digital System Design

1. Time-to-market — Design–verify–program cycle is far shorter than ASIC flow.
2. Design reuse and IP cores — Soft/hard IP (multipliers, DDR controllers, PCIe, Ethernet MAC) are instantiated, so designers work at system level rather than gate level.
3. High density and speed — Modern FPGAs contain millions of logic cells, DSP slices, block RAM and multi-gigabit transceivers, supporting 100G+ telecom interfaces.
4. Cost effectiveness — For volumes below roughly a few tens of thousands of units, FPGA/CPLD cost per unit is lower than ASIC.
5. Verification advantage — The same HDL design can be prototyped on FPGA before committing to silicon, reducing risk.
6. Telecom applications — Line cards, baseband processing, packet parsing, OTN/SDH mappers, and 5G fronthaul use FPGAs heavily because standards evolve quickly.

5. Limitations

• Higher unit cost and lower speed/power efficiency than an equivalent ASIC.
• Limited logic resources; large designs need careful partitioning.
• SRAM FPGAs lose configuration on power loss (need external configuration memory).
• Security concerns — bitstream can be copied unless encrypted.

6. Conclusion

PLDs, especially CPLDs and FPGAs, have become the backbone of modern embedded and digital design. They offer the flexibility of software with the parallelism of hardware, enabling fast, upgradable and cost-effective products. Where very high volume and ultimate performance are needed, the FPGA prototype is migrated to an ASIC; otherwise the PLD itself is the final product.

---

Q2. Distance Vector Routing Algorithm

1. Concept

Distance Vector Routing is a dynamic, decentralized routing algorithm in which every router maintains a distance vector — a table of the least known cost (hop count, delay, etc.) to every destination in the network. Each router knows only the cost to its directly connected neighbours; it learns about distant networks by exchanging vectors with neighbours.

2. Algorithm (Bellman–Ford based)

Each router executes periodically or when its table changes:

1. Initialize: cost to itself = 0, cost to directly connected neighbour = link cost, cost to all others = ∞.
2. Send its own distance vector to all neighbours.
3. On receiving a neighbour's vector $D_j$, for every destination $x$ compute $D_i(x) = \min_{j \in N(i)} \{\, c(i,j) + D_j(x) \,\}$
4. If any entry changes, update the table and inform neighbours; otherwise remain silent.
5. Repeat until no router's table changes (convergence).

3. Example

Consider four routers A, B, C, D connected as:

A ---- B ---- C ---- D
1       2       3      (link costs)

Initial vectors (cost to A, B, C, D):

Routers exchange vectors synchronously, and each round uses the vectors from the end of the previous round.

Round 1 — using the initial vectors:

• A (neighbour B, cost 1): to C = 1+2 = 3; to D = 1+∞ = ∞.
• B (neighbours A cost 1, C cost 2): to D = min(1+∞, 2+3) = 5.
• C (neighbours B cost 2, D cost 3): to A = 2+1 = 3.
• D (neighbour C, cost 3): to B = 3+2 = 5; to A = 3+∞ = ∞.

Round 2 — using the Round 1 vectors:

• A to D = min(1 + D_B(D)) = 1+5 = 6.
• D to A = 3 + D_C(A) = 3+3 = 6.
• All other entries are unchanged.

Round 3 — no router's table changes, so the network has converged.

Final routing table of A:

4. Advantages

• Simple to implement; each router needs only local information.
• No central controller; scales to large networks.
• Used in real protocols: RIP (hop count, max 15).

5. Disadvantages

• Count-to-infinity problem — bad news travels slowly; a failed link can make costs climb indefinitely.
• Slow convergence compared with Link State Routing.
• Full routing table must be exchanged with every neighbour, consuming bandwidth.
• Split horizon, route poisoning and hold-down timers are used as remedies.

1. Fundamental Characteristics of a Distributed System vs. Centralized Architecture

A centralized system keeps all processing, storage and control at one node (mainframe or single server); clients are dumb terminals that request services. A distributed system is a collection of independent computers that appears to users as a single coherent system. The distinguishing characteristics are:

In short, the essential properties are resource sharing, transparency, openness, scalability, concurrency and fault tolerance, all complicated by the absence of a global clock and the possibility of independent failure.

2. IaaS vs. PaaS vs. SaaS

These are the three fundamental service models of cloud computing, distinguished by how much of the stack the provider manages versus how much the customer manages.

The trade-off is clear: moving from IaaS → PaaS → SaaS reduces the customer's administrative burden and cost of ownership, but also reduces control over the underlying environment.

3. Public, Private and Hybrid Cloud Deployment Models

Key distinction: public vs. private is about who owns and who shares the infrastructure; hybrid is about combining both to get control where needed and elasticity where required. (Community cloud — shared by several organizations with common concerns — is sometimes added as a fourth model.)

Common Gateway Interface (CGI) and Its Role in Dynamic Web Pages

Common Gateway Interface (CGI) is a standard protocol (specification) that defines how a web server communicates with an external program (called a CGI script or gateway program) to generate web content dynamically. It acts as a bridge between the web server and external applications.

How CGI Works

1. A client (browser) sends an HTTP request to the web server for a resource that is mapped to a CGI script.
2. The web server executes the CGI program as a separate process, passing request data (query string, form data, headers) through environment variables and standard input (STDIN).
3. The CGI program processes the input, performs the required logic (e.g., database query), and returns the output to the server through standard output (STDOUT).
4. The server sends this output back to the client as an HTTP response (usually HTML).

Role in Creating Dynamic Web Pages

• Interactivity: CGI allows user input (from forms) to be processed and personalized responses to be generated, unlike static HTML pages.
• Database access: CGI scripts can connect to databases to fetch or store data, enabling content that changes with each request.
• Server-side processing: Computation, form validation, session handling, and business logic are performed on the server.
• Platform independence: CGI is language-independent — scripts can be written in Perl, C, C++, Python, PHP, etc.
• Standard interface: It provides a uniform, well-defined protocol so any compliant server (Apache, IIS) can invoke any compliant script.

Limitations

• Each request spawns a new process, causing high overhead and poor scalability under heavy load.
• Slower compared to modern embedded technologies (PHP, ASP, servlets) that run within the server process.

---

Use of PHP and Java for Internet Programming

PHP (Hypertext Preprocessor)

• A server-side scripting language embedded directly within HTML, designed specifically for web development.
• Runs on the web server (via mod_php, CGI, or FastCGI) and generates dynamic HTML output.
• Key uses:
  • Processing HTML forms and user input.
  • Connecting to databases (MySQL, PostgreSQL) for dynamic content.
  • Session and cookie management for user authentication.
  • Building CMS platforms (WordPress, Joomla) and e-commerce sites.
• Advantages: Easy to learn, open source, cross-platform, large community, low cost.

Java for Internet Programming

• Java is used for web development through Java Servlets, JSP (Java Server Pages), and frameworks (Spring, Struts).
• Servlets: Server-side Java programs that extend server functionality, handle requests/responses, and run inside a servlet container (Tomcat). They are multithreaded, so they avoid the process-per-request overhead of CGI.
• JSP: Allows Java code to be embedded in HTML (like PHP), compiled into servlets for execution.
• Key uses:
  • Building enterprise-grade, scalable, secure web applications.
  • Database connectivity via JDBC.
  • Session tracking, authentication, and transaction management.
  • Web services (REST/SOAP) and distributed applications.
• Advantages: Platform independence (Write Once, Run Anywhere), strong typing, robustness, security, and excellent support for large-scale enterprise systems.

Comparison Summary

Conclusion: CGI established the fundamental mechanism for server–application interaction on the web. PHP and Java evolved as more efficient server-side technologies—PHP for rapid, cost-effective dynamic websites and Java for robust, scalable enterprise-grade internet applications.

Bipolar Junction Transistor (BJT) — 5 marks

Construction

A BJT is a three-terminal, three-layer semiconductor device formed by sandwiching two layers of one type around a thin layer of the other type. It has two basic structures:

• NPN transistor — a thin P-type base sandwiched between two N-type regions (emitter and collector).
• PNP transistor — a thin N-type base sandwiched between two P-type regions.

The three regions are:

1. Emitter (E): Heavily doped so that it can supply a large number of majority carriers (electrons in NPN, holes in PNP). It is moderately sized.
2. Base (B): Very thin and lightly doped so that most carriers injected from the emitter can pass through to the collector without recombining. Its thickness is kept much smaller than the diffusion length of carriers.
3. Collector (C): Moderately doped and physically the largest region, so that it can dissipate the heat produced at the reverse-biased collector junction.

Thus two PN junctions are formed: the emitter–base junction (J₁) and the collector–base junction (J₂). Three terminals — emitter, base and collector — are brought out for external connection. The arrow on the emitter terminal shows the direction of conventional current (outward for NPN, inward for PNP).

Operation (NPN, active mode)

For normal amplifying operation the transistor is biased in the active region:

• The emitter–base junction is forward biased (V_BE ≈ 0.7 V for Si), which lowers the barrier potential and allows electrons from the heavily doped emitter to be injected into the thin base.
• The collector–base junction is reverse biased (V_CB large positive), which attracts these electrons across the base into the collector.

Because the base is very thin and lightly doped, only a small fraction (about 1–5%) of the injected electrons recombine with holes in the base and flow out through the base terminal, giving base current I_B. The remaining large fraction (95–99%) is swept into the collector, giving collector current I_C.

The currents are related by

$I_E = I_C + I_B$

and the current gain factors are

$\alpha = \frac{I_C}{I_E} \quad (\approx 0.95\text{–}0.99), \qquad \beta = \frac{I_C}{I_B} = \frac{\alpha}{1-\alpha}$

Since a small base current controls a much larger collector current, the BJT acts as a current-controlled current amplifier and is used in amplification and switching circuits.

1. Object-Oriented Programming Concepts and Modular Program Design in C/C++

Object-Oriented Programming (OOP) organises a program around objects — self-contained units that bundle data (attributes) and the operations on that data (methods) — rather than around functions acting on separate data. Its four pillars are:

Modular program design means decomposing a large problem into small, independent, well-defined modules that can be developed, tested and maintained separately. In C this is achieved through header files (.h) declaring interfaces and source files (.c) implementing them; in C++ additionally through classes/namespaces as modules. Key principles: high cohesion within a module, low coupling between modules, information hiding, and a single well-defined responsibility per module.

// stack.h  — interface (module boundary)
class Stack {
    int* arr; int top, cap;
public:
    Stack(int n);
    ~Stack();
    void push(int x);
    int  pop();
    bool isEmpty() const;
};

// stack.cpp — implementation hidden from users
#include "stack.h"
Stack::Stack(int n) : cap(n), top(-1) { arr = new int[n]; }
Stack::~Stack() { delete[] arr; }
void Stack::push(int x) { if (top < cap-1) arr[++top] = x; }
int  Stack::pop() { return (top >= 0) ? arr[top--] : -1; }
bool Stack::isEmpty() const { return top == -1; }

Benefits of modularity: reusability, easier debugging, parallel development, and maintainability. C++ strengthens this with namespaces (avoid name clashes), templates (generic modules), and access specifiers (enforced encapsulation).

---

2. Implementation and Applications of Stacks, Queues and Binary Trees

Stack (LIFO — Last In, First Out)

Implemented as an array with a top index or as a linked list. Core operations push, pop, peek all run in O(1).

#define MAX 100
int s[MAX], top = -1;
void push(int x){ if(top < MAX-1) s[++top] = x; }
int  pop(){ return (top >= 0) ? s[top--] : -1; }

Applications: expression conversion (infix → postfix/prefix), expression evaluation, function-call/recursion management, undo operations, backtracking (maze, DFS), syntax parsing, backtracking in compilers.

Queue (FIFO — First In, First Out)

Implemented as a circular array (using front and rear with modulo arithmetic) or as a linked list. Operations enqueue/dequeue are O(1).

int q[MAX], front = 0, rear = -1;
void enqueue(int x){ rear = (rear+1)%MAX; q[rear] = x; }
int  dequeue(){ int v = q[front]; front = (front+1)%MAX; return v; }

Applications: CPU/job scheduling, printer and disk I/O buffering, BFS traversal of graphs, message queues in networking, call-centre/request handling, rate limiting.

Binary Tree

A hierarchical structure where each node has at most two children (left, right). A binary search tree (BST) keeps left subtree < node < right subtree.

struct Node { int key; struct Node *left, *right; };
struct Node* insert(struct Node* r, int k){
    if(!r){ struct Node* n = malloc(sizeof *n); n->key=k; n->left=n->right=NULL; return n; }
    if(k < r->key) r->left  = insert(r->left, k);
    else           r->right = insert(r->right, k);
    return r;
}

Traversals: inorder (sorted order for BST), preorder (copy/serialise), postorder (delete/evaluate expression trees), level-order (BFS).

Applications: searching and sorting (BST, AVL, red-black trees), expression trees in compilers, Huffman coding, database indexing (B-tree/B+ tree), file systems, decision trees, priority queues (heap).

---

3. Relational Database Design and Normalization up to 3NF

A relational database stores data in relations (tables) of tuples (rows) and attributes (columns). Design goals: eliminate redundancy, avoid insertion/deletion/update anomalies, and preserve data integrity through keys and constraints.

Functional dependency (FD): X → Y means each value of X determines a unique value of Y. A candidate key is a minimal set of attributes that uniquely identifies a tuple; the chosen one is the primary key.

Normal forms:

• 1NF: Every attribute holds atomic (indivisible) values; no repeating groups or multivalued attributes. Each row is uniquely identified by a primary key.
• 2NF: In 1NF and no partial dependency — every non-key attribute depends on the whole primary key, not part of a composite key.
• 3NF: In 2NF and no transitive dependency — no non-key attribute depends on another non-key attribute. Formally, for every FD X → A, either X is a superkey or A is a prime attribute.

Example — unnormalised:

Enrollment(StudentID, StudentName, CourseID, CourseName, InstructorID, InstructorName)

Assume each course has one instructor. Candidate key: (StudentID, CourseID). FDs: StudentID → StudentName; CourseID → CourseName, InstructorID; InstructorID → InstructorName.

• 1NF: all attributes are atomic, so it is already in 1NF.
• 2NF: StudentName depends only on StudentID, and CourseName, InstructorID, InstructorName depend only on CourseID (partial dependencies). Remove them: Student(StudentID, StudentName), Enroll(StudentID, CourseID), Course(CourseID, CourseName, InstructorID, InstructorName).
• 3NF: in Course, InstructorName depends on InstructorID, which is a non-key attribute (CourseID → InstructorID → InstructorName, a transitive dependency). Split it: Course(CourseID, CourseName, InstructorID) and Instructor(InstructorID, InstructorName).

Final 3NF schema: Student(StudentID, StudentName), Enroll(StudentID, CourseID), Course(CourseID, CourseName, InstructorID), Instructor(InstructorID, InstructorName). There is no redundancy and no update, insertion or deletion anomaly.

---

4. Relational Algebra, SQL Query Facilities and Concurrency Control

Relational Algebra

A procedural query language operating on relations, returning relations. Core operators:

Example: names of students enrolled in course C1 — $\pi_{StudentName}\big(\sigma_{CourseID='C1'}(Enroll) \bowtie Student\big)$

SQL Query Facilities

SQL is a declarative language with these sublanguages:

• DDL: CREATE, ALTER, DROP — define schema.
• DML: SELECT, INSERT, UPDATE, DELETE — manipulate data.
• DCL: GRANT, REVOKE — access control.
• TCL: COMMIT, ROLLBACK, SAVEPOINT — transactions.

SELECT s.StudentName, AVG(m.Marks) AS AvgMarks
FROM   Student s JOIN Marks m ON s.StudentID = m.StudentID
WHERE  m.Semester = 'V'
GROUP  BY s.StudentName
HAVING AVG(m.Marks) > 60
ORDER  BY AvgMarks DESC;

Concurrency Control Mechanisms

When multiple transactions run concurrently, problems such as lost update, dirty read, and unrepeatable read arise. Mechanisms to preserve ACID properties:

1. Locking: Two-phase locking (2PL) — growing and shrinking phases; shared (S) and exclusive (X) locks. Strict 2PL prevents cascading rollback.
2. Timestamp ordering: Each transaction gets a timestamp; conflicting operations are ordered by timestamp.
3. Optimistic concurrency control: Read, validate, then write — abort on conflict.
4. Multiversion concurrency control (MVCC): Maintains multiple versions of data for snapshot reads.
5. Deadlock handling: Prevention (wait-die, wound-wait), detection via wait-for graph, or timeout-based recovery.

These ensure serialisability and consistency while allowing safe concurrent access.

Process Scheduling in an Operating System

Concept of Process Scheduling

A process is a program in execution. In a multiprogramming operating system, many processes reside in main memory at the same time, but the CPU can execute only one process at a time (on a single-core system). Process scheduling is the activity of the operating system by which it decides which process in the ready queue should be allocated the CPU, when, and for how long.

The component of the OS that makes this decision is called the scheduler (or dispatcher-related module). The main objectives of process scheduling are:

1. Maximize CPU utilization — keep the CPU as busy as possible.
2. Maximize throughput — number of processes completed per unit time.
3. Minimize turnaround time — time from submission to completion of a process.
4. Minimize waiting time — time a process spends in the ready queue.
5. Minimize response time — time from submission to first response (important for interactive systems).
6. Ensure fairness — every process gets a fair share of CPU.
7. Enforce priority — high-priority processes get preference.

The scheduling decision is made at the following points:

• When a process switches from Running → Waiting (I/O request).
• When a process switches from Running → Ready (interrupt).
• When a process switches from Waiting → Ready (I/O completion).
• When a process terminates.

If scheduling occurs only in the first and fourth cases, it is called non-preemptive (cooperative) scheduling. If it also occurs in the second and third cases, it is preemptive scheduling.

---

Types of Scheduling Algorithms

1. First Come First Served (FCFS)

Features: The ready queue is a FIFO queue. The process that arrives first is executed first. It is non-preemptive.

Merits:

• Simple to understand and implement.
• No starvation — every process eventually gets the CPU.

Demerits:

• Convoy effect — a long process at the head blocks all short processes behind it.
• Average waiting time is high and highly variable.
• Not suitable for time-sharing systems.

Suitability: Batch processing systems where response time is not critical.

2. Shortest Job First (SJF)

Features: The process with the smallest next CPU burst is selected. It may be non-preemptive or preemptive (preemptive version = Shortest Remaining Time First, SRTF).

Merits:

• Optimal — gives the minimum average waiting time among all non-preemptive algorithms.
• Favours short jobs, improving throughput.

Demerits:

• The length of the next CPU burst is difficult to predict (estimated using exponential averaging).
• Starvation of long processes is possible.
• Requires knowledge of future burst times.

Suitability: Batch systems where burst times are known or can be estimated accurately.

3. Priority Scheduling

Features: Each process is assigned a priority; the CPU is given to the highest-priority process. It may be preemptive or non-preemptive. Priorities may be static or dynamic.

Merits:

• Allows important/system processes to be served first.
• Flexible — priority can be assigned by the administrator or computed dynamically.

Demerits:

• Starvation of low-priority processes.
• Aging is needed to prevent starvation.
• Priority inversion problems in real-time systems.

Suitability: Systems with clearly differentiated classes of work — e.g., real-time and system processes over user jobs.

4. Round Robin (RR)

Features: Designed for time-sharing. Each process gets the CPU for a fixed time quantum (typically 10–100 ms). If it does not finish, it is preempted and placed at the tail of the ready queue. It is preemptive.

Merits:

• Fair — every process gets the CPU periodically.
• Response time is good; no starvation.
• Performance depends on the size of the time quantum.

Demerits:

• If the quantum is too small, context-switching overhead becomes dominant.
• If the quantum is too large, it degenerates into FCFS.
• Average waiting time is often higher than SJF.

Suitability: Time-sharing and interactive systems (e.g., UNIX, Linux).

5. Multilevel Queue Scheduling

Features: The ready queue is partitioned into several separate queues (e.g., system, interactive, batch). Each queue has its own scheduling algorithm and priority. Scheduling between queues may be fixed-priority or time-sliced.

Merits:

• Different classes of processes get appropriate treatment.
• Low overhead and simple to implement.

Demerits:

• Inflexible — a process cannot move between queues.
• Starvation of lower-priority queues.

Suitability: Systems with distinct process categories.

6. Multilevel Feedback Queue Scheduling

Features: Like multilevel queue, but processes can move between queues. A process using too much CPU time is demoted to a lower-priority queue; a process waiting too long may be promoted (aging). It is the most general and flexible algorithm.

Merits:

• Most flexible — can be tuned to a specific system.
• Prevents starvation through aging.
• Favours short and interactive jobs.

Demerits:

• Complex to implement.
• Many parameters must be tuned (number of queues, quantum per queue, promotion/demotion rules).

Suitability: General-purpose modern operating systems (e.g., Windows, Linux scheduling).

---

Comparison of Scheduling Algorithms

Conclusion

Process scheduling is the heart of a multiprogramming operating system. No single algorithm is best for all situations — the choice depends on the system's goals. FCFS is simple but suffers from the convoy effect; SJF is optimal but impractical without burst prediction; Priority scheduling respects importance but risks starvation; Round Robin provides fairness for time-sharing; and Multilevel Feedback Queue combines the advantages of several schemes and is therefore used in most modern general-purpose operating systems.