奇偶校验的DNA算法

范文一：奇偶校验的DNA算法

奇偶校验的DNA 算法

李汪根1,2，丁永生1，朱莹1，邵世煌1

1 东华大学信息科学与技术学院, 上海 (201620)

2 安徽师范大学数学计算机学院，芜湖（241000）

E-mail： 1

摘要：DNA 计算中会发生诸如变异之类的各种错误。如何发现和纠正这些错误对于DNA 计算来说至关重要。奇偶校验是电子计算机通信中被广泛应用的一种最简单的检错方法。本文研究了DNA 计算机中奇偶校验的实现，以期提高DNA 计算的可靠性。经试验仿真，本文提出的DNA 计算机上奇偶校验实现的算法具有可行性。

关键词：奇偶校验，DNA 计算，有限状态自动机

中图分类号：TP384, TP311.12

1. 引言

分子计算是一种新型的计算方式。DNA 计算是分子计算的一种，DNA 计算中被处理的数据存储在DNA 分子中，数据的处理通过诸如合成，杂交，剪切等基因工程的方法来实现。DNA 计算的最大优点是极大的存储密度和计算的高度并行性。

DNA 分子的一个有趣性质是：特定碱基结合在一起构成碱基对：A 和T 配对；C 和G 配对。这个过程实际上就是促成DNA 片段自组织的杂交或退火反应。自组织这种特性使得识别特定DNA 分子成为可能。另一方面，这种自组织可以被用来完成特定意义上的运算。

以DNA 分子作为计算工具的概念最早由Adleman 博士于1994年提出来[1]。自 1995年以后，DNA 计算国际会议每年召开一次。除此之外，在生物信息学和进化计算等国际会议中也常常出现有关DNA 计算的主题。目前DNA 计算取得了很多研究成果，主要体现在以下三个方面：(1) 解决 NP 完全问题[2,3,4]; (2)实现基本的运算操作，比如：逻辑运算和算术运算

[5,6]; (3) 模仿图灵机的操作[7,8,9]。

正如我们所知，DNA 计算的最大缺点是计算的不可靠性，因为在DNA 计算中会发生各种各样的错误。如何发现并且纠正这些错误对DNA 计算来说是非常重要的。奇偶校验是计算机通信中纠错的最简单方法。本文研究的动机在于研究DNA 计算机中奇偶校验的实现，以便提高DNA 计算的可靠性。

2. 奇偶校验

在计算机通信中，二进制数据经传输、存储等处理后往往会被发生错误 (1变为0或0变为1) 。如何发现并纠正这些错误是通信的基础。解决这类问题的一般方法是增加一些冗余数据。奇偶校验是二进制数据传输中最简单的一种纠错方法，对二进制数据中的单一错误能有效发现。奇偶校验是确定二进制数据中1或0的个数是奇数还是偶数。奇校验是数据同步传输的标准，而偶校验则是数据异步传输的标准。

对于给定的码字，统计其中数字1出现的次数，然后根据校验的类型在码字的末尾添加一个额外的校验位。对于奇校验，如果数字1的个数是奇数，则数字0会被附加在校验位；否则数字1会被附加在校验位。同样，对于偶校验，如果数字1的个数是奇数，则数字1会被附加在校验位；否则数字0会被附加在校验位。例如，有码字0010，因其中数字1的个数是1 本课题得到国家自然科学基金（60474037），教育部新世纪优秀人才支持计划（NCET-04-415），教育部高等学校博士学科点专项科研基金资助课题（20030255009）的资助。

奇数，则对于偶校验，校验位应为1，编码后的码字应为00101。对于接收端来说，如果收到的是00100，因其中数字1的个数是奇数，则接收端会知道这是一个错误的码字。

3. DNA 计算机

DNA 计算的基本思想是：以DNA 链作为信息载体，将原始问题映射成为DNA 分子链（单链、双链或带有粘性末端的混合链），然后按照一定的规则将原始问题的数据运算高度并行地映射成对DNA 分子链的可控生化操作。在生化酶的作用下，完成一系列的生化操作。最后，利用分子生物技术如聚合酶链式反应PCR 、亲和层析、电泳、磁珠分离等，检测所需要的运算结果。因此，DNA 计算可分为四个要素：（1）运算载体。从目前的分子生物计算研究情况来看，主要以DNA 分子进行。（2）运算工具。DNA 计算是利用各种生化酶来完成的，这些生化酶包括诸如连接酶、核酸内切酶、DNA 聚合酶、核酸外切酶等。

