信息论与编码 第六章信道编码

在接收端错误地确定所接收的信号叫做差错。在通信系统中需要采用专门的检、纠错误方法,即差错控制

信道编码是以信息在信道上的正确传输为目标的编码,可分为两个层次: - 如何正确收载有信息的信号:通信原理、线路编码; - 如何避免少量差错信号对信息内容的影响:信息论、差错控制编码。

差错控制的任务是发现所产生的错误、并支出发生错误信号或者校正错误,差错控制是采用可靠、有效的i信道编码方法来实现的。

6. 1 信道编码的概念

进行信道编码是为了提高信号传输的可靠性,改善通信系统的传输质量。从原理上看,构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(监督码),以引入最小的多余度为代价来换取最好的抗干扰性能。

6.1.1 信道编码的分类

信号差错——差错符号——误码元率;信息差错——差错比特——误比特率。

二进制传输系统,符号差错等于比特差错。

实际信道:

  • 独立随机差错:差错始终等概率独立发生于各码字、各码元、各比特。(BSC、离散无记忆)
  • 突发性差错:差错前后相关,成堆出现。(双状态一阶马尔可夫链)
  • 混合差错:移动信道属于此类

按照信道特性分类:以纠独立随机差错为主、以纠突发差错为主、纠混合差错。

按功能划分:检错码(发现错误)、纠错码(发现和自动纠正)。

按信息码元与监督码元之间的关系:线性码、非线性码。

  • 线性码:信息码元与监督码之间呈线性关系。

  • 非线性码:信息码元与监督码之间不呈线性关系。

按对信息码元处理方法:分组码、卷积码

  • 分组码:信息序列以每 k 各码元分组,每组按一定规律产生 r 个多余的监督码元,输出序列长度为 n(=k+r),每一码字的 r 个校验元只与本码字的 k 个信息位有关,记作 (n, k)。
    • 循环码:全部码字分成若干组,每组码字中码元循环移位后仍然是这组的码字。
    • 非循环码:每组码字中码元循环移位后不是这组的码字。
  • 卷积码:信息序列以每 k0(通常较小)各码元分组,每组按一定规律产生 r 个多余的监督码元,输出序列长度为 n(=k0+r),每一码字的 r 个校验元不仅与本码字的 k 个信息位有关,还与前面 L 段信息码元有关,记作 (n, k, L)。

按码元的取值:二元码和多元码。

判决与译码准则

对简化的通信系统模型,但符号判决规则为:\(g(y=b_j)=a^* \ \ j=1,…,s,a \in A​\)。意思是:当收到 bj 就判定发送符号为 a^*^。称 g(y) 为判决函数

条件错误率定义为:\(p(e|x=a_i)=\sum_{y,g(y)\ne a_i}p(y|x=a_i)\)

平均错误率定义为:\(P_E =\sum p(x=a_i)p(e|x=a_i)=\sum_x p(x) \sum_{y,g(y)\ne a_i}p(y|x=a_i)=1-\sum_y p(x^*y)​\)

平均正确率为:\(\overline{P_E}=1-P_E=\sum_y p(x^*y)​\)

译码错误概率

误码率:传输码元出错概率;

误字率:码字出错概率。

条件错误率:\(P(g(y)\ne i|x=c_i)​\)

平均错误率:\(P_E=\sum _{i,y}p(c_i)P(g(y)\ne i|x=c_i)\)

