Information Theory and Coding

1.Lempel-Ziv Code
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) (a).begin(),(a).end()
int main()
{
   string text="AABABBBABAABABBBABBABB";
   vector<string>v;
   string s;
   for(int i=0;i<text.size();i++)
   {
       s+=text[i];
       if(!count(all(v),s))
       {
           v.pb(s);
           s.clear();
       }

   }
   v.pb("BB");

 int k=1;
unordered_map<string,int>mp;
   for(auto u:v)
   {
       mp[u]=k;
       cout<<k<<" "<<u<<endl;
       k++;
   }
   mp["BB"]=7;

   vector<pair<int,char>>vp;
   for(auto u:v)
   {
       string ss;
       if(u.size()==1)
       {
           char uv=u[0];
            vp.pb({100,uv});
       }
       else{

      for(int i=0;i<u.size()-1;i++)
      {
         ss+=u[i];
      }
      char ch=u[u.size()-1];
      if(mp[ss])
      {
        vp.pb({mp[ss],ch});
      }
      }
   }
   vector<string>vs;

   for(auto u:vp)
      {
          string x;
          cout<<u.first<<u.second<<endl;
          if(u.first==100){
          x+=bitset<3>(0).to_string();
          }
          else
          {
            x+=bitset<3>(u.first).to_string();
          }
          if(u.second=='A')
            x+='0';
          else
            x+='1';
          vs.pb(x);
      }
      for(auto u:vs)
        cout<<u<<endl;
    return 0;
}

2.Hamming Code
//1011011
//2
#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"Enter the 7 bit data sequence:";
    string str;
    cin>>str;
    reverse(str.begin(),str.end());
    cout<<"Enter parity state:";
    int state;
    cin>>state;
    vector<int>pos,newpos;
    for(int i=1;i<=7;i++)
    {
       if((i&(i-1))==0)
            pos.push_back(i-1);
    }
    reverse(pos.begin(),pos.end());
    newpos=pos;
    vector<int>pp={4,5,6,2,5,6,2,4,6};
    int sz=pp.size();
    string ss;
    int val=0;
    for(int i=0;i<3;i++)
    {
        int cnt=0;

        for(int j=0;j<3;j++)
        {
            if(str[pp[sz-1]]=='1')
            {
                cnt++;
            }
                pp.pop_back();
                sz=pp.size();

        }
        if((cnt+(str[newpos[val]]-'0'))%2!=0)
            {
                ss+='1';
            }
            else
            {
                ss+='0';
            }
        pos.pop_back();
        val++;

    }
    unsigned long long value =bitset<64>(ss).to_ullong();
    if(value>0)
    {
        cout<<"There is an error in this sequence and the position is:"<<value<<endl;
        if(str[value-1]=='1')
            str[value-1]='0';
        else
            str[value-1]='1';
        reverse(str.begin(),str.end());
        cout<<"And the correct sequence is:"<<str<<endl;
    }
    else
    {
        cout<<"There is no error in this code sequence"<<endl;
    }
    return 0;
}

3.Huffman Coding
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    struct Node* left;
    struct Node* right;

    Node(int val)
    {
        data=val;
        left=NULL;
        right=NULL;
    }

};
struct cmp{
bool operator()(Node* l,Node* r)
{
    return (l->data > r->data);
}

};
void preorder(Node *root,string s,vector<string>&ans)
{
    if(!root)
        return;
    if(!root->left && !root->right)
    {
        ans.push_back(s);
    }
    preorder(root->left,s+"0",ans);
    preorder(root->right,s+"1",ans);
}
vector<string>huffman(string s,vector<int>f,int n)
{
    priority_queue<Node*,vector<Node*>,cmp>mh;
    for(int i=0;i<n;i++)
    {
        Node *temp=new Node(f[i]);
        mh.push(temp);
    }
    while(mh.size()!=1)
    {
        Node *left=mh.top();
        mh.pop();
        Node *right=mh.top();
        mh.pop();
        Node *parent=new Node(left->data+right->data);
        parent->left=left;
        parent->right=right;
        mh.push(parent);
    }
    Node *root=mh.top();
    mh.pop();
    vector<string>ans;
    preorder(root,"",ans);
    return ans;
}
int main()
{
    ///abcde
    ///7 9 2 15 3
    string s;
    cout<<"Enter the string:";
    cin>>s;
    int n=s.size();
    vector<int>f(n);
    cout<<"Enter the corresponding frequency:";
    for(int i=0;i<n;i++)
    {
        cin>>f[i];
    }
    vector<string>ans=huffman(s,f,n);
    vector<char>vc={'d','b','c','d','a'};
    int k=0;
    for(auto u:ans)
    {
        cout<<vc[k]<<" = "<<u<<endl;
        k++;
    }
    return 0;
}