（3）生化反应系统。DNA 计算中常用的生化反应包括退火、杂交、连接等。（4）检测系统。用于检测DNA 计算的最后结果，常用的手段包括电泳技术、层析分析技术、分子纯化技术、同位素技术、荧光技术以及激光技术等。

4. DNA 计算机中奇偶校验的实现

4.1 奇偶校验算法

对于输入串S 0= b0b 1b 2 … (b0 , b1, b2 是 0 或 1) ，如果 S 0 的长度大于1，则使S 0= bb 2 …，这里 b=b1⊕b 0。这意味着前两位b 0, b1被它们的异或代替。如果S 0的长度是 1，而其值为0，则意味着输入串中数字1的个数是偶数。另一方面，如果S 0 的长度是1，而其值是1，则意味着输入串中数字1的个数是奇数。奇偶校验的算法如图1所示。

举例来说，输入串S 0=01011的运算过程如图 2所描述。因为当S 0的长度是1的时候，其值为1，因此S 0中数字1的个数是奇数。

图1 奇偶校验算法图2 S0=01011的算法实例

Fig1 the algorithm for parity check Fig2 the instance of S0=01011

4.2 实现奇偶校验的有限状态自动机

上面设计的奇偶校验的算法能用图3所被描述的有限状态自动机来实现。该有限状态自

动机的输入元素是0或1，其初始状态是S 0，终止状态是S 0或S 1，S 0表示数字1的个数是偶数，而S 1 表示数字1的个数是奇数。该有限状态自动机的所有状态转移规则如图4所示。

图3 实现奇偶校验的有限状态自动机图4 状态转移规则 Fig3 The automaton for parity checking Fig4 The transition rules

4.3 有限状态自动机的核苷酸编码

有限状态自动机的输入串中有三个字符{0, 1, t}。这些字母的核苷酸编码彼此互不相同。这里，编码采用6个碱基对的DNA 片段表示，输入字符的具体核苷酸编码如图5(a)所示。

为了完成DNA 有限状态自动机的运行，需要两种核酸酶的协作：限制性核酸内切酶和连接酶。这里我们采用内切酶BsmFI 和连接酶T4。BsmFI 的识别位点是 5'- GGGAC-3' ，而其切割位点是 (10,14)。这样符号串经BsmFI 的切割后将产生一个含有4个寡聚核苷酸粘性末端片段。根据BsmFI 切割输入符号的位置的不同，分别表示不同的（状态/符号）组合。这里，如果切割位置在第一个核苷酸之前，则表示状态S 0; 而切割位置在第二个核苷酸之前，则表示状态S 1。

状态转移规则的编码必须含有与输入符号串经BsmFI 切割后形成的粘性末端互补的4-核苷酸粘性末端。这样，在T4 连接酶的作用下，两个互补粘性末端才会杂交，从而形成代表新的状态的符号串。所有状态转移规则的核苷酸编码如图5(b) 所示。

经过一系列的剪切、连接循环后，有限状态自动机将停止运行。在每一个循环，将有一个合适的转移分子其粘性末端与输入串经BsmFI 切割后形成的粘性末端互补，在连接酶T4的作用下将产生新的符号串。形成的新符号串将在下一个循坏中重新被 BsmFI 切割，产生新的粘性末端。设计好的转移分子确保6bps 的输入符号 0 和 1 只在两个不同的位置被 BsmFI 切割，在最左边切割代表状态S 1，在左边第二个位置切割代表状态S 0。内切酶BsmFI 在输入串的下一个切割位置以及表示的有限状态自动机的状态取决于有限状态自动机的当前状态以及转移分子粘性末端前面的碱基对数目。如果没有合适的转移分子其粘性末端与内切酶BsmFI 切割输入符号串形成的粘性末端互补或者内切酶BsmFI 切割到终结符号，有限状态自动机将停止运行。为了检测有限状态自动机停止运行时的终止状态，我们需要设计相应的检测分子。对应于两种终止状态的检测分子如图5(c) 所示。

图5 有限状态自动机的核苷酸编码 (a) 输入符号的编码 (b) 转移分子的编码 (c) 检测分子的编码 Fig5 The nucleotide encoding for finite state automata. (a) Encodings for input alphabets. (b) Encodings for

