SMRC：一种用于非均匀存储介质的流式混合进制编解码算法

SMRC： A Streamed Mixed Radix Coding Algorithm for Non-Uniform Storage Media

摘要

DNA序列是一种良好的非均匀数据存储介质，受限于各种生物学条件，现有方案无法高效利用其存储空间，或者计算效率较低。因此，设计了一种流式混合进制编码算法SMRC（Streamed Mixed Radix Coding），该算法能够很好地应对非均匀存储介质中进制分布不均匀的情况，并且通过流式计算，能够在较低的计算复杂度下最大化编码空间的信息熵，从而充分利用DNA等非均匀存储介质的存储空间。分析表明，该算法可以在任意混合进制存储介质上以线性复杂度编码出接近理论最大信息熵的编码结果，且算法流程简洁，易于实现应用，技术优势明显。

Abstract

DNA sequences serve as an effective non-uniform data storage medium. However, existing approaches face challenges in efficiently utilizing this storage medium or suffer from low computational efficiency due to various biological constraints. So, we prosose a novel algorithm called Streamed Mixed Radix Coding (SMRC). This algorithm adeptly addresses the situation of non-uniform radix distribution in non-uniform storage media, such as DNA, and maximizes the information entropy of the coding space at lower computational complexity through streaming computation. This approach fully exploits the storage capacity of non-uniform storage media. Analysis reveals that the algorithm can linearly encode results close to the theoretical maximum information entropy on any mixed radix storage medium. Moreover, the algorithm demonstrates simplicity in its workflow, ease of implementation, and clear technological advantages.

Graphical abstract

关键词

DNA存储 / 非均匀存储 / 熵编码 / 流式编码

Key words

DNA storage / non-uniform storage / entropy coding / streamed coding

0　 引 言

如今，数据存储已成为各行各业不可或缺的重要组成部分，然而传统的数字信息存储介质存在一系列限制，例如存储密度有限、寿命较短、易受干扰等问题^[1]。为了应对这些限制，越来越多的科学家和研究人员开始关注DNA信息存储这一领域。DNA作为生命遗传信息载体，具有极高的信息存储密度和长期稳定性。因此，将数字信息转换为DNA序列进行存储已成为一种备受关注的新兴存储方式^[2-5]。与传统存储介质相比，DNA具有更高的存储密度和更长的存储寿命，能够避免电磁干扰和磁介质衰退等问题。DNA由四种不同的核苷酸组成，而密码子是DNA中三个核苷酸的组合，在生物体中有64种不同的密码子和20种不同的氨基酸，其中部分密码子是同义的，也就是说它们会翻译成相同的氨基酸^[6]。这种特性为在DNA基因片段中嵌入数据提供了可能。然而，正是由于同义密码子受到生化条件的约束，传统编码算法并不适合这类存储载体，使得DNA信息存在例如存储效率低、存储空间无法充分利用等问题，这些问题限制了其在实际应用中的推广和发展^[7]。

熵编码（Entropy Coding，EC）作为一类无损压缩算法^[8]，能够利用数据的统计规律减少数据存储量，从而实现更高效的存储，因此成为了研究人员关注的焦点。改进后的熵编码算法，可以在DNA信息存储中实现更高效、更可靠的数据存储。在熵编码领域中，一些广泛使用的编码方法包括算术编码^[9-13]、霍夫曼编码^[14-15]和区间编码^[16]，都是基于概率模型实现的数据压缩。其中，算术编码与区间编码具有较高的压缩比，但运算速度较慢；霍夫曼编码虽然编码速度快，但可能存在编码冲突。相较于算数编码和区间编码，非对称数字系统（Asymmetric Numeral Systems，ANS）^[17]展现出更优的综合性能，ANS具有高压缩比、无损可逆性及快速编解码特性，被证明是极具潜力的熵编码方案。文献[18-20]通过理论分析和实验验证，揭示了ANS在压缩性能与运算效率上的双重优势。

尽管已经提出了许多熵编码方案，但由于不同氨基酸对应的密码子数量不同，早期的方案^[21-23]往往未能充分挖掘DNA存储所能提供的空间，同时在满足生物学约束和实际生物应用中存在明显限制。Choi等^[24]将同等数据量所需的DNA长度和合成成本几乎减半，但合成和解码流程复杂；Abdullah等^[25]将二进制数据编码为多重短寡核苷酸库，实现了对大规模数据的可靠写入与读取，但整体存储密度仍远低于理论极限；Liu等^[26]提出了一些可能的混合进制熵编码方案，在兼顾高信息密度与生化约束上表现较好，但实现复杂且参数选择敏感，可能导致解码风险。

此外，Balado^[27]使用香农理论讨论了DNA存储的容量上限，指出其受DNA中不同碱基的比例和长度的影响；Lenz等^[28-29]通过实验分析证明了香农容量上界在大范围参数下的可实现性。这些研究表明，目前的编码算法存储效率仍未达到理论最优，通过设计更优秀的熵编码算法，既能充分利用DNA中信息熵，又能在混合进制编码环境下实现计算效率与存储效率的平衡，对于解决基因分子存储中由于不同氨基酸具有不同密码子数量而形成的混合进制编码问题具有重要意义，同时也反映出现有方法在生物学条件限制下应用场景的不足。

作为新兴的生物分子存储载体，DNA的非均匀编码特性使其在存储领域展现出独特优势，其中，基于熵编码的研究尤为关键。在基因的编码过程中，不同的氨基酸对应的可选密码子数量存在显著差异，这使DNA分子存储本质上构成混合进制编码（Mixed Radix Coding，MRC）环境。然而，现有熵编码及混合进制编码算法普遍存在三方面局限：1） 编解码过程存储空间利用率不足；2） 算法计算复杂度较高；3） 在生化约束条件下难以平衡算法的计算效率与存储效率，导致实际应用受限。

为了应对以上挑战，本文提出了一种流式混合进制编码算法（Streamed Mixed Radix Coding，SMRC），算法通过同义密码子替换策略实现编码区数据存储，在确保原始氨基酸序列不变的前提下，使信息嵌入后的DNA序列在转录翻译过程中仍能生成与原始序列完全一致的蛋白质产物。该算法的输入和输出序列可以是任意长度的序列，并且可以在输入和输出序列中指定每个位置的进制，使得该算法可以将任意混合进制输入映射到任意混合进制输出，从而在满足基因正确翻译蛋白质的条件下，最大程度地提高输入和输出空间进制分布不均匀下的信息熵。此外，通过设定动态阈值参数，该算法能够在保持线性计算复杂度的前提下完成混合进制序列转换，成功解决了大规模数据流处理的效率瓶颈问题。

