[發明專利]基于Knuth碼的聯合信道與安全編譯碼設計方法

在審

• 申請號: 201310021196.8
• 申請日: 2013-01-22
• 公開（公告）號: CN103944577A
• 公開（公告）日: 2014-07-23
• 發明（設計）人: 陳德元;凃國防
• 申請（專利權）人: 中國科學院大學
• 主分類號: H03M7/12
• 分類號: H03M7/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及Knuth碼，也稱為平衡碼(Balanced?Codes)編碼碼流的一種聯合信道與安全編解碼器設計方法，主要涉及具有碼流檢錯和加密功能的隨機Knuth碼設計方法。

背景技術

為了在有噪信道上進行可靠傳輸，需要克服信道中的噪聲和干擾。信道編碼(Channel?Coding)或稱前向糾錯編碼(Forward?Error?Correction，FEC)，根據一定的準則在待發送的信息碼元中加入必要的校驗碼元，接收端利用校驗碼元與信息碼元之間的編碼準則，檢測和糾正差錯，提高信息碼元傳輸的可靠性。研究信道編碼的目標是利用最少的校驗碼元，獲得較高的可靠性傳輸，即在保證傳輸可靠性的前提下，盡量提高編碼效率。Knuth碼是斯坦福大學著名學者Donald?E.Knuth于1986年在文章《Efficient?Balanced?Codes》中提出的一種具有檢錯功能的信道編碼方案。該碼要求碼字中符號“1”和符號“0”的個數相同，因此，也稱為平衡碼(Balanced?Codes)。

該碼的主要參數為：信息比特數為k，檢驗比特數為r，碼長n＝k+r，共有2^k個碼字，每個碼字中符號“1”的個數(或稱Hamming重量)為其中為下取整函數。Knuth碼編碼簡單，且結構特性良好，具有廣泛的應用。可用于檢測所有的單向錯誤(符號“1”錯為符號“0”，或反過來)，對延時不敏感異步空間通信，超大規模集成電路(Very?Large?Scale?Integration，VLSI)系統降噪，光盤數據存儲等。傳統Knuth碼編碼器框圖如圖1所示。

在Knuth的開創性文章中，提出了一種簡單的并行編碼方案(Parallel?Coding?Scheme)。設輸入信息向量為u，其長度為k，u^(j)＝v(u)表示向量u前j比特取反后的向量，v(·)為部分反轉操作函數，其中j＝1，2，…，k。Knuth證明了對所有輸入向量u，至少存在一個平衡位置點j，使u^(j)的Hamming重量為即u^(j)是平衡的。為傳輸和編碼方便，選擇最小值j作為u的平衡位置點。為了對位置索引j進行平衡編碼，Knuth編碼方案需要在索引j與r比特的平衡序列j₂之間建立一一映射關系表(j＝0，1，…，k-1)。獲得最小值j后，通過查表得到對應的r比特平衡序列j₂。最后輸出信息向量u的Knuth編碼符號表示兩個二進制序列的結連。解碼時，解碼器將接收矢量c分割為k比特數據向量u^(j)和r比特檢驗向量j₂，采用查表方式獲得最小平衡位置點j，然后取反u^(j)的前j比特，則可獲得發送信息向量u。

例如，設信息長度k＝10，校驗比特數r＝6，u＝0111010110，則u⁽³⁾＝1001010110，平衡位置點有3個，分別為j＝3，5，7，選擇最小值j＝3進行編碼。設索引3對應的6比特平衡序列為j₂＝011001，最后輸出編碼碼流為在接收端，解碼器首先從接收向量中分別提取10比特數據向量u⁽³⁾＝1001010110和6比特校驗向量j₂＝011001，然后查表獲得該校驗向量對應的最小平衡位置為3，最后將u⁽³⁾＝1001010110的前3位取反，獲得原輸入信息向量u＝0111010110。

從編碼器框圖1可以看出，Knuth編碼主要由四個部件組成，該碼流不具備加密功能，在信道(特別是無線信道)上傳輸容易泄密。為獲得加密碼流，本發明基于Knuth碼具有良好結構的特點，對傳統Knuth碼編碼器的最小位置平衡點的搜索方向進行隨機化處理，如圖2所示，從而獲得加密碼流。

發明內容

為了解決經典Knuth碼流不具備加密功能的問題，本發明設計了一種基于密鑰控制的隨機編碼方法，實現了Knuth碼流的檢錯和加密功能。

本發明解決技術問題所采用的技術方案是：以密鑰Key為種子，產生一個隨機二進制數b。該二進數用于控制Knuth編碼器的平衡位置點搜索方向：若b＝0，與經典Knuth編碼器搜索方向相同，即前向搜索輸入信息序列的平衡位置點；反之，若b＝1，與經典Knuth編碼器搜索方向相反，即后向搜索輸入信息序列的平衡位置點。經過新設計的編碼器編碼后，輸出碼流具有加密功能。