簡易檢索 / 詳目顯示

回結果列表
研究生： 劉兆敏
Liu, Zhao-Min
論文名稱： 針對Delsarte及Schrijver編碼上界的完整解析及例子說 明
Fully comprehensive analysis with illustrative examples to code upper bounds by Delsarte and by Schrijver
指導教授： 許瑞麟
Sheu, Ruey-Lin
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2018
畢業學年度： 106
語文別： 英文
論文頁數： 116
中文關鍵詞： 錯誤更正碼 、上界 、線性規劃 、半正定規劃
外文關鍵詞： Error-correcting code, Upper bound, Linear programming, Semide finite programming
相關次數： 點閱：64  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在這篇論文裡，我們主要研究的是關於長度為 n 且最小距離為 d 的二進位碼集合的最大個數 A(n,d) 為多少. 這是一個 NP-hard 問題並且有兩個最早關於 A(n,d) 的上界估計，分別是由 Philippe Delsarte 在1973年以及 Alexander Schrijver 在2005年所提出. 前者是基於線性規劃去計算出 A(n,d) 的上界，後者則基於半正定規劃. 本論文的目的是藉由許多實際例子來理解這兩種模型中所使用的困難技術以及其證明. 我們也編寫了程式去比較 Delsarte's bound 以及 Schrijver's bound 在字串長度小於等於18的數值結果.

    In this thesis, we study the maximum size A(n,d) of a binary code of word length n with minimum distance at least d. The problem is NP-hard and there were two earli-
    est upper bounds for A(n,d) introduced by Philippe Delsarte in 1973 and Alexander Schrijver in 2005. The former is based on linear programming whereas the latter on semidefinite programming. The purpose of this thesis is to understand the two models via many practical examples to comprehend difficult techniques used in the models and their proofs. We also write computer codes to compare numerical results between Delsarte's bound and Schrijver's bound for word length n<=18.

    List of Tables v List of Figures vi 1 Introduction 1 1.1 Introduction 1 1.2 Defi nitions and notations 2 1.3 Background 5 1.3.1 Error correction 5 1.3.2 Matrix C*- algebra 9 2 LP model for code upper bound 19 3 SDP model for code upper bound 29 3.1 SDP model for code upper bound 29 3.2 Explicit block-diagonalizaton 54 4 Comparison of numerical results 100 4.1 SDP model with index 100 4.2 Comparison of numerical results 106 Bibliography 114 A Matlab code for Delsarte's LP bound 115

    [1] A. Schrijver, "New code upper bounds from the Terwilliger algebra and semidefinite programming", IEEE Trans. Inf. Theory vol. 51, pp.2859-2866, 2005.
    [2] Chao Li, "Semidefinite programming, binary codes and a graph coloring problem", LAP LAMBERT Academic Publishing, Sep. 2015
    [3] D.C. Gijswijt, H.D. Mittelmann and A. Schrijver, "Semidefinite code bounds based on quadruple distances", IEEE Trans. Inform. Theory 58, 2697-2705, 2012.
    [4] G. P. Barker, L. Q. Eifler, and T. P. Kezlan. A non-commutative spectral theorem. Linear Algebra and Appl., 20(2):95-100, 1978.
    [5] Gijswijt, D.: "Matrix Algebras and Semidefinite Programming Techniques for Codes". PhD thesis, University of Amsterdam, The Netherlands, 2005.
    [6] Hyun Kwang Kim and Phan Thanh Toan, "Improved Semidefinite Programming Bound on Sizes of Codes", arXiv:1212.3467, Dec. 2012.
    [7] Jiri Matousek and Bernd Gartner, "Understanding And Using Linear Programming", Springer Verlag, Jan. 2007.
    [8] Monique Laurent, "Strengthened semidefinite programming bounds for codes", Mathematical Programming (B) 109, 239-261, 2007.
    [9] P. Delsarte, "An algebraic approach to the association schemes of coding theory", Philips Res. Repts. Suppl., no. 10, 1973.
    [10] San Ling and Chaoping Xing, "Coding Theory: A First Course", Cambridge Univ Pr, Mar. 2004.

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE