Differences

This shows you the differences between two versions of the page.

--- notes:soliton [2018/12/01] – gomida
+++ notes:soliton [2022/11/17] (current) – removed gomida
@@ Line 1: / Line 1: @@
-====== 솔리톤 분포 ======
-===== Soliton Distribution =====
-<sq>
-==== 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,...,k)$ |
-\\
-\\
-=== Graph ===
-<HTML><div style="max-width:552px;margin:0 auto;text-align:center;"></HTML>
-{{:notes:soliton_distribution_k10.png?nolink}}
-$$k = 10$$
-<HTML></div></HTML>
-Soliton Distribution의 특징은 Degree 1과 2 사이에서 볼 수 있는 물결(ripple)에 있다. Degree 2 이후로는 함수의 정의에 따라 $1/i(i-1)$을 따라 줄어가는 형태를 가지지만, Degree 1은 일정수준 확보되는 것을 관찰할 수 있다.
-\\
-\\
-<HTML><div style="max-width:552px;margin:0 auto;text-align:center;"></HTML>
-{{:notes:soliton_distribution.png?nolink}}
-$$k = 10000$$
-<HTML></div></HTML>
-하지만 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 ===
-[[https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/Luby02.pdf|M. Luby "LT-codes," in Proc. 43rd Annu. IEEE Symp. Foundations of Computer Science (FOCS), Vancouver, BC, Canada, Nov. 2002, pp. 271–280.]]
-</sq>
-<sq>
-==== Math Symbols ====
-| $P$ | $\rho$ | rho |
-| $T$ | $\tau$ | tau |
-| $M$ | $\mu$ | mu |
-| $D$ | $\delta$ | delta |
-</sq>
-<sq>
-==== 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 ===
-<HTML><div style="max-width:552px;margin:0 auto;text-align:center;"></HTML>
-{{:notes:robust_soliton_distribution.png?nolink}}
-$$k = 10000, c = 0.2, \delta = 0.05 ( S = 244, M = 41, Z = 1.31 )$$
-<HTML></div></HTML>
-\\
-</sq>
-<sq>
-==== 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)$$
-</sq>

Differences

TypeError: Cannot access offset of type string on string