transition rules. (c) Encodings for detectors.

5. 仿真

为了证明本文工作的可行性，我们以 S 0=01011 为例，给出DNA 计算机上奇偶校验的实现方法。

根据上面4.3节中提到的有限状态自动机的核苷酸编码，合成的初始输入符号串如图6所示。图中从左边起第三个方框中的数字10确保自动机的初始状态是S 0。右边第一个方框中的数字300是为了在用电泳检测最终状态时更清晰。

有限状态自动机的模拟运行如图7所示。首先，初始输入符号串被BsmFI 切割后形成一4-核苷酸粘性末端的片段。然后，在T4连接酶的作用下，将有唯一一个含有互补粘性末端的转移分子与该片段连接。经由一系列切割、连接循环后形成报告分子，经由电泳等检测手段可识别自动机的最终状态。

图6 初始输入符号串

Fig6 the initial input string

6. 结论

本文我们提出了DNA 计算机中奇偶校验的实现算法。通过核苷酸编码和自动机运行的模拟仿真，证明了该算法的可行性。DNA 计算机中奇偶校验的实现能帮助纠正DNA 计算中发生的错误，提高DNA 计算的可信度。

参考文献

[1] L. M. Adelman. Molecular computation of solutions to combinatorial problems. Science, 1994, 266(11):1021-1024.

[2] Lipton, R. J. DNA solution of hard computational problem. Science, 1995, 268(4):542-545.

[3] Ouyang, Q., Kaplan, P. D., Liu, S. & Libchaber, A. DNA solution of the maximal clique problem. Science, 1997, 278(17):446-449.

[4] Khodor, J. & Gifford, D. K. Design and implementation of computational systems based on programmed mutagenesis. Biosystems, 1999, 52:93-97.

[5] F Guarnieri, M Fliss, C Bancroft. Making DNA add. Science, 1996, 273(7):220-223.

[6] B Yurke, et al. DNA implementation of addition in which the input strands are separate from the operator strands. Biosystems, 1999, 52:165-174.

[7] Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z. & Shapiro, E. DNA molecule provides a computing machine with both data and fuel. Proc. Natl Acad. Sci. USA, 2003, 100:2191–2196.

[8] Y Benenson, T Paz-Elizur, R Adar, E Keinan, Z Livneh, E Shapiro. Programmable and autonomous computing machine made of biomolecules. Nature,2001, 414(22):430-434.

[9] Y Benenson, B Gil, U Ben-Dor, R Adar, E Shapiro. An autonomous molecular computer for logical control of gene expression. Nature, 2004, 429(27):1-6.

[10] Xu Jin, Zhang Lei. DNA computer principle, advances and difficulties (I): Biological computing system and its applications to graph theory. Chinese Journal of Computers. 2003, 26(1): 1-11 (in Chinese).

[11] Ding Yongsheng, Shao Shihuang, Ren Lihong. DNA Computing and Soft Computing. Beijing: Scientific Publishing House, 2002 (in Chinese).

DNA Simulation of Parity Checking

Li Wanggen 1, 2, Ding Yongsheng 1, Zhu Ying 1, Shao Shihuang 1

1 College of Information Sciences and Technology, Donghua University, Shanghai,

China (201620)

2 College of Mathematics and Computer Sciences, Anhui Normal University, Wuhu,

China (241000)

Abstract

There are all kinds of error that would happen in DNA computing, such as mutation. How to discover and correct these errors is very important to DNA computing. Parity checking is a simple and widely used method in the communication of computer, which causes a minimum increase of distance of the binary transmission system. This paper studies the implementation of parity checking in DNA computer, which can help to improve the reliability of DNA computing. We propose an algorithm of parity checking based on DNA computer. The simulation result demonstrates the feasibility of our algorithm.

Keywords: Parity Check, DNA Computing, Finite State Automaton

作者简介：

李汪根（1973-），男，安徽太湖人，博士研究生，从事DNA 计算和生物信息学等研究；丁永生（1967-），男，安徽怀宁人，博士，教授，博士生导师，从事智能系统、网络智能、DNA 计算、人工免疫系统、生物网络结构、生物信息学、数字化纺织服装、智能决策与分析等研究；

邵世煌（1938-），男，江苏苏州人，教授，博士生导师，从事智能控制、网络智能、DNA 计算、生物信息学、数字化纺织服装等研究。

图7 有限状态自动机的仿真

