二元無記憶通道的最佳極小區塊碼設計

Abstract

在這篇論文中，我們探討數種二元無記憶通道模式下的極小區塊碼 (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.