《信息论与编码基础》课件汇 17 压缩编码方法-33卷积码的译码

§6.3PPM编码§6压缩编码方法1.引入2.原理3.讨论§6.3PPM编码1.引入压缩编码的模型:1)precise.精确得到信源符号的分布概率;2)Unequal.由模型产生的越大越好。1.引入?算术编码中使用的小区间联合概率若信源无记忆：算术编码§6.3PPM编码1.引入但是，信源一般是有记忆的。§6.3PPM编码1.引入§6.3PPM编码英文文本存在不同层次的冗余度:1单字符，概率不同；2字符组合，一些组合的概率高于其它；3上下文，文法规定；1.引入§6.3PPM编码AoccdrnigtoarscheearchatCmabrigde

Uinervtisy,itdeosn't

mttaerinwaht

oredrtheltteersinawrodare,theolny

iprmoetnt

tihngistahtthefristandlsat

ltteerbeattherghit

pclae.Thersetcanbeatotalmsesandyoucansitll

raeditwouthit

porbelm.Tihsisbcuseaethehuamn

mnid

deosnotraed

ervey

lteterbyistlef,butthewrodasawlohe.Amzanig!1.引入§6.3PPM编码不同层次，得到不同熵Shannon的结果---->1阶熵，4.12；无穷熵，1~2(0.6~1.3)1.引入§6.3PPM编码PPM试图利用第2/3层次的冗余度例如，‘u’in‘qu’:p(u)=0.0228;模型要求:2)Unequal.由模型产生的越大越好。p(u/q)>=0.951.引入§6.3PPM编码PPM:PredictionbyPartialMatching§6.3PPM编码*Cleary,Witten.Datacompressionusingadaptivecodingandpartialstringmatching.IEEETr

Commun,1984,32(4):396--402*Moffat.ImplementingPPMdatacompressionscheme.IEEETr

Commun,1990,38(11):1917--1921§6.3PPM编码Prof.J.Cleary§6.3PPM编码Prof.I.Witten§6.3PPM编码§6压缩编码方法1.引入2.原理

3.讨论2.原理§6.3PPM编码有记忆系统：

Markov模型N阶Markov模型，x1x2…xN

xN+1p(xN+1|x1x2…xN)2.原理§6.3PPM编码-1阶：单符号，认为符号是均衡的上下文表Contexttable0阶：单符号，符号实际概率1阶,2阶,…N阶：p(xN+1|x1x2…xN)§6.3PPM编码上下文表(第16拍):完成编码“this$is$his$hat$”0阶a:1h:3i:3s:3t:2$:41阶at:1ha:1hi:2is:3s$:3th:1t$:1$h:2$i:12阶at$:1hat:1his:2is$:3s$h:2s$i:1thi:1$ha:1$hi:1$is:1-1阶ahist$2.原理§6.3PPM编码p(a)<p(a|h)<p(a|$h)高阶Markov模型，符合压缩编码希望的:1)precise.精确得到信源符号的分布概率;2)Unequal.由模型产生的越大越好。2.原理§6.3PPM编码PPM编码，利用高阶Markov模型建模，实现高效压缩。§6.3PPM编码§6压缩编码方法1.引入2.原理3.讨论

3.讨论§6.3PPM编码(1)高效压缩英文文本，应用4阶上下文表，PPM编码的平均码长，2.2bits/symbol相同情况，0阶压缩（算术编码，或近似即信源1阶熵），平均码长，4.7bits/symbol3.讨论§6.3PPM编码(2)N阶，N的取值英文文本，N=3or4(3)资源耗费计算量；内存；(4)初始化效果差§6.4BWT编码§6压缩编码方法1.引入2.编码和解码3.讨论§6.4BWT编码1.引入hh$$$$thh$h$$iiiii$iaassstststthis$is$his$hat$is$it$his$hat§6.4BWT编码1.引入一种新的方法!1983,Wheeler,AT&TBelllab;1994,DEC;DavidWheeler(1927.2.9

–2004.12.13)§6.4BWT编码§6压缩编码方法1.引入2.编码和解码

3.讨论§6.4BWT编码2.编码和解码编码：1信源分块：固定长度字符串；2循环移位，形成置换矩阵；§6.4BWT编码待编码:ACUSAB§6.4BWT编码2.编码和解码编码：1信源分块：固定长度字符串；2循环移位，形成置换矩阵；3矩阵各行排序，形成新矩阵；§6.4BWT编码矩阵各行排序§6.4BWT编码2.编码和解码编码：1信源分块：固定长度字符串；2循环移位，形成置换矩阵；3矩阵各行排序，形成新矩阵；4编两个量：最后一列+原字符串的行号。§6.4BWT编码2.编码和解码编码:“SBAAUC”and“1”§6.4BWT编码2.编码和解码例子：this$is$his$hat$is$it$his$hat无单符号游程待编码的最后一列:hh$$$$thh$h$$iiiii$iaassststst§6.4BWT编码2.编码和解码解码：2由最后一列，排序，得第一列；1解两个量：最后一列+原字符串的行号。§6.4BWT编码2.编码和解码§6.4BWT编码2.编码和解码解码：2由最后一列，排序，得第一列；1解两个量：最后一列+原字符串的行号。3由第一列和最后一列的字母位置关系，推导出任一行；§6.4BWT编码2.编码和解码§6.4BWT编码2.编码和解码解码：2由最后一列，排序，得第一列；1解两个量：最后一列+原字符串的行号。3由第一列和最后一列的字母位置关系，推导出任一行；4由原始字符串行号，得之；§6.4BWT编码§6压缩编码方法1.引入2.编码和解码3.讨论

