HOME
RECENT CHANGES

솔리톤 분포

Soliton Distribution

Ideal Soliton Distribution

Belief-Propagation 알고리즘으로 디코딩하는 것을 상정하여 디자인 된 Luby-Transform에 있어서 핵심이 되는 분포함수이다. BP 알고리즘은 Degree 1인 인코딩심볼로부터 디코딩을 시작하는데, Soliton Distribution은 BP에 적합한 Degree 분포를 생성한다.

Definition

$\rho(1) = 1/k$
$\rho(i)=1/i(i - 1),$ $(i = 2,\ldots,k)$



Graph

$$k = 10$$

Soliton Distribution의 특징은 Degree 1과 2 사이에서 볼 수 있는 물결(ripple)에 있다. Degree 2 이후로는 함수의 정의에 따라 $1/i(i-1)$을 따라 줄어가는 형태를 가지지만, Degree 1은 일정수준 확보되는 것을 관찰할 수 있다.

$$k = 10000$$

하지만 LT가 좋은 성능을 보이는 높은 k 값에서는 Degree 1의 비율이 극단적으로 감소하는 것이 보인다. 이 경우 BP 알고리즘은 충분한 수의 Degree 1인 인코딩 심볼을 확보하기 어려워져 결과적으로 디코딩에 더 많은 인코딩 심볼을 요구하게 된다.

Normalization

함수의 정의에 의해 $k\geq 1,\thinspace i\in\mathbb{N}$ 일 때, Probability Distribution의 ​조건 ​$\sum_i\rho(i)=1$ 을 만족한다. 따라서 별도의 normalization은 필요 없지만, 코드로 구현해보면 자료형의 정밀도 한계에 의해 누적합이 1의 근사치로 나타나기도 한다.

Reference

Math Symbols

$P$ $\rho$ rho
$T$ $\tau$ tau
$M$ $\mu$ mu
$D$ $\delta$ delta

Robust Soliton Distribution

Definition

$\mu(i)=(\rho(i)+\tau(i)) / (\sum\rho(i)+\tau(i))$

Robust Soliton Distribution $\mu(i)$는 Ideal Soliton Distribution $\rho(i)$에 $\tau(i)$를 더하고 누적합이 1이 되도록 normalization을 수행한 것이다.

$\tau(i)= 1/im,$ $(i=1,2,\dots,m-1)$
$\tau(i)= ln((k/m)/\delta)/m,$ $(i=m)$
$\tau(i)= 0,$ $(i=m+1,\dots,k)$

$\tau(i)$의 정의는 논문보다는 $k/R$을 m으로 표기하는 위키피디아의 표기방법이 더 직관적인 것으로 생각되어 이를 따랐다. 논문에서 정의하는 $R$은 상수 $c$와 $\delta$에 의해 그 값이 결정되는데, 최종적으로는 자연수 m으로 표현되기 때문이다.

Graph

$$k = 10000, c = 0.2, \delta = 0.05 ( S = 244, M = 41, Z = 1.31 )$$


CDF / PDF

Probability Distribution Function Probability Mass Function Discrete variable
Probability Density Function Continuous variable
Cumulative Distribution Function PMF의 누적합 또는 PDF의 적분

먼저 CDF의 정의를 찾아보자. A real-valued random variable X 대한 함수의 정의는, $$F(x) = P(X\leq x)$$ 이 때, P는 임의의 실수 X가 x보다 작거나 같을 확률이다. Continuous random variables 에서는 PDF(Probability Density Function)에 대한 적분이고, $$F(x)=\int_{-\infty}^x f(t)dt$$ Discrete random variables 에서는 PMF(Probability Mass Function)에 대한 누적합이다. $$F(x)=\sum\limits_{t \leq x} f(t)$$