Decoding Strategy Notes

The [7,4,3] $_{\QTR{Large}{2}}$ Hamming Code :

The matricies:

MATH and MATH

Again, given we encode it by multiplying on the right by

$\hspace{2in}$

$\$ If is correctly received
Let Suppose there is a single bit transmission error:

The vector received is of the form where , $\QTR{Large}{1}$ in the position $\QTR{Large}{0}$ in every other position.

Since , which is just the row of $\QTR{Large}{H\ }$ , the bit is an error.

______________________________________________________________________________________

Decoding Strategies:

Definition: Given a Channel a Decoding Strategy is a function .

$\hspace{1.5in}$ To be read, "Given that is the output, was the input.

In general, Hamming Distance is not a Decoding Strategy, Why? What additional relationships between code words is required to make it one?
- Working in , the Hamming Distance Decoding Strategy would be, pick a set of code words. For each code word map all words that are at most one bit away onto that code word.
  
  where $\QTR{Large}{x}$ is a code word and $\QTR{Large}{y}$ differs from $\QTR{Large}{x}$ by at most one bit.
  
  This is called The Hamming Ball of radius $\QTR{Large}{1}$ around $\QTR{Large}{x}$ . The problem is that, in general $\QTR{Large}{d}$ is not well defined because some words in may not be within $\QTR{Large}{1}$ of a code word. Indeed sometimes there is no set of code words that avoids this problem.
  
  A good example is . The Hamming Ball of radius $\QTR{Large}{1}$ around any code word contains $\QTR{Large}{9}$ words. But there are possible eight-bit words, and you can't divide $\QTR{Large}{256\ }$ words into disjoint sets of $\QTR{Large}{9}$ .
- The Hamming Distance Decoding Strategy for the Hamming Code is a Perfect Code. The space of output code words is , possible code words. There are "error free" $\QTR{Large}{\ }$ codewords ( ) and The Hamming Ball of radius $\QTR{Large}{1}$ around any code word contains words and
- To give a formal definition of we need defined by ,
  
  whereis the $\ \QTR{Large}{i}$ th row of $\QTR{Large}{H.}$
  
  We also use projection onto the last $\QTR{Large}{4}$ bits in
  
  Define
Given a vector of input probabilities, , the Maximum Likelihood Strategy is:

Compute and define where

As defined, is the Maximum Likelihood Strategy really a strategy? What are the issues?
- No, since two code words might have the same maximum probability.
- Suppose the probability of a single bit error is $\QTR{Large}{0.01}$ and that all bits are independent. The probability of a word being sent correctly or with at most one bit error is $\QTR{Large}{0.997}$
- (Followup Exercise ) Compute where $\ \QTR{Large}{y}\$ is an error word, where $\QTR{Large}{y}\$ is an valid code word.
- (Followup Exercise ) What can be said about the Hamming Ball Strategy and Maximum Likelihood Strategy for Perfect Codes

___________________________________________________________________________________________

Mackay Lectures 6 and 7 - The Three Door Problem

The above image is from MacKay's Lectures

The Description:

The Host hides a money prize behind one of three randomly chosen doors
.
The Player chooses a door, say 1.to simplify the discussion of the problem. The essential calculation is not affected
.
The Host opens either door 2 or door 3 using the following rules:
- If the money is behind door 1 open 2 or 3 at random, flip a coin.
- If the money is behind door 2 open 3 and if it is behind 3 open 2.

The Question: Suppose the Host opens door 3, should the Player open door 1 or open door 2.?

___________________________________________________________________________

The Calculations:

The Random Variables:

The door that the money is hidden behind: $\QTR{Large}{M}$ , which takes on the values with
The door that the Host opens $\QTR{Large}{O}$ , which takes on the values
- Given 1., we would predict that see below

The Conditional Distribution:

In 3. of the Description above, we are not given a joint probability distribution, we are given a conditional probability distribution $\QTR{Large}{C.}$

MATH

_________________________________________________________________________

Some notes:

Check that

If the money prize is hidden using a uniform distribution the door opened is a uniform distribution.
Is there a Shannon Clue in the facts that and ?
The Three Door Problem logic can be considered anologous to Noisy Channel logic. The input alphabet is

The output alphabet is , the channel matrix is $\QTR{Large}{C}$ , and we given the output, the door opened, weare asked to infer the input, where the prize is.

.
The door that the Player chooses is NOT a Random Variable it is a Decoding Strategy

______________________________________________________________________________

The Posterior Distribution:

MATH

Read: Given that door 3 is opened The probability that it is behind door 1 is $\QTR{Large}{1/3}$ , door 2 is $\QTR{Large}{2/3}$ and door 3 is $\QTR{Large}{0}$ .