§6.4BWT编码3.讨论块模式性能：压缩性能，计算量最后一列适合编码：字符局部聚集§6.5LZ编码§6压缩编码方法1.引入2.编解码§6.5LZ编码1.引入ZivLempel§6.5LZ编码1.引入ZivJ&LempelA.Compressionofindividualsequencesviavariable-ratecoding.IEEETrIT,1978,24(5):530--536ZivJ&LempelA.Auniversalalgorithmforsequentialdatacompression.IEEETrIT,1977,23(3):337--343§6.5LZ编码§6压缩编码方法1.引入2.编解码§6.5LZ编码总的思想：基于字典字典如何构造？标号如何给出？待编码词语，找字典中的词语字典中的词语，用该词语的标号编码§6.5LZ编码2.LZ77的编码LZ77字典：过去出现的词语在固定长的窗口中，检查过去出现的词语§6.5LZ编码2.LZ77的编码码字：窗口中短语的偏移位置；短语的长度；匹配字符之外的新的第一个字符；§6.5LZ编码2.LZ77的编码例子this$is$his$hat$is$it$his$hat约定：窗口长度为8个字符§6.5LZ编码事件位置长度新字符

(3bit)(3bit)(3bit)0: 4 1 h1: 0 2 $2: 5 3 h3: 4 4 a4: 0 0 t5: 0 1 i6: 1 2 i7: 2 2 h8: 1 3 h9: 0 0 a10: 0 2 #LZ77:3.3b/s§6.5LZ编码LZ77的编码步骤§6.5LZ编码LZ77的解码步骤§6.6预测与变换§6压缩编码方法1.预测2.变换§6.6预测与变换有损编码常用的基本手段：

预测－－时间或空间域变换－－变换域§6.6预测与变换1.预测（1）预测的两个阶段：训练/使用（2）为什么预测有助于压缩§6.6预测与变换1.预测（1）预测器的使用预测，用以前的值估计当前或以后的值。线性预测：§6.6预测与变换1.预测（1）预测器的使用借助预测误差进一步改进预测精度：§6.6预测与变换1.预测（2）预测器的训练一般采用“最小均方误差”（MMSE）准则，即希望预测误差的均方差最小：任务：求解预测器系数{a}和{b}。§6.6预测与变换1.预测（1）预测的两个阶段：训练/使用（2）为什么预测有助于压缩§6.6预测与变换1.预测（2）为什么预测有助于压缩预测编码：不对原信号编码、而对误差信号编码从信息论角度，统计“熵”。设计一个实验，统计预测前后的信源一阶熵§6.6预测与变换1.预测（2）为什么预测有助于压缩设计实验1）取信号：语音信号§6.6预测与变换设计实验2）只是取简单的一阶dpcme(k)=x(k)–x(k-1)§6.6预测与变换设计实验3）取到直方图取N=64个bins：离散化误差信号分布原信号分布§6.6预测与变换设计实验4）归一化为“概率”，为了求取“熵”p(x):0~0.2671p(e):0~0.3856§6.6预测与变换设计实验5）计算信源一阶熵H(x):3.4927H(e):3.1407§6.6预测与变换1.预测（2）为什么预测有助于压缩从信息论角度，统计“熵”：预测之后，信源熵是减小的！§6.6预测与变换§6压缩编码方法1.预测2.变换§6.6预测与变换2.变换变换编码在音频编码、图象编码中的应用极广。目前，图象有损编码几乎都使用了变换编码。变换：将信号由某类域（例如，语音的时间域、图象的空间域）转到另一域（如频域、小波域）上去分析。§6.6预测与变换2.变换图像压缩编码中主要使用的变换：DCT小波变换§6.6预测与变换一维DCT基函数的时域图（N=8）12345678-0.500.512345678-0.500.512345678-0.500.512345678-0.500.512345678-0.500.512345678-0.500.512345678-0.500.512345678-0.500.5§6.6预测与变换二维DCT基函数的空域图（N=8，N*N=64）§6.6预测与变换2.变换一个DCT的例子变换前的图象矩阵§6.6预测与变换2.变换变换后的DCT系数矩阵低频高频§6.6预测与变换2.变换图像信号DCT系数图像信号DCT系数256*256灰度图的三层级小波分解§6.6预测与变换2.变换大多数图象在局部区域的象素值是缓变的，从频率的角度来看，能量主要集中在低频带。对高频数据作适当的丢弃（量化），一般会在高频区域产生大量的零，此时再辅之以熵编码，可实现对图象数据的高效压缩。§6.6预测与变换2.变换为什么变换有助于压缩设计实验1）取信号：图像信号2）做变换：DCT系数§6.6预测与变换为什么变换有助于压缩3）取直方图§6.6预测与变换为什么变换有助于压缩4）转为“概率”空间域的“熵”是7.321bits/binsdct域的“熵”是2.239bits/bins5）计算“熵”§6.6预测与变换2.变换为什么变换有助于压缩从信息论角度，统计“熵”：变换之后，信源熵是减小的！§6.6预测与变换§6压缩编码方法1.预测2.变换§6.7小结§6压缩编码方法1.从信息论角度看压缩编码2.无损压缩编码方法的实际性能比对3.有损压缩编码方法的实际性能比对§6.7小结1.从信息论角度看压缩编码单符号变长编码算术编码PPM编码BWT编码LZ编码预测变换§6.7小结1.从信息论角度看压缩编码单符号变长码利用统计冗余度H(X)<=lmean

