|
|
This article is incomplete and may require expansion or cleanup. Please help to improve the article, or discuss the issue on the talk page. |
|
|
This article has no lead section, so one should be written. See the lead section guide for more information on writing leads. (September 2009) |
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
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)




