Return to search

Ανίχνευση και διόρθωση σφαλμάτων σε συστήματα επικοινωνιών με κωδικοποίηση Reed-Solomon

Στην εργασία αυτή, μελετώνται διαφορετικοί αποκωδικοποιητές για κώδικες 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.

Identiferoai:union.ndltd.org:upatras.gr/oai:nemertes:10889/4889
Date09 January 2012
CreatorsΒασιλείου, Αλέξανδρος
ContributorsΠαλιουράς, Βασίλειος, Vasileiou, Alexandros, Παλιουράς, Βασίλειος
Source SetsUniversity of Patras
Languagegr
Detected LanguageGreek
TypeThesis
Rights0

Page generated in 0.0018 seconds