有限長度區間碼通道容量

Abstract

對於現今我們所使用的可靠傳輸通道，例如 : 光纖通道、紅外線傳輸通道、電波 無線傳輸通道、利用磁性材料的極性所作成的硬體等。上述的通道，如果在理論上有 完整的了解，對於之後整個系統的特性與極限有相當大的助益，而評估通道的重要參 數為薛能通道容量(Shannon Channel Capacity)是由克勞德.愛華德.薛能 (Claude E .Shannon)在1948年所發表的重要論文“通訊數學理論”所定義的。而薛能通道容量 說明了在給定通道的情況下，最大可以傳輸的消息量為多少，如果我們想使用更高的 傳輸速率的話是不可能的，因為錯誤率會隨著傳輸區塊長度呈指數的成長至一。從另 一方面來看，它代表著我們可以使用低於薛能通道容量的速率來傳送，而錯誤率可以 低於我們任意給定的值。因此薛能通道容量可以完整描述通道容量的極限。 可惜的是，薛能通道容量做了兩個理論上的假設，但我們在使用時通常不會去驗 證該系統是否符合這兩項假設，而第一個假設為傳輸端與接收端可獲得的能量沒有限 制；第二個假設為忽略任何延遲上的限制，事實上薛能所定義的區塊碼長度是無限長， 換而言之，我們系統中將會有濳在無限長的延遲時間。然而現行使用的通訊系統對於 最大的延遲時間都有相當嚴格的限制，尤其是當與人有直接反應的通訊傳輸時。 所以本計畫將會用較接近現實的方式處理延遲時間 : 我們將會對通道容量的定 義作一些修改，以便把延遲時間的限制加入。為了達到此目的，我們會放鬆對錯誤率 的要求 : 不再要求錯誤率趨近零，當區塊碼長度趨近無限大時，而是去要求錯誤率小 於某個給定的值。換句話說，本計畫的主要目的就是去尋找理論上最大可能的傳輸速 率在給定的傳輸通道下，且假設無限的計算能量，最大延遲時間的限制且給定有限的 錯誤率下。

Any communication system in use relies on a certain communication channel. Examples of such channels are optical links on glass fibers, infrared links through air, electromagnetic radiation through air (directed or omnidirectional), or polarization of the magnetic material of a harddrive. For any such channel, it is important to have a profound theoretical understanding of its working, its potential, and its limitations. One parameter that is fundamental for this understanding is the so-called Shannon channel capacity as defined by Claude E. Shannon in his famous landmark paper “A Mathematical Theory of Communication” from 1948. The Shannon capacity gives a fundamental upper limit on the amount of information that can be transferred over the given channel: any attempt to transmit at a higher information rate than the capacity will utterly fail in the sense that the probability of error will tend to one with increasing blocklength exponentially fast. On the other hand it is theoretically possible to transmit information at a rate smaller than capacity with an error probability being as small as one wishes. Hence the Shannon capacity describes a fundamental limit on communication that is imposed by nature. Unfortunately, Shannon’s capacity definition is theoretic in the sense that it makes two, usually not justifiable assumptions about the system in use: firstly, it assumes that the available computational power both at transmitter and receiver is unlimited, and secondly, it ignores any constraints on delay. As a matter of fact, by definition Shannon’s channel capacity assumes a blocklength n going to infinity, i.e., there is a potentially unlimited delay in the system. However, most communication systems in use have very strict limitations concerning the maximum allowed delay, particularly, if the communication involves direct interaction between humans. This project addresses delay in a more realistic way: we will try to adapt the definition of channel capacity so as to incorporate the need of restricting the maxi- mum delay. In order to do so we will relax the conditions on the error probability: instead of asking the probability of error to tend to zero as the blocklength tends to infinity, we will be content with it being smaller than some given finite value. I.e., it is the main goal of this project to find some answers to the following ques- tion: what is the maximum theoretically possible communication rate over a given communication channel when we assume that we have infinite computation power, a maximum allowed delay, and a finite given probability of error?