第九章 信道的纠错编码

第九章

信道的纠错编码第九章信道的纠错编码9.1差错控制的基本形式9.2纠错码分类及基本概念9.3线性分组码

香农第二定理指出,当信息传输速率低于信道容量时,通过某种编译码方法,就能使错误概率为任意小.目前已有许多有效的编译码方法,并形成了一门新的技术

—

纠错编码技术.

纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。

信源编码的目的是压缩冗余度，提高信息的传输速率.

信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性.9.1差错控制的基本形式9.1.1前向纠错方式9.1.2反馈重发方式9.1.3混合纠错方式9.1.4信息反馈方式9.1.1前向纠错（EFC）方式FEC(ForwardErrorControl)方式:发端发送有纠错能力的纠错码,接收端收到这些码后,通过纠错译码器自动地纠正传输中的错误.信源FEC编码信道FEC译码信宿优点是不需要反馈信道;能进行一个用户对多个用户的同时通信;译码实时性较好;控制电路也比较简单.缺点是译码设备较复杂;编码效率较低.9.1.2反馈重发（ARQ）方式ARQ(AutomaticRepeatreQuest)方式:发端发出能够发现错误的检错码,收端译码器收到后,判断在传输中有无错误产生,并通过反馈信道把检测结果告诉发端.发端把收端认为有错的消息再次传送,直到收端认为正确接收为止.信源编码器正向信道译码器信宿缓存器重发控制器反向信道重发判决器9.1.2反馈重发（ARQ）方式优点是译码设备简单,在冗余度一定的情况下,码的检错能力比纠错能力要高得多,因而整个系统能获得极低的误码率.应用ARQ方式必须有一条从收端至发端的反馈信道.其控制电路比较复杂,传输信息的连贯性和实时性也较差.9.1.3混合纠错（HEC）方式反馈信道ARQFEC

编码器正向信道FEC

译码器ARQ9.1.3混合纠错（HEC）方式HEC(HybridErrorControl)方式:前两种方式的结合.发端发送的码既能检错、又有一定的纠错能力.收端译码时若发现错误个数在码的纠错能力以内,则自动进行纠错;若错误个数超过了码的纠错能力,但能检测出来,则通过反馈信道告知发方重发.这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点.9.1.4信息反馈（IRQ）方式信息信号信息信号发端收端IRQ(InformationRepeatRequest)方式:收端把收到的码全部由反馈信道送回发端,在发端进行比较,发现错误后,把出错的码再次重发,直到收端正确接收为止.方法和设备简单,无需纠、检错编译系统.但需要双向信道,传输效率↓、实时性差.纠错方式小结可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号

信息信号发收IRQ信息信号9.2纠错码分类及基本概念9.2.1纠错码分类9.2.2纠错码的基本概念及其纠错能力9.2.1纠错码分类

根据干扰和噪声形式对信道分类随机信道:

错码出现是随机的,统计独立的.例如,高斯白噪声信道,卫星信道、同轴电缆、光缆信道等.—纠随机差错码.突发信道:

错码成串集中出现,在很短的时间出现大量错码,而过后又存在较大的无错码位.例如,移动通信信道、短波信道、带擦伤的光盘等.—纠突发差错码.混合信道:

既存在随机错码,又存在突发错码,两者均不能忽略.—纠混合差错码.9.2.1纠错码分类

按应用目的分类检错码:能发现错误但不能纠正错误的码.纠错码:不仅能发现错误而且还能纠正错误的码.纠删码:

能够纠正被删除了信息的错误的码.9.2.1纠错码分类

按码的结构中对信息序列处理方式分类分组码:把信息序列以每k个码元分组(信息组),编码器将每个信息组按一定规律产生r个多余的码元(校验元),形成一个长为n=k+r的码字.记为(n,k)码.卷积码:把信息序列以每k个分组,通过编码器输出长为n的一个子码,该子码的n－k个校验元不仅与本子码的信息元有关,而且与其前L个子码的信息元有关.记为(n,k,L)码.9.2.1纠错码分类

