한국어
메뉴

정보 이론과 부호의 기초

정보량과 엔트로피, 상호 정보량, 중복도, 고정 길이 부호와 가변 길이 부호, 접두 부호와 크래프트 부등식, 허프만 부호의 평균 부호 길이와 효율, 런 렝스 부호화, LZ77 방식, 무손실 압축과 손실 압축, 패리티와 수직 수평 패리티, 체크섬, CRC 계산, 해밍 거리와 오류의 검출·정정 능력, 해밍 부호와 SECDED, 부호화율, 인터리브, ARQ와 FEC, 이진 대칭 채널의 채널 용량, 채널 부호화 정리, 그레이 코드 변환을 계산 문제를 중심으로 한 객관식 문제로 학습합니다.

10문제 연습하기이 분야에서 무작위 10문제 · 약 5분 이 분야 연습하기이 분야의 모든 문제를 무작위 순서로 풀어요 취약 문제최근에 틀린 문제만 다시 풀어요

정보 이론과 부호의 기초: 핵심 정리

'이 정보는 몇 비트 분량인가?', '이 데이터는 어디까지 작게 할 수 있는가?', '잡음 때문에 잘못된 비트를 어떻게 찾아내어 고칠 수 있는가?' 이런 물음에 답하는 것이 섀넌이 시작한 정보 이론과 부호 이론입니다. 파일 압축, 메모리의 ECC, 통신 채널의 오류 정정, 저장 장치의 CRC 등 컴퓨터와 통신의 모든 곳에서 쓰이고 있습니다.

여기서는 정보량 −log₂ p와 엔트로피, 엔트로피가 최대가 되는 조건, 조건부 엔트로피와 상호 정보량, 중복도, 구별에 필요한 비트 수를 계산으로 확인합니다. 이어서 고정 길이 부호와 가변 길이 부호, 접두 부호와 크래프트 부등식, 허프만 부호를 만드는 법과 평균 부호 길이, 엔트로피와 비교한 효율, 기호를 묶어서 부호화하는 효과, 런 렝스 부호화와 LZ77 방식, 무손실 압축과 손실 압축의 구분 사용을 학습합니다. 후반에서는 패리티와 수직 수평 패리티, 체크섬의 약점, CRC 검사 비트의 계산과 버스트 오류의 검출, 해밍 거리와 오류를 검출·정정할 수 있는 비트 수, 해밍 부호(7, 4)의 신드롬에 의한 오류 위치의 특정, SECDED의 검사 비트 수, 부호화율, 인터리브, ARQ와 FEC, 이진 대칭 채널의 채널 용량과 채널 부호화 정리를 다루고, 마지막으로 그레이 코드의 변환을 확인합니다. IT 자격시험의 기초 이론(정보에 관한 이론, 통신에 관한 이론) 학습에도 도움이 됩니다. 계산 문제의 값은 오답 선택지의 값과 허프만 부호의 트리까지 포함하여 Python으로 계산해 확인했습니다. 2진수와 부동소수점은 '컴퓨터 산술', 패리티 비트의 계산과 그레이 코드의 성질은 '논리 회로', 2진수에서 그레이 코드로의 변환은 '타이밍 분석과 CDC', 패리티로 놓치는 오류의 확률은 '확률·통계와 대기행렬', 섀넌-하틀리 정리에 의한 채널 용량 계산은 '무선 통신의 기초', 메모리의 ECC는 'DRAM', 8b/10b 부호화와 PCI Express의 CRC는 'I/O 인터페이스와 버스', Base64와 gzip은 '웹 기술 기초', 교차 엔트로피는 '머신러닝의 기초', 해시와 암호는 '정보 보안 기초' 분야에서 다룹니다.

