DNA存儲場景下的大小噴泉碼模型設計*

崔競松,蔣昌躍,郭 遲

(1.武漢大學國家網絡安全學院,湖北 武漢 430072;2.武漢大學空天信息安全與可信計算教育部重點實驗室,湖北 武漢 430072; 3.武漢大學衛星導航定位技術研究中心,湖北 武漢 430072)

1 引言

據估計,到2025年全球數據總量將達163 ZB,而當前主流存儲介質的生產已不堪重負[1,2]。DNA是生物體用于存儲遺傳信息的載體,同樣具有存儲數字信息的能力。研究表明,DNA信息存儲密度可以達到1019bit/cm3,是硬盤的106倍[3,4]。DNA作為數據的存儲介質,具有密度大、能耗低、壽命長等優點,因此DNA存儲有廣闊的應用前景[5]。

目前已經提出了多種DNA存儲方案。2012年哈佛大學的Church等人[6]利用二進制轉換首次實現在體外將659 KB的數據存儲進DNA分子中,但該方案引入的冗余過多。2013年Goldman等人[7]利用哈夫曼編碼、四倍重疊法、三進制編碼將739 KB的信息存入DNA中。2015年Grass等人[8]將RS(Reed-Solomon)糾錯應用于DNA存儲,實現了83 KB信息的無錯誤存儲和讀取。2016年Blawat等人[9]將“前向糾錯碼”引入DNA存儲領域,提升了使用DNA分子進行數據存儲的可靠性。同年Bornholt等人[10]設計實現了DNA存儲體系中數據的“隨機訪問”。2017年哥倫比亞大學的Erlich等人[11]將“噴泉碼”引入到DNA編碼體系中,稱之為“DNA噴泉”,實現了較高的數據存儲密度,降低了冗余和成本。2020年Koch等人[12]將噴泉碼運用于信息存儲,并提出了“DNA信息可存儲萬物”的概念DoT(DNA-of-Things)。

過往研究中使用的噴泉碼算法在DNA存儲等應用場景中存在一定的不足:編碼端將源文件劃分成K個分組進行編碼,而解碼端需要確定參數K值才能進行解碼,因此在編碼端與解碼端之間需要額外的信道資源來傳遞關鍵參數K。在實際應用中可將K直接嵌入到所有編碼分組中來進行傳遞。但是,這種做法有極大的冗余,嚴重浪費信道的帶寬。另一種做法是在編碼端和解碼端中將K設為固定值。但是,這種做法忽略了源文件大小、數據分組長度及數據分組數目之間的關系,不適用于實際的DNA存儲應用場景。

基于上述問題,本文以DNA存儲應用為背景,提出了一種大小噴泉碼模型。一方面大噴泉碼用來編碼存儲源文件的內容;另一方面通過增加小噴泉碼帶外信道來優化關鍵參數K的傳遞,提高了帶寬的利用率,同時K可取任意值,擺脫了源文件大小等的限制。大噴泉碼與小噴泉碼互相結合,共同實現對源文件的編碼存儲。

2 噴泉碼與LT碼

噴泉碼是一種糾刪編碼[13-16],最初是針對二進制刪除信道BEC(Binary Erasure Channel)設計的,旨在為大規模數據的傳輸和可靠廣播場景提供一種理想的解決方案。在DNA存儲場景下,DNA分子在保存和復制的過程中會發生一定概率的變異甚至片段丟失。由于變異或片段丟失的DNA分子不可再用,相當于丟棄了數據,因此DNA分子存儲是一個典型的刪除信道。

LT碼(Luby Transform codes)是由Luby[17]在2002年提出的第一種實用噴泉碼。LT碼是一種無速率碼,可產生無限的編碼數據,具有簡單的編譯碼方法、較小的譯碼開銷和編譯碼復雜度。LT碼將源文件轉換為大量較短的信息,這些較短的信息并非源文件的一部分,而是將源文件中的信息通過特定的方式進行運算編碼后產生的。接收端收到一定量以上的編碼數據就可能成功解碼,與收到哪些編碼數據無關。