1　 流式混合进制编码算法

1.1　混合进制系统

进制（Radix）是本文中的一个核心概念，例如日常生活里我们通常使用“十进制”，而在计算机里我们使用“二进制”，这里的“进制”代表不同进制下的计数法可以使用的单个数字取值范围，例如十进制每个数位上可以使用0到9的任意数字，并且“逢十进一”，而二进制则只能使用0和1两个数字，也就是“逢二进一”。这里的进制定义了一串符号序列的最大可用符号数量与符号取值对应关系，可以不限于0至9的数字符号。例如十六进制，从0至9扩展到了包含a至f的十六个数字与字母符号，也就是对应了十六进制的16种不同取值情况（依次代表了0至15的整数取值）。

上述生活中常用的进制是一种“定进制”（Fixed Radix），即每个符号位的进制相同，例如十进制，每一位都可以使用0至9的任何符号。更一般地，我们可以定义混合进制（Mixed Radix）的概念，也就是每个符号位上的进制可以不相同，不同的位置上有着不同的符号数量。生活中最常见的变进制计数系统是时间系统，如果以秒作为基本单位，我们可以对时间“2周，3天，5小时，7分钟，11秒”按(1)式进行换算：

\left(\left(\left(\mathrm{2}\times \mathrm{7}+\mathrm{3}\right)\times \mathrm{24}+\mathrm{5}\right)\times \mathrm{60}+\mathrm{7}\right)\times \mathrm{60}+\mathrm{11}=\mathrm{1}\mathrm{487}\mathrm{231}(1)

所以上述时间等于1 487 231 s这个计算过程体现了不同进制单位之间的换算关系，例如1周有7天，1天有24小时。上述的过程在考虑了熵的情况下没有空间上的浪费，每个位置上每个符号以均等的概率出现^[30]。

在DNA序列中，编码蛋白质的碱基序列由长度为3个碱基的密码子组成，由于同义密码子的存在，因此同一种氨基酸可以由多种密码子进行表达，即不同的氨基酸对应了不同的进制，对应编解码时的混合进制序列。如果要充分利用DNA序列中的存储空间，同时尽可能维持原有的生化特性，就必须使用针对混合进制序列的熵编码算法。

1.2　SMRC算法

1.2.1　问题定义

在利用DNA序列进行信息存储时，通过修改同义密码子完成信息编码存储，如图1所示。

图1中原始序列代表嵌入信息前的DNA编码区碱基序列片段，氨基酸序列为原始序列每个三联碱基密码子对应的氨基酸。要嵌入的数据则是任意的整数序列，为了保证嵌入信息前后碱基序列得到的蛋白质产物相同，需要保证嵌入前后对应的氨基酸序列相同，因此只能在每个位点氨基酸的同义密码子中进行变换。

图1中还展示了部分氨基酸的同义密码子情况，并且展示了一种可能的同义密码子和数值的映射关系。若某个氨基酸含有4个同义密码子，则该位点可以认为是一个进制数为4的数位，且该位点的同义密码子代表了该数位的所有取值集合，同理可得其余位点对应的进制数和取值集合。

因此，对于图1中的编码后序列，可以认为该序列的数字序列表示是\mathrm{1304}，共4位，每一位的进制则是\mathrm{3426}。按如下方式进行问题的一般化定义。

SMRC算法能够实现(2)式的映射关系：

S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{S}\mathrm{M}\mathrm{R}\mathrm{C}\left(S_{\mathrm{I}\mathrm{n}},R_{\mathrm{I}\mathrm{n}},R_{\mathrm{O}\mathrm{u}\mathrm{t}}\right)(2)

式中，在面向DNA编码区序列进行存储时，S_{\mathrm{I}\mathrm{n}}=u_{\mathrm{0}}{u}_{\mathrm{1}}\dots u_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}，为非负整数输入序列，对应要被编码的数据，例如由不同片段组成的数据序列，u_i表示每个片段的数值大小；R_{\mathrm{I}\mathrm{n}}=r_{\mathrm{0}}{r}_{\mathrm{1}}\dots r_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}，为S_{\mathrm{I}\mathrm{n}}每一位上对应的进制，r_i代表每一个u_i的进制，例如不同数据序列片段的取值数量。其中，\mathrm{0}\le u_i\le r_i-\mathrm{1},r_i\ge \mathrm{2,0}\le i\le L_{\mathrm{I}\mathrm{n}}-\mathrm{1}，L_{\mathrm{I}\mathrm{n}}是输入序列长度；S_{\mathrm{O}\mathrm{u}\mathrm{t}}=v_{\mathrm{0}}{v}_{\mathrm{1}}\dots v_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}，为非负整数输出序列，代表对于每个氨基酸位点选择了它的哪一个同义密码子用于信息编码，其中每一个v_j表示下标为j的氨基酸位点的同义密码子的选择结果；R_{\mathrm{O}\mathrm{u}\mathrm{t}}=s_{\mathrm{0}}{s}_{\mathrm{1}}\dots s_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}，为S_{\mathrm{O}\mathrm{u}\mathrm{t}}每一位上对应的进制，对应用于存储信息的DNA序列得到的氨基酸序列，其中每个s_j代表该DNA序列上密码子对应的氨基酸拥有的同义密码子数量。其中，\mathrm{0}\le v_j\le s_j-\mathrm{1},s_j\ge \mathrm{2,0}\le j\le L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}，N是输出序列长度。以图1为例，图中展示的氨基酸序列片段代表R_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{3426}，编码后序列代表S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{1304}。

由以上定义可知，输入与输出序列均是有序的，且每个位置上包含两个信息，分别是“进制”与该进制下的“值”，进制序列与值序列按位形成对应关系。而SMRC算法就是一种数据编解码算法，能够完成输入序列与输出序列之间的互相转换，将某一均匀混合进制下的输入数据映射到另一均匀混合进制下的输出。

1.2.2　算法设计

SMRC算法可将任意混合进制的输入序列转换为另一种混合进制的输出序列，对输入序列进行“编码”操作，并且可以逆向地将输出序列“解码”回原始的输入序列。

SMRC算法具体过程见算法1，要求R_{\mathrm{O}\mathrm{u}\mathrm{t}}足够长才能完全编码S_{\mathrm{I}\mathrm{n}}包含的信息。\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}为正整数，决定了算法的正确运行与效率，将会在后续章节讨论如何进行选择以及对效率的影响。

