Advertisement
makispaiktis

Report - Error Correcting Codes (Repetition and Hamming)

Jan 25th, 2022
1,881
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass[journal]{IEEEtran}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage{geometry}
  4. \geometry{
  5.     a4paper, left=2.75cm, top=3cm
  6. }
  7. \usepackage[english,greek]{babel}
  8. \usepackage{amsmath,amsfonts,amssymb}
  9. \usepackage{graphicx}
  10. \usepackage{float}
  11. \graphicspath{{../PICS/}}
  12. \usepackage{alphabeta}
  13. \usepackage{array}
  14. \usepackage{multirow}
  15. \usepackage{floatrow}
  16. \usepackage{subcaption}
  17.  
  18.  
  19. \def\tl{\textlatin}
  20. \def\tg{\textgreek}
  21. \usepackage{comment}
  22. \usepackage{hyperref}
  23. \usepackage{ragged2e}
  24. \usepackage{multirow}
  25. \usepackage{mathtools}
  26.  
  27. \newcommand{\ENG}{\selectlanguage{english}}
  28. \newcolumntype{\GR}{\selectlanguage{greek}}
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36. \ifCLASSINFOpdf
  37.   % \usepackage[pdftex]{graphicx}
  38.   % declare the path(s) where your graphic files are
  39.   % \graphicspath{{../pdf/}{../jpeg/}}
  40.   % and their extensions so you won't have to specify these with
  41.   % every instance of \includegraphics
  42.   % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
  43. \else
  44.   % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  45.   % will default to the driver specified in the system graphics.cfg if no
  46.   % driver is specified.
  47.   % \usepackage[dvips]{graphicx}
  48.   % declare the path(s) where your graphic files are
  49.   % \graphicspath{{../eps/}}
  50.   % and their extensions so you won't have to specify these with
  51.   % every instance of \includegraphics
  52.   % \DeclareGraphicsExtensions{.eps}
  53. \fi
  54. % graphicx was written by David Carlisle and Sebastian Rahtz. It is
  55. % required if you want graphics, photos, etc. graphicx.sty is already
  56. % installed on most LaTeX systems. The latest version and documentation
  57. % can be obtained at:
  58. % http://www.ctan.org/pkg/graphicx
  59. % Another good source of documentation is "Using Imported Graphics in
  60. % LaTeX2e" by Keith Reckdahl which can be found at:
  61. % http://www.ctan.org/pkg/epslatex
  62. %
  63. % latex, and pdflatex in dvi mode, support graphics in encapsulated
  64. % postscript (.eps) format. pdflatex in pdf mode supports graphics
  65. % in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
  66. % that all non-photo figures use a vector format (.eps, .pdf, .mps) and
  67. % not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
  68. % which can result in "jaggedy"/blurry rendering of lines and letters as
  69. % well as large increases in file sizes.
  70. %
  71. % You can find documentation about the pdfTeX application at:
  72. % http://www.tug.org/applications/pdftex
  73. \hyphenation{op-tical net-works semi-conduc-tor}
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83. \begin{document}
  84.  
  85.  
  86. \title{\ENG Error Correcting Codes: Error rates and transmission rates}
  87. % Κώδικες Διόρθωσης Σφαλμάτων: Ρυθμοί μετάδοσης και πιθανότητα σφάλματος
  88.  
  89. \author{Θωμάς Μπουφίκος,
  90.         Δημήτριος Σκλαβενίτης,
  91.         και Ράλλης Τσολακίδης
  92.        
  93. \thanks{Λεωνίδας Γεωργιάδης, Καθηγητής Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Αριστοτέλειο
  94. Πανεπιστήμιο Θεσσαλονίκης, 2022, T.K. 54636: (\ENG leonid@ece.auth.gr)}}
  95.  
  96. \markboth{\ENG Journal of IEEE - AUTH Branch}
  97. {Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for IEEE Journals}
  98.  
  99. \maketitle
  100.  
  101. \begin{abstract}
  102. Η παρούσα εργασία εστιάζει στην υλοποίηση αλγορίθμων αποκωδικοποίησης γραμμικών κωδίκων για \ENG bit-decoding και σε επόμενο στάδιο πραγματεύεται την επιλογή παραμέτρων \ENG LDPC κωδίκων και την μελέτη της αποδοτικότητας του καθενός.
  103. \end{abstract}
  104.  
  105. \begin{IEEEkeywords}
  106. Κώδικας, αποκωδικοποίηση, βελτιστοποίηση, ρυθμός μετάδοσης, \ENG parity check matrix
  107. % IEEE, IEEEtran, journal, \LaTeX, paper, template.
  108. \end{IEEEkeywords}
  109.  
  110. \IEEEpeerreviewmaketitle
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118. \section{Εισαγωγή}
  119.  
  120. \IEEEPARstart{Σ}{την} εργασία αυτή, θα μελετήσουμε μία σειρά τρόπων κωδικοποίησης μηνυμάτων και διόρθωσής τους αφότου διέλθουν από μη ιδανικό κανάλι. Τα μηνύματα αυτά μετασχηματίζονται μέσω αλγορίθμων σε μεγαλύτερα μηνύματα, τις κωδικολέξεις, των οποίων το μήκος είναι προφανώς μεγαλύτερο του επιθυμητού μηνύματος. Αυτή η διαδικασία ακολουθείται, ώστε κατά την λήψη τους από τον δέκτη και την εφαρμογή των κατάλληλων διαδικασιών να μπορέσουμε να αποφανθούμε για την ταυτότητα της αρχικής κωδικολέξης και άρα και του αρχικού μηνύματος που διαβιβάσαμε μέσα από το κανάλι. Δηλαδή, οι αλγόριθμοι κατασκεύης της κωδικολέξης, αλλά και ανίχνευσής της από τον δέκτη είναι το αντικείμενο της εργασίας αυτής. Όλα αυτά είναι απαραίτητα στις σύγχρονες τηλεπικοινωνίες, μιας και όταν μία κωδικολέξη στέλνεται μέσα από ένα κανάλι (μη ιδανικός δίαυλος) υφίσταται μεταβολές στα \ENG bits της και συνεπως, θα πρέπει να εφεύρουμε ρουτίνες και αλγορίθμους με συγκεκριμένα βήματα, για να ανακτήσουμε το αρχικό μήνυμα μέσα από την "παραμορφωμένη" κωδικολέξη που λάβαμε. Παρακάτω, θα εξεταστούν 3 κώδικες διόρθωσης σφαλμάτων: α) ο repetition code, β) ο κώδικας Hamming με την βοήθεια των factor graphs και τέλος, γ) οι LDPC κώδικες. Θα παρατεθούν αποτελέσματα της προσομοίωσης διαύλων BSC (Binary Symmetric Channel) και BEC (Binary Erasure Channel) σε συνδυασμό με τους παραπάνω κώδικες διόρθωσης και θα μελετήσουμε το ρυθμό μετάδοσης (πόσο κοντά είναι στην χωρητικότητα του διαύλου βάσει της Θεωρίας Πληροφορίας), καθώς και την πιθανότητα σφάλματος.
  121.  
  122. \hfill Ιανουάριος, 2022
  123. \vspace{2mm}
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131. \section{Repetition Code}
  132.  
  133.  
  134. \subsection{\textit{Αποστολή κωδικολέξης από αρχικό μήνυμα}}
  135. Ο repetition code είναι ίσως ο πιο απλός κώδικας διόρθωσης σφαλμάτων που υπάρχει. Σήμερα, δεν χρησιμοποείται στην πλειοψηφία των εφαρμογών, διότι ρίχνει αρκετά τον ρυθμό μετάδοσης από τη μέγιστη τιμή που μπορεί να πάρει και η οποία είναι 1. Πιο συγκεκριμένα, ο κώδικας αυτός, παίρνει τα bits του μηνύματος που επιθυμούμε να στείλουμε και για καθένα από αυτά, αντιγράφει R φορές την ίδια τιμή του εκάστοτε bit μηνύματος (0 ή 1). Αυτό σημαίνει πως όλο το μήνυμα πλέον έχει μετασχηματιστεί σε μία μεγαλύτερη κωδικολέξη, με μήκος R φορές μεγαλύτερο. Αν επιθυμούμε, δηλαδή για παράδειγμα, να αποστείλουμε μέσω ενός καναλιού BSC ένα μήνυμα μήκους L, τότε αφού κάθε Bit του επαναλμάνεται R φορές στην κωδικολέξη, το τελικό μήνυμα-κωδικολέξη θα έχει μήκος \ENG $L' = R \cdot L$ \GR, ρίχνοντας έτσι τον ρυθμό μετάδοσης όπως είπαμε και παραπάνω. Βέβαια, το πολύ θετικό του κώδικα αυτού είναι ότι όσο αυξάνεται το R, τόσο αυξάνεται και η πιθανότητα διόρθωσης ενός μηνύματος για δεδομένη πιθανότητα σφάλματος er του καναλιού BSC. Με άλλα λόγια, υπάρχει ένα trade-off ανάμεσα σε ρυθμό μετάδοσης και πιθανότητα σφάλματος.
  136. \vspace{4mm}
  137.  
  138.  
  139.  
  140. \subsection{\textit{Αποκωδικοποίηση κωδικολέξης και ανίχνευση του αρχικού μηνύματος}}
  141. Όταν στον δέκτη μας φτάσει η παραλλαγμένη κωδικολέξη λόγω της αλλοιωτικής επίδρασης του καναλιού, θα πρέπει να βρούμε έναν τρόπο να μπορούμε να συμπεράνουμε ποια κωδικολέξη έχει σταλεί και επομένως, να βρούμε και το αρχικό μήνυμα. Η διαδικασία που ακολουθούμε είναι η εξής: αρχικά, σπάμε την ληφθείσα κωδικολέξη ανά R bits (το R είναι γνωστό σε πομπό και δέκτη) και μετράμε πόσα bit είναι 0 και πόσα 1 (συνήθως επιλέγουμε R να είναι περιττό). Αν στα R bits, το bit που εμφανίζεται πιο συχνά είναι το 0 συμπεραίνουμε πως στο αρχικό μήνυμα αντί για αυτά τα R bits υπήρχε το 0, αλλιώς συμπεραίνουμε το 1.
  142. \vspace{4mm}
  143.  
  144.  
  145.  
  146. \subsection{Πλεονεκτήματα και μειονεκτήματα}
  147. Από την στιγμή που μετασχηματίζουμε ένα μήνυμα μεγέθους \ENG $L$ \GR, σε μία κωδικολέξη μήκους \ENG $L \cdot R$ \GR, τότε για 1 χρήσιμο bit στέλνουμε R κωδικοποιημένα bit, οπότε για τον κανονικοποιημένο ρυθμό μετάδοσης θα ισχύει: \ENG $r = \frac{bits}{coded \, bits} = \frac{L}{L \cdot R} = \frac{1}{R}$ \GR. Δηλαδή είναι αντιστρόφως ανάλογος της παραμέτρου R. Το ίδιο ισχύει για την πιθανότητα σφάλματος στο εκτιμώμενο μήνυμα για δεδομένο error rate (er). Όσο αυξάνεται το R, η πιθανότητα λαθεμένης εκτίμησης πέφτει με τον ίδιο ρυθμό \ENG $\frac{1}{R}$ \GR, γεγονός που μας συμφέρει πολύ. Δηλαδή, ενώ τα λάθη στην κωδικολέξη αυξάνονται πάντα γραμμικά με το μήκος L και με το R, η πιθανότητα λάθους στο αρχικό μήνυμα μειώνεται αισθητά. Ο λόγος που τα αρχικά λάθη στην κωδικολέξη είναι γραμμικά στηρίζεται στις αρχές της Στατιστικής. Για μήνυμα μεγέθους L, έχουμε κωδικολέξη με \ENG $L \cdot R$ bits \GR, όπου καθένα από αυτά τα bit λαμβάνονται λάθος με μία πιθανότητα er. Σύμφωνα, λοιπόν με τους κανόνες των μεγάλων αριθμών, ο ρυθμός επαναφοράς είναι \ENG $\frac{1}{er}$ \GR, δηλαδή ανά τόσα bit αναμένουμε 1 λαθεμένο bit. Άρα, αν στέλνουμε \ENG $L \cdot R$ \GR bits, αναμένουμε \ENG $er \cdot L \cdot R$ \GR λαθεμένα bit κωδικολέξης (γραμμική εξάρτηση των σφαλμάτων κωδικολέξης με τα er, L, R εν αντιθέσει με τα σφάλματα μηνύματος). Όλες αυτές οι παρατηρήσεις θα καταστούν φανερές και στην επόμενη ενότητα, όπου θα παρατεθούν γραφικές παραστάσεις από πολλαπλές προσομοιώσεις καναλιού.
  148. \GR
  149.  
  150.  
  151.  
  152.  
  153. \subsection{Προσομοιώσεις}
  154.  
  155. \subsubsection{Προσομοίωση 1η}
  156.  
  157. \begin{justify}
  158. Στην προσομοίωση αυτή θεωρήσαμε ένα αρχικό τυχαίο bitstream μήκους 30, δηλαδή \ENG $L = 30$  \GR και επαναληπτική παράμετρο \ENG $R = 3$ \GR, οπότε το τελικό μήκος της κωδικολέξης είναι, όπως είπαμε και πάνω, \ENG $L' = L \cdot R = 90$ \GR. Θεωρήσαμε επίσης και σαν πιθανότητα σφάλματος του BSC διαύλου \ENG $er = 0.1$ \GR. Έτσι, αν επαναλάβουμε πολλές φορές την προσομοίωση ενός τέτοιου καναλιού, ο αναμενόμενος αριθμός σφαλμάτων στην κωδικολέξη είναι 9 (\ENG $[E_{cod}]= er \cdot L \cdot R$ \GR). Αυτό θα φανεί και στο διάγραμμα. Βέβαια, με μία τέτοια διαδικασία προσομοίωσης και με ένα τέτοιο σχετικά μικρό σφάλμα διαύλου, τα τελικά λάθη του αρχικού μηνύματος (με μήκος 30), θα είναι αρκετά πιο χαμηλά από τα αντίστοιχα της κωδικολέξης. Αυτό ισχύει και για κάθε 1/100 simulation ξεχωριστά και για τον μέσο όρο τους φυσικά. Δηλαδή, αυτό που ισχύει σίγουρα και πάνοτε είναι: \ENG $E_{cod} > E_{mes}$ \GR και \ENG $[E_{cod}] > [E_{mes}]$ \GR, όπου με Ε συμβολίζουμε τον αριθμό λαθών (errors) σε κωδικολέξη ή μήνυμα και με [Ε] την μέση τιμή τους. Στο \hyperref[Diagramme1]{figure 1}, φαίνονται 4 γραφικές παραστάσεις των διακριτών προσομοιώσεων. Οι 2 πρώτες αφορούν τα σφάλματα στην ληφθείσα κωδικολέξη, καθώς και το μέσο σφάλμα των bits σε αυτήν (εδώ πρέπει να προσεγγίζει το 9, όπως και αναφέραμε), ενώ οι 2 τελευταίες που βρίσκονται πιο χαμηλά στο διάγραμμα, αφορούν τα λάθη στα μηνύματα που αποφασίζουμε πως στάλθηκαν όντως από τον πομπό αφότου κάνουμε την αποκωδικοποίηση, καθώς και το μέσο σφάλμα τους(εμφανώς μικρότερο του 9 που έχει να κάνει με τις κωδικολέξεις).
  159. \vspace{4mm}
  160.  
  161.  
  162. \subsubsection{Προσομοίωση 2η}
  163. Στην τελευταία αυτή προσομοίωση θεωρήσαμε μήνυμα με \ENG $L = 20, er = 0.1$ \GR, οπότε αν θεωρήσουμε την παράμετρο R ως έναν βαθμό ελευθερίας και της δώσουμε τιμές, τότε για το μέσο σφάλμα στην κωδικολέξη, θα έχουμε: \ENG $[E_{cod}] = er \cdot L \cdot R = 2R$ \GR, για κάθε R. Άρα, με απλά λόγια για κάθε R, αναμένουμε περίπου 2R σφάλματα κωδικολέξης, δηλαδή έχουμε μία γραμμική εξάρτηση των λαθών στην κωδικολέξη που αποστέλλουμε με το R (αυτό απεικονίζεται στο 2ο διάγραμμα του \hyperref[Diagramme2]{figure 2}). Το 1ο και το 3ο δείχνουν την συμπεριφορά του rate και του μέσου σφάλματος αρχικού μηνύματος για R από 1 ως 19 (μόνο για τους περιττούς σε αυτό το διάστημα). Όπως, αναμένεται ο ρυθμός μετάδοσης και τα σφάλματα ακολουθούν την ασυμπτωτική συμπεριφορά της \ENG $f(x) = \frac{1}{x}$ \GR, μιας και $rate = r = r(R) = \frac{1}{R}$ \GR
  164. . Για κάθε τιμή R, πραγματοποιήθηκαν και πάλι 100 simulations για την εύρεση των μέσων σφαλμάτων, τόσο για την κωδικολέξη, όσο και για το μήνυμα.
  165. \newpage
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173. \newpage
  174. \begin{justify}
  175. \begin{figure}[H]
  176.     \centering
  177.     \includegraphics[scale=0.38]{Repetition/rep_err_aver.eps}
  178.     \caption{Errors and average error in repetition code}
  179.     \label{Diagramme1}
  180. \end{figure}
  181. \vspace{4mm}
  182.  
  183.  
  184. \begin{figure}[H]
  185.     \centering
  186.     \includegraphics[scale=0.38]{Repetition/rate_errors.eps}
  187.     \caption{Errors and average error in repetition code}
  188.     \label{Diagramme2}
  189. \end{figure}
  190. \vspace{4mm}
  191. \end{justify}
  192. \end{justify}
  193. \newpage
  194.  
  195.  
  196.  
  197. % ΑΥΤΑ ΕΔΩ ΕΙΝΑΙ ΓΙΑ ΝΑ ΜΠΟΡΕΣΟΥΝ ΝΑ ΜΠΟΥΝΕ ΣΩΣΤΑ ΣΑΝ ΘΕΣΕΙΣ ΚΑΙ ΤΑ 2 ΔΙΑΓΡΑΜΜΑΤΑ
  198. \phantom{s}
  199. \newpage
  200. \phantom{s}
  201. % ΓΡΑΦΟΥΜΕ ΜΕΤΑ ΑΠΟ ΑΥΤΑ ΠΟΥ ΜΟΥ ΔΕΣΜΕΥΣΑΝΕ ΤΙΣ ΑΠΑΡΑΙΤΗΤΕΣ ΘΕΣΕΙΣ ΣΤΟ ΧΑΡΤΙ
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209. \section{Hamming Code}
  210.  
  211.  
  212. \subsection{Αποστολή κωδικολέξης από το αρχικό μήνυμα}
  213. Ο Hamming Code είναι ένας κώδικας, οποίος μπορεί να ανιχνεύσει και να διορθώσει ένα λάθος σε ένα bitstream-codeword. Υπάρχουν και πιο προηγμένες υλοποιήσεις, οι οποίες μπορούν να βρουν βάσει κάποιας δυαδικής αντιστοίχισης τις θέσεις (index) των λαθών που συνέβησαν σε μία κωδικολέξη, όμως σε αυτή την εργασία θα παρουσιαστούν προσομοιώσεις της πρώτης περίπτωσης. Για να γίνει κατανοητή η ανάλυση του κώδικα, πρέπει να ορίσουμε 2 πίνακες, τον G (generator matrix) και τον H (parity check matrix). Ο πρώτος χρησιμοποείται κατά την αποστολή του μηνύματος, ενώ ο δεύτερος για την ανίχνευση του αρχικού μηνύατος στον πομπό βάσει της ληφθείσας κωδικολέξης. Πιο συγκεκριμένα, αν θέλουμε να στείλουμε μία πληροφορία-μήνυμα μήκους k, έστω το διάνυσμα \ENG $u = \langle u_1, u_2, \cdots, u_k \rangle$ \GR, πρέπει να το πολλαπλασιάσουμε με έναν πίνακα διαστάσεων k x n ($n > k$), ώστε να παράξουμε την τελική κωδικολέξη μήκους n.
  214. Ο πίνακας αυτός είναι ο generator matrix και έστω ότι η κωδικολέξη είναι η x:
  215. \vspace{4mm}
  216.  
  217. \ENG
  218. \begin{equation*}
  219.     \begin{split}
  220.         x &= u \cdot G \\
  221.         \langle x_1, \cdots, x_n \rangle &=
  222.         \langle u_1, \cdots, u_k \rangle
  223.         \begin{pmatrix}
  224.             g_{11} & g_{12} & \cdots & g_{1n} \\
  225.             g_{21} & g_{22} & \cdots & g_{2n} \\
  226.             \vdots & \vdots & \vdots & \ddots \\
  227.             g_{k1} & g_{k2} & \cdots & g_{kn} \\
  228.         \end{pmatrix}
  229.     \end{split}
  230. \end{equation*}
  231. \GR
  232. \vspace{4mm}
  233.  
  234.  
  235. Μιας και στέλνουμε bits 0 ή 1, τα στοιχεία $g_{ij}$ είναι κι αυτά 0 ή 1. Συνήθως προτιμούμε ο G να είναι στην λεγόμενη συστηματική μορφή, γιατί κάτι τέτοιο μας βοηθάει να βρίσκουμε εύκολα και τον πίνακα H. Συγκεκριμένα αν ο G μπορεί να γραφεί ως \ENG $G = [I_k | P]$ \GR, όπου \ENG $I_k$ ο μοναδιαίος πίνακας διάστασης k και \GR P είναι ένας k x (n-k) πίνακας, τότε ο H γράφεται ως: \ENG $H = [P^T | I_{n-k}]$ \GR, όπου τώρα \ENG $P^T$ \GR ο transposed του P και \ENG $I_{n-k}$ \GR, ο μοναδιάιος διάστασης n-k. Έτσι, βλέπουμε και πως αν ο G είναι διαστάσεων k x n, τότε ο H προκύπτει (n-k) x n.
  236. \newpage
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244. \subsection{Λήψη κωδικολέξης και ανίχνευση μηνύματος}
  245. Η κωδικολέξη \ENF $\langle x_1, x_2, \cdots, x_n \rangle$ \GR διέρχεται μέσα από BSC δίαυλο με αποτέλεσμα κάποια μηδενικά να γίνουν 1 και το αντίστροφο. Με την εφαρμογή μίας επαναληπτικής διαδικασίας και με την βοήθεια του H, μπορούμε να αποφασίσουμε ποια λέξη στάλθηκε. Για να γίνει αυτό, μία βολική μορφή είναι να θεωρήσουμε πως οι στήλες του Parity Check Matrix είναι της μορφής \ENG $2^m - 1$ \GR και πως οι γραμμές του είναι πλήθους m. Δηλαδή, πλέον έχουμε τις ισότητες:
  246.  
  247. \begin{equation*}
  248.     \begin{split}
  249.         n - k &= m \\
  250.         n &= 2^m - 1 \\
  251.     \end{split}
  252. \end{equation*}
  253.  
  254. Για διάφορα m, λοιπόν, μπορούν να προκύψουν οι εξής κώδικες Hamming:
  255. \begin{itemize}
  256.     \item \ENG $m = 2 \implies \,\, G: 1x3, \,\, H:2x3$ \GR, γνωστός και ως Hamming(3,1),
  257.     \item \ENG $m = 3 \implies \,\, G: 4x7, \,\, H:3x7$ \GR, γνωστός και ως Hamming(7,4),
  258.     \item \ENG $m = 4 \implies \,\, G: 11x15, \,\, H:4x15$ \GR, γνωστός και ως Hamming(15,11),
  259.     \item \ENG $m = 5 \implies \,\, G: 26x31, \,\, H:5x31$ \GR, γνωστός και ως Hamming(31,26),
  260. \end{itemize}
  261. \vspace{4mm}
  262.  
  263. Με αυτούς τους 4 κώδικες θα ασχοληθούμε στην ενότητα των προσομοιώσεων. Όπως αναφέρθηκε και πάνω, μένει να εξετάσουμε την διαδικασία ανίχνευση της κωδικολέξης. Αρχικά, εδώ να τονίσουμε ότι αυτό καθίσταται εφικτό, μιας και ο Hamming code (C) είναι perfect, όπως λέμε, μιας και οι "σφαίρες" των κωδικολέξεων έχουν ακτίνα \ENG $t = \lfloor d(C) - 1 = 1\rfloor$ \GR (d(C) είναι η ελάχιστη απόσταση του κώδικα και ισούται με 3). Αυτό γενικά, δείχνει πως οι σφαίρες των κωδικολέξεων στο ν-διάστατο χώρο απέχουν απόσταση 1, ώστε να μην τέμνονται. Επομένως, όταν μετά από την επαναληπτική διαδικασία παράξουμε μία πιθανή κωδικολέξη, λόγω του ότι δεν υπάρχει σφαίρα που να φιλοξενεί 2 κωδικολέξεις, θα είμαστε σε θέση να αποφανθούμε για το αρχικό μήνυμα. Έτσι, μας δίνεται η δυνατότητα να χρησιμοποιήσουμε ανιχνευτές, όπως ο BD (Bounded Distance Decoder) και ο ML (Maximum Likelihood Detector). Η συνθήκη τερματισμού της επαναληπτικής διαδικασίας είναι: \ENG $H\cdot x^T = 0$ \GR. Αν φτάσει ή παραχθεί μετά από κάθε επανάληψη, τέτοιο x, ώστε να μην επιβεβαιώνει αυτή τη σχέση, τότε πρέπει να συνεχίσουμε. Ο κώδικας Hamming εν τέλει συγκλίνει και διορθώνει το ενδεχόμενο λάθος.
  264. \newpage
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272. \subsection{Επαναλητπική διαδικασία}
  273. Αν δούμε ένα πίνακα H, τότε αυτός έχει μία μορφή σαν αυτήν εδώ (παραθέτουμε τυχαίο παράδειγμα για την ευκολία του αναγνώστη και όσα θα λεχθούν ισχύουν γενικά και όχι μόνο για τον συγκεκριμένο Η):
  274. \[
  275.     H =
  276.     \begin{pmatrix}
  277.         1 & 0 & 1 & 1 & 1 & 0 & 0 \\
  278.         0 & 1 & 1 & 1 & 0 & 1 & 0 \\
  279.         1 & 1 & 0 & 1 & 0 & 0 & 1 \\
  280.     \end{pmatrix}
  281. \]
  282. \vspace{4mm}
  283.  
  284. Από αυτόν τον πίνακα Η, μπορούμε να φτιάξουμε έναν γράφο συνδέσεων ως εξής: δημιουργούμε variable nodes με αριθμό ίσο με τις στήλες του Η (εδώ 7) και check nodes ίσα με τον αριθμό των γραμμών (εδώ 3). Ένας τέτοιος γράφος μοιάζει ως εξής:
  285.  
  286. \begin{figure}[h]
  287.     \centering
  288.     \includegraphics[scale=0.35]{Hamming/graph_ham.png}
  289.     \caption*{Graph connections}
  290.     \label{Graph}
  291. \end{figure}
  292.  
  293. Ο παραπάνω γράφος είναι η ισοδύναμη υλοποίηση του παραδείγματος του Η. Μπορεί να κατασκευαστεί ακολουθώντας τα παρακάτω βήματα:
  294. \begin{enumerate}
  295.     \item Δημιουργούμε γράφο με variable nodes (x) όσα και οι στήλες του Η και με check nodes (f), όσα οι γραμμές του.
  296.     \item Αν διαβάσουμε μία γραμμή i του Η, αυτή μας δείχνει με ποιος κόμβους μεταβλητών x συνδέεται. Όπου υπάρχει 1, υπάρχει σύνδεση των 2 κόμβων, διαφορετικά δεν υπάρχει.
  297.     \item Για παράδειγμα, η 1η γραμμή που αφορά την συνάρτηση \ENG $f_1$ \GR συνδέεται με τους κόμβους μεταβλητών \ENG $x_1, x_3, x_4, x_5$ \GR, ενώ αν το δούμε από την σκοπιά της \ENG $x_4$ \GR που είναι μεταβλητή, αυτή συνδέεται και με τους 3 κόμβους συναρτήσεων \ENG $f_1, f_2,f_3$ \GR.
  298.     \item Έτσι, ένα στοιχείο \ENG $h_{ij}$ \GR του parity check matrix υποδηλώνει σύνδεση της συνάρτησης \ENG $f_i$ \GR με την μεταβλητή \ENG $x_j$ \GR σε περίπτωση που το στοιχείο αυτό είναι μονάδα, διαφορετικά δεν χαράζουμε καμία σύνεση.
  299. \end{enumerate}
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307. Έτσι, από έναν πίνακα Η μπορεί να προκύψει ένας ισοδύναμος γράφος. Ο γράφος αυτός μπορεί να είναι δένδρο, όπως εδώ, ή όχι.
  308. Γενικά αν πάρουμε τους G και Η σε συστηματική μορφή, αυτό θα συμβεί. Για να μην έχουμε δένδρο, θα πρέπει να έχουμε δάσος (που είναι πολλά δέντρα μαζί) ή μία άλλη μορφή γράφου, μορφές που δεν θα ασχοληθούμε σε αυτήν την εργασία, διότι όλες οι προσομοιώσεις αφορούν κώδικα Hamming συστηματικής μορφής. Οι αριστεροί κόμβοι είναι τα σταθερά μηνύματα που στέλνει το κανάλι σε κάθε μεταβλητή και αφορούν τις a-posteriori πιθανότητες του καναλιού. Για να μην στέλνονται διπλά μηνύματα πιθανοτήτων της μορφής:
  309. \[(μ_k(1), μ_k(-1)) = (Pr_{Y_k|X_k}(y_k|1), Pr_{Y_k|X_k}(y_k|-1))\]
  310. κανονικοποιούμε αυτές τις πιθανότητες προσαρμόζοντας τες σε έναν λογαριθμικό λόγο της μορφής \ENG $l_k = \ln (\frac{μ_k(1)}{μ_k(-1)})$ \GR για την k-οστή μεταβλητή. Οι κόμβοι του καναλιού ανταλάσσουν μηνύματα μέσω μίας επαναληπτικής διαδικασίας η οποία σε κάθε επανάληψη εξετάζει την συνθήκη τερματισμού. Για να ελέξξουμε την συνθήκη τερματισμού πρέπει να εφαρμόσουμε το κριτήριο MAP στα μηνύματα που λαμβάνονται στους κόμβους μεταβλητών, δημιουργώντας μία πιθανή κωδικολέξη. Αν όντως \ENG $H\cdot x^T = 0$ \GR, τότε σταματάμε και η κωδικολέξη που συμπεραίνουμε είναι η x, αλλιώς συνεχίζουμε με τις τιμές που ελήφθησαν μέχρις ότου να επαληθευτεί η ισότητα.
  311. \vspace{4mm}
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319. \subsection{Πλεονεκτήματα και μειονεκτήματα}
  320. Ο κώδικας Hamming που υλοποιήσαμε διορθώνει ένα λάθος, συνεπώς σε περίπτωση που γίνουν 2 ή παραπάνω λάθη στην κωδικολέξη δεν τα διορθώνει. Βέβαια, αυτό δεν είναι τόσο περιοριστικό αρκεί να σκεφτούμε ως εξής: αν ένας δίαυλος έχει πιθανότητα λάθους er αυτό σημαίνει ότι μία κωδικολέξη μήκους \ENG $\frac{1}{er}$ \GR, θα περιέχει κατά πάσα πιθανότητα 1 λάθος. Αν η κωδικολέξη έχει παραπάνω μήκος από αυτό, τότε η πιθανότητα να περιέχει κι ένα δεύτερο λάθος σε αυτό το 2ο bitstream αυξάνεται. Εμάς μας συμφέρει η κωδικολέξη μας να έχει μικρότερο μήκος από το \ENG $\frac{1}{er}$ \GR. Δηλαδή:
  321. \newpage
  322.  
  323. \[ n \leq \frac{1}{er} \\ \]
  324. \[2^m - 1 \leq \frac{1}{er} \\ \]
  325. \[ m \leq \log _2 (1 + \frac{1}{er}) \\ \]
  326. \[ m_{max} = \lfloor \log _2 (1 + \frac{1}{er}) \rfloor \\ \]
  327. \vspace{4mm}
  328.  
  329. Για παράδειγμα, για er = 0.1, προκύπτει $ \log _2 (1 + \frac{1}{er}) = 3.4594$ κι άρα $m_{max} = 3$. Αυτό σημαίνει ότι η κωδικολέξη μας θα έχει μήκος \ENG $n_{max} = 2^3-1 = 7$ \GR στην χειρότερη περίπτωση (Hamminf(7,4)). Αν το δούμε αντίστροφα, αν έχουμε αποφασίσει ένα συγκεκριμένο m κι άρα n, τότε αναμένουμε 1 λάθος ανά \ENG $n$ bits\GR. Αυτή η "νέα πιθανότητα" σφάλματος (\ENG $er' = \frac{1}{n}$ \GR) θα πρέπει να είναι μεγαλύτερη από το er του διαύλου που θα επιλέξουμε για μετάδοση. Με άλλα λόγια, θέλουμε: \ENG $er' \geq er \implies \frac{1}{n} \geq er \implies n \leq \frac{1}{er}$ \GR.
  330. \vspace{4mm}
  331.  
  332.  
  333.  
  334.  
  335. \subsection{Προσομοιώσεις}
  336.  
  337. \subsubsection{Προσομοίωση 1}
  338. Στον Hamming code μπορούμε να θεωρήσουμε πως υπάρχουν 2 βαθμοί ελευθερίας: α)το μήκος κωδικολέξης n και β) η πιθανότητα σφάλματος του καναλιού er (single bit error probability). Στην προσομοίωση αυτή, αλλά και στην επόμενη κρατήσαμε το m σταθερό (εδώ στην τιμή 3 και μετά στην τιμή 4) και αλλάζαμε τις τιμές er. Εν συνεχεία για κάθε συγκεκριμένη er τρέχαμε 100 προσομοιώσεις για να βρούμε μία μέση τιμή διόρθωσης του μηνύματος (ασχοληθήκαμε με κωδικολέξεις που όντως έφταναν με 1 error και άρα μπορούσαμε να τις διορθώσουμε). Εντούτοις, ενώ θα περίμενε κανείς να τις διορθώνει πάντα, κάτι τέτοιο δεν γίνεται. Μάλιστα, όπως θα δούμε και παρακάτω για m=3 κι άρα n=7 (κωδικολέξεις μήκους 7), υπάρχει μία περιοχή τιμών κοντά στο er = 0.11 - 0.13, στις οποίες όντως ο αλγόριθμός μας διορθώνει με επιτυχία 100\% όλες τις κωδικολέξεις (και στα 100 simulations). Στις γειτονικές όμως τιμές er, η πιθανότητα διόρθωσης πέφτει. Πιο συγκεκριμένα, για τις πληροφορίες του κώδικα που κατασκευάστηκε:
  339.  
  340. \begin{itemize}
  341.     \item Eπιλέξαμε \ENG $m = 3 \implies n = 7$ \GR, άρα στέλναμε εφτάδες (κωδικολέξεις μήκους 7). \\
  342.     \item Μιας και έχουμε Hamming(7,4) μετασχηματίζουμε μηνύματα 4 bit σε κωδικολέξεις 7 bit. \\
  343.     \item Για 7 bit, η πιθανότητα που θα μας εξασφάλιζε μακροπρόθεσμα περίπου 1 λάθος ανά κωδικολέξη ήταν το \ENG $1/7 = 14.28 \%$ \GR και άρα εμείς αναμένουμε καλή διόρθωση λαθών για τιμές er από 0 ως 14 \% περίπου.
  344.     \item Κάτι τέτοιο, όντως διαπιστώνεται στο \hyperref[Diagramme3]{figure 3}, μιας και βλέπουμε ότι μετά το \ENG $1/7$ \GR, ο αλγόριθμός μας παρότι φτάνει 1 error στην κωδικολέξη δεν διορθώνει καλά. Ο βασικός λόγος είναι ότι με αυτό το er αλλάζουν πολύ οι τιμές των πιθανοτήτων που στέλνει μονίμως το κανάλι σε κάθε μεταβλητή, οπότε και με την MAP ανίχνευση, πέφτουν οι πιθανότητες να κάνουμε όντως την επιθυμητή διόρθωση.
  345.     \item Optimum περιοχή er για Hamming(7,4): \ENG $0.11 \leq er \leq 0.13$ \GR, αλλά και πιο γενικά στην περιοχή $0 \leq er \leq 0.14$.
  346. \end{itemize}
  347. \vspace{2mm}
  348.  
  349.  
  350.  
  351. \subsubsection{Προσομοίωση 2η}
  352. Εδώ κάναμε την ίδια διαδικασία με πάνω, αλλά πήραμε m=4 και άρα n=15. Μιας και στέλνουμε κωδικολέξεις μήκους 15, αναμένουμε καλή συμπεριοφορά στις περιοχές κάτω από το \ENG $1/15 = 6.67 \%$ \GR. Σε αντίθεση με προηγουμένως, στο γράφημα θα φανούν μόνο τιμές από 0.00 ως 0.06 (βήμα 0.005), όπου όντως ο αλγόριθμος είναι αποδοτικός (για την ακρίβεια optimum περιοχή από 0 ως 0.05).
  353. \vspace{2mm}
  354.  
  355.  
  356.  
  357.  
  358. \subsubsection{Προσομοίωση 3η}
  359. Στην τελευταία προσομοίωση, πήραμε 4 περιπτώσεις συνδυασμών των 2 βαθμών ελευθερίας που θέσαμε και εξετάσαμε την πιθανότητα διόρθωσης της απεσταλμένης κωδικολέξης. Επιλέξαμε:
  360.  
  361. \begin{enumerate}
  362.     \item \ENG $m = 2 \implies n = 3$ \GR και \ENG $er = 0.3$ \GR (θέλουμε κάτω του \ENG $1/3 = 33.33 \%$ \GR).
  363.     \item \ENG $m = 3 \implies n = 7$ \GR και \ENG $er = 0.1$ \GR (θέλουμε κάτω του \ENG $1/7 = 14.28 \%$ \GR).
  364.     \item \ENG $m = 4 \implies n = 15$ \GR και \ENG $er = 0.05$ \GR (θέλουμε κάτω του \ENG $1/15 = 6.67 \%$ \GR).
  365.     \item \ENG $m = 5 \implies n = 31$ \GR και \ENG $er = 0.01$ \GR (θέλουμε κάτω του \ENG $1/31 = 3.22 \%$ \GR).
  366. \end{enumerate}
  367. \vspace{2mm}
  368.  
  369. Το αριστερά διάγραμμα απεικονίζει αυτούς τους συνδυασμούς n και er, ενώ το δεξιά μας δείχνει μετά από 500 simulations, το ποσοστό διόρθωσης κωδικολέξης (σε κάθε 1/500 simulations στέλνουμε μία τυχαία) με 1 λάθος για τους επιλεγμένους συνδυασμούς (\hyperref[Diagramme5]{figure 5}).
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378. \newpage
  379. \begin{justify}
  380. \begin{figure}[H]
  381.     \centering
  382.     \includegraphics[scale=0.32]{Hamming/err_prob_n3.eps}
  383.     \caption{Success percentage in Hamming(7,4) for er = 0.00-0.20 (step=0.005)}
  384.     \label{Diagramme3}
  385. \end{figure}
  386. \vspace{4mm}
  387. \end{justify}
  388.  
  389. \begin{justify}
  390. \begin{figure}[H]
  391.     \centering
  392.     \includegraphics[scale=0.32]{Hamming/err_prob_n4.eps}
  393.     \caption{Success percentage in Hamming(15,11) for er = 0.00-0.06 (step=0.005)}
  394.     \label{Diagramme3}
  395. \end{figure}
  396. \vspace{4mm}
  397. \end{justify}
  398. \newpage
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405. % ΑΥΤΑ ΕΔΩ ΕΙΝΑΙ ΓΙΑ ΝΑ ΜΠΟΡΕΣΟΥΝ ΝΑ ΜΠΟΥΝΕ ΣΩΣΤΑ ΣΑΝ ΘΕΣΕΙΣ ΚΑΙ ΤΑ 2 ΔΙΑΓΡΑΜΜΑΤΑ
  406. \phantom{s}
  407. \newpage
  408. \phantom{s}
  409. % ΓΡΑΦΟΥΜΕ ΜΕΤΑ ΑΠΟ ΑΥΤΑ ΠΟΥ ΜΟΥ ΔΕΣΜΕΥΣΑΝΕ ΤΙΣ ΑΠΑΡΑΙΤΗΤΕΣ ΘΕΣΕΙΣ ΣΤΟ ΧΑΡΤΙ
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417. \begin{justify}
  418. \begin{figure}[H]
  419.     \centering
  420.     \includegraphics[scale=0.32]{Hamming/diff_er.eps}
  421.     \caption{Success percentage in Hamming(n,n-m) for combinations of n and er}
  422.     \label{Diagramme3}
  423. \end{figure}
  424. \vspace{4mm}
  425. \end{justify}
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  446. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  447. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  448. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ APPENDICES ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  449. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  450. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  451. \newpage
  452. \phantom{s}
  453. \newpage
  454. \appendices
  455. \section{\ENG Proof of the First Zonklar Equation}
  456. \ENG Appendix one text goes here.
  457.  
  458. % you can choose not to have a title for an appendix
  459. % if you want by leaving the argument blank
  460. \section{}
  461. Appendix two text goes here.
  462.  
  463.  
  464. % use section* for acknowledgment
  465. \section*{Acknowledgment}
  466.  
  467.  
  468. The authors would like to thank...
  469.  
  470.  
  471. % Can use something like this to put references on a page
  472. % by themselves when using endfloat and the captionsoff option.
  473. \ifCLASSOPTIONcaptionsoff
  474.   \newpage
  475. \fi
  476.  
  477.  
  478.  
  479. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  480. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  481. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  482. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ BIBLIOGRAPHY ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  483. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  484. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  485.  
  486. \newpage
  487. \begin{thebibliography}{1}
  488.  
  489.     \bibitem{IEEEhowto:kopka}
  490.     H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
  491.       0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
  492.    
  493.     \end{thebibliography}
  494.    
  495.    
  496.     \begin{IEEEbiography}{Θωμάς Μπουφίκος}
  497.     Biography text here.
  498.     \end{IEEEbiography}
  499.    
  500.     % if you will not have a photo at all:
  501.     \begin{IEEEbiographynophoto}{Δημήτριος Σκλαβενίτης}
  502.     Biography text here.
  503.     \end{IEEEbiographynophoto}
  504.    
  505.     % insert where needed to balance the two columns on the last page with
  506.     % biographies
  507.     %\newpage
  508.    
  509.     \begin{IEEEbiographynophoto}{Ράλλης Τσολακίδης}
  510.     Biography text here.
  511.    
  512. \end{IEEEbiographynophoto}
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520. \end{document}
  521.  
  522.  
  523.  
Advertisement
RAW Paste Data Copied
Advertisement