按码的数学结构中校验元与信息元关系分类线性码:校验元与信息元之间呈线性关系的码.非线性码:校验元与信息元之间呈非线性关系的码.线性码的理论较成熟,但非线性码出现许多好码.

按码是否具有循环性分类循环码:分组码中的任一码字的码元循环移位后仍是这组的码字.非循环码:分组码中的任一码字的码元循环移位后不一定是这组的码字.9.2.1纠错码分类

按码元取值分类二元码和多元(q)码.

按构造码的数学理论分类代数码:建立在近世代数基础上.线性分组码是代数码中一类重要的码.几何码:数学理论基础是投影几何学.算术码:数学理论基础是数论、高等算术.组合码:数学理论基础是排列组合和数论.9.2.1纠错码分类9.2.2纠错码的基本概念及纠错能力

码字信息元校验元

信道编码器将输入信息序列,每k个信息符号分成一组(信息组,个),记为,其中称为信息元.

编码器将每个信息组按一定规律产生r个多余的符号(校验元),形成一个长为n=k+r的码字.码字中每个符号称为码元.

不同的n长的码符号序列总共有种,(n,k)分组码的个称为许用码字,其余称为禁用码字.9.2.2纠错码的基本概念及纠错能力

码字的汉明重量

码字中含非零码元的个数称为码字的汉明重量.记作W(C).设二元码字,则例如,码字10110,码重W=3.9.2.2纠错码的基本概念及纠错能力

错误图样设发送码接收码接收码组和发送码组之差为(模2减)E称为错误图样.无差错发生有差错发生码字、接收序列和错误图样的关系:9.2.2纠错码的基本概念及纠错能力

错误图样在二元无记忆信道中,发生一位随机差错的错误图样个数二位随机差错的错误图样个数发生e位随机差错的错误图样个数全错的错误图样个数全对的错误图样个数9.2.2纠错码的基本概念及纠错能力

