DNA存储场景下的大小喷泉码模型设计.pdf
《DNA存储场景下的大小喷泉码模型设计.pdf》由会员分享,可在线阅读,更多相关《DNA存储场景下的大小喷泉码模型设计.pdf(11页珍藏版)》请在咨信网上搜索。
1、 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嵌入在每一个编码数据分组中进行传递,但这种做法会严重浪费信道的带宽。针对上述问题,提出了一种大小喷泉码模型,通过增加小喷泉码这一带外信道来优化关键参数的传递。小喷
2、泉码将每个编码分组中有关参数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
3、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
4、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
5、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
6、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
7、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
8、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
9、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
10、 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是生物体用于存储遗传信息的载体,同样具有存储数字信息的能力。研究表
11、明,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
12、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存储有广阔的应
13、用前景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存储领域,提升
14、了使用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值才能进行解
15、码,因此在编码端与解码端之间需要额外的信道资源来传递关键参数K。在实际应用中可将K直接嵌入到所有编码分组中来进行传递。但是,这种做法有极大的冗余,严重浪费信道的带宽。另一种做法是在编码端和解码端中将K设为固定值。但是,这种做法忽略了源文件大小、数据分组长度及数据分组数目之间的关系,不适用于实际的D NA存储应用场景。基于上述问题,本文以D NA存储应用为背景,提出了一种大小喷泉码模型。一方面大喷泉码用来编码存储源文件的内容;另一方面通过增加小喷泉码带外信道来优化关键参数K的传递,提高了带宽的利用率,同时K可取任意值,摆脱了源文件大小等的限制。大喷泉码与小喷泉码互相结合,共同实现对源文件的编码存
16、储。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码是一种无速
17、率码,可产生无限的编码数据,具有简单的编译码方法、较小的译码开销和编译码复杂度。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)在实际应用中,编码数据的抽样往往无法精确符合理想孤波分布,总存在一些波动和误差,
18、从而出现解码时度为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崔竞
19、松等: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
20、 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 利用接收到的所有数据分组头部的
21、随机 种子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所示。
22、图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
23、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目前的二代合成芯片高通量合成的寡
24、核苷酸池(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的文件,编码端将源文件划分成的数据分组
25、数目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所示。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DNA 存储 场景 大小 喷泉 模型 设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。