## Algebraic Coding Thoery

2019-01-18 08:00 CST
2019-12-22 15:33 CST
CC BY-NC 4.0

# 代数编码

• maximum-likelihood decoding: $e$ has the least weight
• binary symmetric channel
• $X\sim B(n,p)$
• Block codes
• $(n,m)$-block code
• $[n,m,d]$-code
• encoding function: $E:\mathbb{Z}_2^m\rightarrow\mathbb{Z}_2^n$
• decoding function: $D:\mathbb{Z}_2^n\rightarrow\mathbb{Z}_2^m$
• codeword: element in image of $E$ ($n$)
• Hamming distance: $d(x,y)$
• weight: $w(x)=d(x,0)$
• $w(x+y)=d(x,y)$
• correcting: $t=[\frac{d_{\min}-1}{2}]$
• detecting：$e=d_{\min}-1$
• combined：$d_{\min}\geq t+e+1,(e>t)$
• 冗余度：$\frac{n-m}{m}$
• 编码率：$\frac{m}{n}$
• Group code: code that is also a subgroup of $\mathbb{Z}_2^n$
• $d_{\min}=\min{w(x):x\not=0}$
• Linear code: A linear code $C$ of length n is a linear subspace of the vector space $\mathbb{Z}_2^n$
• $\text{Null}(H), H \in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$
• $C=\text{Null}(H)$ is a group code
• $\text{Col}(G_{n\times k})=\text{Null}(H_{(n-k)\times n})$
• $Gx=y\iff Hy=0$
• 循环码：线性码满足任一码字左移或右移一位后，得到的仍然是该码的一个码字
• 码多项式：把码组中各码元作为多项式系数 $T(x)=\sum_{i=0}^{n-1}a_{i}x^i$
• (n,m) 循环码每个码字在以 $x^n+1$ 为模运算的剩余类中某一类
• 生成多项式 $g(x)$
• 常数项为 $1$ 的 $r=n-m$ 次多项式
• $x^n+1$ 的因式
• 其它码多项式为其倍式
• 不唯一

## Parity-Check

• canonical parity check matrix: $H=(A|I_m),A_{m\times(n-m)}$
• $H$ give rise to an $(n,n-m)$-block code
• standard generator matrix: $G_{n\times(n-m)}=(\frac{I_{n-m}}{A})$
• $HG=0$
• $d(C)$ equals the minimum number of linearly dependent columns of $H$
• $\text{Null}(H)$ is a single error-detecting code if and only if no column of $H$ consists entirely of zeros
• $\text{Null}(H)$ is a single error-correcting code if and only if $H$ does not contain any zero columns and no two columns of $H$ are identical
• Syndrone Decoding
• syndrone of $x$: $Hx$
• $x=c+e,Hx=He$
• if the syndrome of $r$ is equal to some column of $H$, say the ith column, then the error has occurred in the ith bit
• Coset Decoding (Standard Decoding)
• $(n,m)$-linear code has $2^{n-m}$ cosets
• coset leader: an n-tuple of least weight in a coset
• $x$ and $y$ are in the same coset $\iff Hx=Hy$
• Correcting one error: $[2^r − 1, 2^r − r − 1, 3]_2$-code
• Detecting one error: $[r+1, r, 2]_2$-code

## 卷积码

• 卷积码 $(n,k,N)$
• 将当前 $k$ 比特信息编码为 $n$ 个比特
• 前 $m=(N-1)$ 信息段
• 解码
• 代数解码：大数逻辑解码
• 概率解码：维特比解码
• 将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送信号序列
• 最大似然
• 动态规划