PDF《博士学位论文》

分类号: O157.

2 单位代码:

10335 密级: 学号:

11006131 博士学位论文 文论文 目: 几类编码问题研究中的组合学方法 文论文 目: Combinatorial Approaches to Several Selected Topics in Coding Theory 申请人姓名: 指导教师: 合作导师: 专业名称: 学 研究方向: 组合 编码 所在学院: 学学论文 日期: 二一三年 月 几类编码问题研究中的组合学方法 论文作者 名: 指导教师 名: 论文评阅人 1: 学 评阅人 2: 方\学评阅人 3: 学 评阅人 4: 方\学评阅人 5: 学 答辩委员会主席: 学 委员 1: 学 委员 2: 学 委员 3: 学 委员 4: 学 委员 5: 学 答辩日期: 二一三年 五月 Combinatorial Approaches to Several Selected Topics in Coding Theory Author'

s signature: Supervisor'

s signature: External Reviewers: Zhiwei SunProfessorNanjing University Fang LiProfessorZhejiang University Yanxun ChangProfessorBeijing Jiaotong University Fangwei FuProfessorNankai University Jianxing YinProfessorSoochow University Examining Committe Chairperson: Keqin FengProfessorTsinghua University Examining Committe Members: Keqin FengProfessorTsinghua University Song LiProfessorZhejiang University Junde WuProfessorZhejiang University Zhiyi TanProfessorZhejiang University Gennian GeProfessorZhejiang University Date of oral defence: May

2013 致谢 的 的学 中 的方 学 研的 的学的的的学 的学的的学的学研究 学的类学的研究 学学的研学研究中 学的 学的 学的 的的的,的,的的中学I浙江大学博士学位论文 II 摘要 学的的的组合 学 编码 学的组合 学 的研究 学的中组合 学的 编码 中的几类问题 的码中的 码的编码 的 研究 类组码的组合 方法 码 的编码 法中的编码

2 中的码码 的法方法 Ding 码Lander 码的的中的研究 的的的Smith 中的 中的码码 方法 的码 中的码的方法 的码码3中研究 类法码的 组码码LDPC 码类Shannon 的码的中的的的中组合 的码 的方的的45的中中的类组码码合码 中的类编码 的 码的研究 III 浙江大学博士学位论文

3 的码的码的的4码Cayley 的 中的方法 码的码n的的GilbertCVarshamov ?(ln(n))

5 中的合码 码码中的方的码的 类合码的 研究 中Chee

2008 3 的 合码 的码 中的组码 组合 中的 方法

4 5 的 合码 中研究的几类编码 编码中的 组码的67中类编码问题 的 问题 的方法 中的法合6的码Cheng 的合中的中研究 t =

2 码的 问题组的 法的的码码的码方方法 SteinCLovász 码的 中码的方法 的 码的 的的7中的方法 研究 的中的的编码问题 DeVore 法的 的的RiemannCRoch 的的合的的DeVore 的IV 摘要 的方法 的的Gauss 编码 Cayley 码 方法 码SteinCLovász 码 组合 学V浙江大学博士学位论文 VI Abstract Abstract Along with the outbreak of the third industrial revolution, combinatorics enjoyed a great resurgence. It studies the discrete objects as computer science and digital commu- nication technology do. Meanwhile, coding theory plays a fundamental role in the latter two fields. In this dissertation, we will study several topics in coding theory from a com- binatorial point-of-view. These problems include the optimal linear error-correcting block codes, the nonlinear block codes used in powerline communications, the separable codes designed to prevent collusion attacks for digital fingerprintings, and the sparse signal sam- pling in compressed sensing theory. In the first part, we will investigate two kinds of optimal linear codes. Due to the highly efficient encoding algorithms, linear codes are the most commonly used coding schemes in daily lives. In Chapter 2, we will present how to construct submodule code chains from the orbit matrices of difference sets. Our idea comes from Ding'

s and Lander'

s works. They studied the cyclic codes from difference sets and the submodule codes from incidence struc- tures, respectively. In this chapter, we will begin with the cyclic difference sets possessing a semi-regular automorphism of a prime order and investigate the orbits of incidence ma- trices under this automorphism. Using information about invariant factors of the Smith normal forms of orbit matrices, submodule code chains are obtained. A lot of examples will demonstrate that our resultant codes are optimal since their minimum Hamming dis- tances can reach some theoretical upper bounds of linear codes. However, a weakness of these codes is that they usually do not remain the cyclic property. Therefore, the decoding complexity of them will be potentially higher. To overcome this drawback, we will consider a class of linear codes with highly effi- cient encoding and decoding algorithms in Chapter 3, namely the low-density parity-check (LDPC) codes. These codes can be effectively decoded with recursive methods such as message-passing algorithms. LDPC codes play important roles in almost every modern VII 浙江大学博士学位论文 communication standard since their performances are extremely close to the Shannon limit. Based on the binary dispersion of entries in difference matrices over a cyclic group, we will get regular LDPC codes with quasi-cyclic property which can be equipped with even faster encoding and decoding algorithms. Comparing with those from other combinatorial structures in literature, our codes are equally well in the performance and with much more flexibility on parameters. The second part consists of Chapters

