即时码可以采用码树法来构造。例如即时码W={W1,W2,W3,W4}={0,10,110,111},可以按以下步骤得到即时码的码树。

(1)最上端为树根,从根开始,画出两条分支(树枝),每条分支代表一个码元。因为W1的码长L1=1,任选一条分支的终点(称为节点)来表示W1。

(2)从没有选用的分支终点再画出两条分支,因为L2=2,选用其中的一个分支终点来表示W2。

(3)继续下去,直到所有的Wi都有分支终点来表示为止。

(4)从顶点(树根)到Wi,要经过Li条分支,把这些分支所代表的码元依照先后次序就可以写出该码字。

码树还可以用来对即时码进行译码。例如收到一串码字100110010,从码树的树根出发,第一个符号为1,向右走一节;第二个码符号为0,向左走一节,遇到了码字W2。然后再回到树根,从头开始,遇到了码字后又回到树根。这样就可完成对即时码的即时译码。码字100110010译码得到的码字分别为W1=0,W2=10,W3=110,W4=111,如图7.4所示。

图7.4　对即时码100110010进行译码

对较简单的信源,可以很方便地用码树法直观地构造出即时码。但是当信源较复杂时,直接画码树就比较复杂。1949年L.G.Kraft提出一个在数学上与码树等效的、表达即时码存在充要条件的不等式。(www.daowen.com)

定理7.1　对于码长分别为L1,L2,…,Lq的r元码,若此码为即时码,则必定满足

反之,若码长满足上式,则一定存在具有这种码长的r元即时码。

克拉夫特(Kraft)不等式是即时码存在的充要条件。其中,r为码元的进制数,q为信源的符号数,Li为信源符号对应的码字长度。注意的是,上述不等式只是即时码存在的充要条件,而不能作为判断依据。后来麦克米伦(B.McMillan)证明唯一可译码也满足克拉夫特不等式。这说明在码长选择的条件上,即时码与唯一可译码是一致的。

【例7.2】对于二元码,即r=2,如果q=4,L1=2,L2=2,L3=2,L4=2,是否存在这样的唯一可译码和即时码?

解:因为2-Li=2-2+2-2+2-2+2-2=1

所以满足克拉夫特不等式,则一定可以构成至少一种具有这样码长的唯一可译码和即时码。