DNA存儲(chǔ)場(chǎng)景下的大小噴泉碼模型設(shè)計(jì)*

崔競(jìng)松,蔣昌躍,郭 遲

(1.武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院,湖北 武漢 430072;2.武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430072; 3.武漢大學(xué)衛(wèi)星導(dǎo)航定位技術(shù)研究中心,湖北 武漢 430072)

1 引言

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

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

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

基于上述問(wèn)題,本文以DNA存儲(chǔ)應(yīng)用為背景,提出了一種大小噴泉碼模型。一方面大噴泉碼用來(lái)編碼存儲(chǔ)源文件的內(nèi)容;另一方面通過(guò)增加小噴泉碼帶外信道來(lái)優(yōu)化關(guān)鍵參數(shù)K的傳遞,提高了帶寬的利用率,同時(shí)K可取任意值,擺脫了源文件大小等的限制。大噴泉碼與小噴泉碼互相結(jié)合,共同實(shí)現(xiàn)對(duì)源文件的編碼存儲(chǔ)。

2 噴泉碼與LT碼

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

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

2.1 LT碼度分布

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

(1)

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

(2)

(3)

2.2 LT碼編碼

設(shè)有K個(gè)待編碼的原始數(shù)據(jù)分組,LT碼的編碼算法如算法1所示。

2.3 LT碼解碼

LT碼解碼是對(duì)接收到的N(N≥K)個(gè)編碼數(shù)據(jù)進(jìn)行處理,從中恢復(fù)出K個(gè)原始數(shù)據(jù)。傳統(tǒng)LT碼解碼算法通常采用復(fù)雜度較低的置信度傳播BP(Belief Propagation)算法,其平均時(shí)間復(fù)雜度為O(KlnK)。該算法主要是從接收端生成的二分圖中,通過(guò)信息在校驗(yàn)節(jié)點(diǎn)與變量節(jié)點(diǎn)之間不斷流動(dòng)消去無(wú)用的邊,最終恢復(fù)出K個(gè)變量節(jié)點(diǎn)的值。傳統(tǒng)LT碼解碼算法如算法2所示。

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

Figure 1 Process of LT code decoding圖1 LT碼解碼過(guò)程

圖1展示了從編碼數(shù)據(jù){1011}恢復(fù)出原始數(shù)據(jù){101}的過(guò)程,其中空心圓表示原始數(shù)據(jù)分組,實(shí)心圓表示編碼數(shù)據(jù)分組。

2.4 使用噴泉碼算法的DNA存儲(chǔ)框架

使用噴泉碼進(jìn)行DNA存儲(chǔ)的框架主要包括3個(gè)部分:源文件編碼寫(xiě)入、介質(zhì)生化存儲(chǔ)和解碼獲取源文件。

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

3 面向DNA存儲(chǔ)的大小噴泉碼

3.1 DNA存儲(chǔ)場(chǎng)景的局限性

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

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

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

目前普遍使用四進(jìn)制方式編碼DNA序列,即按照{(diào)00,01,10,11}與{A,C,G,T}的對(duì)應(yīng)關(guān)系來(lái)實(shí)現(xiàn)二進(jìn)制數(shù)據(jù)與DNA序列之間的轉(zhuǎn)換。DNA序列長(zhǎng)度的限制會(huì)影響編碼時(shí)源文件數(shù)據(jù)分組長(zhǎng)度的劃分,從而會(huì)導(dǎo)致參數(shù)K有較大變化。例如,當(dāng)規(guī)定噴泉碼編碼輸出的單條DNA序列堿基個(gè)數(shù)為300時(shí),編碼4個(gè)文件,大小分別為1 KB,10 KB,100 KB和1 MB的文件,編碼端將源文件劃分成的數(shù)據(jù)分組數(shù)目K隨文件大小變化的情況如圖3所示。

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

3.2 小噴泉碼設(shè)計(jì)

設(shè)源文件的比特?cái)?shù)為L(zhǎng),源文件劃分的原始數(shù)據(jù)分組比特?cái)?shù)為l,則K的計(jì)算如式(4)所示:

(4)

