Number Systems and Digital Circuits

What to remember

• A number system has a base (radix). Binary is base 2, octal base 8, decimal base 10, hexadecimal base 16. Conversions follow fixed methods.
• Basic gates are AND, OR, NOT; NAND and NOR are universal. Boolean algebra and De Morgan's laws simplify circuits.
• Combinational circuits (adders, multiplexers, decoders) have no memory; sequential circuits (flip-flops, counters, registers) have memory and use a clock.

1. Number systems

Each digit has a place value that is a power of the base. Example: 1101₂ = 1×8 + 1×4 + 0×2 + 1×1 = 13.

Decimal to binary: divide by 2 repeatedly and read the remainders from bottom to top. 25: 25÷2=12 r1, 12÷2=6 r0, 6÷2=3 r0, 3÷2=1 r1, 1÷2=0 r1. Answer 11001₂.

Fraction to binary: multiply by 2 repeatedly and read the integer parts from top. 0.625 × 2 = 1.25 (1), 0.25 × 2 = 0.5 (0), 0.5 × 2 = 1.0 (1). So 0.625 = 0.101₂.

Binary to octal: group bits in threes from the point. 101110₂ = 101 | 110 = 56₈.

Binary to hex: group in fours. 11010110₂ = 1101 | 0110 = D6₁₆.

Hex to decimal: 2F₁₆ = 2×16 + 15 = 47.

Octal to decimal: 17₈ = 1×8 + 7 = 15.

2. Binary codes

• BCD (8421): each decimal digit is coded in 4 bits. 59 = 0101 1001. Codes 1010 to 1111 are invalid.
• Excess-3: BCD + 3; self-complementing.
• Gray code: only one bit changes between successive values. Binary to Gray: keep the MSB, then XOR each bit with the bit before it. 1011 → 1, 1⊕0=1, 0⊕1=1, 1⊕1=0 → 1110.
• ASCII: 7-bit code with 128 characters (extended ASCII uses 8 bits); 'A' = 65, 'a' = 97, '0' = 48. Unicode covers all world scripts, including Telugu.
• Parity bit: an extra bit for simple error detection (even or odd parity). It detects a single-bit error but cannot correct it. Hamming code can detect and correct a single-bit error.

3. Logic gates

Universal gates: NAND and NOR, because any gate can be built from either one. NOT, AND, OR are the basic gates. XOR gives 1 for an odd number of 1s.

4. Boolean algebra

• Identity: A + 0 = A, A·1 = A. Null: A + 1 = 1, A·0 = 0.
• Idempotent: A + A = A, A·A = A. Complement: A + A′ = 1, A·A′ = 0.
• Double negation: (A′)′ = A. Absorption: A + AB = A.
• Distributive: A + BC = (A + B)(A + C).
• De Morgan's laws: (A + B)′ = A′·B′ and (A·B)′ = A′ + B′.
• Principle of duality: swap AND with OR and 0 with 1 to get the dual identity.

Forms: Sum of Products (SOP) uses minterms; Product of Sums (POS) uses maxterms. A minterm is an AND of all variables; a maxterm is an OR of all variables. With n variables there are 2ⁿ minterms.

Karnaugh map (K-map) simplifies Boolean functions by grouping adjacent 1s in groups of 1, 2, 4, 8 (powers of two). Larger groups give simpler terms. Cells are labelled in Gray code order. A "don't care" condition (X) may be used as 0 or 1 to help grouping.

Example: F = AB + AB′ = A(B + B′) = A.

5. Combinational circuits

Output depends only on the present input.

• Half adder: Sum = A ⊕ B, Carry = A·B. Full adder: adds A, B and carry-in. Half subtractor: Difference = A ⊕ B, Borrow = A′·B.
• Multiplexer (MUX): selects one of many inputs to one output. A 2ⁿ-to-1 MUX needs n select lines; 8-to-1 needs 3.
• Demultiplexer (DEMUX): sends one input to one of many outputs.
• Decoder: n inputs give up to 2ⁿ outputs (3-to-8 decoder). Encoder: the reverse; 2ⁿ inputs give n outputs. A priority encoder handles several active inputs by priority.
• Comparator: compares two numbers. Parity generator/checker makes or checks parity bits.

6. Sequential circuits

Output depends on present input and past state. They use a clock and memory elements called flip-flops. A flip-flop stores 1 bit.

A latch is level-triggered; a flip-flop is edge-triggered. Race-around condition appears in a JK flip-flop with J=K=1 when the clock is long; it is removed by master-slave or edge triggering.

