English
Menu

Information Theory and Coding Basics

Learn information theory and coding with multiple-choice questions centered on calculations: self-information and entropy, mutual information, redundancy, fixed-length and variable-length codes, prefix codes and the Kraft inequality, the average code length and efficiency of Huffman codes, run-length encoding, the LZ77 method, lossless and lossy compression, parity and vertical and horizontal parity, checksums, CRC calculation, Hamming distance and error detection and correction capability, Hamming codes and SECDED, code rate, interleaving, ARQ and FEC, the capacity of the binary symmetric channel, the channel coding theorem, and Gray code conversion.

Practice 10 questionsRandom questions from this topic · about 5 minutes Practice this topicAll questions in this topic, in random order Weak questionsRetry only the questions you last got wrong

Information Theory and Coding Basics: key points

"How many bits is this information worth?" "How small can these data be made?" "How can bits corrupted by noise be found and fixed?" Information theory and coding theory, founded by Shannon, answer questions like these. They are at work everywhere in computers and communication: file compression, memory ECC, error correction on communication channels, CRCs in storage devices and more.

This topic checks through calculations the amount of information −log₂ p and entropy, the condition for maximum entropy, conditional entropy and mutual information, redundancy, and the number of bits needed to distinguish items. It goes on to fixed-length and variable-length codes, prefix codes and the Kraft inequality, how to build a Huffman code and its average code length, efficiency compared with the entropy, the effect of coding symbols together, run-length encoding and the LZ77 method, and when to use lossless or lossy compression. The second half deals with parity and vertical and horizontal parity, the weakness of checksums, calculating CRC check bits and detecting burst errors, Hamming distance and the number of bit errors that can be detected and corrected, locating an error with the syndrome of the Hamming (7, 4) code, the number of SECDED check bits, code rate, interleaving, ARQ and FEC, and the capacity of the binary symmetric channel and the channel coding theorem, and it ends with Gray code conversion. It helps with the basic theory (information theory and communication theory) of IT certification exams such as Japan's Fundamental and Applied Information Technology Engineer Examinations. The values in the calculation questions, including those of the wrong choices and the Huffman trees, have been checked by computing them in Python. Binary numbers and floating point are covered in "Computer Arithmetic"; calculating a parity bit and the properties of Gray code in "Logic circuits"; converting binary to Gray code in "Timing analysis and CDC"; the probability of errors that parity misses in "Probability, Statistics and Queueing"; channel capacity with the Shannon–Hartley theorem in "Wireless Communication Basics"; memory ECC in "DRAM"; 8b/10b encoding and the CRC of PCI Express in "I/O Interfaces & Buses"; Base64 and gzip in "Web Technology Basics"; cross-entropy in "Machine Learning Basics"; and hashes and cryptography in "Information Security Basics".