當(dāng)L不能被l整除時(shí),表示劃分的最后一個(gè)數(shù)據(jù)分組不足l比特,需要將其填充為l比特。設(shè)最后一個(gè)數(shù)據(jù)分組填充的比特?cái)?shù)為n(0≤n

n=K×l-L

(5)

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

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

為了盡量減少參數(shù)L的帶寬,為大噴泉碼留出更多的數(shù)據(jù)存儲(chǔ)空間,本文設(shè)計(jì)了小噴泉碼來(lái)對(duì)參數(shù)L的傳輸進(jìn)行優(yōu)化。

3.3 大小噴泉碼模型結(jié)構(gòu)

大小噴泉碼使用了一大一小2個(gè)噴泉碼對(duì)同一個(gè)源文件的不同信息分別進(jìn)行編碼,再將2個(gè)噴泉碼的編碼結(jié)果合并為一個(gè)編碼分組進(jìn)行存儲(chǔ)和傳輸,模型結(jié)構(gòu)如圖4所示。

3.3.1 大噴泉碼編碼內(nèi)容

如圖4上半部分所示,大噴泉碼負(fù)責(zé)對(duì)源文件的內(nèi)容進(jìn)行編碼。編碼端讀取待存儲(chǔ)的源文件后,按照LT碼編碼算法(算法1)的步驟進(jìn)行編碼。

Figure 4 Coding structure of big and small fountain code model圖4 大小噴泉碼模型編碼結(jié)構(gòu)

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

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

3.3.2 小噴泉碼編碼內(nèi)容

如圖4的下半部分所示,小噴泉碼負(fù)責(zé)對(duì)大噴泉碼編碼數(shù)據(jù)的比特?cái)?shù)L進(jìn)行編碼。與大噴泉碼相同,小噴泉碼在對(duì)參數(shù)L編碼之前,先對(duì)其生成一個(gè)固定比特?cái)?shù)的哈希值,再將哈希值拼接在參數(shù)L的末尾。哈希值同樣用來(lái)自校驗(yàn),確保解碼出的數(shù)據(jù)與編碼時(shí)的相同。

小噴泉碼編碼數(shù)據(jù)劃分成的分組長(zhǎng)度相對(duì)較短,一般為1 bit,也可根據(jù)具體場(chǎng)景進(jìn)行調(diào)整。小噴泉碼編碼數(shù)據(jù)的比特?cái)?shù)固定,因此總被劃分為固定數(shù)量的分組,再按照算法1的步驟進(jìn)行編碼。大噴泉碼與小噴泉碼編碼同一個(gè)數(shù)據(jù)分組時(shí),使用同一個(gè)隨機(jī)種子及度分布函數(shù)進(jìn)行獨(dú)立編碼。在實(shí)際應(yīng)用中,編碼輸出的DNA序列數(shù)量通常遠(yuǎn)大于小噴泉碼編碼的原始數(shù)據(jù)分組數(shù),因此小噴泉碼數(shù)據(jù)具有足夠大的冗余可以保證編碼存儲(chǔ)的信息能被解碼端成功解碼。

無(wú)論大噴泉碼還是小噴泉碼,都保留了傳統(tǒng)噴泉碼應(yīng)對(duì)丟刪錯(cuò)誤的特性,即在有部分?jǐn)?shù)據(jù)隨機(jī)丟失的情況下都能從剩余編碼數(shù)據(jù)中恢復(fù)出原始數(shù)據(jù)。

4 大小噴泉碼編解碼

4.1 DNA規(guī)避序列限制問(wèn)題

在DNA序列合成與測(cè)序過(guò)程中,由于生化實(shí)驗(yàn)上的限制,并非所有編碼生成的DNA序列都可用,如GC含量高、均聚物長(zhǎng)(如AAAAAA…)或含有酶切位點(diǎn)的DNA序列是不可取的,因?yàn)樗鼈兒茈y合成且容易出現(xiàn)測(cè)序錯(cuò)誤[20,21]。為了保證編碼數(shù)據(jù)轉(zhuǎn)換成的DNA序列能夠滿足生化實(shí)驗(yàn)上的要求,在編碼輸出序列時(shí)要考慮DNA規(guī)避序列的限制。如何避免規(guī)避序列的影響,本文基于大小噴泉碼提供了2種編碼方案。

