DNA存储场景下的大小喷泉码模型设计.pdf

D N A存储场景下的大小喷泉码模型设计*崔竞松1,2,蒋昌跃1,2,郭 迟3(1.武汉大学国家网络安全学院,湖北 武汉 4 3 0 0 7 2;2.武汉大学空天信息安全与可信计算教育部重点实验室,湖北 武汉 4 3 0 0 7 2;3.武汉大学卫星导航定位技术研究中心,湖北 武汉 4 3 0 0 7 2)摘 要:在D NA存储等应用场景中,传统喷泉码算法需要占用额外信道资源将源文件分组数目K传递给解码端。在实际应用中,虽然可以将K嵌入在每一个编码数据分组中进行传递,但这种做法会严重浪费信道的带宽。针对上述问题,提出了一种大小喷泉码模型,通过增加小喷泉码这一带外信道来优化关键参数的传递。小喷泉码将每个编码分组中有关参数K所占用空间的粒度降至1 b i t,有效减少了带宽资源的消耗。此外,小喷泉码还能适应由于D NA存储介质不均匀所导致的编码序列不定长的限制条件,一定条件下甚至可以完全不占用额外信道带宽。关键词:D NA存储;喷泉码;L T码;规避序列中图分类号:T P 3 0 9文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 4.0 1.0 0 8A l a r g e a n d m i n i f o u n t a i n c o d e m o d e l i n D N A s t o r a g eC U I J i n g-s o n g1,2,J I ANG C h a n g-y u e1,2,GUO C h i3(1.S c h o o l o f C y b e r S c i e n c e a n d E n g i n e e r i n g,Wu h a n U n i v e r s i t y,W u h a n 4 3 0 0 7 2;2.K e y L a b o r a t o r y o f A e r o s p a c e I n f o r m a t i o n S e c u r i t y a n d T r u s t e d C o m p u t i n g,M i n i s t r y o f E d u c a t i o n,W u h a n U n i v e r s i t y,Wu h a n 4 3 0 0 7 2;3.G N S S R e s e a r c h C e n t e r,W u h a n U n i v e r s i t y,W u h a n 4 3 0 0 7 2,C h i n a)A b s t r a c t:I n a p p l i c a t i o n s c e n a r i o s s u c h a s D NA s t o r a g e,t h e t r a d i t i o n a l f o u n t a i n c o d e a l g o r i t h m m u s t t r a n s m i t t h e n u m b e r K o f s o u r c e f i l e p a c k e t s t o t h e d e c o d e r t h r o u g h a n a d d i t i o n a l c h a n n e l.I n p r a c t i c a l a p p l i c a t i o n s,a l t h o u g h K c a n b e e m b e d d e d i n e a c h c o d e d d a t a p a c k e t t o t r a n s m i t t h i s k e y p a r a m e t e r,t h i s m e t h o d w i l l s e r i o u s l y w a s t e t h e c h a n n e l s b a n d w i d t h.A i m i n g a t t h e a b o v e p r o b l e m s,a l a r g e a n d m i n i f o u n t a i n c o d e m o d e l i s p r o p o s e d,w h i c h o p t i m i z e s t h e t r a n s m i s s i o n o f c r i t i c a l p a r a m e t e r s b y a d d i n g t h e o u t-o f-b a n d c h a n n e l o f t h e m i n i f o u n t a i n c o d e.T h e m i n i f o u n t a i n c o d e r e d u c e s t h e g r a n u l a r i t y o f t h e s p a c e o c c u p i e d b y t h e c r i t i c a l i n f o r m a t i o n a b o u t t h e p a r a m e t e r K i n e a c h c o d i n g g r o u p t o 1 b i t,e f f e c t i v e-l y r e d u c i n g t h e c o n s u m p t i o n o f b a n d w i d t h r e s o u r c e s.I n a d d i t i o n,t h e m i n i f o u n t a i n c o d e c a n a l s o a d a p t t o t h e r e s t r i c t i o n o f t h e i n d e f i n i t e l e n g t h o f t h e c o d i n g s e q u e n c e c a u s e d b y t h e i n h o m o g e n e i t y o f t h e D NA s t o r a g e m e d i u m.U n d e r c e r t a i n c o n d i t i o n s,i t c a n n o t e v e n o c c u p y a d d i t i o n a l c h a n n e l b a n d w i d t h a t a l l.K e y w o r d s:D NA s t o r a g e;f o u n t a i n c o d e;L T c o d e;a v o i d a n c e s e q u e n c e1 引言据估计,到2 0 2 5年 全 球 数 据 总 量 将 达1 6 3 Z B,而当前主流存储介质的生产已不堪重负1,2。D NA是生物体用于存储遗传信息的载体,同样具有存储数字信息的能力。研究表明,D NA信息存储密 度 可 以 达 到1 01 9 b i t/c m3,是 硬 盘 的1 06*收稿日期:2 0 2 2-1 0-2 7;修回日期:2 0 2 3-0 4-1 0基金项目:国家重点研发计划(2 0 2 2 Y F B 3 9 0 3 8 0 1);湖北省重大科技专项(2 0 2 2 AAA 0 0 9)通信地址:4 3 0 0 7 2 湖北省武汉市武汉大学国家网络安全学院A d d r e s s:S c h o o l o f C y b e r S c i e n c e a n d E n g i n e e r i n g,W u h a n U n i v e r s i t y,W u h a n 4 3 0 0 7 2,H u b e i,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 6卷第1期2 0 2 4年1月 V o l.4 6,N o.1,J a n.2 0 2 4 文章编号:1 0 0 7-1 3 0 X(2 0 2 4)0 1-0 0 7 2-1 1倍3,4。D NA作为数据的存储介质,具有密度大、能耗低、寿命长等优点,因此D NA存储有广阔的应用前景5。目前已经提出了多种D NA存储方案。2 0 1 2年哈佛大学的C h u r c h等人6利用二进制转换首次实现在体外将6 5 9 K B的数据存储进D NA分子中,但该方案引入的冗余过多。2 0 1 3年G o l d m a n等人7利用哈夫曼编码、四倍重叠法、三进制编码将7 3 9 K B的信息存入D NA中。2 0 1 5年G r a s s等人8将R S(R e e d-S o l o m o n)纠错应用于D NA存储,实 现 了8 3 K B信 息 的 无 错 误 存 储 和 读 取。2 0 1 6年B l a w a t等人9将“前向纠错码”引入D NA存储领域,提升了使用D NA分子进行数据存储的可靠性。同年B o r n h o l t等人1 0设计实现了D NA存储体系中数据的“随机访问”。2 0 1 7年哥伦比亚大学的E r l i c h等人1 1将“喷泉码”引入到D NA编码体系中,称之为“D NA喷泉”,实现了较高的数据存储密度,降低了冗余和成本。2 0 2 0年K o c h等人1 2将喷泉码运用于信息存储,并提出了“D NA信息可存储万物”的概念D o T(D NA-o f-T h i n g s)。过往研究中使用的喷泉码算法在D NA存储等应用场景中存在一定的不足:编码端将源文件划分成K个分组进行编码,而解码端需要确定参数K值才能进行解码,因此在编码端与解码端之间需要额外的信道资源来传递关键参数K。在实际应用中可将K直接嵌入到所有编码分组中来进行传递。但是,这种做法有极大的冗余,严重浪费信道的带宽。另一种做法是在编码端和解码端中将K设为固定值。但是,这种做法忽略了源文件大小、数据分组长度及数据分组数目之间的关系,不适用于实际的D NA存储应用场景。基于上述问题,本文以D NA存储应用为背景,提出了一种大小喷泉码模型。一方面大喷泉码用来编码存储源文件的内容;另一方面通过增加小喷泉码带外信道来优化关键参数K的传递,提高了带宽的利用率,同时K可取任意值,摆脱了源文件大小等的限制。大喷泉码与小喷泉码互相结合,共同实现对源文件的编码存储。2 喷泉码与L T码喷泉码是一种纠删编码1 3 1 6,最初是针对二进制删除信道B E C(B i n a r y E r a s u r e C h a n n e l)设计的,旨在为大规模数据的传输和可靠广播场景提供一种理想的解决方案。在D NA存储场景下,D NA分子在保存和复制的过程中会发生一定概率的变异甚至片段丢失。由于变异或片段丢失的D NA分子不可再用,相当于丢弃了数据,因此D NA分子存储是一个典型的删除信道。L T码(L u b y T r a n s f o r m c o d e s)是由L u b y1 7在2 0 0 2年提出的第一种实用喷泉码。L T码是一种无速率码,可产生无限的编码数据,具有简单的编译码方法、较小的译码开销和编译码复杂度。L T码将源文件转换为大量较短的信息,这些较短的信息并非源文件的一部分,而是将源文件中的信息通过特定的方式进行运算编码后产生的。接收端收到一定量以上的编码数据就可能成功解码,与收到哪些编码数据无关。2.1 L T码度分布度是指与某一编码数据分组相关联的原始数据分组的数目,通常用d表示。传统L T码的度分布函数是由L u b y首先提出来的理想孤波分布1 7,其表达式如式(1)所示:(d)=1K,d=11d d-1 ,d=2,3,K(1)在实际应用中,编码数据的抽样往往无法精确符合理想孤波分布,总存在一些波动和误差,从而出现解码时度为1的数据断层,导致解码失败。所以,通过修正理想孤波分布,给出更实用的鲁棒孤波分布1 8,其表达式如式(2)所示:(d)=(d)+(d),d=1,2,K(2)其 中,=Kd=1(d)+(d)是 归 一 化 因 子,(d)是式(1)的理想孤波分布,(d)是在理想孤波分布上的修正函数,如式(3)所示:(d)=Sd K,d=1,2,KS-1SKl nSd ,d=KS0,dKS (3)其中,S=cl n(K/)K是度为1的编码数据的近似平均个数,c是一个非负常量,是解码端可接受的解码失败概率上限。2.2 L T码编码设有K个待编码的原始数据分组,L T码的编码算法如算法1所示。37崔竞松等:D NA存储场景下的大小喷泉码模型设计算法1 L T码编码算法输入:K个原始数据分组。输出:编码数据分组。S t e p 1 确定一个唯一的随机种子s e e d,根据式(2)的度分布函数,利用随机种子产生一个随机值d作为编码数据分组的度。S t e p 2 从待编码的K个分组中,利用S t e p 1中的随机种子s e e d,均匀随机地挑选d个不重复的数据分组。S t e p 3 将S t e p 2选出的d个原始数据分组进行异或运算,得到一个数据载荷h。S t e p 4 将随机种子s e e d作为分组头部和数据载荷h拼接,打包形成一个编码分组。S t e p 5 重复S t e p 1S t e p 4,可得到任意数量的编码数据分组。2.3 L T码解码L T码解码是对接收到的NNK 个编码数据进行处理,从中恢复出K个原始数据。传统L T码解码算法通常采用复杂度较低的置信度传播B P(B e l i e f P r o p a g a t i o n)算法,其平均时间复杂度为O Kl n K 。该算法主要是从接收端生成的二分图中,通过信息在校验节点与变量节点之间不断流动消去无用的边,最终恢复出K个变量节点的值。传统L T码解码算法如算法2所示。算法2 传统L T码解码算法输入:编码数据分组。输出:K个原始数据分组。S t e p 1 利用接收到的所有数据分组头部的 随机 种子s e e d,恢复出每个分组对应的度d以及参与编码的原始分组编号信息。S t e p 2 根据S t e p 1恢复的信息,利用编码分组和原始分组间的对应关系建立双向图。S t e p 3 遍历所有编码分组,找出所有度为1的数据分组。若不存在度为1的数据分组,则解码停止,否则恢复对应的原始数据。S t e p 4 将已恢复的数据分组的边从图中释放,并将与它相关联的数据分组与其异或,再将所有参与异或的数据分组度数减1。S t e p 5 重复S t e p 3和S t e p 4,直到解码停止。若K个原始数据全部恢复则解码成功,否则解码失败。B P解码算法的双向图解码过程如图1所示。图1展示了从编码数据1 0 1 1 恢复出原始数据1 0 1 的过程,其中空心圆表示原始数据分组,实心圆表示编码数据分组。2.4 使用喷泉码算法的D N A存储框架使用喷泉码进行D NA存储的框架主要包括3F i g u r e 1 P r o c e s s o f L T c o d e d e c o d i n g 图1 L T码解码过程个部分:源文件编码写入、介质生化存储和解码获取源文件。源文件编码写入是利用喷泉码编码算法将源文件转换成若干条等长的D NA序列。介质生化存储是将源文件编码生成的D NA序列进行生化处理,主要包括D NA分子合成及D NA分子储存。解码获取源文件是从D NA分子中还原出源文件,是编码 写 入 的 逆 过 程。在 解 码 之 前,需 要 先 对D NA分子进行生化实验预处理,包括:P C R(P o l y-m e r a s e C h a i n R e a c t i o n)序列扩增、D NA测序(分析特定D NA片段的碱基序列,获取D NA序列的A,C,G,T排列方式),再进行D NA序列 纠错、D NA序列去重等操作,最后进行喷泉码解码,获取源文件。使用喷泉码算法的D NA存储编解码过程如图2所示。3 面向D N A存储的大小喷泉码3.1 D N A存储场景的局限性知名D NA合成公司TW I S T目前的二代合成芯片高通量合成的寡核苷酸池(D NA文库)中,单条D NA序列的碱基最大个数仅为3 0 01 9。D NA序列合成技术的限制使得用户在进行存储编码之前就需要确定出编码输出D NA序列的长度及条数。目前普遍使用四进制方式编码D NA序列,即按照0 0,0 1,1 0,1 1 与A,C,G,T 的对应关系来实现二进制数据与D NA序列之间的转换。D NA序列长度的限制会影响编码时源文件数据分组长度的划分,从而会导致参数K有较大变化。例如,当规定喷泉码编码输出的单条D NA序列碱基个数为3 0 0时,编码4个文件,大小分别为1 K B,1 0 K B,1 0 0 K B和1 MB的文件,编码端将源文件划分成的数据分组数目K随文件大小变化的情况如47C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)F i g u r e 2 D NA e n c o d i n g a n d d e c o d i n g u s i n g f o u n t a i n c o d e a l g o r i t h m图2 使用喷泉码算法的D NA编解码F i g u r e 3 F i l e s i z e v a r y i n g w i t h K v a l u e图3 文件大小随K值的变化情况图3所示。从图3可以看出,当都按照3 0 0碱基长度进行数据分组时,参数K会随文件长度的增大而明显变化。若在编码端和解码端将K设为定值,则会影响源文件数据分组的长度,进而影响编码数据转换成的D NA序列的长度,显然不适合D NA存储的应用场景,因此有必要将参数K的信息传递给解码端。3.2 小喷泉码设计设源文件的比特数为L,源文件划分的原始数据分组比特数为l,则K的计算如式(4)所示:K=Ll(4)当L不能被l整除时,表示划分的最后一个数据分组不足l比特,需要将其填充为l比特。设最后一个数据分组填充的比特数为n0nl ,则解码时为了能将填充的多余比特去除,解码端需要获取编码端对原数据填充的比特数n。n的计算如式(5)所示:n=Kl-L(5)解码端利用四进制编码将接收到的D NA序列还原成二进制数据即可得知数据分组的比特数l。解码端只要再获取源文件的比特数L,即可由式(4)和式(5)计算出解码所需要的关键参数K和n。所以,要将源文件的比特数L传递给解码端。设编码端和解码端将参数L统一用6 4 b i t的整型表示。如果直接将L拼接在每个编码数据分组的末尾,则解码端从接收到的数据末尾截取固定的6 4 b i t即为L。这种做法简单有效,但会严重浪费信息空间,所有数据分组都拼接相同的6 4 b i t信息会造成极大的冗余。解码端只要成功收到一个数据分组即可获得参数L,而其它数据分组末尾的6 4 b i t将全部失去价值。为了尽量减少参数L的带宽,为大喷泉码留出更多的数据存储空间,本文设计了小喷泉码来对参数L的传输进行优化。3.3 大小喷泉码模型结构大小喷泉码使用了一大一小2个喷泉码对同一个源文件的不同信息分别进行编码,再将2个喷泉码的编码结果合并为一个编码分组进行存储和传输,模型结构如图4所示。3.3.1 大喷泉码编码内容如图4上半部分所示,大喷泉码负责对源文件的内容进行编码。编码端读取待存储的源文件后,按照L T码编码算法(算法1)的步骤进行编码。为了在解码时能百分之百还原出存储的源文件,大喷泉码编码的数据中还包含了源文件的名字及一个哈希值。先将固定长度的文件名拼接在源文件内容之后,再整体生成一个固定长度的哈希值并拼接在最后。将拼接了文件名和哈希值的数据作为源数据输入大喷泉码模型进行编码。哈希值用于自校验解码出的内容与编码时的内容是否相同。模型中编码端与解码端约定文件名与哈希值分别是相同的固定字节长度,这样解码端在解码出数据后,从尾部截取固定长度即可获得哈希值与文件名。大喷泉码将拼接了文件名和哈希值的源数据划分为若干等长且互不重叠的数据分组,再利用随机种子和度分布函数生成度值,最后选择相应的数据分组进行异或运算,源源不断地产生编码分组。3.3.2 小喷泉码编码内容如图4的下半部分所示,小喷泉码负责对大喷57崔竞松等:D NA存储场景下的大小喷泉码模型设计F i g u r e 4 C o d i n g s t r u c t u r e o f b i g a n d s m a l l f o u n t a i n c o d e m o d e l 图4 大小喷泉码模型编码结构泉码编码数据的比特数L进行编码。与大喷泉码相同,小喷泉码在对参数L编码之前,先对其生成一个固定比特数的哈希值,再将哈希值拼接在参数L的末尾。哈希值同样用来自校验,确保解码出的数据与编码时的相同。小喷泉码编码数据划分成的分组长度相对较短,一般为1 b i t,也可根据具体场景进行调整。小喷泉码编码数据的比特数固定,因此总被划分为固定数量的分组,再按照算法1的步骤进行编码。大喷泉码与小喷泉码编码同一个数据分组时,使用同一个随机种子及度分布函数进行独立编码。在实际应用中,编码输出的D NA序列数量通常远大于小喷泉码编码的原始数据分组数,因此小喷泉码数据具有足够大的冗余可以保证编码存储的信息能被解码端成功解码。无论大喷泉码还是小喷泉码,都保留了传统喷泉码应对丢删错误的特性,即在有部分数据随机丢失的情况下都能从剩余编码数据中恢复出原始数据。4 大小喷泉码编解码4.1 D N A规避序列限制问题在D NA序列合成与测序过程中,由于生化实验上的限制,并非所有编码生成的D NA序列都可用,如G C含量高、均聚物长(如AAAAAA)或含有酶切位点的D NA序列是不可取的,因为它们很难合成且容易出现测序错误2 0,2 1。为了保证编码数据转换成的D NA序列能够满足生化实验上的要求,在编码输出序列时要考虑D NA规避序列的限制。如何避免规避序列的影响,本文基于大小喷泉码提供了2种编码方案。4.1.1 丢删编码喷泉码主要应用在删除信道场景中,其良好的特性能保证即使在有数据丢失的情况下,只要收集到足够数量的数据,依然有很高的概率能成功解码。因此,当编码生成的D NA序列中出现了需要规避的子序列时,可直接将该条序列丢弃。喷泉码可以生成无限数量的编码数据,丢弃部分数据不会对编解码过程产生影响。该方案操作简单,但当规避序列需要丢弃大量序列时,会导致随机种子的比特空间有较大的膨胀。例如,当需要编码输出1 0 0 0条D NA序列时,在无规避序列的情况下只需1 0 b i t的种子空间;而当规避序列特别多或需要规避一些出现频率较高的子序列时,可能至少需要生成1 0 0 0 0 0条序列才能产生1 0 0 0条合格的序列,而此时随机数种子的空间就变为了1 7 b i t,这会导致原本存放大喷泉码编码数据的带宽被占用。4.1.2 MR C算法编码编码端可采用一些编码算法,在将编码数据转换成D NA序列时直接规避掉不希望出现的子序列,例如L i u等人2 2提出的MR C(M i x e d R a d i x C o d i n g)算法。MR C算法不是利用四进制方式编码D NA序列,而是利用变进制的思想,在把编码数据转换成D NA序列的过程中,结合用户输入的规避序列,通过不断地进行取模、除法操作直接生成不含规避序列的D NA序列。该算法的优点是编码端不会因规避序列而大量丢弃生成的D NA序列,一旦产生足够数量的序列即可结束编码;缺点是D NA存储介质的不均匀性会导致MR C算法编码出 的D NA序 列 是 不 定 长 的。超 过 长 度 的67C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)D NA序列会被丢弃,因此为了保证大多数MR C算法转化的序列长度小于或等于规定的长度,需要适当地缩短源文件划分数据分组的比特数l。对于MR C算法编码生成的长度小于规定长度的D NA序列,需要将末尾的间隙进行填充,使得所有序列保持等长。为了充分利用部分碱基序列尾部的间隙空间,可利用小喷泉码的编码数据进行填充。这种方案下小喷泉码需在大喷泉码编码之后再进行编码。在将大喷泉码编码数据使用MR C算法编码成D NA序列之后,统计该序列缺损的碱基空间数,此时小喷泉码再利用大喷泉码的随机种子编码出相应数量的数据进行填充。2种方案编码生成的数据分组结构示意图如图5所示。F i g u r e 5 E n c o d e d p a c k e t s t r u c t u r e s o f t w o s c h e m e s图5 2种方案的编码分组结构图5 a为丢删编码方案的分组结构示意图,其特点是所有数据分组中的大喷泉码数据及其对应的D NA序列都是等长的;所有分组最后固定的1 b i t为小喷泉码数据,小喷泉码编码数据量等于总编码分组数量。图5 b为MR C算法编码方案的分组结构示意图,其特点是所有数据分组中的大喷泉码数据是等长的,但转换成的D NA序列是不定长的;对那些长度较短的D NA序列利用小喷泉码数据进行填充使其都变为等长的,小喷泉码编码数据与总分组数目之间的关系不固定。4.2 大小喷泉码模型编码喷泉码编码出的每个数据分组都有一个唯一对应的随机数种子。解码端使用与编码端相同的随机算法,即可根据随机种子恢复出编码数据的度及参与编码的原始分组编号等信息,因此随机种子也需要随编码数据一起传递给解码端。由于编码文件的大小不固定,或用户对同一文件有不同的编码D NA序列长度、数量要求时,会导致随机种子的比特空间有较大变化。例如,将同一个文件编码成5 0 0条D NA序列,只需9 b i t的种子空间,而编码成1 0 0 0 0条序列至少需要1 4 b i t的种子空间。为了充分利用有限长度的D NA序列中的所有空间,大小喷泉码模型将编码数据中的随机数种子设计为动态长度的形式进行嵌入。以丢删编码方案为例,模型按照实际需求计算出一个确定长度的随机种子直接拼接在编码数据分组的头部,尾部的1 b i t存放小喷泉码编码数据,中间剩余的空间全部存放大喷泉码的编码数据。对于输入的源文件,编码端进行填充、拼接文件名、生成哈希值等预处理后,大喷泉码与小喷泉码获得各自待编码的数据,结合用户输入的规避序列及D NA序列长度和数量要求,开始进行编码。以丢删编码方案为基础的大小喷泉码模型的编码算法如算法3所示。算法3 大小喷泉码编码算法输入:源文件。输出:指定长度和数量的D NA序列。S t e p 1 读取源文件,对待编码数据进行填充、生成哈希值等预处理。S t e p 2 从根据实际要求计算得出的随机种子空间中产生一个随机种子。S t e p 3 大、小喷泉码分别利用S t e p 2产生的随机种子各自进行编码。S t e p 4 编码端将随机种子与大、小喷泉码编码数据拼接后的数据转换成D NA序列。S t e p 5 检查生成的D NA序列中是否出现规避序列,出现则丢弃该条D NA序列,否则保留该条D NA序列。S t e p 6 重复S t e p 2S t e p 5,若产生足够数量的D NA序列,则编码结束;若种子空间用完还未编码出足够数量的序列,则种子空间长度加1,重复S t e p 2S t e p 6。模型编码算法的流程如图6所示。4.3 大小喷泉码模型解码喷泉码要求用于解码的数据必须是无错的。在实际应用中,还需对喷泉码编码生成的D NA序列添加纠错码用于检错和纠错。在解码前先利用纠错编码挑出所有无错数据。获得无错数据后,解码第一步要先确定所有数据分组对应的随机种子。模型编码时随机种子以动态长度的方式嵌入,但整个编解码过程中并未传递随机种子长度信息。77崔竞松等:D NA存储场景下的大小喷泉码模型设计F i g u r e 6 F l o w c h a r t o f b i g a n d s m a l l f o u n t a i n c o d e e n c o d i n g a l g o r i t h m s图6 大小喷泉码编码算法流程图大小喷泉码模型在解码端通过试探的方式,利用小喷泉码编码数据末尾哈希值的自校验来确定随机种子的长度。小喷泉码编码的数据比特数是固定值,因此被划分为固定数量个原始分组,记为k。解码端每次都先试探解码固定数量的k个小喷泉码数据,并进行哈希自校验确认是否解码成功,若解码失败则种子空间加1后重新试探。试探的过程不能无限进行下去,因此编码端和解码端需要约定好随 机 种 子 比 特 数 的 下 限 值ll o w e r和 上 限 值lu p p e r,则编码端能够编码的D NA序列总数被限定在了2ll o w e r,2lu p p e r 内。假设试探随机种子的起始长度为s e e d l e ns t a r t,解码端接收到的D NA序列数量为N NK ,则式(6)成立:s e e d l e ns t a r t=m a xll o w e r,l b N+1 (6)从式(6)可以看出,从随机种子长度的下限值及根据N计算得出的随机种子长度中选择较大值作为起始值开始试探。大小喷泉码模型的解码算法如算法4所示。算法4 大小喷泉码解码算法输入:D NA序列。输出:源文件。S t e p 1 利用纠错码挑选正确的D NA序列,将D NA序列按照对应方式转换成二进制数据,从所有编码分组数据尾部截取固定比特作为小喷泉码数据。S t e p 2 根据式(6)确定随机种子的起始长度。S t e p 3 按照当前随机种子的比特数,从所有数据头部截取相应长度的随机种子。S t e p 4 利用S t e p 3得到的随机种子及与编码端相同的随机算法和度分布函数尝试小喷泉码解码,并进行小喷泉码尾部哈希值的自校验。S t e p 5 若小喷泉码解码失败或小喷泉码未通过哈希自校验,则随机种子长度加1,重复S t e p 3和S t e p 4。若小喷泉码解码成功,则确定所有编码分组的随机种子及小喷泉码存储的关键参数L。若在约定的随机种子空间范围内小喷泉码解码失败,则返回解码失败,退出程序。S t e p 6 利用S t e p 5确定的随机种子与参数L进行大喷泉码解码,返回大喷泉码解码结果。大小喷泉码模型解码算法流程如图7所示。F i g u r e 7 F l o w c h a r t o f b i g a n d s m a l l f o u n t a i n c o d e d e c o d i n g a l g o r i t h m图7 大小喷泉码解码算法流程图大喷泉码解码成功后,从解码出的数据末尾截取与编码端约定长度的比特数作为哈希值,并进行自校验。通过自校验后再从尾部截取固定的字节长作为文件名,再将剩余的数据全部写入到文件中进行保存,即恢复出了存储的源文件。为了提高解码的成功率,大小喷泉码模型的解码算法均使用了置信度传播-最大似然联合译码B PML(B e l i e f P r o p a g a t i o n-M a x i m u m L i k e-L i h o o d)算法2 3。解码时使用B P算法,利用1度的数据先进行线性解码。B P算法平均时间复杂度较低,消耗资源少,可快速解码出大部分的源数据。对那些因缺少1度数据而无法继续解码的剩余数据,解码端87C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)再使用最大似然(M L)解码算法,利用高斯消元求解方程组解码剩余数据,从而有效提高解码成功率。但是,M L算法的时间复杂度比较高,达到了O(K3)。5 仿真实验与分析以存储图像为例,将图像分别压缩至1 0 K B,1 0 0 K B和2 0 0 K B 3种大小进行D NA存储仿真实验。测试程序用C语言编写。实验中设置随机种子比特数的下限为1 0,上限为2 4,因此编码端能够编码的D NA序列数被限制在1 0 2 4,1 6 7 7 7 2 1 6 内,满足实验及应用的需求。设置式(3)中的参数c=0.0 5,=0.0 5。在假设规避序列只有G GAT C C,AAAA 的情况下,以输出3 0 0个碱基长的D NA序列为标准,对4.1节中提出的2种规避序列编码方案进行测试。3幅图像的编码要求信息如表1所示。T a b l e 1 C o d i n g e x p e r i m e n t i n f o r m a t i o n表1 编码实验信息源文件大小/B编码单条D NA序列的碱基数/个编码D NA序列数量/条1 0 2 9 53 0 01 0 0 01 0 2 2 2 83 0 06 0 0 02 0 4 3 4 63 0 01 2 0 0 05.1 仿真实验测试对4.1节提出的2种方案分别进行编解码实验。实验中设置编码端和解码端约定的文件名长度固定为1 0 0 B,哈希值长度固定为1 6 B,因此大喷泉码实际编码的数据为源文件内容再加上1 0 0 B的文件名和1 6 B的哈希值。模型中编码端和解码端都设置参数L为6 4 b i t的整型表示。小喷泉码实际编码的是一个1 9 2 b i t数的数据,其中包括6 4 b i t的L和1 2 8 b i t的哈希值,因此小喷泉码数据总是被固定地划分为1 9 2个分组。5.1.1 丢删编码方案实验丢删编码方案对3幅不同大小的图像进行编码时产生的数据如表2所示。T a b l e 2 E x p e r i m e n t a l r e s u l t s o f d r o p-a n d-d e l e t e e n c o d i n g 表2 丢删编码方案编码实验结果大喷泉码编码数据大小/B数据分组数大喷泉码数据分组长度/b i t随机种子长度/b i t因规避序列丢弃的D NA序列数量/条1 0 4 1 11 4 25 8 71 21 5 6 01 0 2 3 4 41 4 0 05 8 51 49 9 4 42 0 4 4 6 22 8 0 15 8 41 51 9 5 6 8 表2中的大喷泉码数据分组长度为源文件内容划分的分组长度;随机种子长度是基于规避序列丢弃情况编码所需的D NA序列而确定的实际比特数。3幅图像在编码时被划分成的原始数据分组数K分别为1 4 2,1 4 0 0和2 8 0 1,而编码输出的D NA序列数都远高于原始数据分组数,其冗余率分别为6 0 4.2%,3 2 8.6%和3 2 8.4%,可以保证在有部分数据丢失的情况下依然具有较高的解码成功概率。模拟D NA分子在复制、存储、测序时因变质而丢失的过程,即对3幅图像编码产生的D NA序列随机删除其中5 0%的数据,用剩余的数据进行解码,重复1 0 0次实验。3个样本剩余的用于解码的D NA序列数量分别为5 0 0,3 0 0 0和6 0 0 0,此时冗余率分别为2 5 2.1%,1 1 4.3%和1 1 4.2%。解码过程产生的数据如表3所示。T a b l e 3 E x p e r i m e n t a l r e s u l t s o f d r o p-a n d-d e l e t e d e c o d i n g 表3 丢删编码方案解码实验结果用于解码的D NA数量/条小喷泉