第10章信道编码和差错控制

第10章信道编码和差错控制第一页，共44页。第十章信道编码和差错控制10.1概述信道编码：目的：提高信号传输的可靠性。方法：增加多余比特，以发现或纠正错误。差错控制：包括信道编码在内的一切纠正错误手段。产生错码的原因：乘性干扰引起的码间串扰加性干扰引起的信噪比降低信道分类：按照加性干扰造成错码的统计特性不同划分随机信道：错码随机出现，例如由白噪声引起的错码突发信道：错码相对集中出现，例如由脉冲干扰引起的错码。混合信道2第二页，共44页。差错控制技术的种类：检错重发：能发现错码，但是不能确定错码的位置。通信系统需要有双向信道。前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码。反馈校验：将收到的码元转发回发送端，将它和原发送码元比较。缺点：需要双向信道，传输效率也较低。检错删除：在接收端发现错码后，立即将其删除。适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。3第三页，共44页。编码序列的参数n－编码序列中总码元数量k－编码序列中信息码元数量r

－编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位）k/n－码率(n-k)/k=r/k－冗余度4第四页，共44页。自动要求重发(ARQ)系统停止等待ARQ系统拉后ARQ系统

停止等待ARQ系统接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组拉后ARQ系统214365798接收数据有错码组有错码组91011101112576ACK1NAK5NAK9ACK55769521436798发送数据1011101112重发码组重发码组5第五页，共44页。选择重发ARQ系统ARQ和前向纠错比较：优点监督码元较少，即码率较高检错的计算复杂度较低能适应不同特性的信道缺点需要双向信道。不适用于一点到多点的通信系统或广播系统。传输效率降低，可能因反复重发而造成事实上的通信中断。选择重发ARQ系统9接收数据有错码组有错码组21436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK96第六页，共44页。10.2纠错编码的基本原理分组码举例设：有一种由3个二进制码元构成的编码，它共有23=8种 不同的可能码组：

000–晴001–云010–阴011–雨

100–雪101–霜110–雾111–雹 这时，若一个码组中发生错码，则将收到错误信息。若在此8种码组中仅允许使用4种来传送天气，例如：令

000–晴011–云101–阴110–雨 为许用码组，其他4种不允许使用，称为禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码。若规定只许用两个码组：例如

000–晴111–雨 就能检测两个以下错码，或纠正一个错码。 7第七页，共44页。分组码概念分组码＝信息位＋监督位分组码符号：(n,k)

其中，n－码组总长度，

k－信息码元数目。

r=n–k

－监督码元数目。 右表中的码组为(3,2)码。分组码的一般结构：分组码的参数：码重：码组内“1”的个数码距：两码组中对应位取值不同的位数，又称汉明距离最小码距(d0)：各码组间的最小距离信息位监督位晴000云011阴101雨110k个信息位r个监督位an-1an-2...arar-1an-2...a0t码长n=k+r分组码的结构8第八页，共44页。码距的几何意义：以n=3的编码为例一般而言，码距是n维空间中单位正多面体顶点之间的汉明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a19第九页，共44页。一种编码的纠检错能力：决定于最小码距d0的值。为了能检测e个错码，要求最小码距为了能纠正t个错码，要求最小码距0123BA汉明距离ed0码距等于3的两个码组BtA汉明距离012345td0码距等于5的两个码组10第十页，共44页。为了能纠正t个错码，同时检测e个错码，要求最小码距 纠检结合工作方式：当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发的纠错方式工作，以降低系统的总误码率。AB1tt汉明距离e码距等于(e+t+1)的两个码组11第十一页，共44页。10.3纠错编码系统的性能10.3.1误码率性能和带宽的关系 采用编码降低误码率 所付出的代价是带宽的增大。10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK12第十二页，共44页。10.3.2功率和带宽的关系 采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK13第十三页，共44页。

10.3.3传输速率和带宽的关系 对于给定的传输系统，其传输速率和Eb/n0的关系： 式中，RB

