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 = 2^m-1
  • Num. information bits = k = 2^m-m-1
  • Num. parity check bits = n - k = m
  • Num. possible error corrections = t = 1
  • Parity check matrix H = [I_m Q]
    • Q = collection of 2^m-m-1 columns with weight >= 2
    • I_m = m x m identity matrix
  • Generator matrix G = [Q^T I_2^m-m-1]
  • Standard array coset leaders = 0 vector plus all 2^m-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 = 2^m - l - 1
  • Num. information bits = k = 2^m - 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(1-z)(1-z²)^(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 = 2^m
  • Dimension = k(r,m) = 1 + bin(m,1)+bin(m,2)+...+bin(n,r)
    • bin(x,y) = binomial coefficient
  • Min distance = d_min = 2^m-r
• Information bits can be reconstructed as different combinations of sums of the encoded bits
  • e.g. u₀ = v₀+v₁+v₂+v₃ = v₄+v₅+v₆+v₇ = ...
  • 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 I₁₂]
    P = parity matrix which can be found here (matrix B)
    • P^T = P
  • Parity check matrix H = [I₁₂ P] = [I₁₂ P^T]
  • Decoding process:
    1. Compute syndrome s = received * H^T
    2. if weight(s) <= 3
       • error vec e = (s, 0) (0 is length 12)
       • Goto 8
    3. if weight(s + p_i) <= 2 for any row p_i in P
       • error vec e = (s + p_i, uⁱ) (uⁱ 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 + p_i) == 2 for any row p_i in P
       • error vec e = (uⁱ, s*P + p_i)
       • goto 8
    7. Decoding error if this step is reached and not skipped
    8. Calculate result = (received codeword) + e
  • C++ Implementation here