算法1中的\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}与\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}定义如(3)式和(4)式所示：

N_{\mathrm{1}}=\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}(N_E,r_i,u_i)=N_E\times r_i+u_i(3)

N_{\mathrm{2}}=\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}(N_E,s_j)=(⌊N_E/s_j⌋,N_E\mathrm{\%}{s}_j)(4)

式中，中间值N_E代表算法运行中途的“信息量”变化。

在算法1的第6行，将会通过判断N₁和N₂与Bound的关系确定究竟执行\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}还是\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}操作，随后根据判断结果使用N₁或者N₂更新N_E 的值；通过\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}限制N_E在一定的范围内，以降低算法计算复杂度；\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}操作会使得N_E增加，也就是读取一位输入信息；而\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}操作会使得N_E减小，也就是弹出一位输出信息。N_E与\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}合起来组成了一个在一定大小附近浮动的信息“存储袋”，当算法进行\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}操作，增加信息量到一定程度时，就会水满而溢，此时，应使用\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}输出编码结果序列的每一位。

算法1具有良好的对称性，可以同时用于编码与解码，但解码时需要对输入输出进行一定的处理。对于输入序列S_{\mathrm{I}\mathrm{n}}=u_{\mathrm{0}}{u}_{\mathrm{1}}\dots u_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}，在提供足够大的编码空间时，总能得到唯一的输出序列S_{\mathrm{O}\mathrm{u}\mathrm{t}}=v_{\mathrm{0}}{v}_{\mathrm{1}}\dots v_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}。

编码时的输入为u_{\mathrm{0}}{u}_{\mathrm{1}}\dots u_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}，r_{\mathrm{0}}{r}_{\mathrm{1}}\dots r_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}和s_{\mathrm{0}}{s}_{\mathrm{1}}\dots s_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}时，输出为v_{\mathrm{0}}{v}_{\mathrm{1}}\dots v_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}；解码时使用相同的算法，但是需要将序列倒转，输入为v_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}{v}_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{2}}\dots v_{\mathrm{0}}，s_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{1}}{s}_{L_{\mathrm{O}\mathrm{u}\mathrm{t}}-\mathrm{2}}\dots s_{\mathrm{0}}和r_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}{r}_{L_{\mathrm{I}\mathrm{n}}-\mathrm{2}}\dots r_{\mathrm{0}}时，输出为u_{L_{\mathrm{I}\mathrm{n}}-\mathrm{1}}{u}_{L_{\mathrm{I}\mathrm{n}}-\mathrm{2}}\dots u_{\mathrm{0}}，也即编码前的原始序列的逆序。

需要注意的是，在算法伪代码的14行，若输出进制已用尽，而中间量N_E仍然大于0，则代表提供的输出空间不足，算法无法在给定的输出进制长度内完成序列的转换，此时算法返回None，需要重新提供足够长的输出进制序列才能完整转换。

1.2.3　示例

本节以几个简单的SMRC例子，展示算法1中每一步包含的变量的变化情况。

本节共包含4个示例。其中示例1和示例2为一对编码和解码运算示例，使用相同的阈值参数；示例3和示例4为一对编码和解码运算示例，使用相同的阈值参数，但是阈值参数与示例1、示例2不同。

示例1和示例3均为编码运算，使用相同的输入序列、输入进制和输出进制；示例2和示例4均为解码运算，示例2尝试将示例1的结果解码还原，示例4尝试将示例3的结果解码还原。但是由于阈值参数的不同，算法的运行结果也不尽相同，本节将对示例运算不同过程和结果进行分析。

示例1 SMRC编码算法

输入：输入序列S_{\mathrm{I}\mathrm{n}}=\mathrm{2254012023}；输入进制R_{\mathrm{I}\mathrm{n}}=\mathrm{4476237455}；输出进制R_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{47526232656}；阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}=\mathrm{7}；

输出：转换结果序列S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{25104110032}；

示例1的具体过程见表1。

示例2 SMRC解码算法

输入：输入序列S_{\mathrm{I}\mathrm{n}}=\mathrm{23001140152}；输入进制R_{\mathrm{I}\mathrm{n}}=\mathrm{65623262574}；输出进制R_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{5547326744}；阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}=\mathrm{7}；

输出：转换结果序列S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{3202104522}；

示例2的具体过程见表2。

示例3 SMRC编码算法（阈值参数取值不合适的情况）

输入：输入序列S_{\mathrm{I}\mathrm{n}}=\mathrm{2254012023}；输入进制R_{\mathrm{I}\mathrm{n}}=\mathrm{4476237455}；输出进制R_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{47526232656}；阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}=\mathrm{6}；

输出：转换结果序列S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{25111110032}；

示例3的具体过程见表3。

示例4 SMRC解码算法（阈值参数取值不合适的情况）

输入：输入序列S_{\mathrm{I}\mathrm{n}}=\mathrm{23001111152}；输入进制R_{\mathrm{I}\mathrm{n}}=\mathrm{65623262574}；输出进制R_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{5547326744}；阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}=\mathrm{6}；

输出：转换结果序列S_{\mathrm{O}\mathrm{u}\mathrm{t}}=\mathrm{3202115521}；

示例4的具体过程见表4。

结合上述示例和算法1可知，若算法内层循环结束后中间量N_E大于0，则算法返回None，此时认为SMRC算法未能成功完成转换过程，由于输出空间不足无法完成转换；若内存循环结束后N_E小于等于0，则算法成功完成转换，将会返回转换结果序列。

示例1和示例2中，在给定的输入参数下，中间量N_E在最后都变成了0，对应算法1中成功返回了输出序列，因此示例1和示例2均转换成功。取示例1中动作分支是withdraw的行、v列的值按“步骤顺序”列依次连接可以得到示例1的输出值（编码结果）；类似地，取示例2中动作分支是withdraw的行、u列的值依次连接可以得到示例2的输出值（解码结果），可以发现示例2正确的解码还原出了示例1的输入序列的逆序序列。

示例3和示例4中，在给定的输入参数下，中间量N_E也都在最后都变成了0，因此示例3和示例4的转换过程也都成功，同样从示例中可以获取各自的输出结果，但是可以发现示例4的输出结果并不是示例3的输入序列的逆序，因此示例4未能成功解码还原示例3的输入序列。

