Niesen, U. ; Fragouli, C. ; Tuninetti, D.

In: IEEE Transactions on Information Theory, vol. 53, num. 11, 2007, p. 4039-4058

Date: 2007

We consider communication through a cascade of discrete memoryless channels. The source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of a fixed length. We investigate how the processing at the relays must be chosen in order to maximize the capacity of the cascade, that is, the maximum achievable end-to-end rate between the source and the destination. For infinite cascades with fixed intermediate processing length, we prove that the intermediate processing at the relays can be chosen to be identical without loss of optimality. In this case, we show that the capacity of the cascade coincides with the rate of the best zero error code of length equal to the blocklength of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, the limiting value of the end-to-end rate is achieved exponentially fast in the length of the cascade. Finally, we characterize how the blocklength of the intermediate processing must scale with the length of the cascade to guarantee a constant end-to-end rate. We prove that it is sufficient that the blocklength scales logarithmically with the network length in order to achieve any rates above the zero error capacity. We also show that in many cases of interest logarithmic grow is also necessary.

Keyword(s): channel capacity, channel coding, memoryless systems, coding scheme, discrete memoryless channel, intermediate processing length, line network, zero-error code

Reference: ARNI-ARTICLE-2006-001