On capacity of line networks | EPFL Graph Search

We consider communication through a cascade of discrete memoryless channels (DMCs). The source and destination node of this cascade are allowed to use coding schemes of arbi- trary 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 at the relays, we prove that this intermediate processing can be chosen to be identical without loss of optimality, and that the capacity of the cascade coincides with the rate of the best zero-error code of length equal to the block length of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, convergence of capacity as the length of the cascade goes to infinity is exponentially fast. Finally, we characterize how the block length 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 block length scales logarithmically with the network length in order to achieve any rate above the zero-error capacity. We show that in many cases of interest logarithmic growth is also necessary.

Re-proving Channel Polarization Theorems

Mine Alsan

The general subject considered in this thesis is a recently discovered coding technique, polar coding, which is used to construct a class of error correction codes with unique properties. In his ground-breaking work, Arikan proved that this class of codes, called polar codes, achieve the symmetric capacity --- the mutual information evaluated at the uniform input distribution ---of any stationary binary discrete memoryless channel with low complexity encoders and decoders requiring in the order of

O(N\log N)

operations in the block-length

N

. This discovery settled the long standing open problem left by Shannon of finding low complexity codes achieving the channel capacity. Polar codes are not only appealing for being the first to 'close the deal'. In contrast to most of the existing coding schemes, polar codes admit an explicit low complexity construction. In addition, for symmetric channels, the polar code construction is deterministic; the theoretically beautiful but practically limited "average performance of an ensemble of codes is good, so there must exist one particular code in the ensemble at least as good as the average'' formalism of information theory is bypassed. Simulations are thus not necessary in principle for evaluating the error probability which is shown in a study by Telatar and Arikan to scale exponentially in the square root of the block-length. As such, at the time of this writing, polar codes are appealing for being the only class of codes proved, and proved with mathematical elegance, to possess all of these properties. Polar coding settled an open problem in information theory, yet opened plenty of challenging problems that need to be addressed. This novel coding scheme is a promising method from which, in addition to data transmission, problems such as data compression or compressed sensing, which includes all types of measurement processes like the MRI or ultrasound, could benefit in terms of efficiency. To make this technique fulfill its promise, the original theory has been, and should still be, extended in multiple directions. A significant part of this thesis is dedicated to advancing the knowledge about this technique in two directions. The first one provides a better understanding of polar coding by generalizing some of the existing results and discussing their implications, and the second one studies the robustness of the theory over communication models introducing various forms of uncertainty or variations into the probabilistic model of the channel. See the fulltext of the thesis for the complete abstract.

EPFL2015

Introducing the CLEF 2020 HIPE Shared Task: Named Entity Recognition and Linking on Historical Newspapers

Maud Ehrmann, Matteo Romanello

Since its introduction some twenty years ago, named entity (NE) processing has become an essential component of virtually any text mining application and has undergone major changes. Recently, two main trends characterise its developments: the adoption of deep learning architectures and the consideration of textual material originating from historical and cultural heritage collections. While the former opens up new opportunities, the latter introduces new challenges with heterogeneous, historical and noisy inputs. If NE processing tools are increasingly being used in the context of historical documents, performance values are below the ones on contemporary data and are hardly comparable. In this context, this paper introduces the CLEF 2020 Evaluation Lab HIPE (Identifying Historical People, Places and other Entities) on named entity recognition and linking on diachronic historical newspaper material in French, German and English. Our objective is threefold: strengthening the robustness of existing approaches on non-standard inputs, enabling performance comparison of NE processing on historical texts, and, in the long run, fostering efficient semantic indexing of historical documents in order to support scholarship on digital cultural heritage collections.

Springer International Publishing2020

Re-proving Channel Polarization Theorems

Mine Alsan

O(N\log N)

operations in the block-length

N

EPFL2015