对比示例3与示例1的详细步骤，可以发现，在更换了阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值的情况下，步骤10至步骤12的内部量发生了一些变化，进而导致输出结果有一些细小的区别；同样地，对比示例2和示例4，提供的输入序列发生变化，且阈值参数也不相同，部分步骤内部量也不相同，导致输出结果也不相同，甚至示例4无法正确解码出示例3的输入序列。

结合这几个示例可知，在编码过程输入序列、输入进制、输出进制均相同，仅更换阈值参数的情况下，存在解码无法正确还原编码过程输入序列的情况，这意味着为了顺利地进行互逆的编解码转换，阈值参数的取值是有条件的，这将在第2节中进行详细讨论并给出选择算法以及证明。

1.2.4　与传统算法的对比分析

对于此类混合进制转换算法，一种通用的数学方法是短除法，以一个简单的序列转换为例，设输入序列S_{\mathrm{I}\mathrm{n}}=\mathrm{21101}，输入进制R_{\mathrm{I}\mathrm{n}}=\mathrm{32322}，首先将序列按照其进制计算出中间量，其中中间量是一个纯粹的“无进制的数字”，如(5)式所示。

(((((\mathrm{2}\times \mathrm{3}+\mathrm{1})\times \mathrm{2})+\mathrm{1})\times \mathrm{3})+\mathrm{0})\times \mathrm{2}+\mathrm{1}=\mathrm{91}(5)

对于计算结果，常见的书写方式以十进制表示为“91”，但是在计算过程中，其实是“无进制”的一个数，例如我们可以认为它是“92进制”的，也可以认为是十六进制的“0x5B”，在用计算机进行计算时仅仅是存储了该数的值。

为了完成进制转换，需要将中间量继续使用短除法进行转换，此处将中间量转换回原本的序列，可以看作是(5)式过程的逆运算，如(6)式所示，最后从下往上得到原始输入。

\begin{array}{l}\begin{array}{cc}\mathrm{2}& \overline{)\begin{array}{cc}\mathrm{91}& \end{array}}\end{array}\\ \begin{array}{ccc}\begin{array}{cc}& \mathrm{3}\end{array}& \overline{)\begin{array}{cc}\mathrm{45}& \cdots \cdots \end{array}}& \mathrm{1}\end{array}\\ \begin{array}{cccc}\begin{array}{cc}& \end{array}& \mathrm{2}& \overline{)\begin{array}{cc}\mathrm{15}& \cdots \cdots \end{array}}& \mathrm{0}\end{array}\\ \begin{array}{cccc}\begin{array}{cc}& \end{array}& & \begin{array}{ccc}\mathrm{3}& \overline{)\begin{array}{cc}\mathrm{7}& \cdots \cdots \end{array}}& \mathrm{1}\end{array}& \end{array}\\ \begin{array}{cccc}\begin{array}{cccc}& & & \end{array}& \mathrm{\infty }& \overline{)\begin{array}{cc}\mathrm{2}& \cdots \cdots \end{array}}& \mathrm{1}\end{array}\\ \begin{array}{cccc}\begin{array}{cccc}& & & \end{array}& & & \begin{array}{ccc}\mathrm{0}& \cdots \cdots & \mathrm{2}\end{array}\end{array}\end{array}(6)

经过分析可以得出，无论是为了计算出中间量还是转换中间量，传统算法的计算复杂度均为O(n^{\mathrm{2}})，其中序列长度为n，这是因为参与乘法和除法运算的乘数和被除数的位长均与序列长度n呈线性关系，并且乘法和除法的计算次数也与序列长度n呈线性关系。

而在本文的SMRC算法转换过程中，也存在中间量N_E，但是N_E的大小受\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}限制，因而降低了转换过程中的计算复杂度，但是从前面的示例中可以看出，计算复杂度的降低是有条件限制的，需要选取合适的阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}才能正确地完成转换。

2　 阈值筛选算法

在算法示例中可以看到，当选取不同的阈值\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}时，算法执行的正确性也有可能不同，因此在SMRC算法中，阈值\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}是一个重要的参数，它不仅决定了算法的正确运行，同时影响了中间量的浮动范围，进而决定了算法计算性能。下面首先给出算法的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}筛选原理，再依次给出SMRC算法的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}具体筛选方法与公式。

2.1　阈值筛选原理

回顾前面介绍的算法1，它的核心工作机制是中间量N_E与一对\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}和\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}操作，它们互为逆操作。其中\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}负责处理输入，增加N_E；\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}操作相反，负责处理输出，减少N_E。

图2给出了算法运行时N_E的变化曲线。图中展示了示例1和示例2的运行情况，随着循环轮数的递增，N_E的值也发生变化。从图2中可以看出编码实线与解码虚线沿中轴对称，因此对于图中的实线，若沿循环轮数增大的方向从左往右理解则是编码时N_E的变化，若沿循环轮数减小的方向从右往左理解则是解码时N_E的变化。图中每一条斜率为正的线段代表了编码时的\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}（解码时的\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}）；而斜率为负的折线代表编码时的\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}（解码时的\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}）操作。当选择一个合适的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}时，能够合理的约束N_E的变化范围，使得编码与解码沿着同一条路径行走，使用完全互逆的\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}/\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}操作，从而完成输入与输出序列的一一映射关系。

在使用算法1时，可以按照如下规则去进行\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值的筛选。

设B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}表示不可用的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值，B_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}表示可用的取值，算法正处于编码操作的某一循环轮次，则有关于B_{\mathrm{1}}，B_{\mathrm{2}}的两个表达式(7)式、(8)式。

B_{\mathrm{1}}=n\times \mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}\left(\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}{\mathrm{w}}^{-\mathrm{1}}\left(n,\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{O}\mathrm{u}\mathrm{t}}\right),\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{I}\mathrm{n}}\right)(7)

B_{\mathrm{2}}=n\times \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}{\mathrm{w}}^{-\mathrm{1}}\left(\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}\left(n,\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{I}\mathrm{n}}\right),\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{O}\mathrm{u}\mathrm{t}}\right)(8)

取m=\mathrm{m}\mathrm{i}\mathrm{n}\{B_{\mathrm{1}},B_{\mathrm{2}}\}，M=\mathrm{m}\mathrm{a}\mathrm{x}\{B_{\mathrm{1}},B_{\mathrm{2}}\}，则B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}满足(9)式：

m+\mathrm{1}\le B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}\le M(9)

