Kasami序列的快速分類法

Efficient categorization scheme for Kasami sequences

許哲鳴(Hsu, Che Ming)

指導教授 ： 黃之浩

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2015年)

https://doi.org/10.6843/NTHU.2015.00391

摘要

在數位電視系統中發射端識別碼（transmitter identification，簡稱Tx-ID）的重要性與日俱增，時至今日它已經變成關鍵角色。維持系統正常運作的檢測儀器需要它，電視直播節目也需要它。但是當接收端收到弱的訊號時，要識別弱訊號的來源並不容易，因此虛擬隨機序列（pseudo-random sequences，簡稱PN序列）被嵌入數位電視訊號中作為識別碼。而諸多PN序列中，Kasami序列（Kasami sequences）非常適合作為Tx-ID之用，因為它們可以產生為數眾多而且接近正交（orthogonal）的碼。未來很可能有需要對Tx-ID序列進行分類，例如將Tx-ID序列依不同的廣播公司分群。本論文的重點在於探討小集合（small set）Kasami序列的分類方式。我們設計了新的演算法，它可以很有效率的在 O(n^1.5 (logn)^2) 的時間之內完成Kasami序列的分類，其中ｎ為該序列之長度。電腦模擬結果顯示我們提出的演算法是很快的，在內建Intel i7 2.9GHz CPU的PC上，平均只要0.5秒（或8秒）就可以找出一個14位元（或16位元）Kasami序列的特徵參數組(w,d,d')。另外，如果PN序列的長度太長（16位元的Kasami序列之長度為65,535位元）會造成困擾時，我們建議採用單一個PN序列由多個Kasami序列串接構成的方式，在此情況下，第一個小集合Kasami序列的序列個數，可以視為整個PN序列的分類總類別數。

關鍵字

TxID ； 偽隨機序列 ； Kasami序列 ； 浮水印 ； 有限體

並列摘要

The transmitter identification (Tx-ID) of digital television systems becomes more and more important. Many things need it, such as test and measurement (T&M) equipment and live televised programs. However, identification of the signal source of a weak signal is quite difficult, and therefore the pseudo-random (PN) sequences, widely used in CDMA system, are buried beneath the ATSC signals for the purpose of identification of the emitting transmitter. Kasami sequences are one of well-known PN sequences and are good candidates for transmitter identification since they have good cross-correlation properties and can generate a large number of codes. In the future, there may be an emerging need to categorize Tx-ID sequences. For example, Tx-ID sequences may be grouped separately for different broadcasting companies. In this thesis, we are particularly interested in the Tx-ID sequences made of small set of Kasami sequences. Our main objective is to efficiently categorize and address Kasami sequences. We design a new algorithm that can efficiently classify Kasami sequences within O(n^1.5 (logn)^2)-time, where n is the sequence length. Simulations show that our proposed algorithm is very fast in practice. It will take 0.5 (or 8) seconds on average to find the parameter set (w,d,d') of a 14-bit (or 16-bit) Kasami sequence in the small set, by using a PC with an Intel i7 2.9GHz CPU. We also propose a method of categorization of a PN sequence consisting of several Kasami sequences. If the large length of a PN sequence will be a problem (16-bit Kasami sequence has a length of 65535 bits), we suggest to use two or more Kasami sequences concatenated together to form a single PN sequence. In this case, the size of the first Kasami sequences can be considered as the number of categories of the PN sequences.

並列關鍵字

Transmitter identification ； Pseudo-random sequences ； Kasami sequences ； watermarking ； finite field

參考文獻

[2] X. Wang, Y. Wu, and B. Caron, “Transmitter identification using embedded pseudo-random sequences,” IEEE Transactions on Broadcasting, vol. 50, no. 3, pp. 244–252, September 2004.

[3] X. Feng and H.-C. Wu, “Injection-level optimization for digital television transmitter identification systems using Kasami sequences,” IET Communications, vol. 5, no. 16, pp. 2397–2406, November 2011.

[4] X. Feng, H.-C. Wu, and S. Y. Chang, “On the injection-level optimization for digital television transmitter identification systems using Kasami sequences,” in Proceedings of IEEE International Conference on Communications (ICC), June 2011, pp. 1–5.

[5] X. Feng, H.-C. Wu, and Y. Wu, “New identification sequence analysis for multiple transmitters subject to arbitrary topologies,” in Proceedings of IEEE Global Telecommunications Conference, December 2010, pp.1–5.

[7] S. I. Park, H. Lim, H. M. Kim, Y. Wu, and W. Oh, “Augmented data transmission for the ATSC terrestrial DTV system,” IEEE Transactions on Broadcasting, vol. 58, no. 2, pp. 261–268, June 2012.