最佳判决与译码准则
  1. 最大后验概率(MAP)准则

    平均正确率:\(\sum_y p(x^*y)=\sum_y p(y)p(x^*|y)≤\sum_y max_x p(x|y)​\)

    为使正确率最大,应使每一个输出 y 都选择对应后验概率最大的 x。

    MAP 准则:对给定的信道输出将具有最大后验概率的输入符号作为判决结果。

    \(g(y)=arg \ max_x p(x|y)​\)

    \(\Lambda=\frac{p(y|x=a^*)}{p(y|x=a_i)}≥\frac{p(x=a_i)}{p(x=a^*)}​\),为似然比。

    MAP 准则是使平均错误率最小的准则,可归结为似然比检验。

    由转移概率矩阵每行分别乘 p(x),的到联合概率矩阵;对每一列找一个最大的概率对应的 x 作为判决结果,所有判决结果对应的联合概率的和作为正确概率,其他矩阵元素的和作为错误概率。

  2. 最大似然(ML)准则

    当输入符号概或先验概率未知时,采用此准则。输入符号等概时,ML 等价于 MAP。

    对所有 i,当 \(p(y|x=a^*)≥p(y|x=a_i)\),则选择判决函数为 g(y)=a*,称为 ML 准则,可以简写为:\(g(y)=arg \ max_x p(y|x)\)

    对转移概率矩阵中每列选择最大的一个元素对应的 x 作为判决结果,所有信道输出和所对应判决结果的联合概率之和作为平均正确率,其他的联合概率之和为平均错误率。

6.1.2 与纠错编码有关的基本概念

  1. 码长、码重和码距

    码长:码字中码元的个数称为码字的长度,用 n 表示。

    码重(汉明重量):码字中非 “0” 元的个数,用 W 表示,\(W(\overline C)=\sum_{i=1}^nc_i \ \ c_i \in[0,1]\)

    码距(汉明距离):两个等长码字中间对应码元不相同的数目,\(D =\sum_{i=1}^n x_i \oplus y_i\)

    最小码距:某一码书 C 中,任意两个码字之间汉明距离的最小值,dmin

    最小码距代表着一个码组中最不利的情况,所以最小码距是衡量该码纠错能力的依据。

  2. 错误图样

    二元无记忆 N 次扩展信道中,差错的形式也可以用二元序列来描述。设发送码字为 \(\vec C=(c_n…c_2c_1)\),接受码字为 \(\vec R=(r_n…r_2r_1)\),两者的差别 \(\vec E=(e_n…e_2e_1)=\vec C \oplus \vec R\),称为错误图样。错误图样第 i 位为 1,则表明第 i 位发生了错误。

  3. 重复码和奇偶校验码

    • 重复码(可靠性高、有效性低)

      当发送某个信源符号 ai 时,不是只发一个,而是连续重发多个。重发个数越多,重复吗的抗干扰能力越强,当然效率越低。

      • 不重复时,是(1,1)重复码

        不重复,无抗干扰能力,不能发现、纠正错误。

      • 重复一次时,是(2,1)重复码

        重复一次,效率降低一倍。允许产生一个错误,但不能纠正。

      • 重复一次时,是(3,1)重复码

        用 000 表示信息 0,用 111 表示信息 1。认为接收到 001、010、100 判定传输 000;其他判定 111。因此多余码元使我们可以检出一个错并纠正。

        重发两次,效率降低两倍,可纠正一个差错或发现两个差错的性能改善。

    • 奇偶校验码(可靠性低、有效性高)

      在每 k 个二进制信息位最后加上一个奇(偶)监督位(或校验位),使码长 k+1 的码字中 1 的个数恒为奇数或0偶数。

      • 奇校验:若信息码元中 1 的个数为奇数个,则校验码元值为 0;反之为 1,即所有信息码元与校验码元的模二和等于 1。

      • 偶校验:若信息码元中 1 的个数为偶数个,则校验码元值为 0;反之为 1,即所有信息码元与校验码元的模二和等于 0。

        例如,偶校验的编码规则为:\(c_0=c_k\oplus c_{k-1}\oplus …\oplus c_1=\sum_{i=1}^k c_i\)

      奇偶校验只能检测出 n 位代码中出现的任意奇数个错误。适用于信道干扰不太严重、码长不太长的情况。

      奇偶校验码在一维空间上,有水平奇偶校验码和垂直奇偶校验,二维上有水平垂直奇偶校验。

      • 垂直奇偶校验

        将整个发送的信号划分成长度为 k 的若干组,再对每组进行奇偶校验编码。下图将 70 个码元分成长度为 7 的 10 个组,每组一列,然后每列进行偶校验。

        编码效率:\(\eta=\frac k{k+1}​\),边发送边产生校验位。能够检出每个分组中所有奇数位的错。漏检率接近于 1/2。

      • 水平奇偶校验

        将整个发送的信号划分成长度为 k 的 p 个组,再对水平方向进行奇偶校验编码。下图将 70 个码元分成长度为 7 的 10 个组,每组一列,然后每行进行偶校验。

        编码效率:\(\eta=\frac p{p+1}\),边发送边产生校验位。能够检出每个分组中所有奇数位的错,还能检测出突发长度小于或等于 k 的所有突发性错误。水平奇偶校验的漏检率比垂奇偶校验要低。必须全部数据信号全部到齐,才能够确定校验位。

      • 水平垂直奇偶校验

        同时进行水平奇偶校验和垂直奇偶校验就构成二维的“水平垂直奇偶校验码”。将整个发送的信号划分成长度为 k 的 p 个组,先对每组进行奇偶校验编码,再对水平方向进行奇偶校验编码。下图将 70 个码元分成长度为 7 的 10 个组,每组一列,然后列行进行偶校验。

        编码效率:\(\eta=\frac {kp}{(k+1)(p+1)}\),这种方法能够检测出所有 3 位或 3 位以下的错误。能检测出奇数位错、突发长度小于或等于 k+1 的突发性错以及很大一部分偶数位错。可将误码率降至原始误码率的百分之一到万分之一。不仅检错还可纠部分错(某行和某列都不满足监督关系。修改对应交叉处即可)。

