[發明專利]一種特定條件下超越熵極限的符號編碼方法

在審

• 申請號: 202210532302.8
• 申請日: 2022-05-09
• 公開（公告）號: CN114915295A
• 公開（公告）日: 2022-08-16
• 發明（設計）人: 胡安琪;鞏小雪;郭磊;李瑞
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 方鐘苑

本發明涉及一種特定條件下超越熵極限的符號編碼方法，屬于信息編碼技術領域，基于符號空間的全覆蓋，對源數據按照全覆蓋進行分塊劃分，再以分塊為處理單元進行編碼。編碼過程包括對分塊內的所有符號，按頻次進行降序排序，引入符號向量，所述符號向量是維度為n的單位向量且不同的符號向量之間，兩兩正交；引入塊內終止標記，所述塊內終止標記為n個連續的‘0’，解碼時若遇到塊內終止標記，則不進行最后1個符號的補全。本發明在塊長度小于23的條件下，碼率突破了信源編碼定理中香農熵下限，且沒有丟失任何信息。

技術領域

本發明屬于信息編碼技術領域，涉及一種特定條件下超越熵極限的符號編碼方法。

背景技術

隨著大數據時代的來臨，我們需要處理的數據量呈現爆炸式的增長。這意味著數據需要更高效的表示方式，以達到更好的壓縮效果。與之相關的信息編碼技術是計算機，互聯網，數據存儲，通信等領域的基礎，因此，研究新的信息編碼技術，具有很重要的意義。

在信息論中，香農的信源編碼定理(無噪聲編碼定理)確立了數據壓縮的限度，以及香農熵的操作意義。信源編碼定理表明(在數據長度趨向于無窮的極限情況下)不可能把數據壓縮得碼率(每個符號的平均比特)比信源的香農熵還小，否則信息將丟失。迄今為止，業界尚沒有突破信源編碼定理中香農熵下限的例子。

發明內容

有鑒于此，本發明提出了空間覆蓋碼的概念及其編/解碼算法的實施步驟，并展示了在四進制編碼上，空間覆蓋碼突破香農信源編碼下限的優良特性。

為達到上述目的，本發明提供如下技術方案：

一種特定條件下超越熵極限的符號編碼方法，基于符號空間的全覆蓋，對源數據按照全覆蓋進行分塊劃分，再以分塊為處理單元進行編碼；

所述符號空間是指將源數據D中可能出現的全部符號構建出集合S，S即為符號空間；

所述基于符號空間的全覆蓋是指：源數據D中存在一個數據塊B，其內含有S中的全部符號，則稱數據塊B完成了對符號空間S的全覆蓋；

所述對源數據按照全覆蓋進行分塊劃分，具體包括：從源數據D的第1個符號開始，對源數據中的符號進行統計，直到首次出現對符號空間S的全覆蓋為止，產生第一個數據塊B₁；繼續對源數據中的剩余符號進行統計，直到第2次出現對符號空間S的全覆蓋為止，產生第二個數據塊B₂，以此類推直到源數據統計完成，得到滿足全覆蓋的源數據分塊。

進一步，所述以分塊為處理單元進行編碼具體包括：

以分塊B_i為處理單元進行編碼，分塊B_i內最后1個符號滿足唯一性，將其作為可推斷的信息，其熵為0，不參與編碼；對分塊B_i內的所有符號，按頻次進行降序排序；若兩個符號的頻次相等，則數值大的符號優先排在前面。

進一步，以分塊B_i為處理單元進行編碼時，引入符號向量，所述符號向量是維度為n的單位向量且不同的符號向量之間，兩兩正交，其中n為符號空間S的大小。

進一步，以分塊B_i為處理單元進行編碼后，在編碼結果中，每個符號的編碼形式均為：最后一位為‘1’；前面有若干個‘0’。

進一步，以分塊B_i為處理單元進行編碼后，引入塊內終止標記，所述塊內終止標記為n個連續的‘0’，解碼時若遇到塊內終止標記，則不進行最后1個符號的補全。

進一步，所述以分塊B_i為處理單元進行編碼具體包括：用維度為n的列向量來表示所有符號，單位矩陣I_n就是符號空間S的矩陣表示；依次取B_i中各個符號的列向量來構成矩陣L_n×M，矩陣L_n×M是大小為n×M，M為B_i的長度；