Fig7 the simulation for initial input string

范文二：低密度奇偶校验码及其译码算法实现

维普资讯 http://www.cqvip.com

第ｌ卷８

第２期　

苏州市职业大学学报　

Ｊｕｎｌｏ　ｕｈｕＶｏａｉｎｌＵｎｖｒｉ　ｏｒａ　ｆＳｚｏ　ｃｔａ　ｉｅｓｔｏｙ

２００７年５月　

Ｖ０．８Ｎｏ２１１　．　Ｍａ．２０　ｙ０７

低密度奇偶校验码及其译码算法实现　

张培　

（州市职业大学电子信息工程系，苏江苏苏州２５０）１１４　摘要：根据ＬＰＤＣ码的构造、编码、译码原理，重点论述了在ＭａＷｏｋ公司推出的Ｍｔｂ上的ＬＰｔｒｓｈａｌａＤＣ编译码器　

的算法实现，并给出其与Ｔｒｏ的简单性能对比，出ＬＰ码的发展前景。ｕｂ码指ＤＣ　关键词：ＬＰＤＣ码；编码；译码；Ｍａａ；算法　ｔｂｌ中图分类号：Ｔ９９５文献标识码：Ａ文章编号ｌ０８５７（０７０＿０３ｏ　Ｐ２．　　１０ — ４５２０）２０７一３

０引言　

阵可以采用最大长度线性同余序列（ａｉａＬｎｔＭｘｌｅｇ　ｍ — ｈ

ＬｎａＣｎｒｎａＳｑｅｃ）ｉｒｏｇｅｔ　ｅｕｎｅ产生。ｅ　ｕｉｌ　如上所述一个（√ 训拘正则ＬＰ凡，ＤＣ码由它的校　

低密度奇偶校验码（ＤＣｏ — ｅｓｙＬＰ：ＬｗＤｎｉ　ｔ

ＰｒｙＣｅｋＣｄｓ）Ｇｌｇｒ最早于１６年提　ａｉ— ｈｃ　ｏｅ是ａａｅｔｌ９２

出的一种具有稀疏校验矩阵的分组纠错码，亦称　Ｇｌｅｌｇａａｒ码。之后，Ｔｒｏ码研究巨大成功的带动　在ｕｂ下，Ｍａｋｙ等人重新研究了ＬＰ码，现它是一　ｃａＤＣ发种逼近香农限的新一代高性能纠错码。　ＬＰＤＣ码的特点是易实现，并且系统复杂度低，　应用于采用正交频分复用技术的无线局域网及高速　

验矩阵Ｈ来定义，中ｊｋｋｎ其／（）５中止条件　

复杂度之间达到更好的平衡，又出现了简化的和积　译码算法：最小和算法（ｎＳｍＡｇｉｍ）Ｍｉｕ　ｌｒｈ。和积　　ｏｔ译码算法是一种迭代概率译码算法，

每一轮迭代都　需要对码字中各个比特关于接收码字和信道参数的　后验概率进行估算，因此准确地说和积译码算法是　

种逐比特最大后验概率（Ａ簿法。ＭＰ　本文采用的是Ｌｇｏ域的Ｍ算法，Ｐ是一种基于对　数似然比测度的和积译码算法，该算法的关键是迭代　运算部分的迭代计算后验概率（Ｐ）ＡＰ步骤。对数似然　比测度下的和积译码算法的复杂度为码长的线性函　数，由于引入了对数似然比，乘法运算转化为加法运　算，降低了每轮迭代的计算复杂度和硬件实现难度，　在硬件中的并行实现能够极大地提高译码速度，因此　对数似然比和积译码算法得到广泛认可。该算法适合　

一

伴随式ｃ　０Ｈ或到达最大迭代次数。　

３ＭＡＬ　ＴＡＢ实现　

ＭＴＡＡＬＢ是１８９４年由美国ＭｔＷｏｓ司推　ａｈｒ公ｋ出的荣誉产品。早在二十世纪八十年代中期　ＭＴＡＡＬＢ就曾在我国出现，但真正大规模流行是九　十年代中期以后的事。现在，ＡＬＢ已被从事科　ＭＴＡ

学研究、工程计算的广大科技工作者确认为必须掌　握的计算工具，是可信赖的科技资源之一。因此本文　

采用该软件实现ＬＰＤＣ编解码。限于篇幅，仅以部分　

