【现代通信原理笔记】7 差错控制编码（信道编码）

重点

部分内容结合计算机网络原理

可靠性增加，有效性减小

要将质量要求与误码率两者匹配起来

误码

应根据信道类型、对实时性和误码率的要求等因素来选择。

信道类型 — 根据错码的不同分布规律分为：

差错控制方式：

技术措施：

停止等待 ARQ 系统

拉后 ARQ 系统​

参考计网

编码器 对输入的信码进行分组编码（加入校验元）后发送。若收到接收端的重发(NAK)指令，执行重发。

译码器 对接收码校验，若发现有错，则通过反向信道发送一个 重发(NAK)指令，指示发送端重发。若无错，则发送确认(ACK) 指令，指示发送端正常发送。

ARQ 的主要优点：与前向纠错 (FEC) 方法相比

ARQ 的主要缺点：

校验（监督）码元：发送端在信息码元序列中增加一些差错控制码元，以便收端判断正误，它们被称为校验码元。校验码元位数不同，检错或纠错能力就不同。

编码效率（简称码率）：设编码序列中信息码元数量为 k，总码元数量为 n ( n > k ) n(n>k) n(n>k) ，则比值 R = k / n R=k/n R=k/n 就是码率。校验码元数 r = n − k r=n-k r=n−k。

差错控制编码表面上降低有效性，换取更低误码率，提高可靠性。但信息速率可能更接近信道容量

分组码：把一个长数据文件分成若干个长度相等的信息码组，在每个码组后加上校验码。与分组码并称的另一种码是卷积码。

系统码：信息位保持不变，在其后加上校验位的纠错码

非系统码：编码码组中无对应信息位（信息位和校验位交叉）

许用码组

禁用码组：接收端一旦收到禁用码组，就认为出现了错码。

校验码元：系统码的校验码元冗余

码长 ( n n n)：码组（码字）中的码元个数。

码重 ( W W W)：码组 a a a 中“1”的数目， w ( a ) w(a) w(a)。

码距 ( d d d)： 两个码组 a、b 对应位上不同值的个数，称为码组 的距离 d ( a , b ) = w ( a + b ) d(a, b) = w(a+b) d(a,b)=w(a+b)。—又称汉明距离。（“+”按位模 2 加）

最小码距 ( d 0 d_0 d0​)：某种编码各个码组之间距离的最小值

最小码距 d 0 d_0 d0​ 和检纠错能力的关系（可以画图方便理解）

“1”的数目与“0”的数目之比保持恒定。

每个码组的校验位数等于信息位数，校验位值由信息码中的“1” 的数目确定：

该码能够严格地纠正任意 1 位错码，码率为 1/2。

计网内容

反码、求和、0

符号表示：一种码若码长是 n，其中信息码有 k 位，称为 ( n , k ) (n, k) (n,k) 码，如 (7, 4) 码。以下以 (7, 4) 码为例。

信息码向量 m ⃗ = ( m 3 , m 2 , m 1 , m 0 ) \vec{m} = (m_3,m_2,m_1,m_0) m =(m3​,m2​,m1​,m0​)

发送码向量 A ⃗ = ( a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ) \vec{A} = (a_6,a_5,a_4,a_3,a_2,a_1,a_0) A =(a6​,a5​,a4​,a3​,a2​,a1​,a0​)

接收码向量 B ⃗ = ( b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ) \vec{B} = (b_6,b_5,b_4,b_3,b_2,b_1,b_0) B =(b6​,b5​,b4​,b3​,b2​,b1​,b0​)

校正子：s

校验关系式：

若 s=0，认为无错（偶校验时）；若 s=1，认为有错 。—— 检错

若要构造具有纠错能力的 (n, k) 码，则需增加校验元的数目。 s (即方程)的个数等于校验元位数 r。

对于 (n, k) 线性分组码，若希望用 r=n-k 个校验码元构造出 r 个校验

关系式来指出一位错码的 n 种可能的位置，则 r 必须满足：

2 r − 1 ≥ n   或   2 r ≥ k + r + 1 2^r-1\geq n \ 或\ 2^r \geq k + r + 1 2r−1≥n 或 2r≥k+r+1

-1 是因为还有一种可能性没有错

当“=”成立时，构造的线性分组码称为汉明码——能纠 1 位错码高效线性分组码

( n , k ) = ( 2 r − 1 , 2 r − 1 − r ) (n,k) = (2^r-1,2^r-1-r) (n,k)=(2r−1,2r−1−r)

信息元和校验 (parity check)元是平等的

码参数：

式 2 r − 1 ≥ n 2^{r}-1 \geq n 2r−1≥n 中的等号成文. 即 ( n , k ) = ( 2 r − 1 , 2 r − 1 − r ) (n, k)=\left(2^{r}-1,2^{r}-1-r\right) \quad (n,k)=(2r−1,2r−1−r)，$ r$ 是不小于 3 的任意正整数

最小码距:

d 0 = 3  (纠1或检2)  d_{0}=3 \text { (纠1或检2) } d0​=3 (纠1或检2) 

编码效率:

R c = k n = n − r n = 1 − r 2 r − 1 R_{c}=\frac{k}{n}=\frac{n-r}{n}=1-\frac{r}{2^{r}-1} Rc​=nk​=nn−r​=1−2r−1r​

当 n n n 很大时, r r r 相对很小, 码率 R c R_{\mathrm{c}} Rc​ 接近 1 。

可见，汉明码是能够纠正 1 位错码的最高效线性分组码。

若矩阵由一个小矩阵和满秩的单位阵组合而成，则称它为典型矩阵。

