Title: Goppa codes and their applications Author: Bc. Jaroslav Kotil Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc. Abstract: In this diploma paper we introduce Goppa codes, describe their para- metres and inclusion in Alternant codes, which are residual Generalized Reed- Solomon codes, and Algebraic-geometry codes. Aftewards we demonstrate deco- ding of Goppa codes and introduce Wild Goppa codes. We also describe post- quantum cryptography member: McEliece cryptosystem for which no effective attacks with quantum computers are known. We outline a usage of this crypto- system with Goppa codes and describe the security of the cryptosystem together with possible attacks of which the most effective ones are based on information- set decoding. Keywords: Goppa codes, Generalized Reed-Solomon codes, Algebraic-geometry codes, Post-quantum cryptography, McEliece cryptosystem 1

This research is concerned with the reliable delivery of scalable compressed data over lossy communication channels. Recent works proposed several strategies for assigning optimal code redundancies to elements of scalable data, which form a linear structure of dependency, under the assumption that all source elements are encoded onto a common group of network packets. Given large data and small network packets, such schemes require very long channel codes with high computational complexity. In networks with high loss, small packets are more desirable than long packets. The first contribution of this thesis is to propose a strategy for optimally assigning elements of the scalable data to clusters of packets, subject to constraints on packet size and code complexity. Given a packet cluster arrangement, the scheme then assigns optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results show that the proposed strategy can outperform the previous code assignment schemes subject to the above-mentioned constraints, particularly at high channel loss rates. Secondly, we modify these schemes to accommodate complex structures of dependency. Source elements are allocated to clusters of packets according to their dependency structure, subject to constraints on packet size and channel codeword length. Given a packet cluster arrangement, the proposed schemes assign optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results demonstrate the superiority of the proposed strategies for correctly modelling the dependency structure. The last contribution of this thesis is to propose a scheme for optimizing protection of scalable data where limited retransmission is possible. Previous work assumed that retransmission is not possible. For most real-time or interactive applications, however, retransmission of lost data may be possible up to some limit. In the present work we restrict our attention to streaming sources (e.g., video) where each source element can be transmitted in one or both of two time slots. An optimization algorithm determines the transmission and level of protection for each source element, using information about the success of earlier transmissions. Experimental results confirm the benefit of limited retransmission.

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

