信道编码(1)分组码课件.ppt

《信道编码(1)分组码课件.ppt》由会员分享，可在线阅读，更多相关《信道编码(1)分组码课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 信道编码信道编码 分组码分组码(1)(1)Efficiency vs.ReliabilityEfficiencyAverage code length as small as possibleReliabilityThe ability to recover from errors in the transmissionCodingDecodingInformation sourceSourcecodingChannelcodingInformationchannelChanneldecodingSourcedecodingDestination 提要提要 概述概述-纠错码与差错控制方式纠错

2、码与差错控制方式 信道编码的一般原理信道编码的一般原理 几种简单实用的编码几种简单实用的编码 汉明码汉明码 线性分组码及其描述线性分组码及其描述 循环码及其编译码循环码及其编译码 BCH码与码与RS码简介码简介 卷积码的编码及卷积码的编码及Viterbi译码算法译码算法 交织码交织码,TCM,级连码及级连码及Turbo码码 1 概述概述1什么是信道编码（什么是信道编码（channel coding）?差错控制编码（差错控制编码（error-control coding）-信道编码又称为信道编码又称为差差错控制编码错控制编码，简称为，简称为纠错编码纠错编码，即在信息序列中按一定，即在信息序列中按

3、一定的规则附加若干监督码元，以便对信息传输（或存储）的规则附加若干监督码元，以便对信息传输（或存储）起检错与纠错作用，目的在于起检错与纠错作用，目的在于提高通信（或存储）的可提高通信（或存储）的可靠性，减低靠性，减低误误码率误误码率。纠错码为什么具有纠检错能力？纠错码为什么具有纠检错能力？-引入了冗（多）余度引入了冗（多）余度 多余度多余度可靠性可靠性 信息传输速率信息传输速率（或带宽（或带宽 ）有效有效性性 冗余度=1/3 差错控制能力与什么因素关？差错控制能力与什么因素关？编码规则（包括码及码参数的选择）编码规则（包括码及码参数的选择）差错控制方式差错控制方式 译码方法译码方法 不同信道宜

4、采用不同的编码方案不同信道宜采用不同的编码方案 信道的分类信道的分类-随机干扰信道，突发干扰信道，混合信道随机干扰信道，突发干扰信道，混合信道2差错控制方式（差错控制方式（error-control schemes）：）：3 前向纠错（前向纠错（FEC）自动请求重传（自动请求重传（ARQ）4(1)自动请求重传自动请求重传（Automatic Repeat Request-ARQ）5 ARQ:收端（检错）发现误码收端（检错）发现误码通过反馈信道向发端发通过反馈信道向发端发出重发指令出重发指令发端重发发端重发。6ARQ一般分为三种类型三种类型：等待等待ARQ，退，退N步步ARQ，选择选择ARQ。S

5、top-And-Wait ARQ(SAW ARQ)Transmitting Data1323TimeReceived Data1 23TimeACKACKNAKOutput Data123TimeErrorRetransmissionACK:AcknowledgeNAK:Negative ACK 退退N步步ARQ 选择选择ARQ（2）前向纠错（）前向纠错（FEC-Forward Error Correction）:收端不仅收端不仅能检错，而且能自动纠错，故能检错，而且能自动纠错，故实时性能好，传输效率高，无实时性能好，传输效率高，无须反馈信道须反馈信道。（3）混合）混合ARQ（混合纠错法）：（

6、混合纠错法）：FEC+ARQ 发生少量误码时，收端能自动纠正，超出其纠错能力时，发生少量误码时，收端能自动纠正，超出其纠错能力时，则要求重传，故传输效率与可靠性都可以做得很高。则要求重传，故传输效率与可靠性都可以做得很高。3纠错码的分类：纠错码的分类：2 信道编码的一般原理信道编码的一般原理1如何通过增加冗余度来实现纠、检错？如何通过增加冗余度来实现纠、检错？2例例1 气象台预报天气气象台预报天气3 信码信码 监督元监督元 码字码字（偶校验）传输中错一位（偶校验）传输中错一位4 晴晴 00 0 （000）100，010，0015 云云 01 1 （011）111，001，010 6 阴阴 10