• Register: a group of flip-flops; n flip-flops store n bits. Shift register: moves bits left or right (SISO, SIPO, PISO, PIPO).
• Counter: counts clock pulses. Asynchronous (ripple) counters pass the clock from one stage to the next; synchronous counters clock all stages together and are faster. An n-bit binary counter has 2ⁿ states and its maximum count is 2ⁿ − 1. A mod-N counter counts N states. A 4-bit counter is mod-16.
• Frequency division: each flip-flop in a counter divides the frequency by 2. Three flip-flops divide by 8. A 16 kHz clock after 3 stages gives 2 kHz.

7. Memory and converters

Memory size = number of words × bits per word. Address lines for N words = log₂N. Example: 1K × 8 memory needs 10 address lines (2¹⁰ = 1024) and 8 data lines. A PLA/PAL is a programmable logic device. An ADC converts analog to digital; a DAC converts digital to analog. Number of levels of an n-bit ADC = 2ⁿ.

Logic families: TTL (transistor-transistor logic) is fast; CMOS uses low power. Fan-out is the number of gates an output can drive; noise margin shows resistance to noise.

Worked examples

• 1. Hex to binary: 3A₁₆ = 0011 1010₂. Binary to decimal: 101101₂ = 32 + 8 + 4 + 1 = 45.
• 2. Decimal to hex: 255 ÷ 16 = 15 remainder 15, so 255 = FF₁₆. 100 ÷ 16 = 6 remainder 4, so 100 = 64₁₆.
• 3. Simplify: F = A·B + A·B′ + A′·B = A + A′·B = A + B. (First two terms give A; then A + A′B = A + B.)
• 4. De Morgan: (A + B)′ for A = 1, B = 0 gives (1)′ = 0, and A′·B′ = 0·1 = 0. Both match.
• 5. NAND as NOT: Joining both inputs of a NAND gate gives A′, so a NAND with tied inputs works as a NOT gate.
• 6. Counter: A 3-bit ripple counter counts 000 to 111, that is 0 to 7; it repeats after 8 clock pulses. A 12-bit address can select 4,096 words, since 2¹² = 4,096.
• 7. Parity: The 7-bit data 1011001 has four 1s; even parity bit = 0 and odd parity bit = 1.

Exam traps

• NAND and NOR are universal; XOR and AND are not.
• F in hexadecimal is 15, not 16; the digits run from 0 to 15.
• In binary-to-Gray, the MSB is copied unchanged.
• JK with J=K=1 toggles; SR with S=R=1 is invalid.
• n flip-flops count up to 2ⁿ − 1, but have 2ⁿ states.
• Combinational circuits have no memory; sequential circuits do.
• Fractional conversion multiplies by 2; integer conversion divides by 2.
• A decoder expands lines; an encoder reduces lines.

One-liners

• 1. Binary base is 2; hexadecimal base is 16.
• 2. 1010₂ = 10 = A in hex.
• 3. NAND is a universal gate.
• 4. De Morgan: (A·B)′ = A′ + B′.
• 5. A full adder has three inputs.
• 6. An 8-to-1 MUX needs 3 select lines.
• 7. A D flip-flop stores one bit.
• 8. A T flip-flop toggles when T = 1.
• 9. Gray code changes only one bit at a time.
• 10. ASCII is a 7-bit code.
• 11. BCD uses 4 bits per decimal digit.
• 12. A mod-16 counter needs 4 flip-flops.

Practice questions

1. The base of the hexadecimal number system is

   1. 8
   2. 10
   3. 2
   4. 16
   Answer

   D. 16

   Hexadecimal is base 16.

2. The decimal value of the binary number 1101 is

   1. 14
   2. 13
   3. 15
   4. 11
   Answer

   B. 13

   8 + 4 + 0 + 1 = 13.

3. The decimal number 25 in binary is

   1. 11001
   2. 10011
   3. 11010
   4. 10101
   Answer

   A. 11001

   25 = 16 + 8 + 1 = 11001.

4. The hexadecimal digit F represents the decimal value

   1. 15
   2. 16
   3. 10
   4. 14
   Answer

   A. 15

   A = 10 ... F = 15.

5. Binary 11010110 in hexadecimal is

   1. B6
   2. D6
   3. 6D
   4. D3
   Answer

   B. D6

   1101 = D, 0110 = 6.

6. The octal equivalent of binary 101110 is

   1. 65
   2. 46
   3. 27
   4. 56
   Answer

   D. 56

   Groups 101 = 5 and 110 = 6.

