This dissertation has its focus on two different topics: 1. non-asymptotic analysis of polar codes as a new paradigm in error correcting codes with very promising features, and 2. network properties for wireless networks of practical size. In its first part, we investigate properties of polar codes that can be potentially useful in real-world applications. We start with analyzing the performance of finite-length polar codes over the binary erasure channel (BEC), while assuming belief propagation (BP) as the decoding method. We provide a stopping set analysis for the factor graph of polar codes, where we find the size of the minimum stopping set. Our analysis along with bit error rate (BER) simulations demonstrates that finite-length polar codes show superior error floor performance compared to the conventional capacity-approaching coding techniques. Motivated by good error floor performance, we introduce a modified version of BP decoding while employing a guessing algorithm to improve the BER performance. Each application may impose its own requirements on the code design. To be able to take full advantage of polar codes in practice, a fundamental question is which practical requirements are best served by polar codes. For example, we will see that polar codes are inherently well-suited for rate-compatible applications and they can provably achieve the capacity of time-varying channels with a simple rate-compatible design. This is in contrast to LDPC codes for which no provably universally capacity-achieving design is known except for the case of the erasure channel. This dissertation investigates different approaches to applications such as UEP, rate-compatible coding, and code design over parallel sub-channels (non-uniform error correction). Furthermore, we consider the idea of combining polar codes with other coding schemes, in order to take advantage of polar codes' best properties while avoiding their shortcomings. Particularly, we propose, and then analyze, a polar code-based concatenated scheme to be used in Optical Transport Networks (OTNs) as a potential real-world application The second part of the dissertation is devoted to the analysis of finite wireless networks as a fundamental problem in the area of wireless networking. We refer to networks as being finite when the number of nodes is less than a few hundred. Today, due to the vast amount of literature on large-scale wireless networks, we have a fair understanding of the asymptotic behavior of such networks. However, in real world we have to face finite networks for which the asymptotic results cease to be valid. Here we study a model of wireless networks, represented by random geometric graphs. In order to address a wide class of the network's properties, we study the threshold phenomena. Being extensively studied in the asymptotic case, the threshold phenomena occurs when a graph theoretic property (such as connectivity) of the network experiences rapid changes over a specific interval of the underlying parameter. Here, we find an upper bound for the threshold width of finite line networks represented by random geometric graphs. These bounds hold for all monotone properties of such networks. We then turn our attention to an important non-monotone characteristic of line networks which is the Medium Access (MAC) layer capacity, defined as the maximum number of possible concurrent transmissions. Towards this goal, we provide a linear time algorithm which finds a maximal set of concurrent non-interfering transmissions and further derive lower and upper bounds for the cardinality of the set. Using simulations, we show that these bounds serve as reasonable estimates for the actual value of the MAC-layer capacity.

Transmitting quantum information across quantum channels is an important task. However quantum information is delicate, and is easily corrupted. We address the task of protecting quantum information from an information theoretic perspective -- we encode some message qudits into a quantum code, send the encoded quantum information across the noisy quantum channel, then recover the message qudits by decoding. In this dissertation, we discuss the coding problem from several perspectives.} The noisy quantum channel is one of the central aspects of the quantum coding problem, and hence quantifying the noisy quantum channel from the physical model is an important problem. We work with an explicit physical model -- a pair of initially decoupled quantum harmonic oscillators interacting with a spring-like coupling, where the bath oscillator is initially in a thermal-like state. In particular, we treat the completely positive and trace preserving map on the system as a quantum channel, and study the truncation of the channel by truncating its Kraus set. We thereby derive the matrix elements of the Choi-Jamiolkowski operator of the corresponding truncated channel, which are truncated transition amplitudes. Finally, we give a computable approximation for these truncated transition amplitudes with explicit error bounds, and perform a case study of the oscillators in the off-resonant and weakly-coupled regime numerically. In the context of truncated noisy channels, we revisit the notion of approximate error correction of finite dimension codes. We derive a computationally simple lower bound on the worst case entanglement fidelity of a quantum code, when the truncated recovery map of Leung et. al. is rescaled. As an application, we apply our bound to construct a family of multi-error correcting amplitude damping codes that are permutation-invariant. This demonstrates an explicit example where the specific structure of the noisy channel allows code design out of the stabilizer formalism via purely algebraic means. We study lower bounds on the quantum capacity of adversarial channels, where we restrict the selection of quantum codes to the set of concatenated quantum codes. The adversarial channel is a quantum channel where an adversary corrupts a fixed fraction of qudits sent across a quantum channel in the most malicious way possible. The best known rates of communicating over adversarial channels are given by the quantum Gilbert-Varshamov (GV) bound, that is known to be attainable with random quantum codes. We generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region. We next study upper bounds on the quantum capacity of some low dimension quantum channels. The quantum capacity of a quantum channel is the maximum rate at which quantum information can be transmitted reliably across it, given arbitrarily many uses of it. While it is known that random quantum codes can be used to attain the quantum capacity, the quantum capacity of many classes of channels is undetermined, even for channels of low input and output dimension. For example, depolarizing channels are important quantum channels, but do not have tight numerical bounds. We obtain upper bounds on the quantum capacity of some unital and non-unital channels -- two-qubit Pauli channels, two-qubit depolarizing channels, two-qubit locally symmetric channels, shifted qubit depolarizing channels, and shifted two-qubit Pauli channels -- using the coherent information of some degradable channels. We use the notion of twirling quantum channels, and Smith and Smolin's method of constructing degradable extensions of quantum channels extensively. The degradable channels we introduce, study and use are two-qubit amplitude damping channels. Exploiting the notion of covariant quantum channels, we give sufficient conditions for the quantum capacity of a degradable channel to be the optimal value of a concave program with linear constraints, and show that our two-qubit degradable amplitude damping channels have this property.

