Capacity of noisy, discrete memoryless channels under input constraints

Abstract

ÖZET Bu tez çalışmasında girdi kısıtlamaları altında ayırtık, hafızasız kanalların sığaları incelenmektedir. Burada tartışılan girdi kısıtlamak kanallar için izin verilen girdi dizileri bir sonlu durumlu makinenin çıktıları olarak modellenebilir. Böyle bir kanalın sığasını hesaplayabilmek için verimli bir algoritma bilinmemektedir. Gürültüsüz durumda (kanal girdi harfiyle karşılık gelen çıktı harfi aynı olduğu zaman), Shannon[l] kanal sığasının, kısıtlandırılmış kanal girdi dizilerini üreten sonlu durumlu makinenin bitişiklik matrisinin en büyük özdeğerinin logaritmasına eşit olduğunu göstermiştir. Ayrıca, kanal sığasına ulaşan girdi dizileri üzerindeki olasılık dağılımı birinci dereceden bir markov dağılımıdır. Bu çalışmada biz gürültülü durumu tartışıyoruz. Belirli bir girdi kısıtlamalı kanal için, gürültüsüz durumdan farklı olarak, sığanın birinci dereceden bir markov dağılımı tarafından ulaşılamadığı gösterilmektedir. İzin verilen girdi dizileri üzerinde K'nıncı dereceden bir markov dağılımının ulaşabileceği en yüksek hız üzerine alt ve üst sınırlar elde edilmektedir. Hesaplamalar sonucunda ikinci dereceden bir dağılımın birinci dereceden bir dağılıma göre daha yüksek hızlara ulaştığı görülmüştür. Bu çalışmada ayrıca girdi kısıtlamalı kanalların sığaları üzerine bir üst sınırlar dizisi verilmektedir. Bu dizinin kanal sığasına yakınsadığı gösterilmektedir. Hesaplamalar sonu cunda bu çalışmada kullanılan kanallar için markov dağılımlarının kanal sığasına oldukça yakın hızlara ulaştıkları gözlenmektedir. Anahtar sözcükler: Kanal sığası, Girdi kısıtlamalı kanal, Sonlu durumlu makine, Markov dağılımı. m

ABSTRACT In this thesis work, we examine the capacity of discrete memoryless channels under input constraints. We consider a certain class of input-restricted channels for which con strained sequences can be modeled as outputs of a finite-state machine(FSM). No efficient algorithm is known for computing the capacity of such a channel. For the noiseless case, i.e., when the channel input letter and the corresponding output letter are identical, it is shown that [1] the channel capacity is the logarithm of the largest eigenvalue of the adjacency matrix of the state-transition diagram of the FSM generating the allowed chan nel input sequences. Furthermore, the probability distribution on the input sequences achieving the channel capacity is first-order markovian. Here, we discuss the noisy case. For a specific input-restricted channel, we show that unlike the noiseless case, the capacity is no longer achieved by a first-order distribution. We derive upper and lower bounds on the maximum rate achievable by a K-th order markovian distribution on the allowed input sequences. The computational results show that the second-order distribution does strictly better than the first-order distribution for this particular channel. A sequence of upper bounds on the capacity of an input-restricted channel is also given. We show that this sequence converges to the channel capacity. The numerical results clarify that markovian distribution may achieve rates close to the capacity for the channel considered in this work. Keywords: Channel capacity, Input-restricted channel, Finite-state machine, Marko vian distribution. 11