Scribd
Upload
140 views3 pages

Tutorial 2

This document contains 8 problems related to linear codes and error correction codes. Problem 1 involves finding properties of a linear code over F7 and decoding a received word. Problem 2 involves constructing a decoding table and calculating error probabilities for a (5,2) binary linear code. The remaining problems involve determining properties of cyclic codes, BCH codes, and constructing a Galois field.

Uploaded by

amit100singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
140 views3 pages

Tutorial 2

This document contains 8 problems related to linear codes and error correction codes. Problem 1 involves finding properties of a linear code over F7 and decoding a received word. Problem 2 involves constructing a decoding table and calculating error probabilities for a (5,2) binary linear code. The remaining problems involve determining properties of cyclic codes, BCH codes, and constructing a Galois field.

Uploaded by

amit100singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

EEL 710: Tutorial II

Last Date: 2
nd
Oct. 2014
Problem 1.
Let C be the linear code over F
7
(the eld of integers modulo 7) with parity check matrix
H =

6 5 4 3 2 1
5 4 3 2 1 0

(1)
(a) Find the dimension and minimum distance of the code.
(b) Construct a systematic generator matrix for C.
(c) Suppose that y = [111100] is the received word to be decoded. Find all the codewords
that can be produced as output by a minimum-distance decoder applied to y.
Problem 2.
Consider the (5, 2) binary linear code with systematic generator matrix
G =

1 0 1 1 0
0 1 1 0 1

(2)
A, 2-bit message vector u = [u
1
u
2
] is encoded as C = uG = [u
1
u
2
p
3
p
4
p
5
], and transmitted
across a memoryless binary symmetric channel with crossover probability .
(a) Choose as coset leaders the all-zero word, all words of weight 1, and the words 00011 and
10001. Construct the standard array decoding table, together with the syndromes corresponding
to each coset.
(b) If the standard array as above is used for decoding, what is the probability that the
transmitted codeword C is decoded incorrectly?
1
(c) If the code is used only for error detection, what is the probability that any channel
errors that take place during transmission go undetected?
(d) If the standard array of part (a) is used for decoding, what is the probability that the
rst message bit m
1
, is decoded incorrectly?
Problem 3.
A binary linear cyclic block code with a code length of n = 14 has the generator polynomial
g(X) = 1 +X
2
+X
6
.
(a) Determine the number of information and parity check bits in each code vector.
(b) Determine the number of code vectors in the code.
(c) Determine the generator and parity check matrices of the code.
(d) Determine the minimum Hamming distance of the code.
(e) Determine the burst error-correction capability of the code.
(f) Describe briey how to encode and decode this code.
Problem 4.
Problem 4.8 of Information theory, Coding and Cryptography Second Edition R. Bose.
Problem 5.
Problem 4.9 of Information theory, Coding and Cryptography Second Edition R. Bose.
Problem 6.
The (7, 4) cyclic Hamming code has a generator polynomial g(X) = 1 +X
2
+X
3
.
(a) Find the generator matrix for this code in systematic form.
(b) Find the parity check matrix for the code
(c) Suppose the codeword C = [1011010] is transmitted through a channel and the corre-
sponding received word is C = [1010011]. Find the syndrome polynomial associated with this
received codeword.
(d) Find all possible received codewords such that, for the transmitted codeword C =
[1011010], the received codeword has a syndrome polynomial of zero.
Problem 7.
2
(a) Verify that the polynomial p(X) = 1 +X
2
+X
5
is an irreducible polynomial. It can also
be a primitive polynomial. What are the conditions for this to happen?
(b) Construct the Galois eld GF(25) generated by p(X), showing a table with the polyno-
mial and binary representations of its elements.
(c) Determine the minimal polynomials of the elements of the Galois eld GF(25) constructed
in above part.
Problem 8.
Determine the generator polynomial of a binary BCH code of code length n = 31 able to
correct error patterns of size t = 2 or less. Also, determine the value of k and the minimum
Hamming distance of the code.
3

You might also like