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)