- 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
- 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...2k}) if the error pattern (vector with ones where the errors are (**e**_{2...2n-k})) which caused it is any coset leader. Example:**e**_{2}= 100000 (coset leader for row 2)**v**_{3}= 101010 (first entry of column 3)- Received vector
**r**= 001010 =**e**_{2}+**v**_{3}(error in first MSB) - So the correct version is
**v**_{3}, 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'

- The correct version of a received vector is in its corresponding
column (any of
- 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:

- For initialization, create a table of the 2

- 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

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

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

- 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