7、 1 （101）001，111，1007 雨雨 11 0 （110）010，100，1118 许用码字许用码字 禁用码组禁用码组9 可检一位错，之所以能检错，是因为引入了可检一位错，之所以能检错，是因为引入了冗余（禁用码冗余（禁用码组）组）例例2 附加两个监督元，设只有附加两个监督元，设只有“晴晴”、“雨雨”两种信息两种信息 信码信码 监督元监督元 码字码字 传输中错一位传输中错一位 晴晴 0 00 （000）100，010，001 0 雨雨 1 11 （111）011，101，110 1 可纠可纠1位错位错若若传输中错传输中错2位位，（，（000）110，011，101 （111）001，0

8、10，100 可检查出可检查出2位错。位错。上述例子说明：上述例子说明：附加监督元可实现检（纠错），监督元越多，码的纠、检错能附加监督元可实现检（纠错），监督元越多，码的纠、检错能力越强。力越强。为了提高纠、检错能力，必须有适当的编译码规则。为了提高纠、检错能力，必须有适当的编译码规则。例如，在例例如，在例2中，若编码规则为中，若编码规则为 晴晴 011，雨雨 000，则无纠错能力。当发生则无纠错能力。当发生1位错时：位错时：（011）111，001，010（000）001，100，010则不能纠则不能纠1位错，但仍能检位错，但仍能检1位错。位错。2分组码及其纠检错能力分组码及其纠检错能力 3

9、（1）分组码及其描述分组码及其描述4定义定义把消息序列分成等长的组（每组把消息序列分成等长的组（每组k个信息码元），个信息码元），每组再附加若干（每组再附加若干（r=n-k）个监督元，从而构成个监督元，从而构成n=k+r长长的码字，这种编码方法就叫做分组编码，所有码字的集的码字，这种编码方法就叫做分组编码，所有码字的集合便构成一个合便构成一个(n,k)分组码分组码。5描述分组码的几个参数：描述分组码的几个参数：码长码长n 信息长信息长k 码率码率（编码效率）：（编码效率）：R=k/n 最小距离最小距离d0决定码的纠、检错能力（2）汉明距离）汉明距离d与最小距离与最小距离d0 重量重量：一个码组

10、中非：一个码组中非“0”位的数目，例如，位的数目，例如，01011，w=3 汉明距离汉明距离：两个码组中对应位数值不同的位数，用：两个码组中对应位数值不同的位数，用d表示，表示，例如，例如，000和和111，d=3 最小（汉明）距离最小（汉明）距离：一个码中汉明距离的最小数值，用：一个码中汉明距离的最小数值，用d0表示表示.设一个码由设一个码由4个码字组成，它们分别是个码字组成，它们分别是000，011，101，110，其重量分别是其重量分别是0，2，2，2，最小距离为，最小距离为2。对于线性码，最小距离就等于最小重量最小距离就等于最小重量。（3）纠、检错能力与最小距离）纠、检错能力与最小距离