分组码纠错能力与码最小距离的关系码距的几何意义:以n=3的编码为例,a2a1a0(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1码距是n维空间中单位正多面体顶点之间的汉明距离.发送码字000和111,最小距离是3,可以纠正1位码元的错误,检测2位码元的错误.9.2.2纠错码的基本概念及纠错能力

分组码的码率(n,k)分组码的许用码组数为M=2k,R称作信道信息传输率,也称作码率.它表示了信息位在分组码码字中的比重.一个好的实际纠错编码方案,不但希望其纠错检错能力强,而且希望其码率高.9.3线性分组码9.3.1一致校验矩阵和生成矩阵9.3.2伴随式及标准阵列译码9.3.3汉明码9.3.1一致校验矩阵和生成矩阵分组码:把信息序列以每k个码元分组(信息组),编码器将每个信息组按一定规律产生r个多余的码元(校验元),形成一个长为n=k+r的码字.记为(n,k)码.线性码:校验元与信息元之间呈线性关系的码.各码元应满足齐次线性方程:

一致校验方程9.3.1一致校验矩阵和生成矩阵各码元应满足齐次线性方程:

一致校验方程共r个方程,k个独立变量—

k个独立的信息元,r个校验元可由此方程给出.例某(7,3)线性分组码,k=3,r=4,决定校验元的齐次线性方程组如下9.3.1一致校验矩阵和生成矩阵

一致校验方程共r个方程,k个独立变量—

k个独立的信息元,r个校验元可由此方程给出.上式称一致校验方程,式中c6,c5,c4是独立的,其余4位可由这三个量求得.例某(7,3)线性分组码,k=3,r=4,决定校验元的齐次线性方程组如下9.3.1一致校验矩阵和生成矩阵

一致校验方程令信息组中,信息组m2m1m0

码字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100得(7,3)线性分组码表19.3.1一致校验矩阵和生成矩阵

一致校验矩阵上式称一致校验方程,式中c6,c5,c4是独立的,其余4位可由这三个量求得.矩阵形式表示方程9.3.1一致校验矩阵和生成矩阵

一致校验矩阵矩阵形式表示方程令矩阵

称为(7,3)分组码的一致校验矩阵.9.3.1一致校验矩阵和生成矩阵

一致校验矩阵

矩阵的每一行是线性方程组中各方程的系数.一般分组码的一致校验矩阵,阶:信息元和校验元之间的校验关系完全由一致校验矩阵确定.9.3.1一致校验矩阵和生成矩阵

生成矩阵前例中,信息组中得(7,3)线性分组码校验元例9.29.3.1一致校验矩阵和生成矩阵

生成矩阵前例中,信息组中得(7,3)线性分组码码字例9.29.3.1一致校验矩阵和生成矩阵

生成矩阵矩阵形式表示方程例9.29.3.1一致校验矩阵和生成矩阵

生成矩阵令矩阵

称为(7,3)分组码的生成矩阵.矩阵形式表示方程例9.29.3.1一致校验矩阵和生成矩阵

生成矩阵信息组m2m1m0

码字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100生成矩阵

的行矢量是(7,3)码的一个码字.所有码字可由此行矢量线性组合获得.令矩阵

的三个码字是线性无关的,即独立的.表19.3.1一致校验矩阵和生成矩阵

生成矩阵对于一般的线性分组码(n,k),设有一组k个线性独立的码字,生成矩阵为阶,9.3.1一致校验矩阵和生成矩阵

系统码信息组m2m1m0

码字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100若信息组以不变的形式,在码字的任意k位中出现的码;否则,称为非系统码.若生成矩阵能把信息元保留在各码字的最左边k位上,此系统码的生成矩阵G称为标准生成矩阵.表19.3.1一致校验矩阵和生成矩阵对于某(n,k)线性分组码C,在2k个码字中k个独立码字组不止一种.对于同一码,当选取不同的独立码字组构成的生成矩阵G也可不同.但经过若干次矩阵的初等变换后,可变成其等价的标准生成矩阵.

系统码9.3.1一致校验矩阵和生成矩阵

不同的生成矩阵例9.3二元(7,3)线性码,生成矩阵信息组m2m1m0

码字c6c5c4c3c2c1c000000000000011110100010101001101101001111001001110101011101011000111011111101001表2生成非系统码.G2经过初等变换,得标准生成矩阵①②③②+③①+②码字同表19.3.1一致校验矩阵和生成矩阵

另取标准生成矩阵信息组m2m1m0

码字c6c5c4c3c2c1c000000000000010011110010010011101101110011001001011101101010111011011001111110010表3生成系统码,不同的(7,3)线性分组码.码字不同表19.3.1一致校验矩阵和生成矩阵(n,k)线性分组码的重要性质(1)(n,k)线性分组码由其生成矩阵G或校验矩阵

H确定.(2)封闭性.(n,k)码中任意两个许用码字之和仍为许用码字.证明(3)含有零码字.n位长,(n,k)码的许用码字.9.3.1一致校验矩阵和生成矩阵(n,k)线性分组码的重要性质(4)所有许用码字可由其中一组k个独立码字线性组合而成.(5)码的最小距离等于非零码的最小重量.证明9.3.1一致校验矩阵和生成矩阵

最小距离d与一致校验矩阵H之间的关系定理设(n,k)线性分组码C的校验矩阵为H,则码的最小距离d的充要条件是H中任意d-1个列矢量线性无关,且有d个列矢量线性相关.证明必要性:必有一码字C,具有d个非零分量.因此H中一定有d个列矢量是线性相关的.而d-1个线性无关.充分性:类似.9.3.1一致校验矩阵和生成矩阵

最小距离d与一致校验矩阵H之间的关系

由定理知,当所有列矢量相同时,其排列位置不同的H矩阵所对应的(n,k)码,都有相同的最小距离,则它们在纠错能力和码率上是完全等价的.

对于分组码来说,系统码和非系统码的纠错能力是相同的.由于系统码的编、译码较非系统码简单,且G和H可以方便地互求,主要讨论系统码.例9.4前例(7,3)线性分组码,k=3,r=4,标准一致矩阵为(1)任何三列相加均非零,最少相关列数是4.(2)信息组m2m1m0

码字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100表1(3)验证例9.4前例(7,3)线性分组码,k=3,r=4,G2生成非系统码信息组m2m1m0

码字c6c5c4c3c2c1c000000000000011110100010101001101101001111001001110101011101011000111011111101001表2例9.4前例(7,3)线性分组码,k=3,r=4,G2生成非系统码此时:一致校验方程例9.4前例(7,3)线性分组码,k=3,r=4,G2生成非系统码对应G2一致校验矩阵此时:一致校验方程例9.4前例(7,3)线性分组码,k=3,r=4,G2生成非系统码H1与H2不同,但最小相关数也是4.

G2与G1都生成(7,3,4)分组码,纠错能力是1,码率是3/7.因此说G2与G1是等价的.对应G2一致校验矩阵例9.4前例(7,3)线性分组码,k=3,r=4,G3生成系统码H3最小相关数仍是4.G3与G1生成(7,3,4)码不同,但纠错能力、码率相同.因此说G3与G1也是等价的.对应G2一致校验矩阵9.3.2伴随式及标准阵列译码

线性码的纠错与伴随式令S与发送的许用码字无关,仅与错误图样E有关.称S为R的伴随式.不同的错误图样对应不同的伴随式.根据伴随式判断和纠正传输差错.设(n,k)线性分组码发送许用码字,经信道传输后,接收序列是,错误图样为

.可以将接收码字

用一致校验方程进行检验:

线性码的纠错与伴随式令S与发送的许用码字无关,仅与错误图样E有关.称S为R的伴随式.不同的错误图样对应不同的伴随式.根据伴随式判断和纠正传输差错.例9.5前例(7,3)线性分组码,k=3,r=4,标准一致矩阵为(1)传送时没发生差错,

线性码的纠错与伴随式例9.5前例(7,3)线性分组码,k=3,r=4,标准一致矩阵为(1)传送时没发生差错,(2)传送时发生1位码元差错,H1中的第1列矢量H1中的第3列矢量若发送码字和,都发生E1错误,接收序列为和

线性码的纠错与伴随式伴随式与发送码字无关,仅与错误图样有关!当发生1位差错在第i位上,伴随式Si正好是其H中第i列矢量.(3)传送时发生2位码元差错,若

线性码的纠错与伴随式(3)传送时发生2位码元差错,若伴随式不为零,说明传送的码字发生了差错;由于不同的错误图样对应相同的伴随式,无法纠正发生的2位差错;原因,只能纠正1位码元的错误.

线性码的纠错与伴随式(4)传送时发生3位差错,伴随式不为零,说明传送的码字发生了差错;若用于纠正1位码元的错误,则无法检测出发生3位码元的错误;或者只用于检测差错,能检测出任意小于或等于3位差错的错误.伴随式不为零,说明传送的码字发生了差错;由于不同的错误图样对应相同的伴随式,无法纠正发生的2位差错;原因,只能纠正1位码元的错误.

线性码的纠错与伴随式此码能纠正单个错误,同时检测出2个错误;dmin

≥t+e+12)用于检查3个错误.dmin

