On de Bruijn Array Codes—Part II: Pseudo-Random Array Codes

作者: Simon R. Blackburn, Yeow Meng Chee, Tuvi Etzion, Huimin Lao
来源: IEEE Transactions on Information Theory
主题: 其他
相关性: 1/10
机构绿灯: Technion - Israel Institute of Technology（US News 前 50，免分进入精读）
链接: https://doi.org/10.1109/tit.2026.3686267

---

一、领域脉络与小综述

这个方向是什么

本文研究的“伪随机阵列码”（pseudo-random array codes）是编码理论与组合设计的一个交叉子方向。其根本问题是：如何构造一个由 r1 × r2 矩阵（阵列）组成的线性码，使得每个 n1 × n2 非零矩阵恰好作为“窗口”出现在码中某个阵列的某个位置上一次。这本质上是将一维的“de Bruijn 序列”（每个长度为 n 的二元串恰好出现一次）推广到二维，并进一步推广到码（多个阵列的集合）。该方向成熟度较高，已有经典构造（基于有限域上的线性反馈移位寄存器，LFSR），但参数范围有限，且从单个阵列到阵列码的推广存在构造与验证上的空白。

发展脉络（history）

本文的 introduction 和参考文献勾勒出以下发展线：

1. 奠基工作：一维 de Bruijn 序列与伪随机序列

   • Golomb (1967)：系统建立了移位寄存器序列（尤其是 m-序列）的理论。m-序列具有“移位-加”性质（shift-and-add property），即序列与自身任何非平凡移位相加，得到另一个非平凡移位。这是伪随机阵列的核心性质来源。
   • MacWilliams & Sloane (1976)：在经典教材中总结了 de Bruijn 序列的构造与性质。一维情形已完全解决：对于任意长度 n，存在 de Bruijn 序列，且可通过 LFSR 构造出具有“移位-加”性质的伪随机序列（即 m-序列）。

2. 主要进展：从一维到二维——伪随机阵列的构造

   • MacWilliams & Sloane (1976) 也提出了“折叠”（folding）的思想：将一个一维伪随机序列按某种方式排列成二维阵列。如果折叠方式得当，得到的阵列就是伪随机阵列（每个 n1 × n2 非零窗口恰好出现一次）。这是本文构造方法的核心。
   • Etizon & Vardy (1998) 等后续工作：系统研究了伪随机阵列的构造与性质，给出了基于有限域上迹函数（trace function）的显式构造。这些阵列继承了 m-序列的“移位-加”性质，并具有优良的互相关性质。但参数 (r1, r2, n1, n2) 受限于有限域的大小，例如 r1 * r2 = 2^m - 1 且 n1 * n2 = m 等。

3. 当前 Frontier：从单个阵列到阵列码

   • 本文声称，此前的工作几乎全部集中在构造单个伪随机阵列上。而“伪随机阵列码”（多个阵列的集合，每个 n1 × n2 非零矩阵恰好作为窗口出现在某个阵列中一次）的构造与验证，是一个未被系统研究的问题。
   • 本文的位置：本文是“On de Bruijn Array Codes”系列的第二部分。第一部分（同一作者，可能已发表或同时投稿）建立了 de Bruijn 阵列码（不要求线性、不要求“移位-加”性质）的一般理论。本文则聚焦于具有线性结构和“移位-加”性质的伪随机阵列码，提出了新的构造方法（基于折叠）和两种验证技术。

子线索聚类

这些被引文献大致落在两条子线索上：

• 线索一：序列设计与编码理论（Golomb, MacWilliams & Sloane, 以及 LFSR 相关文献）。这一簇关注一维伪随机序列（m-序列）的代数构造、性质（移位-加、互相关）及其在通信与密码学中的应用。这是本文的工具来源。
• 线索二：二维阵列构造与组合设计（Etizon & Vardy, 以及 de Bruijn 阵列相关文献）。这一簇关注如何将一维序列推广到二维，构造具有特定窗口性质的阵列。本文是这一簇的直接延伸，将其从“单个阵列”推广到“阵列码”。

这个方向在追问的核心问题

