1．DISCRETESOURCESANDENTROPY 1
1.1OverviewofDigitalCommunicationandStorageSystems 1
1.2DiscreteInformationSourcesandEntropy 2
1.2.1Sourcealphabetsandentropy, 2
1.2.2Jointandconditionalentropy, 6
1.2.3Entropyofsymbolblocksandthechainrule, 8
1.3SourceCoding 10
1.3.1Mappingfunctionsandefficiency, 10
1.3.2Mutualinformation, 12
1.3.3Abriefdigressiononencryption, 14
1.3.4Summaryofsection1.3, 15
1.4.1Prefixcodesandinstantaneousdecoding, 16
1.4HuffmanCoding 16
1.4.2ConstructionofHuffmancodes, 17
1.4.3Hardwareimplementationapproaches, 19
1.4.4RobustnessofHuffmancodingefficiency, 20
1.5DictionaryCodesandLempel-ZivCoding 21
1.5.1Therationalebehinddynamicdictionarycoding, 21
1.5.2Alinked-listLZalgorithm, 22
1.5.3Thedecodingprocess, 25
1.5.4Large-blockrequirementofLZcompression, 26
1.6ArithmeticCoding 28
1.6.1Code-wordlengthandtheasymptoticequipartitionproperty, 28
1.6.2Thearithmeticcodingmethod, 30
1.6.3Decodingarithmeticcodes, 32
1.6.4Otherissuesinarithmeticcoding, 33
1.7SourceModelsandAdaptiveSourceCoding 34
1.8ChapterSummary 35
References 36
Exercises 37
2．CHANNELSANDCHANNELCAPACITY 39
2.1TheDiscreteMemorylessChannelModel 39
2.1.1Thetransitionprobabilitymatrix, 39
2.1.2Outputentropyandmutualinformation, 41
2.2ChannelCapacityandtheBinarySymmetricChannel 43
2.2.1Maximizationofmutualinformationandchannelcapacity, 43
2.2.2Symmetricchannels, 45
2.3.1Equivocation, 48
2.3BlockCodingandShannon sSecondTheorem 48
2.3.2Entropyrateandthechannel-codingtheorem, 49
2.4MarkovProcessesandSourceswithMemory 51
2.4.1Markovprocesses, 51
2.4.2Steady-stateprobabilityandtheentropyrate, 54
2.5MarkovChainsandDataProcessing 56
2.6ConstrainedChannels 58
2.6.1Modulationtheoryandchannelconstraints, 58
2.6.2Linearandtime-invariantchannels, 60
2.7AutocorrelationandPowerSpectrumofSequences 62
2.7.1Statisticsoftimesequences, 62
2.7.2Thepowerspectrum, 64
2.8.1Constraintsondatasequences, 68
2.8DataTranslationCodes 68
2.8.2Statespaceandtrellisdescriptionsofcodes, 70
2.8.3Capacityofadatatranslationcode, 73
2.9(d,k)Sequences 75
2.9.1Run-length-limitedcodesandmaxentropicsequences, 75
2.9.2Powerspectrumofmaxentropicsequences, 77
2.10ChapterSummary 82
References 83
Exercises 83
3．RUN-LENGTH-LIMITEDCODES 89
3.1GeneralConsiderationsforDataTranslationCoding 89
3.2PrefixCodesandBlockCodes 91
3.2.1Fixed-lengtnblockcodes, 91
3.2.2Variable-lengthblockcodes, 92
3.2.3PrefixcodesandtheKraftinequality, 94
3.3State-DependentFixed-LengthBlockCodes 96
3.4Variable-LengthFixed-RateCodes 98
3.5Look-AheadCodes 102
3.5.1Code-wordconcatenation, 102
3.5.2Thekconstraint, 104
3.5.3Informalandformaldesignmethods, 105
3.6DC-FreeCodes 107
3.6.1Therunningdigitalsumandthedigitalsumvariation, 107
3.6.2State-splittingandmatchedspectralnullcodes, 109
3.7ChapterSummary 114
Exercises 115
References 115
4．LINEARBLOCKERROR-CORRECTINGCODES 117
4.1GeneralConsiderations 117
4.1.1Channelcodingforerrorcorrection, 117
4.1.2Errorratesanderrordistributionforthebinarysymmetricchannel, 118
4.1.3Errordetectionandcorrection, 121
4.1.4Themaximumlikelihooddecodingprinciple, 123
4.1.5Hammingdistancecodecapability, 124
4.2BinaryFieldsandBinaryVectorSpaces 126
4.2.1Thebinaryfield, 126
4.2.2Representinglinearcodesinavectorspace, 130
4.3.1Elementarypropertiesofvectorspaces, 131
4.3LinearBlockCodes 131
4.3.2Hammingweight,Hammingdistance,andtheHammingcube, 133
4.3.3TheHammingsphereandboundsonredundancyrequirements, 135
4.4DecodingLinearBlockCodes 136
4.4.1Completedecodersandbounded-distancedecoders, 136
4.4.2Syndromedecodersandtheparity-checktheorem, 138
4.5HammingCodes 140
4.5.1ThedesignofHammingcodes, 140
4.5.2ThedualcodeofaHammingcode, 143
4.5.3TheexpandedHammingcode, 144
4.6ErrorRatePerformanceBoundsforLinearBlockError-CorrectingCodes 147
4.6.1Blockerrorrates, 147
4.6.2Biterrorrate, 148
4.7PerformanceofBounded-DistanceDecoderswithRepeatRequests 149
4.7.1Approximateerrorperformance, 152
4.7.2EffectivecoderateofARQsystems, 154
4.7.3ARQprotocols, 156
4.8ChapterSummary 157
References 158
Exercises 158
5．CYCLICCODES 160
5.1DefinitionandPropertiesofCyclicCodes 160
5.2PolynomialRepresentationofCyclicCodes 162
5.3.1Polynomialrings, 164
5.3PolynomialModuloArithmetic 164
5.3.2Someimportantalgebraicidentities, 166
5.4GenerationandDecodingofCyclicCodes 169
5.4.1Generator,parity-check,andsyndromepolynomials, 169
5.4.2Systematiccycliccodes, 169
5.4.3Hardwareimplementationofencodersforsystematiccycliccodes, 171
5.4.4Hardwareimplementationofdecodersforcycliccodes, 174
5.4.5TheMeggittdecoder, 175
5.5Error-TrappingDecoders 178
5.5.1Updatingthesyndromeduringcorrection, 178
5.5.2Bursterrorpatternsanderrortrapping, 180
5.6SomeStandardCyclicBlockCodes 184
5.6.1TheHammingcodes, 184
5.6.2BCHcodes, 185
5.6.3Burst-correctingcodes, 186
5.6.4Cyclicredundancycheckcodes, 187
5.7SimpleModificationstoCyclicCodes 189
5.7.1Expandingacode, 189
5.7.2Shorteningacode, 190
5.7.3Noncyclicityofshortenedcodes, 193
5.7.4Interleaving, 194
5.8ChapterSummary 197
References 197
Exercises 198
6.1DefinitionofConvolutionalCodes 201
6.2.1Thestatediagramandtrellisrepresentations, 205
6.2StructuralPropertiesofConvolutionalCodes 205
6．CONVOLUTIONALCODES 207
6.2.2Transferfunctionsofconvolutionalcodes, 207
6.3TheViterbiAlgorithm 210
6.4WhytheViterbiAlgorithmWorksⅠ:Hard-DecisionDecoding 215
6.4.1Maximumlikelihoodunderhard-decisiondecoding, 215
6.4.2Erroreventprobability, 217
6.4.3Boundsonbiterrorrate, 219
6.5SomeKnownGoodConvolutionalCodes 221
6.6WhytheViterbiAlgorithmWorksⅡ:Soft-DecisionDecoding 223
6.6.1Euclideandistanceandmaximumlikelihood, 223
6.6.2Eliminationoftiesandinformationloss, 226
6.6.3Calculationofthelikelihoodmetric, 228
6.7TheTracebackMethodofViterbiDecoding 229
6.8PuncturedConvolutionalCodes 234
6.8.1Puncturing, 234
6.8.2Goodpuncturedconvolutionalcodes, 236
6.9ChapterSummary 238
References 239
Exercises 239
7．TRELLIS-CODEDMODULATION 242
7.1Multiamplitude/MultiphaseDiscreteMemoryless 242
Channels 242
7.1.1I—Qmodulation, 242
7.1.2Then-aryPSKsignalconstellation, 243
7.1.3PSKerrorrate, 245
7.1.4Quadratureamplitudemodulation, 247
7.2SystematicRecursiveConvolutionalEncoders 248
7.3SignalMappingandSetPartitioning 251
7.4KnownGoodTrellisCodesforPSKandQAM 254
7.5ChapterSummary 257
References 257
Exercises 258
8．INFORMATIONTHEORYANDCRYPTOGRAPHY 259
8.1Cryptosystems 259
8.1.1Basicelementsofciphersystems, 259
8.1.2Somesimpleciphersystems, 261
8.2AttacksonCryptosystems 265
8.3PerfectSecrecy 266
8.4LanguageEntropyandSuccessfulCiphertextAttacks 269
8.4.1Thekey-equivocationtheorem, 269
8.4.2Spuriouskeysandkeyequivocation, 270
8.4.3Languageredundancyandunicitydistance, 271
8.5ComputationalSecurity 272
8.6DiffusionandConfusion 274
8.7ProductCipherSystems 275
8.7.1Commuting,noncommuting,andidempotentproductciphers, 276
8.7.2Mixingtransformationsandgoodproductciphers, 278
8.8Codes 279
8.9Public-KeyCryptosystems 280
8.11ChapterSummary 281
8.10OtherIssues 281
References 282
Exercises 283
9．SHANNON SCODINGTHEOREMS 285
9.1RandomCoding 285
9.2TheAverageRandomCode 287
9.3ADiscussionofShannon sSecondTheorem 289
9.4Shannon-FanoCoding 290
9.5Shannon sNoiseless-CodingTheorem 292
9.6AFewFinalWords 293
References 294
ANSWERSTOSELECTEDEXERCISES 295
INDEX 299