Computer Hardware - ISC Class 12 Computer Science Questions with Answers, Page 3

Answer: (b) Converting Decimal to Binary An encoder has 2^n input lines and n output lines and produces the binary code of the active input.

The diagram is an OR gate. The first gate is a NOR gate; the second NOR gate has both its inputs joined, so it works as a NOT gate. NOR followed by NOT gives OR: $X = \overline{\overline{A+B}} = A + B$.

$X = A + B = 1 + 0 = 1$. (First gate: NOR(1,0) = 0; second gate: NOR(0,0) = 1.) So X = 1.

Octal to binary encoder: it has 8 input lines $D_0$ to $D_7$ (one for each octal digit, only one is 1 at a time) and 3 output lines $A_2 A_1 A_0$ giving the binary code of the digit pressed. Truth table: $D_0 \to 000$, $D_1 \to 001$, $D_2 \to 010$, $D_3 \to 011$, $D_4 \to 100$, $D_5 \to 101$, $D_6 \to 110$, $D_7 \to 111$. From it: $A_2 = D_4 + D_5 + D_6 + D_7$, $A_1 = D_2 + D_3 + D_6 + D_7$, $A_0 = D_1 + D_3 + D_5 + D_7$. Each output is a 4-input OR gate. $D_0$ needs no connection: when it is pressed all three outputs stay 0. Working: when a digit is pressed, only its input line becomes 1 and it feeds those OR gates whose equation contains it. For example, pressing 6 makes $D_6 = 1$; $D_6$ feeds the OR gates for $A_2$ and $A_1$ but not $A_0$, so $A_2 A_1 A_0 = 110$, the binary of 6. Pressing 5 gives $D_5 = 1$, which feeds $A_2$ and $A_0$, so the output is 101. Difference: an encoder converts $2^n$ input lines (only one active) into an n-bit binary code (many inputs to few outputs, built with OR gates). A decoder does the reverse: it converts an n-bit binary input into one of $2^n$ output lines, activating exactly one output (few inputs to many outputs, built with AND gates).

XOR from NOR gates (5 NOR gates): Gate 1: $N_1 = (A + B)'$ Gate 2: $N_2 = (A + N_1)' = A'B$ Gate 3: $N_3 = (B + N_1)' = AB'$ Gate 4: $N_4 = (N_2 + N_3)' = (A'B + AB')' = A \odot B$ (XNOR) Gate 5 (both inputs joined, so it works as a NOT gate): $F = N_4' = A'B + AB' = A \oplus B$ Hence the circuit of five NOR gates gives the two input XOR gate.

Universal gate: a gate from which any other gate (AND, OR, NOT, etc.) and hence any logic circuit can be built. NAND and NOR are the universal gates. Example: NAND gate as an OR gate. Using De Morgan's law, $A + B = ((A + B)')' = (A' \cdot B')'$, which is the NAND of $A'$ and $B'$. Connections: a NAND gate with both inputs joined to A gives $A'$ (NOT); another with both inputs joined to B gives $B'$; the outputs $A'$ and $B'$ feed a third NAND gate whose output is $(A' \cdot B')' = A + B$. So three NAND gates work as a two input OR gate.

Encoder for the decimal digits 2, 3, 5, 7 and 8: it has 5 input lines $D_2, D_3, D_5, D_7, D_8$ (only one is 1 at a time, when that digit is pressed) and 4 output lines $W X Y Z$ that give its BCD (8-4-2-1) code. Truth table:

Digit	D2	D3	D5	D7	D8	W	X	Y	Z
2	1	0	0	0	0	0	0	1	0
3	0	1	0	0	0	0	0	1	1
5	0	0	1	0	0	0	1	0	1
7	0	0	0	1	0	0	1	1	1
8	0	0	0	0	1	1	0	0	0

From the table: $W = D_8$ (the $D_8$ line is taken directly as W), $X = D_5 + D_7$, $Y = D_2 + D_3 + D_7$, $Z = D_3 + D_5 + D_7$. So X is a 2-input OR gate and Y and Z are 3-input OR gates. Working: when a digit key is pressed, only its input line becomes 1 and it feeds those OR gates whose equation contains it. For example, pressing 7 makes $D_7 = 1$, which feeds X, Y and Z, so $WXYZ = 0111$, the BCD of 7. Pressing 8 makes $D_8 = 1$, which gives $W = 1$ and all other outputs 0, i.e. 1000.

4:1 Multiplexer: it has 4 data inputs $I_0$ to $I_3$, 2 select lines $S_1 S_0$ and one output Y. The select lines choose which data input is passed to the output. $Y = S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$ Circuit: four 3-input AND gates, each taking one data input and one combination of the select lines (or their complements), feed one 4-input OR gate whose output is Y. For example, when $S_1S_0 = 10$ only the third AND gate is enabled and $Y = I_2$.

A decoder is a combinational circuit with n input lines and up to $2^n$ output lines; for each input combination it activates exactly one unique output line, i.e. it converts (decodes) a binary code into an individual output signal. A multiplexer (MUX) is a combinational circuit with $2^n$ data input lines, n select lines and a single output line; based on the binary value on the select lines it selects one of the many data inputs and routes it to the single output. So a decoder is a 1-input-code-to-many-output device, while a multiplexer is a many-input-to-1-output (selector) device - they perform opposite (complementary) operations. 3-to-8 decoder truth table (inputs A2 A1 A0; outputs D0..D7, only one output is 1 for each input row):

