第3章计算机学科基础

Chapter3第3章,3-2,ChapterGoals本章目标,Distinguishbetweenanaloganddigitalinformation.区分模拟和数字信息Explaindatacompressionandcalculatecompressionratios.解释数据压缩和计算压缩率Explainthebinaryformatsfornegativeandfloating-pointvalues.解释负数和浮点数的二进制格式DescribethecharacteristicsoftheASCIIandUnicodecharactersets.解释ASCII和Unicode字符集的特征,3-3,ChapterGoals本章目标,Performvarioustypesoftextcompression.执行各种类型的文本压缩Explainthenatureofsoundanditsrepresentation.解释声音的本质和它的表示法ExplainhowRGBvaluesdefineacolor.解释RGB值如何定义颜色Distinguishbetweenrasterandvectorgraphics.区分光栅图形和矢量图形Explaintemporalandspatialvideocompression.解释时间和空间视频压缩,3-4,DataandComputers数据和计算机,Computersaremultimedia多媒体devices,dealingwithavastarrayofinformationcategories.Computersstore,present,andhelpusmodifyNumbers数字Text文本Audio音频Imagesandgraphics图像和图形Video视频,3-5,Datacompression数据压缩Reductionintheamountofspaceneededtostoreapieceofdata.Compressionratio压缩率Thesizeofthecompresseddatadividedbythesizeoftheoriginaldata.AdatacompressiontechniquescanbeLossless无损,whichmeansthedatacanberetrievedwithoutanylossoftheoriginalinformation,Lossy有损,whichmeanssomeinformationmaybelostintheprocessofcompaction.,DataandComputers数据和计算机,3-6,AnalogandDigitalInformation模拟信息和数字信息,Computersarefinite.计算机是有限的Computermemoryandotherhardwaredeviceshaveonlysomuchroomtostoreandmanipulateacertainamountofdata.Thegoal,istorepresentenoughoftheworldtosatisfyourcomputationalneedsandoursensesofsightandsound.,3-7,AnalogandDigitalInformation模拟信息和数字信息,Informationcanberepresentedinoneoftwoways:analog模拟ordigital数字.Analogdata模拟数据Acontinuousrepresentation,analogoustotheactualinformationitrepresents.连续形式表示Digitaldata数字数据Adiscreterepresentation,breakingtheinformationupintoseparateelements.离散形式表示Amercurythermometerisananalogdevice.Themercuryrisesinacontinuousflowinthetubeindirectproportiontothetemperature.,3-8,AnalogandDigitalInformation模拟信息和数字信息,Figure3.1Amercurythermometercontinuallyrisesindirectproportiontothetemperature,75.568,3-9,AnalogandDigitalInformation模拟信息和数字信息,Computers,cannotworkwellwithanaloginformation.Sowedigitizeinformationbybreakingitintopiecesandrepresentingthosepiecesseparately.数字化：把信息分割成离散的片段Whydoweusebinary?Moderncomputersaredesignedtouseandmanagebinaryvaluesbecausethedevicesthatstoreandmanagethedataarefarlessexpensiveandfarmorereliableiftheyonlyhavetorepresentonoftwopossiblevalues.为什么我们要用二进制？现代计算机使用和管理的都是二进制数值。,3-10,ElectronicSignals电信号,Ananalogsignalcontinuallyfluctuatesinvoltageupanddown.Butadigitalsignalhasonlyahighorlowstate,correspondingtothetwobinarydigits.表示模拟信号的电压持续地上下波动，但是数字信号却只有高低两种状态。Allelectronicsignals(bothanaloganddigital)degradeastheymovedownaline.Thatis,thevoltageofthesignalfluctuatesduetoenvironmentaleffects.所有电信号都会因环境的影响而出现衰减，也就是电压会出现波动。,3-11,ElectronicSignals(Contd)电信号,Periodically,adigitalsignalisreclockedtoregainitsoriginalshape.重新计时,Figure3.2Ananalogandadigitalsignal,Figure3.3Degradationofanaloganddigitalsignals,Pulse-code-modulationPCM脉冲编码调制,阈值,3-12,BinaryRepresentations二进制表示法,Onebitcanbeeither0or1.Therefore,onebitcanrepresentonlytwothings.一个位只能表示两种状态。Torepresentmorethantwothings,weneedmultiplebits.Twobitscanrepresentfourthingsbecausetherearefourcombinationsof0and1thatcanbemadefromtwobits:00,01,10,11.要表示多于两种状态，需要多个位。两个位可以表示四种状态。,3-13,BinaryRepresentations二进制表示法,Ifwewanttorepresentmorethanfourthings,weneedmorethantwobits.Threebitscanrepresenteightthingsbecausethereareeightcombinationsof0and1thatcanbemadefromthreebits.如果要表示的状态多于四种，需要两个以上的位，三个位能表示八种状态，四位能表示16种状态。,3-14,BinaryRepresentations二进制表示法,Figure3.4Bitcombinations,3-15,BinaryRepresentations二进制表示法,Ingeneral,nbitscanrepresent2nthingsbecausethereare2ncombinationsof0and1thatcanbemadefromnbits.Notethateverytimeweincreasethenumberofbitsby1,wedoublethenumberofthingswecanrepresent.,3-16,RepresentingNegativeValues负数的表达,Youhaveusedthesigned-magnituderepresentation符号数值表示法ofnumberssincegradeschool.Thesignrepresentstheordering,andthedigitsrepresentthemagnitudeofthenumber.符号表示数所属的分类（正数或负数），数字表示数的量值。,3-17,RepresentingNegativeValues负数的表达,Thereisaproblemwiththesign-magnituderepresentation.符号数值表示法有一个问题Therearetworepresentationsofzero.Thereispluszeroandminuszero.Tworepresentationsofzerowithinacomputercancauseunnecessarycomplexity.Ifweallowonlyafixednumberofvalues,wecanrepresentnumbersasjustintegervalues,wherehalfofthemrepresentnegativenumbers.表示0的方法有两种，一种是+0，另一种是-0。在计算机种，0的两种表示发会引起不必要的麻烦。,3-18,RepresentingNegativeValues负数的表达,Forexample,ifthemaximumnumberofdecimaldigitswecanrepresentistwo,wecanlet1through49bethepositivenumbers1through49andlet50through99representthenegativenumbers-50through-1.例如，假定能够表示的最大十进制数是99（两位数），那么可以用1到49表示正数1到49，用50到99表示负数-50到-1，如下图所示。,3-19,RepresentingNegativeValues负数的表达,Toperformadditionwithinthisscheme,youjustaddthenumberstogetheranddiscardanycarry.在这种模式下执行加法，只需要对两个数求和，舍弃进位即可。,3-20,RepresentingNegativeValues负数的表达,A-B=A+(-B).Wecansubtractonenumberfromanotherbyaddingthenegativeofthesecondtothefirst.从一个数中减去另一个数，等价于给第一个数加上第二个数的负数。,3-21,RepresentingNegativeValues负数的表达,HereisaformulathatyoucanusetocomputethenegativerepresentationThisrepresentationofnegativenumbersiscalledthetenscomplement.这种负数表示法称为十进制补码,3-22,RepresentingNegativeValues,TwosComplementTomakeiteasiertolookatlongbinarynumbers,wemakethenumberlinevertical.二进制补码为了便于察看长的二进制数，我们把实数直线图绘制成垂直的。,3-23,RepresentingNegativeValues,Additionandsubtractionareaccomplishedthesamewayasin10scomplementarithmetic加法和减法的运算方式与十进制补码一样-12710000001+100000001-12610000010Noticethatwiththisrepresentation,theleftmostbitinanegativenumberisalwaysa1.注意，使用这种表示法，负数的最左边一位总是1。因此，在二进制补码中，很容易看出一个数是正数还是负数。,3-24,NumberOverflow数字溢出,Overflowoccurswhenthevaluethatwecomputecannotfitintothenumberofbitswehaveallocatedfortheresult.Forexample,ifeachvalueisstoredusingeightbits,adding127to3overflows.1111111+000001110000010Overflowisaclassicexampleofthetypeofproblemsweencounterbymappinganinfiniteworldontoafinitemachine.溢出，是把无限的世界映射到有限的机器上会发生的典型问题。,3-25,RepresentingRealNumbers实数的表达,Realnumbershaveawholepartandafractionalpart.Forexample104.32,0.999999,357.0,and3.14159.实数具有整数和小数部分thedigitsrepresentvaluesaccordingtotheirposition,and数字的位置表示数值thosepositionvaluesarerelativetothebase.位置的值有基数决定Thepositionstotherightofthedecimalpointarethetenthsposition(10-1oronetenth),thehundredthsposition(10-2oronehundredth),etc.,3-26,RepresentingRealNumbers实数的表达,Inbinary,thesamerulesapplybutthebasevalueis2.Sincewearenotworkinginbase10,thedecimalpointisreferredtoasaradixpoint小数点.Thepositionstotherightoftheradixpointinbinaryarethehalvesposition(2-1oronehalf),thequartersposition(2-2oronequarter),etc.在二进制中，小数点右侧的位置是二分位(二分之一)、四分位(四分之一)，依次类推。,3-27,RepresentingRealNumbers实数的表达,Arealvalueinbase10canbedefinedbythefollowingformula.符号*尾数*10expTherepresentationiscalledfloatingpointbecausethenumberofdigitsisfixedbuttheradixpointfloats.这种表示法成为浮点表示法，因为数字的个数是固定的，但是小数点却是浮动的。,3-28,RepresentingRealNumbers实数的表达,Likewise,abinaryfloatingpointvalueisdefinedbythefollowingformula:sign*mantissa*2exp同样地，下面的公式定义了一个二进制浮点值：符号*尾数*2exp,3-29,RepresentingRealNumbers实数的表达,ScientificnotationAformoffloating-pointrepresentationinwhichthedecimalpointiskepttotherightoftheleftmostdigit.科学记数法：小数点总在最左边数字的右侧。Forexample,12001.32708wouldbewrittenas1.200132708E+4inscientificnotation.,3-30,RepresentingText文本表示法,Torepresentatextdocumentindigitalform,weneedtobeabletorepresenteverypossiblecharacterthatmayappear.用数字形式表示文本文档，只需要表示每个可能出现的字符。Therearefinitenumberofcharacterstorepresent,sothegeneralapproachistolistthemallandassigneachabinarystring.要表示的字符数是有限的，一种表示字符的普通方法是列出所有字符，赋予每个字符一个二进制字符串。Acharactersetisalistofcharactersandthecodesusedtorepresenteachone.字符集：字符和表示它们的代码的清单。Byagreeingtouseaparticularcharacterset,computermanufacturershavemadetheprocessingoftextdataeasier.在计算机制造商就关于使用哪种字符集达成一致后，文本数据的处理变得容易多了。,3-31,TheASCIICharacterSetASCII字符集,ASCIIstandsforAmericanStandardCodeforInformationInterchange.TheASCIIcharactersetoriginallyusedsevenbitstorepresenteachcharacter,allowingfor128uniquecharacters.ASCII是美国信息互换标准代码的缩写。最初ASCII字符集用7位表示每个字符，可以表示128个不同字符。LaterASCIIevolvedsothatalleightbitswereusedwhichallowsfor256characters.之后，ASCII字符集进化了，用8位表示每个字符，可以表示256个字符。,3-32,TheASCIICharacterSetASCII字符集,3-33,TheASCIICharacterSet,Notethatthefirst32charactersintheASCIIcharacterchartdonothaveasimplecharacterrepresentationthatyoucouldprinttothescreen.注意，ASCII表的前32个字符没有简单的字符表示法，不能输出到屏幕。,3-34,TheUnicodeCharacterSetUnicode字符集,TheextendedversionoftheASCIIcharactersetisnotenoughforinternationaluse.ASCII字符集的扩展版本提供256个字符，虽然足够表示英语，但是却无法满足国际需要。TheUnicodecharactersetuses16bitspercharacter.Therefore,theUnicodecharactersetcanrepresent216,orover65thousand,characters.Unicode字符集使用16位表示每个字符，因此Unicode能够表示216个字符。UnicodewasdesignedtobeasupersetofASCII.Thatis,thefirst256charactersintheUnicodecharactersetcorrespondexactlytotheextendedASCIIcharacterset.为了保持一致，Unicode字符集被设计为ASCII的超集，也就是Unicode的前256个字符与ASCII字符集中的完全一样。,3-35,TheUnicodeCharacterSet,Figure3.6AfewcharactersintheUnicodecharacterset,3-36,TextCompression文本压缩,Itisimportantthatwefindwaystostoreandtransmittextefficiently,whichmeanswemustfindwaystocompresstext.找到有效地存储和传递的方法是很重要的，意味着我们必须找到压缩文本的方法。keywordencoding关键字编码run-lengthencoding行程长度编码Huffmanencoding霍夫曼编码,3-37,KeywordEncoding关键字编码,Frequentlyusedwordsarereplacedwithasinglecharacter.Forexample,用单个字符代替常用的单词。,3-38,KeywordEncoding关键字编码,Giventhefollowingparagraph,Thehumanbodyiscomposedofmanyindependentsystems,suchasthecirculatorysystem,therespiratorysystem,andthereproductivesystem.Notonlymustallsystemsworkindependently,theymustinteractandcooperateaswell.Overallhealthisafunctionofthewell-beingofseparatesystems,aswellashowtheseseparatesystemsworkinconcert.,3-39,KeywordEncoding关键字编码,TheencodedparagraphisThehumanbodyiscomposedofmanyindependentsystems,suchcirculatorysystem,respiratorysystem,+reproductivesystem.Notonly&eachsystemworkindependently,they&interact+cooperate%.Overallhealthisafunctionof%-beingofseparatesystems,%how#separatesystemsworkinconcert.,3-40,KeywordEncoding关键字编码,Thereareatotalof349charactersintheoriginalparagraphincludingspacesandpunctuation.Theencodedparagraphcontains314characters,resultinginasavingsof35characters.Thecompressionratioforthisexampleis314/349orapproximately0.9.原始段落总共有349个字符，包括空格和标点。编码后的段落包括314个字符，节省了35个字符。这个例子的压缩率是314/349，约为0.9。Thecharactersweusetoencodecannotbepartoftheoriginaltext.,3-41,Run-LengthEncoding行程长度编码,Asinglecharactermayberepeatedoverandoveragaininalongsequence.ThistypeofrepetitiondoesntgenerallytakeplaceinEnglishtext,butoftenoccursinlargedatastreams.一个字符可能在一个长序列中反复出现。在英语文本中，这种重复不常见，但在大的数据流中，这种情况经常出现，如DNA序列。Inrun-lengthencoding,asequenceofrepeatedcharactersisreplacedbyaflagcharacter,followedbytherepeatedcharacter,followedbyasingledigitthatindicateshowmanytimesthecharacterisrepeated.在行程长度编码中，重复字符的序列将被替换为标志字符，后面加重复字符和说明字符重复次数。,3-42,Run-LengthEncoding行程长度编码,AAAAAAAwouldbeencodedas*A7*n5*x9ccc*h6someothertext*k8eeewouldbedecodedintothefollowingoriginaltextnnnnnxxxxxxxxxccchhhhhhsomeothertextkkkkkkkkeeeTheoriginaltextcontains51characters,andtheencodedstringcontains35characters,givingusacompressionratiointhisexampleof35/51orapproximately0.68.Sinceweareusingonecharacterfortherepetitioncount,itseemsthatwecantencoderepetitionlengthsgreaterthannine.InsteadofinterpretingthecountcharacterasanASCIIdigit,wecouldinterpretitasabinarynumber.因为我们用一个字符记录重复的次数，所以看来不能对重复次数大于9的序列编码。因此，我们将次数字符解释为一个二进制数，而不是解释为ASCII数字。,3-43,HuffmanEncoding霍夫曼编码,Whyshouldthecharacter“X”,whichisseldomusedintext,takeupthesamenumberofbitsastheblank,whichisusedveryfrequently?Huffmancodesusingvariable-lengthbitstringstorepresenteachcharacter.文本中很少用到字符X，那么为何要让它占用的位数与其它字符一样呢？霍夫曼编码采用不同长度的位串表示每个字符。Afewcharactersmayberepresentedbyfivebits,andanotherfewbysixbits,andyetanotherfewbysevenbits,andsoforth.一些字符由5位编码表示，一些字符由6位编码表示，还有些字符由7位编码表示，等等。,3-44,HuffmanEncoding,Ifweuseonlyafewbitstorepresentcharactersthatappearoftenandreservelongerbitstringsforcharactersthatdontappearoften,theoverallsizeofthedocumentbeingrepresentedissmaller.这种方法的基本思想是用较少的位表示经常出现的字符，而将较长的位串留给不经常出现的字符，这样表示的文档的整体大小将比较小。,3-45,HuffmanEncoding,Forexample,3-46,HuffmanEncoding,DOORBELLwouldbeencodeinbinaryas1011110110111101001100100.Ifweusedafixed-sizebitstringtorepresenteachcharacter(say,8bits),thenthebinaryfromoftheoriginalstringwouldbe64bits.TheHuffmanencodingforthatstringis25bitslong,givingacompressionratioof25/64,orapproximately0.39.AnimportantcharacteristicofanyHuffmanencodingisthatnobitstringusedtorepresentacharacteristheprefixofanyotherbitstringusedtorepresentacharacter.Huffman编码的一个重要特征是用于表示一个字符的位串不会是表示另一个字符的位串的前缀。,3-47,RepresentingAudioInformation音频信息表示法,Weperceivesoundwhenaseriesofaircompressionsvibrateamembraneinourear,whichsendssignalstoourbrain.当一系列空气压缩震动我们的耳膜时，给我们的大脑发出一个信号，我们就感觉到了声音。Astereosendsanelectricalsignaltoaspeakertoproducesound.Thissignalisananalogrepresentationofthesoundwave.Thevoltageinthesignalvariesindirectproportiontothesoundwave.一个立体声系统通过把电信号发送到一个扬声器来制造声音。这种信号是声波的模拟表示法。信号。信号中的电压按声波的正比例变化。,3-48,RepresentingAudioInformation音频信息表示法,Todigitizethesignalweperiodicallymeasurethevoltageofthesignalandrecordtheappropriatenumericvalue.Theprocessiscalledsampling.要数字化这种信号，需要周期地测量信号的电压，记录合适的数值，这一过程成为采样。Ingeneral,asamplingrateofaround40,000timespersecondisenoughtocreateareasonablesoundreproduction.一般来说，采样率在每秒40000次左右就足够创建合理的声音复制品。,3-49,RepresentingAudioInformation音频信息表示法,Figure3.8Samplinganaudiosignal,3-50,RepresentingAudioInformation音频信息表示法,Figure3.9ACDplayerreadingbinaryinformation,3-51,RepresentingAudioInformation音频信息表示法,Acompactdisk(CD)storesaudioinformationdigitally.OnthesurfaceoftheCDaremicroscopicpitsthatrepresentbinarydigits.Alowintensitylaserispointedasthedisc.Thelaserlightreflectsstronglyifthesurfaceissmoothandreflectspoorlyifthesurfaceispitted.激光唱盘(CD)则存储了数字化的音频信息。CD的表面是用显微镜可见的凹点，表示二进制数字。低强度的激光将指向唱盘。如果唱盘表面是光滑的，激光的反射强烈，如果表面有凹痕，激光的反射就比较少。,3-52,AudioFormats音频格式,AudioFormatsWAV,AU,AIFF,VQF,andMP3.MP3isdominantMP3isshortforMPEG-2,audiolayer3file.MP3employsbothlossyandlosslesscompression.Firstitanalyzesthefrequencyspreadandcomparesittomathematicalmodelsofhumanpsychoacoustics(thestudyoftheinterrelationbetweentheearandthebrain),thenitdiscardsinformationthatcantbeheardbyhumans.ThenthebitstreamiscompressedusingaformofHuffmanencodingtoachieveadditionalcompression.MP3格式使用有损压缩和无损压缩两种方法。首先，它将分析频率展开，与人类心理声学的数学模型进行比较，然后舍弃那些人类听不到的信息，再用Huffman编码进一步压缩得到的位流。,3-53,RepresentingImagesandGraphics图像和图形的表示法,Colorisourperceptionofthevariousfrequenciesoflightthatreachtheretinasofoureyes.颜色是我们对到达视网膜的各种频率的光的感觉。Ourretinashavethreetypesofcolorphotoreceptorconecellsthatrespondtodifferentsetsoffrequencies.Thesephotoreceptorcategoriescorrespondtothecolorsofred,green,andblue.我们的视网膜有三种颜色感光视锥细胞，负责接收不同频率的光。这些感光器分类分别对应于红、绿和蓝三种颜色。,3-54,RepresentingImagesandGraphics图像和图形的表示法,ColorisoftenexpressedinacomputerasanRGB(red-green-blue)value,whichisactuallythreenumbersthatindicatetherelativecontributionofeachofthesethreeprimarycolors.在计算机中，颜色通常用RGB(红-绿-蓝)值表示，这其实是三个数字，说明了每种原色的相对份额。Forexample,anRGBvalueof(255,255,0)maximizesthecontributionofredandgreen,andminimizesthecontributionofblue,whichresultsinabrightyellow.例如，RGB值(255,255,0)最大化了红色和绿色的份额，最小化了蓝色的份额，结果生成的是嫩黄色。,3-55,RepresentingImagesandGraphics,Figure3.10Three-dimensionalcolorspace,3-56,RepresentingImagesandGraphics,Theamountofdatathatisusedtorepresentacoloriscalledthecolordepth.用于表示颜色的数据量称为色深度。HiColorisatermthatindicatesa16-bitcolordepth.FivebitsareusedforeachnumberinanRGBvalueandtheextrabitissometimesusedtorepresenttransparency.TrueColorindicatesa24-bitcolordepth.Therefore,eachnumberinanRGBvaluegetseightbits.增强色彩指色深度为16位的颜色，RGB值中的每个数字由5位表示，剩下的一位有时用于表示透明度。真彩色指色深度为24位的颜色，RGB值中的每个数字由8位表示。,3-57,RepresentingImagesandGraphics,3-58,IndexedColor索引颜色,Aparticularapplicationsuchasabrowsermaysupportonlyacertainnumberofspecificcolors,creatingapalettefromwhichtochoose.Forexample,theNetscapeNavigatorscolorpaletteis一个特定的应用程序（如浏览器）可能只支持某些颜色，它将创建一个调色板。浏览器显示的是最接近真是颜色的调色板颜色。,Figure3.11TheNetscapecolorpalette,3-59,DigitizedImagesandGraphics数字化图像和图形,Digitizingapictureistheactofrepresentingitasacollectionofindividualdotscalledpixels.数字化一幅图像是把它表示为一套独立的点，这些点称为像素。Thenumberofpixelsusedtorepresentapictureiscalledtheresolution.表示一幅图像使用的像素个数称为分辨率。Thestorageofimageinformationonapixel-by-pixelbasisiscalledaraster-graphicsformat.Severalpopularrasterfileformatsincludingbitmap(BMP),GIF,andJPEG.逐个像素存储图像信息的方法称为光栅图形格式。目前流行的几种光栅文件格式有位图BMP,GIF和JPEG。,3-60,DigitizedImagesand