정보 이론과 부호의 기초 전체 문제 (40)
  1. 사건의 확률을 p라 할 때, 그 사건이 일어났다는 사실을 전달받아 얻는 정보량을 −log₂ p 비트로 한다. 확률 1/8로 일어나는 사건이 일어났다는 사실을 전달받았을 때의 정보량은?
  2. 정보량(확률 p인 사건이 일어났다는 사실을 전달받았을 때의 −log₂ p)의 성질로 올바른 것은?
  3. 기호 A, B, C, D를 각각 확률 1/2, 1/4, 1/8, 1/8로 서로 독립적으로 내는 정보원이 있다. 이 정보원의 엔트로피(1기호당 평균 정보량)는?
  4. 8종류의 기호를 내는 정보원의 엔트로피의 최댓값과, 최대가 되는 조건의 조합으로 올바른 것은?
  5. 0을 확률 0.9, 1을 확률 0.1로 서로 독립적으로 내는 이진 정보원이 있다. log₂ 0.9 ≈ −0.152, log₂ 0.1 ≈ −3.32로 한다. 이 정보원의 엔트로피에 가장 가까운 것은?
  6. 8종류의 기호를 내는 정보원의 엔트로피가 2.4비트였다. 중복도를 1 − (엔트로피 ÷ 최대 엔트로피)로 정의할 때, 이 정보원의 중복도는?
  7. 두 확률 변수 X, Y에 대하여, 조건부 엔트로피 H(X|Y)와 상호 정보량 I(X;Y)의 설명으로 올바른 것은?
  8. 두 확률 변수 X(값은 0 또는 1)와 Y(값은 a, b, c 중 하나)의 결합 확률이 P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4이고, 그 밖의 조합의 확률은 0이다. 상호 정보량 I(X;Y)는?
  9. 영문 대문자 26종류와 숫자 10종류, 합하여 36종류의 문자를 모두 같은 길이의 비트열(고정 길이 부호)로 구별하려고 한다. 1문자당 필요한 최소 비트 수는?
  10. 고정 길이 부호와 비교했을 때 가변 길이 부호의 설명으로 올바른 것은?
  11. 4개의 기호에 할당한 다음 부호어 집합 중 접두 부호(어떤 부호어도 다른 부호어의 앞부분이 되지 않는 부호)인 것은?
  12. 기호 A, B, C, D에 부호어 A = 0, B = 10, C = 110, D = 111을 할당한 접두 부호가 있다. 비트열 110100111을 앞에서부터 복호한 결과는?
  13. 4개의 기호 A~D에 다음 길이(비트 수)의 부호어를 할당하여, 0과 1로 이루어진 접두 부호를 만들려고 한다. 만들 수 있는 부호 길이의 조합은?
  14. 0과 1로 이루어진 접두 부호를 만들고 있다. 길이 2의 부호어 00과 01을 이미 사용하고 있을 때, 접두 부호의 조건을 유지한 채 추가할 수 있는 길이 3의 부호어의 최대 개수는?
  15. 기호 A, B, C, D를 확률 0.4, 0.3, 0.2, 0.1로 서로 독립적으로 내는 정보원을 허프만 부호로 부호화한다. 1기호당 평균 부호 길이는?
  16. 기호 A~E를 확률 0.3, 0.25, 0.2, 0.15, 0.1로 서로 독립적으로 내는 정보원을 허프만 부호로 부호화한다. 같은 확률인 것을 어느 쪽부터 고르느냐에 따라 부호어는 바뀔 수 있지만, 평균 부호 길이는 바뀌지 않는다. 1기호당 평균 부호 길이는?
  17. 기호 A, B, C를 확률 0.6, 0.3, 0.1로 서로 독립적으로 내는 정보원이 있으며, 그 엔트로피는 약 1.30비트이다. 이 정보원을 허프만 부호로 부호화했을 때의 효율(엔트로피 ÷ 평균 부호 길이)에 가장 가까운 것은?
  18. 0을 확률 0.8, 1을 확률 0.2로 서로 독립적으로 내는 이진 정보원이 있다. 2기호씩 묶은 00, 01, 10, 11의 4종류를 각각 하나의 기호로 보고 허프만 부호로 부호화한다. 원래의 1기호당 평균 부호 길이는?
  19. 무손실 압축과 정보원의 엔트로피의 관계에 대한 설명으로 올바른 것은?
  20. 40문자의 문자열 AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD(A가 12개, B가 4개, C가 20개, D가 4개)를, 같은 문자의 연속을 '문자(1바이트)와 개수(1바이트)'의 쌍으로 나타내는 런 렝스 부호화로 압축한다. 원래 문자열은 1문자 1바이트로 하고, 압축률을 '압축 후의 크기 ÷ 압축 전의 크기'로 할 때 압축률은?
  21. 런 렝스 부호화로 압축했을 때 크기를 가장 작게 하기 쉬운 데이터는?
  22. ZIP이나 gzip 등에서 사용되는 LZ77 방식의 개념으로 올바른 것은?
  23. LZ77 방식으로 압축한 데이터를 복원한다. 데이터는 '문자 A', '문자 B', '(거리 2, 길이 5)'의 순서로 늘어서 있다. (거리 d, 길이 L)은 '복원한 문자열의 끝에서 d문자 앞의 문자를 끝에 복사하는' 것을 1문자씩 L번 반복함을 나타낸다. 복원한 문자열은?
  24. 데이터를 압축할 때, 손실 압축이 아니라 무손실 압축을 사용해야 하는 것은?
  25. 데이터 비트열에 1의 개수가 짝수가 되도록 짝수 패리티 비트를 하나 붙여 보낸다. 수신 측에서 1의 개수를 조사하는 검사의 성질로 올바른 것은?
  26. 4비트 데이터 4행에 대해, 각 행의 오른쪽 끝에 그 행의 짝수 패리티 비트를, 마지막에 각 열의 짝수 패리티를 늘어놓은 행을 붙여 보냈다(수직 수평 패리티). 수신한 비트는 1행 1011 1, 2행 0100 0, 3행 1100 0, 4행 0101 0, 패리티 행 0100이었다(각 행의 오른쪽 끝 1비트가 행의 패리티). 1비트만 잘못되었을 때, 잘못된 비트의 위치는?
  27. 데이터를 1바이트씩 더하여, 합의 하위 8비트를 검사값(체크섬)으로 붙여 보낸다. 이 검사로 검출할 수 없는 오류는?
  28. 데이터 1101에 생성 다항식 x³ + x + 1(비트열 1011)의 CRC 검사 비트 3비트를 붙인다. 검사 비트는 데이터 뒤에 0을 3개 붙인 1101000을 1011로 나눈 나머지이며, 나눗셈에서는 뺄셈 대신 배타적 논리합을 사용한다. 검사 비트는?
  29. 생성 다항식의 차수가 r(검사 비트가 r비트)이고 상수항이 1인 CRC의 성질로 올바른 것은?
  30. 두 7비트 부호어 1011010과 0110011의 해밍 거리는?
  31. 어떤 부호의 최소 해밍 거리(어느 두 부호어 사이의 해밍 거리 중 최솟값)가 5이다. 오류 검출에만 사용하는 경우와 정정에만 사용하는 경우를 생각한다. 확실히 검출할 수 있는 오류의 비트 수와, 확실히 정정할 수 있는 오류의 비트 수의 조합으로 올바른 것은?
  32. 4개의 부호어 00000, 01011, 10101, 11110으로 이루어진 부호의 최소 해밍 거리와, 확실히 정정할 수 있는 오류의 비트 수의 조합으로 올바른 것은?
  33. 4비트 데이터에 3비트 검사 비트를 붙여 7비트 부호어로 만드는 해밍 부호(7, 4)의 부호화율에 가장 가까운 것은?
  34. 해밍 부호(7, 4)에서 7비트를 왼쪽부터 1~7번째 비트로 하고, 1, 2, 4번째 비트를 검사 비트로 한다. 검사 1은 1, 3, 5, 7번째 비트, 검사 2는 2, 3, 6, 7번째 비트, 검사 4는 4, 5, 6, 7번째 비트의 1의 개수가 각각 짝수가 되도록 만든다. 수신한 0110001에 1비트 오류가 있을 때, 잘못된 비트는?
  35. 32비트 데이터에, 1비트 오류를 정정하고 2비트 오류를 검출할 수 있는 SECDED 부호를 붙인다. 해밍 부호의 검사 비트 수 r은 2^r ≥ 데이터 비트 수 + r + 1을 만족하는 최솟값이며, SECDED에서는 여기에 전체 패리티를 1비트 더한다. 필요한 검사 비트 수는?
  36. 해밍 부호(7, 4)의 부호어 5개를 늘어놓고, 각 부호어의 1번째 비트 5개, 다음으로 2번째 비트 5개라는 순서로 보낸다(깊이 5의 인터리브). 수신 측에서 원래 순서로 되돌린 뒤 부호어마다 1비트 오류를 정정한다. 연속된 비트에 집중하여 일어나는 버스트 오류 중, 반드시 정정할 수 있는 최대 길이는?
  37. 통신에서 오류에 대처하는 방식인 ARQ(자동 재전송 요구)와 FEC(순방향 오류 정정)의 설명으로 올바른 것은?
  38. 0과 1을 보내며, 각 비트가 서로 독립적으로 확률 0.1로 반전하는 이진 대칭 채널이 있다. 이진 엔트로피 함수를 H(p) = −p log₂ p − (1 − p) log₂(1 − p)라 하면 H(0.1) ≈ 0.469이다. 이 채널의 1회 전송당 채널 용량에 가장 가까운 것은?
  39. 섀넌의 채널 부호화 정리의 내용으로 올바른 것은?
  40. 그레이 코드를 일반 2진수로 바꾸려면, 최상위 비트는 그대로 사용하고, 그보다 하위 비트는 한 자리 위에서 구한 2진수의 비트와 같은 위치의 그레이 코드 비트의 배타적 논리합으로 구한다. 4비트 그레이 코드 1101을 2진수로 바꾼 것은?

컴퓨터 시스템의 다른 분야