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

第6章信道编码26.1概述•作用提高信息传输时的抗干扰能力•目的增加信息传输的可靠性•手段增加信息冗余度•名称信道码、数据传输码、差错控制码36.1概述•信道编码器在通信系统中的位置信源编码信道编码信源译码信道译码解密加密信宿信源4•分类6.1概述分组码树码线性码非线性码检错码纠错码抗随机差错码抗突发差错码代数码几何码组合码线性分组码——群码线性树码——卷积码5•最小差错概率准则理想译码器，依赖于输入概率分布。•最大似然准则实用译码准则，与最小差错概率准则等价。6.2信道译码准则66.3码例信道编译码方法的最初范例。•基本思路将码字分成两段用模二和对二元分组码进行一致性校验。•奇偶校验码只有一个校验位的汉明码。二元分组码信息位校验位奇校验、偶校验。76.3码例奇校验DES算法1100101111001010偶校验86.3码例•多个校验位的汉明码每个校验位是部分或全部信息位按模二和规则确定。N=7，k=4c4c6c5u3u2u1u0401251236013cuuucuuucuuuc4c6c5c3c2c1c096.3码例0101011可以纠正一个错误。•译码-验证校验位-错误位取反106.4线性分组码•同时具有线性特性和分组特性–把符号同时看成是运算的数–引入模2算术•二元有限域–有限个元素的集合，定义两种运算——加和乘–加法有零元，乘法有幺元–有加逆元和乘逆元–加、乘满足结合律和交换律，加和乘满足分配律116.4线性分组码•加法a+b011011001111,,,,,,(,,,)mmmmaaabbbababab•乘法ab=c101111011011()()mod()mmmmmmccxcxaaxaxbbxbxpx不可约多项式126.4线性分组码•线性分组码的基本参数码长：n信息位长：k码字数：M监督位长：r最小码距：dmin重复码000111136.4线性分组码（4，3）偶校验码奇校验码？恒比码？0101101101146.4线性分组码•衡量码的重要指标汉明重量（码重）码字中非零码元的数目。汉明重量（码重）=10110101156.4线性分组码两个码字中相应码元取不同数值的码元数。汉明距离（码距）汉明距离（码距）=1011010111010011166.4线性分组码最小汉明距离（最小码距）同一码所有汉明距离中最小的一个。（4，3）偶校验码10010000001111001010111101010110最小汉明距离（最小码距）=176.4线性分组码检错和纠错能力1检错l=dmin-12纠错t=[（dmin-1）/2]3l+t=dmin-1,tl最小汉明距离（最小码距d）：任意两码字之间的汉明距离的最小值mind186.4线性分组码检、纠错能力图示190011001110101010110001106.4线性分组码检、纠错能力图示20•汉明码简介6.4线性分组码码长：n=2^r-1信息位长：k=n-r=2^r-r-1码字数：M=2^k监督位长：r=n-k最小码距：dmin=3纠错能力：t=1216.4线性分组码•线性分组码编码cuG信息矢量生成矩阵1000101010011100101100001011G226.4线性分组码一致校验方程组0TcH111010001110101101001H校验矩阵236.4线性分组码(1101)ucuG1000101010011100101100001011G(1101001)c编码：246.4线性分组码译码（无差错）：cHT101111110=1101001=0011100010001(1101)u256.4线性分组码译码（有差错）：011011011(,,,)(,,,)(,,,)NNNyyyyccczzz接收矢量伴随式()0TTTsHyHczHzS可以指示差错的存在266.4线性分组码0120123456[]111010001110101101001TTssssHzzzzzzzz276.4线性分组码101242123530136szzzzszzzzszzzz伴随式s0s1s2错误位置错误图样101z01000000111z10100000110z20010000011z30001000100z40000100010z50000010001z60000001286.4线性分组码译码步骤：1计算伴随式，构造伴随式-差错图案表（s，e）；2对接收向量计算伴随式；3查（s，e）表得e；4纠错。296.4线性分组码•系统码线性(N，k)码生成矩阵G具有形式由此产生的码称为系统码。系统码的一致监督矩阵具有形式,kGIA,TNkHAI二元有限域上的-AT=AT码长为N，信息位长度为k的分组码称为(N，k)码。306.4线性分组码•线性分组码的性质零向量是一个码字，称为零码字两码字之和或差仍是一个码字线性性在码的所有码字上减去任一特定的码字，结果仍是这同一码的全部码字。对称性二元有限域上最小码距最小码重。316.5线性循环码•汉明码的对偶码101110001011100010111G•线性循环码1101000011010000110100001101H321000101010011100101100001011G（1）（3）（4）（2）（4）1101000011010000110100001101G6.5线性循环码336.5线性循环码循环码的多项式描述g(x)一致校验多项式)(1)(xgxxhn•编码•译码))()(mod()(xgxrxs34更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。6.5.1循环码的多项式描述35012111013211011,,,,0,1,,,,,,,,,,,,,1,2,,nninnninininniaaaaaaaaaaaaaaaaaaain121210112223101211121010,1nnnninnnnninniiinininniaxaxaxaxaaaxaxaxaxaxaaxaxaxaxaxaxa361mod1mod1niinaxxaxxaxxaxx37定义如果一个线性分组码的任意一个码字c(n元组)都是另外一个码字c’的循环移位,称此线性分组码为一个循环码.将循环码的码字用多项式c(x)，称为码多项式（简称码式）表示后，循环码集合表示C(x),,,iiCccbbCCxcxcxbxbxCx38例6.3.2如下确定的CA是线性循环码，CB是非循环的线性分组码，CC是非线性的循环码。，，39定理：（n,k）循环码C(x)中存在唯一的一个非零的，首一的和最低次为r（rn）的码多项式g(x)满足：g(x)=xr+gr-1xr-1+….+g1X+g0g0≠0r=n-k并且c(x)是码式当且仅当c(x)是g(x)的倍式40定义由上述定理确定的码式g(x)称为循环码(n,k)的生成多项式.因此(n,k)循环码的构造是如何构造生成多项式g(x)。,Cxcxcxaxgxaxk循环码由生成多项式的倍式组成41定理：g(x)是（n,k）循环码的生成多项式，当且仅当g(x)是xn-1的r=n-k次因式。42434445•§6.3.1循环码的多项式描述•§6.3.2循环码的生成矩阵•§6.3.3系统循环码•§6.3.4多项式运算电路•§6.3.5循环码的编码电路•§6.3.6循环码的伴随多项式与检测•§6.3.7BCH码与RS码466.3.2循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为01210121011,,,,,,0,,00,,,,,,,,00,0,,0,,,,,rrrrrrrknggggggggggGgggg47(n,k)循环码的校验矩阵为101010,,,0,0,00,,,,0,00,0,,,kkkkkrnhhhhhhHhhh48§6.3.1循环码的多项式描述§6.3.2循环码的生成矩阵§6.3.3系统循环码§6.3.4多项式运算电路§6.3.5循环码的编码电路§6.3.6循环码的伴随多项式与检测§6.3.7BCH码与RS码496.3.3系统循环码循环码的系统码码式为modrrcxxmxxmxgx50