本文關(guān)鍵詞：源于幾類信息科學(xué)問題的極值組合構(gòu)型　出處：《浙江大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 置換碼 蛇形碼 獨立集 分離哈希函數(shù)族 合謀-安全碼 AONT變換 不可擴展乘積基

【摘要】：信息科學(xué)與組合數(shù)學(xué)的交叉歷來已久。信息科學(xué)在具體應(yīng)用層面刺激著組合數(shù)學(xué)的發(fā)展,組合數(shù)學(xué)的體系的日臻成熟為信息科學(xué)的研究提供了理論支撐。信息科學(xué)中的若干問題,本質(zhì)上都可以轉(zhuǎn)化為一些組合數(shù)學(xué)中的極值構(gòu)型問題。本學(xué)位論文將從組合數(shù)學(xué)的觀點出發(fā),融匯應(yīng)用了圖論、概率方法、極值組合等相關(guān)工具,對若干信息科學(xué)中的問題進行了一定的思考與推進。在第1章緒論部分,我們將簡要介紹本文所涉及的各信息科學(xué)問題的相關(guān)背景,并概述本文對此問題所做的推進工作。在第2章中,我們的研究對象為置換群上的置換碼與蛇形碼,它們在電力線技術(shù)、分組密碼、閃存中的排序調(diào)制等領(lǐng)域有著廣泛應(yīng)用。我們將對碼字數(shù)目的研究轉(zhuǎn)化為圖論上的問題,通過構(gòu)造合適的染色方案給出了圖的獨立數(shù),進而分別改進了漢明距離和Kendall's τ-距離下的置換碼的下界。Kendall's τ-距離下的蛇形碼問題在奇數(shù)階置換群和偶數(shù)階置換群上有明顯的區(qū)別。在S2n+1上我們嚴格證明了'Horovitz-Etzion構(gòu)造”的可行性,并在其基礎(chǔ)上進行微調(diào)得到了更優(yōu)的蛇形碼。在S2n+2上我們利用之前S2n+1中的蛇形碼為基礎(chǔ)進行復(fù)制與拼接,得到了非平凡的蛇形碼構(gòu)造,在漸進意義下達到最優(yōu)。在第3章中,我們的研究對象為源于數(shù)字產(chǎn)品版權(quán)保護背景的合謀-安全碼及相關(guān)哈希函數(shù)族。我們將對碼字數(shù)目的研究轉(zhuǎn)化為超圖上的問題,進而借助超圖的獨立數(shù)的相關(guān)結(jié)論,改進了特定參數(shù)條件下完全哈希函數(shù)族、防誣陷碼、可分離碼的下界。這種利用超圖模型的分析方法尚屬首次。在第4章中,我們研究的問題是怎樣的一個可逆二元矩陣中擁有最大比例的2×2可逆子矩陣。這個純粹的組合問題的研究背景可追溯于圖靈獎得主Ron Rivest為進一步加強分組密碼的安全性所提出的一種預(yù)處理步驟—AONT變換。我們通過建立問題的整數(shù)規(guī)劃,結(jié)合概率方法的分析,完全確定了此問題的最優(yōu)解,并以分圓構(gòu)造為基礎(chǔ)給出了近似最優(yōu)的矩陣構(gòu)造方法。在第5章中,我們研究的問題為多部希爾伯特空間中的不可擴展乘積基的最小規(guī)模問題。此問題是量子信息學(xué)中的最基本問題之一,在量子信息的諸多領(lǐng)域有著廣泛的應(yīng)用。我們綜合利用圖的正交表示、循環(huán)圖的連通性、圖的1-因子分解等若干圖論工具,決定了一系列參數(shù)下的最小規(guī)模UPB的大小的準確值。在第6章中對其它在研問題做了簡要匯報。
[Abstract]:Cross information science and math has always been for a long time. Information Science in the specific application level to stimulate the development of combinatorial mathematics, combinatorial mathematics system has matured for information science research provides a theoretical support. Some problems in Information Science, into some mathematical combination of extreme configuration issues can be essentially this. This dissertation will start from combinatorial mathematics point of view, combined application of graph theory, probability method, extreme combination of tools, some of the problems in the information science and promote certain thinking. In the first chapter, we will briefly introduce the background of the information science problems involved in this thesis, and promote the work of an overview of this issue do. In the second chapter, the object of our study for replacement group on the code and Snake code, their technology in power line block cipher in flash memory Sort of modulation has been widely used. We will aim to study the number of code words into graph theory problems, by constructing appropriate coloring scheme given independence number graph, and then improved the Hamming distance and Kendall's tau distance under permutation codes lower bound of.Kendall's tau is obviously different from the distance of the snake in the code of odd order and even order permutation group on permutation groups in S2n+1. We strictly proved the feasibility of'Horovitz-Etzion structure, and fine tune has better code on the basis of serpentine in S2n+2. We use the S2n+1 code before snake based replication and splicing, are non trivial the Snake code structure, to achieve the optimal in the asymptotic sense. In the third chapter, the object of our study is to protect the copyright of digital products in the background of collusion - safety codes and related hash function family. We will Objective to study the number of code words into the hypergraph problem, relevant conclusions and using independent number hypergraph, improved hash function and completely specified parameter conditions, frameproof codes, can be separated from the lower bound of the codes. The analytic method of the hypergraph model is for the first time. In the fourth chapter, we study the problem of a a reversible two yuan how the matrix has the largest proportion of 2 * 2 matrix inverse. The research background of this purely combinatorial problem can be traced back to the Turing Award winner Ron Rivest in order to further strengthen the security of the proposed block cipher is a preprocessing step for AONT transform. We established by integer programming problems. Analysis with probability method, completely determine the optimal solution of this problem, and to construct circular matrix constructing method is given based on the approximate optimal. In the fifth chapter, we study the problem for many Hilbert Unextendible product basis the minimum size of the problem space. This is one of the basic problems in quantum information science, is widely used in many fields of quantum information. We synthesize the graph orthogonal representation, connectivity of circulant graphs, 1- factor decomposition to graph theory, decision the exact value of a series of parameters under the minimum size of the size of UPB. In the sixth chapter of the research in other problems are briefly reported.

【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157

【相似文獻】

相關(guān)期刊論文 前1條

1 夏樹濤,符方偉,楊義先;廣義B-J碼的周期分布和循環(huán)置換碼的構(gòu)造[J];科學(xué)通報;1997年06期

相關(guān)博士學(xué)位論文 前3條

1 楊禮珍;置換碼的界及構(gòu)造的研究[D];上海交通大學(xué);2007年

2 張一煒;源于幾類信息科學(xué)問題的極值組合構(gòu)型[D];浙江大學(xué);2016年

3 袁媛;自對偶置換碼和m-重量[D];武漢大學(xué);2005年

，

本文編號：1359053