格雷序列結構之探討

Structure of Golay sequences

高翊展(Yi-Chan Kao)

指導教授 ： 李穎

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

摘要

由於格雷互補對(Golay Complement Pairs)的非週期性自相關函數和為脈衝的特性，因此格雷序列有很多的應用，像是應用在OFDM編碼時可將PAPR限制在2之內。而尋找尋究竟有多少格雷序列以及分析格雷序列的結構一直是很有趣的題目。利用窮盡搜尋找到了長度為16、四進位的GDJ格雷序列則打破了Davis和Jedwab所提出的所有格雷序列皆可由Direct Construction產生的假說。本論文解釋了這些Non-GDJ格雷序列所形成的原因，發現這些Non-GDJ格雷序列是透過Golay所提出的Recursive Constructions，由兩組長度為8、四進位跨格雷共集的GDJ格雷互補對所連接出來的。並當長度更長時，依然可連接出Non-GDJ格雷序列。

本論文也透過recursive construction的看法來分析標準布林函數基底，來了解recursive construction和direct construction的關連性。觀察到全部長度為16的GDJ格雷共集首皆可透過特定的連接方式分解為兩個長度為8的GDJ格雷序列。並透過標準布林函數基底座標向量來分析序列翻轉、互補、加常數向量、線性向量對基底座標向量的影響，以及對GDJ序列的影響。發現GDJ格雷序列翻轉互補之後仍然為原格雷共集。

論文中提出了非週期性自相關函數的矩陣表示式，傳統如果要從兩碼字序列的非週期性自相關函數來計算碼字序列相加後的非週期性自相關函數須考慮相互影響的項(cross term)，但利用非週期性自相關函數矩陣可以免除此項。

關鍵字

格雷序列 ； 自相關函數矩陣

並列摘要

Golay sequences have lots of applications, e.g. as codewords for OFDM signals to limit the PAPR to 2. It’s also a very interesting subject to find how many Golay sequences exist and their structure. It was previously believed that Davis and Jedwab’s construction of Golay sequences as Reed-Muller codewords possibly generate all Golay sequences over of length . Exhaustive search by Li and Chu reveals that there are “1024” more quaternary Golay sequences of length 16, thus the hypothesis that “all Golay sequences can be generated from Davis and Jedwab’s construction” is not true. This thesis explains why non-GDJ Golay sequences arise. We found that non-GDJ Golay sequences can be constructed by concatenating or interleaving from a Golay complement pair with two sequences in different Golay cosets. Non-GDJ Golay can be used to generate longer non-GDJ Golay sequences through Recursive Construction.

We also analyze standard Boolean function basis through Recursive Construction’s point of view which provide us more information of the relationship between Recursive Constructions and Direct Construction. We observed that all Golay Coset leaders of length 16 can be constructed by two specific combinations of two pairing GDJ Golay sequences of length 8. We also use standard Boolean function basis to analyze basis sequence flipping, complement, adding constant vector, adding linear vector and their effect to coordinate vector. We observed that GDJ Golay sequences after complement and flipping will still be in the same Golay coset.

Another contribution of this thesis is to present a matrix form of codewords’ AACF. Originally, we can’t calculate the Aperiodic Auto-Correlation Function (AACF) of the sum of two codewords from individual two codewords’ AACFs. When the matrix form of AACF is used, we can derive the AACF of the sum of two codewords from the individual codeword’s AACF matrix without involving cross terms.

並列關鍵字

Golay sequences ； Aperidoic Auto-Correlation Function Matrix