A_mathematical_theory_of_communication

AMathematicalTheoryofCommunication*C.E.ShannonINTRODUCTIONTHErecentdevelopmentofvariousmethodsofmodulationsuchasPCMandPPMwhichexchangeband-widthforsignal-to-noiseratiohasintensifiedtheinterestinageneraltheoryofcommunication.AbasisforsuchatheoryiscontainedintheimportantpapersofNyquist1andHartley2onthissubject.Inthepresentpaperwewillextendthetheorytoincludeanumberofnewfactors,inparticulartheeffectofnoiseinthechannel,andthesavingspossibleduetothestatisticalstructureoftheoriginalmessageandduetothenatureofthefinaldestinationoftheinformation.Thefundamentalproblemofcommunicationisthatofreproducingatonepointeitherexactlyorapproxi-matelyamessageselectedatanotherpoint.Frequentlythemessageshavemeaning;thatistheyrefertoorarecorrelatedaccordingtosomesystemwithcertainphysicalorconceptualentities.Thesesemanticaspectsofcom-municationareirrelevanttotheengineeringproblem.Thesignificantaspectisthattheactualmessageisoneselectedfromasetofpossiblemessages.Thesystemmustbedesignedtooperateforeachpossibleselection,notjusttheonewhichwillactuallybechosensincethisisunknownatthetimeofdesign.Ifthenumberofmessagesinthesetisfinitethenthisnumberoranymonotonicfunctionofthisnumbercanberegardedasameasureoftheinformationproducedwhenonemessageischosenfromtheset,allchoicesbeingequallylikely.AswaspointedoutbyHartleythemostnaturalchoiceisthelogarithmicfunction.Althoughthisdefinitionmustbegeneralizedconsiderablywhenweconsidertheinfluenceofthestatisticsofthemessageandwhenwehaveacontinuousrangeofmessages,wewillinallcasesuseanessentiallylogarithmicmeasure.Thelogarithmicmeasureismoreconvenientforvariousreasons:1.Itispracticallymoreuseful.Parametersofengineeringimportancesuchastime,bandwidth,numberofrelays,etc.,tendtovarylinearlywiththelogarithmofthenumberofpossibilities.Forexample,addingonerelaytoagroupdoublesthenumberofpossiblestatesoftherelays.Itadds1tothebase2logarithmofthisnumber.Doublingthetimeroughlysquaresthenumberofpossiblemessages,ordoublesthelogarithm,etc..Itisnearertoourintuitivefeelingastothepropermeasure.Thisiscloselyrelatedto(1)sinceweintuitivelymeasuresentitiesbylinearcomparisonwithcommonstandards.Onefeels,forexample,thattwopunchedcardsshouldhavetwicethecapacityofoneforinformationstorage,andtwoidenticalchannelstwicethecapacityofonefortransmittinginformation.3.Itismathematicallymoresuitable.Manyofthelimitingoperationsaresimpleintermsofthelogarithmbutwouldrequireclumsyrestatementintermsofthenumberofpossibilities.Thechoiceofalogarithmicbasecorrespondstothechoiceofaunitformeasuringinformation.Ifthebase2isusedtheresultingunitsmaybecalledbinarydigits,ormorebrieflybits,awordsuggestedbyJ.W.Tukey.Adevicewithtwostablepositions,suchasarelayoraflip-flopcircuit,canstoreonebitofinformation.NsuchdevicescanstoreNbits,sincethetotalnumberofpossiblestatesis2uandlog22N=N.Ifthebase10isusedtheunitsmaybecalleddecimaldigits.Sincelog2M=log10M~log102=3.321og10M,*ReprintedfortheBellSystemTechnicalJournalwithcorrections.Copyright1948.LucentTechnologiesInc.Allrightsreserved.1Nyquist,H.,CertainFactorsAffectingTelegraphSpeed,BellSystemTechnicalJournal,April1924,p.324;CertainTopicsinTelegraphTransmissionTheory,A.LE.E.Trans.,v.47,April1928,p.617.2Hartley,R.V.L.,TransmissionofInformation,BellSystemTechnicalJournal,July1928,p.535.MobileComputingandCommunicationsReview,Volume5,NumberI3INFORMATIONSOURCETRANSMITTERMESSAGE_[SIGNAL1RsEFGEiKD[RECEIVERDESTINATIONHMESSAGENOISESOURCEFig.1--Schematicdiagramofageneralcommunicationsystem.adecimaldigitisabout3½bits.Adigitwheelonadeskcomputingmachinehastenstablepositionsandthereforehasastoragecapacityofonedecimaldigit.Inanalyticalworkwhereintegrationanddifferentiationareinvolvedthebaseeissometimesuseful.Theresultingunitsofinformationwillbecallednaturalunits.Changefromthebaseatobasebmerelyrequiresmultiplicationbylogba.ByacommunicationsystemwewillmeanasystemofthetypeindicatedschematicallyinFig.1.Itconsistsofessentiallyfiveparts:.Aninformationsourcewhichproducesamessageorsequenceofmessagestobecommunicatedtothereceivingterminal.Themessagemaybeofvarioustypes:(a)Asequenceoflettersasinatelegraphofteletypesystem;(b)Asinglefunctionoftimef(t)asinradioortelephony;(c)Afunctionoftimeandothervariablesasinblackandwhitetelevision--herethemessagemaybethoughtofasafunctionf(x,y,t)oftwospacecoordinatesandtime,thelightintensityatpoint(x,y)andtimetonapickuptubeplate;(d)Twoormorefunctionsoftime,sayf(t),g(t),h(t)--thisisthecaseinthree-dimensionalsoundtransmissionorifthesystemisintendedtoserviceseveralindividualchannelsinmultiplex;(e)Severalfunctionsofseveralvariables--incolortelevisionthemessageconsistsofthreefunctionsf(x,y,t),g(x,y,t),h(x,y,t)definedinathree-dimensionalcontinuum--wemayalsothinkofthesethreefunctionsascomponentsofavectorfielddefinedintheregion--similarly,severalblackandwhitetelevisionsourceswouldproducemessagesconsistingofanumberoffunctionsofthreevariables;(f)Variouscombinationsalsooccur,forexampleintelevisionwithanassociatedaudiochannel..Atransmitterwhichoperatesonthemessageinsomewaytoproduceasignalsuitablefortransmissionoverthechannel.Intele