4.1.1 丟刪編碼

噴泉碼主要應(yīng)用在刪除信道場(chǎng)景中,其良好的特性能保證即使在有數(shù)據(jù)丟失的情況下,只要收集到足夠數(shù)量的數(shù)據(jù),依然有很高的概率能成功解碼。因此,當(dāng)編碼生成的DNA序列中出現(xiàn)了需要規(guī)避的子序列時(shí),可直接將該條序列丟棄。噴泉碼可以生成無(wú)限數(shù)量的編碼數(shù)據(jù),丟棄部分?jǐn)?shù)據(jù)不會(huì)對(duì)編解碼過(guò)程產(chǎn)生影響。

該方案操作簡(jiǎn)單,但當(dāng)規(guī)避序列需要丟棄大量序列時(shí),會(huì)導(dǎo)致隨機(jī)種子的比特空間有較大的膨脹。例如,當(dāng)需要編碼輸出1 000條DNA序列時(shí),在無(wú)規(guī)避序列的情況下只需10 bit的種子空間;而當(dāng)規(guī)避序列特別多或需要規(guī)避一些出現(xiàn)頻率較高的子序列時(shí),可能至少需要生成100 000條序列才能產(chǎn)生1 000條合格的序列,而此時(shí)隨機(jī)數(shù)種子的空間就變?yōu)榱?7 bit,這會(huì)導(dǎo)致原本存放大噴泉碼編碼數(shù)據(jù)的帶寬被占用。

4.1.2 MRC算法編碼

編碼端可采用一些編碼算法,在將編碼數(shù)據(jù)轉(zhuǎn)換成DNA序列時(shí)直接規(guī)避掉不希望出現(xiàn)的子序列,例如Liu等人[22]提出的MRC(Mixed Radix Coding)算法。MRC算法不是利用四進(jìn)制方式編碼DNA序列,而是利用變進(jìn)制的思想,在把編碼數(shù)據(jù)轉(zhuǎn)換成DNA序列的過(guò)程中,結(jié)合用戶輸入的規(guī)避序列,通過(guò)不斷地進(jìn)行取模、除法操作直接生成不含規(guī)避序列的DNA序列。該算法的優(yōu)點(diǎn)是編碼端不會(huì)因規(guī)避序列而大量丟棄生成的DNA序列,一旦產(chǎn)生足夠數(shù)量的序列即可結(jié)束編碼;缺點(diǎn)是DNA存儲(chǔ)介質(zhì)的不均勻性會(huì)導(dǎo)致MRC算法編碼出的DNA序列是不定長(zhǎng)的。超過(guò)長(zhǎng)度的DNA序列會(huì)被丟棄,因此為了保證大多數(shù)MRC算法轉(zhuǎn)化的序列長(zhǎng)度小于或等于規(guī)定的長(zhǎng)度,需要適當(dāng)?shù)乜s短源文件劃分?jǐn)?shù)據(jù)分組的比特?cái)?shù)l。

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

2種方案編碼生成的數(shù)據(jù)分組結(jié)構(gòu)示意圖如圖5所示。

Figure 5 Encoded packet structures of two schemes圖5 2種方案的編碼分組結(jié)構(gòu)

圖5a為丟刪編碼方案的分組結(jié)構(gòu)示意圖,其特點(diǎn)是所有數(shù)據(jù)分組中的大噴泉碼數(shù)據(jù)及其對(duì)應(yīng)的DNA序列都是等長(zhǎng)的;所有分組最后固定的1 bit為小噴泉碼數(shù)據(jù),小噴泉碼編碼數(shù)據(jù)量等于總編碼分組數(shù)量。圖5b為MRC算法編碼方案的分組結(jié)構(gòu)示意圖,其特點(diǎn)是所有數(shù)據(jù)分組中的大噴泉碼數(shù)據(jù)是等長(zhǎng)的,但轉(zhuǎn)換成的DNA序列是不定長(zhǎng)的;對(duì)那些長(zhǎng)度較短的DNA序列利用小噴泉碼數(shù)據(jù)進(jìn)行填充使其都變?yōu)榈乳L(zhǎng)的,小噴泉碼編碼數(shù)據(jù)與總分組數(shù)目之間的關(guān)系不固定。

4.2 大小噴泉碼模型編碼

噴泉碼編碼出的每個(gè)數(shù)據(jù)分組都有一個(gè)唯一對(duì)應(yīng)的隨機(jī)數(shù)種子。解碼端使用與編碼端相同的隨機(jī)算法,即可根據(jù)隨機(jī)種子恢復(fù)出編碼數(shù)據(jù)的度及參與編碼的原始分組編號(hào)等信息,因此隨機(jī)種子也需要隨編碼數(shù)據(jù)一起傳遞給解碼端。

由于編碼文件的大小不固定,或用戶對(duì)同一文件有不同的編碼DNA序列長(zhǎng)度、數(shù)量要求時(shí),會(huì)導(dǎo)致隨機(jī)種子的比特空間有較大變化。例如,將同一個(gè)文件編碼成500條DNA序列,只需9 bit的種子空間,而編碼成10 000條序列至少需要14 bit的種子空間。為了充分利用有限長(zhǎng)度的DNA序列中的所有空間,大小噴泉碼模型將編碼數(shù)據(jù)中的隨機(jī)數(shù)種子設(shè)計(jì)為動(dòng)態(tài)長(zhǎng)度的形式進(jìn)行嵌入。

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

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

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

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

4.3 大小噴泉碼模型解碼

噴泉碼要求用于解碼的數(shù)據(jù)必須是無(wú)錯(cuò)的。在實(shí)際應(yīng)用中,還需對(duì)噴泉碼編碼生成的DNA序列添加糾錯(cuò)碼用于檢錯(cuò)和糾錯(cuò)。在解碼前先利用糾錯(cuò)編碼挑出所有無(wú)錯(cuò)數(shù)據(jù)。獲得無(wú)錯(cuò)數(shù)據(jù)后,解碼第一步要先確定所有數(shù)據(jù)分組對(duì)應(yīng)的隨機(jī)種子。

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

seedlenstart=max(llower,lbN+1)

(6)

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

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

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

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

大噴泉碼解碼成功后,從解碼出的數(shù)據(jù)末尾截取與編碼端約定長(zhǎng)度的比特?cái)?shù)作為哈希值,并進(jìn)行自校驗(yàn)。通過(guò)自校驗(yàn)后再?gòu)奈膊拷厝」潭ǖ淖止?jié)長(zhǎng)作為文件名,再將剩余的數(shù)據(jù)全部寫(xiě)入到文件中進(jìn)行保存,即恢復(fù)出了存儲(chǔ)的源文件。

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

5 仿真實(shí)驗(yàn)與分析

以存儲(chǔ)圖像為例,將圖像分別壓縮至10 KB, 100 KB和200 KB 3種大小進(jìn)行DNA存儲(chǔ)仿真實(shí)驗(yàn)。測(cè)試程序用C語(yǔ)言編寫(xiě)。

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

Table 1 Coding experiment information表1 編碼實(shí)驗(yàn)信息

5.1 仿真實(shí)驗(yàn)測(cè)試

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

5.1.1 丟刪編碼方案實(shí)驗(yàn)

丟刪編碼方案對(duì)3幅不同大小的圖像進(jìn)行編碼時(shí)產(chǎn)生的數(shù)據(jù)如表2所示。

Table 2 Experimental results of drop-and-delete encoding 表2 丟刪編碼方案編碼實(shí)驗(yàn)結(jié)果

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

模擬DNA分子在復(fù)制、存儲(chǔ)、測(cè)序時(shí)因變質(zhì)而丟失的過(guò)程,即對(duì)3幅圖像編碼產(chǎn)生的DNA序列隨機(jī)刪除其中50%的數(shù)據(jù),用剩余的數(shù)據(jù)進(jìn)行解碼,重復(fù)100次實(shí)驗(yàn)。3個(gè)樣本剩余的用于解碼的DNA序列數(shù)量分別為500,3 000和6 000,此時(shí)冗余率分別為252.1%,114.3%和114.2%。解碼過(guò)程產(chǎn)生的數(shù)據(jù)如表3所示。

Table 3 Experimental results of drop-and-delete decoding 表3 丟刪編碼方案解碼實(shí)驗(yàn)結(jié)果

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

5.1.2 MRC算法編碼方案實(shí)驗(yàn)

使用MRC算法編碼方案測(cè)試時(shí),為了保證大多數(shù)編碼生成的DNA序列長(zhǎng)度小于或等于規(guī)定的長(zhǎng)度,對(duì)源文件的數(shù)據(jù)分組長(zhǎng)度進(jìn)行了適當(dāng)?shù)膲嚎s,編碼過(guò)程產(chǎn)生的數(shù)據(jù)如表4所示。

Table 4 Experimental results of MRC algorithm encoding 表4 MRC算法方案編碼實(shí)驗(yàn)結(jié)果

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

與丟刪編碼方案做法相同,從3幅圖像編碼生成的DNA序列中,隨機(jī)刪除50%的數(shù)據(jù),用剩余的DNA序列分別進(jìn)行解碼測(cè)試,重復(fù)100次實(shí)驗(yàn)。解碼過(guò)程的實(shí)驗(yàn)結(jié)果如表5所示。

Table 5 Experimental resultsof MRC algorithm decoding 表5 MRC算法方案解碼實(shí)驗(yàn)結(jié)果

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

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

5.2 性能分析

5.2.1 解碼成功率分析

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

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

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

5.2.2 解碼時(shí)間效率分析

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

Figure 9 Comparison of average decoding time between big and small fountaincode and traditional LT code圖9 大小噴泉碼與傳統(tǒng)LT碼平均解碼時(shí)間對(duì)比

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

5.2.3 數(shù)據(jù)存儲(chǔ)密度分析

在數(shù)據(jù)存儲(chǔ)密度方面,由于MRC算法編碼的不均勻性,可能會(huì)導(dǎo)致編碼生成的DNA序列超過(guò)規(guī)定長(zhǎng)度。對(duì)該方案的數(shù)據(jù)分組長(zhǎng)度進(jìn)行適當(dāng)壓縮,讓更多MRC編碼生成的DNA序列小于或等于規(guī)定的長(zhǎng)度,但因此會(huì)降低存儲(chǔ)密度。在相同的實(shí)驗(yàn)參數(shù)下,3種方案的存儲(chǔ)密度對(duì)比如圖10所示(圖10中縱坐標(biāo)存儲(chǔ)空間利用率即為存儲(chǔ)密度)。

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

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

實(shí)驗(yàn)結(jié)果表明,本文提出的大小噴泉碼模型能有效降低關(guān)鍵參數(shù)K傳輸?shù)膸?實(shí)現(xiàn)了以較低的帶寬消耗傳輸一個(gè)關(guān)鍵參數(shù)的目的。

6 結(jié)束語(yǔ)

本文針對(duì)DNA存儲(chǔ)應(yīng)用場(chǎng)景下噴泉碼中關(guān)鍵參數(shù)K的傳遞問(wèn)題,設(shè)計(jì)了一種大小噴泉碼模型。該模型中的小噴泉碼作為帶外信道負(fù)責(zé)向解碼端傳遞一些大噴泉碼解碼過(guò)程需要的關(guān)鍵參數(shù),并且在每個(gè)編碼數(shù)據(jù)分組中,小噴泉碼數(shù)據(jù)降低到了1 bit,有效壓縮了關(guān)鍵參數(shù)傳輸?shù)膸?提高了空間利用率。

在未來(lái)的工作中,大小噴泉碼模型需要進(jìn)一步優(yōu)化的方向是如何有效傳遞隨機(jī)種子比特?cái)?shù)信息。目前模型中隨機(jī)種子是根據(jù)實(shí)際計(jì)算的長(zhǎng)度動(dòng)態(tài)嵌入到數(shù)據(jù)分組中的,而解碼時(shí),解碼端無(wú)法獲得隨機(jī)種子比特?cái)?shù)信息,只能通過(guò)試探的方法,借助小噴泉碼的哈希自校驗(yàn)來(lái)確定種子比特?cái)?shù)。這種方法的缺點(diǎn)是需要進(jìn)行多次試探,會(huì)降低時(shí)間效率,未來(lái)可以進(jìn)一步優(yōu)化以提高時(shí)間效率。