4.Optimality
//abcde
7 9 2 15 3
#include<bits/stdc++.h>
using namespace std;
struct Node{

    int data;
    struct Node* left;
    struct Node* right;

    Node(int val)
    {
        data=val;
        left=NULL;
        right=NULL;
    }

};

struct cmp{

    bool operator()(Node* l,Node* r)
    {
        return (l->data > r->data);
    }
};
void preorder(Node *root,string s,vector<string>&ans)
{
    if(!root)
        return;
    if(!root->left && !root->right)
    {
        ans.push_back(s);
    }
    preorder(root->left,s+"0",ans);
    preorder(root->right,s+"1",ans);
}
vector<string>huffman(string s,vector<int>f,int n)
{
    priority_queue<Node*, vector<Node*>,cmp>mh;
    for(int i=0;i<n;i++)
    {
        Node *temp=new Node(f[i]);
        mh.push(temp);
    }
    while(mh.size()!=1)
    {
        Node *left=mh.top();
        mh.pop();
        Node *right=mh.top();
        mh.pop();
        Node *parent=new Node(left->data+right->data);
        parent->left=left;
        parent->right=right;
        mh.push(parent);
    }
    Node *root=mh.top();
    mh.pop();
    vector<string>ans;
    preorder(root,"",ans);
    return ans;
}
int main()
{
    cout<<"Enter a string:";
    string s;
    cin>>s;
    int n=s.size();
    vector<int>f(n);
    for(int i=0;i<n;i++)
    {
        cin>>f[i];
    }
    vector<string>ans=huffman(s,f,n);
  double arr[n];
  int k=0;
  double cnt=0;
    for(auto u:ans)
    {
        arr[k]=u.size();
        cnt+=arr[k];
    }
    double sum=0;
    for(int i=0;i<n;i++)
    {
       sum+=1/pow(2,arr[k]);
    }
    if(sum<=1){
        cout<<"optimal"<<endl;
        for(auto u:ans)
            cout<<u<<endl;
    }
    else
        cout<<"Not Optimal"<<endl;

    cout<<endl;
    return 0;
}


5.Channel Capacity
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int row,col;
    cout<<"Enter the number of rows and columns:";
    cin>>row>>col;
    double arr[row][col];
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            cin>>arr[i][j];
        }
    }
    double H_of_Y_given_X;
    H_of_Y_given_X=arr[0][0]*log2(1/arr[0][0])+arr[0][1]*log2(1/arr[0][1]);
    cout<<"Conditional Probability:"<<H_of_Y_given_X<<" bits/message symbol"<<endl;
    double capacity=1-H_of_Y_given_X;
    cout<<"Capacity = "<<capacity<<" bits/message symbol"<<endl;

    return 0;
}

6.Joint Distribution
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int row,col;
    cout<<"Enter rows and columns:";
    cin>>row>>col;

    ///Take the values of matrix
    cout<<"Enter the values of joint distribution:"<<endl;
    double arr[row][col];

    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            cin>>arr[i][j];
        }
    }
    double x[row],y[col];
    cout<<"Enter the marginal distribution of X:";
    for(int i=0;i<row;i++)
        cin>>x[i];

    cout<<"Enter the marginal distribution of Y:";
    for(int i=0;i<col;i++)
        cin>>y[i];

        ///Calculation H(X)
    double H_of_X=0;
    for(int i=0;i<row;i++)
    {
        H_of_X+=(-x[i]*log2(x[i]));
    }
    cout<<"H(X) = "<<H_of_X<<" bits"<<endl;
        ///Calculation H(Y)
    double H_of_Y=0;
    for(int i=0;i<col;i++)
    {
        H_of_Y+=(-y[i]*log2(y[i]));
    }
    cout<<"H(Y) = "<<H_of_Y<<" bits"<<endl;

    ///Calculation of H(X|Y)

    double H_of_X_given_Y=0,H_of_Y_given_X=0;
    double Hx[row];
    for(int i=0;i<row;i++){
            double val2=0;
    for(int j=0;j<col;j++)
    {
        double val1=(arr[i][j]*(1/y[i]));
    if(val1==0)
        val2+=0;
    else
        val2+=(-val1*log2(val1));
    }
    Hx[i]=val2;
    }
    for(int i=0;i<row;i++)
    {
        H_of_X_given_Y+=(y[i]*(Hx[i]));
    }
    cout<<"H(X|Y) = "<<H_of_X_given_Y<<" bits"<<endl;

     ///Calculation of H(Y|X)

    double Hy[row];
    for(int i=0;i<row;i++){
            double val2=0;
    for(int j=0;j<col;j++)
    {
        double val1=(arr[j][i]*(1/x[i]));
    if(val1==0)
        val2+=0;
    else
        val2+=(-val1*log2(val1));
    }
    Hy[i]=val2;
    }
    for(int i=0;i<row;i++)
    {
        H_of_Y_given_X+=(x[i]*(Hy[i]));
    }
    cout<<"H(Y|X) = "<<H_of_Y_given_X<<" bits"<<endl;
    return 0;
}

