Ο υπολογισμός της χωρητικότητας Shannon ενός τηλεπικοινωνιακού καναλιού είναι ένα από τα κλασικά προβλήματα της θεωρίας πληροφορίας. Η τιμή της προσδιορίζει το μέγιστο δυνατό ρυθμό αξιόπιστης μετάδοσης μέσα από το κανάλι και αποτελεί ρυθμιστική παράμετρο κατά το σχεδιασμό κάθε τηλεπικοινωνιακού συστήματος. Στις πιο ενδιαφέρουσες περιπτώσεις ο υπολογισμός καταλήγει σε ένα πρόβλημα βελτιστοποίησης για το οποίο δε μπορεί να δοθεί αναλυτική λύση, οπότε καταφεύγουμε στη χρήση προσεγγιστικών μεθόδων ή στη διατύπωση φραγμάτων. Στα πλαίσια της εργασίας μελετάται η χωρητικότητα Shannon τηλεπικοινωνιακών καναλιών ενός ή πολλαπλών χρηστών. Η μελέτη ξεκινά από την απλές περιπτώσεις του διακριτού καναλιού χωρίς μνήμη (DMC) και του καναλιού AWGN και επεκτείνεται στις πιο ενδιαφέρουσες περιπτώσεις των σύμφωνων ή μη (coherence/non-coherence) καναλιών διάλειψης, σε κανάλια με μνήμη, κανάλια πολλαπλών κεραιών και κανάλια πολλαπλών χρηστών. Σε κάθε περίπτωση καταγράφονται τα σημαντικότερα ερευνητικά αποτελέσματα σχετικά με το πρόβλημα προσδιορισμού της χωρητικότητας, τη συμπεριφορά της σε σχέση με τους παράγοντες του τηλεπικοινωνιακού μοντέλου, του αλγοριθμικού υπολογισμού της και τα χαρακτηριστικά που πρέπει να έχει η είσοδος ώστε να επιτυγχάνεται η τιμή της. / Computing the Shannon Capacity of a communication channel is one of the classic problems of information theory. Its value determine the maximum possible rate of reliable transmission through the channel and constitutes a design parameter during the designing of the communication system. In most interesting cases the problem ending to an optimization problem which can’t be solved analytically, so we refuge to approximating methods and we can only state bounds for the region in which capacity belongs. In this thesis we study the Shannon Capacity of single user and multiple user communications systems. The study begins with the simple cases of Discrete Memoryless Channel (DMC) and AWGN channel and goes further to more interesting cases like coherence/non-coherence fading channels, channels with memory, multiple antenna channels and channels with multiple users. In each case, we present the most important scientific results considering the problem of capacity, its behavior in relation to the parameters of the communication model, its algorithmic computation and the characteristics of the optimal input.

In this thesis, we consider a vector Gaussian multiple access channel (MAC) with users demanding reliable communication at specific (Shannon-theoretic) rates. The objective is to assign vectors and powers to these users such that their rate requirements are met and the sum of powers received is minimum. We identify this power minimization problem as an instance of a separable convex optimization problem with linear ascending constraints. Under an ordering condition on the slopes of the functions at the origin, an algorithm that determines the optimum point in a finite number of steps is described. This provides a complete characterization of the minimum sum power for the vector Gaussian multiple access channel. Furthermore, we prove a strong duality between the above sum power minimization problem and the problem of sum rate maximization under power constraints. We then propose finite step algorithms to explicitly identify an assignment of vectors and powers that solve the above power minimization and sum rate maximization problems. The distinguishing feature of the proposed algorithms is the size of the output vector sets. In particular, we prove an upper bound on the size of the vector sets that is independent of the number of users. Finally, we restrict vectors to an orthonormal set. The goal is to identify an assignment of vectors (from an orthonormal set) to users such that the user rate requirements is met with minimum sum power. This is a combinatorial optimization problem. We study the complexity of the decision version of this problem. Our results indicate that when the dimensionality of the vector set is part of the input, the decision version is NP-complete.

