undefined | unit 4 digital receiver

Unit-4

Digital Receiver

Q1) Apply Shannon’s encoding (binary algorithm) to the following set of messages and obtain code efficiency and redundancy.

m 1	m 2	m 3	m 4	m 5
1/8	1/16	3/16	¼	3/8

A1) Step 1:

The symbols are arranged according to non-incraesing probabilities as below:

m 5	m 4	m 3	m 2	m 1
3/8	¼	3/16	1/16	1/8
P 1	P 2	P 3	P 4	P 5

The following sequences of are computed

= 0

P1 + = 3/8 + 0 = 0.375

= P2 + = ¼ + 0.375 = 0.625

= P3 + = 3/16 + 0.625 = 0.8125

= P4 + = 1/16 + 0.8125 = 0.9375

= P5 + = 1/8 + 0.9375 = 1

Step 3:

The smallest integer value of li is found by using

2 li ≥ 1/Pi

For i=1

2 l1 ≥ 1/P1

2 l1 ≥ 1/3/8 = 8/3 = 2.66

The samllest value ofl1 which satisfies the above inequality is 2 therefore l1 = 2.

For i=2 2 l2 ≥ 1/P2 Therefore 2 l2 ≥ 1/P2

2 l2 ≥ 4 therefore l2 = 2

For i =3 2 l3 ≥ 1/P3 Therefore 2 l3 ≥ 1/P3 2 l3 ≥ 1/ 3/16 = 16/3 l3 =3

For i=4 2 l4 ≥ 1/P4 Therefore 2 l4 ≥ 1/P4

2 l4 ≥ 8 Therefore l4 = 3

For i=5

2 l5 ≥ 1/P5 Therefore

2 l5 ≥ 16 Therefore l5=4

Step 4

The decimal numbers are expanded in binary form upto li places as given below.

= 0

0.375

0.375 x2 = 0.750 with carry 0

0.75 x 2 = 0.50 with carry 1

0.50 x 2 = 0.0 with carry 1

Therefore

(0.375) 10 = (0.11)2

= 0.625

0.625 X 2 = 0.25 with carry 1

0.25 X 2 = 0.5 with carry 0

0.5 x 2 = 0.0 with carry 1

(0.625) 10 = (0.101)2

= 0.8125

0.8125 x 2 = 0.625 with carry 1

0.625 x 2 = 0.25 with carry 1

0.25 x 2 = 0. 5 with carry 0

0.5 x 2 = 0.0 with carry 1

(0.8125) 10 = (0.1101)2

= 0.9375

0.9375 x 2 = 0.875 with carry 1

0.875 x 2 = 0.75 with carry 1

0.75 x 2 = 0.5 with carry 1

0.5 x 2 = 0.0 with carry 1

(0.9375) 10 = (0.1111)2

= 1

Step 5:

and l1 = 2 code for S1 ----00

=(0.011) 2 and l2 =2 code for S2 ---- 01

= (.101)2 and l3 =3 code for S3 ------- 101

= (.1101)2 and l4 =3 code for S ----- 110

= (0.1111)2 and l5 = 4 code for s5 --- 1111

The average length is computed by using

L =

= 3/8 x 2 + ¼ x 2 + 3/16 x 3 + 1/8 x 3 + 1/16 x 4

L= 2.4375 bits/msg symbol

The entropy is given by

H(s) = 3/8 log (8/3) + ¼ log 4 + 3/16 log 16/3 + 1/8 log 8 + 1/16 log 16

H(s) =2.1085 bits/msg symbol.

Code efficiency is given by

ηc = H(s)/L = 2.1085/2.4375 = 0.865

Percentage code effeciency = 86.5%

Code redundancy

R ηc = 1 - ηc = 0.135 or 13.5%.

Q2) Given the messages X1,X2,X3,X4,X5 and X6 with respective probabilities of 0.4,0.2,0.2,0.1,0.07 and 0.03. Construct a binary code by applying Huffman encoding procedure . Determine the efficiency and redundancy of the code formed.

A2)

Now Huffmann code is listed below:

Source Symbols	Pi	Code	Length (li)
X1	0.4	1	1
X2	0.2	01	2
X3	0.2	000	3
X4	0.1	0010	4
X5	0.07	00110	5
X6	0.03	00111	5

Now Average length (L) = li

L = 0.4 x 1 + 0.2 x 2 + 0.2 x 3 + 0.1 x 4 + 0.07x 5 + 0.03 x 5

L = 2.3 bits/msg symbol.

Entropy H(s) = = log 1/Pi

