Information Theory And Coding

Two binary symmetric channels are connected in cascade as shown in the figure below. Find the overall channel capacity of the cascaded connection, assuming that both channels have the same transition probability.

a) In the transition probability diagram of a Binary Symmetric Channel, the input binary symbols Q and 1 occur with equal probability. Find the probabilities of the binary symbols and 1 appearing at the channel output.

b) Prove that the mean of the strictly stationary process is a constant.

c) Let p denote the probability of some event. Plot the amount of information gained by the occurrence of this event for <= p <= 1.

d) Define coset and coset leaders?

e) State the differences between source and channel coding?

f) What is the dual of (n,k) linear block code.

g) What do you mean by systematic and non-systematic codes? Give examples

h) Find out primitive polynomials for a (7,4) cyclic code.

i)Define free distance of a convolutional code.

j) Define terms hamming distance, hamming weight and minimum distance 

Consider the (31, 15) Reed-Solomon code. Find:

i) How many bits are there in a symbol of the code. 

ii) What is the block length in bits?

iii) What is the minimum distance of the code?

iv) How many symbols in error can the code correct? 

For the (7,4) Hamming code described by the following generator matrix, construct the eight code words in the dual code. Also, find the minimum distance of the dual code determined.

A black-and-white television picture may be viewed as consisting of approximately 3x105 elements, each of which may occupy one of 10 distinct brightness levels with equal probability. Assume that the rate of transmission is 30 picture frames per second and the signal-to-noise ratio is 30dB. Using the information capacity theorem calculate the minimum bandwidth required to support the transmission of the resulting video signal .

State and explain channel coding theorem. Define capacity boundary with the help of bandwidth-efficiency diagram.

A voice grade channel of the telephone network has a band 3.4 kHz.

i) Calculate the information capacity of the telephone channel for a signal-to-noise ratio of 30 dB

. ii) Calculate the minimum signal-to-noise ratio required information transmission through the telephone channel at 9600 b/s.

Consider the continuous random variable Y defined by Y=X+N. Where X and N we statistically independent. Show the conditional differential entropy of Y, given X, equals h(Y/X) = h(N), where h(N) is the differential entropy of N.

Consider a discrete memory less source with source alphabet S={s₀,s₁,s₂} and source statistics (0.7,0.15,0.15). 

i)Calculate the entropy of the source. 

ii)Calculate the entropy of the second-order extension of the source

Two binary random variables X and Y are distributed according to the joint distributions p(X=Y=0)=p(X=0,Y=1)=(X=Y=1)=1/3. Compute H(X), H(Y). H(Y/X), H(X/Y) and H(X,Y).

Consider a sequence of letters of English alphabet with their probabilities of occurrence as given here: 

Compute the two different Huffman codes for this sets of alphabet. Hence, for each of the two codes, find the average code word length and variance of the average code word length over the ensembles of the letters.

a) In the transition probability diagram of a Binary Symmetric Channel, the input binary symbols Q and 1 occur with equal probability. Find the probabilities of the binary symbols and 1 appearing at the channel output.

b) Prove that the mean of the strictly stationary process is a constant.

c) Let p denote the probability of some event. Plot the amount of information gained by the occurrence of this event for <= p <= 1.

d) Define coset and coset leaders?

e) State the differences between source and channel coding?

f) What is the dual of (n,k) linear block code.

g) What do you mean by systematic and non-systematic codes? Give examples

h) Find out primitive polynomials for a (7,4) cyclic code.

i)Define free distance of a convolutional code.

j) Define terms hamming distance, hamming weight and minimum distance 

Consider the (7,4) Hamming code defined by the generator polynomial g(X)=1+X+X³ . The code word 0111001 is sent over a noisey channel, producing the received word 0101001 that has a single error Determine the syndrome polynomial s(X) for this received word and show that it is identical to the error polynomial e(X).

Explain the Viterbi algorithm for the decoding of convolution code with suitable example. 

(b) Explain the decoding procedure of BCH codes. How syndrome computation can be utilized for the decoding of BCH codes.

(a) Write short note on Golay Code.

(b) Explain the fundamental properties of cyclic codes.

(a) Explain how block codes can be used for burst-error correction with suitable example. 

 (b) Calculate the amount of information if binary digit occur with equal likehood in a binary PCH system.

(a) A discrete source emits one of five symbols once every millisecond with probabilities 1/2, 1/4, 1/8, 1/16, and 1/16 respectively. Determine the information content of each symbol, source entropy and information rate. 

Explain Shannon-Fano encoding algorithm with suitable example.

(b) Explain McMillan theorem for noiseless coding.

(a) A channel is described by the following channel matrix:

(i) Draw the channel diagram.

(ii) Find the channel capacity.

Discuss the concept of discrete memory less channels.

Give the help of suitable example explain the viterbi algorithm for decoding of convolutional code.

Give the block diagram and explain the operation of any convolutional encoder.

For the (6, 3) Hamming code, the parity check matrix is given by 