A2	A1	A0	D0	D1	D2	D3	D4	D5	D6	D7
0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0	0	0	0
0	1	0	0	0	1	0	0	0	0	0
0	1	1	0	0	0	1	0	0	0	0
1	0	0	0	0	0	0	1	0	0	0
1	0	1	0	0	0	0	0	1	0	0
1	1	0	0	0	0	0	0	0	1	0
1	1	1	0	0	0	0	0	0	0	1

Logic circuit: Inputs A2, A1, A0 and their complements A2', A1', A0' (obtained via NOT gates) are fed into eight 3-input AND gates, one per output line, each wired to the unique combination of true/complemented inputs matching its minterm, e.g. $D0=A2'.A1'.A0'$, $D1=A2'.A1'.A0$, $D2=A2'.A1.A0'$, ..., $D7=A2.A1.A0$. Working: For any given 3-bit binary input on A2 A1 A0, only the one AND gate whose input combination exactly matches that pattern produces an output of 1; all other AND gates output 0 because at least one of their inputs is 0. Thus the decoder 'decodes' the binary value present on its 3 input lines by activating exactly the corresponding one of its 8 output lines.

A half adder is a combinational circuit that adds two single binary digits A and B, producing a SUM output and a CARRY output (with no provision for an incoming carry). SUM = A'B + AB', CARRY = A.B

XOR (Exclusive-OR) gate: the output is 1 only when the inputs differ.

From the circuit: X and Y feed an OR gate giving $(X+Y)$; X (branched) and Z feed an AND gate giving $X.Z$; the outputs $(X+Y)$ and $(X.Z)$ feed the final AND gate. $F = (X+Y).(X.Z) = X.X.Z + X.Y.Z = X.Z + X.Y.Z = X.Z.(1+Y) = X.Z$ (verified with the boolean tool) So the circuit reduces to $F = X.Z$, i.e. it represents a 2-input AND gate with inputs X and Z (input Y has no effect on the output).

$A'+B$ using only NAND gates. Since $NAND(X,Y) = (X.Y)' = X'+Y'$, we can write: $A'+B = (A.B')' = NAND(A,B')$ Gate 1: $NAND(B,B) = B'$ (a NAND gate used as an inverter, both inputs tied to B) Gate 2: $NAND(A, B') = (A.B')' = A'+B$ (output of Gate 1 fed as one input, A as the other input) Only 2 NAND gates are required.

An Encoder is a combinational logic circuit that converts an active input line (out of $2^n$ possible input lines, only one of which is active/HIGH at a time) into an n-bit binary code representing that active input. Encoder for hexadecimal digits A-F to binary: the hex digits A to F correspond to decimal 10 to 15, i.e. binary codes 1010 to 1111. Using 6 input lines A,B,C,D,E,F (one active at a time) and 4 output lines Y3 Y2 Y1 Y0: A=1010, B=1011, C=1100, D=1101, E=1110, F=1111 $Y3 = A+B+C+D+E+F$ $Y2 = C+D+E+F$ $Y1 = A+B+E+F$ $Y0 = B+D+F$ Application of a Multiplexer: A multiplexer is used in data routing/data selection - e.g. to select one of many input data sources (from several communication lines or registers) and route it to a single output/transmission line, such as in telecommunication/satellite communication systems or for selecting data onto a common data bus.

Half Adder vs Full Adder: - A Half Adder adds two single bits (A and B) and produces a Sum and a Carry; it has no provision for an input carry from a previous stage. - A Full Adder adds three bits - two input bits (A, B) plus a carry-in (Cin) from the previous lower-order addition - and produces a Sum and a Carry-out (Cout). It is used for adding multi-bit binary numbers, where carries must be propagated from one bit position to the next, something a Half Adder alone cannot do. Full Adder logic: $Sum = A \oplus B \oplus Cin$; $Carry(Cout) = A.B + Cin.(A \oplus B)$

Multiplexer: a combinational circuit that has $2^n$ data input lines, n select (control) lines and a single output. It selects one of the data inputs, according to the select lines, and passes it to the output (many-to-one, a data selector). Difference from a decoder: a decoder has n input lines and $2^n$ output lines, has no data inputs, and activates exactly one output line for each input combination (one-to-many); a multiplexer has $2^n$ data inputs with select lines and only one output line that carries the selected data. 8:1 Multiplexer: 8 data inputs D0 to D7, 3 select lines S2 S1 S0 and one output Y. $Y = S_2'S_1'S_0'D_0 + S_2'S_1'S_0D_1 + S_2'S_1S_0'D_2 + S_2'S_1S_0D_3 + S_2S_1'S_0'D_4 + S_2S_1'S_0D_5 + S_2S_1S_0'D_6 + S_2S_1S_0D_7$ Circuit: eight 4-input AND gates (each data input with one select combination) feed one 8-input OR gate giving Y.

Application: a Half Adder adds two single-bit binary numbers and gives a Sum bit and a Carry bit; it is the basic building block of adders (a Full Adder is made from two Half Adders) and of the arithmetic circuits in the ALU. It cannot take a carry-in from a previous stage. Truth table:

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

$Sum = A \oplus B = A'B + AB'$ and $Carry = A \cdot B$. Circuit diagram: inputs A and B go to an XOR gate (output Sum) and to an AND gate (output Carry).

A 2-input XNOR gate gives output 1 when both inputs are equal: $F = A \odot B = AB + A'B' = (A \oplus B)'$. Logic diagram: the XOR gate symbol with a small bubble (NOT) at its output, inputs A and B, output F. Truth table:

A	B	F
0	0	1
0	1	0
1	0	0
1	1	1