# 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 2k 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 Encoding example using a (7,4) generator matrix; addition and multiplication done mod 2
• Multiplication can also be done as follows:
• (1100)*G = 1*g0 + 1*g1 + 0*g2 + 0*g3
• = 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. vj = u0p0,j + u1p1,j ... uk-1p(k-1),j
• Where pi,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*HT = 0
• Parity check matrix H forms a (n,n-k) linear code
• From matrix G=[PI], H can be created by
• H=[In-kPT]
• G*HT = 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 ri and vi 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*HT
• s = 0 IFF r is a valid codeword (no errors)
• else r has errors
• Syndrome calc matrix example using the Generator matrix for the (7,4) code above
• s = r*HT = (e+v)HT = e*HT+v*HT = e*HT (since v*HT = 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*HT = (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(,) = 3)
• d(a,b) = w(a + b)
• minimum distance - dmin 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
• = wmin (dmin = wmin 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. ++ = )
• random-error-detecting capability: An error code with min distance dmin can detect at most dmin-1 errors
• can detect 2n - 2k 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 2k-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 <= dmin <= 2t+2
• t = floor((dmin-1)/2)
• t is called the random error correcting capability
• Standard Array
• Really a matrix
• Used to map 2n possible received codewords into 2k decoded vectors
• Format: • Where v1...v2k are all possible valid codewords of C,
• e2...e2n-k are the remaining possible received n-tuples (the possible n-tuples after removing the valid codewords v1...v2k, hence the notation ei for 'error'
• v1 = 0 (of length n since its an n-tuple)