In this thesis, we present low latency general concatenated code structures suitable for parallel processing. We propose parallel decodable serially concatenated codes (PDSCCs) which is a general structure to construct many variants of serially concatenated codes. Using this most general structure we derive parallel decodable serially concatenated convolutional codes (PDSCCCs). Convolutional product codes which are instances of PDSCCCs are studied in detail. PDSCCCs have much less decoding latency and show almost the same performance compared to classical serially concatenated convolutional codes. Using the same idea, we propose parallel decodable turbo codes (PDTCs) which represent a general structure to construct parallel concatenated codes. PDTCs have much less latency compared to classical turbo codes and they both achieve similar performance. We extend the approach proposed for the construction of parallel decodable concatenated codes to trellis coded modulation, turbo channel equalization, and space time trellis codes and show that low latency systems can be constructed using the same idea. Parallel decoding operation introduces new problems in implementation. One such problem is memory collision which occurs when multiple decoder units attempt accessing the same memory device. We propose novel interleaver structures which prevent the memory collision problem while achieving performance close to other interleavers.

The objective of this thesis is to improve the performance of real-time communication overa wireless channel, by means of specifically tailored channel coding. The deadlinedependent coding (DDC) communication protocol presented here lets the timeliness and thereliability of the delivered information constitute quality of service (QoS) parametersrequested by the application. The values of these QoS parameters are transformed intoactions taken by the link layer protocol in terms of adaptive coding strategies.Incremental redundancy hybrid automatic repeat request (IR-HARQ) schemes usingrate compatible punctured codes are appealing since no repetition of previously transmittedbits is made. Typically, IR-HARQ schemes treat the packet lengths as fixed and maximizethe throughput by optimizing the puncturing pattern, i.e. the order in which the coded bitsare transmitted. In contrast, we define an IR strategy as the maximum number of allowedtransmissions and the number of code bits to include in each transmission. An approach isthen suggested to find the optimal IR strategy that maximizes the average code rate, i.e., theoptimal partitioning of n-kparity bits over at most M transmissions, assuming a givenpuncturing pattern. Concatenated coding used in IR-HARQ schemes provides a new arrayof possibilities for adaptability in terms of decoding complexity and communication timeversus reliability. Hence, critical reliability and timing constraints can be readily evaluatedas a function of available system resources. This in turn enables quantifiable QoS and thusnegotiable QoS. Multiple concatenated single parity check codes are chosen as examplecodes due to their very low decoding complexity. Specific puncturing patterns for thesecomponent codes are obtained using union bounds based on uniform interleavers. Thepuncturing pattern that has the best performance in terms of frame error rate (FER) at a lowsignal-to-noise ratio (SNR) is chosen. Further, using extrinsic information transfer (EXIT)analysis, rate compatible puncturing ratios for the constituent component code are found.The puncturing ratios are chosen to minimize the SNR required for convergence.The applications targeted in this thesis are not necessarily replacement of cables inexisting wired systems. Instead the motivation lies in the new services that wireless real-time communication enables. Hence, communication within and between cooperatingembedded systems is typically the focus. The resulting IR-HARQ-DDC protocol presentedhere is an efficient and fault tolerant link layer protocol foundation using adaptiveconcatenated coding intended specifically for wireless real-time communications. / Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, 2198, Technical report. D, 29,