H 的各行是线性无关的。否则得不到 r 个线性无关的校验关系式。

若一矩阵能写成典型阵形式 [ P I r ] [P\quad I_r] [PIr​]，则其各行一定是线性无关的。

将上面汉明码例子中的校验位计算公式： 改写成矩阵形式：

式中， Q Q Q 为一个 k × r k\times r k×r 阶矩阵，它是 P P P 的转置，即

Q = P T Q=P^\text{T} Q=PT

可见，给定信息位后用信息位行向量乘矩阵 Q Q Q 就产生校验位。

将 Q Q Q 的左边加上一个 k × k k\times k k×k 阶单位方阵，就构成矩阵:

具有 [ I k   Q ] [I_k \ Q] [Ik​ Q] 形式的 G G G 称为典型生成矩阵。由典型得 G G G 到的码称为系统码

系统码：信息位保持不变，在其后加上校验位的纠错码

G 矩阵的性质

① G 矩阵是 k × n k\times n k×n 矩阵。

② G 的各行是线性无关的；它的各行本身就是一个码组。

∴ 若有 k 个线性无关的码组，则可用其组成生成矩阵 G，生成其余码组。

可以看出：任一码组 A 都是 G 的各行的线性组合。G 共有 k 行，可以组合出 2 k 2^k 2k 种不同的码组 A。

G 和 H 的关系

非典型的 G 或 H 可以通过行线性变换变成典型的 G 、H ，仍然对应于该编码。可以由此进行 G 、H 互求。

则发送码组和接收码组之差就是错误图样

设发送码组为一个 n n n 元行向量 A A A, 接收码组行向量 B B B

A = [ a n − 1 a n − 2 ⋯ a 1 a 0 ] B = [ b n − 1 b n − 2 ⋯ b 1 b 0 ] \boldsymbol{A}=\left[\begin{array}{lll} a_{n-1} a_{n-2} & \cdots & a_{1} a_{0} \end{array}\right] \quad \boldsymbol{B}=\left[b_{n-1} b_{n-2} \cdots b_{1} b_{0}\right] A=[an−1​an−2​​⋯​a1​a0​​]B=[bn−1​bn−2​⋯b1​b0​]

则发送码组和接收码组之差就是错误图样:

B − A = E = [ e n − 1 e n − 2 ⋯ e 1 e 0 ] \boldsymbol{B}-\boldsymbol{A}=\boldsymbol{E}=\left[\begin{array}{ll} e_{n-1} e_{n-2} & \cdots e_{1} e_{0} \end{array}\right] B−A=E=[en−1​en−2​​⋯e1​e0​​]

式中：

e i = { 0 ,  当  b i = a i  表示该接收码元无错  1 ,  当  b i ≠ a i  表示该接收码元有错  e_{i}=\left\{\begin{array}{lll} \mathbf{0}, & \text { 当 } b_{i}=a_{i} & \text { 表示该接收码元无错 } \\ \mathbf{1}, & \text { 当 } b_{i} \neq a_{i} & \text { 表示该接收码元有错 } \end{array}\right. ei​={0,1,​ 当 bi​=ai​ 当 bi​​=ai​​ 表示该接收码元无错  表示该接收码元有错 ​

S S S 称为校正子（伴随式）。

校正子 S S S 与错误图样 E 一一对应，而与发送码 A 无关。

(n,k) 线性分组码译码的三个步骤：

注：若 B 中错误超过纠错能力，则也可能 S = H ⋅ B T = 0 S = H · B^T=0 S=H⋅BT=0。此种错误不可检。

一种线性码中任意两个许用码组 A 1 A_1 A1​ 和 A 2 A_2 A2​ 之和 ( A 1 + A 2 ) (A_1+A_2) (A1​+A2​) (按位模 2 加) 后的码组，仍为该码中的一个许用码组。

证明：若 A 1 A_1 A1​ 和 A 2 A_2 A2​ 是两个码组，则有 H ⋅ A 1 T = 0 H \cdot A_1^\text{T} = 0 H⋅A1T​=0 和 H ⋅ A 2 T = 0 H\cdot A_2^\text{T} = 0 H⋅A2T​=0，

将两式相加，有 H ⋅ A 1 T + H ⋅ A 2 T = H ⋅ ( A 1 + A 2 ) T = 0 H \cdot A_1^\text{T} + H\cdot A_2^\text{T} = H\cdot(A_1+A_2)^\text{T}= 0 H⋅A1T​+H⋅A2T​=H⋅(A1​+A2​)T=0（证毕）

码的最小距离就是码的最小重量

证明：根据码的封闭性，可知两个码组 A 1 A_1 A1​ 和 A 2 A_2 A2​ 之间的距离(即对应位不同的数目)必定是另一个码组 A 1 + A 2 A_1 + A_2 A1​+A2​ 的重量(即“1”的数目)。

注：从生成矩阵 G 的最小行重量常常就能判断最小距离

具体内容略

循环性：指任一码组循环移位（将最左端的一个码元移至右端， 或反之），仍为该码中的一个码组；

循环码：除了具有线性分组码的一般性质外，还具有循环性

计网重点

接 受 的 码 字 g ( x ) = c ( x ) g ( x ) + e ( x ) g ( x ) \frac{接受的码字}{g(x)} = \frac{c(x)}{g(x)} + \frac{e(x)}{g(x)} g(x)接受的码字​=g(x)c(x)​+g(x)e(x)​

单个位差错

两个独立的单个位差错

奇数个差错

突发性差错 （ L L L：差错长度； r r r：校验位数）

高性能生成多项式 g ( x ) g(x) g(x) 需要有以下特性：

（模二运算？）