English
Menu

What is Prefix code?

A code in which no codeword is the beginning of another codeword. For example, {0, 10, 110, 111} is a prefix code: reading the received bit string from the start and cutting as soon as a codeword matches decodes it in only one way without waiting for later bits. For this reason it is also called an instantaneous code. If a set of code lengths satisfies the Kraft inequality, a prefix code with those lengths can be built. Huffman codes are prefix codes. Some codes that are not prefix codes, such as {0, 01, 11}, can still be decoded in only one way, but decoding them requires looking ahead at later bits.

Japanese name: 接頭符号

Prefix code appears in 5 practice questions across 1 topic, including Information Theory and Coding Basics.

Field: Information Theory and Coding Basics

Try it: questions about Prefix code

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)?

  1. A{0, 01, 011, 111}
  2. B{0, 10, 110, 111}
  3. C{00, 01, 1, 10}
Show answer and explanation

Answer: B. {0, 10, 110, 111}

In a prefix code, a symbol is determined the moment its codeword has been read, so it can be decoded immediately without waiting for later bits (an instantaneous code). In {0, 10, 110, 111}, no codeword is the beginning of another. In {0, 01, 011, 111}, 0 is the beginning of 01 and 011, and in {00, 01, 1, 10}, 1 is the beginning of 10.

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?

  1. ACABD
  2. BCBDA
  3. CCBAD
Show answer and explanation

Answer: C. CBAD

Read from the start and cut as soon as a codeword matches. 110 gives C, the following 10 gives B, 0 gives A and the remaining 111 gives D, so the result is CBAD. Because it is a prefix code, the string can be cut in only one way like this and can be decoded without any separator symbols.

Prefix code in the explanations

Questions that mention Prefix code (5)

  1. 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)?
  2. 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?
  3. 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?
  4. 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?
  5. Which of the following correctly describes a variable-length code compared with a fixed-length code?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Kraft inequality Average code length Binary symmetric channel Forward error correction (FEC) Hamming code Hamming distance Huffman coding Information entropy Lossless compression Lossy compression

Back to the glossary