# Information theory - is every optimal prefix code a Huffman code?

I'm not sure about it but it seems true for me. I know that for every optimal code there exists a prefix code that is optimal, but I'm not sure if it's Huffman code.

-
I was under the impression that a Huffman code is by definition an optimal prefix code. What's your definition of a Huffman code? – joriki Nov 27 '12 at 11:48
Yes, I believe so. If by optimal you mean "maximizing per-byte information" then yes. – yo' Nov 27 '12 at 11:50
Yes, Huffman Code indeed is an optimal prefix code, but I'm not sure if there exists optimal prefix codes that are not Huffman Codes. For me a Huffman Code is any code that we can retrieve from a tree in Huffman Algorithm (or any automorphic tree) – Gricha Nov 27 '12 at 11:58
this paper claims that not: anyserver.cityu.edu.hk/weijia/2003/DY_Long.pdf – Ayrat May 26 '13 at 12:06

Consider e.g. the probabilities $p(a)=p(b)=p(c)=1/3$. Then all the following codes are Huffman codes:
$$a\to 0, b\to10, c\to 11$$ $$a\to 00, b\to 01, c\to 1$$ $$a\to 10, b\to 0, c\to 11$$ $$\text{etc.}$$