4 and 5. Our focuses are two classes of nonlinear error-correcting codes widely used in powerline communications, namely the permutation codes (PCs) and the constant-composition codes (CCCs). We remark that both codes have been found to have important applications in other areas as well. The researches on PCs went very slow. In fact, we only know how to construct optimal PCs with minimum Ham- ming distance no larger than 3. For the general distances, even the good upper or lower bounds on code sizes are difficult to get. In Chapter 4, we will provide a lower bound of PCs via graph theory. To be specific, we shall establish a connection between PCs and in- dependent sets of a well-chosen Cayley graph. The lower bound of PCs then comes along with analysis of independence number of the graph. Our result asymptotically improves the classical GilbertCVarshamov bound with a factor of ?(ln(n)) with distance d fixed and code length n going to infinity. Chapter

5 is dedicated to constant-composition codes. These codes can be regarded as a relaxation of PCs by loosening the requirement that every symbol occurs exactly once in each codeword. They can also be regarded as a generalization of classical binary constant- weight codes. The systematic study of CCCs only began in late 1990s. Today, the problem of determining the maximum size of a CCC constitutes a central problem in their investigation. In 2008, Chee et al. completely solved the case of ternary CCCs with weight 3. In this chapter, we will follow their work and construct optimal ternary CCCs with weight

4 and distance

5 for all lengths. Our main tools are group divisible codes and several combinatorial recursive methods. All codes in the above two parts belong to the category of channel coding. In the last VIII Abstract part, we shall switch our attention to some coding problems in information theory. In or- der to fight against the pirates of multimedia contents, digital fingerprintings are embedded to all legitimate distributions. Moreover, if we want to defend the collusion attacks, these fingerprintings have to be delicately encoded. Separable codes (SCs) in Chapter

6 were in- troduced by Cheng and Miao to resist the averaging attack which is the most common col- lusion mode. We will investigate the upper and lower bound of SCs for strength two in this chapter. By grouping coordinates, we can tremendously cut down the known upper bound. On the special case that an SC coincidences with a linear vector space over a finite field, the upper bound can be further reduced. Linear SCs matching this bound are constructed via orthogonal arrays as well. On the other hand, probabilistic method and SteinCLovász theorem will be applied to obtain the lower bounds of SCs. When we fix the code length and let the alphabet size go to infinity, codes from probabilistic method share the same order to the upper bound we have just derived. Lastly, we present a way to acquire good compressed sensing matrices from algebraic curves over finite fields in Chapter 7. The theory of compressed sensing studies the problem of recovering sparse signals from outcomes of a small number (comparing to the signal length) of measurements. This setup can be easily restated in the language of a source coding problem. Inspired by DeVore'

s method based on polynomials over finite fields, we will start with the algebraic curves. By evaluating the values of functions in the RiemannCRoch space of a divisor at some rational points of the curve, binary sensing matrices are constructed. With a proper choice of parameters, DeVore'

s results are included in our scheme as a special case. Numerical simulations will also show that our matrices are equally as good as the best known random Gaussian matrices when the signals are not too long. Keywords: algebraic curves, Cayley graph, coding theory, combinatorics, com- pressed sensing, difference matrices, difference sets, independent sets, low-density parity-check codes, permutation codes, probabilistic methods, separable codes, SteinC Lovász theorem IX 浙江大学博士学位论文 X 目次 I III Abstract VII

1 1 1.1 组合 学 编码

1 1.2 码.3 1.3 码61.4 编码

9 2 码码 的13 2.1

14 2.2 码码

17 2.3

24 3 LDPC 码的

27 3.1 LDPC 码27 3.2 LDPC 码29 3.3

32 4 码的35 4.1 码35 4.2 的37 4.3 Cayley

38 4.4 码40

5 合码的组合

47 5.1 合码

47 5.2

49 XI 浙江大学博士学位论文 5.3 A3(n, 5, [3, 1]) 的56 5.4 A3(n, 5, [2, 2]) 的67 5.5

76 6 码 的研究.85 6.1 码85 6.2

85 6.3 2- 码的

89 6.4 码的

94 7 的101 ........