AEP 덕분에 $X_i$가 iid인 경우에, $nH(X)$ bit만 있으면 데이터를 표현할 수 있었다. 그런데 RV가 iid가 아니거나 stationary RV라면 어떻게 될까? 우선 프로세스는 크게 Stochastic process와 Stationary process로 나뉜다. Stochastic process Joint distribution으로 표현 가능한 경우이다. 가령 Entropy의 stochastic process는 다음처럼 나타낼 수 있다. Stationary process 시간에 따라 distribution이 변하지 않는 경우이다. Markov Chain 바로 직전의 결과만이 현재에 영향을 주는 경우를 말한다. Initial state와 transition matrix가 중요하다는 것을 ..

대수적 균등 분할 원리라 하며, 큰 수의 법칙과 밀접한 관련이 있다. 장기간에 걸쳐 확률적 과정의 결과가 어떻게 나타나는지 다룬다. Convergence of Random Variable $X_i$가 iid이며 $E(X_1)=E(X_2)=...=E(X_n)$을 만족한다고 가정하자. 이때 $\overline{X_n}=\frac{1}{n}(X_1+...+X_n)$이라고 하자. 그러면 대수의 법칙에 의해서 $n→\infty$, $\overline{X_n}→\mu$가 된다. 우리는 그러면 $\overline{X_n}$을 다음을 만족하는 RV라고 생각해볼 수 있다. 두가지 type(strong, weak)으로 수렴이 인식된다. Types of Convergence 수렴의 종류는 구체적으로 4가지로 구분된다. A..

Convex function $x_1, x_2$에 대해서 다음의 조건을 만족하면, 함수 $f$는 convex라고 한다. 또한 2차 미분이 모든 곳에서 양수면 convex이다. Inequality Jensen's Inequality 어떤 $f$가 convex이면, 다음의 조건을 만족한다. 어떤 함수의 기댓값은 기댓값을 취한 후, 함수를 적용하는 것보다 크거나 같음을 의미한다. 또한 $f$가 strictly convex면, $X=E[X]$고 $X$는 constant임을 알 수 있다. (equality가 성립하는 조건) Information Inequality 정보 불평등이라 불리는 이유는 오직 p(x)=q(x)일 경우에만, equality가 성립하기 때문이다. 이 말은 대부분의 경우 p와 q는 다르기 때문에..

Uncertainty Random variable X에 대해서 X가 discrete하거나 continuous한 경우, 다음처럼 확률을 표현할 수 있다. Discrete (pmf) : $P(x) = Pr\{X=x\}$ where $\sum P(x)=1$ Continuous (pdf) : $\int f(x) dx = 1$ cdf = $F(x) = Pr(X \leq x)$ $f(x) = F'(x)$ 확률을 보고 uncertainty를 결정할 수 있다. Low Prob. = High Uncertainty High Prob. = Low Uncertainty 예를 들어서, coin toss를 하는데, head가 나올 P가 1이면, uncertainty는 0이 된다. 확실하니까 Entropy Uncertainty를 ..

Axiomatic Approach, 공리적 접근 수학이론의 응용을 "Measure Theory"라고 한다. 보통 triplet $ (\Omega, F, P) $으로 표현한다. $\Omega$ : sample space / 모든 가능한 outputs $F$ : $\sigma$-algebra / 모든 가능한 events $P$ : 확률 Conditional Probability A와 B가 event이고 $P(A) > 0$이면, $$ P(B|A) = \frac{P(A \cap B)}{P(A)} $$ $$ P(A \cap B) = P(B|A)P(A) = P(A|B)P(B) $$ 위의 관계에서 Bayes rule도 유도할 수 있다. $$ P(A|B) = \frac {P(B|A)P(A)} {P(B)} $$ Tota..

정보량을 수학적으로 수치화하고 분석하려는 학문이다. Shannon에 의해 시작된 학문으로 두가지 fundamental한 요소를 파악하는 것이 목표이다. the entropy H the channel capacity C 위에서 볼 수 있듯이, 통신하는 과정에서 정보 손실을 최소화하는 것이 목표이다. 초기에는 어느정도의 에러로 정보를 전송하는 것이 불가능하다고 여겨졌다. 그런데, Shannon이 error 발생 확률을 거의 0이 될 수 있음을 보임으로써, channel noise로 capacity를 구해 정보량의 손실 없이 통신하는 방법을 제안한다. entropy of source < capacity of channel = error-free

File에는 다음의 정보가 저장되어 있다. Inode number Path File descriptor Inode에는 meta data가 저장되어 있다. Hierarchical으로 구성되어 있다. 빈번하게 path를 검색하는 것을 방지하기 위해서 사용된다. 가령 file descriptor는 다음처럼 사용된다. int fd = open(char *path, int flat, mode_t mode) read(int fd, void *buf, size_t nbyte) write(int fd, void *buf, size_t nbyte) close(int fd) Disk Structure Disk는 large array로 구성되어 있다. Data를 이 array에 잘 mapping하는 것이 주요 포인트이다. ..

HW supprot for I/O I/O를 쉽게 하기 위해, 각 HW는 bus에 연결되어 있어 통신이 가능해진다. Canonical HW device HW를 쉽게 관리하기 위해 공통된 protocol을 가지고 있다. Write할 때 발생하는 protocol은 다음과 같다. HW interface가 결국, 동작을 결정하게 된다. 각 친구들의 variants는 다음과 같다. Status Data Control polling interrupts PIO DMA Special instruction Memory-mapped I/O Status Interrupt이 항상 좋은 것은 아니다. Fast device라면 spin하는 것이 더 좋을 수 있다. 또한 interrupt이 계속해서 발생하는 device라면 live..

Conditional variable은 queue에 park하고 unpark를 기다리는 것이었다. 즉, state가 없다. CV에 state를 넣어서 관리하려고 만든 것이 semaphore이다. 동작은 간단하다. Wait sem > 0 이면. semaphore의 값을 1 감소시키고 lock을 acquire한다. sem < 0 이면, 대기한다. post()에 의해 sem 값이 0보다 커지면 깨어날 수 있다. Post: sem의 값을 1 증가시킨다. 그리고 waiter 하나를 깨운다. 위 동작은 atomic하게 구현되어 있다. Conditional variable보다 동작이 간단해진다. Semaphore = Lock + CV Semaphore로 lock이나 CV처럼 사용할 수 있고, lock과 CV가 있으면..