<H(X)+1算术编码扩展信源编码（假设信源是无记忆的）

lmean

－－>H(X)§6.7小结1.从信息论角度看压缩编码PPM编码利用信源符号之间的相关性lmean

－－>H(XN|X1…XN-1)（*）条件熵H(XN|X1,…,XN-1)随N的增加是非递增的，

即：H(XN|X1,…XN-1)≤H(XN-1|X1,…XN-2)≤…≤H(X2|X1)≤H(X1)

（*）称H∞为平稳信源的极限熵或极限信息量。

§6.7小结1.从信息论角度看压缩编码BWT编码利用信源符号之间的相关性lmean

－－>H(X1|X2…XN)PPM利用前向条件概率BWT利用后向条件概率Shannon：前向条件熵≈

后向条件熵§6.7小结1.从信息论角度看压缩编码LZ编码利用信源符号之间的相关性lmean

－－>H(X1X2…XN)（*）称H∞为平稳信源的极限熵或极限信息量。

§6.7小结1.从信息论角度看压缩编码预测和变换利用信号之间的相关性处理之后，信号分布趋向集中通常处理后，大多数值是小值§6.7小结§6压缩编码方法1.从信息论角度看压缩编码2.无损压缩编码方法的实际性能比对3.有损压缩编码方法的实际性能比对§6.7小结2.无损压缩编码方法的实际性能比对pack(Huffmancoder,character-based)huffword(Huffmancoder,word-based)char(arithmeticcoder)ppm(ppm+arithmeticcoder)bzip2(bwt+Huffmancoder)gzip-f(LZ77,fastoption)gzip-b(LZ77,bestcompressionoption)§6.7小结相对速度压缩率编码解码bpc%方法null0.20.28.0100.0pack0.60.94.5356.6huffword2.20.92.9536.9char2.94.04.4956.1ppm5.35.92.1126.4bzip25.52.02.2327.9gzip-f

1.00.42.9136.4gzip-b7.00.32.5331.6§6.7小结§6压缩编码方法1.从信息论角度看压缩编码2.无损压缩编码方法的实际性能比对3.有损压缩编码方法的实际性能比对§6.7小结3.有损压缩编码方法的实际性能比对语音编解码客观性质量评估：ITU-TPESQ问题§6压缩编码方法图片压缩压缩图片两幅bmp原始图：压缩图片两种压缩方法：JPGrar压缩图片对自然图的处理实验1original:布布.bmp770k-->品质因子100：布布100.jpg355k-->布布100.rar

355k.压缩图片对自然图的处理实验2original:布布.bmp770k-->品质因子50：布布50.jpg59k-->布布50.rar

59k.压缩图片对自然图的处理实验3original:布布.bmp770k-->布布.rar

368k

压缩图片实验4original:文字.bmp242k

-->品质因子100（无损？不是）：文字100.jpg195k-->文字100.rar

190k.对文字图的处理压缩图片对文字图的处理实验5original:文字.bmp242k

-->品质因子50（低质量JPEG，质量明显很差）：文字50.jpg97k

-->文字50.rar

95k.压缩图片对文字图的处理实验6original:文字.bmp242k

-->文字.rar

18k.压缩图片1对自然图，JPEG压缩是有效的（原始770k->品质因子50,59k，质量劣化不明显）；但对文字图则不行（原始242k->品质因子50,97k，质量明显较差）。对文字图，rar的压缩效果非常好（242k->18k）。2JPEG压缩后，再用rar压，无用。压缩图片为什么？§7有噪信道编码定理§7.1噪声信道中的编码§7.2信道编码分类§7.3信道译码及译码规则§7.4有噪信道编码定理§7.1噪声信道中的编码数字通信系统模型RC信源信道信宿噪声信源编码信源译码信道编码信道译码调制解调m（保密编码）（解密）降低错误译码概率Pe

一、信道编码的任务

信源检错、纠错编码器编码信道检错、纠错译码器信宿噪声源数字通信系统简化模型§7.1噪声信道中的编码一、信道编码的任务

信息序列码字接收序列信息序列估值错误图样目的：降低错误译码概率PE。对象：信息序列（设码元间彼此无关且等概出现）。

方法：在传输的信息码之中按一定规律产生一些附加码元，经信道传输，在传输中若码字出现错误，收端能利用编码规律发现码的内在相关性受到破坏，从而按一定的译码规则自动纠正或发现错误，降低误码率。二、信道编码概念

§7.1噪声信道中的编码

在保持一定传输信息速率条件下，通过增加一定的码元多余度，使输出的码字具有特定的相关性，从而使收端易于发现或纠正由于信道噪声而引起的传输错误。实质：二、信道编码概念

§7.1噪声信道中的编码增加多余度增强相关性q=rk个k维矢量信息序列禁用码组许用码组码字编码过程n重矢量rn个信道编码器MC校验元信息序列码字编码规则rk个二、信道编码概念

§7.1噪声信道中的编码（mk-1mk-2…m0）（cn-1cn-2…c0）n>k§7有噪信道编码定理§7.1噪声信道中的编码§7.2信道编码分类§7.3信道译码及译码规则§7.4有噪信道编码定理§7.2信道编码分类纠错码非线性码线性码分组码卷积码循环码非循环码纠随机错误码纠突发错误码纠随机与突发错误码检错码纠错码纠删码能发现错误的码能发现错误且能纠正错误的码能纠正删除错误的码线性叠加性例:

