Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

A Thesis Submitted to the Faculty 0/ Engineering, University 0/ Lite Witwatersrand, Johannesburg in fulfilment 0/ the requirements /01' the Degree 0/ Doctor 0/ Philosophy. Johannesburg 1990. / This thesis studies fault tolerant strategies for real-time distributed computer control systems so as to propose an error recovery technique that renders individual processors on the network resistant to soft failures. The technique is effective for soft failures which have as certain maximum duration, and does not require the use of specialised hardware. Attention is focused on achieving resistance to soft failures in environments which have demanding time constraints such as those found in computer systems for process control, materials handling and automated manufacturing. [Abbreviated Abstract. Open document to view full version]

Masters Report A report submitted in ful llment of the requirements for the degree of Master of Science (50/50) in the Centre for Telecommunication Access and Services (CeTAS) School of Electrical and Information Engineering Faculty of Engineering and the Built Environment February 2017 / Bounded distance decoding of Reed Solomon (RS) codes involves nding a unique codeword if there is at least one codeword within the given distance. A corrupted message having errors that is less than or equal to half the minimum distance cor- responds to a unique codeword, and therefore will decode errors correctly using the minimum distance decoder. However, increasing the decoding radius to be slightly higher than half of the minimum distance may result in multiple codewords within the Hamming sphere. The list decoding and syndrome extension methods provide a maximum error correcting capability whereby the radius of the Hamming ball can be extended for low rate RS codes. In this research, we study the probability of having unique codewords for (7; k) RS codes when the decoding radius is increased from the error correcting capability t to t + 1. Simulation results show a signi cant e ect of the code rates on the probability of having unique codewords. It also shows that the probability of having unique codeword for low rate codes is close to one. / MT2017

Submitted in fulfilment of the academic requirements for the Master of Science in Engineering in Electrical and Information Engineering degree in the School of Electrical and Information Engineering at the University of Witwatersrand, Johannesburg, South Africa. August 2017 / There has been a surge in the demand of high speed reliable communication infrastructure in the last few decades. Advanced technology, namely the internet has transformed the way people live and how they interact with their environment. The Internet of Things (IoT) has been a very big phenomenon and continues to transform infrastructure in the home and work place. All these developments are underpinned by the availability of cost-effective, reliable and error free communication services. A perfect and reliable communication channel through which to transmit information does not exist. Telecommunication channels are often characterised by random noise and unpredictable disturbances that distort information or result in the loss of information. The need for reliable error-free communication has resulted in advanced research work in the field of Forward Error Correction (FEC). Low density parity check (LDPC) codes, discovered by Gallager in 1963 provide excellent error correction performance which is close to the vaunted Shannon limit when used with long block codes and decoded with the sum-product algorithm (SPA). However, long block code lengths increase the decoding complexity exponentially and this problem is exacerbated by the intrinsic complexity of the SPA and its approximate derivatives. This makes it impossible for the SPA to be implemented in any practical communication device. Bit flipping LDPC decoders, whose error correction performance pales in comparison to the SPA have been devised to counter the disadvantages of the SPA. Even though, the bit flipping algorithms do not perform as well as the SPA, their exceeding low complexity makes them attractive for practical implementation in high speed communication devices. Thus, a lot of research has gone into the design and development of improved bit flipping algorithms. This research work analyses and focusses on the design of improved multi-bit flipping algorithms which converge faster than single-bit flipping algorithms. The aim of the research is to devise methods with which to obtain thresholds that can be used to determine erroneous sections of a given codeword so that they can be corrected. Two algorithms that use multi-thresholds are developed during the course of this research. The first algorithm uses multiple adaptive thresholds while the second algorithm uses multiple near optimal SNR dependant fixed thresholds to identify erroneous bits in a codeword. Both algorithms use soft information modification to further improve the decoding performance. Simulations show that the use of multiple adaptive or near optimal SNR dependant fixed thresholds improves the bit error rate (BER) and frame error rate (FER) correcting performance and also decreases the average number of iterations (ANI) required for convergence. The proposed algorithms are also investigated in terms of quantisation for practical applications in communication devices. Simulations show that the bit length of the quantizer as well as the quantization strategy (uniform or non-uniform quantization) is very important as it affects the decoding performance of the algorithms significantly. / MT2018

A dissertation submitted in fulfilment of the requirements for the degree of Master of Science in the Centre for Telecommunication Access and Services, School of Electrical and Information Engineering, University of the Witwatersrand, Johannesburg, 2016 / Reed-Solomon codes are very popular codes used in the field of forward error correction due to their correcting capabilities. Thus, a lot of research has been done dedicated to the development of decoding algorithms for this class of code. [Abbreviated Abstract. Open document to view full version]

