(3.238.7.202) 您好!臺灣時間:2021/03/01 22:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鍾孟儒
研究生(外文):Meng-Ru Jung
論文名稱:完整地圖之探討
論文名稱(外文):The study of Perfect maps
指導教授:高金美
指導教授(外文):Chin-Mei Kau Fu
學位類別:碩士
校院名稱:淡江大學
系所名稱:數學學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:47
中文關鍵詞:de Bruijn 序列完整地圖
外文關鍵詞:de Bruijn sequencePerfect maps
相關次數:
  • 被引用被引用:0
  • 點閱點閱:140
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:1
假設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

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