<p>We study the problem of list decoding with focus on the case when we have a list size limited to two. Under this restriction we derive general lower bounds on the maximum possible size of a list-of-2-decodable code. We study the set of correctable error patterns in an attempt to obtain a characterization. For a special family of Reed-Solomon codes - which we identify and name 'class-I codes' - we give a weight-based characterization of the correctable error patterns under list-of-2 decoding. As a tool in this analysis we use the theoretical framework of Sudan's algorithm. The characterization is used in an exact calculation of the probability of transmission error in the symmetric channel when list-of-2 decoding is used. The results from the analysis and complementary simulations for QAM-systems show that a list-of-2 decoding gain of nearly 1 dB can be achieved.</p><p>Further we study Sudan's algorithm for list decoding of Reed-Solomon codes for the special case of the class-I codes. For these codes algorithms are suggested for both the first and second step of Sudan's algorithm. Hardware solutions for both steps based on the derived algorithms are presented.</p>

We study the problem of list decoding with focus on the case when we have a list size limited to two. Under this restriction we derive general lower bounds on the maximum possible size of a list-of-2-decodable code. We study the set of correctable error patterns in an attempt to obtain a characterization. For a special family of Reed-Solomon codes - which we identify and name 'class-I codes' - we give a weight-based characterization of the correctable error patterns under list-of-2 decoding. As a tool in this analysis we use the theoretical framework of Sudan's algorithm. The characterization is used in an exact calculation of the probability of transmission error in the symmetric channel when list-of-2 decoding is used. The results from the analysis and complementary simulations for QAM-systems show that a list-of-2 decoding gain of nearly 1 dB can be achieved. Further we study Sudan's algorithm for list decoding of Reed-Solomon codes for the special case of the class-I codes. For these codes algorithms are suggested for both the first and second step of Sudan's algorithm. Hardware solutions for both steps based on the derived algorithms are presented.

In this dissertation, advanced channel decoding techniques based on bit-level soft information are studied. Two main approaches are proposed: bit-level probabilistic iterative decoding and bit-level algebraic soft-decision (list) decoding (ASD). In the first part of the dissertation, we first study iterative decoding for high density parity check (HDPC) codes. An iterative decoding algorithm, which uses the sum product algorithm (SPA) in conjunction with a binary parity check matrix adapted in each decoding iteration according to the bit-level reliabilities is proposed. In contrast to the common belief that iterative decoding is not suitable for HDPC codes, this bit-level reliability based adaptation procedure is critical to the conver-gence behavior of iterative decoding for HDPC codes and it significantly improves the iterative decoding performance of Reed-Solomon (RS) codes, whose parity check matrices are in general not sparse. We also present another iterative decoding scheme for cyclic codes by randomly shifting the bit-level reliability values in each iteration. The random shift based adaptation can also prevent iterative decoding from getting stuck with a significant complexity reduction compared with the reliability based parity check matrix adaptation and still provides reasonable good performance for short-length cyclic codes. In the second part of the dissertation, we investigate ASD for RS codes using bit-level soft information. In particular, we show that by carefully incorporating bit¬level soft information in the multiplicity assignment and the interpolation step, ASD can significantly outperform conventional hard decision decoding (HDD) for RS codes with a very small amount of complexity, even though the kernel of ASD is operating at the symbol-level. More importantly, the performance of the proposed bit-level ASD can be tightly upper bounded for practical high rate RS codes, which is in general not possible for other popular ASD schemes. Bit-level soft-decision decoding (SDD) serves as an efficient way to exploit the potential gain of many classical codes, and also facilitates the corresponding per-formance analysis. The proposed bit-level SDD schemes are potential and feasible alternatives to conventional symbol-level HDD schemes in many communication sys-tems.

Please download dissertation to view abstract.

One channel model that characterises multipath fading effect of a wireless channel is called Flat Rayleigh Fading channel model. Given the properties of Flat Rayleigh Fading channel, an equation to find the capacity of a Flat Rayleigh fading channel with hard decision decoding is derived. The difference of power requirement to achieve the Additive White Gaussian Noise (AWGN) capacity over a Flat Rayleigh Fading channel fading is found to increase exponentially with Es /N0 . Upper and lower bounds of error performance of linear block codes over a Flat Rayleigh Fading channel are also studied. With the condition that the excess delay of a channel is known earlier, it is shown that a correlator with shorter length, according to excess delay of the channel, can be constructed for use in wireless channel response measurements. Therefore, a rule of construction of a shorter length correlator is defined, involving concatenation of parts of a Constant Amplitude Zero Auto-Correlation (CAZAC) sequence. Simulation of [136,68,24] Double Circulant Code with Dorsch List Decoding is also done in order to evaluate error performance of the channel coding scheme over one of the IEEE Wireless Metropolitan Area Network (WirelessMAN) channel models, the Stanford University Interim Channel Model No. 5 (SUI-5) channel. Performance of the channel cod- ing was severely degraded over the SUI-5 channel when it is compared to its performance over the AWGN channel. Indoor path losses within three multifloor office buildings were investigated at 433 MHz, 869 MHz and 1249 MHz. The work involved series of extensive received signal strength measurements within the buildings for all of the considered frequencies. Results have shown that indoor path loss is higher within a square footprint building than indoor path loss in a rectangular building. Parameters of Log-Distance Path Loss and Floor Attenuation Factor Path Loss models have been derived from the measurement data. In addition, a new indoor path loss prediction model was derived to cater for path loss pre- diction within multifloor buildings with indoor atriums. The model performs with better prediction accuracy when compared with Log-Distance Path Loss and Floor Attenuation Factor Path Loss models.

Thesis (MSc (Mathematics))--University of Stellenbosch, 2006. / The main topic of this thesis is the construction of the algebraic geometric codes (Goppa codes), and their decoding by the list-decoding, which allows one to correct beyond half of the minimum distance. We also consider the list-decoding of the Reed–Solomon codes as they are subclass of the Goppa codes, and the determination of the parameters of the non primitive BCH codes. AMS Subject Classification: 4B05, 94B15, 94B35, 94B27, 11T71, 94B65,B70. Keywords: Linear codes, cyclic codes, BCH codes, Reed–Solomon codes, list-decoding, Algebraic Geometric codes, decoding, bound on codes, error probability.

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.

Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.