附录：堆叠法
贺深泽 (Email：[email protected] )
1. 前言
Lin 堆叠法的基本功能是从现有较小运行数的正交超立方构造出较大的正交超立方（OHC）。 本文遵循 Lin 的思路，但从正交阵列的可堆叠性质出发，推导出真正基于堆叠模型的方法。
正交超立方的构造是一类 NP Hard 难题，十分困难。随着运行数 n 的增加，构造难度迅速地增加。 置换集 S 愈来愈庞大，正交解愈来愈难找，计算时间增长很快。 这种计算一般在较大的计算机上进行。即使再大的计算机都不能应对问题难度的增长的要求。 计算速度的增长永远追不上问题难度的增长。不断增加运行数，大运行数正交阵列最终还是猜想它存在却不能构造出来。 因此，Lin 方法具有重要意义。鉴于 Lin 等的堆叠法基于张量积模型，存在理论障碍，最终结果存在许多疑问。 本文给出一些改进尝试。
目前文献报道，直接法只可检索到 n=21 (C.D.Lin 2008,2010)。He (2009) 第一版(2005) 构造的正交超立方 运行数可以达到 n=33, 但受计算机计算速度制约，正交列数没有突破 5 列。第二版(2017)的结果示于表 1.
表 1. 现有直接法构造的 OHC(除标记* 者外，均为笔者构造)
下面叙述我的方案。
2 简单堆叠法
2.1 简单堆叠操作
一个 u×m 矩阵 A =(aij) 同另一个 v×m 矩阵 B=(bij) 按照上下的顺序组成一个 (u+v)×m 矩阵 ，约定为具有以下形式的一张表：
| a11,a12,...,a1m |
| a21,a22,...,a2m |
| ...,...,...,... |
| an1,an2,...,anm |
| b11,b12,...,b1m |
| b21,b22,...,b2m |
| ...,...,...,... |
| bn1bn2,...,bnm |
正交阵列有可堆叠性质，任何两个正交阵列堆叠起来仍然是正交的，参见 He (2009)。具有如下基本性质。
2.2 堆叠的基本性质 1
设 u×m 矩阵 A =(aij) 和 v×m 矩阵 B=(bij) 满足条件：aiTaj=0, biTbj=0, (i≠j; i,j=1,2,...,m), 且所有列向量的均值为 0, 即 所有向量的均值 a-i=0, b-i=0，则, S(A,B) 是零相关正交阵列。
这个证明很简单。设c =S(A,B),
因为 aiTaj=0, biTbj=0, i≠j; i=1,2,...,m; j=1,2,...,m.
所以，ciTcj=aiTaj+biTbj=0.
一个结果是：假设 A 是一个n×u 标准正交超立方，B 是一个(n+1)×v 标准正交超立方，m=min(u,v)，那么 C=S(A,B) 是一个(2n+1)×m 正交超立方. C 是一个标准化正交超立方。
例 1 设 A=OHC4h2o, B=OHC5h2o, C=S(A,B) 是一个OHC9h2o, C=(( 2,-4, 4, 0,-2, 3,-1, 1,-3)T,( 4,-2,-4, 2, 0,-1,-3, 3, 1,)T)
这种方法对于从小规模 OHC 构造某些较大规模 OHC 有时是有用的。
由此基本性质，两个正交阵列堆叠的结果是正交的。可以建立简单堆叠法。 但两个正交超立方堆叠的结果不一定再是正交超立方。 简单堆叠法的应用非常广，是堆叠法的基础，下文方法与此有关。我们将另文讨论其他应用。
2.3 堆叠的基本性质 2
设 A, B 都是零相关阵列，即，满足条件： aiTaj - ua-i a-j=0, biTbj - vb-i b-j=0, 其中，i≠j; i=1,2,...,m; j=1,2,...,m. 且所有列向量的均值相同, 即 a-i= b-i， 则, C=S(A,B) 是零相关阵列。
证明： 因为aiTaj - u a-i a-j=0, biTbj - vb-i b-i=0, 其中，i≠j; i=1,2,...,m; j=1,2,...,m. 则有，
(aiTaj - ua-i a-j + (biTbj - vb-i b-j= (aiTaj - biTbj) - (u a-i a-j+ vb-i b-i =ciTcj - (u+v) c-i c-j
这是一个充分而非必要的条件。
2.4 堆叠的基本性质 3
同维正交阵列具有可加性，可以与实数相乘，这些操作不影响其正交性。
A 和 B 又可以分别是一个复合结构，只要符合上述条件就不影响结果的正交性。 堆叠也具有递归运算能力，即被堆叠的矩阵可以是另一个堆叠结构。
3. 堆叠之和
3.1 堆叠之和操作
有各种各样的复合结构。本节我们只讨论两个堆叠之和，
为便于表达，我们把这个结构用一个符号表示，这里要注意简单堆叠与堆叠之和符号的区别。
这个结构有一个特性，不管 A,B 是怎样的两个 n×m 矩阵，(αS(A,A))T(βS(B,-B))=0 恒成立。
定理 3.1 设 A,B 是两个 n×m 零相关正交阵列，S(α,β,A,B) 就一定是零相关正交阵列。
证明： 记 X=S(A,A), Y=S(B,B), 则，XTX=YTY = In, XTY=YTX =0
(X+Y)T(X+Y)=(XT+YT)(X+Y)=XTX+YTY+XTY+YTX = 2In .
推论 3.1 当 A, B 都是 n×m 零相关正交阵列时，(3.1) 中的 C 是一个 2n×m 零相关正交阵列。
推论 3.2 设 A,B 是两个 n×m 零相关正交阵列，α, β 是两个实常数， 那么
但是，要注意，在适用系统模型上，(3.2) 和 (3.3) 不同。 (3.2) 是两个简单堆叠之和，而 (3.3) 是矩阵之和与差的简单堆叠。
(3.3) 指出了 C=(cij)2n×m 的元素的结构：
容易理解， αaij+βbij 是将 aij 先拉伸 α 倍，然后平移量 βbij， 其中，βbij 是将bij 拉伸了β 倍。
定理 3.3. 设在(3.1) 式中的 A 为 n×m 正交超立方，α 使 αA 为标准正交超立方, H 为以±0.5 为其两个水平的 n×m 二水平正交阵列，当且仅当 β= n 时，(3.1) 式中的 C 是正交超立方。
证明：
（1）. 证明当 β=n 时，(3.1) 中的 C 是正交超立方。
注意 H 为 “标准二水平正交阵列”，不含 0 水平， 绝对值最小的两个水平分别为 -0.5 和 0.5 (下同)。
由于 αA 为标准正交超立方，各列水平设计相同，研究其一个列，例如第 j 列。不妨假定 A 就是一个标准正交超立方，α=1, Δ=1。
因 hj 是 H 的第 j 列，所以 |hij|=1/2，|hijβ,|=β/2. 所有的 aij 都步进地平移距离 β/2，hij>0 时向右，hij<0 时向左。
由(3.4)和 (3.5), 每个 aij 在堆叠操作 S(A,A) 的两个 A 中各出现一次， hij 有±0.5 两种状态，则 aij+βhij 有四种可能的状态： 当处在上方的 aij 做加法时，对应于下方的那个就执行减操作, 反之，当处在上方做减法时，对应于下方的那个就执行加操作。 所以只可能取 aij±β/2,(i=1,2,...,n) 两个值，参见表 2。 因此，Li 的每个水平分点各执行加减 β/2 一次也只执行一次，每一点都步进地平移同一距离 β/2 。 特别注意四个点 -(n-1)/2, -0.5, 0.5, (n-1)/2 的行为。当β=n, 参见图 1.
表 2. β=n 时，四个点中每个点的两种状态
| aij+β/2 | aij-β/2 |
|---|---|
| -(n-1)/2+n/2=0.5 | -(n-1)/2-n/2=-(2n-1)/2 |
| -0.5+n/2=(n-1)/2 | -0.5-n/2=-(n+1)/2 |
| 0.5+n/2=(n+1)/2 | 0.5-n/2=(n-1)/2 |
| (n-1)/2+n/2=(2n-1)/2 | (n-1)/2-n/2=-0.5 |
图 1. 堆叠过程中向量分量的平移变化示意图。
cj 的定义域恰好是 [-(2n-1)/2,(2n-1)/2]，每个分点的距离 Δ=1, C 是一个超立方。 如果 A 是正交超立方，C 就是正交超立方。
（2）. 证明当 β≠n 时，(3.1) 中的 C 不是正交超立方。
当 β<n, 例如，β=n-k , 其中 k>0 为整数，四个点的移动结果为
| aij+β/2 | aij-β/2 |
|---|---|
| -(n-1)/2+(n-k)/2=-(k-1)/2 | -(n-1)/2-(n-k)/2=-n+(k+1)/2 |
| -0.5+(n-k)/2=(n-k-1)/2 | -0.5-(n-k)/2=-(n-k+1)/2 |
| 0.5+(n-k)/2=(n-k+1)/2 | 0.5-(n-k)/2=(n-k-1)/2 |
| (n-1)/2+(n-k)/2=n-(k+1)/2 | (n-1)/2-(n-k)/2=(k-1)/2 |
cj 的定义区间为 [-n+(1+k)/2, n-(1+k)/2]。 参考图 1，cj 的定义区间的左右两个端点将向内收缩，其内的所有分点都会平行移动。其间某些值相同，这意味着在 0 点两侧的某些点将重迭。例如，k=1 时，出现了0 水平，它是两个点 -0.5，0.5 各平移 0.5 的重合点。 而 ±0.5 的两个点将不复存在。K 越大，重迭的点越多。虽然 C 是正交的，但每个因子的中间水平出现了不等距现象，一些水平重叠了。 它不符合超立方的定义。
当 β=n+k>n 时, 其中 k>0 为整数。四个点的移动结果见表 4。
| aij+β/2 | aij-β/2 |
|---|---|
| -(n-1)/2+(n+k)/2=(k+1)/2 | -(n-1)/2-(n+k)/2=-n-(k-1)/2 |
| -0.5+(n+k)/2=(n+k-1)/2 | -0.5-(n+k)/2=-(n+k+1)/2 |
| 0.5+(n+k)/2=(n+k+1)/2 | 0.5-(n+k)/2=-(n+k-1)/2 |
| (n-1)/2+(n+k)/2=n+(k-1)/2 | (n-1)/2-(n+k)/2=-(k+1)/2 |
cj 的定义区间长度将大于 [-n+1/2,n-1/2], 两个端点将向外平移，其内的所有分点，包括 -0.5,0.5 两点都会移动， 绝对值最小的两个点分别变成 -(k+1)/2, (k+1)/2，在 0 点两侧将出现水平空缺。 绝对值最大的两个点分别为 -n-(k-1)/2, n+(k-1)/2， 中间空缺 k 个水平，不符合超立方的定义。
在上述讨论中，把二水平矩阵的两个水平定义为 ±0.5, 目的在于β 的取值是整数， 恰好 β=n 时，堆叠的结果矩阵的运行数为 2n，当需要嵌入的矩阵的运行数为奇数时， β 设置为对应奇数即可。这样便于理解，也便于记忆。
4. 二重复合堆叠
由前节的定理 3.3, 在式 (3.1) 中，当选取 α 使 A 成为 n×m 正交标准超立方，而选取 β>n， H 为以±0.5 为其两个水平的 n×m 二水平正交阵列时，C 是正交的，但不是正交超立方，中心点 0 两侧有一段水平空缺。 空缺水平数为 k=β-n。如果存在一个 k×m OHC, 则 S(OHCk×m,S(α,βA,H)) 是一个 OHC(2n+k)×m。 如果要构建一个大运行数 OHCu×m 而不能通过一次堆叠和得到，可以采用二重复合堆叠的方法。 将 u 分解成 k+2n, 使其中的 n 是 4 的倍数，而 OHC(2n+k)×m 具有最大的 m 值。 因为目前由 Steinberge,D.M. 和 Lin,D.K.J 构造的一个 OLHD16×12 具有最大的正交饱和度， 是堆叠和中选取 A 的最好 OHC，将有非常高的利用率。我们简称作 SL12，将根据需要从中截取适当的列数。 如果SL后面跟的整数小于12，那是截取的结果。 注意，这里的 H 总是与 A 的规模相匹配，所以，H 的规模省略不写。 用外延生长的方法使堆叠的结果是OHC。其结果存在的问题很多，详见第 3.3 节。基于这一思想，改外延一个正交设计为内嵌一个OHC。这个过程由两次堆叠完成，第一次完成一次堆叠和S(α,β,A,H)，然后完成一次简单堆叠。其中的 OHC 从现有直接法构成的 OHC 中选取或递归使用既已构造的 S(α,β,A,H)。表 1 标明现有最好的 OHC 各运行数对应的正交列数。 例 2 ，要构造 OHC51，51=19+2*16，OHC51h7o=S(OHC19h7o,S(1,16,SL7,H)), 它将有 7 个正交列。 例 3 ，要构造 OHC69，有两种方案，69=32×2+5 , 结果因运行数为 5 的 OHC 只有 2 列，而 69=21+24*2 可以得到 7 个正交列的 OHC69h7o。以此类推。 表 5 是运行数在 32 至 93 的 OHC 的构造方案。| Stacking Ways | Runs | 正交列数 |
| S(1,16,SL12,H) | 32 | 12 |
| S(0,S(1,16+1,SL12,H)) | 33 | 12 |
| 34 | ||
| Directly constructed | 35 | 6 |
| Directly constructed | 36 | 6 |
| Directly constructed | 37 | 6 |
| 38 | ||
| S(OHC15h6o,S(1,12+15,OHC12h6o,H)) | 39 | 6 |
| S(SL6,S(1,12+16,OHC12h6o,H)) | 40 | 6 |
| S(OHC17h6o,S(1,12+17,OHC12h6o,H)) | 41 | 6 |
| 42 | ||
| S(OHC11h7o,S(1,16+11,SL7,H)) | 43 | 7 |
| S(OHC12h6o,S(1,16+12,SL6,H)) | 44 | 6 |
| S(OHC13h6o,S(1,16+13,SL6,H)) | 45 | 6 |
| 46 | ||
| S(OHC23h7o,OHC24h7o) | 47 | 7 |
| S(SL16h12o,S(1,16+16,SL12,H)) | 48 | 12 |
| S(OHC24h7o,OHC25h7o) | 49 | 7 |
| 50 | ||
| S(OHC19h7o,S(1,16+19+20,SL7,H)) | 51 | 7 |
| S(OHC20h6o,S(1,16+20,SL6,H)) | 52 | 6 |
| S(OHC21h7o,S(1,16+21,SL7,H)) | 53 | 7 |
| 54 | ||
| S(OHC23h7o,S(1,16+23,SL7,H)) | 55 | 7 |
| S(OHC24h7o,S(1,16+24,SL7,H)) | 56 | 7 |
| S(OHC25h7o,S(1,16+25,SL7,H)) | 57 | 7 |
| 58 | ||
| S(OHC27h6o,S(1,16+27,SL6,H)) | 59 | 6 |
| S(OHC28h7o,S(1,16+28,SL7,H)) | 60 | 7 |
| S(OHC29h6o,S(1,16+29,SL6,H)) | 61 | 6 |
| 62 | ||
| S(OHC31h6o,S(1,16+31,SL6,H)) | 63 | 6 |
| S(1,32,OHC32h12o,H) | 64 | 12 |
| S(0,S(1,32+1,OHC32h12o,H)) | 65 | 12 |
| 66 | ||
| S(OHC19h7o,S(1,24+19,OHC24h7o,H)) | 67 | 7 |
| S(OHC20h6o,S(1,24+20+20,OHC24h6o,H)) | 68 | 6 |
| S(OHC21h7o,S(1,24+21,OHC24h7o,H)) | 69 | 7 |
| 70 | ||
| S(OHC23h7o,S(1,24+23,OHC24h7o,H)) | 71 | 7 |
| S(OHC24h7o,S(1,24+24,OHC24h7o,H)) | 72 | 7 |
| S(OHC25h7o,S(1,24+25,OHC24h7o,H)) | 73 | 7 |
| 74 | ||
| S(OHC11h7o,S(1,32+11,OHC32h7o,H)) | 75 | 7 |
| S(OHC20h6o,S(1,28+20,OHC28h6o,H)) | 76 | 6 |
| S(OHC21h6o,S(1,28+21,OHC28h7o,H)) | 77 | 7 |
| 78 | ||
| S(OHC23h7o,S(1,28+23,OHC28h7o,H)) | 79 | 7 |
| S(SL12,S(1,32+16,OHC32h12o,H)) | 80 | 12 |
| S(OHC25h6o,S(1,28+25,OHC28h7o,H)) | 81 | 7 |
| 82 | ||
| S(OHC19h7o,S(1,32+19,OHC32h7o,H)) | 83 | 7 |
| S(OHC20h6o,S(1,32+20,OHC32h6o,H)) | 84 | 7 |
| S(OHC21h7o,S(1,32+21,OHC32h6o,H)) | 85 | 7 |
| 86 | ||
| S(OHC23h7o,S(1,32+23,OHC32h7o,H)) | 87 | 7 |
| S(OHC24h7o,S(1,32+24,OHC32h7o,H)) | 88 | 7 |
| S(OHC25h7o,S(1,32+25,OHC32h7o,H)) | 89 | 7 |
| 90 | ||
| S(OHC43h7o,S(1,24+43,OHC24h7o,H)) | 91 | 7 |
| S(OHC28h7o,S(1,32+28,OHC32h7o,H)) | 92 | 7 |
| S(OHC29h6o,S(1,32+29,OHC32h6o,H)) | 93 | 6 |