（4,2）分组码非线性码分组码框图卷积码框图§7.2信道编码分类卷积码示例§7.5信道编码分类分组码示例§7.5信道编码分类纠错码非线性码线性码分组码卷积码循环码非循环码纠随机错误码纠突发错误码纠随机与突发错误码0010011，0100110，0110101，11010101011111，1001100,1111001，0000000(7,3)线性分组码0011101，101001100000000111010，1110100，1101001，0100111，1001110，循环码系统码：每个码字的前k位（Cn-1Cn-2…Cn-k）与k位信息序列（mk-1…m1m0）依次对应相等，称为信息元，其后（n-k）位根据校验关系得到，添加于信息元之后，称为监督元或校验元。§7.5信道编码分类§7有噪信道编码定理§7.1噪声信道中的编码§7.2信道编码分类§7.3信道译码及译码规则§7.4有噪信道编码定理C0C1Ci┋Cj┋C2k-1收端一、信道传输模式

PE～信道传输特性

PE～编译码方法C2k┋Ci’┋C2n-1许用码组禁用码组C0C1┋Ci┋C2k-1许用码组发端不可检出错误传输正确传输可检出错误传输§7.3信道译码及译码规则例1.BSC01101－p=1/31－p=1/3p=2/3p=2/3PE=P(R=1|C=0)P(C=0)+P(R=0|C=1)P(C=1)收0→0收1→1译码一收0→1收1→0译码二PE=P(R=0|C=0)P(C=0)+P(R=1|C=1)P(C=1)译码本质：对码字进行分类§7.3信道译码及译码规则一、信道传输模式

√

设：信道输入：X={a1…ar}，输出：Y={b1…bs}

F(bj)=ai(i=1…r，j=1…s)译码规则：例1（续）：收：Y:｛0，1｝，发：X:｛0，1｝译码规则一译码规则二(whenp<1/2)(whenp>1/2)二、译码规则§7.3信道译码及译码规则

①

最小错误译码准则(MEPD)

F(bj)=a*，PE=min

②

最大后验概率准则(MPPD)or(MAP)

F(bj)=a*，P(a*|bj)≥P(ai|bj)

，(i=1…r)

③

最大联合概率准则(MJPD)

F(bj)=a*，P(a*bj)≥P(aibj)，

(i=1…r)

④

最大似然译码准则(MLD)

F(bj)=a*，P(bj|a*)≥P(bj|ai)，

(i=1…r)

常用准则§7.3信道译码及译码规则二、译码规则

等价在信道输入等概时，MLD与MJPD等价译码规则表§7.3信道译码及译码规则二、译码规则

（6，3）码及译码表§7.3信道译码及译码规则二、译码规则§7有噪信道编码定理§7.1噪声信道中的编码§7.2信道编码分类§7.3信道译码及译码规则§7.4有噪信道编码定理有噪信道编码定理（香农第二定理）设某离散无记忆信道有r个输入，s个输出，信道容量为C，在输入rn个符号中选出M个码字组成一种码，设ε是任意小的正数。若M≤2

n(C-ε)

，则存在这样的码及相应的译码规则，当n足够大时，使信道输出的错误概率PE任意小；若M=2

n(C+ε)

则无论n多大，也找不到一种编码，使译码错误概率任意小。§7.4有噪信道编码定理§7.4有噪信道编码定理例1直接传信息码（0：白，1：黑）：无抗干扰力，PE＝p=0.01（3，1）重复码：§7.4有噪信道编码定理例1直接传信息码（0：白，1：黑）：无抗干扰力，PE＝p=0.01n=1PE=10-2n=3PE=3＊10-4n=5PE=10-5n=7PE=4＊10-7n=9PE=10-8n=11PE=5＊10-10R=1R=1／3R=1／5R=1／7R=1／9R=1／11结论：※

码长n↑，PE↓※

单纯的码长n↑，R↓(冗余增大)§7.4有噪信道编码定理例2．（5.2）线性分组码00011011编码000000110110111110100000000001000100010001000100001000100011011010110001111001011110111100010010111010111101101010111111001110011010011101001101011011110001001001010010111100111001输入编码码字接收码字信道

在码长较长时，采用合适的编码和译码方法，能使错误概率降低，而不降低信息传输率！有噪信道编码定理（香农第二定理）设某离散无记忆信道有r个输入，s个输出，信道容量为C，在输入rn个符号中选出M个码字组成一种码，设ε是任意小的正数，若M≤2

n(C-ε)

，则存在这样的码及相应的译码规则，当n足够大时，使信道输出的错误概率PE任意小；若M=2

n(C+ε)

则无论n多大，也找不到一种编码，使译码错误概率任意小。§7.4有噪信道编码定理表述二：

若在信息传输率R不大于信道容量C（即R≤C-），则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果R>C，则不可能找到一种编码，使输出端错误概率任意小。

有噪信道编码定理（香农第二定理）§7.4有噪信道编码定理说明：1、定理纠正了传统观点：可靠性和有效性是一对不可调和的矛盾，为信道编码理论和技术的研究指明了方向。2、定理仅指出编码的存在性，未给出编码的具体方法。3、定理指出：R<C是可靠传输的必要条件，进一步证明：R=C时，任意小的差错概率也是可以达到的。证明基本条件：1）随机编码

2）码长→∞3）最大似然译码

有噪信道编码定理（香农第二定理）§7.4有噪信道编码定理§8线性分组码的基本原理