(7)~(9)式提供了针对每一轮的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}筛选方式。参数\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{I}\mathrm{n}}对应具体算法需要的输入序列参数；\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}{\mathrm{w}}^{-\mathrm{1}}代表\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}的逆操作，其本质就是对一个中间量n进行反向的\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}操作，也是对n进行增加，\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{s}}_{\mathrm{O}\mathrm{u}\mathrm{t}}对应需要的输入序列参数；\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}和\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{e}}^{-\mathrm{1}}以此类推。

因此，“夹”在B_{\mathrm{1}}，B_{\mathrm{2}}之间的任意值就是不可用的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值。遍历所有可能的中间量n和参数取值，筛去所有的不可用取值，剩下的就是可用的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值。在实际计算时，考虑到编码和解码的进制是可以互换的，因此需要将输入和输出调换后的情况一并遍历。

2.2　阈值筛选公式

对于SMRC算法，设P=R_{\mathrm{1}}{R}_{\mathrm{2}}为任意两个大于等于2的进制乘积，即P是一个大于等于4的合数，设n为任意正整数，r_{\mathrm{1}}，r_{\mathrm{2}}为整数且\mathrm{0}\le r_{\mathrm{1}}\le R_{\mathrm{1}}-\mathrm{1}，\mathrm{0}\le r_{\mathrm{2}}\le R_{\mathrm{2}}-\mathrm{1}。则B_{\mathrm{1}}，B_{\mathrm{2}}可以用(10)式与(11)式进行表示。

B_{\mathrm{1}}=n\left[\left(n{R}_{\mathrm{1}}+r_{\mathrm{1}}\right)R_{\mathrm{2}}+r_{\mathrm{2}}\right]=P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}{r}_{\mathrm{1}}+n{r}_{\mathrm{2}}(10)

B_{\mathrm{2}}=n\left[\left(n{R}_{\mathrm{2}}+r_{\mathrm{2}}\right)R_{\mathrm{1}}+r_{\mathrm{1}}\right]=P{n}^{\mathrm{2}}+n{R}_{\mathrm{1}}{r}_{\mathrm{2}}+n{r}_{\mathrm{1}}(11)

即取任意一对R_{\mathrm{1}}，R_{\mathrm{2}}，枚举B_{\mathrm{1}}，B_{\mathrm{2}}的取值，筛去B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}，得到B_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}取值。例如对于R_{\mathrm{1}}=\mathrm{2}，R_{\mathrm{2}}=\mathrm{3}，通过计算得到一部分结果B_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}=[\mathrm{1,7}]，B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}=[\mathrm{8,10}]，继续枚举则可以得到更多的取值集合。

从(9)式、(10)式与(11)式中可以看到，对任意的正整数n，B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}的取值范围由P个不同的整数区间[m+\mathrm{1},M]取并集得到，令m=M，则易得：

R_{\mathrm{2}}{r}_{\mathrm{1}}+r_{\mathrm{2}}=R_{\mathrm{1}}{r}_{\mathrm{2}}+R_{\mathrm{1}}

\Rightarrow (R_{\mathrm{2}}-\mathrm{1})r_{\mathrm{1}}=(R_{\mathrm{1}}-\mathrm{1})r_{\mathrm{2}}(12)

容易得到当r_{\mathrm{1}}=\mathrm{0}且r_{\mathrm{2}}=\mathrm{0}，或r_{\mathrm{1}}=R_{\mathrm{1}}-\mathrm{1}且r_{\mathrm{2}}=R_{\mathrm{2}}-\mathrm{1}时，m=M，此时区间为空集。又B_{\mathrm{1}}和B_{\mathrm{2}}是关于r_{\mathrm{1}}，r_{\mathrm{2}}单调递增的，所以由(13)式得到m的最小值：

\begin{array}{l}\left\{m\left(r_{\mathrm{1}},r_{\mathrm{2}}\right)\right\}=\mathrm{m}\mathrm{i}\mathrm{n}\left\{m\left(\mathrm{0,1}\right),m\left(\mathrm{1,0}\right)\right\}=\\ \mathrm{m}\mathrm{i}\mathrm{n}\left\{\mathrm{m}\mathrm{i}\mathrm{n}\left\{P{n}^{\mathrm{2}}+n,P{n}^{\mathrm{2}}+R_{\mathrm{1}}n\right\},\mathrm{m}\mathrm{i}\mathrm{n}\left\{P{n}^{\mathrm{2}}+R_{\mathrm{2}}n,P{n}^{\mathrm{2}}+n\right\}\right\}=\end{array}

\mathrm{m}\mathrm{i}\mathrm{n}\left\{P{n}^{\mathrm{2}}+n,P{n}^{\mathrm{2}}+n\right\}=P{n}^{\mathrm{2}}+n(13)

同理可由(14)式得到M的最大值：

\underset{r_{\mathrm{1}},r_{\mathrm{2}}}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{M(r_{\mathrm{1}},r_{\mathrm{2}})\right\}=

\mathrm{m}\mathrm{a}\mathrm{x}\left\{M\left(R_{\mathrm{1}}-\mathrm{2},R_{\mathrm{2}}-\mathrm{1}\right),M\left(R_{\mathrm{1}}-\mathrm{1},R_{\mathrm{2}}-\mathrm{2}\right)\right\}=

P{n}^{\mathrm{2}}+\left(P-\mathrm{2}\right)n(14)

因此对于任意的正整数n来说，B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}能覆盖的最小值和最大值分别为P{n}^{\mathrm{2}}+n+\mathrm{1}和P{n}^{\mathrm{2}}+\left(P-\mathrm{2}\right)n。下面证明B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}就是最小值和最大值之间的所有整数。

不失一般性，令r_{\mathrm{2}}=\mathrm{0}，r_{\mathrm{1}}=\mathrm{1,2},\dots ,R_{\mathrm{1}}-\mathrm{1}，则可以得到R_{\mathrm{1}}-\mathrm{1}个区间[P{n}^{\mathrm{2}}+n{r}_{\mathrm{1}}+\mathrm{1},P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}{r}_{\mathrm{1}}]，区间左右端点的差值大小为：

P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}{r}_{\mathrm{1}}-\left(P{n}^{\mathrm{2}}+n{r}_{\mathrm{1}}+\mathrm{1}\right)=

n{R}_{\mathrm{2}}{r}_{\mathrm{1}}-n{r}_{\mathrm{1}}-\mathrm{1}\ge

\mathrm{2}n{r}_{\mathrm{1}}-n{r}_{\mathrm{1}}-\mathrm{1}=

n{r}_{\mathrm{1}}-\mathrm{1}\ge \mathrm{0}(15)

