计算机导论-讲稿.ppt

DataRepresentation Chapter2 天津大学软件学院 2 1DATATYPES 数据类型 Datatodaycomeindifferentformssuchasnumbers text images audio andvideo Peopleneedtoprocessallthesedatatypes Thecomputerindustryusestheterm multimedia todefineinformationthatcontainsnumbers text images audio andvideo number 数值text 文本image 图像 audio 音频Video 视频Multimedia 多媒体 AnalogandDigital 模拟和数字 Information Computersarefinite 有限的 Computermemoryandotherhardware 硬件 deviceshaveonlysomuchroomtostoreandmanipulateacertainamountofdata Thegoalofdatarepresentation 数据表示 istorepresentenoughoftheworldtosatisfyourcomputationalneedsandoursensesofsightandsound AnalogandDigitalInformation Informationcanberepresentedinoneoftwoways analogordigital AnalogdataAcontinuousrepresentation analogoustotheactualinformationitrepresents DigitaldataAdiscreterepresentation breakingtheinformationupintoseparateelements AnalogandDigitalInformation Amercurythermometerexemplifiesanalogdataasitcontinuallyrisesandfallsindirectproportiontothetemperature Digitaldisplaysonlyshowdiscrete 离散的 information 2 2DATAINSIDETHECOMPUTER Alldatatypesfromoutsideacomputeraretransformedintoauniformrepresentationwhenstoredinacomputerandthentransformedbackwhenleavingthecomputer Thisuniversalformatiscalledabitpattern 位组合格式 BIT 位 Abit binarydigit isthesmallestunitofdatathatcanbestoredinacomputer itiseither0or1 BITPATTERN 位组合格式 Abitpatternisasequence orasitissometimescalled astringofbitsthatcanrepresentasymbol e g BYTE 字节 Abitpatternoflength8iscalledabyte Examplesofbitpatterns 2 3REPRESENTINGDATA TEXT 文本 Apieceoftextinanylanguageisasequenceofsymbolsusedtorepresentanideainthatlanguage Youcanrepresenteachsymbolwithabitpattern Inotherwords textsuchas BYTE whichismadeoffoursymbols canberepresentedas4bitpatterns eachpatterndefiningasinglesymbol Howmanybitsareneededinabitpatterntorepresentasymbolinalanguage Thelengthofthebitpatternthatrepresentsasymbolinalanguagedependsonthenumberofsymbolsusedinthatlanguage Moresymbolsmeanalongerbitpattern Therelationshipisnotlinear itislogarithmic Ifyouneednsymbols thelengthislog2nbit Codes 编码 Differentsetsofbitpatternshavebeendesignedtorepresenttextsymbols Eachsetiscalledacode andtheprocessofrepresentingsymbolsiscalledcoding ASCIITheAmericanNationalStandardsInstitute ANSI developedacodecalledAmericanStandardCodeforInformationInterchange ASCII 美国信息交换标准代码 Thiscodeuses7bitsforeachsymbol Thismeans128differentsymbolscanbedefinedbythiscode e g ASCIICODEAmericanStandardCodeforInformationInterchange TheUnicodeCharacterSet 统一的字符编码标准 采用双字节对字符进行编码 Figure3 6AfewcharactersintheUnicodecharacterset AUDIO 音频 Audioisconvertedtodigitaldata thenwecanusebitpatternstostorethem Audioisbynatureanalogdata Itiscontinuous analog notdiscrete digital WAV AU AIFF VQF andMP3 sampling 采样quantization 量化Coding 编码 IMAGES 图像 Imagestodayarerepresentedinacomputerbyoneoftwomethods bitmapgraphicorvectorgraphic BitmapGraphic 位图 Inthismethod animageisdividedintoamatrixofpixels pictureelements whereeachpixelisasmalldot Thesizeofthepixeldependsonwhatiscalledtheresolution Afterdividinganimageintopixels eachpixelisassignedabitpattern Thesizeandthevalueofthepatterndependontheimage pixel 像素resolution 分辨率 Torepresentcolorimages eachcoloredpixelisdecom posedintothreeprimarycolors red green andblue RGB Thentheintensityofeachcolorismeasured andabitpattern usually8bits isassignedtoit Inotherwords eachpixelhasthreebitpatterns onetorepresenttheintensityoftheredcolor onetorepresenttheintensityofthegreencolor andonetorepresenttheintensityofthebluecolor BMP GIF JPEG PNG TIFF XBM andPCX threeprimarycolors 三基色 DigitizedImages VectorGraphicThevectorgraphicmethoddoesnotstorethebitpatterns Animageisdecomposedintoacombinationofcurvesandlines Eachcurveorlineisrepresentedbyamathematicalformula Forexample alinemaybedescribedbythecoordinatesofitsendpoints andacirclemaybedescribedbythecoordinatesofitscenterandthelengthofitsradius Thecombinationoftheseformulasisstoredinacomputer Whentheimageistobedisplayedorprinted thesizeoftheimageisgiventothesystemasaninput Thesystemredesignstheimagewiththenewsizeandusesthesameformulatodrawtheimage Inthiscase eachtimeanimageisdrawn theformulaisreevaluated WMF PICT EPS SVG SWF andTrueTypefonts curve 曲线 mathematicalformula 数学公式 RepresentingVideo Tosimulatemotion moviesneedtorecord andplayback atleast12framespersecond However goodsoundqualityrequires24frames s 24frames s 1440frames minute 46400frames hour Ifeachframehasaresolutionof1024x768 thereare786 432pixelsinaframe Ifthecolourofeachpixelisstoredas24bits 3bytes ofdata oneframealonerequires2 359 296bytes 2MB ofmemory Anhouroffilmthen requires203 843 174 400bytes 194 400MB morethan190Gigabytes ofstorage justfortheimages video 视频frame 祯 DataCompression 数据压缩 Itisimportantthatwefindwaystostoreandtransmitdataefficiently whichleadscomputerscientiststofindwaystocompressit Datacompressionisareductionintheamountofspaceneededtostoreapieceofdata Compressionratioisthesizeofthecompresseddatadividedbythesizeoftheoriginaldata Datacompression 数据压缩Compressionratio 压缩比 DataCompression Adatacompressiontechniquecanbelossless whichmeansthedatacanberetrievedwithoutanylossoftheoriginalinformation lossy whichmeanssomeinformationmaybelostintheprocessofcompaction Asexamples considerthese3techniques keywordencoding 关键字编码 run lengthencoding 扫描宽度编码 Huffmanencoding 霍夫曼编码 Lossless 无损Lossy 有损 Numbers text images audio andvideoareallformsofdata Computersneedtoprocessalltypesofdata Alldatatypesaretransformedintoauniformrepresentationcalledabitpatternforprocessingbycomputers Abitisthesmallestunitofdatathatcanbestoredinacomputer Abitpatternisasequenceofbitsthatcanrepresentasymbol Abyteis8bits SUMMARY Codingistheprocessoftransformingdataintoabitpattern ASCIIisapopularcodeforsymbols Imagesusethebitmapgraphicorvectorgraphicmethodfordatarepresentation Theimageisbrokenupintopixelswhichcanthenbeassignedbitpatterns Audiodataaretransformedtobitpatternsthoughsampling quantization andcoding Videodataareasetofsequentialimages SUMMARY continued EXERCISES 2 1 2 2 2 11 2 12 2 13 2 14 2 152 23 2 24 2 25 2 26 2 272 34 2 35 2 36 2 37 2 38 2 39 NumberRepresentation Chapter3 天津大学软件学院 NumberSystem TheDecimalsystemisbasedon10 0 9 Thebinarysystemisbasedon2 0 1 Octalnotationisbasedon8 0 7 Hexadecimalnotationisbasedon16 0 9 A F Decimalsystem 十进制binarysystem 二进制Octalnotation 八进制Hexadecimalnotation 十六进制 3 1DECIMALANDBINARY Twonumberingsystemsaredominanttodayintheworldofcomputers decimalandbinary DECIMALSYSTEM BINARYSYSTEMThebinarysystemisbasedon2 Thereareonlytwodigitsinthebinarysystem 0and1 OCTALNOTATION Octalnotationisbasedon8 Thismeansthereare8symbols 0 1 2 3 4 5 6 7 BitPattern 000001010011 OctDigit 0123 BitPattern 100101110111 OctDigit 4567 Binarytooctalandoctaltobinarytransformation HEXADECIMALNOTATION Hexadecimalnotationisbasedon16 hexadecisGreekfor16 Thismeansthereare16symbols hexadecimaldigits 0 1 2 3 4 5 6 7 8 9 A B C D E andF Eachhexadecimaldigitcanrepresent4bits 4bitscanberepresentedbyahexadecimaldigit CONVERSION 转换 Convertingfromabitpatterntohexadecimalisdonebyorganizingthepatternintogroupsoffourandfindingthehexadecimalvalueforeachgroupof4bits Forhexadecimaltobitpatternconversion converteachhexadecimaldigittoits4 bitequivalent Hexadecimalnotationiswrittenintwoformats Inthefirstformat youaddalowercase oruppercase xbeforethedigits Forexample xA34 Inanotherformat youindicatethebaseofthenumber 16 asthesubscriptafterthenotation Forexample A34 16 A34H Showthehexadecimalequivalentofthebitpattern110011100010 Eachgroupof4bitsistranslatedtoonehexadecimaldigit TheequivalentisxCE2 Showthehexadecimalequivalentofthebitpattern0011100010B Dividethebitpatterninto4 bitgroups fromtheright Inthiscase addtwoextra0satthelefttomakethenumberofbitsdivisibleby4 Soyouhave000011100010 whichistranslatedto0E2H Whatisthebitpatternforx24C Writeeachhexadecimaldigitasitsequivalentbitpatterntoget001001001100 3 2CONVERSION BINARYTODECIMALCONVERSIONStartwiththebinarynumberandmultiplyeachbinarydigitbyitsweight Sinceeachbinarybitcanbeonly0or1 theresultwillbeeither0orthevalueoftheweight Aftermultiplyingallthedigits addtheresults Convertthebinarynumber10011todecimal Writeoutthebitsandtheirweights Multiplythebitbyitscorrespondingweightandrecordtheresult Attheend addtheresultstogetthedecimalnumber Binary10011Weights168421 16 0 0 2 1Decimal19 DECIMALTOBINARYCONVERSIONToconvertfromdecimaltobinary userepetitivedivision division 除法quotient 商remainder 余数 Convertthedecimalnumber35tobinary Writeoutthenumberattherightcorner Dividethenumbercontinuouslyby2andwritethequotientandtheremainder Thequotientsmovetotheleft andtheremainderisrecordedundereachquotient Stopwhenthequotientiszero 0 1 2 4 8 17 35Dec Binary100011 3 3INTEGERREPRESENTATION 整数表示法 Integersarewholenumbers i e numberswithoutafraction Anintegercanbepositiveornegative 0 Tousecomputermemorymoreefficiently twobroadcategoriesofintegerrepresentationhavebeendeveloped unsignedintegersandsignedintegers Signedintegersmayalsoberepresentedinthreedistinctways Integer 整数fraction 分数unsignedinteger 无符号整数signedinteger 带符号整数 UNSIGNEDINTEGERSFORMATAnunsignedintegerisanintegerwithoutasign Mostcomputersdefineaconstantcalledthemaximumunsignedinteger Anunsignedintegerrangesbetween0andthisconstant Themaximumunsignedintegerdependsonthenumberofbitsthecomputerallocatestostoreanunsignedinteger Range 0 2N 1 Nisthenumberofbitsallocatedtorepresentoneunsignedinteger RepresentationStoringunsignedintegersisastraightforwardprocessasoutlinedinthefollowingstep 1 Thenumberischangedtobinary 2 IfthenumberofbitsislessthanN 0sareaddedtotheleftofthebinarynumbersothatthereisatotalofNbit Store7inan8 bitmemorylocation 存储单元 Firstchangethenumbertobinary111 Addfive0stomakeatotalofN 8 bits 00000111 Thenumberisstoredinthememorylocation Store258ina16 bitmemorylocation Firstchangethenumbertobinary100000010 Addseven0stomakeatotalofN 16 bits 0000000100000010 Thenumberisstoredinthememorylocation Overflow 溢出 Ifyoutrytostoreanunsignedintegersuchas256inan8 bitmemorylocation yougetaconditioncalledoverflow InterpretationHowdoyouinterpretanunsignedbinaryrepresentationindecimal Theprocessissimple ChangetheNbitsfromthebinarysystemtothedecimalsystem Interpret00101011indecimalifthenumberwasstoredasanunsignedinteger UsingtheprocedureshowninFigure3 3 thenumberindecimalis43 SIGNEDINTEGERSFORMATSIGN AND MAGNITUDEFORMAT 原码 Insign and magnituderepresentationtheleftmostbitdefinesthesignofthenumber Ifitis0 thenumberispositive Ifitis1 thenumberisnegative positive 正数negative 负数 SIGN AND MAGNITUDEFORMAT Range 2N 1 1 2N 1 1 Therearetwo0sinsign and magnituderepresentation positiveandnegative Inan8 bitallocation 0 00000000 0 10000000 RepresentationStoringsign and magnitudeintegerisastraightforwardprocess 1 Thenumberischangedtobinary thesignisignored 2 IfthenumberofbitsislessthanN 1 0sareaddedtotheleftofthenumbersothatthereisatotalofN 1bits 3 Ifthenumberispositive 0isaddedtotheleft tomakeitNbits Ifthenumberisnegative 1isaddedtotheleft tomakeitNbits Store 7inan8 bitmemorylocationusingsign and magnituderepresentation Firstchangethenumbertobinary111 Addfour0stomakeatotalofN 1 7 bits 0000111 Addanextrazerobecausethenumberispositive Theresultis 00000111 Store 258ina16 bitmemorylocationusingsign and magnituderepresentation Firstchangethenumbertobinary100000010 Addsix0stomakeatotalofN 1 15 bits 000000100000010 Addanextra1becausethenumberisnegative Theresultis 1000000100000010 InterpretationHowdoyouinterpretasign and magnitudebinaryrepresentationindecimal Theprocessissimple 1 Ignorethefirst leftmost bit 2 ChangetheN 1bitsfrombinarytodecimalasshownatthebeginningofthechapter 3 Attacha ora signtothenumberbasedontheleftmostbit Interpret10111011indecimalifthenumberwasstoredasasign and magnitudeinteger Ignoringtheleftmostbit theremainingbitsare0111011 Thisnumberindecimalis59 Theleftmostbitis1 sothenumberis 59 ONE SCOMPLEMENTFORMAT 反码 One scomplementofanumberisobtainedbychangingall0sto1sandall1sto0s Theleftmostbitdefinesthesignofthenumber Ifitis0 thenumberispositive Ifitis1 thenumberisnegative Apositivenumberispresentedbyit sSIGN AND MAGNITUDEFORMATAnegativenumberispresentedbyit sONE SCOMPLEMENTFORMAT Therearetwo0sinone scomplementrepresentation positiveandnegative Inan8 bitallocation 0 00000000 0 11111111 RepresentationStoringone scomplementintegersrequiresthefollowingsteps 1 Thenumberischangedtobinary thesignisignored 2 0sareaddedtotheleftofthenumbertomakeatotalofNbits 3 Ifthesignispositive nomoreactionisneeded Ifthesignisnegative everybitiscomplemented changedfrom0to1orfrom1to0 NumberofBits 81632 127 0 32767 0 2 147 483 647 0 0 127 0 32767 0 2 147 483 647 Range Range 2N 1 1 2N 1 1 Store 7inan8 bitmemorylocationusingone scomplementrepresentation Firstchangethenumbertobinary111 Addfive0stomakeatotalofN 8 bits 00000111 Thesignispositive sonomoreactionisneeded Theresultis 00000111 Store 258ina16 bitmemorylocationusingone scomplementrepresentation Firstchangethenumbertobinary100000010 Addseven0stomakeatotalofN 16 bits 0000000100000010 Thesignisnegative soeachbitiscomplemented Theresultis 1111111011111101 One scomplementmeansreversingallbits Ifyouone scomplementapositivenumber yougetthecorrespondingnegativenumber Ifyouone scomplementanegativenumber yougetthecorrespondingpositivenumber Ifyouone scomplementanumbertwice yougettheoriginalnumber InterpretationHowdoyouinterpretaone scomplementbinaryrepre sentationindecimal Theprocessinvolvesthesesteps 1 Iftheleftmostbitis0 positivenumber a Changetheentirenumberfrombinarytodecimal b Putaplussign infrontofthenumber 2 Iftheleftmostbitis1 negativenumber a Complementtheentirenumber changingall0sto1s andviceversa b Changetheentirenumberfrombinarytodecimal c Putanegativesign infrontofthenumber Interpret11110110indecimalifthenumberwasstoredasaone scomplementinteger Theleftmostbitis1 sothenumberisnegative Firstcomplementit Theresultis00001001 Thecomplementindecimalis9 Sotheoriginalnumberwas 9 TWO SCOMPLEMENTFORMAT 补码 2N 1 2N 1 1 Rangeoftwo scomplementintegers Two scomplementisthemostcommon themostimportant andthemostwidelyusedrepresentationofintegerstoday RepresentationStoringtwo scomplementrequiresthefollowingsteps 1 Thenumberischangedtobinary thesignisignored 2 IfthenumberofbitsislessthanN 0sareaddedtotheleftofnumbersothatthereisatotalofNbits 3 Ifthesignispositive nofurtheractionisneeded Ifthesignisnegative leavealltherightmost0sandthefirst1unchanged Complementtherestofthebits Store 7inan8 bitmemorylocationusingtwo scomplementrepresentation Firstchangethenumbertobinary111 Addfive0stomakeatotalofN 8 bits 00000111 Thesignispositive sonomoreactionisneeded Theresultis 00000111 Store 40ina16 bitmemorylocationusingtwo scomplementrepresentation Firstchangethenumbertobinary101000 Addten0stomakeatotalofN 16 bits 0000000000101000 Thesignisnegative soleavetherightmost0suptothefirst1 includingthe1 unchangedandcomplementtherest Theresultis 1111111111011000 Exampleofstoringtwo scomplementintegersintwodifferentcomputers InterpretationHowdoyouinterpretatwo scomplementbinaryrepresen tationindecimal Theprocessinvolvesthesesteps 1 Iftheleftmostbitis0 positivenumber a Changethewholenumberfrombinarytodecimal b Putaplussign infrontofthenumber 2 Iftheleftmostbitis1 negativenumber a Leavetherightmostbitsuptothefirst1 inclusive unchanged Complementtherestofthebits b Changethewholenumberfrombinarytodecimal c Putanegativesign infrontofthenumber Interpret11110110Bindecimalifthenumberwasstoredasatwo scomplementinteger Theleftmostbitis1 Thenumberisnegative Leave10attherightaloneandcomplementtherest Theresultis00001010B Thetwo scomplementnumberis10 Sotheoriginalnumberwas 10 Summaryofintegerrepresentation 3 4EXCESSSYSTEM AnotherrepresentationthatallowsyoutostorebothpositiveandnegativenumbersinacomputeriscalledtheExcesssystem Inthissystem itiseasytotransformanumberfromdecimaltobinary andviceversa However operationsonthenumbersareverycomplicated Theonlyapplicationinusetodayisinstoringtheexponentialvalueofafraction Thisisdiscussedinthenextsection Inanexcessconversion apositivenumber calledthemagicnumber isusedintheconversionprocess Themagicnumberisnormally 2N 1 or 2N 1 1 whereNisthebitallocation Forexample ifNis8 themagicnumberiseither128or127 Inthefirstcase wecalltherepresentationExcess 128 andinthesecondcase itisExcess 127 exponential 指数的magicnumber 幻数 RepresentationTorepresentanumberinExcess usethefollowingprocedure 1 Addthemagicnumbertotheinteger 2 Changetheresulttobinaryandadd0ssothatthereisatotalofNbits Represent 25inExcess 127usingan8 bitallocation Firstadd127toget102 Thisnumberinbinaryis1100110 Addonebittomakeit8bitsinlength Therepresentationis01100110 InterpretationTointerpretanumberinexcess usethefollowingprocedure 1 Changethenumbertodecimal 2 Subtractthemagicnumberfromtheinteger Interpret11111110iftherepresentationisExcess 127 Firstchangethenumbertodecimal Itis254 Thensubtract127fromthenumber Theresultisdecimal127 3 5FLOATING POINTREPRESENTATION Torepresentafloating pointnumber anumbercontaininganintegerandafraction thenumberisdividedintotwoparts theintegerandthefraction Forexample thefloating pointnumber14 234hasanintegerof14andafractionof0 234 CONVERTINGTOBINARYToconvertafloating pointnumbertobinary usethefollowingprocedure 1 Converttheintegerparttobinary 2 Convertthefractiontobinary 3 Putadecimalpointbetweenthetwoparts floating pointnumber 浮点数 Convertingtheintegerpart 整数部分 Convertingthefractionpart 小数部分 Toconvertafractiontobinary userepetitivemultiplication Transformthefraction0 875tobinary Writethefractionattheleftcorner Multiplythenumbercontinuouslyby2andextracttheintegerpartasthebinarydigit Stopwhenthenumberis0 0 0 875 1 750 1 5 1 0 0 00 111 Transformthefraction0 4toabinaryof6bits Writethefractionattheleftcorner Multiplythenumbercontinuouslyby2andextracttheintegerpartasthebinarydigit Youcannevergettheexactbinaryrepresentation Stopwhenyouhave6bits 0 4 0 8 1 6 1 2 0 4 0 8 1 60 011001 例1 00234 1 00236154302345 00 6154302345 00 NORMALIZATION 标准化 规格化 10011 1011 10 0111011 10011101 1 Astandardrepresentationforfloating pointnumbers Normalizationisthemovingofthedecimalpointsothatthereisonlyone1totheleftofthedecimalpoint 1 XXXXXXXXXXXXXXXX