§8.1线性分组码基本概念§8.2线性分组码的编译码方法§8.3线性分组码的纠错性能§8.4Hamming码

线性分组码定义生成矩阵一致校验矩阵§8.1线性分组码基本概念分组码信息序列码字M=(mk-1…m0)C=(cn-1…c0){M}{C}f(.)2k2k一、线性分组码定义线性映射：其中，例1：例2：非线性分组码§8.1线性分组码基本概念例3：例4:线性分组码§8.1线性分组码基本概念

如果一个（n，k）分组码的编码规则可用线性方程组表示，则称该码为（n，k）线性分组码。

GF(2)域上的n维线性空间的一个k维子空间Vn,k

构成一个二进制（n，k）线性分组码。群码一、线性分组码定义§8.1线性分组码基本概念定理8.1：一个（n，k）线性分组码中非零码字的最小重量等于码的最小距离。一、线性分组码定义§8.1线性分组码基本概念定义8-1：一个码字c中非零码元的个数称为该码字 的（汉明）重量，记为W(c)。

定义8-2：码集中非零码字的汉明重量的最小值，称为该码的最小汉明重量，记为Wmin(C)。

定义8-3：两个长度相同的码字c和c’中，对应位码 元不同的码元数目称为这两个码字间的汉明距 离，简称码距，记为d(c；c’)。

定义8-4：码集中码字间汉明距离时为最小值称为该 码的最小汉明距离，记为d0或dmin。二、生成矩阵§8.1线性分组码基本概念二、生成矩阵§8.1线性分组码基本概念习题系统码二、生成矩阵§8.1线性分组码基本概念小结：行：基本码字C=MG二、生成矩阵§8.1线性分组码基本概念小结：C=MG二、生成矩阵§8.1线性分组码基本概念小结：行：基本码字C=MG列：某位码元的编码方式例5：(5，2)线性分组码的校验情况一致校验矩阵§8.1线性分组码基本概念三、一致校验矩阵§8.1线性分组码基本概念行：一个校验方程列：某位码元受约束情况CNVN三、一致校验矩阵§8.1线性分组码基本概念GHT=0§8线性分组码的基本原理

§8.1线性分组码基本概念§8.2线性分组码的编译码方法§8.3线性分组码的纠错性能§8.4Hamming码

线性分组码的编码标准阵列译码伴随式译码一、线性分组码的编码§8.2线性分组码的编译码方法C=MG一、线性分组码的编码§8.2线性分组码的编译码方法例1：c6c5c4c3c2c1c0m2m1m0标准阵列译码规则表码字C（0）C（1）C（2）C（2k-1）(00…0)子群…子集

…m0m1m2m2k-1禁用码组

E1

E1+C（1）

E1+C（2）

E1+C（2k-1）

…E2

E2+C（1）

E2+C（2）

E2+C（2k-1）

…E2n-k-1

E2n-k-1+C（1）E2n-k-1+C（2）…E2n-k-1+C（2k-1）陪集二、标准阵列译码§8.2线性分组码的编译码方法例2：（4，2）线性分组码译码表：禁用码组100011110010010101000011111010010001011010111100三、标准阵列译码§8.2线性分组码的编译码方法三、标准阵列译码§8.2线性分组码的编译码方法

收到的R落到标准阵列中哪一列(设为第i列),则将其译为该列的第一个矢量,即许用码字Ci。

译码过程：

标准阵列译码方法等价于最大似然译码，当信息组等概时可保证译码错误概率最小。实际上各陪集首选取原则即是选取出现概率最大的错误图样E。定理8.2：每一个（n，k）线性分组码都能纠正2n-k个错误图样。

三、伴随式译码伴随式S:S=（sr-1…s1s0）§8.2线性分组码的编译码方法定理8.3：标准阵列中每个陪集的2k个矢量都有相同的伴随式，且不同的陪集有不同的伴随式。例6（续）三、线伴随式性分组码的译码§8.2线性分组码的编译码方法例3：（4，2）码的伴随式译码

Step1：由R求SS=RHTStep2：由S求E令E＝(e3e2e1e0)，Step3：纠错

C=R+E三、伴随式译码§8.2线性分组码的编译码方法S0R=(r3r2r1r0)r0r1r2r3S1e0e2e3串行输出伴随式计算错型产生C=R+E^三、伴随式译码c0c1c2c3§8.2线性分组码的编译码方法r0r1rn-1s0s1sr-1e0e1en-1c0c1cn-1（n，k）线性分组码一般译码电路S=RHTS=EHT^C=R+E接收矢量缓存器伴随式计算电路错误图样产生器n级移位寄存器输出三、伴随式译码§8.2线性分组码的编译码方法（6，3）码标准阵列§8.2线性分组码的编译码方法§8线性分组码的基本原理

§8.1线性分组码基本概念§8.2线性分组码的编译码方法§8.3线性分组码的纠错性能§8.4Hamming码

码的纠检错能力与最小距离一致校验矩阵与伴随式线性分组码的纠错性能基本码限定义8-5：如果一种码的任一码字内出现了e位或e位以内的错误仍能自动发现，则称该码的检错能力为e。

定义8-6：如果一种码的任一码字在传输中出现了t位或t位以内的错误仍能自动纠正，则称该码的纠错能力为t。一、码的纠检错能力与最小距离§8.3线性分组码的纠错性能定理8.5：若码的最小距离满足d0≥e+1，则码的检错 能力为e。