Transmitting quantum information across quantum channels is an important task. However quantum information is delicate, and is easily corrupted. We address the task of protecting quantum information from an information theoretic perspective -- we encode some message qudits into a quantum code, send the encoded quantum information across the noisy quantum channel, then recover the message qudits by decoding. In this dissertation, we discuss the coding problem from several perspectives.} The noisy quantum channel is one of the central aspects of the quantum coding problem, and hence quantifying the noisy quantum channel from the physical model is an important problem. We work with an explicit physical model -- a pair of initially decoupled quantum harmonic oscillators interacting with a spring-like coupling, where the bath oscillator is initially in a thermal-like state. In particular, we treat the completely positive and trace preserving map on the system as a quantum channel, and study the truncation of the channel by truncating its Kraus set. We thereby derive the matrix elements of the Choi-Jamiolkowski operator of the corresponding truncated channel, which are truncated transition amplitudes. Finally, we give a computable approximation for these truncated transition amplitudes with explicit error bounds, and perform a case study of the oscillators in the off-resonant and weakly-coupled regime numerically. In the context of truncated noisy channels, we revisit the notion of approximate error correction of finite dimension codes. We derive a computationally simple lower bound on the worst case entanglement fidelity of a quantum code, when the truncated recovery map of Leung et. al. is rescaled. As an application, we apply our bound to construct a family of multi-error correcting amplitude damping codes that are permutation-invariant. This demonstrates an explicit example where the specific structure of the noisy channel allows code design out of the stabilizer formalism via purely algebraic means. We study lower bounds on the quantum capacity of adversarial channels, where we restrict the selection of quantum codes to the set of concatenated quantum codes. The adversarial channel is a quantum channel where an adversary corrupts a fixed fraction of qudits sent across a quantum channel in the most malicious way possible. The best known rates of communicating over adversarial channels are given by the quantum Gilbert-Varshamov (GV) bound, that is known to be attainable with random quantum codes. We generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region. We next study upper bounds on the quantum capacity of some low dimension quantum channels. The quantum capacity of a quantum channel is the maximum rate at which quantum information can be transmitted reliably across it, given arbitrarily many uses of it. While it is known that random quantum codes can be used to attain the quantum capacity, the quantum capacity of many classes of channels is undetermined, even for channels of low input and output dimension. For example, depolarizing channels are important quantum channels, but do not have tight numerical bounds. We obtain upper bounds on the quantum capacity of some unital and non-unital channels -- two-qubit Pauli channels, two-qubit depolarizing channels, two-qubit locally symmetric channels, shifted qubit depolarizing channels, and shifted two-qubit Pauli channels -- using the coherent information of some degradable channels. We use the notion of twirling quantum channels, and Smith and Smolin's method of constructing degradable extensions of quantum channels extensively. The degradable channels we introduce, study and use are two-qubit amplitude damping channels. Exploiting the notion of covariant quantum channels, we give sufficient conditions for the quantum capacity of a degradable channel to be the optimal value of a concave program with linear constraints, and show that our two-qubit degradable amplitude damping channels have this property.

Cette thèse est consacrée à l'amélioration des performances de codage/décodage de systèmes de transmission d'images fixes sur des canaux bruités et réalistes. Nous proposons, à cet effet, le développement de méthodes de transmission d'images optimisées en se focalisant sur les deux couches application et physique des réseaux sans fil. Au niveau de la couche application et afin d'assurer une bonne qualité de service, on utilise des algorithmes de compression efficaces permettant au récepteur de reconstruire l'image avec un maximum de fidélité (JPEG2000 et JPWL). Afin d'assurer une transmission sur des canaux sans fil avec un minimum de TEB à la réception, des techniques de transmission, de codage et de modulation avancées sont utilisées au niveau de la couche physique (système MIMO-OFDM, modulation adaptative, CCE, etc). Dans un premier temps, nous proposons un système de transmission robuste d'images codées JPWL intégrant un schéma de décodage conjoint source-canal basé sur des techniques de décodage à entrées pondérées. On considère, ensuite, l'optimisation d'une chaîne de transmission d'images sur un canal MIMO-OFDM sans fil réaliste. La stratégie de transmission d'images optimisée s'appuie sur des techniques de décodage à entrées pondérées et une approche d'adaptation de lien. Ainsi, le schéma de transmission proposé offre la possibilité de mettre en oeuvre conjointement de l'UEP, de l'UPA, de la modulation adaptative, du codage de source adaptatif et de décodage conjoint pour améliorer la qualité de l'image à la réception. Dans une seconde partie, nous proposons un système robuste de transmission de flux progressifs basé sur le principe de turbo décodage itératif de codes concaténés offrant une stratégie de protection inégale de données. Ainsi, l'originalité de cette étude consiste à proposer des solutions performantes d'optimisation globale d'une chaîne de communication numérique pour améliorer la qualité de transmission. / This work is devoted to improve the coding/ decoding performance of a transmission scheme over noisy and realistic channels. For this purpose, we propose the development of optimized image transmission methods by focusing on both application and physical layers of wireless networks. In order to ensure a better quality of services, efficient compression algorithms (JPEG2000 and JPWL) are used in terms of the application layer enabling the receiver to reconstruct the images with maximum fidelity. Furthermore, to insure a transmission on wireless channels with a minimum BER at reception, some transmission, coding and advanced modulation techniques are used in the physical layer (MIMO-OFDM system, adaptive modulation, FEC, etc). First, we propose a robust transmission system of JPWL encoded images integrating a joint source-channel decoding scheme based on soft input decoding techniques. Next, the optimization of an image transmission scheme on a realistic MIMO-OFDM channel is considered. The optimized image transmission strategy is based on soft input decoding techniques and a link adaptation approach. The proposed transmission scheme offers the possibility of jointly implementing, UEP, UPA, adaptive modulation, adaptive source coding and joint decoding strategies, in order to improve the image visual quality at the reception. Then, we propose a robust transmission system for embedded bit streams based on concatenated block coding mechanism offering an unequal error protection strategy. Thus, the novelty of this study consists in proposing efficient solutions for the global optimization of wireless communication system to improve transmission quality.