Algebraic and Stochastic Coding Theory

Using a simple yet rigorous approach, Algebraic and Stochastic Coding Theory makes the subject of coding theory easy to understand for readers with a thorough knowledge of digital arithmetic, Boolean and modern algebra, and probability theory. It explains the underlying principles of coding theory and offers a clear, detailed description of each code. More advanced readers will appreciate its coverage of recent developments in coding theory and stochastic processes.

After a brief review of coding history and Boolean algebra, the book introduces linear codes, including Hamming and Golay codes. It then examines codes based on the Galois field theory as well as their application in BCH and especially the Reed–Solomon codes that have been used for error correction of data transmissions in space missions.

The major outlook in coding theory seems to be geared toward stochastic processes, and this book takes a bold step in this direction. As research focuses on error correction and recovery of erasures, the book discusses belief propagation and distributions. It examines the low-density parity-check and erasure codes that have opened up new approaches to improve wide-area network data transmission. It also describes modern codes, such as the Luby transform and Raptor codes, that are enabling new directions in high-speed transmission of very large data to multiple users.

This robust, self-contained text fully explains coding problems, illustrating them with more than 200 examples. Combining theory and computational techniques, it will appeal not only to students but also to industry professionals, researchers, and academics in areas such as coding theory and signal and image processing.

Historical BackgroundCodes Predating HammingCodes Leading to ASCIIBCD CodesDigital ArithmeticNumber SystemsBoolean and Bitwise OperationsChecksumRing CountersResidues, Residue Classes, and CongruencesIntegral ApproximationsLexicographic OrderLinear CodesLinear Vector Spaces over Finite FieldsCommunication ChannelsSome Useful DefinitionsLinear CodesVector OperationsSphere PackingHamming CodesError Correcting CodesHamming (7,4) CodeHamming (11,7) CodeGeneral AlgorithmHamming's Original AlgorithmEquivalent Codesq-ary Hamming CodesExtended Hamming CodesSEC-DED CodesHamming (8,4) CodeHamming (13,8) CodeHamming (32,26) CodeHamming (72,64) CodeHsiao CodeProduct NotesUses of Hamming CodesBounds in Coding Theory DefinitionsSphere-Packing BoundJohnson BoundGilbert–Varshamov BoundHamming BoundSingleton BoundPlotkin BoundGriesmer BoundZyablov BoundBounds in F2nReiger BoundKrawtchouk PolynomialsLinear Programming BoundStochastic Bounds for SEC-DED CodesGolay CodesPerfect CodesGeometrical RepresentationOther Construction MethodsFinite-State CodesMacWilliams’ IdentityGolay's Original AlgorithmStructure of Linear CodesGalois FieldsFinite FieldsConstruction of Galois FieldsGalois Fields of Order pPrime FieldsBinary FieldsArithmetic in Galois FieldsPolynomialsPolynomial CodesMatrix CodesMatrix Group CodesEncoding and Decoding MatricesDecoding ProcedureHadamard CodeHadamard TransformHexacodeLexicodes Octacode Simplex CodesBlock CodesCyclic CodesDefinitionConstruction of Cyclic CodesMethods for Describing Cyclic CodesQuadratic-Residue CodesBCH CodesBinary BCH CodesExtended Finite FieldsConstruction of BCH CodesGeneral DefinitionGeneral AlgorithmReed–Muller CodesBoolean PolynomialsRM EncodingGenerating Matrices for RM CodesProperties of RM CodesClassification of RM CodesDecoding of RM CodesRecursive DefinitionProbability AnalysisBurst ErrorsReed–Solomon CodesDefinitionReed–Solomon’s Original ApproachParity Check MatrixRS Encoding and DecodingBurst ErrorsErasuresConcatenated SystemsApplicationsBelief PropagationRational BeliefBelief PropagationStopping TimeProbability Density FunctionLog-Likelihood RatiosLDPC CodesTanner GraphsOptimal Cycle-Free CodesLDPC CodesHard-Decision DecodingSoft-Decision DecodingIrregular LDPC CodesSpecial LDPC CodesClassification of LDPC CodesGallager CodesIRA CodesSystematic CodesTurbo CodesBP DecodingPractical Evaluation of LDPC CodesDiscrete DistributionsPolynomial InterpolationChernoff BoundGaussian DistributionPoisson DistributionDegree DistributionProbability DistributionsProbability ComputationSoliton DistributionsErasure CodesErasure CodesTornado CodesRateless CodesOnline CodesFountain CodesLuby Transform CodesTransmission MethodsLuby Transform (LT) CodesPerformanceComparison of LT Codes with Other CodesRaptor CodesEvolution of Raptor CodesImportance SamplingCoupon Collector’s AlgorithmOpen ProblemsAppendicesA ASCII TableB Some Useful GroupsC Tables in Finite FieldsD Discrete Fourier TransformE Software ResourcesBibliographyIndex