Practical 3 - DE424

DE424 Practical 3 - Report

Name & Surname: Robert Jaret Thompson Student Number: 24704806 Date: 2 March 2025

Plagiarism Declaration

This submission is entirely my own work, excepting the inclusion of resources explicitly permitted for this assignment, and assistance as noted in the following two items.

• DE424 Practical 3 outline
• Emdw userguide

I have not and will not facilitate plagiarism, such as by distributing any written work or source code created by fellow students. I understand that any code I submit may be inspected for plagiarism detection (either manually or by automated systems).

Signed:

---

The Hamming (7,4) error correction code

In the Hamming (7,4) code, we have:

• Transmitting input bits: $b_0,b_1,b_2,b_3$ which is the original data bits
• Parity check bits: $b_4,b_5,b_6$ which is computed from the information bits
• Receiving bits: $r_0,r_1,r_2,r_3,r_4,r_5,r_6$

Figure 1

3.2 PGM to calculate the check bits $b_4,b_5$ and $b_6$ given input bits $b_0,b_1,b_2$ and $b_3$

a)

Figure 2: Bayes Network (BN) of relationship between input & check bits

b) From Figures 1 & 2, it is observed that $b_4,b_5$ and $b_6$ are bits that are dependent on the input bits.

• The check bit $b_4$ is dependent on the input bits $b_0,b_1,b_2$. It gives the conditional distribution $p(b_4\mid b_0,b_1,b_2)$.
• The check bit $b_5$ is dependent on the input bits $b_1,b_2,b_3$. It gives the conditional distribution $p(b_5\mid b_0,b_2,b_3)$.
• The check bit $b_6$ is dependent on the input bits $b_0,b_2,b_3$. It gives the conditional distribution $p(b_6\mid b_0,b_1,b_3)$.

The input bits $b_0,b_1,b_2,b_3$ are assumed to be independent and this results in the joint distribution of all these components into the following equation:

$$p(b_0,b_1,b_2,b_3,b_4,b_5,b_6)=p(b_4\mid b_0,b_1,b_2)p(b_5\mid b_0,b_2,b_3)p(b_6\mid b_0,b_1,b_3)p(b_0)p(b_1)p(b_2)p(b_3)$$

c)

Similar results for the truth tables of $\tilde{p}(b_5\mid b_0,b_2,b_3)$ and $\tilde{p}(b_6\mid b_0,b_1,b_3)$ are obtained.

d) Conversion of a Bayes Network (BN) to a Markov Network (MN) involves identifying the directed edges from the BN:

• $b_0,b_1,b_2\to b_4$
• $b_0,b_2,b_3\to b_5$
• $b_0,b_1,b_3\to b_6$

Then we have to marry the parents (moralisation) by changing the directed edges into undirected edges and then connecting the parents of each node.

• $b_4$ has parents $b_0,b_1$ and $b_2$ so we add edges between $(b_0,b_1),(b_1,b_2)$ and $(b_0,b_2)$.
• $b_5$ has parents $b_0,b_2$ and $b_3$ so we add edges between $(b_0,b_2),(b_2,b_3)$ and $(b_0,b_3)$.
• $b_6$ has parents $b_0,b_1$ and $b_3$ so we add edges between $(b_0,b_1),(b_1,b_3)$ and $(b_0,b_3)$.

Figure 3: Markov Network

In an MN, the joint distribution is represented as a product of factors $\varphi$ over maximal cliques:

$p(b_0,...,b_6)\propto {\varphi }_1(b_0,b_1,b_2){\varphi }_2(b_0,b_2,b_3){\varphi }_3(b_0,b_1,b_3)$ where ${\varphi }_1:(b_0,b_1,b_2,b_4),{\varphi }_2:(b_0,b_2,b_3,b_5)$ and ${\varphi }_3:(b_0,b_1,b_3,b_6)$

e)

f)

The marginal distributions $p(b_0),p(b_1),p(b_2)$ and $p(b_3)$ are defined in emdw as follows:

rcptr<Factor> ptrb0 = 
	uniqptr<DT>(       
	    new DT(
          {b0},
          {binDom},
          defProb,
          {
            {{0}, 1},
            {{1}, 1},
          } ));