所以这R_{\mathrm{1}}-\mathrm{1}个区间都至少包含一个整数，又有(16)式：

P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}{r}_{\mathrm{1}}-\left(P{n}^{\mathrm{2}}+n\left(r_{\mathrm{1}}+\mathrm{1}\right)+\mathrm{1}\right)=

n{R}_{\mathrm{2}}{r}_{\mathrm{1}}-n{r}_{\mathrm{1}}-n-\mathrm{1}\ge

\mathrm{2}n{r}_{\mathrm{1}}-n{r}_{\mathrm{1}}-n-\mathrm{1}=

n\left(r_{\mathrm{1}}-\mathrm{1}\right)-\mathrm{1}\ge -\mathrm{1}(16)

(16)式说明r_{\mathrm{1}}取相邻整数时，前后两个区间互相有交集或刚好相邻。综上，这R_{\mathrm{1}}-\mathrm{1}组区间可以连续覆盖从它们的最小值到最大值的所有整数，即区间[P{n}^{\mathrm{2}}+n+\mathrm{1},P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}(R_{\mathrm{1}}-\mathrm{1})]内所有整数。

再令r_{\mathrm{2}}=\mathrm{0,1},\dots ,R_{\mathrm{2}}-\mathrm{2}，r_{\mathrm{1}}=R_{\mathrm{1}}-\mathrm{1}，可以得到R_{\mathrm{2}}-\mathrm{1}个区间[P{n}^{\mathrm{2}}+n(R_{\mathrm{1}}-\mathrm{1})+n{R}_{\mathrm{1}}{r}_{\mathrm{2}}+\mathrm{1},P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}(R_{\mathrm{1}}-\mathrm{1})+n{r}_{\mathrm{2}}]。类似的，我们同样可以证明这R_{\mathrm{2}}-\mathrm{1}个区间也可以连续覆盖从它们的最小值到最大值的所有整数，即区间[P{n}^{\mathrm{2}}+n(R_{\mathrm{1}}-\mathrm{1})+\mathrm{1},P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}(R_{\mathrm{1}}-\mathrm{1})]内的所有整数。

又当r_{\mathrm{1}}=R_{\mathrm{1}}-\mathrm{1}，r_{\mathrm{2}}=\mathrm{0}时，区间[P{n}^{\mathrm{2}}+n(R_{\mathrm{1}}-\mathrm{1})+\mathrm{1},P{n}^{\mathrm{2}}+n{R}_{\mathrm{2}}(R_{\mathrm{1}}-\mathrm{1})]为上述两组区间的公共区间。所以上述两组区间能够覆盖它们的最小值与最大值之间的所有数，即(13)式和(14)式的结果。综上，我们可以得到B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}的通项公式为：

P{n}^{\mathrm{2}}+n+\mathrm{1}\le B_{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}\le P{n}^{\mathrm{2}}+\left(P-\mathrm{2}\right)n(17)

进一步可以得到B_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}的通项公式为：

P{n}^{\mathrm{2}}-\left(P+\mathrm{2}\right)n+\mathrm{3}\le B_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}\le P{n}^{\mathrm{2}}+n(18)

其中n均为正整数。

(17)式和(18)式给出了SMRC算法的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}选择公式，在数轴上看是一段可用一段不可用的间隔连续区间。(17)式和(18)式仅仅限定了算法循环过程中的某一步的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值。当每次需要在循环中计算一次N_{\mathrm{1}}与N_{\mathrm{2}}时，\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}的取值范围仅受当前正在处理的输入进制与输出进制的影响，即每一对进制之间都会有属于它们自己的合法\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围。

最后，要使得混合进制下的SMRC算法正常工作，需要将输入输出的进制之间进行两两组合，算出它们的合法\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值的交集，才能得到最终的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围；其中对于定进制这一特殊形式，只需要计算输入与输出进制这一对情况即可。

例如输入进制的取值有2、3，输出进制的取值有2、5，则最终算法的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围如图3所示。输入与输出的进制对组合情况共有4种，取这四种情况下的交集便能得到混合进制下的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值集合。图3中所有区间是左开右闭的整数取值，区间右侧虚线表示不包括该位置数值，图中浅色阴影行表示每一对进制的取值区间，深色阴影行表示所有浅色阴影行混合后的交集区间结果。

2.3　对SMRC算法的扩展

在实际使用中，一般提前枚举计算算法中所有进制组合的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值，并对它们取交集，得到整个算法的可用取值。但是有时候混合进制取值数过多，如果对所有进制组合结果取交集，得到的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围将非常有限；并且为了限制算法的计算复杂度，减小数据运算范围，还要按需选择合适大小的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值。

为了解决上述问题，可以放宽算法对\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值的限制，将\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围限定在每一轮循环而不是整个算法流程。具体来说，在算法的每一轮计算时，仅考虑当前正在处理的输入进制与输出进制，并计算这一对进制的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值，然后选取合适的值，而下一轮则又是新的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围。实际计算中，由于输入进制与输出进制都是提前已知的，因此可以预计算出所有进制的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围，在真正计算时只需要查表即可。算法2给出了算法1的扩展形式。

在算法1中，只能使用一个固定单独适用于整个混合进制的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}值，当混合进制数量增加时，想要找到一个较小的可用\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}是困难的，而\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}越大，则中间量N_E的浮动范围会处于一个较大值，从而带来较大的计算开销，不能很好的利用流式计算降低计算复杂度的优势。

而在算法2中，可以针对每一组进制单独设置一个\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}值，因此所有的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值可以在一个较小的数字附近浮动，全局近似取到一个较小值，从而降低整体计算复杂度，提高编解码效率。

3　 算法分析

3.1　复杂度分析

根据文献[1,16-17]中展示的构造方法和分析，流式形式的算法1和算法2的时间复杂度从非流式的O(N^{\mathrm{2}})降低至流式算法下的O(N\sqrt[]{k})，其中k\propto \mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}，在选定\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}的情况下，对于最终的复杂度是一个常数因子，因此实际运用时\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}越小时间复杂度越低，可以近似认为是线性时间复杂度；两个算法的空间复杂度均为O(N)，即可以不需要使用额外的空间。

基于（17）式和（18）式计算Bound取值时，固定\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}筛选算法的时间复杂度为O(R^{\mathrm{2}})，空间复杂度为O(R^{\mathrm{2}})，其中R是编解码中涉及的进制种类数，但是\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}的取值是可以提前预计算的，在实际使用时复杂度可以单独考虑，不会对算法运行造成额外负担。