2.1 LT碼度分布

度是指與某一編碼數據分組相關聯的原始數據分組的數目,通常用d表示。傳統LT碼的度分布函數是由Luby首先提出來的理想孤波分布[17],其表達式如式(1)所示:

(1)

在實際應用中,編碼數據的抽樣往往無法精確符合理想孤波分布,總存在一些波動和誤差,從而出現解碼時度為1的數據斷層,導致解碼失敗。所以,通過修正理想孤波分布,給出更實用的魯棒孤波分布[18],其表達式如式(2)所示:

(2)

(3)

2.2 LT碼編碼

設有K個待編碼的原始數據分組,LT碼的編碼算法如算法1所示。

2.3 LT碼解碼

LT碼解碼是對接收到的N(N≥K)個編碼數據進行處理,從中恢復出K個原始數據。傳統LT碼解碼算法通常采用復雜度較低的置信度傳播BP(Belief Propagation)算法,其平均時間復雜度為O(KlnK)。該算法主要是從接收端生成的二分圖中,通過信息在校驗節點與變量節點之間不斷流動消去無用的邊,最終恢復出K個變量節點的值。傳統LT碼解碼算法如算法2所示。

BP解碼算法的雙向圖解碼過程如圖1所示。

Figure 1 Process of LT code decoding圖1 LT碼解碼過程

圖1展示了從編碼數據{1011}恢復出原始數據{101}的過程,其中空心圓表示原始數據分組,實心圓表示編碼數據分組。

2.4 使用噴泉碼算法的DNA存儲框架

使用噴泉碼進行DNA存儲的框架主要包括3個部分:源文件編碼寫入、介質生化存儲和解碼獲取源文件。

源文件編碼寫入是利用噴泉碼編碼算法將源文件轉換成若干條等長的DNA序列。介質生化存儲是將源文件編碼生成的DNA序列進行生化處理,主要包括DNA分子合成及DNA分子儲存。解碼獲取源文件是從DNA分子中還原出源文件,是編碼寫入的逆過程。在解碼之前,需要先對DNA分子進行生化實驗預處理,包括:PCR(Polymerase Chain Reaction)序列擴增、DNA測序(分析特定DNA片段的堿基序列,獲取DNA序列的A,C,G,T排列方式),再進行DNA序列糾錯、DNA序列去重等操作,最后進行噴泉碼解碼,獲取源文件。使用噴泉碼算法的DNA存儲編解碼過程如圖2所示。

3 面向DNA存儲的大小噴泉碼

3.1 DNA存儲場景的局限性

知名DNA合成公司TWIST目前的二代合成芯片高通量合成的寡核苷酸池(DNA文庫)中,單條DNA序列的堿基最大個數僅為300[19]。DNA序列合成技術的限制使得用戶在進行存儲編碼之前就需要確定出編碼輸出DNA序列的長度及條數。

Figure 2 DNA encoding and decoding using fountain code algorithm圖2 使用噴泉碼算法的DNA編解碼

Figure 3 File size varying with K value圖3 文件大小隨K值的變化情況

目前普遍使用四進制方式編碼DNA序列,即按照{00,01,10,11}與{A,C,G,T}的對應關系來實現二進制數據與DNA序列之間的轉換。DNA序列長度的限制會影響編碼時源文件數據分組長度的劃分,從而會導致參數K有較大變化。例如,當規定噴泉碼編碼輸出的單條DNA序列堿基個數為300時,編碼4個文件,大小分別為1 KB,10 KB,100 KB和1 MB的文件,編碼端將源文件劃分成的數據分組數目K隨文件大小變化的情況如圖3所示。

