# Chapter 4 - Important Linear Block Codes

### Terms

• Perfect Code: Has no uncorrectable codewords with <= t errors
• Weight distribution: Set of count of codewords in a code each having the same weight
• E.g. 5 codewords have a weight of 1, etc.
• Weight enumerator: Polynomial function used to calculate the weight distribution of a code
• The coefficients for each degree are the count for that weight
• SEC-DED: Single error correcting, double error detecting

### Hamming Codes

• Min distance of 3
• Corrects single bit errors
• Detects all <= 2 errors
• Is a perfect code (only one besides Golay code)
• Easily decoded using lookup table
• For any m >= 3
• Code Length = n = 2m-1
• Num. information bits = k = 2m-m-1
• Num. parity check bits = n - k = m
• Num. possible error corrections = t = 1
• Parity check matrix H = [Im Q]
• Q = collection of 2m-m-1 columns with weight >= 2
• Im = m x m identity matrix
• Generator matrix G = [QT I2m-m-1]
• Standard array coset leaders = 0 vector plus all 2m-1 tuples with weight 1
• This is why "Perfect Code" definition applies (corrects ALL single bit errors, and has NO other coset leaders besides the ones that correct <= t errors)
• C++ Implementation here ((7,4) example from chapter 3)

### Shortened Hamming Codes

• Made by deleting l columns from H of a hamming code
• Has following parameters:
• Code length = n = 2m - l - 1
• Num. information bits = k = 2m - m - l - 1
• Num. parity bits = n - k = m
• Num. possible error corrections = t = min distance > = 3
• If the columns are removed correctly, will have a min distance of 4
• In this case, can correct single bit errors and detect ALL double errors
• Decoding process
1. If syndrome s is 0, no error occured
2. else
1. If s has odd number of 1s
• result = (matching error pattern) + s
2. else
• Uncorrectable error detected
• Weight enumerator: 1/(n+1) [(1+z)n) + n(1-z)(1-z2)(n-1)/2]

### Reed-Muller Codes

• Multiple random error correction
• Simple construction
• Many choices for decoding (both hard and soft decision)
• Reed decoding algorithm
• Majority-Logic decoding algorithm
• Easily implemented
• For any m,r with 0 <= r <= m, denoted as RM(r,m)
• Code length = n = 2m
• Dimension = k(r,m) = 1 + bin(m,1)+bin(m,2)+...+bin(n,r)
• bin(x,y) = binomial coefficient
• Min distance = dmin = 2m-r
• Information bits can be reconstructed as different combinations of sums of the encoded bits
• e.g. u0 = v0+v1+v2+v3 = v4+v5+v6+v7 = ...
• These are called checksums
• Using the different possible combinations, majority vote on what the decoded bit should be
• The decoded bits are calculated recursively starting with longer checksums then getting shorter
• This is called "Majority Logic Decoding", with the number of recursive steps giving the name "N-step majority logic decoding"
• Errors that happen in earlier steps of decoding affect later steps, called "error propogation"

### Golay Code

• Two versions
• (23,12)
• (24,12)
• (24,12) has an additional parity bit
• Min distance of 8 for (24,12) or 7 for (23,12)
• Many uses, including U.S. space communication programs
• Only other perfect code besides Hamming
• Used as the primary error control system for NASA's Voyager between 1979-1981, used to take pictures of Jupiter and Saturn
• For the (24,12) code:
• Generator matrix G = [P I12]
P = parity matrix which can be found here (matrix B)
• PT = P
• Parity check matrix H = [I12 P] = [I12 PT]
• Decoding process:
1. Compute syndrome s = received * HT
2. if weight(s) <= 3
• error vec e = (s, 0) (0 is length 12)
• Goto 8
3. if weight(s + pi) <= 2 for any row pi in P
• error vec e = (s + pi, ui) (ui is 0 vec except a 1 in the ith position)
• Goto 8
4. Compute s*P
5. if weight(s*P) == 2 or weight(s*P) == 3
• error vec e = (0, s*P)
• goto 8
6. if weight(s*P + pi) == 2 for any row pi in P
• error vec e = (ui, s*P + pi)
• goto 8
7. Decoding error if this step is reached and not skipped
8. Calculate result = (received codeword) + e
• C++ Implementation here