Tutorial 8 for CSC 310

For this tutorial, you should make sure they understand how syndrome
decoding of linear codes works for the BSC (see section 11a in the
lecture notes).

To demonstrate syndrome decoding, you need to first show how to build
a syndrome decoding table from the parity check matrix.  You could use
a parity check matrix in systematic form, such as

         1 1 0 1 0 0 0
         0 1 0 0 1 0 0
    H =  0 1 1 0 0 1 0
         1 1 1 0 0 0 1

You might review how this lets you create the generator matrix from
the transpose of the left part of H:

        1 0 0 1 0 0 1
    G = 0 1 0 1 1 1 1
        0 0 1 0 0 1 1

This would be used to encode a three-bit message by combining the
three message bits with four parity check bits, which are parity
checks on bits 1&2, bit 2 (ie, just a copy of bit 2), bits 2&3, 
and bits 1&2&3.

When a message r, is received, we compute the syndrome z = Hr.  If
it's zero, then r is a codeword, and the best guess is that it's
the codeword that the sender transmitted.  Otherwise, there must
be at least one error, and we decode by looking up the syndrome z
in the syndrome decoding table, to find the error pattern, n (with
1s in the positions where we guess there are errors).  We then decode
to the codeword r+n.

To make the syndrome decoding table, we first list all possible
non-zero syndromes.  For the example, this list is:

        z

     0 0 0 1
     0 0 1 0
     0 0 1 1
     0 1 0 0
     0 1 0 1
     0 1 1 0
     0 1 1 1
     1 0 0 0
     1 0 0 1
     1 0 1 0
     1 0 1 1
     1 1 0 0
     1 1 0 1
     1 1 1 0
     1 1 1 1
  
We then consider the pssible error patterns, n, in some order with
non-decreasing numbers of 1s (ie, we consider fewer errors before more
errors), adding n to the table above opposite the the value Hn.  Note
that the syndrome will be the same for this error pattern regardless of 
which true codeword, t, was sent, since z = Hr = H(t+n) = Ht+Hn = 0+Hn = Hn.

For the example, we might start by considering n = [1 0 0 0 0 0 0],
which gives the syndrome z = [ 1 0 0 1 ].  So we add this entry to
the table:

        z            n

     0 0 0 1
     0 0 1 0
     0 0 1 1
     0 1 0 0
     0 1 0 1
     0 1 1 0
     0 1 1 1
     1 0 0 0
     1 0 0 1   1 0 0 0 0 0 0
     1 0 1 0
     1 0 1 1
     1 1 0 0
     1 1 0 1
     1 1 1 0
     1 1 1 1

We then go on to consider n = [0 1 0 0 0 0 0], for which z = [ 1 1 1 1 ], 
and add that entry to the table.  After we have considered all single
error patterns, the table should look like

        z            n

     0 0 0 1   0 0 0 0 0 0 1
     0 0 1 0   0 0 0 0 0 1 0
     0 0 1 1   0 0 1 0 0 0 0
     0 1 0 0   0 0 0 0 1 0 0
     0 1 0 1
     0 1 1 0
     0 1 1 1
     1 0 0 0   0 0 0 1 0 0 0
     1 0 0 1   1 0 0 0 0 0 0
     1 0 1 0
     1 0 1 1
     1 1 0 0
     1 1 0 1
     1 1 1 0
     1 1 1 1   0 1 0 0 0 0 0


We now go on to patterns with two errors, such as n = [ 1 1 0 0 0 0 0 ],
for which z = [ 0 1 1 0 ], which we also add to the table.  However,
when we consider n = [ 0 0 0 0 0 1 1 ], for which z = [ 0 0 1 1 ],
we DON'T add this to the table, because we already have an error 
patter for that syndrom with fewer errors in it.  We stop when we've
filled in the entire table.

This procedurue works fine when the number of check bits is fairly
small, as in this example, but will obviously break down when the
number of check bits is too large, since the table grows exponentially
with the number of check bits.