定理8.6：若码的最小距离满足d0≥2t+1，则码的纠错 能力为t。一、码的纠检错能力与最小距离§8.3线性分组码的纠错性能定理8.7：对于任意（n，k）分组码，若要求：码的检错能力为e，则码的最小距离d0≥e+1；码的纠错能力为t，则码的最小距离d0≥2t+1。二、伴随式与一致校验矩阵的关系例1：（7，3）线性分组码设E＝(e6e5e4e3e2e1e0)S=RHT=EHT§8.3线性分组码的纠错性能(n,k)要想纠t个错，则S必须与可能的错误图样对应。结论：S是E中不为0的码元位所对应的H矩阵的列的线性组合。二、伴随式与一致校验矩阵的关系§8.3线性分组码的纠错性能定理8.8：任一线性分组码,若要纠正小于等于t个 错，其充分必要条件是H矩阵中任2t列线性无 关。

例2:若要纠t＝1个错，则H矩阵中任意两列必须线性 无关。定理8.9：

(n,k)线性分组码具有最小距离d的充分必 要条件是H矩阵中任意d-1列线性无关,至少有 一种d列线性相关。三、码的一致校验矩阵与纠错能力

上述定理是构造满足纠错要求的线性分组码的基础H矩阵列排序不同，码集不同，但纠错能力不变§8.3线性分组码的纠错性能三、码的一致校验矩阵与纠错能力§8.3线性分组码的纠错性能例3：设计t=1，n=5的线性分组码。d0=3四、基本码限定理8.10：任一

（n，k）线性分组码d0≤n-k+1。汉明限定理8.11：若[C]是k维n重二元码，当已知k时，若 要使[C]能纠正t个以内的错误，则必须有r=n-k

位校验元，且r满足：汉明限Singleton限§8.3线性分组码的纠错性能（极大最小距离码）（完备码）§8线性分组码的基本原理

§8.1线性分组码基本概念§8.2线性分组码的编译码方法§8.3线性分组码的纠错性能§8.4Hamming码Hamming码定义

Hamming码编码

Hamming码译码扩展Hamming码定义8-7：若H矩阵的列是由不全为0且互不相同的 所有二进制m（≥2的正整数）重组成，则由 此H矩阵得到的线性分组码称为GF(2)上的 （2m-1，2m-1-m，3）汉明码。§8.4Hamming码定理8.12：若线性分组码能纠正一个错误，当且仅 当其H矩阵没有全零列，且H的任意两列都不 相等。一、Hamming码的定义例1：（7，4）汉明码系统码A:1＋2→11＋3→21＋2＋3→1系统码B:§8.4Hamming码一、Hamming码的定义编码器（7，4）汉明码B:二、Hamming码的编码§8.4Hamming码（7，4）汉明码B:译码器三、Hamming码的译码§8.4Hamming码伴随式计算错型产生纠错汉明码

对汉明码的所有码字加1位全校验位，使得校验位数从m增加到m+1，码长由2m-1增加到2m，信息位数保持不变，这种码就称为扩展汉明码。扩展汉明码四、扩展Hamming码§8.4Hamming码系统汉明码的校验矩阵扩展汉明码的校验矩阵扩展汉明码最小码距离：四、扩展Hamming码§8.4Hamming码思考： 扩展汉明码增加的校验位能起到什么作用？四、扩展Hamming码§8.4Hamming码定义8-8：如果一种码的任一码字在传输中出现了t位或t位以内的错误都能自动纠正，当出现多于t而小于e＋1个错误时（e>t），此码能检出而不造成译码错误，则称该码能纠t个错误同时检出e个错误。定理5.13：若码的最小距离满足d0≥e+t+1（e>t），则 该码能纠t个错误同时检出e个错误。§8线性分组码的基本原理

1．已知一个(7,4)码的生成矩阵为

G0=(1)求出该码的全部码字；(2)求出该码的一致校验矩阵H0。2．对题1给出的(7,4)码列出标准陈列译码表。习题：（P161：T1）（P161：T2）§8线性分组码的基本原理

3．令(6,3)码的一致校验矩阵为H0=

（1）若接收矢量分别为Rl=（110110），R2=（010100），分别求对应的伴随式。（2）试求该码的最小距离和纠错能力。4．对于一个码长为15的线性码，若允许纠正2个随机错误，需多少个不同的伴随式？至少要多少位校验元？（P161：T3）（P162：T7）习题：1.一个(8,4)系统码，其信息序列为（m3m2m1m0）码字序列为（c7c6c5c4c3c2clc0）它的校验方程为

c3=m3+m1+m0c2=m3+m2+m0c1=m2+m1+m0c0=m3+m2+m1

求出该码的一致校验矩阵H0并证明该码最小重量为4。思考题：

2.已知(6,3)码为(7,4)汉明码的缩短码，求它的生成矩阵和一致校验矩阵。§8线性分组码的基本原理

（P162：T4）（P162：T6）§9.1循环码的基本概念§9循环码基本原理§9.2循环码的编码§9.3循环码的一般译码方法§9.1循环码的基本概念§9循环码基本原理§9.2循环码的编码§9.3循环码的一般译码方法§9.1循环码的基本概念什么是循环码？如何用代数理论来描述循环码？如何构造循环码？待解决的问题：(7,4)线性分组码所有码字(0000000)(0001011)(0010110)(0100111)(1000101)(0011101)(0101100)(1001110)(0110001)(1010011)(1100010)(0111010)(1011000)(1110100)(1101001)(1111111)(0000000)(0001011)(0010110)(0100111)(1000101)(0011101)(0101100)(1001110)(0110001)(1010011)(1100010)(0111010)(1011000)(1110100)(1101001)(1111111)§9.1循环码的基本概念100010110001010001011001011001011001011000011000111000100100111100111000111010111010111010011010011010011010011111111110000000§9.1循环码的基本概念具有循环移位特性的线性分组码就是循环码。

