ASSIGNMENT NO 01

ALGEBRAIC CODING THEORY

SUBMITTED TO: Dr ATIF HASAN SOORI

SUBMITTED BY: M NUMAN SHAHZAD
REGISTRATION ID: 240445
CLASS: PhD-MTH-II
SUBMITTED ON: 14-10-2024
Q.1: Suppose that codewords from the binary code {000, 100, 111} are being sent over a
BSC (binary symmetric channel) with crossover probability p = 0.03. Use the maximum
likelihood decoding rule to decode the following received words:
(a) 010 (b) 011 (c) 001.
Solution:
First Method:
Pr{r | b} = ⏟
arg max ¿
bE B
dist (r | b1) = dist (010 | 000) = 1, here b = b1
Pr{010 | 000} = ¿ = (0.97)3 (0.0309) = (0.9126) (0.0309) = 0.0281
dist (r | b2) = dist (010 | 100) = 2, here b = b2
Pr{010 | 100} = ¿ = (0.97)3 (0.0309)2 = 0.0008714
dist (r | b3) = dist (010 | 111) = 2, here b = b3
Pr{010 | 111} = ¿= (0.97)3 (0.0309)2 = 0.0008714
b^ ( r )=arg
⏟ max Pr {r | b} = argmax {0.0281, 0.0008714, 0.0008714}
bE B
Since the max likelihood probability: Pr{010 | 000}.
By the maximum decoding rule, 010 is decoded to 000.

Second Method:

(a) We have the following:

P(010 received | 000 sent) = P(1 received | 0 sent) P(0 received | 0 sent)2
= p (1 − p)2
= (0.03) (0.97)2
= 0.028

P(010 received | 100 sent)

= P(0 received | 1 sent) P(1 received | 0 sent) P(0 received | 0 sent)
= p2 (1 − p)
= (0.03)2 (0.97) = 0.000873
≈ 0.0009
P(010 received | 111 sent) = P(0 received | 1 sent)2 P(1 received | 1 sent)
= p2 (1 − p)
= (0.03)2 (0.97) = 0.000873
≈ 0.0009
By the maximum decoding rule, 010 is decoded to 000.

(b) P(011 received | 000 sent) = P(0 received | 0 sent) P(1 received | 0 sent)2
= p2 (1 − p)
= (0.03)2 (0.97) = 0.000873
≈ 0.0009
P(011 received | 100 sent) = P(0 received | 1 sent) P(1 received | 0 sent)2
= p3 = (0.03)3
= 0.000027
 P(011 received | 111 sent) = P(0 received | 1 sent) P(1 received | 1 sent)2
= p (1 − p)2 = (0.03) (0.97)2
= 0.028

By the maximum decoding rule, 011 is decoded to 111

(c) P(001 received | 000 sent) = P(1 received | 0 sent) P(0 received | 0 sent)2
= p (1 − p)2
= 0.028
P(001 received | 100 sent) = P(0 received | 1 sent)P(0 received | 0 sent)P(1 received |
0 sent)
= p2 (1 − p) = (0.03)2 (0.97) = 0.000873
≈ 0.0009
P(001 received | 111 sent) = P(0 received | 1 sent)2 P(1 received | 1 sent)
= p2 (1 − p) = (0.03)2 (0.97) = 0.000873
≈ 0.0009

By the maximum decoding rule, 001 is decoded to 000.

Q. 2: Consider a memoryless binary channel with channel probabilities P(0 received | 0

sent) = 0.7, P(1 received | 1 sent) = 0.8. If code words from the binary code {000, 100, 111}
are being sent over this channel, use the maximum likelihood decoding rule to decode the
following received words: (a) 010 (b) 011 (c) 001.

Solution:

(a) P(010 received | 000 sent) = P(1 received | 0 sent) P(0 received | 0 sent)2
= (0.7)2 (0.3) = 0.147
P(010 received | 100 sent) = P(0 received | 1 sent) P(1 received | 0 sent) P(0 received | 0
sent)
= (0.2)(0.3)(0.7) = 0.042
P(010 received | 111 sent) = P(0 received | 1 sent)2 P(1 received | 1 sent)
= (0.2)2 (0.8) = 0.032

By the maximum decoding rule, 010 is decoded to 000.

(b) P(011 received | 000 sent) = P(0 received | 0 sent)P(1 received | 0 sent)2

= (0.7) (0.3)2 = 0.063

P(011 received | 100 sent) = P(0 received | 1 sent)P(1 received | 0 sent)2

= (0.2) (0.3)2 = 0.018

P(011 received | 111 sent) = P(0 received | 1 sent) P(1 received | 1 sent)2
 = (0.2) (0.8)2 = 0.128

By the maximum decoding rule, 011 is decoded to 111.

(c) P(001 received | 000 sent) = P(1 received | 0 sent) P(0 received | 0 sent)2

= (0.3) (0.7)2 = 0.147

P(001 received | 100 sent) = P(0 received | 1 sent) P(0 received | 0 sent) P(1 received |
0 sent) = (0.2) (0.7) (0.3) = 0.42

P(001 received | 111 sent) = P(0 received | 1 sent)2 P(1 received | 1 sent)

= (0.2)2 (0.8) = 0.032

By the maximum decoding rule, 001 is decoded to 000.

Q.3: Let C = {001, 011} be a binary code.

(a) Suppose we have a memoryless binary channel with the following probabilities:
P(0 received | 0 sent) = 0.1 and P(1 received | 1 sent) = 0.5. Use the maximum likelihood
decoding rule to decode the received word 000.
(b) Use the nearest neighbor decoding rule to decode 000.

Solution:

(a) P(000 received | 001 sent) = P(0 received | 0 sent)2 P(0 received | 1 sent)

= (0.1)2 (0.5) = 0.005

P(000 received | 011 sent) = P(0 received | 0 sent) P(0 received | 1 sent)2

= (0.1) (0.5)2 = 0.025

By the maximum decoding rule, 000 is decoded to 011.

(b) We have

d(000, 001) = 1 & d(000, 011) = 2.

By the nearest neighbor decoding rule, 000 is decode to 001.

Q.4: For the ternary code C = {00122, 12201, 20110, 22000}, use the nearest neighbor
decoding rule to decode the following received words:
 (a) 01122 (b) 10021 (c) 22022 (d) 20120

Solution:

Received word d(r, 00122) d(r, 12201) d(r, 20110) d(r, 22000) Decoded word
(r)
01122 1 5 4 5 00122
10021 3 3 4 4 Tie b/w 00122
& 12201
22022 3 4 4 2 22000
20120 2 5 1 3 20110

Hence, we assume incomplete decoding.

Another approach to solve this question by coset method, which is given by:

(a) C = {00122, 12201, 20110, 22000} ∈ F 53

01000 + C = {01122, 10201, 21110, 20000}

r = 01122; e = 01000

b = r – e = 01122 – 01000 = 00122

By the nearest neighbor decoding rule, 01122 is decode to 00122.

(c) 00022 + C = {00100, 12220, 20102, 22022}

r = 22022; e = 00022

b = r – e = 22022 – 00022 = 22000

By the nearest neighbor decoding rule, 22022 is decode to 22000.

(d) 00010 + C = {00102, 12211, 20120, 22010}

r = 20120; e = 00010

b = r – e = 20120 – 00010 = 20110

By the nearest neighbor decoding rule, 20120 is decode to 20110.