7. The decimal number 255 in hexadecimal is

   1. FF
   2. 1F
   3. EE
   4. F0
   Answer

   A. FF

   255 = 15 × 16 + 15 = FF.

8. The binary equivalent of 0.625 is

   1. 0.011
   2. 0.101
   3. 0.1001
   4. 0.110
   Answer

   B. 0.101

   0.625 = 1/2 + 1/8 = 0.101.

9. Which gate gives output 1 only when all its inputs are 1?

   1. NOR
   2. XOR
   3. OR
   4. AND
   Answer

   D. AND

   AND outputs 1 only if all inputs are 1.

10. Which gates are called universal gates?

    1. NAND and NOR
    2. AND and OR
    3. XOR and XNOR
    4. NOT and AND
    Answer

    A. NAND and NOR

    Any gate can be built from NAND alone or NOR alone.

11. The output of an XOR gate is 1 when

    1. its inputs are the same
    2. its inputs are different
    3. both inputs are 1
    4. both inputs are 0
    Answer

    B. its inputs are different

    XOR is 1 for an odd number of 1s.

12. According to De Morgan's law, (A + B)′ equals

    1. A′ + B′
    2. A + B′
    3. A′ · B′
    4. A · B
    Answer

    C. A′ · B′

    The complement of a sum is the product of complements.

13. A NAND gate with both inputs joined together works as a

    1. OR gate
    2. XOR gate
    3. AND gate
    4. NOT gate
    Answer

    D. NOT gate

    NAND(A, A) = A′.

14. The Boolean expression A + A′B simplifies to

    1. A · B
    2. A
    3. A + B
    4. A′ + B
    Answer

    C. A + B

    A + A′B = (A + A′)(A + B) = A + B.

15. The expression AB + AB′ simplifies to

    1. A
    2. A + B
    3. AB
    4. B
    Answer

    A. A

    AB + AB′ = A(B + B′) = A.

16. A K-map is used to

    1. add binary numbers
    2. simplify Boolean expressions
    3. store data bits
    4. count clock pulses
    Answer

    B. simplify Boolean expressions

    Karnaugh maps group adjacent 1s to reduce expressions.

17. In a K-map, groups of adjacent 1s must have a size that is

    1. an odd number
    2. any number
    3. a multiple of three
    4. a power of two
    Answer

    D. a power of two

    Valid groups are 1, 2, 4, 8 ... cells.

18. The BCD code of the decimal number 59 is

    1. 1001 0101
    2. 1011 1011
    3. 0101 0101
    4. 0101 1001
    Answer

    D. 0101 1001

    Each digit is coded in 4 bits: 5 = 0101, 9 = 1001.

19. The Gray code of binary 1011 is

    1. 0110
    2. 1101
    3. 1110
    4. 1010
    Answer

    C. 1110

    Keep 1, then 1⊕0 = 1, 0⊕1 = 1, 1⊕1 = 0.

20. Gray code is useful because

    1. it needs fewer bits than binary
    2. it is used for letters only
    3. only one bit changes between consecutive numbers
    4. it is self-correcting for all errors
    Answer

    C. only one bit changes between consecutive numbers

    Single-bit change reduces errors in transitions.

21. The ASCII code is a

    1. 7-bit code
    2. 16-bit code
    3. 32-bit code
    4. 4-bit code
    Answer

    A. 7-bit code

    Standard ASCII has 128 characters in 7 bits.

22. A parity bit is used for

    1. encryption
    2. error detection
    3. data compression
    4. addition
    Answer

    B. error detection

    A parity bit can detect a single-bit error.

23. An 8-to-1 multiplexer has how many select lines?

    1. 2
    2. 3
    3. 4
    4. 8
    Answer

    B. 3

    2^3 = 8, so 3 select lines.

24. A 3-to-8 decoder has how many outputs?

    1. 3
    2. 6
    3. 8
    4. 9
    Answer

    C. 8

    n inputs give 2^n outputs.

25. The Difference output of a half subtractor is

    1. A AND B
    2. A OR B
    3. A NOR B
    4. A XOR B
    Answer

    D. A XOR B

    Difference = A ⊕ B; Borrow = A′B.

26. Which of these is a sequential circuit?

    1. Counter
    2. Decoder
    3. Half adder
    4. Multiplexer
    Answer

    A. Counter

    Counters use flip-flops and have memory.

27. A flip-flop can store how many bits?

    1. 2
    2. 1
    3. 4
    4. 8
    Answer

    B. 1

    One flip-flop stores one bit.

