Share on Facebook Share on Twitter Email
Answers.com

Shannon-Fano-Elias coding

 
Wikipedia: Shannon-Fano-Elias coding

This technique doesn't involve sorting of probabilities as in Shannon-Fano coding. The following formula is used to calculate F'(x) which in turn generates the code

F'(x) = F(x) + p(x) / 2,

where F(x) is cummulative sum of probabilities p(x).

It can be further understood with the following C code

#include <stdio.h>
#include <string.h>
 
#define max 10
#define maxLongCode 5
 
struct node
{
    char sym;
    float pro;
    float fx;
    float fx1;
    char code[20];
}s[max];
 
void bin(float,int);
 
int main(void)
{
    int n,i,j;
    float p,f=0,x;
    char ch;
    printf("\nEnter no. of symbols are needed: ");
    scanf("%d",&n);
    printf("\n");
 
    for(i=0;i<n;i++)
    {
        printf("Enter symbol %d: ",i+1);
        scanf(" %c",&ch);
        s[i].sym=ch;
        printf("Enter probability for symbol: ");
        scanf("%f",&p);
        s[i].pro=p;
        for(j=i;j<=i;j++)
        {
            f=f+p;
        }
        s[i].fx=f;
        if(i==0)
        {
            s[i].fx1=s[i].pro/2;
        }
        else
        {
            s[i].fx1=s[i-1].fx+(s[i].pro/2);
        }
        x=s[i].fx1;
        bin(x,i); //binary code generation function
    }
    //Table Generation
    printf("\nSymbol\tProbability\tF(x)\t\tF'(x)\t\tCode\n");
    for(i=0;i<n;i++)
    {
        printf("%c\t%f\t%f\t%f\t%s\n",s[i].sym,s[i].pro,s[i].fx,s[i].fx1,s[i].code);
    }
    return 0;
}
 
void bin(float x,int i)
{
    int j=0;
    while(j<maxLongCode)
    {
        x=x*2;
        if(x>=1)
        {
            strcat(s[i].code,"1");
            x=x-1;
        }
        else
            strcat(s[i].code,"0");
 
        if(x==0)
            break;
        j++;
    }
}

Output of above code:

Enter no. of symbols are needed: 4

Enter symbol 1: a
Enter probability for symbol: .25
Enter symbol 2: b
Enter probability for symbol: .5
Enter symbol 3: c
Enter probability for symbol: .125
Enter symbol 4: d
Enter probability for symbol: .125

Symbol	Probability	F(x)		F'(x)		Code
a	0.250000	0.250000	0.125000	001
b	0.500000	0.750000	0.500000	1
c	0.125000	0.875000	0.812500	1101
d	0.125000	1.000000	0.937500	1111

Search unanswered questions...
Enter a question here...
Search: All sources Community Q&A Reference topics
 
 

 

Copyrights:

Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Shannon-Fano-Elias coding" Read more