We consider the transmission of correlated sources over a multiple access channel(MAC). Multiple access channels are important building blocks in many practical communication systems, e.g., local area networks(LAN), cellular systems, wireless multi-hop networks. Thus this topic has been studied for last several decades. One recent motivation is estimating a random field via wireless sensor networks. Often the sensor nodes are densely deployed resulting in correlated observations. These sensor nodes need to transmit their correlated observations to a fusion center which uses this data to estimate the sensed random field. Sensor nodes have limited computational and storage capabilities and very limited energy. Since transmission is very energy intensive, it is important to minimize it. This motivates our problem of energy efficient transmission of correlated sources over a sensor network. Sensor networks are often arranged in a hierarchical fashion. Neighboring nodes can first transmit their data to a cluster head which can further compress information before transmission to the fusion center. The transmission of data from sensor nodes to their cluster-head is usually through a MAC. At the fusion center the underlying physical process is estimated. The main trade-off possible is between the rates at which the sensors send their observations and the distortion incurred in estimation at the fusion center. The availability of side information at the encoders and/or the decoder can reduce the rate of transmission. In this thesis, the above scenario is modeled as an information theoretic problem. Efficient joint source-channel codes are discussed under various assumptions on side information and distortion criteria. Sufficient conditions for transmission of discrete/continuous alphabet sources with a given distortion over a discrete/continuous alphabet MAC are given. We recover various previous results as special cases from our results. Furthermore, we study the practically important case of the Gaussian MAC(GMAC) in detail and propose new joint source-channel coding schemes for discrete and continuous sources. Optimal schemes are identified in different scenarios. The protocols like TDMA, FDMA and CDMA are widely used across systems and standards. When these protocols are used the MAC becomes a system of orthogonal channels. Our general conditions can be specialized to obtain sufficient conditions for lossy transmission over this system. Using this conditions, we identify an optimal scheme for transmission of Gaussian sources over orthogonal Gaussian channels and show that the Amplify and Forward(AF) scheme performs close to the optimal scheme even at high SNR. Next we investigate transmission of correlated sources over a fast fading MAC with perfect or partial channel state information available at both the encoders and the decoder. We provide sufficient conditions for transmission with given distortions. We also provide power allocation policies for efficient transmission. Next, we use MAC with side information as a building block of a hierarchical sensor network. For Gaussian sources over Gaussian MACs, we show that AF performs well in such sensor network scenarios where the battery power is at a premium. We then extend this result to the hierarchical network scenario and show that it can perform favourably to the Slepian-Wolf based source coding and independent channel coding scheme. In a hierarchical sensor network the cluster heads often need to send only a function of the sensor observations to the fusion center. In such a setup the sensor nodes can compress the data sent to the cluster head exploiting the correlation in the data and also the structure of the function to be computed at the cluster head. Depending upon the function, exploiting the structure of the function can substantially reduce the data rate for transmission. We provide efficient joint source-channel codes for transmitting a general class of functions of the sources over the MAC.

No description available.

Opportunistic selection algorithms have grown in importance as next generation wireless systems strive towards higher data rates and spectral efficiencies. For example, in orthogonal frequency division multiple access(OFDMA), the system bandwidth is divided into many sub channels. For each sub channel, the user with the highest channel gain is opportunistically assigned to it. .Likewise, in a multi-source, multi-destination (MSD) cooperative relay system, a relay node must be assigned for every source-destination (SD) pair. The assignment decisions are based on local channel knowledge and must be fast so as to maximize the time available for data transmission. We develop novel multiple access based splitting-based selection algorithms for OFDMA and MSD systems. These systems are unique in that the same user and relay can be the most suitable one for multiple sub channels and multiple SD pairs, respectively. For OFDMA systems, we propose an algorithm called Split Select that assigns for every sub channel the user with the highest channel gain over it. For MSD systems, we propose a contention-based en masse assignment (CBEA) algorithm that assigns to each SD pair a relay that is capable of aiding it. Both Split Select and CBEA are fast and scale well with the number of nodes. For example, Split Select requires just 2.2 slots, on average, to assign a sub channel to its best user even when there are an asymptotically large number of contending users. Likewise, CBEA often takes far less than one slot, on average, to assign a relay to each SD pair.