28. In a JK flip-flop, J = K = 1 causes the output to

    1. toggle
    2. stay unchanged
    3. set
    4. reset
    Answer

    A. toggle

    J = K = 1 toggles the state.

29. Which input condition is invalid for an SR flip-flop?

    1. S = 0 and R = 1
    2. S = 1 and R = 0
    3. S = 0 and R = 0
    4. S = 1 and R = 1
    Answer

    D. S = 1 and R = 1

    S = R = 1 is the forbidden state.

30. A flip-flop that follows the input data at the clock edge is the

    1. D flip-flop
    2. SR flip-flop
    3. JK flip-flop
    4. T flip-flop
    Answer

    A. D flip-flop

    The D (delay) flip-flop passes D to the output.

31. A 4-bit binary counter has how many states?

    1. 4
    2. 16
    3. 8
    4. 15
    Answer

    B. 16

    2^4 = 16 states, counting 0 to 15.

32. A 3-bit counter driven by a 16 kHz clock gives, at its last stage, a frequency of

    1. 8 kHz
    2. 4 kHz
    3. 5.3 kHz
    4. 2 kHz
    Answer

    D. 2 kHz

    Three stages divide by 2^3 = 8; 16/8 = 2 kHz.

33. A memory of 1K × 8 needs how many address lines?

    1. 11
    2. 8
    3. 10
    4. 1024
    Answer

    C. 10

    1K = 1024 = 2^10.

34. The 7-bit data 1011001 has even parity bit

    1. 0
    2. 1
    3. 2
    4. Cannot be found
    Answer

    A. 0

    There are four 1s (even), so the even parity bit is 0.

35. Consider these statements about gates. 1. NAND is a universal gate. 2. XOR is a universal gate. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    XOR is not universal.

36. Consider these statements about circuits. 1. Combinational circuits have memory. 2. Sequential circuits use flip-flops. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    B. 2 only

    Combinational circuits have no memory; only 2 is correct.

37. Consider these statements about counters. 1. In a synchronous counter all flip-flops get the clock together. 2. Ripple counters are faster than synchronous counters. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    Synchronous counters are faster; statement 2 is wrong.

38. Consider these statements about number systems. 1. Octal uses digits 0 to 7. 2. Hexadecimal uses digits 0 to 9 and letters A to F. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are correct.

39. Consider these statements. 1. A decoder has n inputs and up to 2^n outputs. 2. An encoder has 2^n inputs and n outputs. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both describe the circuits correctly.

40. Consider these statements about Boolean algebra. 1. (A·B)′ = A′ + B′. 2. A + A = 2A. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    In Boolean algebra A + A = A, so 2 is wrong.

41. Match the gate with its output rule. P. NOR Q. XNOR R. NAND 1. 1 when inputs are equal 2. 1 only when all inputs are 0 3. 0 only when all inputs are 1

    1. P-3, Q-1, R-2
    2. P-2, Q-3, R-1
    3. P-1, Q-2, R-3
    4. P-2, Q-1, R-3
    Answer

    D. P-2, Q-1, R-3

    NOR is 1 for all-zero inputs, XNOR for equal inputs, NAND is 0 only for all-one inputs.

42. Match the flip-flop with its feature. P. T Q. D R. JK 1. Output follows data input 2. Toggles when input is 1 3. No invalid input state

    1. P-1, Q-2, R-3
    2. P-2, Q-1, R-3
    3. P-3, Q-1, R-2
    4. P-2, Q-3, R-1
    Answer

    B. P-2, Q-1, R-3

    T toggles, D follows data, JK has no invalid state.

43. Match the code with its property. P. Gray Q. BCD R. ASCII 1. Codes characters 2. Single-bit change between steps 3. Four bits per decimal digit

    1. P-1, Q-2, R-3
    2. P-2, Q-1, R-3
    3. P-3, Q-2, R-1
    4. P-2, Q-3, R-1
    Answer

    D. P-2, Q-3, R-1

    Gray changes one bit; BCD uses 4 bits per digit; ASCII codes characters.

44. A circuit that converts an analog signal into digital form is an

    1. latch
    2. decoder
    3. ADC
    4. DAC
    Answer

    C. ADC

    An ADC (analog to digital converter) does this.

45. In the binary 1101 + 0111 addition, the result is

    1. 11100
    2. 10100
    3. 10010
    4. 10101
    Answer

    B. 10100

    13 + 7 = 20 = 10100.