## Matlab Huffman code

This Matlab code generates a Huffman codebook for a specified set of symbol probabilities.

Copyright © 2010 Robert G. Maunder. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

April 27th, 2011 at 4:13 am

thank you very much

June 9th, 2011 at 11:11 pm

i need this realy.

thx for help

September 16th, 2011 at 9:21 pm

thank you very much.real i want this code.

October 13th, 2011 at 8:19 am

thank you very much sir

March 2nd, 2012 at 7:34 am

thnk you

May 11th, 2012 at 5:48 pm

Thank you

November 29th, 2012 at 2:49 am

Thanks for your help

March 4th, 2013 at 5:31 pm

Thank you for the code. It’s awesome!

May 10th, 2013 at 11:51 am

Can you plz tell me how to write Huffman code in matlab with user entering the probabilities and asking the user to enter the base for getting the huffman code.

May 10th, 2013 at 5:31 pm

Hi Pooja Shah,

The Matlab code that you can download from this page will generate a Huffman codebook for you, when you provide it with the symbol probabilities. Here is some code a Huffman encoder and decoder…

http://users.ecs.soton.ac.uk/rm/wp-content/HuffmanEncoder.m

http://users.ecs.soton.ac.uk/rm/wp-content/HuffmanDecoder.m

Take care, Rob.

August 13th, 2013 at 4:51 pm

repeat accumulate code i need

November 27th, 2013 at 2:05 am

Easy to understand. Very useful. Optimum coding

November 27th, 2013 at 2:26 am

Hi Rob,

Your program gives out Huffman Codes which are of a minimum length 2 bits for the highest probability. But the highest probability symbol should have a binary Huffman Code of only 1 bit. Could you please verify this?

November 27th, 2013 at 3:07 am

Please ignore my previous question. I did not know the Huffman Code\’s algorithm properly. The code is perfect.

March 9th, 2014 at 9:31 pm

I used this to make an dictionary but it failed the prefix free condition for long text files though it works for short text file.

March 9th, 2014 at 9:45 pm

Actually I found it is not…I draw a tree from the codewords and found it is prefix-free code but somehow matlab recognizes this as prefix code…

Thanks,

March 10th, 2014 at 6:07 pm

Hi Kiyeob,

I hope you got this working - I can’t tell from your messages if you solved the problem or not…

Take care, Rob.

April 19th, 2014 at 5:01 pm

please i need a huffman code ^^

April 20th, 2014 at 8:24 am

Hello Tiha,

You can download the code from…

http://users.ecs.soton.ac.uk/rm/wp-content/huffman.m

Take care, Rob.

February 3rd, 2015 at 6:47 am

i was no to use matlab very well and traduces all the code in telecommunication. thank you for all you are doing to make the technologies growing

February 3rd, 2015 at 6:53 am

please can i have huffman code that return (valeur moyenne, entrepie et l\’efficacité ) and binary code, and the user will enter any probability that he need , the probability can be above one . thank you

February 3rd, 2015 at 7:04 am

thank you rob for all you are doing for us

February 4th, 2015 at 7:30 pm

Hello Liberte,

You can download my Matlab tools for Huffman codes from…

http://www.edshare.soton.ac.uk/5293/

Take care, Rob.

February 16th, 2015 at 9:15 pm

sir plz give me idea of how to store Huffman encoded bits for image in matlab

February 17th, 2015 at 7:47 pm

Hi Manju,

It is easy to store these bits in Matlab by using the ’save’ command.

Take care, Rob.

February 18th, 2015 at 6:12 pm

Hello Sir,

sir please provide me matlab code for huffman image compression with single bit error.

February 19th, 2015 at 7:10 pm

Hello Abhikalp,

I’m afraid that I don’t have any Matlab code for image compression, but it should be possible to apply my Huffman code to this application.

Take care, Rob.

February 20th, 2015 at 10:34 am

Thankyou sir,

Sir I used the command huff_code= huffmanenco(sig,dict) to encode the signal in Huffman jpeg image compression. Sir now I want to calculate Huffman binary file what will be the procedure for this. And one more thing sir will reconstructed image size be the same as compressed image size or it will be different?

February 20th, 2015 at 10:34 am

Thankyou sir,

