한국어
메뉴

정보 이론과 부호의 기초

4개의 기호 A~D에 다음 길이(비트 수)의 부호어를 할당하여, 0과 1로 이루어진 접두 부호를 만들려고 한다. 만들 수 있는 부호 길이의 조합은?

  1. AA: 1, B: 2, C: 3, D: 3
  2. BA: 1, B: 2, C: 2, D: 3
  3. CA: 1, B: 1, C: 2, D: 3
정답과 해설 보기

정답: A. A: 1, B: 2, C: 3, D: 3

부호 길이가 l₁, l₂, …인 접두 부호를 만들 수 있는 것은 크래프트 부등식 Σ 2^(−lᵢ) ≤ 1이 성립할 때입니다. 1, 2, 3, 3에서는 1/2 + 1/4 + 1/8 + 1/8 = 1이므로 만들 수 있으며, 예를 들어 0, 10, 110, 111이 됩니다. 1, 2, 2, 3에서는 1/2 + 1/4 + 1/4 + 1/8 = 9/8, 1, 1, 2, 3에서는 1/2 + 1/2 + 1/4 + 1/8 = 11/8로, 둘 다 1을 넘으므로 만들 수 없습니다.

이 분야 연습하기 분야로 돌아가기

정보 이론과 부호의 기초의 다른 문제

  1. 0과 1로 이루어진 접두 부호를 만들고 있다. 길이 2의 부호어 00과 01을 이미 사용하고 있을 때, 접두 부호의 조건을 유지한 채 추가할 수 있는 길이 3의 부호어의 최대 개수는?
  2. 기호 A, B, C, D를 확률 0.4, 0.3, 0.2, 0.1로 서로 독립적으로 내는 정보원을 허프만 부호로 부호화한다. 1기호당 평균 부호 길이는?
  3. 기호 A~E를 확률 0.3, 0.25, 0.2, 0.15, 0.1로 서로 독립적으로 내는 정보원을 허프만 부호로 부호화한다. 같은 확률인 것을 어느 쪽부터 고르느냐에 따라 부호어는 바뀔 수 있지만, 평균 부호 길이는 바뀌지 않는다. 1기호당 평균 부호 길이는?
  4. 기호 A, B, C를 확률 0.6, 0.3, 0.1로 서로 독립적으로 내는 정보원이 있으며, 그 엔트로피는 약 1.30비트이다. 이 정보원을 허프만 부호로 부호화했을 때의 효율(엔트로피 ÷ 평균 부호 길이)에 가장 가까운 것은?
  5. 0을 확률 0.8, 1을 확률 0.2로 서로 독립적으로 내는 이진 정보원이 있다. 2기호씩 묶은 00, 01, 10, 11의 4종류를 각각 하나의 기호로 보고 허프만 부호로 부호화한다. 원래의 1기호당 평균 부호 길이는?