格雷互補序列遞迴建構探討

Recursive Construction of Golay Complementary Sequences

黃國倫(Kuo-Lun Huang)

指導教授 ： 李穎

元智大學/工程學院/通訊工程學系/碩士(2006年)

https://doi.org/10.6838/YZU.2006.00115

摘要

Golay互補序列對具有非週期性自相關函數和為脈衝函數的特性。此種性質使Golay序列在通訊領域有許多應用。Davis及Jedwab曾提出一種經由布林函數產生Polyphase Golay序列的直接生成方法。此種方式生成的碼字序列會填滿Reed-Muller一階碼的特定二階共集，這些序列被稱為GDJ Golay互補序列。其後發現有些互補序列無法以Davis及Jedwab提出的方式生成，這些序列被稱為non-GDJ Golay互補序列。
過去對於non-GDJ Golay互補序列的結構，只在長度16有較完整的分析，對更長序列的了解有限。本文首先經由電腦生成長度32至128的四進制non-GDJ Golay互補序列，再運用非週期性自相關函數的性質，解釋non-GDJ Golay互補序列的遞迴生成方式，及其與GDJ Golay序列遞迴生成方式之不同。本文採用的合成方式比現有文獻所用的還多，也生成更多長度超過16的non-GDJ Golay互補序列。
Non-GDJ Golay互補序列的產生，源自長度8的四進制互補序列有少見的自相關函數雷同現象，以致出現跨共集互補序列對。本研究在不同長度，以電腦搜尋二進制、四進制、八進制的序列，觀察序列的非週期性自相關函數，找出罕見的自相關函數雷同現象，以更加了解序列的特性。

關鍵字

互補序列 ； 遞迴建構 ； 自相關函數

並列摘要

Golay Complementary Sequences have the property that the sum of aperiodic auto-correlation functions of pairing sequences is an impulse function. There are many applications for Golay complementary sequences in communications. David and Jedwab described a direct construction of polyphase Golay complementary sequences through algebraic normal forms of generalized Boolean functions. Sequences constructed in this way fill specific second-order cosets of the generalized first-order Reed-Muller code. These sequences are called “GDJ Golay complementary sequences.” However, some complementary sequences cannot be obtained by the direct construction given by David and Jedwab. These sequences are called “non-GDJ Golay complementary sequences.”
Previously the structure of non-GDJ Golay complementary sequences has only been studied for length 16. We construct quaternary non-GDJ Golay complementary sequences of lengths 32, 64, and 128 recursively by computer. Using properties of aperiodic auto-correlation functions, we provide explanations for structures in the recursive construction. Differences between GDJ Golay complementary sequences and non-GDJ Golay complementary sequences are described. We use more methods in the recursive construction compare to existing literature and construct more non-GDJ Golay complementary sequences with longer lengths.
Non-GDJ Golay complementary sequences arise as a result of the unusually large sets of quaternary complementary sequences of length 8 with identical aperiodic auto-correlation function. We search for this rare event in binary, quaternary, and octary sequences, exhaustively, in order to obtain more understanding of this phenomenon.

並列關鍵字

Complementary Sequences ； Recursive Construction ； Auto-Correlation Function

參考文獻

[Bud90] S. Z. Budišin, ”New Complementary Pairs of Sequences”, Electronics Letters, Vol. 26, Issue 13, pp. 881 – 883, Jun. 1990.

[Car02] R. Craig, W. Holzmann and H. Kharaghani,“Complex Golay sequences: structure and applications”, Discrete Mathematics, Vol. 252, Issue 1-3, pp. 73-89, May. 2002.

[Che05] C. Y. Chen, C. H. Wang and C. C. Chao, “Complementary Sets and Reed-Muller Codes for Peak-to-Average Power Ratio Reduction in OFDM”, 16th AAECC, 2005.

[Chu04] 儲文彬, ”以格雷序列與非格雷序列降低OFDM訊號之峰均比”, 元智大學碩士論文, 2004.

[Dav98] J. A. David, J. Jedwab and K. G. Paterson, “Codes, Correlations and Power Control in OFDM”, HP Laboratories Bristol, HPL-98-199, 1998.