用ＭＴＡＡＬＢ实现，解码性能较好，复杂度适中。　

解码算法为例。　ＬＰＤＣ码的译码时除了中（函数的计算外，ｘ）主　要是加法（２）模加运算，以下是校验点更新部分的　

代码：　

ｆｒｊ１ｏ　＝：Ｍ　

具体的译码算法可以分为如下两个步骤：　第一，初始化。　对于高斯噪声信道，初始化比特点　

Ｌ　／　Ｑ＝仃

其中Ｌ表示比特更新值，／ＱＹ表示接受到的信　

息比特，表示噪声方差。　　

ｂ＝ｎ（（：＝）ｉｆｄＨｊ）０；ｔｉ，一　ｏ　＝：ｎｔｂｔｆｒｉｌｅｇ（ｉ　ｌｈ）ｔｍｂｔｎ（ｉ＝ｉｉ）ｅ＝ｉｆｄｂｔｂｔ）；（ｉ￣（）　

第二，迭代运算。　定义Ｌ　：ｏＰ（Ｆ０／），Ｐｃ　／）（）ｌｃ＝ｇ（Ｃ　　）（　Ｆ１　）　

＝　

ａａｐｏ（ｇ（ｑｊｅ）；ｌ＝ｒｄｓｎＬ（ｔｍ）　ｆｉ，）

％

．　

（１ ‘ ／　　）ｐ

ｂｔ＝　ｔｈｐｏ（ｎ（ｂ（ｑｊｅ）２）；ｅａ２ａｎ（ｒｄｔｈａｓ（ｔｍ．））ａａＬ，／）　

其中ｐ　（Ｆ　）＝１ｅＦｐｃ１（＋　

时发送是１的概率。　（）校验点更新　１

）表示接受为　

ｂｔ＝ｌ（ｎ（ｍ（ｌ（ｎ（ｓｑｊｅ）ｅａ－ｏｔｈｓ－ｏｔｈａ（（ｔｍ）ｇａｕｇａｂＬ，．　

／）／）＝））！２；）　Ｌ（ｂ（）ａａｂｔ；ｒ，ｉｉ＝ｌ　ｅ　ｊｔ）ｆａ

ｅｄｎ　ｅｄｎ　

定义Ｌｑ，ｒｉ）＝ｌ　（）（）ｏｇ（Ｏ　Ｉ）为校验　的　

更新值，传递给比特ｂ　　。记函数　）一ｏｔｈｌ＝ｚ（）ｅ）＝ｌａ　／ｇｎ２　ｅ／　１））　１（　

令ａｓｎＬ（）￣ｉ（ｑｉ）是（ｑｉ）的符号　．ｇ＝ｊＬ（）ｊ

（：校验点的数目）注Ｍ：　以下是比特点更新部分的代码：　

ｏ　ｉ：ｆｒ＝ｌＮ　

￣．ｂ（ｑｉ）ｏａｓＬ（）是（ｑｉ）的绝对值　＝ｉＬ（）ｊＬ（）（　刍　［　ｒｉｎｊ＝－） ∑ 合，　ｉ】Ｅ＼）），０ｉ　　

ｃｅｋｎ（（ｉ＝）ｈｃ－ｄＨ：）ｏ；￣，一　

表示与第　个ｃｅｋｈｃ节点相连的比特节点的集　

Ｅ＼表示该集合中不包含第ｉ　ｉ个比特节点　的其它元素。　（）比特点更新　２

Ｌ（＝ＱＯｓｍ（ｒｈｃ，）Ｑ１Ｌ（＋ｕＬ（ｅｋｉ；）ｃ）　

ｅｄｎ　

４ＤＣ码与Ｔｒｏ码的性能比较　　ＬＰｕｂ

Ｌ（）＝Ｌｃ＋ ∑ ｒ　ｉｑｉｊ（）　（，　，），（　　＼）ＪＥｔ　　ｃ

式中Ｃ表示与第ｉｂ节点相连的ｃｅｋ节　　个ｉｔｈｃ

Ｔｒｏ又叫做并行级联卷积码，由ＣＢｒｕｕ码ｂ．ｅｏ　ｒ等人在１９年首次提出。Ｔｒｏ９３ｕｂ码编码器通过交织　器把两个递归系统卷积码（Ｓ）ＲＣ并行级联，对校验　位采取不同的删除方式来得到各种不同速率的　