從圖3可以看出,當都按照300堿基長度進行數據分組時,參數K會隨文件長度的增大而明顯變化。若在編碼端和解碼端將K設為定值,則會影響源文件數據分組的長度,進而影響編碼數據轉換成的DNA序列的長度,顯然不適合DNA存儲的應用場景,因此有必要將參數K的信息傳遞給解碼端。

3.2 小噴泉碼設計

設源文件的比特數為L,源文件劃分的原始數據分組比特數為l,則K的計算如式(4)所示:

(4)

當L不能被l整除時,表示劃分的最后一個數據分組不足l比特,需要將其填充為l比特。設最后一個數據分組填充的比特數為n(0≤n

n=K×l-L

(5)

解碼端利用四進制編碼將接收到的DNA序列還原成二進制數據即可得知數據分組的比特數l。解碼端只要再獲取源文件的比特數L,即可由式(4)和式(5)計算出解碼所需要的關鍵參數K和n。所以,要將源文件的比特數L傳遞給解碼端。

設編碼端和解碼端將參數L統一用64 bit的整型表示。如果直接將L拼接在每個編碼數據分組的末尾,則解碼端從接收到的數據末尾截取固定的64 bit即為L。這種做法簡單有效,但會嚴重浪費信息空間,所有數據分組都拼接相同的64 bit信息會造成極大的冗余。解碼端只要成功收到一個數據分組即可獲得參數L,而其它數據分組末尾的64 bit將全部失去價值。

為了盡量減少參數L的帶寬,為大噴泉碼留出更多的數據存儲空間,本文設計了小噴泉碼來對參數L的傳輸進行優化。

3.3 大小噴泉碼模型結構

大小噴泉碼使用了一大一小2個噴泉碼對同一個源文件的不同信息分別進行編碼,再將2個噴泉碼的編碼結果合并為一個編碼分組進行存儲和傳輸,模型結構如圖4所示。

3.3.1 大噴泉碼編碼內容

如圖4上半部分所示,大噴泉碼負責對源文件的內容進行編碼。編碼端讀取待存儲的源文件后,按照LT碼編碼算法(算法1)的步驟進行編碼。

Figure 4 Coding structure of big and small fountain code model圖4 大小噴泉碼模型編碼結構

為了在解碼時能百分之百還原出存儲的源文件,大噴泉碼編碼的數據中還包含了源文件的名字及一個哈希值。先將固定長度的文件名拼接在源文件內容之后,再整體生成一個固定長度的哈希值并拼接在最后。將拼接了文件名和哈希值的數據作為源數據輸入大噴泉碼模型進行編碼。哈希值用于自校驗解碼出的內容與編碼時的內容是否相同。模型中編碼端與解碼端約定文件名與哈希值分別是相同的固定字節長度,這樣解碼端在解碼出數據后,從尾部截取固定長度即可獲得哈希值與文件名。

大噴泉碼將拼接了文件名和哈希值的源數據劃分為若干等長且互不重疊的數據分組,再利用隨機種子和度分布函數生成度值,最后選擇相應的數據分組進行異或運算,源源不斷地產生編碼分組。

3.3.2 小噴泉碼編碼內容

如圖4的下半部分所示,小噴泉碼負責對大噴泉碼編碼數據的比特數L進行編碼。與大噴泉碼相同,小噴泉碼在對參數L編碼之前,先對其生成一個固定比特數的哈希值,再將哈希值拼接在參數L的末尾。哈希值同樣用來自校驗,確保解碼出的數據與編碼時的相同。

小噴泉碼編碼數據劃分成的分組長度相對較短,一般為1 bit,也可根據具體場景進行調整。小噴泉碼編碼數據的比特數固定,因此總被劃分為固定數量的分組,再按照算法1的步驟進行編碼。大噴泉碼與小噴泉碼編碼同一個數據分組時,使用同一個隨機種子及度分布函數進行獨立編碼。在實際應用中,編碼輸出的DNA序列數量通常遠大于小噴泉碼編碼的原始數據分組數,因此小噴泉碼數據具有足夠大的冗余可以保證編碼存儲的信息能被解碼端成功解碼。

無論大噴泉碼還是小噴泉碼,都保留了傳統噴泉碼應對丟刪錯誤的特性,即在有部分數據隨機丟失的情況下都能從剩余編碼數據中恢復出原始數據。

4 大小噴泉碼編解碼

4.1 DNA規避序列限制問題

在DNA序列合成與測序過程中,由于生化實驗上的限制,并非所有編碼生成的DNA序列都可用,如GC含量高、均聚物長(如AAAAAA…)或含有酶切位點的DNA序列是不可取的,因為它們很難合成且容易出現測序錯誤[20,21]。為了保證編碼數據轉換成的DNA序列能夠滿足生化實驗上的要求,在編碼輸出序列時要考慮DNA規避序列的限制。如何避免規避序列的影響,本文基于大小噴泉碼提供了2種編碼方案。

4.1.1 丟刪編碼

噴泉碼主要應用在刪除信道場景中,其良好的特性能保證即使在有數據丟失的情況下,只要收集到足夠數量的數據,依然有很高的概率能成功解碼。因此,當編碼生成的DNA序列中出現了需要規避的子序列時,可直接將該條序列丟棄。噴泉碼可以生成無限數量的編碼數據,丟棄部分數據不會對編解碼過程產生影響。

該方案操作簡單,但當規避序列需要丟棄大量序列時,會導致隨機種子的比特空間有較大的膨脹。例如,當需要編碼輸出1 000條DNA序列時,在無規避序列的情況下只需10 bit的種子空間;而當規避序列特別多或需要規避一些出現頻率較高的子序列時,可能至少需要生成100 000條序列才能產生1 000條合格的序列,而此時隨機數種子的空間就變為了17 bit,這會導致原本存放大噴泉碼編碼數據的帶寬被占用。

4.1.2 MRC算法編碼

編碼端可采用一些編碼算法,在將編碼數據轉換成DNA序列時直接規避掉不希望出現的子序列,例如Liu等人[22]提出的MRC(Mixed Radix Coding)算法。MRC算法不是利用四進制方式編碼DNA序列,而是利用變進制的思想,在把編碼數據轉換成DNA序列的過程中,結合用戶輸入的規避序列,通過不斷地進行取模、除法操作直接生成不含規避序列的DNA序列。該算法的優點是編碼端不會因規避序列而大量丟棄生成的DNA序列,一旦產生足夠數量的序列即可結束編碼;缺點是DNA存儲介質的不均勻性會導致MRC算法編碼出的DNA序列是不定長的。超過長度的DNA序列會被丟棄,因此為了保證大多數MRC算法轉化的序列長度小于或等于規定的長度,需要適當地縮短源文件劃分數據分組的比特數l。

對于MRC算法編碼生成的長度小于規定長度的DNA序列,需要將末尾的間隙進行填充,使得所有序列保持等長。為了充分利用部分堿基序列尾部的間隙空間,可利用小噴泉碼的編碼數據進行填充。這種方案下小噴泉碼需在大噴泉碼編碼之后再進行編碼。在將大噴泉碼編碼數據使用MRC算法編碼成DNA序列之后,統計該序列缺損的堿基空間數,此時小噴泉碼再利用大噴泉碼的隨機種子編碼出相應數量的數據進行填充。

2種方案編碼生成的數據分組結構示意圖如圖5所示。

Figure 5 Encoded packet structures of two schemes圖5 2種方案的編碼分組結構

圖5a為丟刪編碼方案的分組結構示意圖,其特點是所有數據分組中的大噴泉碼數據及其對應的DNA序列都是等長的;所有分組最后固定的1 bit為小噴泉碼數據,小噴泉碼編碼數據量等于總編碼分組數量。圖5b為MRC算法編碼方案的分組結構示意圖,其特點是所有數據分組中的大噴泉碼數據是等長的,但轉換成的DNA序列是不定長的;對那些長度較短的DNA序列利用小噴泉碼數據進行填充使其都變為等長的,小噴泉碼編碼數據與總分組數目之間的關系不固定。

4.2 大小噴泉碼模型編碼

噴泉碼編碼出的每個數據分組都有一個唯一對應的隨機數種子。解碼端使用與編碼端相同的隨機算法,即可根據隨機種子恢復出編碼數據的度及參與編碼的原始分組編號等信息,因此隨機種子也需要隨編碼數據一起傳遞給解碼端。

由于編碼文件的大小不固定,或用戶對同一文件有不同的編碼DNA序列長度、數量要求時,會導致隨機種子的比特空間有較大變化。例如,將同一個文件編碼成500條DNA序列,只需9 bit的種子空間,而編碼成10 000條序列至少需要14 bit的種子空間。為了充分利用有限長度的DNA序列中的所有空間,大小噴泉碼模型將編碼數據中的隨機數種子設計為動態長度的形式進行嵌入。

以丟刪編碼方案為例,模型按照實際需求計算出一個確定長度的隨機種子直接拼接在編碼數據分組的頭部,尾部的1 bit存放小噴泉碼編碼數據,中間剩余的空間全部存放大噴泉碼的編碼數據。對于輸入的源文件,編碼端進行填充、拼接文件名、生成哈希值等預處理后,大噴泉碼與小噴泉碼獲得各自待編碼的數據,結合用戶輸入的規避序列及DNA序列長度和數量要求,開始進行編碼。以丟刪編碼方案為基礎的大小噴泉碼模型的編碼算法如算法3所示。

算法3 大小噴泉碼編碼算法輸入:源文件。輸出:指定長度和數量的DNA序列。Step 1 讀取源文件,對待編碼數據進行填充、生成哈希值等預處理。Step 2 從根據實際要求計算得出的隨機種子空間中產生一個隨機種子。Step 3 大、小噴泉碼分別利用Step2產生的隨機種子各自進行編碼。Step 4 編碼端將隨機種子與大、小噴泉碼編碼數據拼接后的數據轉換成DNA序列。Step 5 檢查生成的DNA序列中是否出現規避序列,出現則丟棄該條DNA序列,否則保留該條DNA序列。Step 6 重復Step 2～Step 5,若產生足夠數量的DNA序列,則編碼結束;若種子空間用完還未編碼出足夠數量的序列,則種子空間長度加1,重復Step 2～Step 6。

模型編碼算法的流程如圖6所示。

Figure 6 Flow chart of big and small fountain code encoding algorithms圖6 大小噴泉碼編碼算法流程圖

4.3 大小噴泉碼模型解碼

噴泉碼要求用于解碼的數據必須是無錯的。在實際應用中,還需對噴泉碼編碼生成的DNA序列添加糾錯碼用于檢錯和糾錯。在解碼前先利用糾錯編碼挑出所有無錯數據。獲得無錯數據后,解碼第一步要先確定所有數據分組對應的隨機種子。

模型編碼時隨機種子以動態長度的方式嵌入,但整個編解碼過程中并未傳遞隨機種子長度信息。大小噴泉碼模型在解碼端通過試探的方式,利用小噴泉碼編碼數據末尾哈希值的自校驗來確定隨機種子的長度。小噴泉碼編碼的數據比特數是固定值,因此被劃分為固定數量個原始分組,記為k。解碼端每次都先試探解碼固定數量的k個小噴泉碼數據,并進行哈希自校驗確認是否解碼成功,若解碼失敗則種子空間加1后重新試探。試探的過程不能無限進行下去,因此編碼端和解碼端需要約定好隨機種子比特數的下限值llower和上限值lupper,則編碼端能夠編碼的DNA序列總數被限定在了[2llower,2lupper]內。假設試探隨機種子的起始長度為seedlenstart,解碼端接收到的DNA序列數量為N(N≥K),則式(6)成立:

seedlenstart=max(llower,lbN+1)

(6)

從式(6)可以看出,從隨機種子長度的下限值及根據N計算得出的隨機種子長度中選擇較大值作為起始值開始試探。大小噴泉碼模型的解碼算法如算法4所示。

算法4 大小噴泉碼解碼算法輸入:DNA序列。輸出:源文件。Step 1 利用糾錯碼挑選正確的DNA序列,將DNA序列按照對應方式轉換成二進制數據,從所有編碼分組數據尾部截取固定比特作為小噴泉碼數據。Step 2 根據式(6)確定隨機種子的起始長度。Step 3 按照當前隨機種子的比特數,從所有數據頭部截取相應長度的隨機種子。Step 4 利用Step 3得到的隨機種子及與編碼端相同的隨機算法和度分布函數嘗試小噴泉碼解碼,并進行小噴泉碼尾部哈希值的自校驗。Step 5 若小噴泉碼解碼失敗或小噴泉碼未通過哈希自校驗,則隨機種子長度加1,重復Step 3和Step 4。若小噴泉碼解碼成功,則確定所有編碼分組的隨機種子及小噴泉碼存儲的關鍵參數L。若在約定的隨機種子空間范圍內小噴泉碼解碼失敗,則返回解碼失敗,退出程序。Step 6 利用Step 5確定的隨機種子與參數L進行大噴泉碼解碼,返回大噴泉碼解碼結果。

大小噴泉碼模型解碼算法流程如圖7所示。

Figure 7 Flow chart of big and small fountain code decoding algorithm圖7 大小噴泉碼解碼算法流程圖

大噴泉碼解碼成功后,從解碼出的數據末尾截取與編碼端約定長度的比特數作為哈希值,并進行自校驗。通過自校驗后再從尾部截取固定的字節長作為文件名,再將剩余的數據全部寫入到文件中進行保存,即恢復出了存儲的源文件。

為了提高解碼的成功率,大小噴泉碼模型的解碼算法均使用了置信度傳播-最大似然聯合譯碼BPML(Belief Propagation-Maximum Like-Lihood)算法[23]。解碼時使用BP算法,利用1度的數據先進行線性解碼。BP算法平均時間復雜度較低,消耗資源少,可快速解碼出大部分的源數據。對那些因缺少1度數據而無法繼續解碼的剩余數據,解碼端再使用最大似然(ML)解碼算法,利用高斯消元求解方程組解碼剩余數據,從而有效提高解碼成功率。但是,ML算法的時間復雜度比較高,達到了O(K3)。

5 仿真實驗與分析

以存儲圖像為例,將圖像分別壓縮至10 KB, 100 KB和200 KB 3種大小進行DNA存儲仿真實驗。測試程序用C語言編寫。

實驗中設置隨機種子比特數的下限為10,上限為24,因此編碼端能夠編碼的DNA序列數被限制在[1 024,16 777 216]內,滿足實驗及應用的需求。設置式(3)中的參數c=0.05,δ=0.05。在假設規避序列只有{GGATCC,AAAA}的情況下,以輸出300個堿基長的DNA序列為標準,對4.1節中提出的2種規避序列編碼方案進行測試。3幅圖像的編碼要求信息如表1所示。

Table 1 Coding experiment information表1 編碼實驗信息

5.1 仿真實驗測試

對4.1節提出的2種方案分別進行編解碼實驗。實驗中設置編碼端和解碼端約定的文件名長度固定為100 B,哈希值長度固定為16 B,因此大噴泉碼實際編碼的數據為源文件內容再加上100 B的文件名和16 B的哈希值。模型中編碼端和解碼端都設置參數L為64 bit的整型表示。小噴泉碼實際編碼的是一個192 bit數的數據,其中包括64 bit的L和128 bit的哈希值,因此小噴泉碼數據總是被固定地劃分為192個分組。

5.1.1 丟刪編碼方案實驗

丟刪編碼方案對3幅不同大小的圖像進行編碼時產生的數據如表2所示。

Table 2 Experimental results of drop-and-delete encoding 表2 丟刪編碼方案編碼實驗結果

表2中的大噴泉碼數據分組長度為源文件內容劃分的分組長度;隨機種子長度是基于規避序列丟棄情況編碼所需的DNA序列而確定的實際比特數。3幅圖像在編碼時被劃分成的原始數據分組數K分別為142,1 400和2 801,而編碼輸出的DNA序列數都遠高于原始數據分組數,其冗余率分別為604.2%,328.6%和328.4%,可以保證在有部分數據丟失的情況下依然具有較高的解碼成功概率。

模擬DNA分子在復制、存儲、測序時因變質而丟失的過程,即對3幅圖像編碼產生的DNA序列隨機刪除其中50%的數據,用剩余的數據進行解碼,重復100次實驗。3個樣本剩余的用于解碼的DNA序列數量分別為500,3 000和6 000,此時冗余率分別為252.1%,114.3%和114.2%。解碼過程產生的數據如表3所示。

Table 3 Experimental results of drop-and-delete decoding 表3 丟刪編碼方案解碼實驗結果

由表3可知,利用式(6)計算3幅圖像的隨機種子試探的起始長度分別為10 bit, 12 bit和13 bit,小噴泉碼試探解碼的次數均為3次,大噴泉碼的解碼結果均為成功。

5.1.2 MRC算法編碼方案實驗

使用MRC算法編碼方案測試時,為了保證大多數編碼生成的DNA序列長度小于或等于規定的長度,對源文件的數據分組長度進行了適當的壓縮,編碼過程產生的數據如表4所示。

Table 4 Experimental results of MRC algorithm encoding 表4 MRC算法方案編碼實驗結果

由表4可知,該方案比丟刪編碼方案中的大噴泉碼數據長度平均短8 bit,但平均丟棄的DNA序列數僅為丟刪編碼方案的0.8%。丟棄序列的減少降低了隨機種子的比特長度,該方案比丟刪編碼方案的隨機種子長度平均短了1 bit。

與丟刪編碼方案做法相同,從3幅圖像編碼生成的DNA序列中,隨機刪除50%的數據,用剩余的DNA序列分別進行解碼測試,重復100次實驗。解碼過程的實驗結果如表5所示。

Table 5 Experimental resultsof MRC algorithm decoding 表5 MRC算法方案解碼實驗結果

由表5可知,利用MRC解碼算法求出的小噴泉碼數據數目不固定,從表5的第2列可以看出,在3組樣本的實驗中,用于小噴泉碼解碼的數據量均大于192;由于隨機種子長度縮短,所以試探解碼小噴泉碼的次數也比丟刪編碼方案的有所減少;大噴泉碼的解碼結果均為成功。

在上述2種方案的實驗中,由于小噴泉碼數據編碼時被固定劃分為192個分組,因此用于解碼小噴泉碼的數據分組數要大于或等于門限值才有可能成功解碼。若用于解碼的數據分組數量小于192,則模型不會進行小噴泉碼解碼而是直接返回解碼失敗。同理,當小噴泉碼成功解碼出參數K后,若用于解碼大噴泉碼的數據量小于K,也會直接返回解碼失敗,并返回失敗原因。

5.2 性能分析

5.2.1 解碼成功率分析

對大小噴泉碼模型與傳統LT碼進行解碼成功率對比測試。源文件的原始分組數目K會影響相同冗余度下的解碼結果,K越小越需要更高的冗余才能有較高的解碼成功率。以丟刪編碼為例,對3幅圖像數據分別進行冗余度1～1.2的解碼實驗,對每幅圖像數據樣本的各個冗余度分別進行100次重復實驗。2種方法的平均解碼成功率對比如圖8所示。

Figure 8 Comparison of decoding success rate between two methods圖8 2種方法的解碼成功率對比

從圖8可以看出,圖像的上半部分,當用于解碼的DNA序列冗余度達到1.04及以上時,大小噴泉碼模型都能以接近100%的概率成功解碼;圖像的下半部分,傳統LT碼在冗余度為1.10的情況下,解碼成功率約等于20%。傳統LT碼解碼只使用BP算法,難以在較低冗余的情況下達到較高的解碼成功率。

5.2.2 解碼時間效率分析

本文使用大小噴泉碼與傳統噴泉碼對大小為100 KB的圖像進行解碼時間的對比仿真實驗。實驗環境為:操作系統為Windows10 64位,處理器為Intel?CoreTMi5-7200U CPU @ 3.10 GHz,4 GB RAM。每組實驗100次,結果取平均值,最終結果如圖9所示。

Figure 9 Comparison of average decoding time between big and small fountaincode and traditional LT code圖9 大小噴泉碼與傳統LT碼平均解碼時間對比

從圖9可以看出,在相同的硬件環境下大小噴泉碼模型的解碼時間僅略高于傳統噴泉碼的,平均解碼時間相差不超過10%。大小噴泉碼模型解碼時通過試探的方式確定隨機種子長度,因此可能首先會進行多次小噴泉碼解碼,此過程需要花費一定的時間。此外大小噴泉碼模型在解碼后期對因缺少1度而無法繼續解碼的數據使用了ML算法繼續解碼。ML算法本質是高斯消元法求解方程組,可有效提高解碼的成功率,但需要消耗更多的時間。設因缺少1度而無法繼續解碼的數據規模為S,則BPML算法解碼的時間復雜度約為O((K-S)ln(K-S))+O(S3)。當解碼的數據量達到一定冗余時,S的規模會很小,因此整個解碼算法的復雜度僅略高于BP算法的。

5.2.3 數據存儲密度分析

在數據存儲密度方面,由于MRC算法編碼的不均勻性,可能會導致編碼生成的DNA序列超過規定長度。對該方案的數據分組長度進行適當壓縮,讓更多MRC編碼生成的DNA序列小于或等于規定的長度,但因此會降低存儲密度。在相同的實驗參數下,3種方案的存儲密度對比如圖10所示(圖10中縱坐標存儲空間利用率即為存儲密度)。

Figure 10 Comparison of storage space utilization among three schemes圖10 3種方案的存儲空間利用率對比

從圖10可以看出,丟刪編碼方案具有更高的存儲密度。丟刪編碼方案中每條編碼的DNA序列中大噴泉碼的存儲密度比MRC算法方案的要多出約1.3%;而這2種方案與傳統的LT碼在數據分組末尾直接拼接整個參數L的做法相比,存儲密度要高出約11.8%。

實驗結果表明,本文提出的大小噴泉碼模型能有效降低關鍵參數K傳輸的帶寬,實現了以較低的帶寬消耗傳輸一個關鍵參數的目的。

6 結束語

本文針對DNA存儲應用場景下噴泉碼中關鍵參數K的傳遞問題,設計了一種大小噴泉碼模型。該模型中的小噴泉碼作為帶外信道負責向解碼端傳遞一些大噴泉碼解碼過程需要的關鍵參數,并且在每個編碼數據分組中,小噴泉碼數據降低到了1 bit,有效壓縮了關鍵參數傳輸的帶寬,提高了空間利用率。

在未來的工作中,大小噴泉碼模型需要進一步優化的方向是如何有效傳遞隨機種子比特數信息。目前模型中隨機種子是根據實際計算的長度動態嵌入到數據分組中的,而解碼時,解碼端無法獲得隨機種子比特數信息,只能通過試探的方法,借助小噴泉碼的哈希自校驗來確定種子比特數。這種方法的缺點是需要進行多次試探,會降低時間效率,未來可以進一步優化以提高時間效率。