定义在任一个GF(q)(q为素数或素数幂)上的n维线性空间Vn中，一个n重子空间Vn,k∈Vn，若对任何一个C=(cn-1,cn-2,…,c0)∈Vn,k，恒有C1=(cn-2,…,c0,cn-1)∈Vn,k，则称Vn,k是循环子空间或循环码。一、循环码的定义§9.1循环码的基本概念二、循环码的多项式描述C=(cn-1,cn-2,…,c1,c0)C(1)=(cn-2,cn-3,…,c0,cn-1)√√左循环移位后§9.1循环码的基本概念码多项式C(2)=(cn-3,…,c0,cn-1,cn-2)

定理若C(x)是n长循环码中的一个码多项式，则xiC(x)按模xn+1运算的余式必为循环码中另一码多项式。§9.1循环码的基本概念二、循环码的多项式描述三、生成多项式

定理一个二进制(n,k)循环码中有唯一的非零最低次多项式g(x)，且其常数项为1。+g0=0g0=10001011011000100101101100010010110010001011011000000000001110101010011001110111010011001110111010001001111111111

定义

如果一个码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。§9.1循环码的基本概念(7,4)循环码

定理GF(2)上的(n,k)循环码中，存在有唯一的n-k次首1多项式g(x)，使得每一码多项式C(x)都是g(x)的倍式，且每一小于或等于n-1次的g(x)的倍式一定是码多项式。

定理设g(x)是(n,k)循环码[C(x)]中的一个次数最低的多项式（g(x)≠0），则该循环码由g(x)生成，并且g(x)|(xn+1)。例可以构建出几种循环码？§9.1循环码的基本概念三、生成多项式码多项式码字（0010111）（0101110）（1011100）（0111001）（1110010）（1100101）（1001011）（0000000）只要知道了xn+1的因式分解，用它的各个因式的乘积，便能得到很多个不同的循环码。（7，3）循环码§9.1循环码的基本概念§9.1循环码的基本概念什么是循环码？如何用代数理论来描述循环码？如何构造循环码？已解决的问题：§9.1循环码的基本概念生成多项式与生成矩阵的关系？如何设计循环码的编码器？遗留的问题：思考与练习§9.1循环码的基本概念

2.设在GF(q)上xn+1可分解称t个不同的不可约多项式的乘积，问有多少个码长为n的q元循环码？

1.任何循环码中一定存在全零码字吗？§9.1循环码的基本概念§9循环码基本原理§9.2循环码的编码§9.3循环码的一般译码方法§9.1循环码的基本概念§9循环码基本原理§9.2循环码的编码§9.3循环码的一般译码方法如何构建循环码的编码器？待解决的问题：§9.2循环码的编码(7,4)循环码生成矩阵生成多项式+++m3m2m1m0c6c5c4c3c2c1c0§9.2循环码的编码§9.2循环码的编码如何用生成多项式来生成码多项式？系统码C=(cn-1,cn-2,…,c1,c0)=(mk-1,mk-2,…,m1,m0,rn-k-1,rn-k-2,…,r1,r0)信息位校验位一、多项式除法运算电路§9.2循环码的编码D0D1Dr-2+Dr-1+++grgr-1g2g1g0A(x)例D0D1D2++x3x1§9.2循环码的编码一、多项式除法运算电路D0D1D2++x3x1§9.2循环码的编码节拍输入寄存器内容输出D0D1D2000000111000211100300110401111510011商式余式D0D1D2++门1门2输入m(x)输出C(x)§9.2循环码的编码二、循环码编码器n-k

级编码器例（7，4）循环码§9.2循环码的编码节拍信息位输出码字0000111110200011300111411011500116000170000D0D1D2++门1门2输入m(x)输出C(x)§9.2循环码的编码二、循环码编码器k级编码器各项系数为0。cn-k

cn-k+1

cn-2cn-1h0h1hk-2hk-1§9.2循环码的编码二、循环码编码器如何构建循环码的编码器？已解决的问题：§9.2循环码的编码除法电路组合逻辑电路乘法电路如何设计循环码的译码器？遗留的问题：§9.2循环码的编码§9.2循环码的编码思考与练习D0+门1门2输入输出

D0D1++门1门2输入输出奇偶校验码（3，1）重复码§9.1循环码的基本概念§9循环码基本原理§9.2循环码的编码§9.3循环码的一般译码方法如何构建循环码的译码器？待解决的问题：§9.3循环码的一般译码方法线性分组码的伴随式译码§9.3循环码的一般译码方法1.计算伴随式；2.根据伴随式估计错误图样；3.利用错误图样对接收序列进行错误纠正，得到译码器输出的估计码字。一、伴随式计算和错误检测§9.3循环码的一般译码方法一、伴随式计算和错误检测§9.3循环码的一般译码方法一、伴随式计算和错误检测§9.3循环码的一般译码方法一、伴随式计算和错误检测§9.3循环码的一般译码方法若S(x)=0，则R(x)是合法码字；若S(x)≠0，则R(x)不是合法码字；若E(x)<g(x)=n-k，则S(x)≠0；(n,k)循环码至多能检测长度等于n-k的突发错误，以及检测所有使S(x)≠0的错误图样。二、伴随式计算电路性质及一般译码器§9.3循环码的一般译码方法

