Logic gates and Boolean algebra
Electronics · 23 questions and templates for GATE Physics, in order from warm-up to top rank. Check each answer, then read the full solution.
Loading questions… (they need JavaScript; nothing you type is sent anywhere)
Written questions with solutions
The same questions as a list, so you can print them or read without the practice box. Templates (fresh numbers) appear only in the practice box above.
-
MCQWarm-up
The smallest number of bits that can represent every whole number from to in plain binary isAnswer and solution
Answer: B
bits cover to . is too small; . So bits ().Why people get this wrong: Choosing 8 because data usually comes in whole bytes: 7 bits already reach 127.
-
NATStandard
A memory chip stores KB, organised as one byte per address ( KB bytes). The number of address lines it needs is ______.Answer and solution
Answer: 12
KB addresses, and address lines select locations. So lines. The data lines carry the byte itself and are not part of the count.Why people get this wrong: Counting bits (, giving 15) instead of addressable words.
-
MCQStandard
In excess-3 code, the decimal digit is written asAnswer and solution
Answer: D
Excess-3 adds to each decimal digit and writes the result in 4-bit binary: . The code is self-complementing: the 9's complement of a digit is obtained by inverting its bits (, ).Why people get this wrong: is plain BCD; subtracts 3 instead of adding.
-
NATExam level
A synchronous counter uses flip-flops with clock-to-output delay ns and setup time ns; the logic that forms each flip-flop's next input adds at most ns. The highest clock frequency at which it works reliably is ______ MHz.Answer and solution
Answer: 50 MHz
In one clock period the outputs must change ( ns), ripple through the next-state logic ( ns) and be stable at the next flip-flop inputs for the setup time ( ns). ns, so MHz. Unlike a ripple counter, this does not grow with the number of bits (as long as the logic delay does not).Why people get this wrong: Leaving out the setup time ( MHz) or multiplying by the number of flip-flops as in a ripple counter.
-
MSQExam level
Which statements are correct?- A shift register is a sequential circuit.
- A multiplexer needs a clock to choose which input to pass.
- A latch is level-sensitive, while an edge-triggered flip-flop responds only at a clock edge.
- A ROM used as a look-up table is a combinational circuit: its output depends only on the present address.
Answer and solution
Answer: A, C, D
A circuit is sequential if its output depends on past inputs (it has memory). A ROM read is a fixed function of the address: combinational. A shift register stores bits in flip-flops: sequential. A multiplexer is pure gating, with select lines and no clock. A latch is transparent while its enable is active; a flip-flop samples only at an edge.Why people get this wrong: A ROM "stores" data, but reading it involves no state that changes with time, so it counts as combinational.
-
MCQExam level
A 16-bit ripple-carry adder is built from full adders, each taking ns from carry-in to carry-out. The worst-case time for the carry to settle is about- ns
- ns
- ns
- ns
Answer and solution
Answer: A
In the worst case (e.g. adding to ) a carry made in the lowest stage must pass through all 16 stages in turn: ns. Carry-lookahead adders compute the carries in parallel, so their delay grows only as ; ns is the kind of figure such a design would give.Why people get this wrong: Assuming all full adders work at once (2 ns): each one has to wait for the carry from below.
-
NATHard
With as the most significant bit, . The total number of literals in its minimal sum-of-products form is ______.Answer and solution
Answer: 2
Look at the missing minterms: , i.e. , which are exactly the rows with and . So and : two groups of eight on the K-map, two literals in all.Why people get this wrong: Grouping into quads (, , ...) gives a correct but not minimal answer. Looking at the 0s first is often faster.
-
MSQHard
Which statements about flip-flops are correct?- The output of a D flip-flop after an active clock edge equals the value of just before the edge.
- A T flip-flop with divides the clock frequency by 2.
- A level-triggered JK latch with can toggle many times while the clock is high (race-around).
- An SR flip-flop can safely be given .
Answer and solution
Answer: A, B, C
A D flip-flop samples at the edge: . A T flip-flop with toggles once per clock, so its output completes one cycle every two clock cycles. A level-triggered JK latch with keeps toggling as long as the clock stays high, if the clock pulse is longer than the gate delay; edge triggering or master-slave designs fix this. is the forbidden input of an SR flip-flop.Why people get this wrong: Race-around is a problem of level triggering, not of the JK idea itself.
-
MCQHard
A 4-bit ripple counter uses flip-flops with a propagation delay of ns each. If every count must have settled at all four outputs before the next clock edge, the highest usable clock frequency is- MHz
- MHz
- MHz
- MHz
Answer and solution
Answer: A
In a ripple counter each flip-flop is clocked by the one before, so the worst case (e.g. ) needs all four to toggle one after another: ns. The clock period must be at least that, so MHz. A synchronous counter avoids the build-up because all flip-flops share one clock.Why people get this wrong: Using one flip-flop delay ( MHz) and forgetting that the delays add up along the ripple chain.
-
MCQHard
Two 8-bit two's complement numbers are added. Overflow (a wrong signed result) has occurred exactly when- there is a carry out of the most significant bit
- the carry into the most significant bit differs from the carry out of it
- the two numbers have opposite signs
- the sum is negative
Answer and solution
Answer: B
Overflow happens only when two numbers of the same sign give a sum of the other sign. That is the same as saying the carry into the sign bit and the carry out of it differ (). A carry out alone is harmless: e.g. gives a carry out and the correct answer . Numbers of opposite sign can never overflow.Why people get this wrong: Treating the carry-out bit as the overflow flag; that is right only for unsigned numbers.
-
MSQHard
With the most significant bit, , where lists don't-care terms. Which statements are correct?- is a minimal sum-of-products form of .
- is also a minimal sum-of-products form of .
- Every minimal sum-of-products form of has three product terms.
- Every minimal form must treat the don't-care as 1.
Answer and solution
Answer: A, B
covers . Only is left. It can be covered by (cells , using don't-care ) or by (cells , using don't-cares and ); both are two-literal terms, so both two-term forms are minimal (A, B true, C false). The form leaves at 0, so D is false.Why people get this wrong: Assuming the minimal form is unique, or that don't-cares must all be used.
-
NATHard
A linear-feedback shift register made of flip-flops, with XOR feedback chosen for the longest possible sequence, steps through ______ different states before repeating.Answer and solution
Answer: 31
Five bits have states. With XOR feedback the all-zeros state maps to itself, so it can never be part of the main cycle. A maximal-length (primitive-polynomial) LFSR visits all the others: states. Such registers make pseudo-random bit sequences and CRC checks.Why people get this wrong: Answering 32: the all-zero state is a lock-up state, not part of the cycle.
-
MCQHard
The circuit , built as two AND gates into an OR gate, can glitch (a brief ) when and changes. The extra product term that removes this static hazard isAnswer and solution
Answer: C
With , , but as changes one AND gate turns off before the other turns on (the inverter adds delay), so can dip. The consensus term equals 1 throughout that change and holds the output high. Logically (consensus theorem), so the function is unchanged; only the timing improves.Why people get this wrong: Minimising the expression removes exactly the redundant term that prevents the glitch.
-
MSQHard
Which of these sets of operations are functionally complete (able to build every Boolean function)?Answer and solution
Answer: A, C, D
NAND alone gives NOT () and AND (NAND then NOT), and hence OR by De Morgan. AND with NOT gives OR as . XOR with the constant 1 gives NOT (), and with AND that is complete. AND and OR alone can only build functions that never fall when an input rises (monotone functions); they can never make NOT.Why people get this wrong: Thinking AND and OR are enough because sums of products use them: the complements of the variables are needed as well.
-
MSQTop rank
Consider . Which statements are correct?- is self-dual: its dual function equals .
- No two 1s of are adjacent on its K-map, so its minimal SOP has four terms of three literals each.
- can be built from two two-input XOR gates.
- is the carry output of a full adder.
Answer and solution
Answer: A, B, C
Dual: . Complementing all three inputs flips the parity (odd number of flips), so and . On the K-map the 1s (minterms 1, 2, 4, 7) form a checkerboard: changing any one input changes , so no cells can be grouped and . uses two XOR gates. is the SUM of a full adder; the carry is the majority function.Why people get this wrong: Parity functions are the worst case for K-maps: no grouping is possible at all.
-
NATTop rank
Three D flip-flops are clocked together with , and . Starting from , the number of distinct states in the sequence before it repeats is ______.Answer and solution
Answer: 6
Apply the rule step by step: . Six states. This is a 3-bit Johnson (twisted-ring) counter; with flip-flops it has states, and the other two (, ) form a separate unused loop.Why people get this wrong: Answering assumes a binary counter; a ring with one inversion gives .
-
MCQTop rank
The expression simplifies toAnswer and solution
Answer: D
The term is the consensus of and : whenever , either (then ) or (then ). So it adds nothing: , which is absorbed by and . .Why people get this wrong: The redundant term is the one that does NOT contain the variable appearing both plain and barred.
-
NATTop rank
Two 8-bit two's complement numbers, and , are added in an 8-bit adder and the carry out is discarded. Read as an 8-bit two's complement number, the result is ______ in decimal.Answer and solution
Answer: -76
The numbers are and . Their true sum is above , the largest 8-bit signed value. The adder gives , whose top bit is 1: as a signed number it is . Two positive numbers giving a negative result is the sign of OVERFLOW.Why people get this wrong: Answering 180 ignores the 8-bit range: the hardware cannot hold it.
-
NATTop rank
A Boolean function of , , is called symmetric if swapping any two inputs never changes it (so it depends only on how many inputs are 1). The number of different symmetric functions of three variables is ______.Answer and solution
Answer: 16
A symmetric function is fixed by its value for each possible count of 1s: or . That is independent choices of 0 or 1, giving functions (among them the constants, AND, OR, majority and XOR of all three). In general there are symmetric functions of variables, against functions of three variables in all.Why people get this wrong: Counting (all functions) or (input rows).