- 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

- Split into message blocks (
- 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**_{0}+ 1***g**_{1}+ 0***g**_{2}+ 0***g**_{3} - = 1*(1101000) + 1*(0110100)
- = (1011100)

- (1100)*G = 1*

- 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

- Denoted

- Codeword split into
- 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_{0}p_{0,j}+ u_{1}p_{1,j}... u_{k-1}p_{(k-1),j}- Where p
_{i,j}are from the parity (**P**) portion of the generator matrix**G**=[**PI**]

- Where p
- 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*****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-k}**P**^{T}]

**G*****H**^{T}=**0**

- The non-identity matrix portions when multiplying input
- 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- (10010
**0**1) --> (10010**1**1)

- (10010

- 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)

- = min{w(
- 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])

- E.g. for the (7,4) example code the minimum distance is 3
since no two columns in
- random-error-detecting capability:
An error code with min distance d
_{min}can detect at most d_{min}-1 errors- can detect 2
^{n}- 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- 2
*t*+1 <= d_{min}<= 2*t*+2 *t*= floor((d_{min}-1)/2)*t*is called the random error correcting capability

- 2

- can detect 2

- Hamming weight (w(
- Standard Array
- Really a matrix
- Used to map 2
^{n}possible received codewords into 2^{k}decoded vectors - Format:
- Where
**v**_{1}...**v**_{2k}are all possible valid codewords of*C*, **e**_{2}...**e**_{2n-k}are the remaining possible received n-tuples (the possible n-tuples after removing the valid codewords**v**_{1}...**v**_{2k}, hence the notation**e**_{i}for 'error'**v**_{1}=**0**(of length n since its an n-tuple)

- Where