In this project we perform data transmission across noisy channels and recover the message first by using the Golay code, and then by using the first-order Reed- Muller code. The main objective of this thesis is to determine which code among the above two is more efficient for text message transmission by applying the two codes to exactly the same data with the same channel error bit probabilities. We use the comparison of the error-correcting capability and the practical speed of the Golay code and the first-order Reed-Muller code to meet our goal. / by Olga Shukina. / Thesis (M.S.)--Florida Atlantic University, 2013. / Includes bibliography. / Mode of access: World Wide Web. / System requirements: Adobe Reader.

Chei Kwok-hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 66-73). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Typical Digital Communication Systems --- p.2 / Chapter 1.1.1 --- Source coding --- p.3 / Chapter 1.1.2 --- Channel coding --- p.5 / Chapter 1.2 --- Joint Source-Channel Coding System --- p.5 / Chapter 1.3 --- Thesis Organization --- p.7 / Chapter Chapter 2 --- Trellis Coding --- p.9 / Chapter 2.1 --- Convolutional Codes --- p.9 / Chapter 2.2 --- Trellis-Coded Modulation --- p.12 / Chapter 2.2.1 --- Set Partitioning --- p.13 / Chapter 2.3 --- Trellis-Coded Quantization --- p.14 / Chapter 2.4 --- Joint TCQ/TCM System --- p.17 / Chapter 2.4.1 --- The Combined Receiver --- p.17 / Chapter 2.4.2 --- Viterbi Decoding --- p.19 / Chapter 2.4.3 --- Sequence MAP Decoding --- p.20 / Chapter 2.4.4 --- Sliding Window Decoding --- p.21 / Chapter 2.4.5 --- Block-Based Decoding --- p.23 / Chapter Chapter 3 --- Soft Decoding Joint TCQ/TCM over AWGN Channel --- p.25 / Chapter 3.1 --- System Model --- p.26 / Chapter 3.2 --- TCQ with Optimal Soft-Decoder --- p.27 / Chapter 3.3 --- Gaussian Memoryless Source --- p.30 / Chapter 3.3.1 --- Theorem Limit --- p.31 / Chapter 3.3.2 --- Performance on PAM Constellations --- p.32 / Chapter 3.3.3 --- Performance on PSK Constellations --- p.36 / Chapter 3.4 --- Uniform Memoryless Source --- p.38 / Chapter 3.4.1 --- Theorem Limit --- p.38 / Chapter 3.4.2 --- Performance on PAM Constellations --- p.39 / Chapter 3.4.3 --- Performance on PSK Constellations --- p.40 / Chapter Chapter 4 --- Soft Decoding Joint TCQ/TCM System over Rayleigh Fading Channel --- p.42 / Chapter 4.1 --- Wireless Channel --- p.43 / Chapter 4.2 --- Rayleigh Fading Channel --- p.44 / Chapter 4.3 --- Idea Interleaving --- p.45 / Chapter 4.4 --- Receiver Structure --- p.46 / Chapter 4.5 --- Numerical Results --- p.47 / Chapter 4.5.1 --- Performance on 4-PAM Constellations --- p.48 / Chapter 4.5.2 --- Performance on 8-PAM Constellations --- p.50 / Chapter 4.5.3 --- Performance on 16-PAM Constellations --- p.52 / Chapter Chapter 5 --- Joint TCVQ/TCM System --- p.54 / Chapter 5.1 --- Trellis-Coded Vector Quantization --- p.55 / Chapter 5.1.1 --- Set Partitioning in TCVQ --- p.56 / Chapter 5.2 --- Joint TCVQ/TCM --- p.59 / Chapter 5.2.1 --- Set Partitioning and Index Assignments --- p.60 / Chapter 5.2.2 --- Gaussian-Markov Sources --- p.61 / Chapter 5.3 --- Simulation Results and Discussion --- p.62 / Chapter Chapter 6 --- Conclusion and Future Work --- p.64 / Chapter 6.1 --- Conclusion --- p.64 / Chapter 6.2 --- Future Works --- p.65 / Bibliography --- p.66 / Appendix-Publications --- p.73