(i) Construct the generator matrix.

(ii) Determine the codeword that begin with 110

(iii) If the received vector y is (011010) than calculate the syndrome.

Explain the decoding procedure of BCH codes.

What is the use of syndromes? Explain syndrome decoding for linea rblock codes. Draw the syndrome circuit for an (n,k) systematic linear block code.

A DMS has five symbol x₁, x₂, x₃, x₄, and x₅ with respective probabilities 0.2, 0.15, 0.05, 0.1, and 0.5

(a) Construct a Shannon Fano code for X and calculate the code efficiency.

(b) Construct Huffman code and find code efficiency. 

A channel has the following channel matrix

Explain Shannon theorem in detail, on coding for memory less channel.

Consider a telegraph source having two symbols dot and dash. The dot duration is 0.2 seconds. The dash duration is 2.5 times the dot duration. The probability of dot occuring is twice that of dash and the time between symbol is 0.2 seconds. Calculate the information rate of the telegraph source.

Explain the properties of mutual information.

(b) Explain Gaussian, Poisson and Markov process in detail.

Define of ergodic process. Explain the difference between ergodic process and stationary process.

What is source encoding? Discuss.

How the convolutional code are different from block codes? Discuss.

Write short note on Golay and BCH codes

Explain the fundamental properties of cyclic codes.

What is entropy? Explain its properties.

What are random signals? State the significance of random signals in probability theory.

Consider the following generator matrices for the rate 1/2 turbo codes:

i) Construct the block diagram for this RSC encoder.

ii) Setup the parity-check equation associated with the encoder. 

Explain the following decoding algorithms of a convolution encoder:

i) Maximum likelihood decoding and

ii) Viterbi algorithm 

The encoder in the below ligure has a rate r=1/2 constraint length K=4 convolutional code. Determine the encoder output produced by the message sequence 10111.

Explain the properties of mutual information.

Consider the (3, 1, 2) convolutional code with
and
i) Draw the encoder block diagram.
ii) Find the generator matrix.
iii) Find the code word corresponding to the information sequence (1 1 1 0 1) using time domain approach.

What are convolutional codes? Explain encoding of convolutional codes using transform domain approach.

Witte short notes on:
a. BCH codes.
b. RS codes.
c. Golay codes.
d. Brust error correcting codes.

A (15,5) linear cyclic code has a generator polynomial,

i) Draw the block diagram of an encoder for this code 
ii) Find the code vector for the message polynomial  in systematic form
iii) is code polynomial?

Define Binary cyclic codes. Explain the properties of cyclic codes.

The parity check bits of a (7,4) Hamming code are generated by,

where  are the message bits.
i)Find generator matrix and parky check matrix.
ii) Prove that

Consider a (6,3) linear code whose generator matrix is.

i) Find all code vectors.
ii) Find all the Hamming weights.
iii) Find minimum weight parity check matrix,
iv) Draw the encoder circuit for the above codes.

What are the types of errors and types of codes in error control coding?

A Gaussian channel has a bandwidth of 4 kHz and a two-side noise power spectral density  watts/Hz. The signal power at the receiver has to be maintained at a level less than or equal to 1/10th of milliwatt. Calculate the capacity of this channel.

State Shannon-Hartley theorem and explain its implications.

A source has an alphabet consisting of seven symbols A, B, C, D, E, F & G with probabilities 1/4, 1/4, 1/8, 1/8, 1/8, 1/16, and 1/16 respectively. Construct Huffman Quarternery code. Find coding efficiency.

The noise characteristics of a non-symmetric binary channel is given in the following figure.

i)
ii) Also find the capacity of the channel with

Show that H(X,Y) = H(Y)+H(X/Y)

Construct a Shannon-Fano ternary code for the following ensemble and find code efficiency and redundancy. Also draw the corresponding code-tree. with

A source emits one of the 5 symbols A, B, C, D & E with probabilities 1/4, 1/8, 1/8, 3/16 and 5/16 respectively in an independent sequence of symbols. Using Shannon's binary encoding algorithm find all the code words for the each symbol. Also find coding efficiency and redundancy.

State the properties of entropy.

For the Markov source model shown in the following figure;
i) Compute the state probabilities.
ii) Compute the entropy of each state.
iii) Compute the entropy of the source.

The output of an information source consists of 128 symbols, 16 of which occur with a probability of 1/32 and the remaining occur with a probability of  1/224. The source emits 1000 symbols per second. Assuming that the symbols are chosen independently, find the average information rate of this source.

(a) What do you mean by spectral density. Explain the properties of power spectral density. 

(e) How cyclic codes can be generated from the generator polynomial.Explain.

(d) What are convolutional codes? How they different from block codes.

(c) What is entropy? Explain alongwith its properties.. 

(b) Define ergodic process. Explain the difference between ergodic process and stationary process. 

(a) What are random signals? State the significance of random signals in probability theory. 

Define self information, entropy of the long independent messages, information rate, symbol rate and mutual information.