1. 存在性问题：对于给定的参数 (r1, r2, n1, n2)，伪随机阵列（或阵列码）是否存在？必要条件是什么（如 r1 * r2 = 2^(n1*n2) - 1 对于二元阵列）？
2. 构造方法：如何系统性地构造出所有可能的伪随机阵列（码）？现有的折叠方法能否覆盖所有参数？能否构造出具有额外理想性质（如线性、移位-加）的阵列码？
3. 验证问题：给定一个通过折叠构造出的阵列（或阵列集），如何高效地验证它确实是伪随机阵列（或码）？暴力枚举所有 n1 × n2 窗口的复杂度太高，需要更聪明的代数或组合验证方法。

⚠️ 作者的 framing

• 作者把缺口 frame 成什么：作者声称，尽管伪随机阵列的构造已有大量研究，但伪随机阵列码（即多个阵列的集合）的构造与验证是一个“未被探索的领域”（unexplored area）。他们将此作为本文的核心贡献，并强调其构造方法（折叠）是通用的，可以系统性地产生新参数。
• 哪些竞争路线被他淡化或回避了：作者完全回避了非构造性存在性证明（如概率方法）或计算机搜索的路线。他们的方法完全基于有限域上的代数构造。对于参数不满足 r1 * r2 = 2^m - 1 这种代数结构的情形，本文没有提供任何构造或讨论。
• 什么明显该被引 / 该存在、却没出现在 intro 里？：本文的参考文献列表非常短（约 10 篇），且全部是编码理论/组合设计领域的经典或近亲工作。没有引用任何关于二维 de Bruijn 序列的计算机搜索算法或更一般的组合设计理论（如拉丁方、正交数组）的文献。这可能意味着作者认为这些路线与他们的代数构造正交，或者这些领域本身对“阵列码”问题关注不多。值得研究者去查：是否存在用计算机搜索构造 de Bruijn 阵列（非码）的近期工作？如果有，它们的参数范围是否比代数构造更广？

张力

未见明显对立引用。该领域的发展是累积性的：从一维到二维，从单个阵列到阵列码，每一步都是在前人基础上自然延伸。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

• 符号：

  • r1, r2：阵列的行数和列数。我们构造的每个阵列是一个 r1 × r2 的二元矩阵。
  • n1, n2：窗口的行数和列数。我们关心的是阵列中所有可能的 n1 × n2 子矩阵（窗口）。
  • F_2：二元域 {0, 1}。所有阵列的元素都来自 F_2。
  • 伪随机阵列：一个 r1 × r2 的二元阵列 A，使得每个非零的 n1 × n2 二元矩阵恰好作为窗口在 A 中出现一次（考虑循环移位，即阵列的边界是卷起来的，形成一个环面）。
  • 伪随机阵列码：一个由 r1 × r2 二元阵列组成的集合 C（线性码，即 C 在加法下封闭），使得每个非零的 n1 × n2 二元矩阵恰好作为窗口出现在 C 中某个阵列的某个位置一次。
  • 移位-加性质：对于阵列 A，A 与它的任何非平凡循环移位相加，结果等于 A 的另一个非平凡循环移位。
  • 折叠：将一个长度为 L 的一维序列 s 映射到一个 r1 × r2 阵列 A 的映射，其中 A[i][j] = s[ (i * c1 + j * c2) mod L ]，c1, c2 是选定的步长。

• 模型：

  • 数据生成机制是确定性的代数构造。没有概率模型。
  • 已知：一个长度为 L = r1 * r2 的伪随机序列（m-序列）s，它具有“移位-加”性质，且每个长度为 m 的非零二元向量恰好作为连续子串出现一次。这里 m 是序列的“窗口长度”，满足 L = 2^m - 1。
  • 要构造的对象：一个 r1 × r2 的阵列 A，使得每个 n1 × n2 的非零窗口恰好出现一次。这里 n1 * n2 = m。

• 可观测数据：

  • 在构造阶段，我们“观测”到的是已知的 m-序列 s。
  • 在验证阶段，我们“观测”到的是构造出的阵列 A（或阵列集 C）。
  • 想要但观测不到：我们无法直接“看到”阵列 A 是否具有伪随机性质。我们需要通过验证技术来确认每个 n1 × n2 窗口是否恰好出现一次。暴力枚举所有窗口是可行的，但计算量大。作者提供了更高效的代数验证方法。

第二步：讲最小内核

本文的核心思路可以归结为一个最简特例：如何通过“折叠”一个一维 m-序列来构造一个二维伪随机阵列，并验证它？

最简特例： - 设 m = 3。那么一维 m-序列的长度 L = 2^3 - 1 = 7。一个例子是 s = [1, 0, 0, 1, 0, 1, 1]（这是一个 m-序列，每个长度为 3 的非零二元向量恰好出现一次）。 - 我们想构造一个 r1 × r2 的阵列，使得 n1 * n2 = m = 3。最简单的选择是 n1 = 1, n2 = 3（即窗口是 1×3 的行向量）或 n1 = 3, n2 = 1（即窗口是 3×1 的列向量）。但为了体现二维性，我们选 n1 = 1, n2 = 3，并设 r1 = 1, r2 = 7。这退化成了一维情况，没有意思。 - 更有趣的是选 n1 = 1, n2 = 3，但设 r1 = 7, r2 = 1，同样退化。 - 为了得到真正的二维阵列，我们需要 n1 > 1 且 n2 > 1。例如，设 n1 = 2, n2 = 2，那么 m = n1 * n2 = 4。此时 L = 2^4 - 1 = 15。我们需要一个长度为 15 的 m-序列。 - 构造：我们想把这个长度为 15 的序列 s 折叠成一个 r1 × r2 的阵列。一个经典选择是 r1 = 3, r2 = 5（因为 3 * 5 = 15）。折叠映射为：A[i][j] = s[ (i * 5 + j * 1) mod 15 ]，其中 i = 0,1,2，j = 0,1,2,3,4。这相当于把序列 s 按行优先顺序写入一个 3×5 的矩阵，但每行写完就换行。 - 验证：现在，我们声称这个 A 是一个伪随机阵列，即每个 2×2 的非零二元矩阵恰好作为窗口出现一次。如何验证？ - 暴力法：枚举所有 3×5 = 15 个可能的 2×2 窗口（考虑循环边界），检查它们是否覆盖了所有 2^4 - 1 = 15 个非零 2×2 矩阵。这可行，但计算量随阵列大小增长。 - 作者的验证技术：利用 m-序列的代数性质。因为折叠映射是线性的，阵列 A 中的每个 2×2 窗口对应序列 s 中一个长度为 4 的连续子串（但索引是跳跃的）。由于 s 本身是 m-序列，其所有长度为 4 的非零子串恰好出现一次。作者证明了，如果折叠参数选择得当（例如 r1 和 r2 互质，且与 L 满足某种关系），那么这种对应关系是一一对应的，从而阵列 A 的窗口性质自动成立。验证就转化为检查折叠参数是否满足这些代数条件。

核心思路：将二维阵列的窗口性质，归约到一维序列的窗口性质。只要折叠映射是“好的”（即一个双射，将二维窗口的集合一一对应到一维窗口的集合），那么一维序列的性质就直接保证了二维阵列的性质。验证一个阵列，就变成了验证一个代数条件（折叠参数是否满足要求），而不是枚举所有窗口。

三、这篇论文做了什么

三句话

1. 研究了什么问题：本文研究如何构造和验证伪随机阵列码（即具有线性结构和“移位-加”性质的 de Bruijn 阵列码），这是对单个伪随机阵列构造的系统性推广。
2. 核心工具 / 方法：核心方法是序列折叠（folding），即将一维伪随机序列（m-序列）通过一个线性映射排列成二维阵列，并进一步将这种构造推广到生成整个线性码（阵列集）。提出了两种验证技术，分别用于验证单个阵列和阵列码的伪随机性。
3. 主要结论：给出了新的伪随机阵列参数（例如，对于 n1=2, n2=2，构造了 r1=3, r2=5 的阵列），并首次系统构造了伪随机阵列码。验证技术被证明是有效的，并且可以应用于 VLSI 测试中的模式生成。

关键设定与假设

• 设定：所有阵列和序列的元素都来自二元域 F_2。阵列的边界是循环的（即考虑环面）。码 C 是线性的，即对加法封闭。
• 假设：
  1. 存在一个已知的 m-序列：构造的起点是一个长度为 L = 2^m - 1 的 m-序列，它具有“移位-加”性质。这是经典结论，无需证明。
  2. 折叠参数条件：折叠映射 A[i][j] = s[ (i * c1 + j * c2) mod L ] 需要满足特定条件，以确保它是一个从 Z_{r1} × Z_{r2} 到 Z_L 的双射。这通常要求 r1 和 r2 互质，且 L = r1 * r2。此外，为了将窗口性质从一维传递到二维，还需要 c1 和 c2 与 L 和窗口大小 n1, n2 满足某种“无歧义”条件（例如，c1 和 c2 在模 L 下是线性无关的，且与窗口的“形状”兼容）。
  3. 线性码的构造：对于阵列码，构造基于一个线性映射，将 m-序列的某个子空间映射到阵列码。这要求 m-序列本身是某个线性递归的输出。

主要结果

本文的主要结果是构造性和验证性的，而非理论下界。核心结果可以概括为：

• 定理 1（伪随机阵列的构造）：给定一个长度为 L = 2^m - 1 的 m-序列，以及满足特定条件的折叠参数 (r1, r2, c1, c2)（其中 r1 * r2 = L，n1 * n2 = m），通过折叠构造出的阵列 A 是一个伪随机阵列。直觉：折叠映射是一个双射，它将阵列中所有 n1 × n2 窗口的集合，一一对应到序列中所有长度为 m 的连续子串的集合。由于 m-序列的窗口性质，后者恰好包含每个非零 m 长向量一次，因此前者也恰好包含每个非零 n1 × n2 矩阵一次。
• 定理 2（伪随机阵列码的构造）：在上述构造的基础上，通过考虑 m-序列的所有循环移位（或更一般地，一个由 m-序列生成的线性子空间），并将每个移位独立地折叠成阵列，得到的阵列集合构成一个伪随机阵列码。直觉：m-序列的所有非平凡循环移位恰好覆盖了所有长度为 m 的非零向量一次（作为窗口）。将这些移位分别折叠，就得到了一个阵列码，其中每个非零 n1 × n2 矩阵恰好作为窗口出现在某个阵列中一次。
• 验证技术：
  • 技术一（验证单个阵列）：通过检查折叠参数是否满足一个代数条件（例如，一个关于 c1, c2, n1, n2 的矩阵是否满秩），来判定构造出的阵列是否为伪随机阵列。这避免了枚举所有窗口。
  • 技术二（验证阵列码）：类似地，通过检查一个更复杂的代数条件，来判定通过折叠 m-序列的线性子空间得到的阵列集是否为伪随机阵列码。

证明路线与技术技巧

• 整体路线：

  1. 建立双射：证明折叠映射 f: Z_{r1} × Z_{r2} → Z_L 是一个双射。这是所有后续论证的基础。
  2. 窗口对应：证明阵列 A 中的每个 n1 × n2 窗口，在折叠映射下，对应于序列 s 中一个长度为 m = n1 * n2 的连续子串（但索引是 f 的像）。关键在于证明这个对应关系是一一对应的：不同的窗口对应不同的子串，且所有可能的窗口恰好覆盖所有可能的子串。
  3. 利用 m-序列性质：由于 s 是 m-序列，其所有长度为 m 的非零连续子串恰好出现一次。结合步骤 2 的一一对应，立即得出阵列 A 的所有 n1 × n2 非零窗口恰好出现一次。
  4. 推广到码：对于阵列码，将步骤 2 和 3 中的“单个序列”替换为“由 m-序列生成的一个线性子空间”。证明该子空间中的所有序列（即所有非平凡循环移位）的窗口集合，恰好覆盖了所有非零 m 长向量一次。然后通过折叠，这个性质被传递到阵列码。

• 关键跳跃点：

  • 最吃功夫的引理：证明“窗口对应”是一一对应的。这需要仔细分析折叠映射的代数结构。难点在于，二维窗口的索引 (i, j) 到 (i+n1-1, j+n2-1) 在折叠后，对应到一维序列上的索引集合并不是一个简单的连续区间，而是一个“锯齿形”的集合。作者需要证明，这个锯齿形集合恰好覆盖了 Z_L 中的一个长度为 m 的连续区间（模 L），并且不同的二维窗口对应不同的连续区间。这依赖于 c1, c2, n1, n2 之间满足的特定数论条件（例如，c1 和 c2 在模 L 下生成的子群与窗口的“步长”兼容）。
  • 作者用什么办法绕过去：作者没有直接处理这个复杂的对应关系，而是将问题转化为一个线性代数问题。他们构造了一个 m × m 的矩阵，其行由窗口内每个位置的折叠坐标 (i * c1 + j * c2) mod L 的某种线性组合构成。然后证明，当且仅当这个矩阵是可逆的（在 F_2 上），窗口对应才是一一对应的。这样，一个复杂的组合问题就变成了一个简单的矩阵秩的检验。

• 技术技巧点名：

  • 有限域上的线性代数：整个证明的核心工具。m-序列的性质、折叠映射、窗口对应，全部用 F_2 上的向量空间和线性变换来描述。
  • 中国剩余定理：用于分析折叠映射 f 何时是双射。Z_{r1} × Z_{r2} 和 Z_L 之间的双射存在当且仅当 r1 和 r2 互质且 L = r1 * r2，这本质上是环 Z_L 与 Z_{r1} × Z_{r2} 的同构。
  • 矩阵秩的论证：将验证问题转化为检验一个特定矩阵是否满秩。这是本文验证技术的核心，使得验证变得高效。

真实例子与应用

• 例子：本文给出了一个具体的构造例子。例如，对于 n1 = 2, n2 = 2（窗口大小 2×2），m = 4，L = 15。他们选择 r1 = 3, r2 = 5，并给出了一个具体的 m-序列和折叠参数，构造出一个 3×5 的伪随机阵列。然后，他们通过检查矩阵秩来验证了这个阵列。
• 应用：作者指出，这些验证技术可以用于 VLSI 测试。在 VLSI 测试中，需要生成一组测试模式（即输入向量），使得每个可能的错误模式都能被检测到。伪随机阵列码恰好提供了一种生成这种测试模式的方法：每个阵列是一个测试模式集，而整个码覆盖了所有可能的非零错误模式。验证技术可以确保生成的测试模式集确实具有这种全覆盖性质。

🔎 结论是否比证明窄

• 是。本文的构造和验证技术严格依赖于存在一个已知的 m-序列。这意味着：
  • 参数 (r1, r2, n1, n2) 必须满足 r1 * r2 = 2^(n1*n2) - 1。这是一个非常强的限制。对于不满足这个等式的参数，本文的方法完全失效。
  • 构造出的阵列码是线性的，且具有“移位-加”性质。作者在结论中声称构造了“伪随机阵列码”，但并未声称构造了所有可能的伪随机阵列码。对于非线性的、或不具有“移位-加”性质的伪随机阵列码，本文没有提供任何构造或存在性讨论。
  • 论文的标题和摘要中“new parameters”的声称，需要放在这个限制下理解：他们只是找到了满足 r1 * r2 = 2^(n1*n2) - 1 的新的 (r1, r2) 分解，而不是找到了新的 (n1, n2) 组合。

四、开放问题

1. 打破参数限制：如何构造参数不满足 r1 * r2 = 2^(n1*n2) - 1 的伪随机阵列（码）？这是本文方法最根本的限制。是否存在非代数（如组合、概率）的构造方法？扎根于：本文所有构造都基于 m-序列，而 m-序列的长度必须是 2^m - 1。
2. 非线性阵列码：本文只考虑了线性码。是否存在有意义的非线性伪随机阵列码？它们的构造和性质如何？扎根于：本文的“伪随机阵列码”定义中包含了线性条件，但更一般的 de Bruijn 阵列码（第一部分）并不要求线性。
3. 验证技术的复杂度：本文的验证技术基于检查矩阵的秩，这已经是多项式时间。但对于非常大的阵列，是否存在更快的（例如，基于 FFT 或数论变换）验证方法？扎根于：本文的验证技术是代数验证，但未讨论其计算复杂度或优化。
4. 与统计学的潜在连接：伪随机阵列与空间统计中的“空间填充设计”或“均匀设计”有概念上的相似性。是否存在将这类代数构造应用于统计实验设计的可能性？扎根于：本文是纯编码理论工作，但“每个窗口恰好出现一次”的性质与某些实验设计中的“正交性”或“均匀性”要求有类比。这是一个非常弱的连接，需要研究者自己判断是否值得探索。

---

Maintained by 陈星宇 · Homepage · Source on GitHub

评论