[n,k] linear code가 cyclic shift해도 codeword를 유지하면, cyclic code라고 한다. Code는 두 가지 형식으로 표현이 가능하다.Vector representation : $ c = (c_0, c_1, ..., c_{n-1})$Polynomial representation : $ c(x) = c_0 + c_1x + c_2x^2 + ... + c_{n-1}x^{n-1} $두 표현 모두 일대일 대응이다. 먼저 Polynomial representation을 가정한다. $c(x)$에 $x^kc(x)$를 하고 $(x^n -1)$로 mod 연산을 해주면 cyclic을 구현할 수 있게 된다. 쉽게 말하면 다음과 같다.$a(x)c(x) mod x^n-1 $도 codeword이다...

디지털 통신 시스템의 Error-correcting code는 다음과 같다. $RSyndrome checkingCyclic Redundancy Check (CRC)Applications: Automatic Repeat reQuest (ARQ) 가장 나이브한 방법은 Message size를 알고 그에 따른 codeword를 알고 있을 때, received된 codeword와 table에 있는 codeword의 유사도를 비교하는 방법이다.위 방법은 $2^3$개의 table row를 요구하기 때문에, k이 작은 경우에만 사용할 수 있다. 유사도는 어떻게 비교할까?Hamming distance : 다른 bit의 수를 세기Hamming weight : nonzero bit의 수를 세기Binary case : $d..

통신 시스템에서 중요한 개념 중 하나는 "Channel capacity"이다. Channel capacity란 통신 채널을 통해서 안전하게 전달될 수 있는 데이터의 최대 비율을 의미한다. 통신이란 A가 B에게 message를 전달하는 행위를 말하며, B가 A가 보낸 message를 정확하게 복원할 수 있으면 통신이 성공했다고 말할 수 있다. 이때 간섭이나 공격에 의해 message는 변조가 될 수 있어, B에서 복원할 수 있음이 중요한 요소로 작용한다. Channel capacity는 이런 에러가 작은 통신에서 최대로 전송할 수 있는 데이터 양이라고 생각하면 된다. Channel codes는 channel capacity만큼의 통신을 가능하게 해주는 code라고 보면 된다. 1. Discrete Memo..

Coding은 데이터 압축, 암호화, 오류감지 및 수정, 데이터 전송 및 저장에 사용되는 이론이다. 주된 목적은 데이터의 패턴을 분석해서 압축하여 통신을 가능하게 하는 것이다. 1. Source coding: Data compression데이터 압축의 목적으로 사용되는 coding의 경우, 가장 빈번하게 나오는 결과에는 짧은 표현을, 가장 덜 발생하는 결과에는 상대적으로 긴 표현을 주어 압축한다.(ex. 모스 부호가 한국인에게는 가장 유명하다) DefinitionsSource code란 부호화된 데이터라고 보면된다.$c(x)$ : codeword of x$l(x)$ : $c(x)$의 길이$D*$ : D-ary alphabet으로 만들 수 있는 source code의 집합 (유한한 길이) Code를 평가하..

Entropy $$H(X) = - \sum p(x) log p(x)$$ Properties of H $H(X) \geq 0$ $H_b(X) = log_b a H_a(X)$ Conditioning reduces entropy $H(X|Y) \leq H(X)$ (w/ eq. iff X and Y are independet) $H(X_1, X_2, ..., X_n) \leq \sum H(X_i)$ (w/ eq. iff $X_i$ are independent) $H(X) \leq log |X|$ (w/ eq. iff X is uniformly distributed over X) $H(p)$ is concave in $p$ Relative Entropy $$D(p||q) = \sum p(x) log \frac {..

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를 ..