6.1.3 检错与纠错原理

检错常用方法,在发送端要传送的信息序列中截取长度相等(k)的码元进行分组,组成 k 位码元信息序列 \(\vec M\),并根据某种编码算法在每个信息组后面产生 r 个冗余码元,得到 n=k+r 位编码序列,即:

r 个冗余编码与原信息码元中建立某种对应关系,称之为校验关系。译码就是利用检验关系进行检错、纠错的。

将信息码元分组,为每组码附加若干校验码的编码称为分组码。分组码中,校验码元仅校验本码组中的信息码元。

分组码一般用符号(n,k)表示,其中 k 是每组二进制信息码元的数目,n 是码长,r=n-k 是每码组中的校验码元。

实现检纠错的基本方法除了 n 重复码和奇偶校验方法外,还有等重码(或定比码)方法:

  • 奇偶校验方法:增加就奇偶校验位使得对消息序列的校验方程成立,当校验位数增加时,可检测到的差错图样种类数页增加,但同时码率减小。
  • n 重复码方法。重复消息位可以检测出任意小于 n 个差错的错误图样。
  • 等重码方法。涉及码字中非 “0” 符号个数为常数,使码书由全体重量恒等的长矢量组成。

纠错码的抗干扰能力完全取决于码数 C 中许用码字间的距离。码距越小,最小差别越大,抗干扰能力越强。即差错控制编码是用增加码元数,利用“冗余”来提高抗干扰能力的,削弱了有效性。

6.1.4 检错和纠错方式和能力

  1. 检错与纠错方式

    • 自动请求重发方式(ARQ)

      发送端进行差错编码,接收端只检测有无差错,不纠正。同时反馈错误,请求重发。降低传输系统的有效信息速率,对突发错误特别有效。主要用于复杂信道及要求误码率极低的场合。

    • 前向纠错方式(FEC)

      发送端进行差错编码,接收端检测有无差错,有差错自动纠正。实时性好。在单工通信系统中应用多。

    • 混合纠错(HEC)

      混合前两种。接收端对少量差错自动前向纠正,超出纠正额能力的请求重发。缺点需要反向信道和复杂的译码设备。卫星通信系统常用。

  1. 检错和纠错能力

    常用汉明距离来描述这一特性(检、纠错的数目)。一个纠错码的每个码字都可以形成一个汉明球。因此,要能够纠正所有不多于 t 位的差错,纠错码的所有汉明球均应不相交,判定纠错码的检、纠错能力可根据任意两个汉明球不相交,由码的最小距离 dmin 来决定。

    通常用 \(\eta=k/n\) 来表示码字中信息码元所占的比例,称为编码效率,简称码率。码率和纠错能力之间是有矛盾的。

