Left and right edges become the bits in each symbol's code.

highlighted = computed this step

Edges become bit names

After the merges, each left edge contributes 0 and each right edge contributes 1.

left=0,right=1\text{left}=0,\quad \text{right}=1
Read the code tableHuffman rows recomputed from pinned counts and message.Read the code table - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

A gets the shortest code

A is the most common symbol, and its code is 1.

A=1A=1
Read the code tableHuffman rows recomputed from pinned counts and message.Read the code table - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

The smaller counts get longer names

B uses 00, C uses 010, and D uses 011.

B=00,C=010,D=011B=00,C=010,D=011
Read the code tableHuffman rows recomputed from pinned counts and message.Read the code table - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

Summary

No code is the prefix of another code, so the receiver can read the bitstream from left to right.

prefix code\text{prefix code}
Read the code tableHuffman rows recomputed from pinned counts and message.Read the code table - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes