0
$\begingroup$

We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ".

I have created a Huffman tree for the string w.

We get the following table:

enter image description here

Now I want to create a Huffman tree for a Block-Code with length of block $4$.

Do we maybe take each consecutive 4 letters, i.e., {aabc, eefg, eebd, aabb, ceef, fghd, cbbe, efbb, bbgh, hie} to make the tree?

But then the last one is of length 3 and not 4.

So, do we choose in an other way the blocks?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

In your context, a block code of length $\ell$ encodes $\ell$ letters at a time. The domain thus consists of all words over the alphabet of length $\ell$. Unless you're told otherwise, the assumption is that the individual letters are independent - the probability of a word $\sigma_1 \dots \sigma_\ell$ is the product of the probabilities of the individual letters.

Improve this answer
$\endgroup$
8
  • $\begingroup$ So do we have to find all the possible words with 4 letters and then we create the tree considering these words as the symbols? $\endgroup$
    – Mary Star
    Commented Dec 7, 2016 at 7:59
  • $\begingroup$ Yes, that's the idea. $\endgroup$
    – Yuval Filmus
    Commented Dec 7, 2016 at 8:03
  • $\begingroup$ The words: "befa" and "efba" are counted as the same word, or not? $\endgroup$
    – Mary Star
    Commented Dec 7, 2016 at 10:14
  • $\begingroup$ The idea of the block code is to encode streams of letters more efficiently than one letter at a time. Given this rationale, you should be able to answer this question yourself. If you have any further questions, I suggest asking your TA or instructor. $\endgroup$
    – Yuval Filmus
    Commented Dec 7, 2016 at 10:17
  • $\begingroup$ I am not taking that subject,... I am trying to learn it by myself, by looking at some examples/notes of the internet... Unfortunately, I haven't found an example for a Huffman tree for a block code.... So, do we have the following block? $$$$ idcf, idca, idce, idcb, idch, idcg, dcgh, dcgf, dcga, dcge, dcgb, cghf, cgha, cghe, cghb, ghfa, ghfe, ghfb, hfae, hfab, faeb $$$$ How do we know if we have found all the possibilities? $\endgroup$
    – Mary Star
    Commented Dec 7, 2016 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.