点的集合　ＥＡ『　－ｃ表示该集合中不含第　个ｃｅｋｈｃ　

— —

７ — ４ — 　

维普资讯 http://www.cqvip.com

２０年第２０７期　

张培：低密度奇偶校验码及其译码算法实现　

Ｔｒｏ；解码部分由两个软输入软输出的子译码　ｕｂ码器（ＩＯ采用多级级联结构组成。Ｔｒｏ通过对　ＳＳ）ｕｂ码子码的伪随机交织实现大约长度的编码，具有接近　

的突发误码情况下，ＤＣＬＰ码有更优良的性能；在编码　器和译码器中不需要交织等等。因此可以说，ＤＣＬＰ　码是迄今为止纠错码理论界所发现的编解码复杂度　可接收的性能最好的纠错码之一。　

５结论　

随机编码的特性，同时采用迭代算法使译码复杂度　

达到中等水平。Ｔｒ码

在低信噪比条件下性能非　ｕｏｂ

常优越，但是在高信噪比情况下性能却有所下降，原　

因是它的码字间的最小欧式距离较小，误码率曲线　

随着译码算法的性能越接近香农限，它的改进　难度也越来越大，在未来的研究中，如何提高ＬＰ　ＣＣ码译码性能，如何降低译码复杂度，以及如何在这两　者间找到更好的平衡点将是研究的方向。目前，　ＬＰ码已成为第四代移动通信编码技术中的首　ＤＣ

选，使用通用ＤＰ实现ＬＰＳ来ＤＣ的编码、译码也是　

一

在误码率低于某个值的时候斜率突然减小，出现所　谓的 “ 板效应 ”　地。Ｔｒ码的提出为编码研究带来了新的曙光，ｕｂｏ　突破了传统码的约束，真正挖掘了级联码的潜力。在　

Ｔｒｏ码出现以后，ＤＣ码也被重新提出，它和　ｕｂＬＰ

个高效可行的方法。　

Ｔｒｏ码有着相似的构成原则，同样具有接近　ｕｂＳａｎｎ容量极限的性能，ｈｎｏ并且可以实现并行译码。　ＬＰＤＣ码在性能和复杂度方面被认为是Ｔｒ　ｕｂｏ码强有力的竞争者，二者基于相同的思想：约束随机码　参考文献：　

［】ＧＬＡＥ　　．１ｄｎｉ　ａｉ－ｈｃ　ｃｄｓＭ．１ＡＬＧＲＲＧｏｗ－ｅｓｙｐｒｙｃｅｋｏｅ［】ｔｔ　

Ｃａｒｇ，ｓ：ＴＰｅｓ，９３　ｍｂｉｅＭａｓＭＩ　ｒｓ１６．ｄ

集合和迭代解码算法。最近对ＬＰＤＣ码设计的改进和　

硬件的实现，使其在性能和复杂度方面都能与Ｔｒ　ｕｂｏ码媲美，甚至超越Ｔｒｏ码。现已经证明当分组长度　ｕｂ

［】ＭＡＫＹＤＪＣＧｏ　ｒｒＣｒｃｎ　ｏｅ　ａｅ　ｎ２ＣＡ　　　．ｏｄＥｒ　ｏｒｔｇＣｄｓＢｓｄｏ　ｏｅｉＶｅ　ＳａｅＭａ　ｉｓ【．ＩＥ　Ｔａｓｎｎｒｔｎｒｐｒ　ｔｒｅＪＥＥｒｎ　ｏ　Ｉｆｍａｏ　ｙｓｃ】ｏｉ

Ｔｅｒ，９，５２３９４１ｈｏ１９（）：－３．ｙ９４９　

［ＴＭＡ　ＪＲｃａｄｏ　ａｄＲｄｇｒＬＵｂｎｅ３ＨＯＳ．ｉｈｒｓｎｎ　ａｉ　．ｒａｋ．】ｅ　

Ｅｆｉｎ　Ｅｃｄｎ　ｆＬｗ－ｎｉ　Ｐｒｔ－ｅｋｄｅ　ｆｃｅｔｎｏｉｇｏ　ｏＤｅｓｔａｙ－ｉｙｉＣｈｃ　Ｃｏａ

的限制条件为无穷大时，码率为１／２的ＬＰ码的　ＤＣ性能可在香农限００５Ｂ以内可靠通信若分组长度　

