Computation Structures 1: Digital Circuits

데이터를 저장하는데 필요한 비트수를 어떻게 표현할 수 있을까?
어떤 확률을 컴퓨터에 저장하기 위한 비트로 표현하기 위한 비트수는 Claude Shannon이라는 사람이 1948년에 다음과 같이 정의했다.

$I(x) = log_2(\frac{1}{P_x})$
이 확률을 만들기 위해 몇비트가 필요한지를 나타내는 것이라 $log_2$가 사용되었다.

예를들어 $P(x)$가 카드에서 어떤걸 뽑는 확률이라고 해보자.
조건은 하트라는 점이다. 그러면 확률 $P(x)$는 $\frac{13}{52}$ 가 된다.
그러면 아까 식에 대입해 보면 $I(x) = log_2(\frac{52}{13}) = 2bits$ 가 나오게 된다.

data	$P_x$	$log_2(\frac{1}{P_x})$
하트이다	$\frac{13}{52}$	2 bits
스페이드에이스 카드가 아니다	$\frac{51}{52}$	0.028 bits
J, Q, K이다	$\frac{12}{52}$	2.115 bits
suicide king(하트킹)이다	$\frac{1}{52}$	5.7 bits

위에는 다양한 상황의 확률변수에 대해 몇비트가 필요한기 구한 표이다.
표를 자세히 보면 정확한 조건일 수록 필요한 비트수가 많아진다. 왜냐하면 정확한 조건일 경우 전체에 대해 적은양의 데이터를 표현해야 함으로 더 많은 비트수가 필요하고
덜 정확한 조건일 경우 전체에 대해 상대적으로 많은양의 데이터를 포함할 수 있음으로 적은 비트수가 필요하다.

그러면 인코딩이 얼마나 효율적인지는 어떻게 알아볼까?
정보과학에서 엔트로피 $H(x)$는 $x$에 대해 받은 데이터 들에 포함되어있는 정보의 양의 평균이다.
$$H(x) = E(I(x)) = \sum_{i=1}^NP_i \cdot log_2(\frac{1}{P_i}) $$
여기서 $E(X)$는 평균 즉 기대값을 의미한다
그래서 이 엔트로피를 어디에 쓰느냐 라고 물어보면 다음과 같이 설명 할 수 있다.

확률이 모두 $\frac{1}{4}$인 확률변수들의 집합인 $X = \{A, B, C, D\}$이 있다고 해보자.
$X$중에서 어떤 값을 구별 한다고 했을때
1. $AB$ 인지 $CD$인지 구분한다
2. 1번의 결과에서 두개중 한개를 질문($A$인가?)대상으로 잡고 참 거짓으로 판단
총 2개의 질문으로 $A, B, C, D$를 구별 할 수 있다.

그렇다면 확률이 다른경우는 어떨까?

확률변수	$P_x$	$log_2(\frac{1}{P_x})$
A	0.5	1 bits
B	0.125	3 bits
C	0.125	3 bits
D	0.25	2 bits

다음과 같은 확률변수 $A, B, C, D$를 가진 집합 $X$가 있다고 했을때
$A$는 질문 한번 ($A$인가 아닌가)로 구별 할수 있고 $B, C$는 3번 $D$는 2번의 질문을 통해 어떤 값인지 구별 할 수 있다.


위 그림과 같이 엔트로피를 구해보면 평균적으로 1.75번 안에 어떤 값인지 구별할 수 있다는 의미를 가진다!