This dissertation considers several coding techniques based on Reed-Solomon (RS) and low-density parity-check (LDPC) codes. These two prominent families of error-correcting codes have attracted a great amount of interest from both theorists and practitioners and have been applied in many communication scenarios. In particular, data storage systems have greatly benefited from these codes in improving the reliability of the storage media. The first part of this dissertation presents a unified framework based on rate-distortion (RD) theory to analyze and optimize multiple decoding trials of RS codes. Finding the best set of candidate decoding patterns is shown to be equivalent to a covering problem which can be solved asymptotically by RD theory. The proposed approach helps understand the asymptotic performance-versus-complexity trade-off of these multiple-attempt decoding algorithms and can be applied to a wide range of decoders and error models. In the second part, we consider spatially-coupled (SC) codes, or terminated LDPC convolutional codes, over intersymbol-interference (ISI) channels under joint iterative decoding. We empirically observe the phenomenon of threshold saturation whereby the belief-propagation (BP) threshold of the SC ensemble is improved to the maximum a posteriori (MAP) threshold of the underlying ensemble. More specifically, we derive a generalized extrinsic information transfer (GEXIT) curve for the joint decoder that naturally obeys the area theorem and estimate the MAP and BP thresholds. We also conjecture that SC codes due to threshold saturation can universally approach the symmetric information rate of ISI channels. In the third part, a similar analysis is used to analyze the MAP thresholds of LDPC codes for several multiuser systems, namely a noisy Slepian-Wolf problem and a multiple access channel with erasures. We provide rigorous analysis and derive upper bounds on the MAP thresholds which are shown to be tight in some cases. This analysis is a first step towards proving threshold saturation for these systems which would imply SC codes with joint BP decoding can universally approach the entire capacity region of the corresponding systems.

Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher-Kiayias-Yung is extended to the polynomials whose degrees are allowed to be distinct. Furthermore, it is observed that probability of the algorithm can be increased. Specifically, for a finite field $F$, we present a probabilistic algorithm which can recover polynomials $p_1,ldots, p_r in F[x]$ of degree less than $k_1,k_2,ldots,k_r$, respectively with given field evaluations $p_l(z_i) = y_{i,l}$ for all $i in I$, $|I|=t$ and $l in [r]$ with probability at least $1 - (n - t)/|F|$ and with time complexity at most $O((nr)^3)$. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed-Solomon codes. It is observed that interleaved Reed-Solomon codes over $F$ with rate $R$ can be decoded up to burst error rate $frac{r}{r+1}(1 - R)$ probabilistically for an interleaving parameter $r$. It is proved that a Reed-Solomon code RS$(n / k)$ can be decoded up to error rate $frac{r}{r+1}(1 - R&#039 / )$ for $R&#039 / = frac{(k-1)(r+1)+2}{2n}$ when probabilistic interleaved Reed-Solomon decoders are applied. Similarly, for a finite field $F_{q^2}$, it is proved that $q$-folded Hermitian codes over $F_{q^{2q}}$ with rate $R$ can be decoded up to error rate $frac{q}{q+1}(1 - R)$ probabilistically. On the other hand, it is observed that interleaved codes whose subcodes would have different minimum distances can be list decodable up to radius of minimum of list decoding radiuses of subcodes. Specifically, we present a list decoding algorithm for $C$, which is interleaving of $C_1,ldots, C_b$ whose minimum distances would be different, decoding up to radius of minimum of list decoding radiuses of $C_1,ldots, C_b$ with list size polynomial in the maximum of list sizes of $C_1,ldots, C_b$ and with time complexity polynomial in list size of $C$ and $b$. Next, by using this list decoding algorithm for interleaved codes, we obtained new list decoding algorithm for $qh$-folded Hermitian codes for $q$ standing for field size the code defined and $h$ is any positive integer. The decoding algorithm list decodes $qh$-folded Hermitian codes for radius that is generally better than radius of Guruswami-Sudan algorithm, with time complexity and list size polynomial in list size of $h$-folded Reed-Solomon codes defined over $F_{q^2}$.

Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

This Master´s thesis discuses the protection of data transmission against long error bursts. The data is transmited throught the channel with defined error rate. Parameters of the channel are error-free interval 2000 bits and length of burst error 250 bits. One of the aims of this work is to make a set of possible methods for the realization of a system for data correction. The basic selection is made from most known codes. These codes are divided into several categories and then the best one is chosen for higher selection. Of course interleaving is used too. Only one code from each category can pass on to the higher level of the best code selection. At the end the codes are compared and the best three are simulated using the Matlab program to check correct function. From these three options, one is chosen as optimal regarding practical realization. Two options exist, hardware or software realization. The second one would seem more useful. The real codec is created in validator language C. Nowadays, considering language C and from a computer architecture point of view the 8 bits size of element unit is convenient. That´s why the code RS(255, 191), which works with 8 bits symbols, is optimal. In the next step the codec of this code is created containing the coder and decoder of the code above. The simulation of error channel is ensured by last program. Finally the results are presented using several examples.

The main objective of this thesis was to create a model of forward error correction (FEC) system used in ADSL modem, which will be able to check its individual settings using the test methods specified in Recommendation G.996.1. The work is divided into two basic parts – theoretical and practical. The first part describes the basic functional characteristics of ADSL system, with attention being paid to aspects affecting the activity and setting of the error protection system. There are also discussed the theoretical basics of FEC coding techniques used in ADSL. The work also contains a description of the method for testing DSL system resistance against impulsive interference, which is specified in Recommendation G.996.1. The practical part of this thesis contains a description of the proposed model of the FEC system. The model was implemented in the programming environment Matlab Simulink. The proposed model includes the simulation of FEC coding process, DMT modulation and transmission channel with the impulse interference and the background noise. The proposed program is able to calculate parameters for setting FEC system from the specified data transfer rates and the requirement for interleaving. In addition, allows you to set the parameters of transmission line and sources of impulse interference and of the background noise. Under the set of input characteristics of the transmission is calculated bit allocation and the resulting parameters are given to a computational core of the model. In the application can be performed two types of test tasks. The first one is based on the Recommendation G.996.1 and makes it possible to determine probability of errored second. The second test task is for the measurement of resistance of the transmission system against impulsive interference. The results of the simulations are summarized in the conclusion of work.

This thesis deals with Matlab application developed for simulation of the DVB-T channel coder and decoder. The first part of this thesis includes description of terrestrial digital video broadcasting system and comparison with analogue television. Channel coding and OFDM modulation, used in the DVB-T standard, is described in detail. Application developed in the Matlab environment is described in the second part. The application simulates data transfer of the DVB-T system. Results of the simulated transmission, using developed application are presented in the last part. Namely dependence of the BER on the S/N ratio, using various coder settings, was examined. Maximal possible data rate was determined for these various setting. All obtained values are graphically represented.