《通信工程专业英语（第二版）》课件Unit 9

Unit9TextAShannon’sSourceCodingTheoremShannon’sSourceCodingTheoremThemathematicalfieldofinformationtheoryattemptstomathematicallydescribetheconceptof“information”.Inthefirsttwoposts,wediscussedtheconceptsofself-informationandinformationentropy.Inthispost,westepthroughShannon’s[1]SourceCodingTheoremtoseehowtheinformationentropyofaprobabilitydistributiondescribesthebest-achievableefficiencyrequiredtocommunicatesamplesfromthedistribution.TextTextWordsNotesDiscussionHome1.IntroductionSofar,wehavediscussedhow,intuitively,accordingtoInformationTheory,“information”canbeinterpretedastheamountofsurpriseexperiencedwhenwelearntheoutcomeofsomerandomprocess.InformationTheoryexpressesthis“surprise”bycountingtheminimumnumberofsymbolsthatwouldberequiredtocommunicatetheoutcomeofthisrandomprocesstoanotherperson/agent.TextTextWordsNotesDiscussionHomeThisideaofmeasuring“surprise”bysomenumberof“symbols”ismadeconcretebyShannon’sSourceCodingTheorem.Shannon’sSourceCodingTheoremtellsusthatifwewishtocommunicatesamplesdrawnfromsomedistribution,thenonaverage,wewillrequireatleastasmanysymbolsastheentropyofthatdistributiontounambiguouslycommunicatethosesamples.Saiddifferently,thetheoremtellsusthattheentropyprovidesalowerboundonhowmuchwecancompressourdescriptionofthesamplesfromthedistributionbeforeweinevitablyloseinformation(“information”usedhereinthecolloquialsense).TextWordsNotesDiscussionHomeInthispost,wewillwalkthroughShannon’stheorem.Myunderstandingofthismaterialcame,inpart,fromwatchingthisexcellentseriesofvideosbymathematicalmonkonYouTube[2].Thispostattemptstodistillmuchoftheinformationpresentedinthesevideosinmyownwords,keepingonlythepartsoftheexplanationnecessarytogetthroughthetheorem.TextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHome2.EncodingandcommunicatingsamplesfromadistributionRecallfromthepreviouspost,wediscussedhowtheinformationentropyofarandomvariabletellsyou,onaverage,theminimumnumberofsymbolsthatyouwillneedtousetocommunicatetheoutcomeofarandomvariable.Thatis,letussaywehavetwopeople,PersonAandPersonB,whoaretryingtocommunicatewithoneanother.Specifically,PersonAisobservingsamples,drawnoneatatime,fromsomedistributionX.PersonAthenwishestocommunicateeachsampletoPersonB.Forexample,XmightbeadiceandPersonAwishestocommunicatetoPersonBtheoutcomesofrepeateddicerolls.ThisframeworkisdepictedinFigure9-1:TextTextWordsNotesDiscussionHomeFigure9-1LetusrigorouslydescribethemathematicalframeworkinwhichPersonAiscommunicatingmessagestoPersonB.Todoso,wewillintroduceabunchoffundamentalconceptsfromCodingTheory.TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFirst,insteadofcallingeachdrawfromXa“sample”,wewillinsteadcalleachdrawasymbol.TheideahereisthatPersonAisgoingtocomeupwithsomerandomsequenceofsymbols,eachdrawnfromadistributionX,andattempttocommunicatethisrandommessage,composedoftherandomsequenceofsymbols,toPersonB.We’llcallthisrandommessagethesequenceofsourcesymbols:TheideaofeachXibeinga“symbol”,intuitivelyimpliesthatthenumberofoutcomesthateachXicantakeonisfinite.Tomakethisconcrete,wewillassertthatXisacategoricaldistribution.Thatis,suchthatTextTextWordsNotesDiscussionHomewhereisafinitesetofsymbolscalledthesourcealphabetandθisavectordescribingtheprobabilitiesthatagivenwilltakeonagivensymbolin.TextWordsNotesDiscussionHomeBeforecommunicatingeachsourcesymboltoPersonB,PersonAwillfirstencodeeachsymbolusingacodefunctionC.ThecodefunctionCtakesasinputasourcesymbolandoutputsasequenceofsymbolsfromanewsetofsymbolscalledthecodealphabet,denoted.Thecodeiscalledab-arycodeifthesizeofthecodealphabetisb.Thatis.Forexample,ifconsistsoftwosymbols,wecallthecode2-ary(a.k.a.binary).TextTextWordsNotesDiscussionHomeTomakethisconcrete,let’slookatasimplified,2-aryversionofMorseCode[3]forencodingtheEnglishalphanumericsymbolsintotwosymbols:“dots”and“dashes”(seeFigure9-2).InMorseCode,thesourcealphabet,consistsofthealphanumericsymbols,thecodealphabetconsistsofonlyadotanddash,andthecodefunction