≥e+1

总结:时,

9.3.2伴随式及标准阵列译码

最小距离译码规则满足n次无记忆扩展信道中,随机差错的错误图样E出现的概率为发生1位随机错误发生2位随机错误9.3.2伴随式及标准阵列译码n次无记忆扩展信道中,随机差错的错误图样E出现的概率为发生1位随机错误发生2位随机错误发生e位随机错误发生n位全错9.3.2伴随式及标准阵列译码

一般采用最大似然译码规则,在BSC信道中,重量最小的E,发生的概率最大.因此选取最轻的E作为译码的错误图样.这也是采用了最小距离译码准则.发生e位随机错误发生n位全错9.3.2伴随式及标准阵列译码

线性分组码的基本译码步骤Step1:

由接收到的序列R,计算伴随式S=RHT

;Step2:

若S=0,正确接收;若S不为零,寻找错误图样;Step3:

由错误图样解出码字C=R+E.

标准阵列译码步骤Step1:

接收序列R;Step2:

查标准阵列译码表,直接得到译码C.9.3.2伴随式及标准阵列译码

标准阵列译码表构造方法(1)根据许用码字将禁用码字进行分类,分类的依据是错误图样.9.3.2伴随式及标准阵列译码错误图样E0+Cj

=Cj………………码字禁用码字标准阵列译码(陪集首)E0+C1=C1E0+C0=0E1+C0=E1E1+C1E1+Cj…E2+C0=E2E2+C1E2+Cj……S0

S1

S2

…伴随式

标准阵列译码表构造方法9.3.2伴随式及标准阵列译码(1)根据许用码字将禁用码字进行分类,分类的依据是错误图样.(2)先把全部2k个码字,C0,C1,…，置于表的第一行；(3)在余下的2n－2k个禁用码字中,选择一个重量最轻的n长序列记作E1,作为第二行的首位元素,于是第二行的元素是E1和每个码字Ci（i＝0,1,…,2k-1）相加.

标准阵列译码表构造方法9.3.2伴随式及标准阵列译码(4)在余下的禁用码字中,再选择一个重量最轻的n长序列记作E2,作为第三行的首位元素,于是第三行的元素是E2和每个码字Ci（i＝0,1,…,2k-1）相加.(5)依此类推,直到全部禁用码字分完为止.(6)在表的最前面增加一列,为错误图样对应的伴随式Si.

标准阵列译码表构造方法9.3.2伴随式及标准阵列译码(1)标准阵列译码表是一个2n－k行、2k列的阵列.(2)表中每列元素组成一个子集,许用码字Cj（j＝0,1,…,2k-1）是它的子集首.(3)表中每一行称为一个陪集,每一行的首位元素Ei

（i＝0,1,…,2n-k-1）称作陪集首.

标准阵列译码表构成小结9.3.2伴随式及标准阵列译码(1)如果把陪集首看成是错误图样,则同一陪集中的所有元素都对应相同的伴随式,而不同的陪集具有不同的伴随式.(2)对于同一列的各子集来说,2n-k个序列的错误图样虽然不同,但都对应同一个许用码字.

标准阵列特性

标准阵列译码方法方法1:

在表中搜寻接收码字R,把R所在列的子集首Cj作为译码;方法2:

求出伴随式S,找出S所在行中的R,把R所在列的子集首Cj作为的译码.例9.6设(5,2)系统线性码的生成矩阵G,构造该码的标准阵列译码表.若接收码,求发送码的估值.解:(1)信息组,求出许用码字(2)求出校验矩阵(3)求最小距离错误图样(陪集首)码字禁用码字标准阵列译码伴随式C1=01101C0=00000C2=10111C3=11010S0=000S1=111E1=100001110100111

01010

E2=01000001011111110010E3=00100010011001111110E4=00010011111010111000E5=00001011001011011011E6=00011011101010011001E7=00110010111000111100S2=101S3=100S4=010S5=001S6=011S7=110能纠正1位随机错误！(4)构造标准阵列译码表(5)对接收码译码选择不唯一9.3.2伴随式及标准阵列译码(1)标准阵列译码表需要存入2n个R,随n呈指数增大.

简化译码表(2)只保留标准阵列译码表中伴随式Si和错误图样Ei(3)由R计算出伴随式S

由表查找S对应的错误图样E

计算SiEiS0=000E0=00000S1=111S2=101S3=100S4=010S5=001E1=1000