通信抗干扰编码—分组码概述

目录：

• 1 相关概念
• 2 线性分组码
• • 2.1 监督矩阵
  • 2.2 生成矩阵
  • 2.3 校正子
• 3 交织码
• 4 循环码
• • 4.1 循环码的表示
  • 4.2 循环码的生成多项式和生成矩阵
  • 4.3 循环码编码
• 5 截短循环码
• 6 BCH码
• 7 RS码

1 相关概念

• 分组码结构

    分组码包括信息码元和监督码元，通常表示为(n,k)，n是总位数，k是信息码元的位数，那么r=n-k就是监督码元的个数。例如：(7,4)就代表长度为7，其中包括4个信息位，3个监督位。

• 编码效率η及编码冗余度E

  η = k n \frac{k}{n} nk​

  E = n − k k \frac{n-k}{k} kn−k​

• 码重和码距

    码组中1的个数成为“码重”，不同码组之间对应位上码元不同的位数称为码距。例如：码组1：00110110，码组2：10011011，码组1的码重为4，码组2的码重为5，二者码距为5。对于某种编码方式而言，各个码组距离的最小值称为最小码距(dmin)，它直接决定着这种编码方式的检错和纠错能力。

2 线性分组码

  线性分组码就是信息码元和监督码元之间呈现线性关系的分组码。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种位置，则要求

2 r − 1 ≥ n 2^r-1≥n 2r−1≥n

2.1 监督矩阵

  监督矩阵是由监督方程关系式构成，每一行都是一个监督方程，每一个监督方程都是码组中其中一个监督码元和某些信息码元之间满足的关系式。例如 ( 7,4 ) 码有三个监督码元，那么对应的就是三个监督方程，方程中出现的码元对应矩阵元素为1，未出现的码元对应矩阵元素为0。

  假设某 ( 7,4 ) 码组A=[ a6 a5 a4 a3 a2 a1 a0 ]，其中a6 a5 a4 a3 为信息码元，a2 a1 a0为监督码元，满足以下关系：

