關于前綴碼、極大前綴碼計數問題的研究

瞿冰潔 玉溪師范學院數學與信息技術學院 指導教師 劉云

1 引言

近些年來,數字通信領域尤其是移動通信,衛星通信和計算機通信有了巨大的增長.在這些系統中,信息被表示成一個二進制的碼元序列。然后這些二進制的碼經過調制并被送到傳輸信道中傳輸。

因此為了確保一個可靠而高效的傳輸,對信息的編碼需要增加各種要求和限制.這使得碼的計數問題是碼論中的一個重要問題,它關系到我們在實際應用中可以使用的碼的數量多少,這在信息壓縮、傳輸、糾錯、加密等應用中是至關重要的。本文主要研究有限字母表上最大碼字長度為任意給定值的前綴碼、極大前綴碼的計數問題。

2 準備知識

我們在本文中主要討論前綴碼的計數問題。

由定理2,3可得：

定理得證。

3 最大字長為的前綴碼、極大前綴碼的計數問題研究

樹碼022122+1=5 3252+1=26 213(此處由于碼個數太多, 省略)262+1=677 6514(此處由于碼個數太多, 省略)6772+1=458330 457653

從而有：

對于極大前綴,類似地有下表：

?

由定理4, 我們可得以下更一般的結論。

由定理6得：

因此最大長度為n的前綴碼的個數為

同理可知：

從而有

定理得證。