Processing math: 100%
no image
[09] Cyclic Codes
[n,k] linear code가 cyclic shift해도 codeword를 유지하면, cyclic code라고 한다. Code는 두 가지 형식으로 표현이 가능하다.Vector representation : c=(c0,c1,...,cn1)Polynomial representation : c(x)=c0+c1x+c2x2+...+cn1xn1두 표현 모두 일대일 대응이다. 먼저 Polynomial representation을 가정한다. c(x)xkc(x)를 하고 (xn1)로 mod 연산을 해주면 cyclic을 구현할 수 있게 된다. 쉽게 말하면 다음과 같다.a(x)c(x)modxn1도 codeword이다...
2024.06.11
no image
[08] Linear Codes
디지털 통신 시스템의 Error-correcting code는 다음과 같다. RSyndromecheckingCyclicRedundancyCheck(CRC)Applications:AutomaticRepeatreQuest(ARQ)Messagesizecodeword,receivedcodewordtablecodeword.2^3tablerow,k.?Hammingdistance:bitHammingweight:nonzerobitBinarycase:d..
2024.06.11
no image
[07] Channel Capacity
통신 시스템에서 중요한 개념 중 하나는 "Channel capacity"이다. Channel capacity란 통신 채널을 통해서 안전하게 전달될 수 있는 데이터의 최대 비율을 의미한다. 통신이란 A가 B에게 message를 전달하는 행위를 말하며, B가 A가 보낸 message를 정확하게 복원할 수 있으면 통신이 성공했다고 말할 수 있다. 이때 간섭이나 공격에 의해 message는 변조가 될 수 있어, B에서 복원할 수 있음이 중요한 요소로 작용한다. Channel capacity는 이런 에러가 작은 통신에서 최대로 전송할 수 있는 데이터 양이라고 생각하면 된다. Channel codes는 channel capacity만큼의 통신을 가능하게 해주는 code라고 보면 된다. 1. Discrete Memo..
2024.06.09
no image
[06] Data Compression
Coding은 데이터 압축, 암호화, 오류감지 및 수정, 데이터 전송 및 저장에 사용되는 이론이다. 주된 목적은 데이터의 패턴을 분석해서 압축하여 통신을 가능하게 하는 것이다. 1. Source coding: Data compression데이터 압축의 목적으로 사용되는 coding의 경우, 가장 빈번하게 나오는 결과에는 짧은 표현을, 가장 덜 발생하는 결과에는 상대적으로 긴 표현을 주어 압축한다.(ex. 모스 부호가 한국인에게는 가장 유명하다) DefinitionsSource code란 부호화된 데이터라고 보면된다.c(x) : codeword of xl(x) : c(x)의 길이D : D-ary alphabet으로 만들 수 있는 source code의 집합 (유한한 길이) Code를 평가하..
2024.06.08
SUMMARY
Entropy H(X)=p(x)logp(x) Properties of H H(X)0 Hb(X)=logbaHa(X) Conditioning reduces entropy H(X|Y)H(X) (w/ eq. iff X and Y are independet) H(X1,X2,...,Xn)H(Xi) (w/ eq. iff Xi are independent) H(X)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 {..
2024.04.10
no image
[05] Entropy Rates
AEP 덕분에 Xi가 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가 중요하다는 것을 ..
2024.04.10
no image
[04] AEP, Asymptotic Equipartition Property
대수적 균등 분할 원리라 하며, 큰 수의 법칙과 밀접한 관련이 있다. 장기간에 걸쳐 확률적 과정의 결과가 어떻게 나타나는지 다룬다. Convergence of Random Variable Xi가 iid이며 E(X1)=E(X2)=...=E(Xn)을 만족한다고 가정하자. 이때 ¯Xn=1n(X1+...+Xn)이라고 하자. 그러면 대수의 법칙에 의해서 n, ¯Xnμ가 된다. 우리는 그러면 ¯Xn을 다음을 만족하는 RV라고 생각해볼 수 있다. 두가지 type(strong, weak)으로 수렴이 인식된다. Types of Convergence 수렴의 종류는 구체적으로 4가지로 구분된다. A..
2024.04.10
no image
[03-2] Jensen's Inequality
Convex function x1,x2에 대해서 다음의 조건을 만족하면, 함수 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는 다르기 때문에..
2024.04.09
no image
[03-1] Entropy, Relative Entropy & Mutual Information
Uncertainty Random variable X에 대해서 X가 discrete하거나 continuous한 경우, 다음처럼 확률을 표현할 수 있다. Discrete (pmf) : P(x)=Pr{X=x} where P(x)=1 Continuous (pdf) : f(x)dx=1 cdf = F(x)=Pr(Xx) f(x)=F(x) 확률을 보고 uncertainty를 결정할 수 있다. Low Prob. = High Uncertainty High Prob. = Low Uncertainty 예를 들어서, coin toss를 하는데, head가 나올 P가 1이면, uncertainty는 0이 된다. 확실하니까 Entropy Uncertainty를 ..
2024.04.09