Similar code is used to declare ptrb1 ptrb2 and ptrb3.

    rcptr<Factor> ptrb4gb0b1b2 = 
      uniqptr<DT>( 
        new DT(
          {b0,b1,b2,b4},
          {binDom,binDom,binDom,binDom},
          defProb,
          {
            {{0,0,0,0}, 1},
            {{0,0,0,1}, 0},
            {{0,0,1,0}, 0},
            {{0,0,1,1}, 1},
            {{0,1,0,0}, 0},
            {{0,1,0,1}, 1},
            {{0,1,1,0}, 1},
            {{0,1,1,1}, 0},
            {{1,0,0,0}, 0},
            {{1,0,0,1}, 1},
            {{1,0,1,0}, 1},
            {{1,0,1,1}, 0},
            {{1,1,0,0}, 1},
            {{1,1,0,1}, 0},
            {{1,1,1,0}, 0},
            {{1,1,1,1}, 1},
          } ));

Similar code is used to declare ptrb5gb0b2b3 and ptrb6gb0b1b3which denotes $p(b_5\mid b_0,b_2,b_3)$ and $p(b_6\mid b_0,b_1,b_3)$.

g) Multiplying the probabilities with absorb to get the joint probability $p(b_1,...,b_6)$ as shown in this code and normalize() so that the probabilities add up to 1.

rcptr<Factor> ptrb0b1b2b3b4b5b6 = ptrb4gb0b1b2->absorb(ptrb5gb0b2b3)->absorb(ptrb6gb0b1b3)->absorb(ptrb0)->absorb(ptrb1))->absorb(ptrb2)->absorb(ptrb3)->normalize();
std::cout << __FILE__ << __LINE__ << ": " << *ptrb0b1b2b3b4b5b6 << std::endl;

Figure 5: Joint Probability Distribution $p(b_0,...,b_6)$

h) Arbitrary input bits $b_0=1,b_1=0,b_2=1,b_3=0$ are given and through observeAndReduce will generate values for the check bits given the original four input bits.

std::cout << __FILE__ << __LINE__ << ": " << *ptrb0b1b2b3b4b5b6->observeAndReduce({b0},{1})->observeAndReduce({b1},{0}-> observeAndReduce({b2},{1})->observeAndReduce({b3},{0})->normalize() << std::endl;

3.3 PGM to decode the received $r_0,...,r_6$ bits: binary symmetric channel (BSC) case.

a)

Figure 5: BN with receiving bits included

b) The joint probability distribution for the receiver side builds upon the transmitter-side BN while incorporating the additional noise factors $p(r_i|b_i)$ for each received bit. $p(b_0,...,b_6,r_0,...,r_6)=p(b_4\mid b_0,b_1,b_2)p(b_5\mid b_0,b_2,b_3)p(b_6\mid b_0,b_1,b_3)p(b_0)p(b_1)p(b_2)p(b_3)\times p(r_i\mid b_i)$

c) The error probability $P_e$ is the likelihood that $r_i$ differs from the transmitted bit. If $P_e=0.1$, then when the transmitted bit $b_i$ is 0, there is a 90% chance that $r_i$ is also 0, and a 10% chance it gets flipped to 1.

$b_i$	$r_i$	$p(r_i\mid b_i)$
0	0	$1-P_e$
0	1	$P_e$
1	0	$P_e$
1	1	$1-P_e$
d)

Figure 6: Mn with receiving bits included

e) New factors of the $r_i\forall i=0,...,6$ are created and the error probability $P_e$ is added

rcptr<Factor> ptrr0 = 
	  uniqptr<DT>(
		  new DT(           
              {r0,b0},
              {binDom,binDom},
              defProb,
              {
                {{0, 0}, 0.9},
                {{0, 1}, 0.1},
                {{1, 0}, 0.1},
                {{1, 1}, 0.9},
              } ));

std::cout << __FILE__ << __LINE__ << ": " << *ptrr0 << std::endl;

f) g)

rcptr<Factor> ptrbgr = ptrb0b1b2b3b4b5b6->absorb(ptrR0)->absorb(ptrR1)->absorb(ptrR2)->absorb(ptrR3)->absorb(ptrR4)->absorb(ptrR5)->absorb(ptrR6)->normalize();

    std::cout << __FILE__ << __LINE__ << ": " << *ptrbgr << std::endl;

Figure 8: Normalized joint probability distribution

We are now implementing error correction using probabilistic inference. By multiplying all factors together and normalizing, we compute the posterior joint distribution $p(b_0,\dots ,b_6|\text{observed }{r}_0,\dots ,r_6)$. The goal is to find the most probable original sequence and confirm that the error correction mechanism successfully works. In this case, the most probable sequence for $(b_0,b_1,b_2,b_3,b_4,b_5,b_6)$ is $(1,0,1,1,0,1,0)$ with a 72% chance.

Figure 9: Posterior marginal beliefs $p(b_0=1\mid observedvalues)$