7.Entropy

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<double>v[4];
    v[0]={1,2,1};
    v[1]={1,1};
    v[2]={2,1,1};
    v[3]={1,1};
    double cnt=0;
    vector<double>vv;
    for(int i=0;i<4;i++)
    {
        int tmp=0;
        for(auto u:v[i])
        {
           tmp+=u;
        }
        vv.push_back(tmp);
        cout<<tmp<<" ";
        cnt+=tmp;
    }
    cout<<endl;
    double mu=0;
    double h_mu=0;
    for(int i=0;i<4;i++)
    {
        for(auto u:v[i])
        {
            h_mu+=-((u/cnt)*log2(u/cnt));
        }
    }
    cout<<h_mu<<endl;
    for(auto u:vv)
    {
        mu+=-((u/cnt)*log2(u/cnt));
    }
    cout<<mu<<endl;

    cout<<h_mu-mu<<endl;



    return 0;
}


8.Convolutional Code
//1011
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

#define rapid_io() ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

int main()
{
    //rapid_io();
    string str;
    cout<<"Enter the code sequence:";
    cin>>str;
    str+="000";
    str="00"+str;
    vector<int>res;
    int v1,v2;
    for(int i=str.size()-1;i>=2;i--)
    {
        v1=(str[i]-'0')^(str[i-1]-'0')^(str[i-2]-'0');
        res.pb(v1);
        v2=(str[i]-'0')^(str[i-2]-'0');
        res.pb(v2);
    }

    for(auto u:res)
        cout<<u;
    cout<<endl;



    return 0;
}

lempel-ziv

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) (a).begin(),(a).end()
int main()
{
   string text="000101110010100101";
   vector<string>v;
   v.pb("0");
   v.pb("1");
   string s;
   for(int i=0;i<text.size();i++)
   {
       s+=text[i];
       if(!count(all(v),s))
       {
           v.pb(s);
           s.clear();
       }

   }
   for(auto u:v)
   {
       cout<<u<<endl;
   }
   //v.pb("BB");



 int k=1;
unordered_map<string,int>mp;
   for(auto u:v)
   {
       mp[u]=k;
       cout<<k<<" "<<u<<endl;
       k++;
   }

   //mp["BB"]=7;

   vector<pair<int,int>>vp;
   for(auto u:v)
   {
       string ss;
       if(u.size()==1)
       {
           if(u=="0")
           vp.pb({0,1});
           else
            vp.pb({1,2});

       }
       else{

      for(int i=0;i<u.size()-1;i++)
      {
         ss+=u[i];
      }
      int ch=(u[u.size()-1])-'0';
      if(ch==1)
      {
        vp.pb({mp[ss],2});
      }
      else{
        vp.pb({mp[ss],1});
      }
      }
   }
   vector<string>vs;
    int flag=1;
   for(auto u:vp)
      {
          string x;
          cout<<u.first<<" "<<u.second<<endl;
          if(u.first==0){
          x+=bitset<3>(0).to_string();
          }
          else if(u.first==1 && flag==2)
          {
              x+=bitset<3>(0).to_string();
          }
          else if(u.first==1)
          {
              x+=bitset<3>(1).to_string();
          }
          else
          {
            x+=bitset<3>(u.first).to_string();
          }
          if(u.second==1)
            x+='0';
          else
            x+='1';
          vs.pb(x);
          flag++;
      }
      for(auto u:vs)
        cout<<u<<endl;
    return 0;
}