ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Computation Structures 1: Digital Circuits
    공부 2016. 1. 29. 11:45
    데이터를 저장하는데 필요한 비트수를 어떻게 표현할 수 있을까?
    어떤 확률을 컴퓨터에 저장하기 위한 비트로 표현하기 위한 비트수는 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번의 질문을 통해 어떤 값인지 구별 할 수 있다.

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

    댓글

Designed by Tistory.