Sir I used the command huff_code= huffmanenco(sig,dict) to encode the signal in Huffman jpeg image compression. Sir now I want to calculate Huffman binary file what will be the procedure for this. And one more thing sir will reconstructed image size be the same as compressed image size or it will be different?

February 21st, 2015 at 3:00 pm

Hello Manju,

I suspect that you can do this by taking eight bits at a time and converting to a decimal number in the range 0 to 255, then using fwrite to write this into a binary file. If you are applying Huffman coding to a file that has already been jpeg encoded, then I would not expect you to achieve any compression. However, I suspect that the resultant binary file would have a different file size to the original jpeg file, albeit only slightly.

Take care, Rob.

February 21st, 2015 at 4:09 pm

Thankyou sir,

Sir I applied jpeg compression using Huffman on a image that is in bmp format not in jpeg. Sir I want to know that compressed image or reconstructed image will be same or different.

February 23rd, 2015 at 7:53 pm

Hi Manju,

JPEG compression is lossy, so the reconstructed image will be different to the original image.

Take care, Rob.

February 26th, 2015 at 7:30 pm

hello sir,

Sir I want to introduce error in huffman binary file and then decoded this binary file.what will be the procedure for this?Is differnt decoding technique used for this error phenomena or same as we use for huffman without error..

February 28th, 2015 at 11:39 am

Hi Abhikalp,

If errors are introduced into the Huffman-encoded bit sequence, the decoding procedure is the same, although there is one thing that you need to think about.

Suppose that we have the codebook 1, 00, 010, 011 and we have the transmitted bit sequence 0001110101001010. If the tenth bit has a transmission error then the received bit sequence will be 0001110100001010. This decodes to the following sequence of codewords, 00, 011, 1, 010, 00, 010, 1, 0. However, that final 0 does not give a complete codeword - you need to write your Huffman decoder so that it doesn’t crash when it encounters this problem. The simple thing you can do is just have the Huffman decoder ignore that final 0 and output only the 7 complete codewords that precede it.

Take care, Rob.

March 24th, 2015 at 11:17 am

hello sir,

sir plz tell me in JPEG image compression there is a command i.e. y = blkproc(x, [8 8], ‘P1 * x * P2′, t, t’); here what is the P1 * x * P2′..

March 24th, 2015 at 4:55 pm

Hello Abhikalp,

It seems to me that you are using the following version of the blkproc command…

B = blkproc(A,[m n],fun,P1,P2)

You can read more about this command at…

https://nf.nci.org.au/facilities/software/Matlab/toolbox/images/blkproc.html

I suspect that ‘P1 * x * P2′ will return the value of t*x*t’, where x is each 8×8 sub-block of A and t’ is the transpose of whatever t is.

Take care, Rob.

March 25th, 2015 at 12:20 pm

thank you sir,

sir i am doing jpeg image compression using huffman coding here is my code

clc

clear all

I=imread(\’C:\\Users\\my-computer\\Pictures\\newlena.bmp\’)

[row col]=size(I)

%Quantization matrix for quality factor Q=10

Q= [80 60 50 80 120 200 255 255;

55 60 70 95 130 255 255 255 ;

70 65 80 120 200 255 255 255 ;

70 85 110 145 255 255 255 255 ;

90 110 185 255 255 255 255 255 ;

120 175 255 255 255 255 255 255 ;

245 255 255 255 255 255 255 255 ;

255 255 255 255 255 255 255 255 ];

% dct transform

dct=dctmtx(8)

idct=(dct\’);

Im=double(I);

for i=1:8:row

for j=1:8:col

b=Im(i:i+7,j:j+7);

temp_b1=dct*b*idct;

Im_dctq(i:i+7,j:j+7)=round(temp_b1./Q);

end

end

% Huffman coding

temp=1

temp2=0

pixel_count = row*col;

symbol = reshape(Im_dctq,[1,row*col]);

symbol1 = unique(symbol)

len = length(symbol1)

for i = 1:len

k = Im_dctq==symbol1(i);

count(temp) = sum(k(:));

prob_pix(temp) = double(count(temp)/pixel_count)

temp2 = temp2 + prob_pix(temp);

prob_cum(temp) = temp2;

temp = temp+1

end

[dict,avg_len] = huffmandict(symbol1,prob_pix).

sir is this procedure right??I m getting average length of the huffmancode less than 2.I think which is not correct it can\’t be so much less.Sir plz guide me

