臺灣博碩士論文加值系統

在這篇論文中，我們探討數種二元無記憶通道模式下的極小區塊碼 (ultra-small block code) 的最佳設計 (optimal design)，所探討的二元無記憶通道模式包含：二元非對稱通道 (binary asymmetric channel or BAC) 與二元輸入三元輸出的二元抹除通道 (binary erasure channel or BEC)。針對前者，我們另將特別著重兩個特例，即二元對稱通道 (binary symmetric channel or BSC) 與Z-通道 (Z-channel or ZC)。本研究中所謂的最佳碼，指的是在最大概度解碼 (maximum-likelihood decoding) 法則下，可達最低平均錯誤率的區塊碼設計。而所謂的極小區塊碼指的是碼字個數極小的情況，例如2、3或4。

針對二元非對稱通道 (BAC)，我們證明了當碼字個數為2時，相對碼 (flip codes) 為最佳區塊碼設計。另外，針對二元非對稱通道 (BAC) 的特例Z-通道，我們在碼字個數為2、3、4時，也提出給定任意碼長 (block length) 的最佳設計。而對於對稱式的通道，例如二元對稱通道 (BSC) 與二元抹除通道 (BEC)，我們針對碼字個數為2與3的情況下，找到給定任意碼長的最佳碼的設計規律。此外針對這兩個對稱式的通道，在碼字個數增加為4時，我們也設計了最佳的線性區塊碼 (linear block code)。

我們證明所設計的區塊碼可達最低的最大概度解碼錯誤率的主要關鍵技巧，乃是我們使用新的區塊碼建構觀點。簡言之，我們不用傳統碼字 (codeword) 為基準的分析法則，而是針對區塊碼矩陣採用以直列組合方式進行分析。這種新的分析方式可以精巧的定義出必要的區塊碼類別, 使我們可用區塊碼的碼長遞迴的方式來建構碼，同時也讓我們可以推導出區塊碼的平均錯誤率的精確公式，而不需依賴傳統的聯集上限 (union bound) 或是其他所謂的錯誤率近似值的分析技巧。

Optimal block-codes with a very small number of codewords are investigated for the binary input discrete memoryless channels. Those channels are the binary asymmetric channel (BAC), including the two special cases of the binary symmetric channel (BSC) and the Z-channel (ZC). The binary erasure channel (BEC) is a common used channel with ternary output. For the asymmetric channels, a general BAC, it is shown that so-called flip codes are optimal codes with two codewords. The optimal (in the sense of minimum average error probability, using maximum likelihood decoding) code structure is derived for the ZC in the cases of two, three, and four codewords and an arbitrary finite blocklength. For the symmetric channels, the BSC and the BEC, the optimal code structure is derived with at most three codewords and an arbitrary finite blocklength, a statement for linear optimal codes with four codes is also given.
The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the codebook matrix not row-wise (codewords), but column-wise. This new tool allows an elegant definition of interesting code families that is recursive in the blocklength n and admits their exact analysis of error performance that is not based on the union bound or other approximations.

1 Introduction 2

1.1 Introduction.................................... 2

2 Definitions

2.1 Discrete Memoryless Channel .......................... 6

2.2 Coding for DMC ................................. 7

3 Channel Models 11

4 Preliminaries 15

4.1 Error Probability of theBAC ........................ 15

4.1.1 Capacity of the BAC........................... 15

4.2 Error (and Success) Probability of the ZC................... 16

4.3 Error (and Success) Probability of the BSC .................. 17

4.3.1 Capacity of the BSC........................... 17

4.4 Error(andSuccess)Probability of the BEC.................. 17

4.4.1 Capacity of the BEC........................... 18

4.5 Pairwise Hamming Distance........................... 18

5 A Counter example 19

6 Flip Codes, Weak Flip Codes and Hadamard Codes 20

6.1 Characteristics of Weak Flip Codes....................... 25

7 Previous Work 29

7.1 SGB Bounds on the Average Error Probability . . . . . . . . . . . . . . . . 29

7.2 Gallager Bound.................................. 31

7.3 PPV Bounds for the BSC ............................ 32

7.4 PPV Bounds for the BEC............................ 33

8 Analysis of the BAC 34

8.1 OptimalCodes .................................. 34

8.2 The Optimal Decision Rule for Flip Codes................... 35

8.3 Best Codes for a Fixed Decision Rule...................... 37

9 Analysis of the ZC 42

9.1 Optimal Codes with Two Codewords (M=2). . . . . . . . . . . . . . . . . 42

9.2 Optimal Codes with Three or Four Codewords (M=3,4) . . . . . . . . . . 42

9.3 Error Exponents ................................. 46

9.4 Application to Known Bounds on the Error Probability for a Finite Block-length....................................... 46

9.5 Conjectured Optimal Codes with Five Codewords (M = 5) . . . . . . . . . 49

10 Analysis of the BSC 51

10.1 Optimal Codes with Two Codewords (M=2). . . . . . . . . . . . . . . . . 51

10.2 Optimal Codes with Three or Four Codewords (M=3,4) . . . . . . . . . . 51

10.3 Pairwise Hamming Distance Structure ..................... 53

10.4 Application to Known Bounds on the Error Probability for a Finite Block-length....................................... 55

11 Analysis of the BEC 59