{ a 6 ⊕ a 5 ⊕ a 4 ⊕ a 2 = 0 a 6 ⊕ a 5 ⊕ a 3 ⊕ a 1 = 0 a 6 ⊕ a 4 ⊕ a 3 ⊕ a 0 = 0 (2-1) \left\{\begin{matrix}a6⊕a5⊕a4⊕a2=0\\a6⊕a5⊕a3⊕a1=0\\a6⊕a4⊕a3⊕a0=0\end{matrix}\right. \tag{2-1} ⎩⎨⎧​a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0a6⊕a4⊕a3⊕a0=0​(2-1)

那么根据监督方程关系式可得到如下行元素，进而构成监督矩阵H：

{ 1110100 1101010 1011001 \left\{\begin{matrix}1110100\\1101010\\1011001\end{matrix}\right. ⎩⎨⎧​111010011010101011001​

  将监督方程组看成监督矩阵H和码组相乘，可满足以下线性代数关系：

[ 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 ] ⋅ [ a 6 a 5 a 4 a 3 a 2 a 1 a 0 ] = [ 0 0 0 ] \left[ \begin{matrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix} \right] · \left[ \begin{matrix} a_6\\ a_5\\ a_4\\ a_3\\ a_2\\ a_1\\ a_0\\ \end{matrix} \right]= \left[ \begin{matrix} 0\\ 0\\ 0\\ \end{matrix} \right] ⎣⎡​111​110​101​011​100​010​001​⎦⎤​⋅⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​a6​a5​a4​a3​a2​a1​a0​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎡​000​⎦⎤​

  可以简记为

H ⋅ A T = 0 T A ⋅ H T = 0 (2-2) H·A^T=0^T\tag{2-2}\\ A·H^T=0 H⋅AT=0TA⋅HT=0(2-2)

2.2 生成矩阵

   式（2-1）可以表示为：

{ a 2 = a 6 ⊕ a 5 ⊕ a 4 a 1 = a 6 ⊕ a 5 ⊕ a 3 a 0 = a 6 ⊕ a 4 ⊕ a 3 (2-3) \left\{\begin{matrix} a2=a6⊕a5⊕a4\\ a1=a6⊕a5⊕a3\\ a0=a6⊕a4⊕a3 \end{matrix}\right. \tag{2-3} ⎩⎨⎧​a2=a6⊕a5⊕a4a1=a6⊕a5⊕a3a0=a6⊕a4⊕a3​(2-3)

  将式（2-2）表示为矩阵形式：

[ a 2 a 1 a 0 ] = [ a 6 a 5 a 4 a 3 ] [ 111 110 101 011 ] = [ a 6 a 5 a 4 a 3 ] Q k × r \left[ \begin{matrix} a_2a_1a_0 \end{matrix}\right] = \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]\left[ \begin{matrix} 111\\ 110\\ 101\\ 011 \end{matrix} \right]= \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]Q_{k×r} [a2​a1​a0​​]=[a6​a5​a4​a3​​]⎣⎢⎢⎡​111110101011​⎦⎥⎥⎤​=[a6​a5​a4​a3​​]Qk×r​

  可见，只要已知信息码元，通过矩阵Q就可以得到监督码元。此外，信息码元通过与单位矩阵的运算仍然可以得到信息码元。那么与信息码元同维度的单位矩阵与Q可拼成矩阵G，即通过信息码元和矩阵G的运算可以得到整个码组，这样的矩阵G称为生成矩阵。

[ a 6 a 5 a 4 a 3 ] I k = [ a 6 a 5 a 4 a 3 ] \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]I_{k}= \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right] [a6​a5​a4​a3​​]Ik​=[a6​a5​a4​a3​​]

G k × r = [ I k Q k × r ] G_{k×r}=[I_{k}Q_{k×r}] Gk×r​=[Ik​Qk×r​]

2.3 校正子

  假设接收端接收到的码组B，由式（2-2）可知以下关系。当S=0，无错码，当S≠0，有错码，此时S为校正子，可根据校正子不为0的位指示误码的码元。

B ⋅ H T = S B·H^T=S B⋅HT=S

3 交织码

  交织码是应用于抗突发干扰的一种编码方式。交织分为三种：随机交织、矩阵交织(块交织)、卷积交织。

  随机交织，利用PN码进行随机排序，使得数据具有随机性，这一特征导致在传输过程中，不仅要传输数据序列，还要附带对应交织器的信息，多用于保密信道和扩频。

  矩阵交织，按行读入按列输出，或者按列读入按行输出。

  卷积交织，通过特定结构的卷积交织器，解交织则与交织器结构相反。

  举一种交织的例子：交织码将已编码的码字(例如(n,k)分组码)按行读入，即每一行都是一个许用码组，一共有n列，这样将会构成一个矩阵，经过交织后，矩阵转置，然后传输，最后按列读取，即再次进行转置。若某一个码组在传输过程中成串发生p比特错误，那么经过转置后，这些原本位于某一行的p个误码将会变为某一列的p个元素，即有p行发生了1比特错误。如此看来，交织可以将成串的突发误码转化为随机误码。因此，只要错误的数目在码组的差错控制范围内便可实现检错和纠错。交织码的交织深度越大，离散度就越大，抗突发差错能力也越强。

4 循环码

4.1 循环码的表示

  循环码是一类具有循环性的线性分组码。循环性是指任意码组循环移位后，仍然为该码的一个许用码组。循环码也可以用多项式表示。

A ( x ) = a n − 1 x n − 1 + a n − 2 x n − 2 + . . . + a 1 x + a 0 A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{1}x+a_0 A(x)=an−1​xn−1+an−2​xn−2+...+a1​x+a0​

  若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，那么F(x)等价于R(x)即：

F ( X ) N ( X ) = Q ( x ) + R ( x ) N ( x ) \frac{F(X)}{N(X)}=Q(x)+\frac{R(x)}{N(x)} N(X)F(X)​=Q(x)+N(x)R(x)​

F ( x ) ≡ R ( x ) F(x)≡R(x) F(x)≡R(x)

  在循环码中，设A(x)是一个长度为n的码组，若

x i ⋅ A ( x ) ≡ A ′ ( x ) （ 模 ( x n + 1 ) ） x^i·A(x)≡A'(x) （模(x^n+1)） xi⋅A(x)≡A′(x)（模(xn+1)）

  则 A ′ ( x ) A'(x) A′(x)也是一个许用码组。例如：一循环码是1001011，即

A ( x ) = x 6 + x 3 + x + 1 A(x)=x^6+x^3+x+1 A(x)=x6+x3+x+1

  若给定i=3，那么

x 3 ⋅ A ( x ) = x 9 + x 6 + x 4 + x 3 ≡ x 6 + x 4 + x 3 + x 2 （ 模 x 7 + 1 ） x^3·A(x)=x^9+x^6+x^4+x^3≡x^6+x^4+x^3+x^2（模x^7+1） x3⋅A(x)=x9+x6+x4+x3≡x6+x4+x3+x2（模x7+1）

  由多项式，移位后的循环码为1011100，正好是1001011左移三位后的结果。因此，长度为n的循环码必定为模( x n + 1 x^n+1 xn+1)的一个余式。

4.2 循环码的生成多项式和生成矩阵

  在2.2节中，我们提到了生成矩阵，通过信息码和生成矩阵可以得到整个码组，而生成矩阵的每一行都是一个许用码组，由循环码特点，循环码组通过移位可以互相转化，那么循环码的生成矩阵G可以表示为

G ( x ) = [ x k − 1 g ( x ) x k − 2 g ( x ) ︙ x g ( x ) g ( x ) ] G(x)=\left[ \begin{matrix} x^{k-1}g(x)\\ x^{k-2}g(x)\\ ︙\\ xg(x)\\ g(x) \end{matrix} \right] G(x)=⎣⎢⎢⎢⎢⎡​xk−1g(x)xk−2g(x)︙xg(x)g(x)​⎦⎥⎥⎥⎥⎤​

  这里的生成多项式g(x)需要满足常数项为1，且是（ x n x^n xn+1）的n-k次因子。

4.3 循环码编码

  分为如下5个步骤：

1. 首先根据给定的(n,k)值选定生成多项式g(x)，即从 x n x^n xn+1的因式分解中选一个常数项为1的(n-k)次多项式作为g(x)
2. 将信息码表示为多项式m(x)，其幂次小于k。
3. 用 x n − k x^{n-k} xn−k乘m(x)，得到的 x n − k x^{n-k} xn−km(x)的幂次必定小于n。
4. 用g(x)除 x n − k x^{n-k} xn−km(x)，得到余式r(x)，r(x)的幂次必定小于g(x)的幂次，即小于(n-k)。
5. 将此余式r(x)加于信息位之后作为监督位，即将r(x)和 x n − k x^{n-k} xn−km(x)相加，得到的多项式即为码多项式，即编出的码组A(x)为：A(x)= x n − k x^{n-k} xn−km(x)+r(x)。

5 截短循环码

  假设循环码(n,k)，共有2k个许用码组，现使前i(0＜i＜k)位信息位全为"0"，于是它变成仅有2{k-i}个许用码组。然后删去这i位全"0"的信息位，最终得到一个(n-i,k-i)的线性码，将这种码称为截短循环码，它与原循环码具有相同的纠错能力，并且编解码方法仍和截短前一样。

6 BCH码

  BCH码可以纠正多个错码，也属于循环码，因此也可以由循环码的生成方式生成，只需要确定g(x)即可，而g(x)根据n、k和纠错个数t查表得到。即先查g(x)，然后产生生成矩阵G，用信息码乘G得到BCH编码。

7 RS码

  假如BCH码的码元不用二进制的"0"和"1"表示，而取多进制的一个元素，如BCH的每个码元用 2 m 2^m 2m进制中的一个m位的二进制码组表示，则这种多进制BCH码就是RS码。例如对于信息位为10101010101的本原(15,11)码，其码序列为10101010101011。如果进行RS编码，取m=2，即每一位将用一个2比特的二进制码表示(“01"表示"0”，“10"表示"1”)，那么输出的RS码就是1001100110011001100110011010。由此可见，当以2b为一组计算时，一旦出现"00"或者"11"或不符合循环码的循环关系时，表示序列传输出现差错。因此，RS码是一类具有很强纠错能力的多进制BCH码。

  当然，RS编码原理并不仅仅是像上述说得轻松，还涉及到伽罗华域的相关概念，在后期学习中，会更一篇RS码编解码原理的博文。