6.2 线性分组码

6.2.1 线性分组码的基本概念

对信源编码器输出的 D 进制序列进行分组,设分组长度为 k,相应的码字表示为 \(\vec M=(m_k,…,m_2,m_1)​\)。其中,每个码字 m_i(1≤i≤k)都是 D 进制的,显然这样的码字共有 Dk个。信道编码使其称为以下形式: \(\vec C=(c_k…c_2c_1)​\)。其中,n > k,ci(1≤i≤n)为 D 进制数,显然这样的码字共有 DN 个。称全体码字 \(\vec C​\) 的集合为 D 元分组码。若之间是线性变化,则称全体码字 \(\vec C​\) 的集合为 D 元线性分组码,通常用 (n,k) 表示。

一个(n,k)线性分组码中非零码字的最小重量等于该码的最小距离 dmin

6.2.2 生成矩阵和一致校验矩阵

  1. 生成矩阵

    若信息组以不变的形式,在码字的任意 k 位中出现,则该码称为系统码。否则,称为非系统码。常用两种系统码:把信息组排在码字最左边或最有边 k 位。

    能够产生系统码的生成矩阵为典型矩阵(标准阵)。

  2. 一致校验矩阵

    \(C = [I_k:P]\)\(H=[P^T:I_r]\)

  3. 线性分组码的编码

  4. 对偶码和缩短码

    把 (n,k) 码的一致校验矩阵看作 (n,r) 码的生成矩阵,把 (n,k) 码的生成矩阵看作 (n,r) 码的一致校验矩阵,则称这两种码互为对偶码。

    某些情况下,如果对某一给定长度的信息码元找不到合适码长的码,则可将某一 (n,k) 码缩短以满足要求,这种就是缩短码。

    (n-i,k-i) 码的生成矩阵式将 (n,k) 码的生成和矩阵去掉前 i 行和前 i 列即可,而 H 矩阵只要去掉前 i 列即可。

    对偶码和缩短码对纠错能力不受影响,即它们与原码的纠错性能相同。

6.2.3 线性分组码的译码

发送码字为 \(\vec C=(c_nc_{n-1}…c_1)​\),信道产生的错误图样为 \(\vec E=(e_ne_{n-1}…e_1)​\),接收序列为 \(\vec R=(r_nr_{n-1}…r_1)​\),那么 \(\vec R = \vec C+\vec E​\),译码就是由 \(\vec R​\)\(\vec E​\)。若 \(\vec RH^T=\vec EH^T=\vec 0​\),那么接收序列满足校验关系,可以认为它是一个码字,反之,则认为其有错。

定义 \(\vec S=\vec RH^T=\vec EH^T\) 为接收序列 \(\vec R\) 的伴随式或校正子。其为全 0,则无错,反之有错。

注:若错误图样本身就是一个码字,那么计算伴随式得到的结果必然为 0,此时错误不能被发现和纠正。称为不可检错误图样。

6.2.4 线性分组码的纠错能力

(n,k) 线性分组码最小码距等于 dmin 的充要条件是 H 矩阵中任何 dmin-1 列线性无关。

  • 为了构造最小距离 dmin≥e+1(可检测 ≤e 个错误)或 dmin≥2t+1(可检测 ≤t 个错误)的线性分组码,其充要条件是要求 H 矩阵中任意 dmin-1 列线性无关。

    例如:构造 dmin=3 的码,要求 H 任意两列线性无关。对于二元码,H 矩阵无相同列和无全 0 列,就可以纠正所有单个错。

  • 交换 H 矩阵各列不会影响码的最小距离。因此所有列相同但排列不同的 H 矩阵所对应的分组码,其纠错能力等价。

  • 任一线性分组码的最小距离(最小重量) dmin 均满足 dmin≤n-k+1。

满足 dmin=n-k+1 的线性分组码称为极大最小距离码。同样 n,k 之下,dmin 最小,纠错能力更强。

若 C 是 (n,k) 二元码,已知 k 时,要使 C 能纠正 t 个错误,则必须有不少于 r 个校验位,并且使 r 满足:\(2^r-1≥\sum_{i=1}^tC_n^i​\),称为汉明不等式。