Kwong Cheuk Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 72-74). / Abstracts in English and Chinese. / Acknowledgements --- p.i / Abstract --- p.ii / Table of Contents --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Quantization --- p.2 / Chapter 1.2 --- Trellis-Coded Quantization --- p.3 / Chapter 1.3 --- Thesis Organization --- p.4 / Chapter 2 --- Trellis-Coded Modulation --- p.6 / Chapter 2.1 --- Convolutional Codes --- p.7 / Chapter 2.1.1 --- Generator Polynomials and Generator Matrix --- p.9 / Chapter 2.1.2 --- Circuit Diagram --- p.10 / Chapter 2.1.3 --- State Transition Diagram --- p.11 / Chapter 2.1.4 --- Trellis Diagram --- p.12 / Chapter 2.2 --- Trellis-Coded Modulation --- p.13 / Chapter 2.2.1 --- Uncoded Transmission verses TCM --- p.14 / Chapter 2.2.2 --- Trellis Representation --- p.17 / Chapter 2.2.3 --- Ungerboeck Codes --- p.18 / Chapter 2.2.4 --- Set Partitioning --- p.19 / Chapter 2.2.5 --- Decoding for TCM --- p.22 / Chapter 3 --- Trellis-Coded Quantization --- p.26 / Chapter 3.1 --- Scalar Trellis-Coded Quantization --- p.26 / Chapter 3.2 --- Trellis-Coded Vector Quantization --- p.31 / Chapter 3.2.1 --- Set Partitioning in TCVQ --- p.33 / Chapter 3.2.2 --- Codebook Optimization --- p.34 / Chapter 3.2.3 --- Numerical Data and Discussions --- p.35 / Chapter 4 --- Trellis-Coded Quantization with Unequal Distortion --- p.38 / Chapter 4.1 --- Design Procedures --- p.40 / Chapter 4.2 --- Fine and Coarse Codebooks --- p.41 / Chapter 4.3 --- Set Partitioning --- p.44 / Chapter 4.4 --- Codebook Optimization --- p.45 / Chapter 4.5 --- Decoding for Unequal Distortion TCVQ --- p.46 / Chapter 5 --- Unequal Distortion TCVQ on Memoryless Gaussian Source --- p.47 / Chapter 5.1 --- Memoryless Gaussian Source --- p.49 / Chapter 5.2 --- Set Partitioning of Codewords of Memoryless Gaussian Source --- p.49 / Chapter 5.3 --- Numerical Results and Discussions --- p.51 / Chapter 6 --- Unequal Distortion TCVQ on Markov Gaussian Source --- p.57 / Chapter 6.1 --- Markov Gaussian Source --- p.57 / Chapter 6.2 --- Set Partitioning of Codewords of Markov Gaussian Source --- p.58 / Chapter 6.3 --- Numerical Results and Discussions --- p.59 / Chapter 7 --- Conclusions --- p.70 / Bibliography --- p.72

Ho Man-Shing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 65-66). / Abstracts in English and Chinese. / Acknowledgement --- p.i / Abstract --- p.ii / List of Abbreviation --- p.iii / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Digital Communication System --- p.3 / Chapter 1.2 --- Thesis Organization --- p.4 / Chapter 2. --- Error-Correcting Codes --- p.6 / Chapter 2.1 --- Convolutional Codes --- p.7 / Chapter 2.1.1 --- Generator Polynomials --- p.8 / Chapter 2.1.2 --- Generator Matrix --- p.9 / Chapter 2.1.3 --- Circuit Diagram --- p.10 / Chapter 2.1.4 --- State-transition Diagram --- p.11 / Chapter 2.1.4 --- Trellis Diagram --- p.12 / Chapter 2.1.5 --- Distance property --- p.13 / Chapter 2.2 --- Rate-Compatible Punctured Convolutional Codes --- p.14 / Chapter 2.3 --- Trellis-Coded Modulation --- p.17 / Chapter 2.3.1 --- General Model of TCM --- p.18 / Chapter 2.3.2 --- Trellis Representation --- p.20 / Chapter 2.3.3 --- Set Partitioning --- p.21 / Chapter 2.3.4 --- Code Modulation --- p.23 / Chapter 2.4 --- Decoding Algorithm --- p.25 / Chapter 2.4.1 --- Viterbi Algorithm --- p.27 / Chapter 2.4.2 --- List Viterbi Algorithm --- p.30 / Chapter 3. --- Unequal-Error-Protection for Embedded Image Coder --- p.33 / Chapter 3.1 --- SPIHT Coder --- p.35 / Chapter 3.1.1 --- Progressive Image Transmission --- p.36 / Chapter 3.1.2 --- Set Partitioning Sorting Algorithm --- p.37 / Chapter 3.1.3 --- Spatial Orientation Trees --- p.38 / Chapter 3.2 --- System Description --- p.39 / Chapter 3.3 --- Code Allocation --- p.41 / Chapter 3.4 --- System Complexity --- p.42 / Chapter 3.5 --- Simulation Result --- p.43 / Chapter 4. --- Unequal-Error-Protection Provided by Trellis-Coded Modulation --- p.51 / Chapter 4.1 --- System Description --- p.52 / Chapter 4.2 --- Unequal Constellation --- p.53 / Chapter 4.3 --- Free Distance --- p.55 / Chapter 4.4 --- Simulation Results --- p.59 / Chapter 5. --- Conclusion --- p.63 / Bibliography --- p.65

Lin, Jian. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 44-49). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.