定理若S(x)是R(x)的伴随式，则R(x)的循环移位xR(x)(在模xn+1运算下)的伴随式S1(x)，是S(x)在伴随式计算电路中无输入时（自发运算）右移1位的结果，即§9.3循环码的一般译码方法二、伴随式计算电路性质及一般译码器

定理

xjR(x)的伴随式Sj(x)≡xjS(x)modg(x),j=0,1,…,n-1。而任意多项式a(x)乘R(x)所对应的伴随式为§9.3循环码的一般译码方法二、伴随式计算电路性质及一般译码器例二进制（7，4）循环码§9.3循环码的一般译码方法二、伴随式计算电路性质及一般译码器D0D1D2+++与门S0S1S2输入输出7级缓存器门000110000100001011000111011101110000111111011010011000§9.3循环码的一般译码方法输入缓存译码D0D1D2+++与门S0S1S2输入输出7级缓存器门（7，4）循环码完整译码器§9.3循环码的一般译码方法伴随式计算电路组合逻辑电路§9.3循环码的一般译码方法循环码的通用译码器（梅吉特译码器）—输入R(x)输出纠错信号门k级缓存器伴随式计算电路1伴随式计算电路2组合逻辑电路如何构建循环码的译码器？已解决的问题：§9.3循环码的一般译码方法D0D1++门1门2输入输出思考与练习生成多项式一致校验矩阵§9.3循环码的一般译码方法（3，1）重复码译码器设计§9.3循环码的一般译码方法D0D1++门+与门输入输出3级缓存器（3，1）重复码译码器设计思考与练习§10.1卷积码的定义及其应用§10卷积码基础§10.2卷积码的译码§10.1卷积码的定义及其应用§10卷积码基础§10.2卷积码的译码什么是卷积码？待解决的问题：§10.1卷积码的定义及其应用如何对卷积码进行描述？卷积码的应用情况是怎样的？一、卷积码的基本概念§10.1卷积码的定义及其应用卷积码框图：分组码框图：

S/P（串/并）P/S（并/串）无记忆编码1kn1S/P（串/并）P/S（并/串）有记忆编码1k0n01每个编码分组不仅取决于当前单位时间对应的k0比特信息组，而且与前m个信息组有关。§10.1卷积码的定义及其应用一、卷积码的基本概念D0D1+++mkck1ck2ckn0=2k0=1m=2（2，1，2）卷积码编码存储§10.1卷积码的定义及其应用D0D1+++mkck1ck2ckmkmk-1mk-2mkmk+1mk-1mkmk+2mk+1ckck+1ck+2编码约束度编码约束长度n0(m+1)

（2，1，3）卷积码

二、卷积码的描述D1D0D2mkck1ck2ck§10.1卷积码的定义及其应用D1D0D2mkck1ck2ck§10.1卷积码的定义及其应用M=(m0,m1,m2,…)=(100…)C=(c0,c1,c2,…)=(11,01,11,11,00,00,00…)二、卷积码的描述（2，1，3）卷积码

§10.1卷积码的定义及其应用M=(m0,m1,m2,…)=(100…)C=(c0,c1,c2,…)=(11,01,11,11,00,00,00…)M=(11100…)

=(100…)+(0100…)+(0010…)+…二、卷积码的描述C=(11,01,11,11,00,00,00,…)+(00,11,01,11,11,00,00,…)+(00,00,11,01,11,11,00,…)+…

=(11,10,01,01,00,11,00,…)生成矩阵基本生成矩阵1.生成矩阵描述

§10.1卷积码的定义及其应用M=(m0,m1,m2,…)=(100…)C=(c0,c1,c2,…)=(11,01,11,11,00,00,00…)二、卷积码的描述D1D0D2mkck1ck2ck1+D2+D31+D+D2+D31.生成矩阵描述

§10.1卷积码的定义及其应用二、卷积码的描述2.多项式描述生成多项式矩阵(11,10,01,01,00,11)子生成元G=[13,17]

§10.1卷积码的定义及其应用二、卷积码的描述3.状态图描述D1D0D2mkck1ck2ck§10.1卷积码的定义及其应用S0S1S4S2S5S3S6S70/001/110/111/001/100/001/000/100/010/111/011/110/101/010/011/10状态图(11,10,01,01,00,11)

三、卷积码的应用§10.1卷积码的定义及其应用IS-95中的卷积码G=[557663711]

三、卷积码的应用§10.1卷积码的定义及其应用WCDMA系统中的卷积码G=[561753]

三、卷积码的应用§10.1卷积码的定义及其应用跟踪和数据中继卫星系统（TDRSS）外码(RS码)内码(卷积码)（2，1，6）卷积码

三、卷积码的应用§10.1卷积码的定义及其应用跟踪和数据中继卫星系统（TDRSS）6dB3dB什么是卷积码？已解决的问题：§10.1卷积码的定义及其应用如何对卷积码进行描述？卷积码的应用情况是怎样的？如何对卷积码进行译码？遗留的问题：§10.1卷积码的定义及其应用§10.1卷积码的定义及其应用思考与练习Turbo码

写出RSC的生多项式矩阵，绘制其状态图。§10.1卷积码的定义及其应用§10卷积码基础§10.2卷积码的译码§10.1卷积码的定义及其应用§10卷积码基础§10.2卷积码的译码待解决的问题：§10.2卷积码的译码如何进行卷积码的译码？§10.2卷积码的译码代数译码概率译码反馈译码定译码R(