0.4 log 1/0.4 + 0.2 log 1/0.2 + 0.1 log 1/0.1 + 0.07 log 1/0.07 + 0.03 log 1/0.03

H(s) = 2.209 bits /msg symbol.

Code effeciency = ηc = H(s) /L = 2.209/2.3 = 96.04%.

Q3) Given are the messages X1,X2,X3,X4,X5,X6 with respective probabilities 0.4,0.2,0.2,0.1,0.07 and 0.03. Construct a binary code by applying Shannon-fano encoding procedure . Determine code effeciency and redundancy of the code.

A3) Applying Shannon-fano encoding procedure

Average length L is given by

L =

= 0.4 x 1 + 0.2 x 3 + 0.2 x 3 + 0.1 x 3 + 0.07 x4 + 0.03 X 4

L = 2.3 bits/msg symbol.

Entropy

H(s) = log 1/Pi

0.4 log 1/0.4 + 2x 0.2 log 1/0.2 + 0.1 log 1/0.1 + 0.07 log 1/0.07 + 0.03 log 1/0.03

H(s) = 2.209 bits/msg symbol.

Code Efficiency = ηc = H(s) / L = 2.209/2.03 = 96.04%

Code Redundancy = R ηc = 1- ηc = 3.96%

Q4) You are given four messages X1 , X2 , X3 and X4 with respective probabilities 0.1,0.2,0.3,0.4

Device a code with pre-fix property (Shannon fano code) for these messages and draw the code.

Calculate the efficiency and redundancy of the code.

Calculate the probabilities of 0’s and 1’s in the code.

A4) Average length L = li

= 0.4 x1 + 0.3 x 2 + 0.2 x 3 + 0.1 x3

L = 1.9 bits/symbol.

Entropy H(s) = log 1/Pi

= 0.4 log 1/0.4 + 0.3 log 1/0.3 + 0.2 log 1/0.2 + 0.1 log 1/0.1

H(s) = 1.846 bits/msg symbol.

Code efficiency ηc = H(s) / L = 1.846/1.9 = 97.15%

Code Redundancy = R ηc = 1- ηc = 2.85%

The code tree can be drawn

The probabilities of 0’s and 1’s in the code are found by using the

P(0)= 1/L no of 0’s in code xi) (Pi)

= 1/1.9 [ 3 x 0.1 + 2x 0.2 + 1x 0.3 + 0(0.4)]

P(0) = 0.5623

P(1) = 1/L no of 1’s in code xi) (Pi)

= 1/1.9 [ 0x0.1+1x0.2+1x0.+1x0.4]

P(1) = 0.4737

Q5) Construct a Shannon-fano ternary code for the following ensenble and find the code efficiency and redundancy.Also draw the corresponding code tree.

S = { S1,S2,S3,S4,S5,S6,S7}

P={ 0.3,0.3,0.12,0.12,0.06,0.06,0.04} with

X= {0,1,2}

A5)

The average length of the ternary tree is given by

L = li -----------------(1)

= 0.3 x 1 + 0.3 x 1 + 0.12 x 2 +0.12 x 2 + 0.06 x3 +0.06x 3 +0.04 x 3

L = 1.56 trinits/msg symbol.

Entropy in bits/msg symbolis given by

H(s) = log 1/Pi

= 0.3 log 1/0.3 x 2 + 0.12 log1/0.12 x2 + 0.06 log 1/0.06 x 2 +0.04 log 1/0.04

= 2.4491 bits/msg symbol.

Now entropy in r-ary units per message symbol is given by

H r (s) = H(s) / log 2 r

r=3

H3 (s) = H(s) / log 2 3 = 2.4419/ log 2 3 = 1.5452.

The terenary coding effeciency is given by

ηc = H3(s) / L = 1.5452/ 1.56 = 0.99 bits/msg symbol.

ηc = 99.05%

Q6) Explain RLE Algorithm.

A6) RLE is probably the easiest compression algorithm there is. It replaces sequences of the same data values within a file by a count number and a single value.

Suppose the following string of data (17 bytes) has to be compressed:
ABBBBBBBBBCDEEEEF

Using RLE compression, the compressed file takes up 10 bytes and could forms like this:
A *8B C D *4E F

The repetitive strings of data are replaced by a control character (*) followed by the number of repeated characters and the repetitive character itself.

The control character is not fixed, it can differ from implementation to implementation.

If the control character itself appears in the file then one extra character is coded.

RLE encoding is only effective if there are sequences of 4 or more repeating characters because three characters are used to conduct RLE so coding two repeating characters would even lead to an increase in file size.