3.2　存储效率分析

为了测试算法的实际存储效率，使用计算机程序对其进行了大规模编解码数据的模拟测试。测试参数设置为将随机长度为10 000的2~6混合进制输入序列编码成随机的4~6混合进制输出序列，取1 000轮结果作为平均值。对\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}在10、50、100附近取值时分别进行了统计分析，计算了各自输出序列信息熵（表5），以及输出序列中每个进制下符号的分布情况，图4仅展示了不同\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值下输出序列进制6的符号分布情况。

对于某一种进制n的信息熵，按(19)式进行计算。

H(X)=-{\displaystyle \sum _{i=\mathrm{1}}^n}{p}_{i}lo{g}_n(p_i)(19)

其中，p_i代表数字i-\mathrm{1}出现的频率

对于整条序列的信息熵，则是对不同进制的信息熵进行求和平均。其中输入序列的每个进制下的每个数字总是按照均匀随机分布产生，因此在长度足够、测试次数足够的情况下认为输入序列的信息熵总是理论最大值1。

从表5中可以看出，输出序列的信息熵距离理论极限值1.0存在一些差距，控制在1%以内，意味着每1 000 bit的存储空间实际只能存储约990 bit的信息。随着\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值变大，信息熵也逐渐变大，不断逼近理论极限值，但是随之而来的是计算量的提升，中间量N_E 的变化范围将随着Bound取值的变大而变大，使得算法中的乘法运算计算复杂度增大，从而失去流式计算的优势。

从图4中可以得到信息熵变化的原因，输出序列存在分布不均匀的问题，数字越小概率越高，因为在算法的内层循环受到\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}的限制，中间量超过一定范围之后便会进行withdraw操作，所以偏小的数字符号以更高的概率出现。这一现象当\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}值越小时越明显，因为小的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}值将使得中间量N_E在较小的取值范围浮动，更加提高了偏小数字符号的出现概率。一种极限情况是\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取为无穷大，此时SMRC算法退化为普通的MRC算法，时间复杂度变为O(N^{\mathrm{2}})，但是输出序列的信息熵为理论极限值。

通过以上分析可以知道，\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}作为算法中的关键参数，影响着算法的计算复杂度与存储效率。实际使用时，在求解可用的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值范围后，通常选择区间内最小的\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}值作为算法参数，既能充分利用存储空间，又能获得较好的计算性能。

3.3　实验对比分析

3.3.1　实验环境

为了评价本文算法性能，并与现有方案进行对比，将使用计算机程序进行模拟测试。

测试所使用语言为C语言，处理器为13th Gen Intel(R) Core(TM) i7-13700H，内存大小为16 GB，操作系统为Win11。

3.3.2　参数设置

生成模拟测试数据时，为了仿真DNA嵌入环境，所使用的进制范围为2~6的5种混合进制，这对应所有可以用于编码的氨基酸的密码子数量种类数^[31]。

在对比时，本算法的阈值参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}选择10附近的可用取值，即常数项k约等于10。

测试方式设置为将随机长度为10 000的2~4混合进制输入序列编码成随机的2~6混合进制输出序列，每次测试1 000轮结果，重复多次。

3.3.3　评价指标

将从时间复杂度和存储信息密度两方面对算法进行分析并与不同方案对比。时间复杂度通过多次实验得到序列长度为10 000时不同算法每千次的平均执行耗时；信息密度通过(19)式计算输出结果每一种进制的信息熵得到，取所有不同进制信息熵的平均值。所有结果均保留至小数点后6位。

3.3.4　实验结果及分析

表6给出了本文及现有方案的测试结果。

由表6的测试结果可以看到，在计算复杂度是O(N^{\mathrm{2}})的方案中，信息密度均能够达到理论最大值1；计算复杂度为线性复杂度O(N)时，则存储信息密度大幅下降，即使是相对较高的BioCode^[23]也只能达到0.97左右。而本文提出的SMRC算法，能够在参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}的控制下，以接近线性的计算复杂度O(\sqrt[]{k}N)获得0.99左右的存储信息熵，接近理论最大值。

相较于其他方案，本文的SMRC引入了可控参数\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}，以损失极小部分的存储效率为代价，显著提高了计算效率。同时在某些场景下，可以让使用者权衡计算复杂度与存储效率之间的权衡关系，自主调节\mathrm{B}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}取值大小，提高了算法的泛用性，能够适应不同的使用场景。

4　 结 语

本文提出了一种新的流式混合进制编码算法SMRC，该算法能够高效处理混合进制数据。在生物密码子数量不均等的情况下，最大程度地提高输入和输出空间进制分布不均匀下的信息熵，充分利用非均匀存储介质的信息存储容量。通过证明与实验分析，该算法能够在不到1%的存储空间浪费下，以线性计算复杂度进行混合进制数据编解码操作，为DNA等非均匀信息存储领域提供了一种新的熵编码方法。

随着未来研究的发展，作者认为该领域还需要就以下几个问题进行深入研究：1） 在用于DNA序列存储进行数据编解码时，考虑更加严格的生化条件约束，例如考虑同义密码子分布的不均衡等；2） 继续寻找更优秀的转换算法，解除算法对特殊参数的限制，进一步逼近信息存储密度的理论最大值；3） 发掘此类混合进制编解码算法的应用场景，根据不同场景进行针对性的优化适配；4）针对混合进制存储场景设计相匹配的数据容错算法，增强数据编解码算法在存储数据时的鲁棒性。总的来看，针对非均匀存储介质的信息存储算法仍会是未来的一大研究重点，该领域将为新一代信息存储技术的发展开辟更加广阔的前景。

参考文献

[1] GU M， LI X P， CAO Y Y. Optical storage arrays： A perspective for future big data storage［J］. Light： Science & Applications， 2014， 3（5）： e177. DOI：10.1038/lsa.2014.58 .

[2] CEVALLOS Y， NAKANO T， TELLO-OQUENDO L， et al. A brief review on DNA storage， compression， and digitalization［J］. Nano Communication Networks， 2022， 31： 100391. DOI：10.1016/j.nancom.2021.100391 .

[3] 昝乡镇， 姚翔宇， 许鹏， 等. DNA存储文件系统研究进展［J］. 电子与信息学报， 2023， 45（6）： 1911-1920. DOI： 10.11999/JEIT220561 .

[4] ZAN X Z， YAO X Y， XU P， et al. A survey on file architecture in DNA storage［J］. Journal of Electronics & Information Technology， 2023， 45（6）： 1911-1920. DOI： 10.11999/JEIT220561 .

