Spelling suggestions: "subject:"decoder"" "subject:"decode""
71 |
Robust high throughput space-time block coded MIMO systems : a thesis submitted in fulfilment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer Engineering from the University of Canterbury, Christchurch, New Zealand /Pau, Nicholas S. J. January 1900 (has links)
Thesis (Ph. D.)--University of Canterbury, 2007. / Typescript (photocopy). "June 2007." Includes bibliographical references (p. 159-166). Also available via the World Wide Web.
|
72 |
Επεξεργαστές VLSI για διόρθωση λαθών με συνελικτικούς κώδικεςΚαζίλης, Φάνης 21 March 2012 (has links)
Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη και ο σχεδιασμός VLSI επεξεργαστών για τη διόρθωση λαθών. Η κατηγορία των VLSI επεξεργαστών στην οποία εστιάζει η έρευνά μου είναι ο αποκωδικοποιητής Viterbi.
Αρχικά, παρουσιάζεται η δομή του ψηφιακού τηλεπικοινωνιακού συστήματος και κάποιες βασικές έννοιες των κωδικών διόρθωσης λαθών. Έπειτα, αναλύονται οι Συνελικτικοί κωδικοποιητές, ανάμεσα στους οποίους περιλαμβάνεται ο Συνελικτικός κωδικοποιητής που χρησιμοποιείται στην εργασία μου και ο οποίος χρησιμοποιείται ευρέως στο πρότυπο Wifi 802.11a. Ακολούθως, γίνεται αναφορά στο κανάλι AWGN και στη διαμόρφωση BPSK. Ακόμα, παρουσιάζονται οι βασικές έννοιες του αλγόριθμου Viterbi, η λειτουργία του, η δομή του καθώς και οι εφαρμογές του.
Στη συνέχεια, μελετώνται διάφορες αρχιτεκτονικές του αποκωδικοποιητή Viterbi σε VLSI. Με βάση τον τρόπο υλοποίησης αριθμητικών πράξεων, οι αρχιτεκτονικές που αναπτύσσονται είναι ο Radix-2 και ο Radix-4 Viterbi, ενώ με βάση τον τρόπο αποκωδικοποίησης αναπτύσσονται οι αρχιτεκτονικές του Viterbi για συνεχή αποκωδικοποίηση-εφαρμογές streaming και του Viterbi για αποκωδικοποίηση πακέτων των 20 bits. Επίσης, μελετάται η απόδοση των αρχιτεκτονικών αυτών με κριτήριο τη συχνότητα λαθών που πραγματοποιούνται (Bit Error Rate – BER) και αναλύεται η υλοποίηση των αρχιτεκτονικών αυτών στο αναπτυξιακό σύστημα Xilinx.
Τέλος, προκύπτουν τα κατάλληλα συμπεράσματα. / The purpose of this diploma thesis is to study and implement VLSI processors for correcting errors. The category of VLSI processor which will focus in this work is the Viterbi decoder.
Initially, the structure of the digital telecommunications system is presented along with some basic concepts of error correcting codes. Then we explain the theory behind convolutional encoders and we describe the convolutional encoder that is used in my work and is consistent in the Wifi 802.11a standard. Next we analyze briefly the AWGN channel and the BPSJ modulation. Also the basic concepts of the Viterbi algorithm, how it works, its structure and the different applications are given.
For the practical part which is the main part of this project, is to study the different architectures of the Viterbi decoder in VLSI approach. The main architectures that were developed for the implementation arithmetic operations is Radix-2 and Radix-4 Viterbi, but in terms of decoding two more architectures were developed, Viterbi continuous decoding-streaming applications and Viterbi decoding for packets of 20 bits. Then, the performance of these architectures in terms of frequency of errors made (BER) was investigated and also the implementation of these architectures in the development system Xilinx was analyzed.
At the end we give our conclusion regarding the results of the different simulations that we’ve done.
|
73 |
FPGA Implementation of Low Density Party Check Codes DecoderVijayakumar, Suresh 08 1900 (has links)
Reliable communication over the noisy channel has become one of the major concerns in the field of digital wireless communications. The low density parity check codes (LDPC) has gained lot of attention recently because of their excellent error-correcting capacity. It was first proposed by Robert G. Gallager in 1960. LDPC codes belong to the class of linear block codes. Near capacity performance is achievable on a large collection of data transmission and storage.In my thesis I have focused on hardware implementation of (3, 6) - regular LDPC codes. A fully parallel decoder will require too high complexity of hardware realization. Partly parallel decoder has the advantage of effective compromise between decoding throughput and high hardware complexity. The decoding of the codeword follows the belief propagation alias probability propagation algorithm in log domain. A 9216 bit, (3, 6) regular LDPC code with code rate ½ was implemented on FPGA targeting Xilinx Virtex 4 XC4VLX80 device with package FF1148. This decoder achieves a maximum throughput of 82 Mbps. The entire model was designed in VHDL in the Xilinx ISE 9.2 environment.
|
74 |
Design and implementation of decoders for error correction in high-speed communication systemsCatalà Pérez, Joan Marc 01 September 2017 (has links)
This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.
A new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor.
In order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices.
Finally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity. / Esta tesis se ha centrado en el diseño e implementación de decodificadores binarios basados en códigos de comprobación de paridad de baja densidad (LDPC) válidos para los sistemas de comunicación modernos de alta velocidad. Los conceptos básicos de códigos LDPC, sus prestaciones y cuellos de botella, en términos de complejidad y eficiencia hardware, fueron analizados para los principales algoritmos de decisión soft y decisión hard (como Min-Sum, Optimized 2-bit Min-Sum y Reliability-based iterative Majority-Logic). La complejidad y prestaciones de estos algoritmos se han mejorado para conseguir arquitecturas hardware eficientes.
Se ha propuesto un nuevo algoritmo de decodificación llamado One-Minimum Min-Sum. Éste reduce considerablemente la complejidad de las ecuaciones de actualización del nodo de comprobación del algoritmo Min-Sum. El segundo mínimo se ha estimado a partir del valor del primer mínimo por medio de una aproximación lineal, la cuál permite un ajuste dinámico. El algoritmo Optimized 2-bit Min-Sum se ha modificado para ser inicializado con los valores LLR e introducir la información extrínseca en los mensajes enviados desde los nodos variables. La ecuación del nodo variable de este algoritmo ha sido reformulada para reducir su complejidad. Ambos algoritmos fueron probados para el código (2048,1723) RS-based LDPC y para el código (16129,15372) LDPC utilizando un emulador hardware implementado en un dispositivo FPGA. Éstos han alcanzado unas prestaciones de BER muy cercanas a las del algoritmo Min-Sum evitando, además, la aparición temprana del fenómeno denominado suelo del error.
Con el objetivo de mostrar las ventajas hardware de los algoritmos propuestos, los decodificadores se implementaron en hardware utilizando tecnología CMOS de 90 nm y en dispositivos FPGA basados en dos tipos de arquitecturas: completamente paralela y parcialmente paralela utilizando el método de actualización por capas horizontales. Los resultados muestran que los decodificadores propuestos e implementados son más eficientes en área-tiempo que otros decodificadores publicados y que la baja complejidad del algoritmo Modified Optimized 2-bit Min-Sum permite la implementación de decodificadores en los dispositivos FPGA actuales consiguiendo una tasa de 10 Gbps.
Finalmente, se ha presentado un nuevo algoritmo de decodificación de decisión hard, el Historical-Extrinsic Reliability-Based Iterative Decoder. Este algoritmo introduce la nueva idea de considerar los votos de decisión hard como decisión soft para calcular la información extrínseca de iteracions anteriores. Este algoritmo es adecuado para códigos de alta velocidad y mejora el rendimiento BER de los algoritmos RBI-MLGD anteriores, con una complejidad similar. / Aquesta tesi s'ha centrat en el disseny i implementació de descodificadors binaris basats en codis de comprovació de paritat de baixa densitat (LDPC) vàlids per als sistemes de comunicació moderns d'alta velocitat. Els conceptes bàsics de codis LDPC, les seues prestacions i colls de botella, en termes de complexitat i eficiència hardware, van ser analitzats pels principals algoritmes de decisió soft i decisió hard (com el Min-Sum, Optimized 2-bit Min-Sum y Reliability-based iterative Majority-Logic). La complexitat i prestacions d'aquests algoritmes s'han millorat per aconseguir arquitectures hardware eficients.
S'ha proposat un nou algoritme de descodificació anomenat One-Minimum Min-Sum. Aquest redueix considerablement la complexitat de les equacions d'actualització del node de comprovació del algoritme Min-Sum. El segon mínim s'ha estimat a partir del valor del primer mínim per mitjà d'una aproximació lineal, la qual permet un ajust dinàmic. L'algoritme Optimized 2-bit Min-Sum s'ha modificat per ser inicialitzat amb els valors LLR i introduir la informació extrínseca en els missatges enviats des dels nodes variables. L'equació del node variable d'aquest algoritme ha sigut reformulada per reduir la seva complexitat. Tots dos algoritmes van ser provats per al codi (2048,1723) RS-based LDPC i per al codi (16129,15372) LDPC utilitzant un emulador hardware implementat en un dispositiu FPGA. Aquests han aconseguit unes prestacions BER molt properes a les del algoritme Min-Sum evitant, a més, l'aparició primerenca del fenomen denominat sòl de l'error.
Per tal de mostrar els avantatges hardware dels algoritmes proposats, els descodificadors es varen implementar en hardware utilitzan una tecnologia CMOS d'uns 90 nm i en dispositius FPGA basats en dos tipus d'arquitectures: completament paral·lela i parcialment paral·lela utilitzant el mètode d'actualització per capes horitzontals. Els resultats mostren que els descodificadors proposats i implementats són més eficients en àrea-temps que altres descodificadors publicats i que la baixa complexitat del algoritme Modified Optimized 2-bit Min-Sum permet la implementació de decodificadors en els dispositius FPGA actuals obtenint una taxa de 10 Gbps.
Finalment, s'ha presentat un nou algoritme de descodificació de decisió hard, el Historical-Extrinsic Reliability-Based Iterative Decoder. Aquest algoritme presenta la nova idea de considerar els vots de decisió hard com decisió soft per calcular la informació extrínseca d'iteracions anteriors. Aquest algoritme és adequat per als codis d'alta taxa i millora el rendiment BER dels algoritmes RBI-MLGD anteriors, amb una complexitat similar. / Català Pérez, JM. (2017). Design and implementation of decoders for error correction in high-speed communication systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/86152 / TESIS
|
75 |
Soft-decision decoding of permutation codes in AWGN and fading channelsKolade, Oluwafemi Ibrahim January 2017 (has links)
A Dissertation submitted in ful llment of the requirements for the degree of Master
of Science in the
School of Electrical and Information Engineering
January, 2017 / Permutation codes provide the required redundancy for error correction in a noisy
communication channel. Combined with MFSK modulation, the outcome produces
an e cient system reliable in combating background and impulse noise in the com-
munication channel. Part of this can be associated with how the redundancy scales
up the amount of frequencies used in transmission.
Permutation coding has also shown to be a good candidate for error correction in
harsh channels such as the Powerline Communication channel. Extensive work has
been done to construct permutation code books but existing decoding algorithms
become impractical for large codebook sizes. This is because the algorithms need
to compare the received codeword with all the codewords in the codebook used in
encoding.
This research therefore designs an e cient soft-decision decoder of Permutation
codes. The decoder's decision mechanism does not require lookup comparison with
all the codewords in the codebook. The code construction technique that derives the
codebook is also irrelevant to the decoder.
Results compare the decoding algorithm with Hard-decision plus Envelope Detec-
tion in the Additive White Gaussian Noise (AWGN) and Rayleigh Fading Channels.
The results show that with lesser iterations, improved error correction performance
is achieved for high-rate codes. Lower rate codes require additional iterations for
signi cant error correction performance. The decoder also requires much less comup-
tational complexity compared with existing decoding algorithms. / MT2017
|
76 |
Décodeurs Haute Performance et Faible Complexité pour les codes LDPC Binaires et Non-Binaires / High Performance and Low Complexity Decoders for Binary and Non-Binary LDPC CodesLi, Erbao 19 December 2012 (has links)
Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteurd'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliserdes décodeurs de complexité faibles et de faible latence tout en garantissantde bonne performances dans la région des très faibles taux d'erreur (error floor).Dans la première partie de cette thèse, nous étudions des décodeurs itératifssur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont étérécemment proposés dans la littérature. En utilisant un grand nombre de décodeursFAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité decorrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique.La diversité des décodeurs permet de garantir une correction d'erreur minimale sousdécodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnonsdans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrigetous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petitetaille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènementsd'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger.Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques etnous analysons les comportements de ces décodeurs sur des évènements d'erreur lesplus problématiques. En nous basant sur l'observation des trajectoires périodiquespour ces cas d'étude, nous proposons un algorithme qui combine la diversité dudécodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nousmontrons par simulations que cette technique permet de s'approcher des performancesd'un décodage optimal au sens du maximum de vraisemblance, et ce pourplusieurs codes.Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithmede décodage à complexité réduite pour les codes LDPC non-binaires. Nous avonsappellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domainede message en un domaine appelée domaine delta, nous sommes capable dechoisir les déviations ligne par ligne par rapport à la configuration la plus fiable,tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviationscolonne par colonne. Cette technique de sélection des déviations ligne parligne nous permet de réduire la complexité du décodage sans perte de performancepar rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoudle problème de latence des décodeurs existants. La colonne supplémentaire permetde calculer tous les messages extrinséque en parallèle, avec une implémentationmatérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architecturesmatérielles parallèle que les architectures matérielles série pour l'exécution de notrealgorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS estparticulièrement adapté pour les codes LDPC non-binaires sur des corps finis deGalois de petite et moyenne dimensions. / This thesis is dedicated to the study of iterative decoders, both for binary and non-binary low density parity check (LDPC) codes. The objective is to design low complexity and low latency decoders which have good performance in the error floor region.In the first part of the thesis, we study the recently introduced finite alphabet iterative decoders (FAIDs). Using the large number of FAIDs, we propose a decoding diversity algorithm to improve the error correction capability for binary LDPC codes with variable node degree 3 over binary symmetric channel. The decoder diversity framework allows to solve the problem of guaranteed error correction with iterative decoding, beyond the pseudo-distance of the LDPC codes. We give a detailed example of a set of FAIDs which corrects all error patterns of weight 7 or less on a (N=155,K=64,Dmin=20) short structured LDPC, while traditional decoders (BP, min-sum) fail on 5-error patterns. Then by viewing the FAIDs as dynamic systems, we analyze the behaviors of FAID decoders on chosen problematic error patterns. Based on the observation of approximate periodic trajectories for the most harmful error patterns, we propose an algorithm which combines decoding diversity with random jumps in the state-space of the iterative decoder. We show by simulations that this technique can approach the performance of Maximum LikelihoodDecoding for several codes.In the second part of the thesis, we propose a new complexity-reduced decoding algorithm for non-binary LDPC codes called trellis extended min sum (T-EMS). By transforming the message domain to the so-called delta domain, we are able to choose row-wise deviations from the most reliable configuration, while usual EMS-like decoders choose the deviations column-wise. This feature of selecting the deviations row-wise enables us to reduce the decoding complexity without any performance loss compared to EMS. We also propose to add an extra column to the trellis representation of the messages, which solves the latency issue of existing decoders. The extra column allows to compute all extrinsic messages in parallel, with a proper hardware implementation. Both the parallel and the serial hardware architectures for T-EMS are discussed. The complexity analysis shows that the T-EMS is especially suitable for high ratenon-binary LDPC codes on small and moderate fields.
|
77 |
Parallel VLSI Architectures for Multi-Gbps MIMO Communication SystemsJanuary 2011 (has links)
In wireless communications, the use of multiple antennas at both the transmitter and the receiver is a key technology to enable high data rate transmission without additional bandwidth or transmit power. Multiple-input multiple-output (MIMO) schemes are widely used in many wireless standards, allowing higher throughput using spatial multiplexing techniques. MIMO soft detection poses significant challenges to the MIMO receiver design as the detection complexity increases exponentially with the number of antennas. As the next generation wireless system is pushing for multi-Gbps data rate, there is a great need for high-throughput low-complexity soft-output MIMO detector. The brute-force implementation of the optimal MIMO detection algorithm would consume enormous power and is not feasible for the current technology. We propose a reduced-complexity soft-output MIMO detector architecture based on a trellis-search method. We convert the MIMO detection problem into a shortest path problem. We introduce a path reduction and a path extension algorithm to reduce the search complexity while still maintaining sufficient soft information values for the detection. We avoid the missing counter-hypothesis problem by keeping multiple paths during the trellis search process. The proposed trellis-search algorithm is a data-parallel algorithm and is very suitable for high speed VLSI implementation. Compared with the conventional tree-search based detectors, the proposed trellis-based detector has a significant improvement in terms of detection throughput and area efficiency. The proposed MIMO detector has great potential to be applied for the next generation Gbps wireless systems by achieving very high throughput and good error performance. The soft information generated by the MIMO detector will be processed by a channel decoder, e.g. a low-density parity-check (LDPC) decoder or a Turbo decoder, to recover the original information bits. Channel decoder is another very computational-intensive block in a MIMO receiver SoC (system-on-chip). We will present high-performance LDPC decoder architectures and Turbo decoder architectures to achieve 1+ Gbps data rate. Further, a configurable decoder architecture that can be dynamically reconfigured to support both LDPC codes and Turbo codes is developed to support multiple 3G/4G wireless standards. We will present ASIC and FPGA implementation results of various MIMO detectors, LDPC decoders, and Turbo decoders. We will discuss in details the computational complexity and the throughput performance of these detectors and decoders.
|
78 |
Algorithmes itératifs à faible complexité pour le codage de canal et le compressed sensingDanjean, Ludovic 29 November 2012 (has links) (PDF)
L'utilisation d'algorithmes itératifs est aujourd'hui largement répandue dans tous les domaines du traitement du signal et des communications numériques. Dans les systèmes de communications modernes, les algorithmes itératifs sont utilisés dans le décodage des codes "low-density parity-check" (LDPC), qui sont une classe de codes correcteurs d'erreurs utilisés pour leurs performances exceptionnelles en terme de taux d'erreur. Dans un domaine plus récent qu'est le "compressed sensing", les algorithmes itératifs sont utilisés comme méthode de reconstruction afin de recouvrer un signal ''sparse" à partir d'un ensemble d'équations linéaires, appelées observations. Cette thèse traite principalement du développement d'algorithmes itératifs à faible complexité pour les deux domaines mentionnés précédemment, à savoir le design d'algorithmes de décodage à faible complexité pour les codes LDPC, et le développement et l'analyse d'un algorithme de reconstruction à faible complexité, appelé ''Interval-Passing Algorithm (IPA)'', dans le cadre du "compressed sensing". Dans la première partie de cette thèse, nous traitons le cas des algorithmes de décodage des codes LDPC. Il est maintenu bien connu que les codes LDPC présentent un phénomène dit de ''plancher d'erreur" en raison des échecs de décodage des algorithmes de décodage traditionnels du types propagation de croyances, et ce en dépit de leurs excellentes performances de décodage. Récemment, une nouvelle classe de décodeurs à faible complexité, appelés ''finite alphabet iterative decoders (FAIDs)'' ayant de meilleures performances dans la zone de plancher d'erreur, a été proposée. Dans ce manuscrit nous nous concentrons sur le problème de la sélection de bons décodeurs FAID pour le cas de codes LDPC ayant un poids colonne de 3 et le cas du canal binaire symétrique. Les méthodes traditionnelles pour la sélection des décodeurs s'appuient sur des techniques asymptotiques telles que l'évolution de densité, mais qui ne garantit en rien de bonnes performances sur un code de longueurs finies surtout dans la région de plancher d'erreur. C'est pourquoi nous proposons ici une méthode de sélection qui se base sur la connaissance des topologies néfastes au décodage pouvant être présente dans un code en utilisant le concept de "trapping sets bruités''. Des résultats de simulation sur différents codes montrent que les décodeurs FAID sélectionnés grâce à cette méthode présentent de meilleures performance dans la zone de plancher d'erreur comparé au décodeur à propagation de croyances. Dans un second temps, nous traitons le sujet des algorithmes de reconstruction itératifs pour le compressed sensing. Des algorithmes itératifs ont été proposés pour ce domaine afin de réduire la complexité induite de la reconstruction par "linear programming''. Dans cette thèse nous avons modifié et analysé un algorithme de reconstruction à faible complexité dénommé IPA utilisant les matrices creuses comme matrices de mesures. Parallèlement aux travaux réalisés dans la littérature dans la théorie du codage, nous analysons les échecs de reconstruction de l'IPA et établissons le lien entre les "stopping sets'' de la représentation binaire des matrices de mesure creuses. Les performances de l'IPA en font un bon compromis entre la complexité de la reconstruction sous contrainte de minimisation de la norme $ell_1$ et le très simple algorithme dit de vérification.
|
79 |
Turbo codes a VLSI implementation /Israr, Moeed, January 1900 (has links)
Thesis (M.App.Sc.) - Carleton University, 2007. / Includes bibliographical references (p. 101-107). Also available in electronic format on the Internet.
|
80 |
Ανίχνευση και διόρθωση σφαλμάτων σε συστήματα επικοινωνιών με κωδικοποίηση Reed-SolomonΒασιλείου, Αλέξανδρος 09 January 2012 (has links)
Στην εργασία αυτή, μελετώνται διαφορετικοί αποκωδικοποιητές για κώδικες Reed-Solomon. Αφού γίνει μια εισαγωγή στο σύστημα επικοινωνίας, στα πεπερασμένα σώματα και στη θεωρία κωδίκων, παρουσιάζονται αλγόριθμοι που υλοποιούν αποκωδικοποιητές περιορισμένης απόστασης, λίστας και soft decoders. Συγκεκριμένα, μελετώνται κλασσικοί αποκωδικοποιητές, αποκωδικοποιητές βασισμένοι
στον αλγόριθμο Guruswami-Sudan, και αποκωδικοποιητές βασισμένοι στον αλγόριθμο Koetter-Vardy. Η σύγκριση γίνεται ως προς τη διορθωτική ικανότητα και τη χρονική πολυπλοκότητα.
Στα πλαίσια της εργασίας αυτής, σε συνέχεια της μελέτης υπαρχόντων αποκωδικοποιητών προτείνεται ένα είδος προσαρμοστικού
αποκωδικοποιητή: φέρει την ίδια διορθωτική ικανότητα με έναν αποκωδικοποιητή λίστας, αλλά σε ορισμένες περιπτώσεις έχει
ικανοποιητικά μικρότερη χρονική πολυπλοκότητα. Επίσης γίνεται μία ποιοτική διερεύνηση για το πότε πρέπει να προτιμάται ο προσαρμοστικός αποκωδικοποιητής.
Προτείνονται δύο διαφορετικοί προσαρμοστικοί αποκωδικοποιητές. Η πρώτη εκδοχή, είναι μία διάταξη με δύο αποκωδικοποιητές. Αρχικά
το ληφθέν διάνυσμα από το κανάλι, εισέρχεται ως είσοδος σε έναν κλασσικό αποκωδικοποιητή. Αν ο κλασσικός παρουσιάσει αδυναμία
αποκωδικοποίησης, τότε επιχειρεί να διορθώσει το ίδιο διάνυσμα ένας
αποκωδικοποιητής λίστας. Η δέυτερη εκδοχή, μοιάζει με την πρώτη, με τη διαφορά ότι ο δεύτερος αποκωδικοποιητής χρησιμοποιεί αποτελέσματα που έχουν ήδη υπολογιστεί από τον πρώτο, μειώνοντας έτσι την συνολική
χρονική πολυπλοκότητα, σχετικά με την πρώτη εκδοχή. / In this thesis we study a family of linear block codes, the Reed-Solomon(RS) codes. RS codes are q-ary codes over some finite field GF(q). Therefore, they have strong burst-error correction capability, because they deal with groups of bits instead of single bits.
Initially, we describe the employed communication system model, and introduce basic from finite field theory (construction and identities) and coding theory. After describing the RS encoding process, we describe different RS decoders (bounded distance decoder, list decoder and soft-input
decoder). Specifically, in addition to traditional approaches, we focus on decoders based on Guruswami-Sudan and Koetter – Vardy
algorithms. We compare them according to their complexity and performance, both in theory and experimentally.
Furthermore, in this thesis, we propose an adaptive decoder, which has the same performance as a list decoder but in some cases it achieves much lower average time complexity. We present the experimental
results, highlighting the cases where the adaptive decoder outperforms conventional decoders.
The adaptive decoder comes in two different types. The first type is a system with two different decoders: the low complexity decoder attempts to decode a received vector and in case of decoding failure the
subsequent decoder tries to decode the same received vector. The second type resembles the general organization of the above system; the second decoder re-uses intermediate results, previously computed by the first one.
|
Page generated in 0.0498 seconds