无失真编码学习.pptx
《无失真编码学习.pptx》由会员分享,可在线阅读,更多相关《无失真编码学习.pptx(34页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Generalmodelofdiscrete,lossless(无失真),non-memorysource:Input symbol setCode symbol setCode word set5.1Losslessencoder第1页/共34页Howtocodelosslessly?Assumingthatthestatisticalcharacteristicsofthesourcecanbeignored,itmustsatisfy thefollowingcondition.To get the target of lossless coding,it must conform to
2、 the condition ,which guarantees that there are plenty of code symbols to be used.lFrom the condition we can get an inequality,第2页/共34页E.g.5.1SupposeweonlyhavethefirsteightlettersofEnglishalphabet(AtoH)inourvocabulary.TheFixedLengthCode(FLC)forthissetofletterswouldbeLetterCodewordLetterCodewordA000E
3、100B001F101C010G110D011H111Fixed Length Code第3页/共34页AVariableLengthCode(VLC)forthesamesetofletterscanbeLetterCodewordLetterCodewordA00E101B010F110C011G1110D100H1111Variable Length Code1(Huffman coding)第4页/共34页Supposewehavetocodetheseriesofletters:”ABADCAB”.Thefixedlengthcodeandvariablelengthcoderepr
4、esentationsofthe7lettersareFixed Length Code000 001 000 011 010 000 001Total bits=21Variable Length Code00 010 00 100 011 00 010Total bits=18It can be seen that the VLC uses a fewer number of bits than FLC since the letters,for example,A,appearing more frequently in the sentence are represented with
5、 a fewer number of bits 00.第5页/共34页Instantaneous code(prefix code)(1)Itisakindofuniquelydecodablecode(2)Inanunfixedlengthcode,thereisnoonecodebeingprefixtoothercodes.(3)Whendecoding,itdoesnotneedtorefertoitsfollowingcodes,andcanmakethejudgmentimmediately,carryingoutnon-delaydecoding.第6页/共34页Letushav
6、ealookatExample5.1again.NowweconsideranotherVLCforthefirst8lettersofEnglishalphabet:LetterCodewordLetterCodewordA0E10B1F11C00G000D01H111Variable Length Code2第7页/共34页Thissecondvariablelengthcodeappearstobemoreefficientthanthefirstoneintermsofrepresentationoftheletters.Variable Length Code100 010 00 1
7、00 011 00 010Total bits=18Variable Length Code20 1 0 01 00 0 1Total bits=9However,it has decoding problemsHowever,it has decoding problems:Original:0 1 0 01 00 0 1 -A BAD CABNow:0 10 0 1 0 0 01 -A EAB AADOr 0 1 0 0 1 0 0 0 1 -A BAAB AAAB第8页/共34页Definition 5.1APrefix Codeisoneinwhichnocodewordformsth
8、eprefixofanyothercodeword.SuchcodesarealsocalledUniquely DecodableorInstantaneous Codes.lThe optimal codeIt is a kind of uniquely decodable codeIts average code length is less than that of any other uniquely decodable code.第9页/共34页5.2.1Fixedlengthcodingtheorem5.2 Lossless source codingFixed length s
9、ource coding theoremFixed length source coding theorem:As to the discrete,non-memory,stationary,ergodic source symbol sequence S=(S1,S2.Sq),we can use r different symbols X=(x1,x2.xr)to perform fixed length code.For any 0 and0,as to the N-expansion source,If is satisfied,and when N is big enough,the
10、 decoding error can be less than.The fixed length coding theorem has presented a theoretical limit of the code length used for fixed length coding.第10页/共34页Iftheequallengthcodeisdemandedtobeuniquelydecodable,thenitmusthas:IfN1,then:Conclusion:foruniquedecoding,eachsourcesymbolneedsatleastcodesymbols
11、toberepresented.Whenusedual-codesymboltocode,r2,then:Conclusion:whenuseequallengthdual-code,thelimitcodelengthofeachsourcesymbolisExample第11页/共34页5.2.2Unfixedlength(Variablelength)sourcecodingSeveralconceptsofcodetype(Eg.2.4.2)Non-singularcodeandsingularcodeUniquelydecodablecodePrefixcode(instantane
12、ouscode,non-delaycode)KrafttheoremUnfixedlengthcodingtheorem(ShannonFirstTheorem)第12页/共34页Kraft theoremquestion:findreal-time,uniquelydecodablecodemethod:researchthecodepartitionconditionofthereal-timeuniquelydecodablecodeintroduction:conceptof“codetree”conclusion:presenttheconditionthatthereal-time
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 失真 编码 学习
限制150内