mapseachalphanumericsymboltoasequenceofdotsanddashes.Morespecifically:TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFigure9-2Forexample,thename“Morse”wouldbeencodedasfollows(seeFigure9-3):TextTextWordsNotesDiscussionHomeFigure9-3Statedmorerigorously,ifwedenotetobethesetofsequencesofcodesymbolsthenCisafunctionTextTextWordsNotesDiscussionHomeWecalleachelementacodeword,whereistheimageofC.Wedenotethelengthofacodewordas|α|.Intheaboveexample,thelengthofcodeword“⋅-⋅”(i.e.)issimply3.TextTextWordsNotesDiscussionHomeForthepurposesofourdiscussion,wewillfocusonlyonuniquelydecodablecodefunctions.Acodefunctionisuniquelydecodableifitisaninvertiblefunction.Statedplainly,ifacodeCisuniquelydecodable,thenwecanalwaysdecodethecodewordsunambiguouslyintotheoriginalsequenceofsourcesymbolsusingtheinverseofC.Mostcodesusedinpracticeareuniquelydecodable.Anon-uniquelydecodablecodewouldnotbeveryusefulsincePersonBwhoreceivestheencodedmessagefromPersonAwouldbeunabletounambiguouslydecodePersonA’smessage.TextTextWordsNotesDiscussionHome3.Shannon’sSourceCodingTheoremGivensomecategoricaldistributionX,Shannon’sSourceCodeTheoremtellsusthatnomatterwhatCyouchoose,thesmallestpossibleexpectedcodewordlengthistheentropyofX.Thatis,TextTextWordsNotesDiscussionHomeMoreformally:Theorem1(Shannon’sSourceCodingThoerem):GivenacategoricalrandomvariableXoverafinitesourcealphabetandacodealphabet,thenforalluniquelydecodable,itholdsthatE[|C(X)|]≥H(X).TextTextWordsNotesDiscussionHomeTheexpectedcodewordlengthofXundersomecodeCtellsushowefficientlyonecan“compress”theinformationinX.Ifonaverage,CisabletoproducesmallcodewordsforeachsymboldrawnfromX,thenweareabletomoreefficientlycommunicatethesesymbols.Shannon’sSourceCodingTheoremtellsusthattheentropyofXis,insomesense,thetrue“informationcontent”oftherandomvariablebecausethereisnoCthatwillenableyoutocompressXpastX’sentropy.TextTextWordsNotesDiscussionHomeentropy[ˈentrəpɪ]n.熵，平均信息量；负熵theorem[ˈθɪərəm]n.[数]定理；[能证明的]一般原理，公理，定律，法则;probability[ˌprɒbəˈbɪlətɪ]n.可能性；几率，概率；或然性distribution[ˌdɪstrɪˈbjuːʃn]n.分配，分布;[法][无遗嘱死亡者的]财产分配;[无线]频率分布;[电]配电colloquial[kəˈləʊkwɪəl]adj.口语的，会话的dice[daɪs]n.骰子;掷骰游戏;v.将…切成丁WordsWordsTextWordsNotesDiscussionHomealphabet[ˈælfəbet]n.字母表;字母系统;入门，初步alphanumeric[ˌælfənjuːˈmerɪk]adj.文字数字的，包括文字与数字的WordsTextWordsNotesDiscussionHome[1]Shannon：克劳德·艾尔伍德·香农（ClaudeElwoodShannon，1916年4月30日—2001年2月24日），出生于美国密歇根州佩托斯基，美国数学家，美国国家工程院院士、美国国家科学院院士、美国艺术与科学院院士，信息论创始人，生前是麻省理工学院名誉教授。克劳德·艾尔伍德·香农提出了信息熵的概念，为信息论和数字通信奠定了基础。TextWordsNotesDiscussionNotesHome[2]YouTube：是一个视频网站，早期公司位于美国加利福尼亚州的圣布鲁诺。注册于2005年2月15日，由美国华裔陈士骏等人创立，让用户下载、观看及分享影片或短片。TextWordsNotesDiscussionHome[3]Morsecode：摩尔斯电码，也被称作摩斯密码，是一种时通时断的信号代码，通过不同的排列顺序来表达不同的英文字母、数字和标点符号。它发明于1837年，是一种早期的数字化通信形式。不同于现代化的数字通讯，摩尔斯电码只使用零和一两种状态的二进制代码，它的代码包括五种：短促的点信号“・”，保持一定时间的长信号“—”，表示点和划之间的停顿、每个词之间中等的停顿，以及句子之间长的停顿。TextWordsNotesDiscussionHomeQuestionsfordiscussion1.