All Information Theory and Coding Basics questions (40)
  1. Let the amount of information obtained on being told that an event of probability p has occurred be −log₂ p bits. Which of the following is the amount of information obtained on being told that an event of probability 1/8 has occurred?
  2. Which of the following correctly describes a property of the amount of information (−log₂ p on being told that an event of probability p has occurred)?
  3. A source emits the symbols A, B, C and D independently with probabilities 1/2, 1/4, 1/8 and 1/8. Which of the following is the entropy (average amount of information per symbol) of this source?
  4. Which of the following correctly pairs the maximum entropy of a source that emits 8 kinds of symbols with the condition under which it is reached?
  5. A binary source emits 0 with probability 0.9 and 1 with probability 0.1, independently. Take log₂ 0.9 ≈ −0.152 and log₂ 0.1 ≈ −3.32. Which of the following is closest to the entropy of this source?
  6. A source that emits 8 kinds of symbols has an entropy of 2.4 bits. Defining redundancy as 1 − (entropy ÷ maximum entropy), which of the following is the redundancy of this source?
  7. For two random variables X and Y, which of the following correctly describes the conditional entropy H(X|Y) and the mutual information I(X;Y)?
  8. Two random variables X (value 0 or 1) and Y (value a, b or c) have the joint probabilities P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4, and every other combination has probability 0. Which of the following is the mutual information I(X;Y)?
  9. The 36 characters made up of the 26 capital letters and the 10 digits are to be distinguished by bit strings all of the same length (a fixed-length code). Which of the following is the minimum number of bits needed per character?
  10. Which of the following correctly describes a variable-length code compared with a fixed-length code?
  11. Which of the following sets of codewords assigned to four symbols is a prefix code (a code in which no codeword is the beginning of another codeword)?
  12. A prefix code assigns the codewords A = 0, B = 10, C = 110 and D = 111 to the symbols A, B, C and D. Which of the following is the result of decoding the bit string 110100111 from the start?
  13. A binary prefix code is to be built by assigning codewords of the following lengths (numbers of bits) to the four symbols A to D. Which of the following sets of code lengths makes this possible?
  14. A binary prefix code is being built, and the length-2 codewords 00 and 01 are already in use. Which of the following is the maximum number of length-3 codewords that can be added while keeping the prefix condition?
  15. A source emits the symbols A, B, C and D independently with probabilities 0.4, 0.3, 0.2 and 0.1, and it is encoded with a Huffman code. Which of the following is the average code length per symbol?
  16. A source emits the symbols A to E independently with probabilities 0.3, 0.25, 0.2, 0.15 and 0.1, and it is encoded with a Huffman code. The codewords may change depending on which of two equal probabilities is chosen first, but the average code length does not. Which of the following is the average code length per symbol?
  17. A source emits the symbols A, B and C independently with probabilities 0.6, 0.3 and 0.1, and its entropy is about 1.30 bits. Which of the following is closest to the efficiency (entropy ÷ average code length) when this source is encoded with a Huffman code?
  18. A binary source emits 0 with probability 0.8 and 1 with probability 0.2, independently. Symbols are taken two at a time, each of the four pairs 00, 01, 10 and 11 is treated as one symbol, and they are encoded with a Huffman code. Which of the following is the average code length per original symbol?
  19. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?
  20. The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?
  21. Which of the following data is most likely to be made smallest by run-length encoding?
  22. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?
  23. Data compressed with the LZ77 method are to be restored. The data consist of "character A", "character B" and "(distance 2, length 5)", in that order. (distance d, length L) means repeating L times, one character at a time, "copy the character d characters back from the end of the restored string to its end". Which of the following is the restored string?
  24. When compressing data, which of the following must use lossless compression rather than lossy compression?
  25. A single even parity bit is added to a bit string of data so that the number of 1s is even, and the receiver checks the number of 1s. Which of the following correctly describes this check?
  26. Four rows of 4-bit data were sent with an even parity bit for each row at its right end and a final row of even parity bits for each column (vertical and horizontal parity). The received bits were row 1: 1011 1, row 2: 0100 0, row 3: 1100 0, row 4: 0101 0 and parity row: 0100 (the rightmost bit of each row is its row parity). If exactly one bit is wrong, which of the following is its position?
  27. Data are added up one byte at a time, and the low 8 bits of the sum are sent along as a check value (checksum). Which of the following errors cannot be detected by this check?
  28. Three CRC check bits for the generator polynomial x³ + x + 1 (bit string 1011) are to be appended to the data 1101. The check bits are the remainder of dividing 1101000, the data followed by three 0s, by 1011, using exclusive OR instead of subtraction in the division. Which of the following are the check bits?
  29. Which of the following correctly describes a CRC whose generator polynomial has degree r (r check bits) and a constant term of 1?
  30. Which of the following is the Hamming distance between the two 7-bit codewords 1011010 and 0110011?
  31. The minimum Hamming distance of a code (the smallest Hamming distance between any two codewords) is 5. Consider using it only for error detection, or only for error correction. Which of the following correctly pairs the number of bit errors that can always be detected with the number that can always be corrected?
  32. Which of the following correctly pairs the minimum Hamming distance of the code consisting of the four codewords 00000, 01011, 10101 and 11110 with the number of bit errors it can always correct?
  33. Which of the following is closest to the code rate of the Hamming (7, 4) code, which adds 3 check bits to 4 bits of data to form a 7-bit codeword?
  34. In a Hamming (7, 4) code, the seven bits are numbered 1 to 7 from the left, and bits 1, 2 and 4 are check bits. They are set so that the number of 1s is even in bits 1, 3, 5 and 7 (check 1), in bits 2, 3, 6 and 7 (check 2) and in bits 4, 5, 6 and 7 (check 4). If the received word 0110001 has a single-bit error, which of the following is the wrong bit?
  35. A SECDED code, which corrects 1-bit errors and detects 2-bit errors, is added to 32 bits of data. The number of check bits r of a Hamming code is the smallest value satisfying 2^r ≥ number of data bits + r + 1, and SECDED adds 1 bit of overall parity to this. Which of the following is the number of check bits needed?
  36. Five Hamming (7, 4) codewords are lined up and sent in the order of bit 1 of each of the five codewords, then bit 2 of each, and so on (interleaving of depth 5). The receiver restores the original order and then corrects a 1-bit error in each codeword. Which of the following is the maximum length of a burst error, concentrated in consecutive bits, that can always be corrected?
  37. Which of the following correctly describes ARQ (automatic repeat request) and FEC (forward error correction), methods for dealing with errors in communication?
  38. In a binary symmetric channel, 0s and 1s are sent and each bit flips independently with probability 0.1. With the binary entropy function H(p) = −p log₂ p − (1 − p) log₂(1 − p), H(0.1) ≈ 0.469. Which of the following is closest to the channel capacity of this channel per transmission?
  39. Which of the following correctly states Shannon's channel coding theorem?
  40. To convert a Gray code into an ordinary binary number, the most significant bit is used as it is, and each lower bit is found as the exclusive OR of the binary bit already found one position higher and the Gray code bit in the same position. Which of the following is the 4-bit Gray code 1101 converted into binary?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Other topics in Computer systems