Q7) Explain FHSS.

A7) This is frequency hopping technique, where the users are made to change the frequencies of usage, from one to another in a specified time interval, hence called as frequency hopping. For example, a frequency was allotted to sender 1 for a particular period of time. Now, after a while, sender 1 hops to the other frequency and sender 2 uses the first frequency, which was previously used by sender 1. This is called as frequency reuse.

The frequencies of the data are hopped from one to another in order to provide a secure transmission. The amount of time spent on each frequency hop is called as Dwell time.

Fig: FHSS

Q8) Compare FHSS and DSSS.

A8)

FHSS	DSSS
Multiple frequencies are used	Single frequency is used
Hard to find the user’s frequency at any instant of time	User frequency, once allotted is always the same
Frequency reuse is allowed	Frequency reuse is not allowed
Sender need not wait	Sender has to wait if the spectrum is busy
Power strength of the signal is high	Power strength of the signal is low
Stronger and penetrates through the obstacles	It is weaker compared to FHSS
It is never affected by interference	It can be affected by interference
It is cheaper	It is expensive
This is the commonly used technique	This technique is not frequently used

Q9) Explain OFDM.

A9)

The Orthogonal Frequency Division Multiplexing (OFDM) transmission scheme is the optimum version of the multicarrier transmission scheme. In the past, as well as in the present, the OFDM is referred in the literature Multi-carrier, Multi-tone and Fourier Transform.

The concept of using parallel data transmission and frequency multiplexing was published in the mid-1960s. After more than thirty years of research and development, OFDM has been widely implemented in high-speed digital communications.

Due to recent advances of digital signal Processing (DSP) and Very Large-Scale Integrated circuit (VLSI) technologies, the initial obstacles of OFDM implementation such as massive complex computation, and high-speed memory do not exist anymore.

The use of Fast Fourier Transform (FFT) algorithms eliminates arrays of sinusoidal generators and coherent demodulation required in parallel data systems and makes the implementation of the technology cost effective (Weinstein and Ebert, 1971).

The OFDM concept is based on spreading the data to be transmitted over a large number of carriers, each being modulated at a low rate. The carriers are made orthogonal to each other by appropriately choosing the frequency spacing between them.

In contrast to conventional Frequency Division Multiplexing, the spectral overlapping among sub-carriers are allowed in OFDM since orthogonality will ensure the subcarrier separation at the receiver, providing better spectral efficiency and the use of steep bandpass filter was eliminated.

OFDM transmission system offers possibilities for alleviating many of the problems encountered with single carrier systems. It has the advantage of spreading out a frequency selective fade over many symbols. This effectively randomizes burst errors caused by fading or impulse interference so that instead of several adjacent symbols being completely destroyed, many symbols are only slightly distorted.

This allows successful reconstruction of majority of them even without forward error correction. Because of dividing an entire signal bandwidth into many narrow sub bands, the frequency response over individual sub bands is relatively flat due to sub band are smaller than coherence bandwidth of the channel. Thus, equalization is potentially simpler than in a single carrier system and even equalization may be avoided altogether if differential encoding is implemented.

The orthogonality of subchannels in OFDM can be maintained and individual subchannels can be completely separated by the FFT at the receiver when there are no intersymbol interference (ISI) and intercarrier interference (ICI) introduced by the transmission channel distortion.

Since the spectra of an OFDM signal is not strictly band limited, linear distortions such as multipath propagation causes each subchannel to spread energy into the adjacent channels and consequently cause ISI.

One way to prevent ISI is to create a cyclically extended guard interval, where each OFDM symbol is preceded by a periodic extension of the signal itself. When the guard interval is longer than the channel impulse response or multipath delay, the ISI can be eliminated.

By using time and frequency diversity, OFDM provides a means to transmit data in a frequency selective channel. However, it does not suppress fading itself. Depending on their position in the frequency domain, individual subchannels could be affected by fading.

This requires the use of channel coding to further protect transmitted data. Coded OFDM combined with frequency and time interleaving is considered the most effective means for a frequency selective fading channel (Shelswell, 1995).

Q10) Explain Shannon’s encoding algorithm.

A10) The following steps indicate the Shannon’s procedure for generating binary codes.

Step 1:

List the source symbols in the order of non-increasing probabilities

S = {S1,S2,S3……………………Sq} with P = {P1,P2,P3…………………..Pq}

P1 ≥P2 ≥P3 ≥………………….Pq

Step 2

Compute the sequences