Tutorial VI: Source Coding Fundamentals I

A very Happy New Year to all the readers. It is really long I guess three months and no post on this blog. We, WirelessCafe Team, seriously apologies for that. Through this post, we are continuing our tutorial series on digital communication. In this post we will discuss some fundamentals of source coding and in later posts we will write codes for some source coding algorithms. We will like to remind our readers that we are right now discussing the basics of simulation and soon we will go for OFDM and more advance topics. So lets hit it!

Mutual Information:

The information content provided by the occurrence of the event Y = y_i about the event X = x_i is defined as

Mutual Information

I(x_i;y_j) is called the mutual information between x_i and y_j.

Self Information:

when we talk about the information of a single event X= x_i we called it self information and is denoted as

Self Information

it is a matter of fact, that , a high probability event conveys less information than a low probability event. That is, P(x) = 1 which means I(x) = 0.

Conditional Self Information:

In addition to self information and mutual information, conditional self information as

Conditional Self Information

Average Mutual Information:

the mutual information associated with the pair of the events (x_i,y_j), which are possible outcomes of the two random variables X and Y, we can obtain the average value of the mutual information by simply weighting I(x_i,y_j) by the probability of occurrence of the joint event and summing over all possible joint events.

Mathematically

Average Mutual Information

as a matter of fact, I(X;Y) = 0 when X and Y are statistically Independent. Also I(X;Y) ≥ 0.

Entropy:

Entropy or Average self information denoted as H(X) and defined as

Entropy

Conditional Entropy:

the average conditional self information is called conditional entropy

Conditional Entropy

we also get the relation from the above the equations

Relation Between Information and Entropy

Here is a plot of binary conditional entropy produced in matlab. In next post we will discuss some left over theorems of source coding like Kraft’s inequality and will start some real coding work !

binary entropy function

What is Orthogonal Variable Spreading Factors? (A note about OVSF Codes)

With the advancement in the cellular technology and convergence of wireless technologies, now it is the need to combine two messages having different data rates in an orthogonal manner. Take an example, the date rate of user 1 is r₁ and of user 2 is r₂ and we have to spread the user 1 message by spreading factor s₁ and that of user 2 by s₂, so that we can produce and overall chip rate of ρ. we can use Walsh Hadamard sequences if the spreading factors are powers of 2. The result so obtained is referred to as Orthogonal Variable Spreading factor and is showed in figure 1.

 

Orthogonal Variable Spreading Factor - An Illustration

 

For OVSF the orthogonality requirement can be stated mathematically as (for the given figure)

 

ovsf orthogonality requirement

 

 

This is, code 1, of duration T₁ is orthogonal to all subsequences of code 2, of the same length, and offset by a multiple of T₁, the length of code 1.

Now, as we know, OVSF is important in terms of WCDMA and LTE, the question is how we will generate OVSF codes? We can generate OVSF codes by following algorithm.

Suppose we want to generate OVSF codes of length n₁ and n₂, where n₁ < n₂, then:

1. Construct H_n1 by usual Walsh-Hadamard algorithm.
   
2. Choose one row of matrix H_n1 as the code length of 2ⁿ¹. Let H_n1‘ represent the Hadamard matrix with the selected row removed.
   
3. Continue the Walsh- Hadamard algorithm with H_n1‘: that is
   

 

Modified Matrix for OVSF

 

 

Then continue until desired H_n2‘ is constructed.

1. Choose any row of H_n2‘ as the spreading code of length 2n2
   
2. If a third code is needed, then continue in a similar manner.
   

A matlab function can be downloaded from the given below links. The usage is given below.

Usage

% x = ovsf(y,z)

%x, the output cell array having required OVSF codes

%y, number of codes required

%z, array having length of each code to the base 2 i.e. 2.^2 = 4

%example y = 3 z = [4 2 3]

%this will give a cell array with [1x4] [1x8] [1x16]

%length = 2.^n , enter n in length of array

%The code is not optimized yet, user is free to optimize

%do not forget to leave a comment

 

Download Links:

Resource Center
Matlab File Exchange

================

Author : Ashwini Patankar

A note about PN Sequence

PN sequences or Pseudo Noise sequence is a periodic binary code which is random in nature generated by the use of shift registers, but generated with taking into considerations some generator polynomials. For sequence to be a pseudo noise or pseudo random it should follow the following basic rules. The rules mentioned below are simply mentioned in brief:

1. The relative frequency of 0′s and 1′s are each ½
2. The run lengths of 0′s and 1′s are: ½ of all run lengths are of length 1; ¼ are of length 2; 1/8 are of length 3; and so on.
3. If a PN sequence is shifted by any non zero number of elements, the resulting sequence will have an equal number of agreements and disagreements with respect to the original sequence.

These properties are known also known as balance property, run property, and correlation property respectively. This code is orthogonal in nature. PN sequence is also known as Maximal Length Sequences.

PN sequences are used in spread spectrum systems, like CDMA, WCDMA, and Radar etc. In CDMA IS 95, 64 ling PN sequence codes are used for the identification if the reverse link channels.

The matlab script for generating pn sequence is given below, and also can be downloaded from this link.

refer figure as a companion for the matlab file

 

block diagram of pn sequence generator

 

 

function [op_seq] = pnseq (a, b, c)

% a : no of fliflops; b = tapp _ function starting frm highest order; c = initial stae

%tapp functions or genrator polynomial

%e.g. no of flip flops 4 ==> a = 4

%generator polynomial x4+x+1 ==> b = [1 0 0 1]

%initial state [1 0 0 0] ==> c = [1 0 0 0]

%refere figure to set a relation between tap function and initial state

%

%

%

%

% <

% ———–X____________________________________

% | ___ | _____ ____ _____ |

% |> | | | | | | | | | ^|

% —–| |——–| |—| |——-| |————->o/p

% —– —– —– —-

% x1 + x2 + x3 + x4

%initial state

% 1 0 0 1

%

%take care of the reverse order of genrator polynomial and intiial states

%

%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

close all;

clc;

x = a;

tap_ff =b;

int_stat= c;

for i = 1:1: length(int_stat)

old_stat(i) = int_stat(i);

gen_pol(i) = tap_ff(i);

end

len = (2 ^x)-1;

gen_pol(i+1)= 1;

gen_l = length(gen_pol);

old_l = length(old_stat);

for i1 = 1: 1:len

% feed back input genration

t = 1;

for i2 = 1:old_l

if gen_pol(i2)==1

stat_str(t) = old_stat(gen_l – i2);

i2 = i2+1;

t = t+1;

else

i2 = i2+1;

end

end

stat_l = length(stat_str);

feed_ip = stat_str(1);

for i3 = 1: stat_l-1

feed_ip = bitxor(feed_ip,stat_str(i3 + 1));

feed_ipmag(i1) = feed_ip;

i3 = i3+1;

end

% shifting elements

new_stat = feed_ip;

for i4 = 1:1:old_l

new_stat(i4+1) = old_stat(i4);

old_stat(i4)= new_stat(i4);

end

op_seq(i1) = new_stat(old_l +1);

end

%op_seq;

==============================

Author: Ashwini Patankar