Chapter 3 - Linear Block Codes

Terms

• Block Code
  • Split into message blocks (u) of length k
  • Encodes u into codeword v of length n, where n>k
  • Denoted as a (n,k) block code
• Linear Block Code - all possible 2^k codewords form a subspace of the vector space of all n-tuples over GF(2)
  • A binary block code is linear IFF the sum (mod 2) of two codewords is also a codeword
• Generator Matrix
  • Matrix whose rows are linearly independant codewords
  • These codewords are like the basis vectors for the linear block code
  • Every codeword can be represented as a linear combination of these rows
  • Given input vector u, the encoded codeword v= u*G
    • G is is the generator matrix
  • Which is why the matrix G is called the generator matrix since it 'generates' codewords from inputs

    

  • Multiplication can also be done as follows:
    • (1100)*G = 1*g₀ + 1*g₁ + 0*g₂ + 0*g₃
    • = 1*(1101000) + 1*(0110100)
    • = (1011100)
• Systematic Code
  • Codeword split into systematic portion and parity check portion
  • Systematic portion - information bits, which are the same as the input bits to the encoder
  • Parity bits - checking part, which are linear sums of the input/systematic portion
  • The above example (7,4) generator matrix is an example of a linear systematic block code - the four right bits output equal the input four bits
  • The generator matrix in this case contains an identity matrix of size k by k (the matrix above has the identity matrix on the right side of size 4 by 4)
    • Denoted G=[PI], where I is the identity portion
• Parity Check Matrix
  • The non-identity matrix portions when multiplying input u with the generator matrix G are known as the parity-check equations
  • i.e. v_j = u₀p_0,j + u₁p_1,j ... u_k-1p_(k-1),j
    • Where p_i,j are from the parity (P) portion of the generator matrix G=[PI]
  • Parity check matrix (H): (n-k) by n matrix with rows that are
    1. linearly independant and
    2. orthogonal to any vector in the row space of generator matrix G
  • v is a codeword from G IFF v*H^T = 0
  • Parity check matrix H forms a (n,n-k) linear code
  • From matrix G=[PI], H can be created by
    • H=[I_n-kP^T]

    • 

  • G*H^T = 0
• Error vector: e = r + v
  • r = received vector after transmission (rx), possibly with errors due to noise and such
  • v = sent, original transmitted vector
  • If the bits r_i and v_i are the same, then their sum will be 0 (1+1=0, 0+0=0)
  • If the bits are different, their sum will be 1 (1+0=1, 0+1=1)
  • So any nonzero bit in e is an error for that message index
• Syndrome
  • s = r*H^T
  • s = 0 IFF r is a valid codeword (no errors)
  • else r has errors

  • 

  • s = r*H^T = (e+v)H^T = e*H^T+v*H^T = e*H^T (since v*H^T = 0)
  • s is a set of linear combinations of the error digits with the parity matrix
  • Error correction/decoding solves these sets of equations
  • Since there can be multiple solutions, the one with the least amount of errors (nonzero) numbers is considered the solution for BSC codes
    • Example: using the (7,4) code above
    • r = (1001001) but v = (1001011) (second LSB error)
    • s = r*H^T = (111) = ((e0+e3+e5+e6),(e1+e3+e4+e5),(e2+e4+e5+e6))
    • which gives us the set of equations
      • 1 = e0 + e3 + e5 + e6
      • 1 = e1 + e3 + e4 + e5
      • 1 = e2 + e4 + e5 + e6
    • There are 16 possible solutions, but the one with the fewest errors (1s) is (0000010), so that's our chosen error vector
    • To correct r, flip the bits wherever the index in e is 1, so the second LSB in r is flipped
      • (1001001) --> (1001011)
• Minimum Distance
  • Hamming weight (w(v)) - the number of 1s in a vector
  • Hamming distance (d(a,b)) - the number of places the vectors differ (ex: d([1001011],[0100011]) = 3)
  • d(a,b) = w(a + b)
  • minimum distance - d_min is the minimum d(a,b) where a != b within an entire block code C.
    • = min{w(a+b)} where a,b are in C
    • = min{w(x)} where x is in C and x!=0
    • = w_min (d_min = w_min for nonzero vecs) (minimum weight)
  • The minimum distance for C given its parity matrix H is the smallest number of columns in H needed to sum to 0
    • E.g. for the (7,4) example code the minimum distance is 3 since no two columns in H sum to 0, but with 3 cols its possible (ex. [110]+[011]+[101] = [000])
  • random-error-detecting capability: An error code with min distance d_min can detect at most d_min-1 errors
    • can detect 2ⁿ - 2^k error patterns of length n (fraction of total possible codeword combos) (detectable error patterns)
    • An 'error' pattern is an impossible sequence of bits, for length n error patterns it's the entire codeword
    • There are 2^k-1 undetectable error patterns since a sent codeword could have errors such that the received bits are another different yet valid codeword
    • Block code C can correct all error patterns with t or fewer errors, where
      • 2t+1 <= d_min <= 2t+2
      • t = floor((d_min-1)/2)
      • t is called the random error correcting capability
• Standard Array
  • Really a matrix
  • Used to map 2ⁿ possible received codewords into 2^k decoded vectors
  • Format:
    • Where v₁...v_2^k are all possible valid codewords of C,
    • e₂...e_2^n-k are the remaining possible received n-tuples (the possible n-tuples after removing the valid codewords v₁...v_2^k, hence the notation e_i for 'error'
    • v₁ = 0 (of length n since its an n-tuple)
  • Each entry in the array is unique (the rows are 'disjoint (no intersections) and so are the columns')
  • Each row is a 'coset' of C
  • The first entry in each row is the 'coset leader/representative'
  • The columns of the standard array are used to decode the codewords
    • The correct version of a received vector is in its corresponding column (any of v_1...2^k) if the error pattern (vector with ones where the errors are (e_2...2^n-k)) which caused it is any coset leader. Example:
      • e₂ = 100000 (coset leader for row 2)
      • v₃ = 101010 (first entry of column 3)
      • Received vector r = 001010 = e₂+v₃ (error in first MSB)
      • So the correct version is v₃, the first entry in the third column
    • The codeword will be properly corrected IFF the error pattern is a coset leader, so the coset leaders are called 'correctable error patterns'
  • All n-tuples of the same coset have the same syndrome
  • Each coset has a different syndrome
  • Using the above two properties, decoding can be done as follows (called 'syndrome decoding' or 'table lookup decoding'):
    • For initialization, create a table of the 2^n-k coset leaders and their corresponding syndrome
    • Compute the syndrome of the receieved vector r (s = r*H^T)
    • Use the look up table to find the corresponding coset leader e_l for that syndrome (s)
    • Decode r into the codeword v^* = r + e_l
    • Example:

      

Dual Code

• 2^n-k linear combinations of the rows of parity matrix H
• An (n,n-k) linear code C_d
• Is the null space of linear (n-k) code (v*w=0, where v is any codeword from original code and w is any codeword from the (n,n-k) dual code

Single Parity Check Codes (SPC)

• Linear block code with a single parity check digit
• The parity digit is the mod 2 sum of all digits in the unencoded message
• The encoded message is the parity digit + the original message, so it generates a (k+1,k) code
• Codeword v=(p,u0,u1,u2,...u(k-1))
• p=1 if weight of unencoded u is odd (odd number of 1s)
• p=0 if weight of unencoded u is even (even number of 1s)
• Generator matrix and Parity Check Matrix =

  

• Also called an "even parity check code" because all codewords have even weights (even amount of 1s)

Repitition Code

• Code of (n,1) where the code is either all zeros or all ones
• Made by repeating the input bit n times
• Generator matrix G=[1,1,1,...,1]
• (n,1) rep code and (n,n-1) SPC codes are dual codes of each other
• Rep code and SPC codes are combined for constructing "long, powerful codes"

Self Dual Code

• Code where its dual code C_d is equal to itself's code C
• Its generator matrix is also its parity matrix; G*G^T=0
• Code of size (n,n/2) and n must be even; its code rate is 1/2
• Example self-dual code is the (24,12) Golay code