March 25th, 2015 at 5:36 pm

Hi Abhikalp,

Your code seems reasonable to me. I suspect that the vast majority of your symbols have a value of 0, which is why your average codeword length is so short. If your source image has 8 bits per pixel and your compression is reducing this to less than 2 bits per pixel, then your compression ratio is around 4, which seems reasonable to me.

Take care, Rob.

March 26th, 2015 at 4:06 am

Very good stuff, Keep up the good job please.

March 26th, 2015 at 6:52 am

hello sir….. m doing image compression using huffman coding sir plz tell me how to calculate probablility of each pixel..

%clearing all variableas and screen

clear all;

close all;

clc;

%Reading image

a=imread(’ab.jpg’);

figure,imshow(a)

%converting an image to grayscale

I=rgb2gray(a);

imshow(I);

%size of the image

[m,n]=size(I);

Totalcount=m*n;

%variables using to find the probability

cnt=1;

sigma=0;

%computing the cumulative probability.

for i=0:255

k=I==i;

count(cnt)=sum(k(:))

%pro array is having the probabilities

pro(cnt)=count(cnt)/Totalcount;

sigma=sigma+pro(cnt);

cumpro(cnt)=sigma;

cnt=cnt+1;

end;

%Symbols for an image

symbols = [0:255];

%Huffman code Dictionary

dict = huffmandict(symbols,pro);

%function which converts array to vector

vec_size = 1;

for p = 1:m

for q = 1:n

newvec(vec_size) = I(p,q);

vec_size = vec_size+1;

end

end

%Huffman Encodig

hcode = huffmanenco(newvec,dict);

%Huffman Decoding

dhsig1 = huffmandeco(hcode,dict);

%convertign dhsig1 double to dhsig uint8

dhsig = uint8(dhsig1);

%vector to array conversion

dec_row=sqrt(length(dhsig));

dec_col=dec_row;

%variables using to convert vector 2 array

arr_row = 1;

arr_col = 1;

vec_si = 1;

for x = 1:m

for y = 1:n

back(x,y)=dhsig(vec_si);

arr_col = arr_col+1;

vec_si = vec_si + 1;

end

arr_row = arr_row+1;

end

%converting image from grayscale to rgb

[deco, map] = gray2ind(back,256);

RGB = ind2rgb(deco,map);

imwrite(RGB,’pa.JPG’);

this is a code for image compression bt it is not working properly…this code provide output a gray image instead of color…sir plzzz check it…

March 26th, 2015 at 9:04 am

hello sir,

thanks for previous help..

sir now i m doing jpeg image compression using huffman coding with single bit error.But sir from this code i m note getting correct picture.Final picture should be half part or less part decoded n rest should be the gray or black.Sir in my code with single bit error ,another problem is the size of input signal and huffman decoded signal is not same.here is my code please check this and provide me suitable correction…

clc

clear all

I=imread(’C:\Users\Manju-Sharma\Pictures\aerial.tiff’)

[row col]=size(I)

%[row col]=size(Im1)

%Qunatization matrix for chrominance

%Q =[ 17 18 24 47 99 99 99 99;

%18 21 26 66 99 99 99 99;

%24 26 56 99 99 99 99 99;

%47 66 99 99 99 99 99 99;

%99 99 99 99 99 99 99 99;

%99 99 99 99 99 99 99 99;

%99 99 99 99 99 99 99 99;

%99 99 99 99 99 99 99 99];

%quantization matrix for quality factor Q=50

Q= [ 16 11 10 16 24 40 51 61;

12 12 14 19 26 58 60 55;

14 13 16 24 40 57 69 56;

14 17 22 29 51 87 80 62;

18 22 37 56 68 109 103 77;

24 35 55 64 81 104 113 92;

49 64 78 87 103 121 120 101;

72 92 95 98 112 100 103 99];

%Quantization matrix for quality factor Q=10

%Q= [80 60 50 80 120 200 255 255;

% 55 60 70 95 130 255 255 255 ;

% 70 65 80 120 200 255 255 255 ;

% 70 85 110 145 255 255 255 255 ;

%90 110 185 255 255 255 255 255 ;

%120 175 255 255 255 255 255 255 ;

%245 255 255 255 255 255 255 255 ;

%255 255 255 255 255 255 255 255 ];