－码元速率。 提高传输速率，采用编 码以保持误码率不变；付出 的代价仍是带宽增大。10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK14第十四页，共44页。10.3.4编码增益 定义：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比Eb/n0称为编码增益： 式中，(Eb/n0)u

－未编码时的信噪比(dB)；

(Eb/n0)c

－编码后所需的信噪比(dB)。15第十五页，共44页。10.4奇偶监督码

10.4.1一维奇偶监督码奇偶监督码－分为奇数监督码和偶数监督码两类。在奇偶监督码中，监督位只有1位，故码率等于k/(k+1)。偶数监督码中，此监督位使码组中“1”的个数为偶数： 式中，a0为监督位，其他位为信息位。奇数监督码中，此监督位使码组中“1”的个数为奇数：检错能力－能够检测奇数个错码。16第十六页，共44页。10.4.2二维奇偶监督码码率等于有可能检测偶数个错码适合检测突发错码能够纠正部分错码………………………17第十七页，共44页。10.5线性分组码基本概念代数码－利用代数关系式产生监督位的编码线性分组码－代数码的一种，其 监督位和信息位的关系由线性代数方程决定汉明码－一种能够纠正一个错码的线性分组码校正子： 在偶数监督码中，计算 实际上就是计算 并检验S是否等于0。

S称为校正子。监督关系式：18第十八页，共44页。纠错基本原理中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置。从而可以有纠错能力。一般而言，若有r个监督关系式，则r个校正子可以指明一个错码的(2r–1)个不同位置。当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求19第十九页，共44页。汉明码例：要求设计一个能够纠正1个错码的分组码(n,k)，给定的码组中有4个信息位，即k=4。由 这时要求监督位数r

3。若取r=3，则n=k+r=7。现在用a6

a5

a4

a3

a2

a1

a0表示这7个码元，用S1S2

S3表示校正子，则这3个校正子恰好能够指明23–1=7个错码的位置。若规定校正子和错码位置的关系如下表，则仅当在a6

a5

a4

a2位置上有错码时，校正子S1的值才等于1；否则S1的值为零。这就意味着a6

a5

a4

a2四个码元构成偶数监督关系：同理，有S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码20第二十页，共44页。在编码时，信息位a6

a5

a4

a3的值决定于输入信号，它们是随机的。监督位a2

a1

a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有 给定信息位后，为了 计算监督位，上式可 以改写为 按照上式计算结果为信息位a6a5a4a3监督位a2a1a0信息位a6a5a4a3监督位a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111121第二十一页，共44页。在接收端解码时，对于每个接收码组，先按式 计算出校正子S1，S2和S3，然后按照表 判断错码的位置。 例：若接收码组为，则按上三式计算得到：S1=0，S2=1，S3=1。这样，由上表可知，错码位置在a3。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码22第二十二页，共44页。上例中的汉明码是(7,4)码，其最小码距d0=3。由式可知，此码能够检测2个错码，或纠正1个错码。汉明码的码率：

当r(或n)很大时，上式趋近于1。所以汉明码是一种高效编码。23第二十三页，共44页。分组码的一般原理线性分组码的监督位和信息位的关系 可以改写为 上式中，已经将“”简写成“+”。24第二十四页，共44页。监督矩阵 上式可以写成矩阵形式：

（模2）

将上式简写为

HAT=0T

或AHT=025第二十五页，共44页。

HAT=0T

式中， －称为监督矩阵监督矩阵的性质监督矩阵H确定码组中的信息位和监督位的关系。H的行数就是监督关系式的数目，即监督位数r

。H的每行中“1”的位置表示相应的码元参与监督关系。

H可以分成两部分，例如 －典型监督矩阵式中，P为r

k阶矩阵，Ir为r

r阶单位方阵。

A=[a6a5a4a3a2a1a0]

