book

Algebraic and Stochastic Coding Theory

by Dave K. Kythe, Prem K. Kythe

July 2017

Intermediate to advanced

512 pages

13h 21m

English

CRC Press

Read now

Unlock full access

Cover
Title Page
Copyright Page
Dedication
Table of Contents
Preface
Notations and Abbreviations
1 Historical Background
1.1 Codes Predating Hamming1.2 Codes Leading to ASCII1.2.1 Original Morse Code1.2.2 Baudot’s Code1.2.3 Murray’s Code1.2.4 Bacon’s Telegraph Code1.2.5 Gauss and Weber’s Telegraph Code1.2.6 ITA21.2.7 US TTY1.2.8 ASCII-1967 Code1.3 BCD Codes1.3.1 Four-Bit BCD Codes1.3.2 Addition with 8421 and Excess-3 Codes1.3.3 Codes Larger than Four Bits1.3.4 Biquinary Code
2 Digital Arithmetic
2.1 Number Systems2.1.1 Decimal Numbers2.1.2 Division Algorithm2.1.3 Base Conversion2.1.4 Conversion of Integers2.1.5 LCM and GCD2.1.6 Modulo2.2 Boolean and Bitwise Operations2.2.1 Boolean Logical Operations2.2.2 Bitwise Operations2.2.3 Applications2.2.4 XOR Swap Algorithm2.2.5 XOR Linked Lists2.2.6 Bit Shifts2.2.7 Arithmetic Shifts2.2.8 Logical Shifts2.2.9 Circular Shifts2.2.10 Shift Registers2.2.11 Rotate through Carry2.2.12 One’s and Two’s Complement Arithmetic2.3 Checksum2.3.1 Fletcher’s Checksum2.3.2 Cyclic Redundancy Check (CRC)2.4 Ring Counters2.5 Residues, Residue Classes, and Congruences2.6 Integral Approximations2.7 Lexicographic Order
3 Linear Codes
3.1 Linear Vector Spaces over Finite Fields3.2 Communication Channels3.2.1 Shannon’s Theorems3.3 Some Useful Definitions3.3.1 Hamming Distance3.3.2 Lee Distance3.3.3 Hamming Cubes3.3.4 Hamming Weight3.3.5 Residual Code3.2.6 Tree Algorithm3.4 Linear Codes3.4.1 Linear Code3.4.2 Dual Codes3.4.3 Dimension of a Code3.4.4 Self-Dual Codes and Types3.4.5 Advantages of Linear Codes3.4.6 Popcount3.4.7 Parity Bits3.4.8 Uses of Parity Bits3.4.9 Stop Bit3.4.10 Parity-Check Matrix3.4.11 Decoding3.4.12 Decoding Methods3.4.12.1 Ideal Observer Decoding3.4.12.2 Maximum Likelihood Decoding3.4.12.3 Minimum Distance Decoding3.4.12.4 Nearest Neighbor Decoding3.4.12.5 Standard Array Decoding3.4.12.6 Syndrome Decoding3.4.13 Syndrome Lookup Table3.5 Vector Operations3.5.1 Wedge Product3.5.2 Bar Product3.6 Sphere Packing

