臺灣博碩士論文加值系統

假設r,s,u及v為正整數，一個(r,s;u,v)的完整地圖為一個r by s的二元陣列，其中所有u by v的二元陣列都出現一次且只有一次。一個v-視窗的de Bruijn 序列，指一個長度為2^(v)且其中的元素只有”0”和”1”的序列且具有以下條件 : 如果s是一個長度為v的一個二元序列,存在m,使得s=(a_(m),a_(m+1),…,a_(m+v-1))，且 ，對於每一個i，1≦i≦2^(v)。假設s是一個週期為n的c元循環序列，在序列s中，如果沒有c元v位序列同時出現在兩個不同的位置，則稱s為c元v-視窗的循環序列。一個c元v-視窗的de Bruijn 序列是一個週期為c^(v)的c元v-視窗的循環序列，使得所有c元v位序列都出現一次且只有一次。記為(c^(v),c,v)的de Bruijn 序列。一個(2^(v),2,v)的de Bruijn 序列可被視為一個(2^(v),1; v,1)或(1, 2^(v);1,v)的完整地圖。在這篇論文中，對於v≧1，我們利用一個(2^(v),2,v)的de Bruijn 序列，建構出一個(4^(v),4,v)的de Bruijn 序列，並介紹完整因子及完整地圖的基本建構法。

Given positive intergers r, s, u, and v, an (r,s;u,v) Perfect map (PM) is defined to be a periodic r by s binary array in which every u by v binary array appears exactly once as a periodic
A de Bruijn sequence for v (in 0’s and 1’s) is a sequence of 2^(v) bits having the property that if s is a bit string of length v, for some m, s = a_(m)a_(m+1)…a_(m+v-1) , and we define for i = 0,…,2^(v).
If s is a c-ary cycle of period n, then we say that s is a v-window sequence if no c-ary v-tuple occurs in two distinct positions within a period of s. A c-ary de Bruijn sequence of span v is a v-window sequence of period equal to c^(v). That is, every possible c-ary v-tuple occurs precisely once in a period c^(v) of the de Bruijn sequence , it is denoted by (c^(v),c,v) de Bruijn sequence. A (2^(v),2,v) de Bruijn sequence can be viewed as a (2^(v),1;v,1) PM or (1,2^(v);1,v)PM.
In this thesis , we construct a (4^(v),4,v) de Bruijn sequence B by using a (2^(v),2,v) de Bruijn sequence A , for v≧1.

第一章緒論…………………………...1
第二章先備知識……………………....3
第三章de Bruijn 序列的建構……….11
第四章完整因子的建構………………30
第五章完整地圖的建構……………….34
參考書目…………………………………..41

[1] S.Blackburn , T.Etzion , and K.Paterson , Permutation polynomials , de Bruijn sequence and linear complexity , J.Combin . Theory Ser . A,to appear
[2] J.Bondy and U.Murty , Graph Theory with Applications, Elsevier , New York ,1976
[3] J.Burns and C.Mitchell , Coding schemes for two-dimensional position sensing , in Cryptography and Coding Thirt
[4] T.Etzion , Constructions for perfect maps and pseudo-random arrays , IEEE Trans . Inform. Theory , 34(1988) ,pp. 1308-1316
[5] A.Lempel , On a homomorphism of the de bruijn graph and its application to the design feedback shift registers , IEEE Trans. Comput. C-19 (1970) , pp 1204-1209
[6] C.Mitchell , Constructing c-ary perfect factors , Designs ,Codes and Cryphes , 4 (1994) pp.341-368
[7] C.Mitchell , New c-ary perfect factors in the de bruijn graph , in Codes and Cyphers.
[8] C.Mitchell , T. Etsion , and K.Paterson , A method for consructing decodable de Bruijn sequences , IEEE Trans.42 (1996) , pp.1472-1478
[9] C.Mitchell , and K.Paterson , Decoding perfect maps , Designs , Codes and Cryptography , 4(1994),pp.11-30
[10] K.Paterson , Perfect maps , IEEE Trans. Inform. Theory , 40(1994),pp.743-753
[11] K.Paterson, Perfect factors in the de Bruijn graph ., Designs , Codes and Cryptography , 5(1995),pp.115-138
[12] K.Paterson , New classes of perfect maps 1, J.Combin. Theory ser.A ,73(1996)302-334
[13] K.Paterson , New classes of perfect maps2, J.Combin. Theory ser.A ,73(1996)335-345