% dct transform

dct=dctmtx(8)

idct=(dct’);

Im=(double(I))-128;

for i=1:8:row

for j=1:8:col

b=Im(i:i+7,j:j+7);

temp_b1=dct*b*idct;

Im_dctq(i:i+7,j:j+7)=temp_b1./Q;

end

end

% Huffman

% coding—————————————————————-

Im_dctq=round(Im_dctq)

temp=1

temp2=0

pixel_count = row*col;

symbol = reshape(Im_dctq,[1,row*col]);

symbol1 = unique(symbol)

len = length(symbol1)

for i = 1:len

k = Im_dctq==symbol1(i)

count(temp) = sum(k(:));

prob_pix(temp) = count(temp)/pixel_count

temp2 = temp2 + prob_pix(temp);

prob_cum(temp) = temp2;

temp = temp+1

end

[dict,huff_len] = huffmandict(symbol1,prob_pix);

temp = 1;

for i= 1:row

for j = 1:col

Im_huff(temp) = Im_dctq(i,j);

temp = temp+1;

end

end

huff_code = huffmanenco(Im_huff,dict);

s=[huff_code(6181)]

s=[huff_code(6181)]

s=xor(1,s)

huff_code(6181) = s;

huff_decode=huffmandeco(huff_code,dict);

Means the size of Im_huff and size of huffmandeco is not same…

sir plzzzzzzzzz provide be correct way…

March 26th, 2015 at 9:07 am

I insert error in the 6181 position or it can be another.Sir for inserting random error what should I do???

March 26th, 2015 at 4:35 pm

hello sir,

sir after introducing single bit in the encoded bit stream as discussed above what changes should I do in huffman decoder so that i can get correct result.here is the code for huffman decoding

function deco = huffmandeco(comp, dict)

% Error checking ——————

msg=nargchk(2,2, nargin);

if ( msg )

error(\’comm:huffmandeco:InputArgumentCount\’, msg)

end

[m,n] = size(comp);

if ( m ~= 1 && n ~= 1)

error(\’comm:huffmandeco:VectorInputSignal\’, \’The input signal must be a vector.\’);

end

checkDictValidity(dict);

if ( strcmp(class(comp), \’double\’) == 0 )

error(\’comm:huffmandeco:InvalidCodeType\’, …

\’The encoded signal has to be a vector of type double.\’)

end

% End of error checking ———————-

% isSigNon Numeric is used to later convert the decoded signal from cell

% array format to a double vector.

isSigNonNumeric = max(cellfun(\’isclass\’, {dict{:,1}}, \’char\’) );

deco = {};

i = 1;

while(i <= length(comp))

tempcode = comp(i);

found_code = is_a_valid_code(tempcode, dict);

while(isempty(found_code) && i < length(comp))

i = i+1;

tempcode = [tempcode, comp(i)];

found_code = is_a_valid_code(tempcode, dict);

end

if( i == length(comp) && isempty(found_code) )

error(\’comm:huffmanenco:CodeNotFound\’, …

\’The encoded signal contains a code which is not present in the dictionary.\’);

end

deco{end+1} = found_code;

i=i+1;

end

if( n == 1 ) % if input was a column vector

deco = deco\’; % the decoded output should also be a column vector

end

if ( ~isSigNonNumeric )

decoMat = zeros(size(deco));

decoMat = feval(class(dict{1,1}), decoMat); % to support single precision

for i = 1 : length(decoMat)

decoMat(i) = deco{i};

end

deco = decoMat;

end

%————————————————————————–

% This functions does a reverse lookup for a signal. This function will

% compare the code with the entries in the codebook and return the signal

% if there is a match

function found_code = is_a_valid_code(code, dict)

found_code = [];

m = size(dict);

for i=1:m(1)

if ( isequal(code, dict{i,2}) )

found_code = dict{i,1};

return;

end

end

March 27th, 2015 at 3:28 am

Hi sir, I wanted to do a Project on Huffman Coding in Image Processing where in I need to compress the original .tiff or .jpg image file. What do you suggest in order to start it.?

March 30th, 2015 at 3:50 pm

Hi Parul,

It seems to me that your ‘pro’ variable is giving you the probabilities that you need to design your Huffman code.

Take care, Rob.

March 30th, 2015 at 3:55 pm