Whatdoestheinformationmeaninthisarticle?2.

WhatdoestheShannon’sSourceCodingTheoremtellsus?3.HowdoespersonAcommunicatesourcesymbolstopersonB?TextWordsNotesDiscussionHomeAnswerstoquestionsfordiscussionTextWordsNotesDiscussionHome1.Whatdoestheinformationmeaninthisarticle?Intuitively,accordingtoInformationTheory,“information”canbeinterpretedastheamountofsurpriseexperiencedwhenwelearntheoutcomeofsomerandomprocess.InformationTheoryexpressesthis“surprise”bycountingtheminimumnumberofsymbolsthatwouldberequiredtocommunicatetheoutcomeofthisrandomprocesstoanotherperson/agent.TextWordsNotesDiscussionHome2.WhatdoestheShannon’sSourceCodingTheoremtellsus?Shannon’sSourceCodingTheoremtellsusthatifwewishtocommunicatesamplesdrawnfromsomedistribution,thenonaverage,wewillrequireatleastasmanysymbolsastheentropyofthatdistributiontounambiguouslycommunicatethosesamples.TextWordsNotesDiscussionHome3.HowdoespersonAcommunicatesourcesymbolstopersonB?BeforecommunicatingeachsourcesymbolXitoPersonB,PersonAwillfirstencodeeachsymbolusingacodefunctionC.ThecodefunctionCtakesasinputasourcesymbolandoutputsasequenceofsymbolsfromanewsetofsymbolscalledthecodealphabet.TextWordsNotesDiscussionHomeThankyou!Unit9TextBHowDataCompressionTechniquehelpsinDataRepresentation?HowDataCompressionTechniquehelpsinDataRepresentation?Eversincehumanslearnedtocommunicateandexchangeinformation,theyhavedonetheirbesttoreducethelengthorsizeoftheinformation.Priortothedigitalage,techniqueslikemorsecodewereimplemented.Later,telephonescameintobeing,andvoicetransmissionunderwentinnovationslikecuttingoffhighfrequencies.Fast-forwardtothepresentera–wearenowdealingwithinformationindigitalformwiththevelocity,veracity,andvolumeincreasingexponentially.Asaresult,datacompressionhasbecomeessentialforefficientstorageandtransmission.TextTextWordsNotesDiscussionHome1.Whycompressdata?Storing,managing,andtransferringdatabecomesessentialindatacommunicationandotherdata-drivensolutions.Thisisbecausenomatterthedegreeofadvancementincomputerhardware(RAM,ROM,GPU)andformsofcommunication(internet),theseresourcesarescarce.TextTextWordsNotesDiscussionHomeToutilizetheseresourcesefficiently,thedataisoftenrequiredtobecompressed,i.e.,reducedtoasmallersizewithoutlosinganyorlosingminimalinformation.TextWordsNotesDiscussionHomeVariedkindsofdatacanbecompressed.Thisincludesnumbers,text,video,images,audio,orevenprogramsandsoftware.Thesedatatypescanbereducedindifferentratios,suchas2:1,whichmeansadatafilewitha100MBsizecantakeuponly50MBofdiskspaceaftercompression.Thiscompression,alsoknownascompaction,isperformedthroughvariouscompressiontechniques.TextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHome2.Whatisdatacompressiontechnique?Datacompressiontechniquesindigitalcommunicationrefertotheuseofspecificformulasandcarefullydesignedalgorithmsusedbyacompressionsoftwareorprogramtoreducethesizeofvariouskindsofdata.Thereareparticulartypesofsuchtechniquesthatwewillgetinto,buttohaveanoverallunderstanding,wecanfocusontheprinciples.Datacompressioncanbeperformedbyusingsmallerstringsofbits(0sand1s)inplaceoftheoriginalstringandusinga‘dictionary’todecompressthedataifrequired.Othertechniquesincludetheintroductionofpointers(references)toastringofbitsthatthecompressionprogramhasbecomefamiliarwithorremovingredundantcharacters.TextTextWordsNotesDiscussionHomeForavideo,compressioncanbeachievedbyskippingevery3rdframe,asthiswillresult(asonecanimagine)ina1/3reductioninthesizeofthefile.Allsuchcompressioncandramaticallyreducedatasize(incasesupto70%ormorewithoutlosinganysignificantdata).CompressionformatslikeZIP,GZIP,etc.,areusedwhentransferringdataviatheinternet.TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeTheuseofdatacompressiontechniquesindigitalcommunicationgreatlyhelpsinreducingthetimeforafiletransfer,thecostofstorage,andtrafficinthenetwork.3.TypesofdatacompressiontechniquesWhileonecanrefertothisdatacompressiontechniquePDF[source],toknowaboutthevarioustypeoftechniquesavailable,thetwocommontypesthatalwaysstandoutare:TextTextWordsNotesDiscussionHome(1)LossycompressionTounderstandthelossycompressiontechnique(seeFigure9-4),wemustfirstunderstandthedifferencebetweendataandinformation.Dataisaraw,oftenunorganizedcollectionoffactsorvaluesandcanmeannumbers,text,symbols,etc.Ontheotherhand,Informationbringscontextbycarefullyorganizingthefacts.TextWordsNotesDiscussionHomeToputthisincontext,ablackandwhiteimageof4×6inchesin100dpi(dotsperinch)willhave2,40,000pixels.Eachofthesepixelscontainsdataintheformofanumberbetween0to255,representingpixeldensity(0beingblackand255beingwhite).TextTextWordsNotesDiscussionHomeThisimageasawholecanhavesomeinformationlikeitisapictureofthe16thpresidentoftheUSA-AbrahamLincoln.Ifwedisplayanimagein50dpi,i.e.,in60,000pixels,thedatarequiredtosavetheimagewillreduce,andperhapsthequalitytoo,buttheinformationwillremainintact.Onlyafterconsiderablelossindata,wecanlosetheinformation.Belowisanexplanationofhowitworks.TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFigure9-4Withtheaboveunderstandingofthedifferencebetweendataandinformation,wenowcancomprehendLossycompression.Asthenamesuggests,Lossycompressionlosesdata,i.e.,getsridofittoreducethesizeofthedata.TextTextWordsNotesDiscussionHome(2)LosslessCompressionLosslesscompression,unlikelossycompression,doesn’tremoveanydata;instead,ittransformsittoreduceitssize.Tounderstandtheconcept,wecantakeasimpleexample.TextTextWordsNotesDiscussionHomeThereisapieceoftextwheretheword‘because’isrepeatedquiteoften.Thetermiscomprisedofsevenletters,andbyusingashorthandorabbreviatedversionofitlike‘bcz’,wecantransformthetext.Thisinformationofreplacing‘because’with‘bcz’canbestoredinadictionaryforlateruse(duringdecompression).TextTextWordsNotesDiscussionHomeMethodology:Whilelossycompressionremovesredundantorunnoticeablepiecesofdatatoreducethesize,losslesscompressiontransformsitthroughencodingitbyusingsomeformulaorlogic.Here’showlosslesscompressionworks(seeFigure9-5).TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFigure9-5(3)Neuralnetwork-basedmodelsSomeneuralnetwork-basedmodelsarealsousedforcompression,suchas-1)MultilayerPerceptron(MLP)basedcompression(usedforimagecompression)2)ConvolutionalNeuralNetwork(CNN)basedcompressionsuchasDeepCoder(usedforvideocompression)3)GenerativeAdversarialNetworks(GAN)basedcompression(usedforreal-timecompression)TextTextWordsNotesDiscussionHomeThisisallaboutdatacompressiontechniques.Ifyouhaveanyquestionsonhowthesemodelsfunction,wearehappytohelp.Meanwhile,hereareafewcommonlyaskedquestionsondatacompressiontechniques.TextTextWordsNotesDiscussionHome4.DataCompressionTechniques:FAQs[1](1)Whataresomecommondatacompressionexamples?Datacompressionisusedwheneverthereisaneedtoreducethesizeofdata.Commonexamplesinclude:TextTextWordsNotesDiscussionHomeImagecompression:Certaindigitcamerascompresstheimagesforefficientstorage.Also,toaddressthereductionincameraspeedduetolargerawimages,compressionisdone.Thisiswhytheimagesareoftensavedasajpegthatuseslossydatacompressiontechniqueofdatacompressioncomparedtopng[2]thatuseslosslesscompression(seeFigure9-6).TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFigure9-6Audiocompression:Afewyearsback,theteamworkingonthestandardsofaudioandvideosystemsidentifiedtheadvantagesoftherepresentationofaudiodatadigitally.Thisgroup,knownasMPEG(MotionPicturesExpertsGroup)[3],cameupwithanaudio-videoencodingmechanismknownasMPEG-1.Themostcommonformofaudiocompressionismp3,i.e.,MPEG-1Layer3,whereeachsuccessivelayergetsmorecomplexandremovesredundantdata.Mp3isalossycompression,whichcanreducethequality;however,itslosslesscounterparts,suchasaudioinWAVandFLACformat,canalsobeused(seeFigure9-7.AllsuchformatsareusedtostoreaudioonCD/DVD,streammusiconwebsites,etc.TextTextWordsNotesDiscussionHomeTextTextWordsNotesDiscussionHomeFigure9-7Diskcompression:MostOperatingSystemsincludesomeformofcompressiontostoredataonthedisk.WhilethecompressedfilesrequiremoretimefortheOStoaccess,theupsideisthequickprocessingspeedgainedfromthiscompression.Archivefiles:Multiplefilescanbeplacedinafilethatcanthenbecompressed.HerefileformatslikeZIPandRARcomeinhandy,andthishelpsintheeaseoftransferringfilesandcreatingtheirbackup.TextTextWordsNotesDiscussionHome(2)Whatisthecompressiontechniqueindatacompression?Therearebroadlytwotypesofdatacompressiontechniques—lossyandlossless.Inlossy,theinsignificantpieceofdataisremovedtoreducethesize,whileinlosslesscompression,thedataistransformedthroughencoding,anditssizeisreduced.TextTextWordsNotesDiscussionHome(3)Whatisusedfordatacompression?Traditionally,deviceslike‘MorseKey’and‘MoreCodeReceiver’wereusedtopassandreceiveinformationinmorsecode,atypeofdatacompression.Today,differentsoftwareimplementsvarioustypesofmodelsbuiltondatacompressionalgorithms.Forexample,inLinuxandWindows,programslikegzipandZIPareusedrespectively,whereas,onmacOS,StuffItisthestandardtooltoperformdatacompression.Toachievecompressioninvideos,GIF(GraphicsInterchangeFormat)[4]formatisusedwhileJPEG(JointPhotographicExpertsGroup)[5]isusedforimages.TextTextWordsNotesDiscussionHomecompaction[kəm'pækʃən]n.压紧，紧束的状态;压实;redundant[rɪˈdʌndənt]adj.多余的，累赘的;[因人员过剩]被解雇的，失业的;重沓;衍;lossy[ˈlɔːsɪ]adj.有损耗的，致损耗的;pixel[ˈpɪksl]n.[显示器或电视机图像的]像素;methodology[ˌmeθəˈdɒlədʒɪ]n.[从事某一活动的]一套方法;方法学;方法论;convolutional[kɒnvə'luːʃənəl]adj.回旋的(卷积的；匝的；涡流的)WordsWordsTextWordsNotesDiscussionHomeneural[ˈnjʊərəl]adj.神经的;背的，背侧的;perceptron[pə'septrɔn]n.感知机(模拟大脑识别事物和差异的人工网络)generative[ˈdʒenərətɪv]adj.能生产的，有生产力的;生殖的;adversarial[ˌædvəˈseərɪəl]adj.敌手的，对手的，对抗[性]的;WordsTextWordsNotesDiscussionHome[1]FAQ：英文FrequentlyAskedQuestions的缩写，中文意思就是“经常问到的问题”，或者更通俗地叫做“常见问题解答”。FAQ是当前网络上提供在线帮助的主要手段，通过事先组织好一些可能的常问问答对，发布在网页上为用户提供咨询服务。TextWordsNotesDiscussionNotesHome[2]png（portablenetworkgraphics）：便携式网络图形，是一种采用无损压缩算法的位图格式，支持索引、灰度、RGB三种颜色方案以及Alpha通道等特性。[5]其设计目的是试图替代GIF和TIFF文件格式，同时增加一些GIF文件格式所不具备的特性。PNG使用从LZ77派生的无损数据压缩算法，一般应用于JAVA程序、网页或S60程序中，原因是它压缩比高，生成文件体积小。PNG文件的扩展名为.png。TextWordsNotesDiscussionHome[3]MPEG(MotionPicturesExpertsGroup)：动态图像专家组MPEG标准主要有以下五个，MPEG-1、MPEG-2、MPEG-4、MPEG-7及MPEG-21等。该专家组建于1988年，专门负责为C