0과 1로 이루어진 부호에서 부호 길이가 l₁, l₂, …, lₙ인 접두 부호를 만들 수 있기 위한 필요충분조건 Σ 2^(−lᵢ) ≤ 1을 나타내는 부등식. 길이 l인 부호어를 하나 사용하면 그것으로 시작하는 비트열을 모두 사용할 수 없게 되어 전체의 2^(−l)을 차지한다고 생각하면 이해하기 쉽다. 예를 들어 길이 1, 2, 3, 3에서는 합이 정확히 1이 되어 0, 10, 110, 111과 같이 만들 수 있다. 한 가지로 복호할 수 있는 어떤 부호도 이 부등식을 만족하므로(맥밀런의 정리), 부호 길이를 정할 때는 접두 부호 중에서 고르면 충분하다.
일본어 명칭: クラフトの不等式
크래프트 부등식(Kraft Inequality)은(는) 정보 이론과 부호의 기초 등 1개 분야의 연습 문제 2개에 나와요.
분야: 정보 이론과 부호의 기초
정답: A. 4개
길이 3의 비트열은 2³ = 8가지가 있지만, 00이나 01로 시작하는 000, 001, 010, 011의 4개는 사용할 수 없습니다. 나머지 100, 101, 110, 111의 4개는 00과도 01과도 앞부분의 관계가 되지 않으므로 모두 추가할 수 있습니다. 크래프트 부등식으로도 2/4 + n/8 ≤ 1에서 n ≤ 4가 됩니다.
부호 길이가 l₁, l₂, …인 접두 부호를 만들 수 있는 것은 크래프트 부등식 Σ 2^(−lᵢ) ≤ 1이 성립할 때입니다.
4개의 기호 A~D에 다음 길이(비트 수)의 부호어를 할당하여, 0과 1로 이루어진 접두 부호를 만들려고 …크래프트 부등식으로도 2/4 + n/8 ≤ 1에서 n ≤ 4가 됩니다.
0과 1로 이루어진 접두 부호를 만들고 있다. 길이 2의 부호어 00과 01을 이미 사용하고 있을 때, 접…접두 부호(Prefix Code) 런 렝스 부호화(Run-Length Encoding) 무손실 압축(Lossless Compression) 상호 정보량(Mutual Information) 손실 압축(Lossy Compression) 순방향 오류 정정(FEC) 이진 대칭 채널(Binary Symmetric Channel) 정보 엔트로피(Information Entropy) 정보량(Self-Information) 패리티 비트(Parity Bit)