0=[000]26第二十六页，共44页。H矩阵的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式。若一个矩阵能写成典型阵形式[PIr]，则其各行一定是线性无关的。生成矩阵例： 可以写为 上式两端分别转置后，可以变成式中，Q为k

r阶矩阵，是P的转置，即 Q=PT

27第二十七页，共44页。

将Q的左边加上一个k阶单位方阵，称为生成矩阵： －生成矩阵

G称为生成矩阵，因为可以用它产生整个码组A，即有生成矩阵的性质具有[IkQ]形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。矩阵G的各行也必须是线性无关的。如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。28第二十八页，共44页。错误图样 设：发送码组A是一个n列的行矩阵： 接收码组是一个n列的行矩阵B： 令接收码组和发送码组之差为

E就是错码的行矩阵 －称为错误图样 式中，

(i=0,1,…,n-1)

若ei

=0，表示该码元未错；若ei=1，表示该码元为错码。B–A=E(模2)29第二十九页，共44页。校正子矩阵

B–A=E可以改写成B=A+E上式表示发送码组A与错码矩阵E之和等于接收码组B。例如，若发送码组A=[1000111]， 错码矩阵E=[0000100]，则 接收码组B=[1000011]。在接收端解码时，将接收码组B代入式

AHT=0

中A的位置进行计算。若接收码组中无错码，则B=A。代入后，该式仍成立，即有

BHT=0

只有当错码未超出检测能力时，上式才不成立。

30第三十页，共44页。10.6循环码

10.6.1循环码的概念： 循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001031第三十一页，共44页。一般情况 若(an-1

an-2…a0)是循环码的一个码组，则循环移位后的码组： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是该编码中的码组。多项式表示法 一个长度为n的码组(an-1

an-2…a0)可以表示成

上式中x的值没有任何意义，仅用它的幂代表码元的位置。 例：码组1100101可以表示为32第三十二页，共44页。10.6.2循环码的运算整数的按模运算 在整数运算中，有模n运算。例如，在模2运算中，有

1+1=20(模2)， 1+2=31(模2)，23=60(模2)

等等。 一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有

m

p(模n)

所以，在模n运算下，一个整数m等于它被n除得的余数。33第三十三页，共44页。码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 则在按模N(x)运算下，有 这时，码多项式系数仍按模2运算。 例1：x3被(x3+1)除，得到余项1，即 例2： 因为

x

x3+1x4+x2+1

x4+x

x2+x+1

在模2运算中加法和减法一样。34第三十四页，共44页。循环码的数学表示法 在循环码中，设T(x)是一个长度为n的码组，若 则T(x)也是该编码中的一个码组。

[证]设一循环码为 则有 上式中的T(x)正是码组T(x)向左循环移位i次的结果。 例：一循环码为，即 若给定i=3，则有 上式对应的码组为，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式。35第三十五页，共44页。循环码的生成有了生成矩阵G，就可以由k个信息位得出整个码组： 例： 式中， 生成矩阵G的每一行都是一个码组。因此，若能找到k个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，xg(x)，x2g(x)，，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。36第三十六页，共44页。在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n–k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n–k)，即连续“0”的个数多于(k–1)。显然，这是与前面的结论矛盾的。我们称这唯一的(n–k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。37第三十七页，共44页。因此，循环码的生成矩阵G可以写成例： 上表中的编码为(7,3)循环码，n=7,k=3,n–k=4，其中唯一的一个(n–k)=4次码多项式代表的码组是第二码组，与它对应的码多项式，即生成多项式，为

g(x)=x4+x2+x+1。码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001038第三十八页，共44页。 g(x)=x4+x2+x+1即“10111”

将此g(x)代入上矩阵，得到 或 上式不符合G=[IkQ]形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。 此循环码组的多项式表示式T(x)： 上式表明，所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k–1)的多项式乘g(x)都是码多项式。39第三十九页，共44页。10.6.5截短循环码截短目的： 在设计时，通常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长截短，得出满足要求的编码。截短方法： 设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0<i<k)个信息位全为“0”