1. 项目概述从“完美”的局限到“实用”的突破在通信与信号处理领域寻找具有理想自相关特性的序列一直是个既经典又充满挑战的课题。Golay互补对Golay Complementary Pair, GCP无疑是这个领域的明珠——一对序列其各自的自相关函数之和除了零时延点外其余位置全部为零。这种“完美”的互相关抵消特性让GCP在正交频分复用OFDM系统中大放异彩成为抑制高峰均功率比PAPR的利器。然而传统GCP构造方法大多被束缚在长度为2的幂次如2, 4, 8, 16…这个“舒适区”内并且序列的取值元数也常常局限于二元±1。现实世界的系统设计需求却是灵活多样的可能需要特定长度的导频序列来匹配信道估计需求或者需要非二元的相位序列来承载更多信息。当工程师面对一个要求序列长度为12或20的OFDM符号设计时传统二元2幂次长度的GCP就显得捉襟见肘了。“基于扩展布尔函数的非2幂次长度q元Golay互补对构造方法”这个课题正是为了打破这两重枷锁一是突破长度的2幂次限制二是将序列从二元推广到q元通常q为2的幂次对应多相制信号。其核心价值在于它提供了一套系统性的数学工具扩展布尔函数让我们能够按需“定制”出各种长度、各种元数的Golay互补对从而将这种优异的信号特性应用到更广泛的通信、雷达乃至密码学场景中。如果你正在设计新一代的通信协议、寻找低相关性的编码序列或者对离散数学在工程中的应用感兴趣那么理解这套构造方法的脉络无疑会为你打开一扇新的大门。2. 核心原理扩展布尔函数如何编织出“互补”的图案要理解这个构造方法我们必须先深入到两个核心概念的内部什么是Golay互补对的数学本质扩展布尔函数又扮演了怎样的角色2.1 Golay互补对的数学刻画与q元扩展首先我们明确一下q元序列。一个长度为N的q元序列A可以表示为A [a_0, a_1, ..., a_{N-1}]其中每个元素a_k是q次单位根即a_k exp(2πi * c_k / q)c_k ∈ {0, 1, ..., q-1}i是虚数单位。当q2时就退化为我们熟悉的二元序列[1, -1]。序列A的非周期自相关函数R_A(τ)定义为R_A(τ) Σ_{k0}^{N-1-τ} a_k * conj(a_{kτ}), 当0 ≤ τ N。 其中conj()表示复共轭。对于一对序列(A, B)如果它们满足以下互补条件R_A(τ) R_B(τ) 0 对于所有τ ≠ 0。 那么(A, B)就构成了一个Golay互补对。在τ0时R_A(0) R_B(0) 2N即总能量。这个条件的物理意义非常直观单个序列的自相关函数可能有较高的旁瓣但这一对序列的旁瓣恰好正负抵消总和为零。在OFDM中每个子载波可以看作一个序列元素使用GCP作为调制相位可以有效避免多个子载波信号同相叠加产生极高的瞬时功率从而降低PAPR。2.2 扩展布尔函数从布尔域到复数域的桥梁布尔函数f(x_1, x_2, ..., x_m)将m个二进制变量映射到{0, 1}。而扩展布尔函数也称为广义布尔函数或复值布尔函数则将这个映射扩展到了复数域更具体地说是映射到q次单位根上。其形式通常为f(x) (q/2) * (∑_{i1}^{m} a_i x_i ∑_{1≤ij≤m} b_{ij} x_i x_j ... c) mod q其中系数a_i, b_{ij}, ... , c是模q的整数。然后通过ω_q^f(x)ω_q exp(2πi/q)生成一个复数序列。这里的关键在于通过精心设计这个多项式f(x)的系数即布尔函数的代数正规型我们可以直接控制最终生成序列的相关特性。Golay互补对的构造本质上就转化为寻找一对具有特定代数结构的扩展布尔函数。传统方法如Rudin-Shapiro构造对应着一种特殊的二次型扩展布尔函数但其天然产出长度是2^m。我们的目标是设计更一般的多项式形式使其在变量数m确定时能生成长度N不等于2^m的序列。注意扩展布尔函数中的“模q”运算是核心。它保证了函数值始终是整数进而通过指数映射成为单位根。不同的系数组合相当于在单位圆上选择了不同的相位点。2.3 构造的核心思想可控的“折叠”与“填充”如何实现非2幂次长度一个核心技巧是引入“哑变量”或进行“变量折叠”。假设我们需要一个长度为N 2^{m-1} * L的序列其中L是奇数比如3, 5, 6等。我们可以从m个变量的扩展布尔函数出发但不对所有2^m个可能的输入赋值。相反我们只取其中特定的N个输入组合。这可以通过在布尔函数中引入特定的线性约束来实现。例如构造长度N12 (2^2 * 3)。我们可以从m4个变量(x1, x2, x3, x4)的扩展布尔函数开始。标准的GCP构造会生成一对长度为16的序列。为了得到12我们需要“舍弃”4个点。但随意舍弃会破坏互补性。因此我们需要设计函数f(x)使得当变量满足某个线性方程如x1 ⊕ x2 0时序列A和B在对应的位置上具有某种对称性从而在剔除这些位置后剩余长度为12的子序列依然保持互补特性。另一种等价且更系统的观点是我们实际上是在构造一个定义在更小群而非完全的布尔超立方体上的扩展布尔函数。这个群的大小就是目标长度N。构造的通用步骤框架如下确定目标参数明确所需序列长度N和元数q。将N分解为N 2^{m-d} * L的形式其中L是奇数d是待定的“折叠”维度。设计扩展布尔函数形式构建一个关于m个变量的扩展布尔函数f(x)。其多项式包含线性项、二次项可能还有更高次项。系数需要满足一系列由互补性条件推导出的代数方程。施加线性约束引入d个线性约束方程如∑_{i∈I} x_i 0这些约束定义了一个维度为(m-d)的仿射子空间。该子空间上的点数正好是2^{m-d}。再结合对部分变量的取值进行“复制”或“周期延拓”以匹配因子L最终得到总长度为N的定义域。求解系数条件将Golay互补对的数学条件自相关函数之和为零转化为关于扩展布尔函数系数a_i, b_{ij}, c的方程组。求解这个方程组得到一系列可行的系数组合模板。生成序列对将满足约束的所有输入点x代入函数f(x)和其互补函数g(x)通常g(x) f(x) (q/2)*x_1或类似形式通过映射ω_q^{f(x)}和ω_q^{g(x)}生成最终的q元序列对(A, B)。3. 方法拆解一步步走进构造的细节让我们以一个相对具体的例子来感受这个过程。假设我们的目标是构造一对q4元四相制、长度N12的Golay互补对。3.1 步骤一参数分析与函数框架设立长度N12。我们将其写为12 2^2 * 3。这里2^{m-d} 2^2所以m-d 2。L3。为了有足够的自由度我们选择m4那么d m - (m-d) 2。这意味着我们需要引入2个线性约束将4维布尔超立方体16个点“折叠”到一个2维的仿射子空间4个点上再通过某种方式将每个点扩展为3个值从而得到12个点。我们定义四个布尔变量x1, x2, x3, x4 ∈ {0,1}。目标扩展布尔函数的形式设为f(x) (2)*(c0 c1*x1 c2*x2 c3*x3 c4*x4 c12*x1*x2 c13*x1*x3 c14*x1*x4 c23*x2*x3 c24*x2*x4 c34*x3*x4) mod 4其中系数c_i, c_ij ∈ {0,1,2,3}。因为q4所以系数模4。3.2 步骤二引入约束定义有效定义域我们需要两个线性约束来定义一个2维子空间。例如选择约束1: x1 ⊕ x3 0即x1 x3约束2: x2 ⊕ x4 0即x2 x4 满足这两个约束的(x1,x2,x3,x4)组合只有4种(0,0,0,0),(0,1,0,1),(1,0,1,0),(1,1,1,1)。这对应了长度为4的“骨架”。为了将长度扩展到124*3我们采用“复制并施加相位旋转”的策略。具体来说我们对每个骨架点让变量x1或x2在三个不同的“相位状态”下取值。更优雅的做法是引入一个模3的索引t ∈ {0,1,2}并重新解释我们的函数定义域。我们可以将序列索引n (0 ≤ n 12)唯一地表示为n 4 * t s, 其中t 0,1,2,s 0,1,2,3。 然后将s用2位二进制表示(s1, s0)并令x1 s1,x2 s0,x3 s1(由约束1),x4 s0(由约束2)。 同时将索引t作为一个加性相位项引入函数。因此我们重新定义扩展布尔函数为f(t; s1, s0) (2)*[ 基函数(s1, s0) λ*t ] mod 4。 其中基函数(s1, s0)就是前面f(x)在约束下的简化形式λ是一个待确定的模4整数系数控制着三个“副本”之间的相位差。3.3 步骤三建立并求解互补性方程Golay互补条件R_A(τ) R_B(τ) 0 (τ≠0)可以转化为在函数域上的一个条件。对于由扩展布尔函数f和g生成的一对序列其互补性等价于以下等式对于所有非零时延τ对应的输入对(x, y)成立ω_q^{f(x)-f(y)} ω_q^{g(x)-g(y)} 0。 通常我们选取g(x) f(x) (q/2)*x_k即互补序列的函数是原函数加上一个特定变量的线性项模q。对于q4q/22。我们不妨设g(x) f(x) 2*x1。将f和g的表达式代入上述条件。经过一系列代数运算涉及单位根的和差化积这个条件可以简化为关于f的二次型差分方程。对于我们的参数化形式f(t; s1,s0)这个方程会分解为一系列关于系数c_i, c_ij和λ的模4同余方程。例如考虑时延τ对应t相同但(s1,s0)不同的情况序列“骨架”内部的相关以及t不同的情况“副本”之间的相关。通过系统性地列出所有可能的(x,y)对满足索引差为τ我们可以得到一组方程。这是一个关键且繁琐的步骤。通常我们会借助计算机代数系统如Mathematica, SageMath来符号求解。求解的目标是找到一组非平凡的系数解。一个经典的解可能形如基函数f_base(s1,s0) (2)*(s1 s0 s1*s0) mod 4。相位因子λ 1。因此完整函数f(t; s1,s0) [2*(s1 s0 s1*s0) 2*t] mod 4。互补函数g(t; s1,s0) f(t; s1,s0) 2*s1。实操心得手动推导全部方程几乎不可行尤其是对于更大的N和q。必须借助符号计算工具。核心是正确定义索引映射n - (t, s1, s0,...)和函数形式然后让程序生成并求解方程。验证解的正确性时可以先小规模枚举生成序列直接计算其自相关函数之和进行验证。3.4 步骤四序列生成与验证一旦得到系数解生成序列就变得直接。我们遍历所有t ∈ {0,1,2}和(s1,s0) ∈ {(0,0),(0,1),(1,0),(1,1)}共12个索引。 对于每个(t, s1, s0)计算f_val (2*(s1 s0 s1*s0) 2*t) mod 4。计算g_val (f_val 2*s1) mod 4。序列元素为A[n] ω_4^{f_val} i^{f_val}B[n] ω_4^{g_val} i^{g_val}其中i是虚数单位。例如当(t,s1,s0)(0,0,0)f_val0,g_val0。A[0]1,B[0]1。当(t,s1,s0)(0,0,1)f_val (2*(010)) mod 4 2,g_val(20) mod 42。A[1]-1,B[1]-1。当(t,s1,s0)(1,0,0)f_val (0 2*1) mod 4 2,g_val2。A[4]-1,B[4]-1。 以此类推计算出全部12个元素最后必须编写一个简单的脚本计算序列A和B的非周期自相关函数R_A(τ)和R_B(τ)并验证对于τ1,2,...,11是否恒有R_A(τ) R_B(τ) 0。这是检验构造是否成功的金标准。4. 构造方法的关键变体与优化策略上述示例展示了一种基于变量约束和索引分解的构造思路。在实际研究中还有多种等效或更强大的形式化方法。4.1 基于交织迭代的构造法这是另一种非常直观的构造非2幂次长度GCP的方法。其核心思想是已知一个较短长度的GCP(A, B)通过特定的交织Interleaving和相位旋转规则构造出一个更长长度的GCP(C, D)。设(A, B)是长度为N的GCP。定义长度为2N的新序列对(C, D)如下C A || (φ * B)连接D A || (-φ * B)或者D (ψ * B) || (ξ * A)等不同形式。 其中||表示连接φ、ψ、ξ是单位根q次根。通过精心选择旋转相位φ等可以证明(C, D)也是GCP。要得到非2幂次长度我们可以从一个短的非2幂次长度GCP可能是通过搜索得到的作为种子通过多次交织迭代生成一系列更长的、长度呈倍数增长但仍非2幂次的GCP。例如从一个长度为6的GCP如果存在出发通过交织可以生成12, 24, 48等长度的GCP。这种方法的优势在于结构清晰生成规则简单易于硬件或软件实现。保持特性如果种子序列有其他好特性如低互相关迭代后的序列可能仍保留。缺点需要先有一个种子非2幂次GCP。而寻找这样的种子本身可能就是通过扩展布尔函数方法完成的。4.2 利用Zadoff-Chu序列的变换Zadoff-Chu序列本身具有理想的自相关特性但并非Golay互补对。有研究通过将Zadoff-Chu序列进行特定的分段共轭反转操作可以构造出Golay互补对。对于长度为合数N L * M的情况这种方法有时能系统地产生非2幂次长度的GCP。其基本操作是给定一个Zadoff-Chu序列Z将其分成L段每段长度为M。然后对其中某些段进行共轭、反转或共轭反转操作并将这些处理后的段重新排列形成一对新的序列。在满足特定条件下这对新序列就是GCP。这种方法与扩展布尔函数的联系在于Zadoff-Chu序列的相位函数本身可以看作一种特殊的扩展布尔函数或更一般的定义在整数环上的函数。因此这种构造法可以纳入更广义的框架下理解。4.3 计算机搜索与代数验证结合对于中小长度的非2幂次q元GCP一种务实的方法是启发式计算机搜索。我们可以将扩展布尔函数的系数作为搜索变量将Golay互补条件作为约束利用优化算法如爬山法、模拟退火或穷举对于非常小的参数空间来寻找解。搜索策略的关键是缩小空间利用对称性Golay互补对具有多种对称性如交换、取反、全局相位旋转等这些对称性对应了系数空间的等价类。只需在每个等价类中搜索一个代表即可。设定标准型通过变量代换可以将扩展布尔函数化为某种“标准型”减少自由变量的数量。分层搜索先固定线性项系数搜索二次项系数或者先搜索二元q2情况再推广到q元。一旦通过搜索找到一个候选解必须用严格的代数方法验证它是否满足所有时延下的互补条件而不仅仅是测试几个随机时延。这通常需要借助符号计算来完成证明。注意事项纯粹的暴力搜索只能解决非常小规模的问题例如长度小于20q2或4。对于更大参数必须依赖本文所述的代数构造方法。搜索更多是用于发现新的构造模式或验证猜想。5. 实际应用中的考量与问题排查将理论上的构造方法应用于实际工程会面临一系列具体问题。5.1 参数选择对系统性能的影响构造出GCP只是第一步如何选择适合特定应用的(N, q)组合至关重要。长度N的选择在OFDM中序列长度N通常对应一个OFDM符号内的子载波数量或一个簇。N需要与FFT点数、循环前缀长度、信道相干带宽等因素匹配。非2幂次长度提供了更大的灵活性。例如在LTE或NR中某些参考信号资源块大小为12那么长度12的GCP就非常合适。元数q的选择q决定了每个序列元素能承载的相位状态数。q2BPSK最简单功率归一化方便但信息密度低。q4QPSK能携带两倍信息但会略微增加PAPR因为信号点不在一个圆上。更高的q如8-PSK, 16-PSK能承载更多信息但对功率放大器的线性度要求更高且可能削弱PAPR抑制效果。通常q4是一个在PAPR抑制性能、信息承载量和实现复杂度之间较好的折衷。5.2 硬件实现中的量化与存储在FPGA或ASIC中实现q元GCP序列发生器时需要关注相位量化生成的复数序列ω_q^k需要量化为有限位宽的定点数如16位存储。这会引入量化误差破坏理论上的完美互补性。需要评估量化后自相关旁瓣的抬高程度确保其仍在系统容限内。存储资源对于较长的序列直接存储整个序列会消耗ROM资源。更好的方法是实时计算。由于序列由扩展布尔函数f(x)生成而f(x)是一个多项式计算量很小。只需要存储少数几个系数然后根据索引n实时计算出n对应的变量取值(x1, x2, ...)和函数值f。这比存储整个长序列要节省得多。索引映射电路实现从线性索引n到布尔变量组(x1, x2, ...)的映射可能需要一个小的组合逻辑电路或查找表。这部分需要精心设计以保证时序。5.3 常见问题与排查技巧在实际构造和使用中可能会遇到以下典型问题问题1按照论文公式生成的序列验证自相关和不为零。可能原因1索引映射错误。这是最常见的问题。确保你的索引n(从0到N-1) 到布尔变量向量x的映射是一一对应且覆盖所有有效点的。检查约束条件是否应用正确t和s的分解是否无遗漏、无重复。可能原因2模运算处理不当。编程语言中%运算符对负数的处理可能与数学上的模运算不同。确保所有系数和函数值的模q运算结果都在{0, 1, ..., q-1}范围内。建议使用((a % q) q) % q或类似的确保非负的函数。可能原因3单位根计算误差。ω_q^k exp(2πi * k / q)。使用双精度浮点数计算时可能存在极小的浮点误差。在验证R_A(τ)R_B(τ)0时应判断其模长是否小于一个极小阈值如1e-10而不是直接判断是否等于0。排查步骤打印出前几个索引n对应的x向量、f(x)值、g(x)值以及计算出的序列值A[n],B[n]。手动验算是否正确。单独计算序列A和B的自相关函数R_A和R_B观察它们的旁瓣图案是否看起来像“互补”的大致相反数。将你的生成代码用于一个已知的、标准的2幂次长度GCP如Rudin-Shapiro序列进行测试确保基础计算模块正确。问题2构造出的序列PAPR抑制效果不理想。可能原因1序列的“互补性”仅存在于非周期自相关而OFDM中使用的是周期自相关不对。对于PAPR抑制使用的是序列本身作为频域数据经过IFFT后得到时域信号。其峰均比与序列的非周期自相关函数的“和”的傅里叶变换有关。Golay互补对的理论保证了最优的PAPR上界3 dB for BPSK。如果效果不理想首先确认你是在频域应用GCP序列并且IFFT点数与序列长度一致或通过补零扩展到IFFT点数。可能原因2q值过大或调制方式不匹配。如前所述高阶PSK会劣化PAPR性能。尝试换用q2或4的序列进行对比测试。可能原因3信道编码或扰码的影响。在实际系统中GCP序列可能经过信道编码或加扰这些操作可能会破坏其代数结构从而影响互补性。需要考虑将GCP构造与后续编码过程联合设计。问题3需要特定长度的GCP但找不到现成的构造公式。解决路径分解长度将目标长度N进行质因数分解。查看是否有已知的基于交织的构造法能用更短的因子长度组合出来。尝试通用框架使用本文第3节描述的通用框架。设定变量数m根据N2^{m-d}*L确定d。尝试不同的线性约束组合不一定是x1x3, x2x4可以是更一般的线性方程∑ a_i x_i b。然后建立方程利用符号计算工具如SageMath的整数环上的方程求解尝试求解系数。这是一个探索性过程。查阅最新文献非2幂次GCP是一个活跃的研究领域。在IEEE Xplore等数据库搜索“non-power-of-two length Golay”、“generalized Boolean function Golay”等关键词可能会找到针对特定长度的最新构造。个人经验从理论构造到实际仿真最脆弱的环节往往是“索引映射”。我习惯在代码中写一个详细的“debug”函数将前10个和后10个索引的生成过程以人类可读的格式打印出来并与手工推导的预期结果逐项对比。这个习惯帮我节省了大量调试时间。另外对于新的构造先用一个极短的长度比如N6去验证整个生成和验证流程的正确性再扩展到目标长度会稳妥得多。