English
Menu

Information Theory and Coding Basics

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?

  1. AABAB
  2. BABABABA
  3. CABAAAAA
Show answer and explanation

Answer: B. ABABABA

Start from "AB", A followed by B. Copying the A two characters back gives "ABA", and then copying the B, now two characters back, gives "ABAB"; each copy moves the copy source forward by one, so copying five characters gives the seven-character "ABABABA". The length may thus exceed the distance, and by using just-copied characters as the source, a long repetition of a short pattern can be represented by a single pair.

  • A. This treats only the two characters present at the start as the copy source. Since copying is done one character at a time, the copied characters also become sources for the next copies.
  • B. Correct. A, B, A, B, A are copied after AB, giving seven characters.
  • C. This copies the same A five times, but the end moves forward with each copied character, so the character two back alternates between A and B.
Practice this topic Back to topic

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

More Information Theory and Coding Basics questions

  1. When compressing data, which of the following must use lossless compression rather than lossy compression?
  2. 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?
  3. 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?
  4. 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?
  5. 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?