4 Hamming Codes
4.1 Error Correcting Codes4.1.1 Binary Linear Hamming Codes4.2 Hamming (7,4) Code4.2.1 Encoding and Decoding4.2.2 Computation of Parity Bits4.2.3 Syndrome Method4.2.4 Parity Check Method4.2.5 Mapping Method4.2.6 Systematic Hamming codes4.2.7 Codeword Sequences4.2.8 Multiple-Bit Errors4.3 Hamming (11,7) Code4.4 General Algorithm4.4.1 All Sixteen Possible Hamming (7,4) Codes4.4.2 Hamming Code for Longer Data4.5 Hamming’s Original Algorithm4.6 Equivalent Codes4.7 q-ary Hamming Codes
5 Extended Hamming Codes
5.1 SEC-DED Codes5.1.1 Extension of Hamming Codes5.2 Hamming (8,4) Code5.3 Hamming (13,8) Code5.4 Hamming (32,26) Code5.5 Hamming (72,64) Code5.5.1 Modified Hamming (72,64) Code5.5.2 Encoding of Hamming (72,64) Code5.6 Hsiao Code5.6.1 Parity Encoder and Decoder5.7 Product Notes5.8 Uses of Hamming Codes
6 Bounds in Coding Theory
6.1 Definitions6.2 Sphere-Packing Bound6.3 Johnson Bound6.4 Gilbert-Varshamov Bound6.5 Hamming Bound6.6 Singleton Bound6.7 Plotkin Bound6.8 Griesmer Bound6.9 Zyablov Bound6.10 Bounds in Fn26.11 Reiger Bound6.12 Krawtchouk Polynomials6.13 Linear Programming Bound6.14 Stochastic Bounds for SEC-DED Codes
7 Golay Codes
7.1 Perfect Codes7.1.1 Repetition Code7.1.2 Hamming (7,4,3) Code7.1.3 Binary Golay Codes7.1.4 Extended Binary Golay Codes7.1.5 Ternary Golay Codes7.2 Geometrical Representation7.2.1 Construction of Golay Codes7.3 Other Construction Methods7.4 Finite-State Codes7.5 MacWilliams’ Identity7.6 Golay’s Original Algorithm7.7 Structure of Linear Codes7.7.1 Decoding of Linear Codes
8 Galois Fields
8.1 Finite Fields8.1.1 Extension Fields8.2 Construction of Galois Fields8.3 Galois Fields of Order p8.4 Prime Fields8.5 Binary Fields8.5.1 Polynomial Basis Representation8.6 Arithmetic in Galois Fields8.6.1 Addition in Extension Field GF(2m)8.6.2 Primitive Polynomials8.6.3 Simple Test for Primitiveness8.6.4 Gauss Elimination Method8.7 Polynomials8.7.1 Division Algorithm8.7.2 Euclidean Algorithm8.7.3 Subfields8.8 Polynomial Codes
9 Matrix Codes
9.1 Matrix Group Codes9.2 Encoding and Decoding Matrices9.3 Decoding Procedure9.4 Hadamard Code9.4.1 Hadamard Matrices9.4.2 Nonlinear Codes9.4.3 Hadamard Graph9.4.4 Decoding9.5 Hadamard Transform9.6 Hexacode9.7 Lexicodes9.8 Octacode9.9 Simplex Codes9.9.1 n-Simplex9.9.2 M-Sequences9.10 Block Codes
10 Cyclic Codes
10.1 Definition10.2 Construction of Cyclic Codes10.3 Methods for Describing Cyclic Codes10.4 Quadratic-Residue Codes10.4.1 Generator Polynomials10.4.2 Quadratic-Residue Codes
11 BCH Codes
11.1 Binary BCH Codes11.2 Extended Finite Fields11.3 Construction of BCH Codes11.4 General Definition11.5 General Algorithm11.5.1 BCH (31,16) Code
12 Reed-Muller Codes
12.1 Boolean Polynomials12.2 RM Encoding12.2.1 Encoding Matrices12.3 Generating Matrices for RM Codes12.4 Properties of RM Codes12.5 Classification of RM Codes12.6 Decoding of RM Codes12.6.1 Another Version12.6.2 Decoding First-Order RM Codes12.6.3 One More Algorithm12.7 Recursive Definition12.8 Probability Analysis12.9 Burst Errors12.9.1 Interleaving12.9.2 Interleaving Method12.9.3 Types of Interleavers
13 Reed–Solomon Codes
13.1 Definition13.2 Reed-Solomon’s Original Approach13.3 Parity Check Matrix13.3.1 Properties of RS Codes13.3.2 Extended RS Codes13.3.3 Structure of RS Codes13.3.4 Symbol Errors13.3.5 Solution for Large Alphabet Size13.4 RS Encoding and Decoding13.4.1 Modified Peterson Algorithm13.4.2 LSFR Encoder13.4.3 Encoding and Decoding Architecture13.4.4 Hardware Implementation13.4.5 Software Implementation13.5 Burst Errors13.6 Erasures13.6.1 Reconstruction Algorithm13.7 Concatenated Systems13.7.1 Types of Concatenated Codes13.8 Applications
14 Belief Propagation
14.1 Rational Belief14.2 Belief Propagation14.2.1 Pairwise MRF14.2.2 Messages14.2.3 Belief Read-Out Equation14.2.4 Sum-Product versus Max-Product14.2.5 Complications and Pitfalls14.3 Stopping Time14.3.1 Continuous Local Martingales14.4 Probability Density Function14.5 Log-Likelihood Ratios14.5.1 LLR Algebra14.5.2 Message Passing Algorithm14.5.3 Sum-Product Algorithm
15 LDPC Codes
15.1 Tanner Graphs15.1.1 Row-Graph of a Tanner Graph15.2 Optimal Cycle-Free Codes15.2.1 Codes without Cycle-Free Tanner Graphs15.3 LDPC Codes15.3.1 Channel Capacity15.3.2 Types of Communication Channels15.3.2.1 BEC15.3.2.2 BSC15.4 Hard-Decision Decoding15.5 Soft-Decision Decoding15.6 Irregular LDPC Codes15.6.1 Decoding
16 Special LDPC Codes
16.1 Classification of LDPC Codes16.2 Gallager Codes16.2.1 Construction of Gallager Codes16.2.2 Gallager Decoding16.3 IRA Codes16.4 Systematic Codes16.4.1 Nonsystematic Codes16.4.2 Binary Convolutional Codes16.4.3 Trellis Design16.4.4 Recursive Systematic Codes16.4.5 RSC Decoder16.5 Turbo Codes16.5.1 Log-Likelihood Ratio Method16.6 BP Decoding16.6.1 Probabilistic Shuffled Decoding16.6.2 Probabilistic Check-Shuffled Decoding16.7 Practical Evaluation of LDPC Codes
17 Discrete Distributions
17.1 Polynomial Interpolation17.2 Chernoff Bound17.3 Gaussian Distribution17.4 Poisson Distribution17.5 Degree Distribution17.6 Probability Distributions17.6.1 Discrete Probability Distributions17.6.2 Continuous Probability Distributions17.7 Probability Computation17.8 Soliton Distributions17.8.1 Solitons17.8.2 Ideal Soliton Distribution17.8.3 Robust Soliton Distribution
18 Erasure Codes
18.1 Erasure Codes18.1.1 Forward Error Correcting Codes18.1.2 Vandermonde Matrix18.2. Tornado Codes18.3 Rateless Codes18.4 Online Codes18.5 Fountain Codes
19 Luby Transform Codes
19.1 Transmission Methods19.2 Luby Transform (LT) Codes19.2.1 LT Encoding19.2.2 Decoding of LT Codes19.2.3 Decoder Recovery Rule19.3 Performance19.3.1 Error Floor Problem19.4 Comparison of LT Codes with Other Codes
20 Raptor Codes
20.1 Evolution of Raptor Codes20.1.1 Pre-Code Only Raptor Codes20.1.2 Shokrollahi’s Condition20.1.3 Asymptotically Good Raptor Codes20.1.4 Proof of Asymptotic Performance20.1.5 Finite-Length Raptor Codes20.1.6 Design and Error Analysis of Pre-Code20.1.7 Systematic Raptor Codes20.2 Importance Sampling20.3 Coupon Collector’s Algorithm20.4 Open Problems
A ASCII Table
B Some Useful Groups
C Tables in Finite Fields
D Discrete Fourier Transform
E Software Resources
Bibliography
Index

Content preview from Algebraic and Stochastic Coding Theory

LDPC Codes

15.1 Tanner Graphs

A Tanner graph is a pictorial representation for the parity-check constraints of an ECC (Tanner [1981]). In Tanner graphs each square represents a parity-check bit and each circle connected to a square represents a bit that participates in that parity check. Thus, the nodes of the graph are separated into two distinct sets: c-nodes (top nodes, circles) and p-nodes (bottom nodes, squares). For an (n, k) code, the c-nodes c_i, i = 1, …, n, and the p-nodes p_j, j = 1,…, m, m = n − k, represent the message bits (symbols) and the parity bits, respectively, for a transmitted word c_i (or received word denoted by w_i). These nodes are connected to each other by the following formula:

${\begin{matrix} p-node p_{j} is connected to c-node ... \end{matrix}$

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

A First Course in Mathematical Logic and Set Theory

Publisher Resources

ISBN: 9781466505629

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Algebraic and Stochastic Coding Theory

by Dave K. Kythe, Prem K. Kythe

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.