Hi abhikalp,

As you have found, a single bit error can cause the number of received symbols to become different to the number of transmitted symbols. This is a problem that you should expect and that you should design a solution for. It is not indicative of a bug in your code.

To insert the error in a random position, you can use something like

random_number = randi(length(bit_vector);

bit_vector(random_number) = ~bit_vector(random_number);

You can’t expect to get the correct decoding result when there are bit errors in your Huffman-encoded bit vector. The Huffman code is unable to detect and correct these errors.

Take care, Rob.

March 30th, 2015 at 3:56 pm

Hi Shashi,

I would advise you to look at what Abhikalp and Parul are doing here.

Take care, Rob.

March 31st, 2015 at 5:17 am

Thanku sir…..but this code outputs the compressed gray image….i want RGB image….sir plz tell wht is the error…???

March 31st, 2015 at 4:43 pm

Hi Parul,

This is because you are using the rgb2gray function to throw away the colour information. Normally, colour image compression is achieved by converting to the YUV format and then encoding each of the Y, U and V channels separately. Often, more compression is applied to the U and V channels because the human eye is less sensitive to these.

Take care, Rob.

April 1st, 2015 at 6:18 am

thanku sir…..

i found a code for rgb to YUV image conversion..is this code is useful for my problem???….sir plzz suggest me….

RGB = imread(\’life.jpg\’);

R = RGB(:,:,1);

G = RGB(:,:,2);

B = RGB(:,:,3);

Y = 0.299 * R + 0.587 * G + 0.114 * B;

U = -0.14713 * R - 0.28886 * G + 0.436 * B;

V = 0.615 * R - 0.51499 * G - 0.10001 * B;

YUV = cat(3,Y,U,V);

imshow(YUV);

April 1st, 2015 at 2:07 pm

Hello Sir, do you have a code for huffman decoder without using the built in function in matlab? thank you

April 1st, 2015 at 3:50 pm

Hi Parul,

That looks right to me.

Take care, Rob.

April 1st, 2015 at 3:52 pm

Hi Blaze,

You can download my Huffman decoder from…

http://www.edshare.soton.ac.uk/5293/

Take care, Rob.

April 3rd, 2015 at 6:10 am

thanku sir….bt sir i hv used imwrite funcn bt still my compressed image is not saved.?????plz help me…my code is not working

April 9th, 2015 at 3:27 pm

Hello Parul,

I’m afraid that I haven’t used imwrite before, so I can’t think what might be wrong with your code.

Take care, Rob.

April 16th, 2015 at 7:32 am

thanku sir….Now m done with imwrite funcn and i hv save my compressed image…bt sitll there is a problm with dis code again give gray compressed image…plz help me

April 21st, 2015 at 7:25 pm

Hi Parul,

I’m very sorry but I don’t have enough experience with image compression in Matlab to be able to suggest where you might be going wrong.

Take care, Rob.

April 22nd, 2015 at 9:06 am

Hello sir,

Sir can u tell me what will be generator matrix for (13,5,3) fixed length code

April 23rd, 2015 at 2:31 pm

hello sir,iam doing my project in video processing i want code how to generate codebook using kmeans

April 23rd, 2015 at 4:59 pm

Hi Abhikalp,

I’m afraid that I don’t have any generator matrices for block codes, so I can’t help you with this.

Take care, Rob.

April 23rd, 2015 at 5:01 pm

Hello Anusha,

I assume that you want to design a Max-Lloyd quantiser using the kmeans algorithm. You can do this using

[~, quantisation_levels] = kmeans(samples_from_the_source, number_of_quantisation_levels);

Take care, Rob.

April 24th, 2015 at 2:40 pm

hi sir thaq fr ur ans….sir how to get training frames from a video

April 24th, 2015 at 2:48 pm

or a block

April 27th, 2015 at 4:56 pm

Hi Anusha,

I would suggest finding a selection of standard video sequences (such as those used by the Video Quality Expert Group) and using them for training.

Take care, Rob.

April 30th, 2015 at 6:12 am

Hello Sir,

I’m bit confused about huffman tree which has generated. How do I store the huffman tree for decompresn another time ?

May 3rd, 2015 at 8:32 pm

I=imread(\’C:\\Users\\my-computer\\Pictures\\newlena.bmp\’)

[row col]=size(I)

%Quantization matrix for quality factor Q=10

Q= [80 60 50 80 120 200 255 255;

55 60 70 95 130 255 255 255 ;

70 65 80 120 200 255 255 255 ;

70 85 110 145 255 255 255 255 ;

90 110 185 255 255 255 255 255 ;

120 175 255 255 255 255 255 255 ;

245 255 255 255 255 255 255 255 ;

255 255 255 255 255 255 255 255 ];

% dct transform

dct=dctmtx(8)

idct=(dct\’);

Im=double(I);

for i=1:8:row

for j=1:8:col

b=Im(i:i+7,j:j+7);

temp_b1=dct*b*idct;

Im_dctq(i:i+7,j:j+7)=round(temp_b1./Q);

end

end

% Huffman coding

temp=1

temp2=0

pixel_count = row*col;

symbol = reshape(Im_dctq,[1,row*col]);

symbol1 = unique(symbol)

len = length(symbol1)

for i = 1:len

k = Im_dctq==symbol1(i);

count(temp) = sum(k(:));

prob_pix(temp) = double(count(temp)/pixel_count)

temp2 = temp2 + prob_pix(temp);

prob_cum(temp) = temp2;

temp = temp+1

end

[dict,avg_len] = huffmandict(symbol1,prob_pix).

temp = 1;

for i= 1:row

for j = 1:col

Im_huff(temp) = Im_dctq(i,j);

temp = temp+1;

end

end

huff_code = huffmanenco(Im_huff,dict)

Hello sir,

Sir in JPEG image compression is compressed size of image is size of binary file after huffmanenco??and sir in this code please tell me the size format of binary file(output of huffmanenco) is this in bit form or in byte form??

May 4th, 2015 at 7:12 pm

Hi Lukman,

The transmitter and receiver will both need to have knowledge of the Huffman codebook (or equivalently, the Huffman tree) so that they can work together. In practice, this knowledge could be hard-coded into the transmitter and receiver, preventing it from ever changing. Alternatively, the transmitter could somehow transmit the codebook to the receiver, before using it.

Take care, Rob.

May 4th, 2015 at 7:14 pm

Hello Manju,

If the encoder is creating a binary file, then yes - the compressed image size will be equal to the file size. I’m not sure what you mean by bit form or byte form - any binary file can be written or read one bit at a time or one byte at a time - binary files are not bit or byte, they are both.

Take care, Rob.

June 24th, 2015 at 3:38 pm

Let assume you have a channel with capacity: “c” bits/channel-use at 10 dB SNR, and you have an uncoded BER of 0.1 at 15 dB SNR with “n” bits are transmitted in a single channel use. Here “n > c”. Here SNR is not the SNR per bit, but the SNR per symbol. One symbol carries “n” bits. For instance assume n=15 and c=10. What can you make of this channel? Can this channel achieve the capacity of 10 bits/channel-use at 10dB. The Shannon limit in terms of SNR is 10 dB.

June 29th, 2015 at 12:51 pm

Hi Dush,

Without coding, you will not able able to achieve a low BER at an effective throughput n that is close to the capacity c. If you use a well designed long turbo or LDPC code, then you should be able to achieve a low BER when n is close to (but no higher than) c.

However, you are talking about using an effective throughput of n=15 in a channel having a capacity of c=10. Since n>c, it will be impossible for you to achieve a low BER.

Take care, Rob.

June 29th, 2015 at 1:02 pm

Thank Rob,

Let me kindly clarify my problem further. In my example “n” is the number of bits transmitted in a single channel use which includes both information and redundant bits. If n=15, and c=10, we have 5 parity bits to reduce the BER.

Here we are definitely not transmitting above the channel capacity.

Does my clarification make sense? Looking forward to your response.

June 29th, 2015 at 1:28 pm

Dear Rob,

Do you have any use of uncoded BER of a communication channel when designing codes?

Could you please provide some references also please?

June 30th, 2015 at 1:00 pm

Hi Dush,

That makes more sense. Note that parity bits do not usually count towards the number of bits per channel use - I always think of it as being bits of information per channel use. So, you are describing an effective throughput of 10 bits per channel use, not 15. In which case, it is possible to achieve a low BER, provided that you have a good code and provided that the channel capacity is at least 10 bits per channel use.

You can compare the BER of your code with the uncoded BER if you use Eb/N0 for your x axis, rather than SNR. This makes the comparison fair in terms of energy, although it is still unfair in terms of transmission duration or bandwidth - since your coded scheme employs parity bits, it will need a higher transmission duration or bandwidth than the uncoded scheme. For this reason, I always prefer to compare my coded schemes with another (older) coded scheme having the same coding rate.

Take care, Rob.

July 28th, 2015 at 6:00 am

Hi sir, i\’m working on huffman coding i want a matlab code to compress the color image usig huffman coding can you please provide me the code..,

July 28th, 2015 at 6:02 am

Hi sir, i’m working on huffman coding i want a matlab code to compress the color image usig huffman coding can you please provide me the code..,

July 28th, 2015 at 6:10 am

Hi sir,

how to compress the huffman coding using matlab.

July 28th, 2015 at 8:22 am

Hello Pavithra,

I’m afraid that I don’t have any Matlab code for compressing images using Huffman codes. But you can download my Matlab code for Huffman codes above.

Take care, Rob.

October 20th, 2015 at 4:47 pm

Hello Sir,

I want after compression “Shannon Fano” scheme Code on matlab , can you provide me sir.

October 21st, 2015 at 11:58 am

Hi Fazalullah,

I’m afraid that I don’t have any Matlab code for Shannon-Fano coding. However, you should be able to modify my Matlab code for Huffman coding to do this.

Take care, Rob.

November 3rd, 2015 at 11:59 pm

Hi Rob,

It may be just a tiny effect of roundoff errors, but let me describe what happened, in case the explanation is more interesting than that and/or useful in teaching students.

1. I generated 256 probabilities for Bernoulli(0.9) blocks of length 8 as follows:

p=0.9; q=1-p;

N=8;

probabilities = [];

pN0=q^N;

BinomN0=1;

for N0=0:N

probabilities = [probabilities, pN0*ones(1, BinomN0)];

pN0=pN0*p/q;

BinomN0=BinomN0*(N-N0)/(N0+1);

end

2…and ran your code with these probabilities, which gave me

The Huffman coding rate is: 0.9857

3. I calculated the coding rate of the following version of run length encoding:

an 8-zero input run is coded as \"0\".

a less-than-8-zero input run is coded as \"1\" followed by 3-bit number for the number of zeroes in the run.

For example, \"00000000,1,1,01\" would be coded as \"0,1000,1000,1001\"; where commas are used only to facilitate human reading.

4. The coding rate of such run length encoding was slightly (0.04%) higher than that of Huffman.

Since the input \"chunks\" for this run length encoder are at most 8-bit long, I would expect that Huffman encoder should do at least as well on 8-bit blocks.

This expectation could be wrong, since it may be like comparing \"apples to pine-apples\": after all, Huffman encoder is optimal on fixed-length input blocks.

What do you think?

Thank you very much,

Glen

P.S. I could add the details of calculating the run-length coding rate, e.g. in case I made a mistake there.

P.P.S. Another observation, which is not mysterious:

The Huffman coding rate does not have to monotonically increase with the block size.

For example, Bernoulli(0.9) blocks of length 6 have coding rate 0.99753, while Bernoulli(0.9) blocks of length 7 have coding rate of \"only\"

0.98873.

Sanity check: blocks of length 12,18 etc should have coding rate >= that of 6-blocks, and this is indeed the case for Bernoulli(0.9) blocks of length 12 (coding rate is 0.99791).

November 5th, 2015 at 8:58 pm

Hi Glen,

This is very interesting. In the Huffman code, you take 8 bits from the source at a time and map them to one of 256 codewords of various lengths - I guess that the shortest codeword comprises just one bit. In the run length code, you take between 1 and 8 bits from the source at a time and map them to one of 9 codewords - one of these codewords have a length of 1 bit, while the other 8 codewords have a length of 4 bits.

I agree that a Huffman code is the best choice *if* you are required to consider 8 bits from the source at a time. However, a Huffman code is not guaranteed to be the best choice if you can consider different numbers of bits from the source at a time - an arithmetic code will typically beat a Huffman code for this reason. I suspect that something about the way that the run-length code takes different numbers of bits from the source at a time makes it better than the Huffman code in this case. I’m not sure exactly what though…

Take care, Rob.