．４ｄ０为１　０该码的性能在离香农限０ｄ．Ｂ以内其误码率　４０为１　。而ＬＰＯＤＣ码迭代解码算法的复杂度远低于　Ｔｒｕｂｏ码并且现以证明ＬＰ码编码器的复杂度低　ＤＣ于解码器的复杂度。此外ＬＰＤＣ码优于Ｔｒｏｕｂ码的其　

它特点是：ＤＣＬＰ码可以方便的任意改变码率和改变　码长进行编解码不必向Ｔｒｏｕｂ码那样采用打孑方法　Ｌ改变码率牺牲了性能；ＤＣ没有不可检测错误，ＬＰ也　

［．ＩＥ　Ｔａｓｎｎｏａｏ　Ｔｅｒ，２０，７（）ＪＥＥｒ　ｏ　Ｉｒｔｎｈｏ】ｎｆｍｉｙ０１４２：　

３９４１９－３．　

［４】张志涌，彦琴，．ＴＡ徐等ＭＡＬＢ教程一于６Ｘ版本［．基．Ｍ】北　京：空航天大学出版社，０３航２０．　［】高晟，５杜百川．ＬＰＤＣ码研究及其应用田．电视技术，现代　

２０１１６０．０４，０：０ —１９　

［袁东风，张海霞，宽带移动通信中的先进信道编码技　６】等．

术［．Ｍ】北京：邮电大学出版社，０４２０．　

就是说不存在错误平层，ｕｂＴｒｏ却不然；ＤＣ码的吞　ＬＰ吐量大，更适合高码率应用；在干扰、衰落等原因引发　

（责任编辑：洁）杜　

Ｌｏｄｎｉ　ｒｔ　ｃｅｋＣｏｅ　ｎ　ｔ　ｃｄｎ　ｇｒｔｍ　ｗ－ｅｓｔＰａｉ－ｈｃ　ｄｓａｄＩｓＤｅｏｉｇＡｌｏｉｙ￣ｈ

ＺＨＡＮＧ　Ｐｉｅ　

（ｕｈｕＶｃｔｎｌＵｉｅｉ，Ｓｚｏ　１　４ＣｉａＳｚｏ　ｏａｉａｎｖｒｔｕｈｕ２５０，ｈｎ）ｏ　ｓｙ１　

Ａｓｒｃ：Ｔｉｐｐｒｆｔ　ｎｒｄｃｓｔｅｓｕｔｒ　ｎ　ｅｐｎｉｌ　ｆＬｗＤｎｉ　ａｉ — ｈｃ（ＤＣ　ｂｔａｔｈｓａｅ　ｉｌｉｔｕｅ　ｈ　ｔｃｅａｄｔ　ｒｃｅｏ　ｏ－ｅｓｙＰｒｙＣｅｋＬＰ）　ｓｒｙｏｒｕｈｉｐｓｔｔ

ｃｄｎ　ａｄｄｃｄｎ，ｔｅ　ｄｓｒｅ　ｈｗｏｉｌｍｅｔｉ　ａｇｒｔｍ　ｏ　ＭａｌｂＦｎｌ，ｉｉｅ　ｔｅｏｉｇｎ　ｅｏｉｇｈｎｅｃｂｓｏ　ｔ　ｍｐｅｎ　ｔｉｓｌｏｈｉｎｔ．ｉａｌａｙｔｖｓｈ　　ｇｐｒｒｎｅｃｍｐｒｓｎｂｔｅ　ｔｅＤＰ　ａｄｈｅＴｒｏｃｄｓＡｎ　ｅｂｌａｔｆｔｒ　ｏ　ｅＤＰ　ｉｅｏｍａｃ　ｏａｉｏ　ｅｗｅｎｈ

　ＬＣｎ　ｔ　ｕｂ　ｏｅ．ｆｄｔ　ｒｌｎ　ｕｕｅｆｔ　ＬＣｓｈｉｉｈ　

ｐｉｔｄｏｔｏｎｅ　ｕ．　

Ｋｅ　ｒｓＬＣＣｏｉｇＤｅｏｉｇｙｗｏｄ：ＤＰ；ｄｎ；ｃｄｎ；ＭａｌｂＡｌｏｔｍ　ｔ；ａｇｒｈｉ

一

７ —　５

范文三：基于加权图的准循环低密度奇偶校验码构造算法

2008年10月第35卷

转载请注明出处范文大全网 » 奇偶校验的DNA算法