11、d0之间的关系之间的关系 (n,k,d0)分组码的纠检错能力分组码的纠检错能力：只用于检错只用于检错(ARQ)：能检出：能检出 个错误个错误；只用于纠错只用于纠错(FEC)，能纠正，能纠正个错误个错误；用于既纠用于既纠t个错，又检个错，又检e个错（个错（te）(混合混合ARQ)几何解释几何解释：C 检检e个错，同时纠个错，同时纠t个错个错(tC2E 1(R)E 2(R)P1P2 C一定，一定，n一定，一定，R E(R)P R一定，一定，C一定，一定，n P 降低错误概率的方法：降低错误概率的方法：增大信道容量增大信道容量C（增加带宽（增加带宽W，或增大平均功率，或增大平均功率S）；）；R一定时

12、，可增大码长一定时，可增大码长n;n一定时，可降低码率一定时，可降低码率R。假设在前三位中只发生一位错，第四位无错，假设在前三位中只发生一位错，第四位无错，正确译码概率正确译码概率：设译码后码元正确概率为设译码后码元正确概率为,则 复习思考题复习思考题1 1信道编码的作用是什么？纠错码为什么具有纠信道编码的作用是什么？纠错码为什么具有纠检错能力？检错能力？2 2差错控制方式通常有哪几类？其原理是什么？差错控制方式通常有哪几类？其原理是什么？各有什么优缺点？各有什么优缺点？3 3信道编码的理论依据是什么？要降低误比特率，信道编码的理论依据是什么？要降低误比特率，可采用哪几种措施？可采用哪几种措施

13、？4 44 4 说明说明(n,k,d(n,k,d0 0)分组码具有怎样的纠检错分组码具有怎样的纠检错能力。能力。解：解：天气 代码 偶检验码 奇校验码 晴 00 000 001 云 01 011 010 阴 10 101 100 雨 11 110 111（2）检错能力：）检错能力：能检出能检出奇数奇数个个错误，但不能检出偶数个错误错误，但不能检出偶数个错误。例例 设信息序列为设信息序列为00000，分别将其编为偶检验码与奇检验码，分别将其编为偶检验码与奇检验码，当差错序列分别为当差错序列分别为101100和和011000时，判断其是否能检错。时，判断其是否能检错。解：解：偶校验：偶校验：发送码

14、字为发送码字为000000 当差错序列为当差错序列为101100时，接收码组为时，接收码组为101100，可检；，可检；当差错序列为当差错序列为011000时，接收码组为时，接收码组为011000，不可检；，不可检；奇校验：奇校验：发送码字为发送码字为000001 当差错序列为当差错序列为101100时，接收码组为时，接收码组为101101，可检；，可检；当差错序列为当差错序列为011000时，接收码组为时，接收码组为011001，不可检；，不可检；（3）不可检错误概率）不可检错误概率(不要求不要求)：对对于BSC一个一个n长码字在长码字在BSC上传输，发生上传输，发生m位错误的概率为位错误的

15、概率为 采用奇偶校验码后采用奇偶校验码后例如，当例如，当n=4,时时，若不用编码，则若不用编码，则采用编码后采用编码后奇偶校验码奇偶校验码-适用于随机错误信道，采用适用于随机错误信道，采用ARQ进行检错。进行检错。2二维奇偶检验码（水平垂直检验码，方阵码）二维奇偶检验码（水平垂直检验码，方阵码）3 （1）编码规则）编码规则：把信息序列排成一个阵列，然后分别将：把信息序列排成一个阵列，然后分别将每行每列编成奇偶校验码。发送时，按顺序逐列发送；接每行每列编成奇偶校验码。发送时，按顺序逐列发送；接收后，再逐行逐列检测。收后，再逐行逐列检测。（2）码率）码率：（3）检错能力）检错能力：能检出行（列）中

16、奇数个错误；能检出行（列）中奇数个错误；能检出部分偶数个错误；能检出部分偶数个错误；能检出长度小于等于能检出长度小于等于m(行数行数)的突发错误；的突发错误；恰好位于矩形恰好位于矩形4个角上的错误无法检出。个角上的错误无法检出。（4）适用范围）适用范围：突发错误信道或混合信道（采用：突发错误信道或混合信道（采用ARQ）。3定比码定比码：每个码字中每个码字中“1”的数目是固定的，即的数目是固定的，即“1”与与“0”数目之比为一定值，故称为定比码。在数学上又称为数目之比为一定值，故称为定比码。在数学上又称为“n中取中取m码码”。4（1）常用定比码：）常用定比码：5中取3码（用于中文电报），7中取4

17、码5例例 中文电报中文电报6汉字汉字4位阿拉伯数字位阿拉伯数字每位用一个每位用一个5中取中取3码的码字来表示码的码字来表示7数字数字 码字码字 数字式数字式 码字码字8 1 01011 6 101019 2 11001 7 1110010 3 10110 8 0111011 4 11010 9 1001112 5 00111 0 01101 五 邑 大 学 0063 6712 1129 133101101 01101 10101 10110 10101 11100 01011 1100101011 01011 11001 10011 01011 10110 10110 01011（1）编码效率

18、：）编码效率：对于5中取3码，（3）检错能力与不可检查错误概率）检错能力与不可检查错误概率(不要求推导不要求推导)检错能力：可检出所有检错能力：可检出所有奇数个奇数个错误和错误和部分偶数个部分偶数个错误错误；不可检错误概率：不可检错误概率：不能检出的情况不能检出的情况-“1”“0”，“0”“1”成对出现，成对出现，其中，出现一对的概率最大，两对以上概率较小，可忽略，因其中，出现一对的概率最大，两对以上概率较小，可忽略，因而只须估算出现一对时的情况。而只须估算出现一对时的情况。一个码字中有一个码字中有m个个1，故，故1变成变成0的概率为的概率为一个码字中有一个码字中有n-m个个0，故，故0变成变

19、成1的概率为的概率为所以，定比码的不可检错误概率可近似为所以，定比码的不可检错误概率可近似为例如，例如，5中取中取3码，若码，若，则若不用定比码，则若不用定比码，则5中错中错1个以上错就会发生差错，故错误概个以上错就会发生差错，故错误概率为率为（4）用途：用于电传机，或键盘产生的电码。）用途：用于电传机，或键盘产生的电码。4重复码重复码：是一种最简单的纠错码，是一种最简单的纠错码，(n,k)=(n,1)，n为奇数，为奇数，监督元是信息元的简单重复，用大数判决法译码监督元是信息元的简单重复，用大数判决法译码,可纠正不可纠正不多于多于(n-1)/2个错误。个错误。5例如，例如，n=5,信元符号信元

20、符号0和和1分别编为分别编为00000和和11111，在通过，在通过BSC传输，设信道转移概率传输，设信道转移概率p1/2,当收到当收到01001时，因时，因0的数的数目比目比1多，故译成多，故译成0,反之，译成反之，译成1。这是因为这是因为p1/2,故错两位的概率大于错三位的概率，即故错两位的概率大于错三位的概率，即码字错误概率：码字错误概率：译码后码字正确的概率是译码后码字正确的概率是码字错误概率为码字错误概率为重复码的优点：简单，易于实现重复码的优点：简单，易于实现缺点：码率很低缺点：码率很低 4 汉明码汉明码 如何构造纠一位错的高效如何构造纠一位错的高效(n,k)码码?奇偶检验码：奇偶

21、检验码：校正子校正子：一个监督元，一个监督元，得到一个校正子，只能表示有错与无错；得到一个校正子，只能表示有错与无错；两个监督元，得到两个校正子，共两个监督元，得到两个校正子，共4种状态，可表示有错及种状态，可表示有错及3个错位，即个错位，即 同理，同理，r个监督元个监督元得到得到r个校正字，共个校正字，共种状态一种表示无错，其余的表示一种表示无错，其余的表示个错位可构造一个，k=n-r 纠一位错的纠一位错的(n,k)分组码，当等号分组码，当等号成立时效率最高。成立时效率最高。因此，要构造一个纠一位错的要构造一个纠一位错的(n,k)码，须满足码，须满足其中，其中，k为信息长，为信息长，r为监督

22、元的数目为监督元的数目，n=k+r .2如何得到如何得到r个监督关系式？个监督关系式？3例例 试设计一个试设计一个k=4,纠一位错的高效纠一位错的高效(n,k)分组码。分组码。设编出的码字为设编出的码字为其中其中，为信息元为信息元，为监督元为监督元 构造构造3 3个监督方程，将得到个监督方程，将得到S S1 1S S2 2S S3 3的的8 8种不同状态，将其与错种不同状态，将其与错误状态的对应关系列表，再按列读出，便可写出监督关系式误状态的对应关系列表，再按列读出，便可写出监督关系式编码时须满足编码时须满足S1=S2=S3=0，即即故编码规则编码规则为例例 设待编码的信息组为设待编码的信息组

23、为 则则 经传输后若接收码组为（经传输后若接收码组为（0000011），将其代入方程组，得），将其代入方程组，得查表，知错在查表，知错在位，取反，译得码字为（0001011），即信息组为（信息组为（0001）。）。这就是著名的（这就是著名的（7，4）汉明码）汉明码。3（n,k）汉明码的描述）汉明码的描述 码参数码参数：码率码率：码字错误概率：码字错误概率：4汉明码是一种完备码（汉明码是一种完备码（perfect code）(不要求不要求)5 一个（一个（n,k,t）二元线性分组码：二元线性分组码：6 接收码组中发生接收码组中发生1tc个错误个错误禁用码组；禁用码组；以每个码字为球心，以以每个码

24、字为球心，以 为半径作球，共为半径作球，共 构成构成 禁用码组可落在球内，也可落在球外；禁用码组可落在球内，也可落在球外；落在球面或球内的接收码组落在球面或球内的接收码组译成球心的码字；译成球心的码字；一个球体内包含的码组数（点数）：一个球体内包含的码组数（点数）：个球；其中，落在球心的为码字，其其中，落在球心的为码字，其余为禁用码组；余为禁用码组；显然，任何线性分组码均满足任何线性分组码均满足，即或 完备码：满足完备码：满足的的(n,k)分组码便称分组码便称为完备码。在完备为完备码。在完备码中，所有禁用码码中，所有禁用码组都均匀地分布在组都均匀地分布在以以tc 为半径的球体内。（球互不相交，

25、球之间无禁用码组）分析：为半径的球体内。（球互不相交，球之间无禁用码组）分析：等号成立等号成立k最大最大R=k/n最大最大效率最高。效率最高。汉明码是一种完备码：汉明码是一种完备码：将将（汉明球包限）（汉明球包限）代入不等式，得 完备码的完备码的优点优点：在码长相同，纠错能力相同的情况下，码率最高（所须监督位最少）；同在码长相同，纠错能力相同的情况下，码率最高（所须监督位最少）；同时，译码错误最小。时，译码错误最小。完备码是一种最佳码完备码是一种最佳码注注：完备码的数量非常少，除汉明码外，只有（：完备码的数量非常少，除汉明码外，只有（23，12）t=3的二进制的二进制Golay码，及码，及(1

26、1,6)t=2的三进制的三进制Golay码也是完备码码也是完备码。复习思考题复习思考题1 什么是什么是奇偶校验码、二维奇偶校验码、定比码、重复奇偶校验码、二维奇偶校验码、定比码、重复码？其纠（检）错能力如何？码？其纠（检）错能力如何？2 汉明码的基本参数是什么？能纠正几位错误？汉明码的基本参数是什么？能纠正几位错误？3 什么叫汉明限（分组码什么叫汉明限（分组码n,k,r之间有什么关系）？什之间有什么关系）？什么叫完备码？完备码有何优点？么叫完备码？完备码有何优点？(不要求不要求)小结小结1.信道编码的基本概念信道编码的基本概念2.差错控制方式差错控制方式 前向纠错前向纠错(FEC)自动请求重传自动请求重传(ARQ):3种形式种形式3.几种简单的实用编码几种简单的实用编码 奇偶校验码奇偶校验码 定比码定比码 重复码重复码4.汉明码汉明码 基本概念基本概念 构造方法构造方法 基本参数基本参数