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
linearly independant and
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]
Parity check matrix formation
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 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([1001011],[0100011]) = 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. [110]+[011]+[101] = [000])
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'