满足 \(2^r-1=\sum_{i=1}^tC_n^i\) 的码称为完备码

6.2.5 汉明码

对任意正整数 m≥3,存在具有下列参数的二进制汉明码:

  • 码长 n = 2m - 1
  • 信息位数 k = 2m - m - 1
  • 监督位数 r = n - k = m
  • 最小码距 dmin = 3

6.3 循环码

若 C 是 (n,k) 线性分组码,若它的任意一个码字的每一次循环移位后仍然是 C 中的一个码字,则称 C 为循环码。

优点:编码和译码易于用简单的具有反馈连接的移位寄存器来实现。

6.3.1 循环码的多项式描述

设有循环码字 \(\vec C=(c_nc_{n-1}…c_1)​\),则可以用一个次数不超过 n-1 的多项式唯一去确定,其相应的多项式可表示为:\(C(x)=c_nx^{n-1}+…+c_2x+c_1​\)

由循环码特性,若 \(\vec C=(c_nc_{n-1}…c_1)​\) 是循环码 C 的一个码字,则 \(\vec C=(c_{n-1}…c_1c_n)​\) 也是该循环码的一个码字,它的码多项式为:\(C^{(1)}(x)=c_{n-1}x^{n-1}+…+c_1x+c_n​\)

码字循环 i 次的码多项式 \(C^{(1)}(x)\) 是原码多项式 C(x) 乘 xi 后再除以 xn+1 所得的余式。

6.3.2 循环码的生成矩阵

在 (n,k) 循环码中,每一个能整除 xn+1 的 (n-k) 次首一多项式(其最高此项系数为 1)都是该码的生成多项式,记 g(x)。则生成矩阵为: \[ G(x)=\begin{bmatrix} x^{k-1}g(x) \\ x^{k-2}g(x) \\ … \\ xg(x) \\ g(x) \end{bmatrix} \] 说明 (n,k) 循环码可由它的一个 (n-k) 次首一多项式 g(x) 来确定,所以可以说 g(x) 生成了 (n,k) 循环码。称 g(x) 为码的生成多项式。即 \(g(x)=g_{n-k}x^{n-k}+…+g_1x+g_0\)

循环码也是线性码,若 g(x) 为码的生成多项式,则 \(x^n+1=g(x)h(x)\)。称 h(x) 为 (n,k) 循环码的校验多项式,且 \(h(x)=h_kx^k+…+h_1x+h_0\)。其一致校验矩阵为: \[ H(x)=\begin{bmatrix} h^{*}(x) \\ xh^{*}(x) \\ … \\ x^{n-k-2}h^{*}(x) \\ x^{n-k-1}h^{*}(x) \end{bmatrix} \\ H(x)=\begin{bmatrix} 0 & … & 0 & h_0 & h_1 & … & h_{k-1} & h_k \\ 0 & … & h_0 & h_1 & … & h_{k-1} & h_k & 0 \\ … & … & … & … & … & … & … & … \\ h_0 & h_1 & … & h_{k-1} & h_k & 0 & … & 0 \\ \end{bmatrix} \] 式中 h*(x) 是 h(x) 的反多项式: \(h^* (x)=h_0x^k+h_1x^{k-1}…+h_{k-1}x+h_k\)

g(x) 是 (n-k) 次多项式,以 g(x) 为生成多项式,则生成一个 (n,k) 循环码,若以 h(x) 为生成多项式,则生成一个 (n,n-k) 循环码,这两个循环码互为对偶码。

6.3.3 系统循环码

通过行变换,使得 \(G=[I_k:P]\) 的形式,则 \(H=[P^T:I_{n-k}]\)

6.3.7 常用的循环码

  1. 循环冗余校验码(CRC)

    \(C(x) =x^{n-k}m(x)+r(x)\),r(x) 是 xn-km(x) 除以 g(x) 后的余式,g(x) 为 n-k 次多项式。

    若接受码字\(R(x)=C(x)\),这时 R(x) 能被 g(x) 整除,传输过程无差错;否则传输过程中出现了误码。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×