中国余数定理的解析——文档阅读

中国余数定理的解析

Doerry, Armin & Bickel, Douglas. (2022). Notes on the Chinese Remainder Theorem for Radar.

1. 引言与背景

中国余数定理（Chinese Remainder Theorem, CRT），这一古老的数论工具，最早可追溯至公元三至五世纪的中国数学家孙子。其现代应用极为广泛，尤其在雷达信号处理领域，它被用于解决因采用多种脉冲重复频率（PRF）进行测量而引发的多普勒或距离模糊问题。定理的本质在于，通过一组关于未知数  的同余方程，求解出该未知数。每个方程都基于一个模数  和一个余数 。除了雷达，它还在计算、编码理论和现代密码学中占据核心地位。

2. 整数形式的理论与算法

2.1 基本定理与矩阵解法

CRT的核心是求解一个联立同余方程组。对于一个未知的正整数 ，我们已知它被一组整数模数  除后，得到相应的余数 。这可以表示为：

其中， 是一个未知的整数乘子。传统CRT指出，若所有模数  两两互质，那么在模  的范围内，存在一个唯一的解 。

为了进行算法实现，报告提出了一种巧妙的线性代数构造。首先将方程变换为 ，然后构建如下的矩阵方程：

这个方程组包含  个未知数（ 和  个 ）和  个方程，因此本身是不定的。然而，关键的约束在于所有的  必须是整数。利用这一点，我们可以将其中一个乘子，比如 ，的猜测值  当作已知输入。这样，方程组就变成了  的方阵，从而可解。通过在一个有限的整数范围内  对  进行遍历搜索，当找到一个  使得计算出的所有其他  也恰好为整数时，对应的  就是我们寻找的联立解。

2.2 放宽“两两互质”的限制

报告接着指出即使模数不互质（例如，一组模数为{5, 25, 125}），上述的矩阵解法依然有效，因为求解矩阵的逆矩阵依然存在。在这种情况下，解的唯一性区间不再由模数的简单乘积  决定，而是由它们的最小公倍数（Least Common Multiple, LCM）决定：

这意味着解  在模  的意义下是唯一的。这个推广极大地增强了CRT在实际选型中的灵活性。

2.3 负整数与解的周期性

解的周期性是关键：如果  是一个解，那么所有 （其中  是任意正、零或负整数）都是等价的解，因为它们在用模数  相除时会产生完全相同的余数。这表明，解空间是一个在实数轴上以  为周期无限延伸的集合。因此，我们可以根据具体问题定义一个长度为  的解区间，例如 ，并将最终计算出的解通过加减整数倍的  来映射到这个区间内。

3. 非整数形式的理论扩展

3.1 有理数与实数系统

首先考虑基数  和余数  均为有理数的情况。任何有理数都可以表示为分数。通过将方程组中的每一项乘以所有分母的最小公倍数 ，可以将有理数方程无损地转换为一个等价的、系数更大的整数方程组。之后，便可应用前述的整数CRT算法求解。由于计算机中所有的浮点数本质上都是有理数（分母是2的幂），且任何实数（包括无理数如 ）都可以被有理数以任意精度逼近，这为CRT处理实数问题打开了大门。当基数中包含无理数时，不存在一个有限的公共周期 。解决方法是对无理数进行有理近似（例如，截取到特定的小数位数）。近似的精度越高，计算出的唯一解区间  就越大，允许解模糊的范围也就越广。

3.2 实数算法与噪声鲁棒性

对于实数系统 ，乘子  依然必须是整数。算法的核心是在预设的解区间  内，通过迭代搜索一个基准乘子  的整数值。由于测量噪声的存在，计算出的其他  会是带有微小小数部分的实数。算法通过一个非线性决策步骤来寻找最优解：选择那一组解，其乘子向量  与其四舍五入后的整数向量  之间的欧几里得距离（L2范数）最小。

这本质上是寻找最“接近”整数解的方案。一旦确定了最优的整数乘子组合，最终的解  可以通过对所有方程的解进行加权平均或算术平均得到，这进一步增强了算法对余数测量噪声的鲁棒性。

4. 误差、分辨率与系统设计

在任何实际测量系统中，误差都是不可避免的。余数  的测量误差  对CRT的性能有直接且深刻的影响。

4.1 误差传播与两种失效模式

误差的传播可以表示为：。这里存在两种截然不同的失效模式：

1. 残余误差（良性）：当余数噪声  足够小，算法能够正确地将计算出的乘子舍入到其真实的整数值时（即  的小数部分被正确处理，整数部分为0）。此时，解的误差约等于余数的测量误差，。这是系统正常工作时的误差表现。

2. 乘子选择错误（恶性）：当余数噪声过大，导致算法将乘子舍入到了一个错误的整数值时（例如，将  错误地判断为6）， 的整数部分不再为零。由于基数  通常远大于1， 这一项会产生一个巨大的误差，导致最终的解  发生灾难性的偏离。这是应用CRT时必须极力避免的情况。

4.2 避免乘子错误的关键条件

为了保证系统能够可靠地工作在“良性”模式下，必须对余数的测量精度提出严格要求。报告推导出了一条至关重要的设计准则：为了能正确分辨乘子，任意两个余数的测量误差之差的绝对值，必须小于对应基数之差绝对值的一半。

这个不等式是整个系统设计的核心约束。它定量地揭示了基数的选择（，即分离度）与测量精度（，即噪声水平）之间的权衡关系。为了获得可靠的解模糊性能，系统的噪声标准差必须远小于基数之间的最小间隔。

附录：避免乘子选择错误的数学推导

原文中给出了避免乘子错误的关键条件，以下是该条件的逐步推导。

1. 问题设定

我们考虑一个使用两个不同基数  和  的系统。真实的未知量为 ，真实的整数乘子为  和 。我们有：

然而，我们实际测量到的是带有噪声的余数  和 ：

其中  和  是测量误差。

CRT算法的目标是根据测量的  和已知的  来反推出一个解  和对应的整数乘子 。

2. 求解过程中的误差关系

算法在求解时，实际上是寻找一个共同的解 ，它满足：

其中  是算法计算出的、最接近整数的实数乘子。

将(3)和(4)联立，我们得到：

3. 引入真实值

现在，我们把真实的关系代入。从(1)和(2)可知 ，即：

用方程(5)减去方程(6)，得到：

这里， 和  分别是两个乘子的计算误差。

4. 关键假设与推导

在许多实际应用中，基数  和  会被选取得非常接近。在这种情况下，真实的整数乘子  和  很有可能是相等的（除非  恰好落在一个周期的边缘）。我们假设 。同样，算法在寻找解时也会倾向于找到一组相等的整数乘子，即我们期望 。

因此，我们可以假设乘子的误差也是高度相关的，近似有 。将此假设代入方程(7)：

5. 得出最终条件

算法的最后一步是将计算出的实数乘子误差  进行四舍五入，以确定最终的整数乘子误差。为了不发生乘子选择错误，我们必须确保计算出的  在经过四舍五入后等于0。

四舍五入的规则是：当一个数的绝对值小于0.5时，它被舍入为0；当其绝对值大于等于0.5时，它被舍入为1或-1（或其他非零整数）。因此，要保证 ，必须满足：

将方程(8)代入这个条件：

这个推导过程表明，为了确保CRT算法能够正确地将计算出的乘子舍入到其真实的整数值，两个余数上的组合测量噪声必须被严格限制在由两个基数之间差值所确定的范围之内。