估计$C_{m}^k$的值：Chernoff bound

对独立同分布的随机变量$X_{0},X_{1},X_{2},\dots X_{n}$ Bernoulli distribution: $E(X) = p,0\leq x\leq 1$

$$P\left( \frac{1}{m} \sum_{i=1}^m X_{i} - p \geq \epsilon \right) \leq e^{-mD_{B}(p+\epsilon\mid\mid p)}\leq e^{-2m\epsilon^2}$$

其中

$$D_{B}(p+\epsilon\mid\mid p) = (p+\epsilon) \ln \frac{p+\epsilon}{p} + (1-p-\epsilon) \ln \frac{1-p-\epsilon}{1-p}$$

对于长为n的编码，为了使$d(c_{i},c_{j})\geq \frac{m}{4}$，需要m维的空间（长为m编码）得到最小的$m=f(n)$。可以证明$m=O(n)$.

Basic Definition

A code $C$ of a block length $n$, message length $k$ and distance $d$ over an alphabet $\Sigma$ is called a $(n,k,d)|_{\Sigma}$ code.

Rate of a code $C \subseteq \Sigma^n$ is defined as $R= \frac{{\log_{\mid \Sigma\mid} |C|}}{n}=\frac{k}{n}$。It shows the speed of information transmission.

Distance between two linear codes is the number of positions at which the corresponding symbols are different.

Hamming ball in $\sum^n$ of radius $e$ about $x \in \sum^n$ is defined as

$$B_{\Sigma^n} (x,e) = \left\{y\in \Sigma^n :\delta(x,y)\leq e\right\}$$

As in the code space, the volumn of Hamming ball is denoted as

$$Vol_{q}(e,n) = 1+C_{n}^1 (q-1)+C_{n}^2 (q-1)^2+\dots+C_{n}^e(q-1)^e$$

Our main purpose is to find out the erasures or errors during codes' transmission. Generally, a code with distance $d$ can :

1. correct $\leq d-1$ erasures
2. detect $\leq d-1$ errors
3. correct $\lfloor \frac{d-1}{2}\rfloor$ errors

Hamming Bound, GV Bound

They all show the trade-off between rate and distance. Briefly, Hamming Bound is the upper bound on the rate of a code (an impossibility result), and GV bound shows the lower bound of the rate (a possibility result).

$$1 - \frac{\log(Vol_{q}(d-1,n))}{n} \leq \text{optimal}\left( \frac{k}{n} \right)\leq 1-\frac{\log_{q}\left( Vol_{q}\left( \lfloor \frac{d-1}{2}\rfloor,n \right) \right)}{n}$$

Gilvert-Vashamov Bound

使用长m的coding编码长n的符号的纠错码Error Correcting Codes (ECC)：$\{0,1\}^n\to\{0,1\}^m\ for\ \forall\ 0<\delta<\frac{1}{2}$
如果$m\geq \frac{2n}{1-H(\delta)}$那么存在codewords $C$使得码元之间距离总不小于$\delta m$,即$d_{H}(c_{i},c_{j})\geq\delta m$ for $\forall\ i\neq j$。其中$H(\delta)=-(\delta \ln\delta + (1-\delta)\ln(1-\delta))$

Proof:
IDEA: Probablisitc Method, if one randomly chooses objects from a specified class, the probablity that the result is of the prescribed kind is strictly greater than zero.

Let C be a random subspace of $F^q$ of dimension $k$ , and $G$ is a random generator matrix of $C$ (generator matrix is not unique). For any fixed $x\neq 0,G\cdot x$ is uniformly random in $F^q-\{0\}$
Then,
uniformly and independently draw $c_{1},\dots c_{2^n}$ For fixed $i,j,i\neq j$,

$$P(d_{H}(c_{i},c_{j})\leq\delta m) \leq \dots$$

那么

$$P(\exists i\neq j,d_{H}(c_{i},c_{j})\leq\delta m) \leq 2^{2m}\times P(d_{H}(c_{i},c_{j})\leq\delta m)<1$$

得证

Encoding & decoding is computationally efficient.

Hamming Codes

以3bit为例，构造$(3,7)$矩阵H,使得其从左到右每一列均为从1到7的二进制编码

$$H=\left[\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix}\right]$$

考虑H的Kernel space，$dim(Ker(H))=dim(H)-rank(H)=4$也就是空间中有4个独立向量。
从中任意取出两个不同的$x_{1},x_{2}$必然有$d_{H}(x_{1},x_{2})\geq 3$
可以得知$x_{1} \oplus x_{2}\neq 0$，而且$H(x_{1}\oplus x_{2})=0$.首先$d$不可能为1，否则需要H有一列全0；d也不可能为2，否则需要H有两列全相同；事实上d有可能为3.

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview