Голеевские комплементарные (добавочные) пары массивов
Рассмотрены конструкции и условия не существования для многомерных Голеевских комплементарных (добавочных) пар массивов. Дана конструкция для d-размерной Голеевской пары массивов, из (d+1)-размерной пары массивов. Это используется для того чтобы объяснить и расширить известное прежде о конструкции и отсутствия результатов в двоичном случае.
Мы определяем длину s как одномерный массив A = (A[i]) из комплекснозначных вводных чисел, для которых:A[i] = 0 если i < 0 или i s.Обычно элементы последовательности ограничены и лежат в малом конечном множестве S называются алфавитной последовательностью. Если для какого-либо простого H-го корня из , тога А – это Н-фазная последовательность. Случаи, представляющий особый интерес – это бинарный случай, Н=2, для которого S = , и четвертичный, Н=4, для которого . Тройной случай - - это не Н-фазная последовательность, но она была достаточно хорошо изучена в последнее время. Апериодическая автокорреляционная функция длиной s последовательности A = (A[i]) задается выражением: для целого u,Где подчеркнутое представляет собой комплексное сопряжение.
С 1950-х годов инженеры цифровой связи пытались определить двоичные последовательности, для которых абсолютные значения апериодической автокорреляционной функции в общем мало, для применения в синхронизации, сжатия импульса, и в особенно в радиолокационных станциях.С этой точки зрения идеальная длинна s двоичной последовательности А, известная как код Баркера, это такая последовательность, для которой |CA(u)| 1, для всех u 0.Для неограниченной длины s, известны такие последовательности Баркера: 2,3,4,5,7,11 и 13, и в 1963 году было предположено, что другие последовательности не могут существовать. Поскольку очевидно, что идеальное поведение (идеальный режим) определяемое последовательностью Баркера вряд ли будет достигнуто до последовательности длинной 13, ученые исследовали некоторые вариации условий Баркера для бинарных кодов. К ним относятся последовательности с верхним ограничением максимального уровня боковых лепестков на целое число, большее 1, или стремящиеся максимально увеличить коэффициент качества . Другой подход, рассматриваемый здесь – это требование, чтобы сумма апериодических корреляционных функций пар, длинной s последовательностей A и B примеров идеального поведения: при всех Такие пары последовательностей называются Голеевскими комплементарными парами массивов длинной s. В предварительных исследованиях Голеевских пар массивов, рассматривался только бинарный случай. Бинарные Голеевские последовательности пар также известны для длин – 2 10 и 26. Можно получить бесконечно много бинарных последовательностей пар, следую этим правилам:Теорема 1. Если существует бинарная Голеевская последовательность для длин и , тогда существует бинарная Голеевская последовательность длинной .Следствие 2. Существует бинарная Голеевская последовательность пар длинной для целых .Предложение 3. Если существует бинарная Голеевская последовательность пар длинной , тогда s – целое.Доказательство. Для бинарной последовательности A длинной s, известно что: для всех целых удовлетворяющих условию Пусть A и B из бинарных Голеевских последовательностей пар длинной . Прибавим конгруэнтность A к конгруэнтности B, и установим , получим .Теорема 4. Если существует бинарная Голеевская пара длины s, тогда s – это не факторизация, конгруэнтная трем по модулю 4.Предложение 3 и теорема 4 включает в себя все известные теоретические сведенья о не существовании двоичных пар последовательностей Голея, в том числе то, что s должно быть суммой двух квадратов. Но следствие 2, пропозиция 3 и теорема 4 все же оставляют не решенными бесконечное множество значений s, для которых существование бинарной Голеевской последовательности пар длинной s.Борвейн и Фергюсон исчерпывающе расширили известное ранее при помощи компьютерных исследований для случаев при s<100.
После исследований Голея, некоторые авторы исследовали несколько больших алфавитов, включая тройной, четвертной, -фазный, Н-фазный для целых Н, и случай |A[i]| = 1 для . Недавно Фидлер, Джедваб и Паркер дали структурную основу для конструирования Н-фазных последовательностей, при целых Н, которые прежде были известны как -фазные Голеевские последовательностей пар, длинной , которые могут быть получены в точной алгебраической нормальной форме.
Мы описали один подход к последовательностям Баркера с явной нехваткой, а именно для замены одной последовательности парой последовательностей. Альтернативный подход заключается в обобщении А из одноразмерного в многоразмерный, в надежде на существование более богатой модели\схемы. Мы определяем S1 × • • • × Sr массив будет r-мерный массив A = (A [ . ]) комплекснозначных позиции, для которых:| ( , . . . , )| для всех ( , . . . , ) (0, . . . , 0).
Массив - это массив Баркера размера 2х2, но также бывают и другие размерности r-мерных массивов Баркрера с r>1:
Теорема 5. Не существует массива Баркера размера , при , кроме случая .Теорема 6. Не существует массивов Баркера, размера , для которых , и для каждого
Мы уже описали два варианта последовательностей Баркера: для Голеевских последовательностей пар, и для массив Баркер. Первый вариант дает бесконечное семейство бинарных последовательность пар, с длинной , в то время как второй не представляет никаких новых бинарных примеров, за исключением размера 2 × 2. Таким образом, мы определяем Голеевскую (комплементарную) пару массивов, как пару , массивы А и В в которых: , для любых .Главный вопрос, это для каких размеров такая пара существует. Еще один важный вопрос, это сколько различных Голеевских пар массивов заданного размера существует. В 1978 Охияма, Хонда и Цуджиучи предложили использовать 2-мерные бинарные Голеевские пары массивов для рентгеновского и гамма-кодированного апертурного изображения.
C + D2form an s1t1 × · · · × srtr binary Golay array pair.Using Theorem 9 we can construct a binary Golay array pair of size s1×· · ·×sr−1×srfrom binary array Golay pairs of size s1 × · · · × sr−1 × 1 and 1 × · · · × 1 × sr, from whichTheorem 7 can be recovered by repeated application. But although Theorem 9 is a moregeneral construction than Theorem 7, it does not produce new sizes of binary Golay arraypairs beyond those given in Corollary 8.4On the nonexistence side, Dymond [8] proved that if an s1 × · · · × sr binary Golayarray pair exists thenQri=1 si is an even sum of two squares (generalising Golay’s resultsfor the binary sequence pair case [16]). She ruled out the existence of a binary Golay arraypair of size 2 × 5 by exhaustive search, and could find no examples of size 3 × 6, 2 × 9 or2 × 3 × 3 by extensive (though non-exhaustive) search [8, p. 143].We will use our main result, Theorem 11, to explain many of these previously knownconstructive and nonexistence results.2 Reduction of the dimension of a Golay array pairIn [19] the authors observed that a (d + 1)-dimensional binary array can be mapped to ad-dimensional binary array so that the aperiodic autocorrelation functions of both arraysare closely related. The proof given in [19] does not make use of the condition that thearray is binary, and holds without modification for arrays of complex-valued entries:Lemma 10 (Jedwab and Parker [19, Lemma 2.1]). For integer r 0, let A = (A[i, j, i1, . . . , ir])be an s×t×s1×· · ·×sr array. Define the st×s1×· · ·×sr array (A) = (B[m, i1, . . . , ir])byB[ti+j, i1, . . . , ir] := A[i, j, i1, . . . , ir] for 0 i < s, 0 j < t, 0 ik < sk (k = 1, . . . , r).Then, for all integer u, v, u1, . . . , ur, where 0 v < t,C (A)(tu + v, u1, . . . , ur) = CA(u, v, u1, . . . , ur) + CA(u + 1, v − t, u1, . . . , ur).Lemma 10 expresses each aperiodic autocorrelation C (A) as the sum of exactly twoterms CA (one or both of which might be trivially zero, according to the values of u and v).We now use this result to show that the existence of a (d + 1)-dimensional Golay arraypair implies the existence of a d-dimensional Golay array pair.Theorem 11. For integer r 0, suppose that A and B form an s×t×s1×· · ·×sr Golayarray pair over an alphabet S. Then (A) and (B), as defined in Lemma 10, form anst × s1 × · · · × sr Golay array pair over S.Proof. Fix integers u, v, u1, . . . , ur, where 0 v < t and (u, v, u1, . . . , ur) 6= (0, . . . , 0). ByLemma 10,C (A)(tu + v, u1, . . . , ur) + C (B)(tu + v, u1, . . . , ur)= CA(u, v, u1, . . . , ur) + CA(u + 1, v − t, u1, . . . , ur) +CB(u, v, u1, . . . , ur) + CB(u + 1, v − t, u1, . . . , ur)= 0,since A and B form a Golay array pair. Therefore (A) and (B) form an st×s1×· · ·×srGolay array pair, and are defined over the same alphabet as A and B.Repeated application of Theorem 11 gives:5Corollary 12. If there exists an s1 × · · · × sr Golay array pair then there exists a Golaysequence pair of lengthQrk=1 sk over the same alphabet.Theorem 11 also allows an alternative formulation of Theorem 9 that is conceptuallysimpler: specialise Theorem 9 to the case where A and B have size s1 × · · · × sr × 1 ×· · · × 1 (with v 1’s), and C and D have size 1 × · · · × 1 × t1 × · · · × tv (with r 1’s). TheKronecker product then simplifies to the tensor product, giving a constructed array of sizes1 × · · · × sr × t1 × · · · × tv. We can recover the original form of Theorem 9 from thissimpler formulation by setting v = r and then applying Theorem 11.3 Application to the binary caseTheorem 11 and Corollary 12 are of particular interest in the binary case, where we have:Proposition 13. Up to reordering of dimensions, an s1×· · ·×sr binary Golay array pairwith 1 <Qrk=1 sk < 100 exists for precisely the following sizes, together with the derivedsizes arising from Theorem 11:2, 2 × 2, 2 × 2 × 2, 2 × 2 × 2 × 2, 2 × 2 × 2 × 2 × 2, 2 × 2 × 2 × 2 × 2 × 2,10, 2 × 10, 2 × 2 × 10, 2 × 2 × 2 × 10,26, 2 × 26.Proof. All the listed sizes of binary Golay array pairs exist, by Corollary 8. We now showthat, up to reordering of dimensions, no other sizes satisfying the stated conditions exist.Suppose there exists an s1 ×· · ·×sr binary Golay array pair with 1 <Qrk=1 sk < 100.By Corollary 12, a binary Golay sequence pair of lengthQrk=1 sk exists. The computersearch results of [1] then forceYrk=1sk 2 .By Theorem 11, it is now sufficient to rule out the existence of binary Golay array pairsof the following sizes:2 × 5, 4 × 5, 8 × 5, 16 × 5, 2 × 13, 4 × 13(since, for example, the nonexistence of a binary Golay array pair of size 16 × 5 impliesthe nonexistence of binary Golay array pairs of size 2×2×2×2×5, 2×2×4×5, 2×8×5,and 4×4×5). Since there exists a binary Golay sequence pair of length 2, by Theorem 9it is then sufficient to rule out the existence of binary Golay array pairs of just two sizes:16 × 5 and 4 × 13.We describe an efficient computer procedure by which this ruling out can be done forsize 16×5; the procedure for size 4×13 is similar. If A and B form a binary Golay arraypair of size 16 × 5 then, by Theorem 11, (A) and (B) form a binary Golay sequence6pair of length 80 (where the mapping is defined in Lemma 10). Now the exact numberand structure of binary Golay sequence pairs of length 80 is known from [1], so we canapply the inverse map −1 to all such sequence pairs and test the resulting array pairs ofsize 16 × 5 for the Golay property. Since we find that no such array pair is a Golay arraypair, we conclude that there is no 16 × 5 binary Golay array pair.In particular, Proposition 13 confirms Dymond’s computer search results [8] that establishedthe nonexistence of a binary Golay array pair of size 2 × 5 and suggested thenonexistence of binary Golay array pairs of size 3×6, 2×9 and 2×3×3 (see Section 1).The proof of Proposition 13 demonstrates that the fundamental object of interest is aGolay array pair having the largest possible number of dimensions, and that other Golayarray pairs arising from Theorem 11 should be regarded as derived objects. For example,the existence of a 2 × 2 × 10 binary Golay array pair given by Corollary 8 implies theexistence of binary Golay array pairs of size 2 × 20, 4 × 10, and 40. Similarly, if thenonexistence of a binary Golay array pair of size 4 × 25 were established, it would implythe nonexistence of binary Golay array pairs of size 2×2×25, 4×5×5, and 2×2×5×5.The following two nonexistence results generalise Proposition 3 and Theorem 4 frombinary sequences to multi-dimensional binary arrays. Both results could be established byadapting the original proofs to multiple dimensions, but follow directly as a consequenceof Corollary 12:Corollary 14. If there exists an s1 × · · · × sr binary Golay array pair thenQrk=1 sk = 1orQrk=1 sk is even.Proof. Combine Proposition 3 and Corollary 12.Corollary 15. If there exists an s1 × · · · × sr binary Golay array pair then no sk has aprime factor congruent to 3 modulo 4.Proof. Combine Theorem 4 and Corollary 12.Corollary 14 was previously established by Dymond [8]. If an s1×· · ·×sr binary Golayarray pair exists then Corollary 15 implies thatQrk=1 sk is the sum of two squares, as wasalso previously established by Dymond [8].4 ConclusionWe conclude by summarising the results of the paper, and presenting some open questions.Historically, the primary theoretical and practical motivation for the generalisationfrom Golay sequence pairs to Golay array pairs was to enlarge the set of available objects.Comparison of Corollaries 2 and 8 demonstrates some success for this approach in thebinary case, and prompts the question:1. Does the existence of an s1 ×· · ·×sr binary Golay array pair imply the existence ofa binary Golay sequence pair of length sk for each k?7A subsidiary question suggested by the proof of Proposition 13 is:2. Does the existence of an s1×· · ·×sr binary Golay array pair with each sk > 1 implythat each sk is even?Golay array pairs are not just a possible source of further examples: we have shownthat a Golay array pair having the largest possible number of dimensions is in fact afundamental object of interest, from which lower-dimensional Golay array pairs can bederived via Theorem 11.In the quaternary case, Craigen, Holzmann and Kharaghani [4] showed by computersearch that a length s Golay sequence pair exists for 1 < s 22 precisely whens 2 .We ask:3. Does an array viewpoint shed light on the existence pattern for quaternary Golaysequence pairs, and in particular the conjectures in [4]?The focus of this paper is the set of sizes for which a Golay array pair can exist,especially in the binary case. A further paper [12] considers the explicit construction,structure, and enumeration of Golay array pairs of a given size s1 × · · · × sr, especiallywhenQrk=1 sk is a power of 2.