[5] 魏亚男， 刘倩， 齐浩. 面向海量数据的集成化DNA存储系统［J］. 化学工业与工程， 2025， 42（1）： 173-182. DOI： 10.13353/j.issn.1004.9533.20220337 .

[6] WEI Y N， LIU Q， QI H. Integrated DNA storage system for massive digital data［J］. Chemical Industry and Engineering， 2025， 42（1）： 173-182. DOI： 10.13353/j.issn.1004.9533.20220337 .

[7] 丁双玫. DNA存储技术及其在档案信息存储中应用的可能［J］. 中国档案， 2022（7）： 60-62.

[8] DING S M. DNA storage technology and the possibility of its application in archival information storage［J］. China Archives， 2022（7）： 60-62.

[9] GRANTHAM R， GAUTIER C， GOUY M， et al. Codon catalog usage and the genome hypothesis［J］. Nucleic Acids Research， 1980， 8（1）： r49-r62. DOI：10.1093/nar/8.1.197-c .

[10] BORNHOLT J， LOPEZ R， CARMEAN D M， et al. Toward a DNA-based archival storage system［J］. IEEE Micro， 2017， 37（3）： 98-104. DOI：10.1109/MM.2017.70 .

[11] RUDNER B. Construction of minimum-redundance codes with an optimum synchronizing property［J］. IEEE Transactions on Information Theory， 1971， 17（4）： 478-487. DOI：10.1109/TIT.1971.1054657 .

[12] RISSANEN J， LANGDON G G. Arithmetic coding［J］. IBM Journal of Research and Development， 1979， 23（2）： 149-162. DOI：10.1147/rd.232.0149 .

[13] RISSANEN J J. Generalized kraft inequality and arithmetic coding［J］. IBM Journal of Research and Development， 1976， 20（3）： 198-203. DOI：10.1147/rd.203.0198 .

[14] LANGDON G G. An introduction to arithmetic coding［J］. IBM Journal of Research and Development， 1984， 28（2）： 135-149. DOI：10.1147/rd.282.0135 .

[15] WITTEN I H， NEAL R M， CLEARY J G. Arithmetic coding for data compression［J］. Communications of the ACM， 1987， 30（6）： 520-540. DOI：10.1145/214762.214771 .

[16] PENNEBAKER W B， MITCHELL J L， LANGDON G G， et al. An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder［J］. IBM Journal of Research and Development， 1988， 32（6）： 717-726. DOI：10.1147/rd.326.0717 .

[17] HUFFMAN D A. A method for the construction of minimum-redundancy codes［J］. Resonance， 2006， 11（2）： 91-99. DOI：10.1007/BF02837279 .

[18] HUFFMAN D A. A method for the construction of minimum-redundancy codes［J］. Proceedings of the IRE， 1952， 40（9）： 1098-1101. DOI： 10.1109/JRPROC.1952.273898 .

[19] MARTIN G N N. Range encoding： An algorithm for removing redundancy from a digitised message［EB/OL］. ［2024-06-16］.

[20] DUDA J， TAHBOUB K， GADGIL N J， et al. The use of asymmetric numeral systems as an accurate replacement for Huffman coding［EB/OL］. ［2015-07-30］. DOI: 10.1109/pcs.2015.7170048 .

[21] YOKOO H， DUBÉ D. Asymptotic optimality of asymmetric numeral systems［EB/OL］. ［2024-05-26］.

[22] DUBÉ D， YOKOO H. Empirical evaluation of the effect of the symbol distribution on the performance of ANS［EB/OL］. ［2024-05-27］.

[23] YOKOO H. On the stationary distribution of asymmetric binary systems［C］//2016 IEEE International Symposium on Information Theory （ISIT）. New York： IEEE Press， 2016： 11-15. DOI： 10.1109/ISIT.2016.7541051 .

[24] SHIMANOVSKY B， FENG J， POTKONJAK M. Hiding data in DNA［C］//Information Hiding. Berlin： Springer， 2003： 373-386. DOI：10.1007/3-540-36415-3_24 .

[25] MODEGI T. Watermark embedding techniques for DNA sequences using codon usage bias features［EB/OL］. ［2024-05-30］.

[26] HAUGHTON D， BALADO F. BioCode： Two biologically compatible algorithms for embedding data in non-coding and coding regions of DNA［J］. BMC Bioinformatics， 2013， 14： 121. DOI：10.1186/1471-2105-14-121 .

[27] CHOI Y， RYU T， LEE A C， et al. High information capacity DNA-based data storage with augmented encoding characters using degenerate bases［J］. Scientific Reports， 2019， 9： 6582. DOI：10.1038/s41598-019-43105-w .

[28] ABDULLAH A A， EESA A S， ABDO A M. New data hiding approach based on biological functionality of DNA sequence［J］. Science Journal of University of Zakho， 2019， 7（4）： 184-189. DOI：10.25271/sjuoz.2019.7.4.647 .

[29] LIU Q， WANG P C， CUI J S， et al. MRC： A high density encoding method for pratical DNA-based storage［C］//2020 Eighth International Conference on Advanced Cloud and Big Data （CBD）. New York： IEEE Press， 2020： 13-19. DOI：10.1109/CBD51900.2020.0001 .

[30] BALADO F. On the embedding capacity of DNA strands under substitution， insertion， and deletion mutations［EB/OL］. ［2024-06-03］.

[31] LENZ A， SIEGEL P H， WACHTER-ZEH A， et al. An upper bound on the capacity of the DNA storage channel［C］//2019 IEEE Information Theory Workshop （ITW）. New York： IEEE Press， 2019： 1-5. DOI：10.1109/ITW44776.2019.8989388 .

[32] LENZ A， SIEGEL P H， WACHTER-ZEH A， et al. Achieving the capacity of the DNA storage channel［C］//ICASSP 2020—2020 IEEE International Conference on Acoustics， Speech and Signal Processing （ICASSP）. New York： IEEE Press， 2020： 8846-8850. DOI：10.1109/ICASSP40776.2020.9053049 .

[33] SHANNON C E. A mathematical theory of communication［J］. Bell System Technical Journal， 1948， 27（3）： 379-423. DOI：10.1002/j.1538-7305.1948.tb01338.x .

[34] GENSCRIPT. GenScript Codon Table Tool［EB/OL］. ［2024-01-01］.

基金资助

国家重点研发计划(2020YFA0712104)