11.1 Optimal Codes with Two Codewords (M=2). . . . . . . . . . . . . . . . . 59

11.2 Optimal Codes with Three or Four Codewords (M=3,4) . . . . . . . . . . 59
11.3 Quick Comparison between BSC and BEC................... 62

11.4 Application to Known Bounds on the Error Probability for a Finite Block-length....................................... 62

12 Conclusion 66

A Derivations concerning the BAC 67

A.1 Proof of Proposition 4.1 ............................. 67

A.2 The LLR Function ................................ 68

A.3 Alternative Proof of Theorem8.1........................ 69

A.4 Proof of Theorem 8.3............................... 73

B Derivations concerning the ZC 76

B.1 Proof of Theorem 9.2............................... 76

B.2 Proof of Lemma 9.5 ............................... 80

C Derivations concerning the BSC 84

C.1 Proof of Theorem 10.2.............................. 84

C.1.1 Case i: Step from n−1=3k−1 to n=3k .............. 86

C.1.2 Case ii: Step from n−1=3k to n=3k+1 .............. 92

C.1.3 Case iii: Step from n−1=3k+1 to n=3k+2............ 93

C.2 Proof of Theorem 10.3.............................. 94

D Derivations concerning the BEC 109

D.1 Proof of Theorem 11.2..............................109

List of Figures 110
Bibliography 112

[1] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423 and 623–656, July and October 1948.

[2] Y. Polyanskiy, H. V. Poor, and S. Verdu ́, “Channel coding rate in the finite block-length regime,” IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2307– 2359, May 2010.

[3] M. C. Gursoy, “Throughput analysis of buffer-constrained wireless systems in the finite blocklength regime,” in Proceedings IEEE International Conference on Communications (ICC), Kyoto, Japan, June 5–9, 2011.

[4] T. J. Riedl, T. P. Coleman, and A. C. Singer, “Finite block-length achievable rates for queuing timing channels,” in Proceedings IEEE Information Theory Workshop (ITW), Paraty, Brazil, October 16–20, 2011, pp. 200–204.

[5] A. Martinez and A. Guill ́en i F`abregas, “Saddlepoint approximation of random coding bounds,” in Proceedings Information Theory and Applications Workshop (ITA), University of California, San Diego, USA, February 6–11, 2011.

[6] R. G. Gallager, Information Theory and Reliable Communication. New York: John Wiley &; Sons, 1968.

[7] S. Shamai (Shitz) and S. Verdu ́, “The empirical distribution of good codes,” IEEE Transactions on Information Theory, vol. 43, no. 3, pp. 836–846, May 1997.

[8] C.-L. Wu, P.-N. Chen, Y. S. Han, and Y.-X. Zheng, “On the coding scheme for joint channel estimation and error correction over block fading channels,” in Proceedings IEEE International Symposium on Personal, Indoor and Mobile Radio Communica- tions (PIMRC), Tokyo, Japan, September 13–16, 2009, pp. 1272–1276.

[9] M. Dohler, R. W. Heath Jr., A. Lozano, C. B. Papadias, and R. A. Valenzuela, “Is the PHY layer dead?” IEEE Communications Magazine, vol. 49, no. 4, pp. 159–165, April 2011.

[10] J. N. Laneman, “On the distribution of mutual information,” in Proceedings Information Theory and Applications Workshop (ITA), University of California, San Diego, USA, February 6–10, 2006.

[11] D. Buckingham and M. C. Valenti, “The information-outage probability of finite-length codes over AWGN channels,” in Proceedings Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA, March 19–21, 2008, pp. 390–395.

[12] S. Lin and D. J. Costello, Jr., Error Control Coding, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2004.

[13] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Am- sterdam: North-Holland, 1977.

[14] P.-N. Chen, H.-Y. Lin, and S. M. Moser, “Weak flip codes and applications to op- timal code design on the binary erasure channel,” in Proceedings Fiftieth Allerton Conference on Communication, Control and Computing, Allerton House, Monticello, IL, USA, October 1–5, 2012.

[15] S. M. Moser, Information Theory (Lecture Notes), version 1, fall semester 2011/2012, Information Theory Lab, Department of Electrical Engineering, National Chiao Tung University (NCTU), September 2011. [Online]. Available: http://moser.cm.nc tu.edu.tw/scripts.html

[16] P.-N. Chen, H.-Y. Lin, and S. M. Moser, “Optimal ultra-small block-codes for binary discrete memoryless channels,” 2013, to appear in IEEE Transactions on Information Theory. [Online]. Available: http://moser.cm.nctu.edu.tw/publications. html

[17] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error prob- ability for coding on discrete memoryless channels,” Information and Control, pp. 522–552, May 1967, part II.

[18] P.-N. Chen, H.-Y. Lin, and S. M. Moser, “Equidistant codes meeting the Plotkin bound are not optimal on the binary symmetric channel,” to be presented at IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, July 7–13, 2013. [Online]. Available: http://moser.cm.nctu.edu.tw/publications.html

[19] S. J. MacMullan and O. M. Collins, “A comparison of known codes, random codes, and the best codes,” IEEE Transactions on Information Theory, vol. 44, no. 7, pp. 3009–3022, October 1998.

[20] Y. Polyanskiy, “Saddle point in the minimax converse for channel coding,” 2013, to appear in IEEE Transactions on Information Theory.