信息论第6章信道编码课件

第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次：如何正确接收载有信息的信号如何避免少量差错信号对信息内容的影响纠错编码试图克服信道中噪声造成的损害基本思想：在消息通过一个有噪信道传输前，以多余符号的形式在消息中增添冗余度。通信原理THISISANINTRSTNGBOOKTHISISANINTERESTINGBOOK12/14/20221第6章信道编码信道编码是以信息在信道上的正确传输为目标的编第6章信道编码m：输入信息序列的每k个信息符号分成一段，称为信息组mi：信息元C：码字 Ci：码元r=n-k：校验元分组码：每个码字中增加的r个校验元只由本组的k个信息元产生，与其他信息组的信息元无关。记为(n,k)卷积码：增加的r个校验元既与本组信息元有关，还与前面L组信息元有关。记为(n,k,L)(m1,m2,…,mk){x0,x1,…xq-1}(c1,c2,…,cn)qkqn12/14/20222第6章信道编码m：输入信息序列的每k个信息符号分成一段，称第6章信道编码6.1 有扰离散信道的编码定理6.2 纠错编译码的基本原理与分析方法12/14/20223第6章信道编码6.1 有扰离散信道的编码定理12/11/2差错和差错控制系统分类差错符号、差错比特符号是信息比特的载体。信号差错与信息差错既有联系又有区别。符号差错概率（误码元率）指信号差错概率 误比特率指信息差错概率12/14/20224差错和差错控制系统分类差错符号、差错比特12/11/2022差错和差错控制系统分类随机差错差错始终以相等的概率独立发生于各码字、各码元和各比特之间，与前后位置和时间无关。如加性高斯白噪声突发差错由突发噪声引起的前后相关、成堆出现的差错。数学模型：双状态一阶马尔可夫链模型12/14/20225差错和差错控制系统分类随机差错12/11/20225纠错码分类从功能角度，差错码分为检错码和纠错码检错码：用于发现差错的信道码纠错码：能自动纠正差错的信道码例：要发送A和B可以采用以下三种方法：不重复：用0代表A，1代表B。重复一次：用00代表A，11代表B。 增加一位码元，传送效率降低一倍。重复两次：用000代表A，用111代表B。 增加两位码元，效率降低两倍。既不检错，又不纠错检错但不纠错既检错又纠错12/14/20226纠错码分类从功能角度，差错码分为检错码和纠错码既不检错，又不纠错码分类按照对信息序列的处理方法，有分组码和卷积码两种。分组码：将信息序列分割成k位一组后独立编解码，分组间无关。卷积码：编解码运算不仅与本组信息有关，还与前面若干组有关。按照码元与原始信息位的关系，分为线性码和非线性码。线性码：所有码元均是原始信息元的线性组合，编码器不带反馈回路。非线性码：码元并不都是信息元的线性组合，可能还与前面的码元有关，编码器可能含反馈回路。12/14/20227纠错码分类按照对信息序列的处理方法，有分组码和卷积码两种。1纠错码分类按照适用的差错类型，分成纠随机差错码和纠突发差错码两种。随机差错差错是相互独立的，不相关存在这种差错的信道是无记忆信道或随机信道突发差错指成串出现的错误，错误与错误间有相关性，一个差错往往要影响到后面一串字0010010000001001110000000突发长度=4突发长度=6用可纠独立差错的个数来衡量用可纠突发差错的最大长度来衡量12/14/20228纠错码分类按照适用的差错类型，分成纠随机差错码和纠突发差错码差错控制系统分类前向纠错方式（FEC）发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，如果传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。实时性好，适用于单工通信12/14/20229差错控制系统分类前向纠错方式（FEC）实时性好，适用于单工通检错与纠错方式自动请求重发方式（ARQ）发送端发送检错码 接收端译码器判断当前码字传输是否出错当有错时，按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字译码设备不复杂，对突发错误特别有效12/14/202210检错与纠错方式自动请求重发方式（ARQ）译码设备不复杂，对突检错与纠错方式混合纠错（HEC）FEC与ARQ方式的结合。发送端发送同时具有自动纠错和检测能力的码组，收端收到码组后检查差错情况。如果差错在码的纠错能力内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。检错、纠错能力强，译码设备复杂，应用广泛12/14/202211检错与纠错方式混合纠错（HEC）检错、纠错能力强，译码设备复与差错控制有关的基本概念码长：码字中码元的个数，用n表示汉明重量（码重）：码字中非0码元的个数，用W表示。对于二进制来说，指码字中码元1的数目。若码字C=(c1c2…cn)，则汉明距离（码距）：两个等长码字之间对应码元不相同的数目，用D表示。设两个二元码字X=(x1x2…xn)和Y=(y1y2…yn)，则有两个码字模二相加得到的新码字的重量应是这两个码字之间的汉明距离，即12/14/202212与差错控制有关的基本概念码长：码字中码元的个数，用n表示12与差错控制有关的基本概念码的最小距离dmin在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即例：码集C={0111100,1011011,1101001}最小码距是衡量该码纠错能力的重要依据从避免码字受干扰而出错的角度出发，希望码字间有尽可能大的距离，因为最小码距代表着一个码集中最不利的情况。从安全出发，应使用最小码距来分析码的检错、纠错能力。dmin=312/14/202213与差错控制有关的基本概念码的最小距离dmindmin=312与差错控制有关的基本概念错误图样在二元无记忆N次扩展信道中，差错的形式也可以用二元序列来描述，称为错误图样。设发送码字为C=(c1c2…cn)，接收码字为R=(r1r2…rn)，两者的差别为例：R=(110000)，C=(100001)E＝C⊕R=(010001)，表明接收符号系列的第2位和第6位出现了错误。12/14/202214与差错控制有关的基本概念错误图样12/11/202214检错、纠错能力差错的产生码字集合是N维矢量空间XN中的一个子集。若传输无误，接收到的码字应在码字集合内。若出现差错，有两种可能：对应到码字集合外的一点上。对应到码字集合内的另一点上。检错与纠错能力纠错码的检、纠错能力是指能够检测、纠正差错的数目。能够检错不能检错12/14/202215检错、纠错能力差错的产生能够检错不能检错12/11/2022检错、纠错能力检错能力纠错码的最小距离dmin表示从子集中一点偏移到另一点的距离。若差错数目e大于等于dmin，将导致一个码字被译成另一个码字，这种错误无法检测。若差错数目e小于dmin，则不可能从子集的一个点偏移到另一个点，即可以检测出差错。dminee≤dmin－112/14/202216检错、纠错能力检错能力dminee≤dmin－112/11检错、纠错能力纠错能力以每个码字为球心，以汉明距离t为半径作2k个球体。球体之间不相交（且不相切）的条件是：dmin=2t+1译码时，所有落在球内的接收码字都被译为位于球心的码字。纠错能力总是小于检错能力的。dmintt=INT[(dmin-1)/2]12/14/202217检错、纠错能力纠错能力dmintt=INT[(dmin-1检错、纠错能力检、纠错能力若将检错和纠错统一考虑，情况会有所变化。要增加检错能力，必须抑制纠错能力。如码字A、B的码距为7码字A发生3个差错时能够纠正；若发生4个差错时，将被译成B。即：检错和纠错能力都为3。若要提高检错能力为4，需将纠错能力减为2。若最小距离dmin的码同时能检ed、纠ec个差错，则ed+ec≤dmin-112/14/202218检错、纠错能力检、纠错能力ed+ec≤dmin-112/1检错、纠错能力对纠错编码的基本要求纠错和检错能力尽量强，编码效率尽量高，码长尽量短，编码规律尽量简单。在实际系统中，要求检、纠错易于实现，成本尽量低。信道编码的主要目标以可靠性为主，即在保证抗干扰能力尽量强的基础上，适当兼顾有效性，寻求和构造最小距离dmin比较大的码。12/14/202219检错、纠错能力对纠错编码的基本要求12/11/202219随机编码随机编码从N维矢量空间XN的qN个点中选取qK个点作为码字，可以借助近世代数理论寻找最佳的方法，也可以随机地选择。平均差错概率E(R)：可靠性函数。R：码率，表示每码元携带 的信息量，又称为传信率。临界速率R012/14/202220随机编码随机编码临界速率R012/11/202220随机编码有扰离散信道编码定理若有一离散无记忆平稳信道，其容量为C，输入符号序列长度为N。只要待传送的信息率R＜C，总可以找到一种编码方法，当N足够长时，使译码错误概率Pe＜ε，ε为任意正数。反之，当R＞C时，任何编码的Pe＞0。当N→∞时，Pe→1。与信源编码定理类似，香农第二定理只是一个存在性定理，它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可以几乎无失真地把信息传送过去。12/14/202221随机编码有扰离散信道编码定理12/11/202221第6章信道编码6.1 有扰离散信道的编码定理6.2 纠错编译码的基本原理与分析方法12/14/202222第6章信道编码6.1 有扰离散信道的编码定理12/11/2差错控制差错控制：从公式和概念两条途径来论述差错控制与信道编码的基本原理。途径一：信道编码定理的公式减小差错概率：增大码长N或增大可靠性函数E(R)增大E(R)：加大信道容量C或减小码率（传信率）R对于同样的码率，信道容量大者其可靠性函数E(R)也大。对于同样的信道容量，码率减小时其可靠性函数E(R)增大。增大C、减小R、增加N12/14/202223差错控制差错控制：从公式和概念两条途径来论述差错控制与信道编差错控制增大信道容量C扩展带宽开发新的宽带媒介：例如从电缆到光纤，从中短波到毫米波、微米波。采取信道均衡措施。加大功率提高发送功率：例如提高天线增益，提高波束的方向系数等。降低噪声：例如采用低噪声器件、滤波、屏蔽、接地、低温运行等。在纠错编码技术发展之前，主要依靠增大C来提高通信的可靠性。12/14/202224差错控制增大信道容量C在纠错编码技术发展之前，主要依靠增大C差错控制减小码率R二进制(N,K)分组码：R=K/N q进制(N,K)分组码：R=Klog2q/N降低码率的方法q、N不变而减小K：降低信息源速率，每秒少传一些信息。q、K不变而增大N：提高符号速率，占用更大带宽。N、K不变而减小q：减小信道的输入、输出符号集。用增加信道容量的冗余度来换取可靠性12/14/202225差错控制减小码率R用增加信道容量的冗余度来换取可靠性12/1差错控制增加码长N保持码率R不变，增加码长N的同时应增大信息位K。在C和R固定的情况下加大N，并不增加信道容量的冗余度。随着N增大，矢量空间XN增大，码字间距离加大，从而可靠性提高。码长N越大，实际差错概率就越能符合统计规律。增加码长N的代价是编解码算法复杂，编解码器昂贵。通过增加码长N来提高可靠性已成为纠错编码的主要途径之一12/14/202226差错控制增加码长N通过增加码长N来提高可靠性已成为纠错编码的差错控制途径二：从概念上分析纠错编码的基本原理利用冗余度噪声均化利用冗余度冗余比特与信息比特之间存在特定的相关性。若个别信息比特出错，可以利用其他比特推测出错比特，保证信息的可靠性。传输冗余比特，必然要运用冗余的资源：时间频带功率设备复杂度12/14/202227差错控制途径二：从概念上分析纠错编码的基本原理时间频带功率设差错控制噪声均化基本思想：设法将危害较大的、较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。噪声均化的方法：增加码长N：码长越长，平均每个码字中的误码元比例降低，差错概率减小。卷积码：将相关性从各个码字内扩大到码字间，使噪声分摊到码字序列而不是一个码字上。交错（或交织）：对付突发差错的有效措施。将符号流作顺序上的交换，使突发差错被均化，转换为可纠正的差错。12/14/202228差错控制噪声均化12/11/202228差错控制7654321141312111098212019181716152827262524232235343332313029入入12/14/202229差错控制76543211413121110982120191第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次：如何正确接收载有信息的信号如何避免少量差错信号对信息内容的影响纠错编码试图克服信道中噪声造成的损害基本思想：在消息通过一个有噪信道传输前，以多余符号的形式在消息中增添冗余度。通信原理THISISANINTRSTNGBOOKTHISISANINTERESTINGBOOK12/14/202230第6章信道编码信道编码是以信息在信道上的正确传输为目标的编第6章信道编码m：输入信息序列的每k个信息符号分成一段，称为信息组mi：信息元C：码字 Ci：码元r=n-k：校验元分组码：每个码字中增加的r个校验元只由本组的k个信息元产生，与其他信息组的信息元无关。记为(n,k)卷积码：增加的r个校验元既与本组信息元有关，还与前面L组信息元有关。记为(n,k,L)(m1,m2,…,mk){x0,x1,…xq-1}(c1,c2,…,cn)qkqn12/14/202231第6章信道编码m：输入信息序列的每k个信息符号分成一段，称第6章信道编码6.1 有扰离散信道的编码定理6.2 纠错编译码的基本原理与分析方法12/14/202232第6章信道编码6.1 有扰离散信道的编码定理12/11/2差错和差错控制系统分类差错符号、差错比特符号是信息比特的载体。信号差错与信息差错既有联系又有区别。符号差错概率（误码元率）指信号差错概率 误比特率指信息差错概率12/14/202233差错和差错控制系统分类差错符号、差错比特12/11/2022差错和差错控制系统分类随机差错差错始终以相等的概率独立发生于各码字、各码元和各比特之间，与前后位置和时间无关。如加性高斯白噪声突发差错由突发噪声引起的前后相关、成堆出现的差错。数学模型：双状态一阶马尔可夫链模型12/14/202234差错和差错控制系统分类随机差错12/11/20225纠错码分类从功能角度，差错码分为检错码和纠错码检错码：用于发现差错的信道码纠错码：能自动纠正差错的信道码例：要发送A和B可以采用以下三种方法：不重复：用0代表A，1代表B。重复一次：用00代表A，11代表B。 增加一位码元，传送效率降低一倍。重复两次：用000代表A，用111代表B。 增加两位码元，效率降低两倍。既不检错，又不纠错检错但不纠错既检错又纠错12/14/202235纠错码分类从功能角度，差错码分为检错码和纠错码既不检错，又不纠错码分类按照对信息序列的处理方法，有分组码和卷积码两种。分组码：将信息序列分割成k位一组后独立编解码，分组间无关。卷积码：编解码运算不仅与本组信息有关，还与前面若干组有关。按照码元与原始信息位的关系，分为线性码和非线性码。线性码：所有码元均是原始信息元的线性组合，编码器不带反馈回路。非线性码：码元并不都是信息元的线性组合，可能还与前面的码元有关，编码器可能含反馈回路。12/14/202236纠错码分类按照对信息序列的处理方法，有分组码和卷积码两种。1纠错码分类按照适用的差错类型，分成纠随机差错码和纠突发差错码两种。随机差错差错是相互独立的，不相关存在这种差错的信道是无记忆信道或随机信道突发差错指成串出现的错误，错误与错误间有相关性，一个差错往往要影响到后面一串字0010010000001001110000000突发长度=4突发长度=6用可纠独立差错的个数来衡量用可纠突发差错的最大长度来衡量12/14/202237纠错码分类按照适用的差错类型，分成纠随机差错码和纠突发差错码差错控制系统分类前向纠错方式（FEC）发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，如果传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。实时性好，适用于单工通信12/14/202238差错控制系统分类前向纠错方式（FEC）实时性好，适用于单工通检错与纠错方式自动请求重发方式（ARQ）发送端发送检错码 接收端译码器判断当前码字传输是否出错当有错时，按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字译码设备不复杂，对突发错误特别有效12/14/202239检错与纠错方式自动请求重发方式（ARQ）译码设备不复杂，对突检错与纠错方式混合纠错（HEC）FEC与ARQ方式的结合。发送端发送同时具有自动纠错和检测能力的码组，收端收到码组后检查差错情况。如果差错在码的纠错能力内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。检错、纠错能力强，译码设备复杂，应用广泛12/14/202240检错与纠错方式混合纠错（HEC）检错、纠错能力强，译码设备复与差错控制有关的基本概念码长：码字中码元的个数，用n表示汉明重量（码重）：码字中非0码元的个数，用W表示。对于二进制来说，指码字中码元1的数目。若码字C=(c1c2…cn)，则汉明距离（码距）：两个等长码字之间对应码元不相同的数目，用D表示。设两个二元码字X=(x1x2…xn)和Y=(y1y2…yn)，则有两个码字模二相加得到的新码字的重量应是这两个码字之间的汉明距离，即12/14/202241与差错控制有关的基本概念码长：码字中码元的个数，用n表示12与差错控制有关的基本概念码的最小距离dmin在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即例：码集C={0111100,1011011,1101001}最小码距是衡量该码纠错能力的重要依据从避免码字受干扰而出错的角度出发，希望码字间有尽可能大的距离，因为最小码距代表着一个码集中最不利的情况。从安全出发，应使用最小码距来分析码的检错、纠错能力。dmin=312/14/202242与差错控制有关的基本概念码的最小距离dmindmin=312与差错控制有关的基本概念错误图样在二元无记忆N次扩展信道中，差错的形式也可以用二元序列来描述，称为错误图样。设发送码字为C=(c1c2…cn)，接收码字为R=(r1r2…rn)，两者的差别为例：R=(110000)，C=(100001)E＝C⊕R=(010001)，表明接收符号系列的第2位和第6位出现了错误。12/14/202243与差错控制有关的基本概念错误图样12/11/202214检错、纠错能力差错的产生码字集合是N维矢量空间XN中的一个子集。若传输无误，接收到的码字应在码字集合内。若出现差错，有两种可能：对应到码字集合外的一点上。对应到码字集合内的另一点上。检错与纠错能力纠错码的检、纠错能力是指能够检测、纠正差错的数目。能够检错不能检错12/14/202244检错、纠错能力差错的产生能够检错不能检错12/11/2022检错、纠错能力检错能力纠错码的最小距离dmin表示从子集中一点偏移到另一点的距离。若差错数目e大于等于dmin，将导致一个码字被译成另一个码字，这种错误无法检测。若差错数目e小于dmin，则不可能从子集的一个点偏移到另一个点，即可以检测出差错。dminee≤dmin－112/14/202245检错、纠错能力检错能力dminee≤dmin－112/11检错、纠错能力纠错能力以每个码字为球心，以汉明距离t为半径作2k个球体。球体之间不相交（且不相切）的条件是：dmin=2t+1译码时，所有落在球内的接收码字都被译为位于球心的码字。纠错能力总是小于检错能力的。dmintt=INT[(dmin-1)/2]12/14/202246检错、纠错能力纠错能力dmintt=INT[(dmin-1检错、纠错能力检、纠错能力若将检错和纠错统一考虑，情况会有所变化。要增加检错能力，必须抑制纠错能力。如码字A、B的码距为7码字A发生3个差错时能够纠正；若发生4个差错时，将被译成B。即：检错和纠错能力都为3。若要提高检错能力为4，需将纠错能力减为2。若最小距离dmin的码同时能检ed、纠ec个差错，则ed+ec≤dmin-112/14/202247检错、纠错能力检、纠错能力ed+ec≤dmin-112/1检错、纠错能力对纠错编码的基本要求纠错和检错能力尽量强，编码效率尽量高，码长尽量短，编码规律尽量简单。在实际系统中，要求检、纠错易于实现，成本尽量低。信道编码的主要目标以可靠性为主，即在保证抗干扰能力尽量强的基础上，适当兼顾有效性，寻求和构造最小距离dmin比较大的码。12/14/202248检错、纠错能力对纠错编码的基本要求12/11/202219随机编码随机编码从N维矢量空间XN的qN个点中选取qK个点作为码字，可以借助近世代数理论寻找最佳的方法，也可以随机地选择。平均差错概率E(R)：可靠性函数。R：码率，表示每码元携带 的信息量，又称为传信率。临界速率R012/14/202249随机编码随机编码临界速率R012/11/202220随机编码有扰离散信道编码定理若有一离散无记忆平稳信道，其容量为C，输入符号序列长度为N。只要待传送的信息率R＜C，总可以找到一种编码方法，当N足够长时，使译码错误概率Pe＜ε，ε为任意正数。反之，当R＞C时，任何编码的Pe＞0。当N→∞时，Pe→1。与信源编码定理类似，香农第二定理只是一个存在性定理，它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可以几乎无失真地把信息传送过去。12/14/202250随机编码有扰离散信道编码定理12/11/202221第6章信道编码6.1 有扰离散信道的编码定理6.2 纠错编译码的基本原理与分析方法12/14/202251第6章信道编码6.1 有扰离散信道的编码定理12/11/2差错控制差错控制：从公式和概念两条途径来论述差错控制与信道编码的基本原理。途径一：信道编码定理的公式减小差错概率：增大码长N或增大可靠性函数E(R)增大E(R)：加大信道容量C或减小码率（传信率）R对于同样的码率，信道容量大者其可靠性函数E(R)也大。对于同样的信道容量，码率减小时其可靠性函数E(R)增大。增大C、减小R、增加N12/14/202252差错控制差错控制：从公式和概念两条途径来论述差错控制与信道编差错控制增大信道容量C扩展带宽开发新的宽带媒介：例如从电缆到光