makispaiktis

Report - Error Correcting Codes

Jan 21st, 2022 (edited)
945
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. \subsection{\textit{Αποστολή κωδικολέξης από αρχικό μήνυμα}}
  134. Ο repetition code είναι ίσως ο πιο απλός κώδικας διόρθωσης σφαλμάτων που υπάρχει. Σήμερα, δεν χρησιμοποείται στην πλειοψηφία των εφαρμογών, διότι ρίχνει αρκετά τον ρυθμό μετάδοσης από τη μέγιστη τιμή που μπορεί να πάρει και η οποία είναι 1. Πιο συγκεκριμένα, ο κώδικας αυτός, παίρνει τα bits του μηνύματος που επιθυμούμε να στείλουμε και για καθένα από αυτά, αντιγράφει R φορές την ίδια τιμή του εκάστοτε bit μηνύματος (0 ή 1). Αυτό σημαίνει πως όλο το μήνυμα πλέον έχει μετασχηματιστεί σε μία μεγαλύτερη κωδικολέξη, με μήκος R φορές μεγαλύτερο. Αν επιθυμούμε, δηλαδή για παράδειγμα, να αποστείλουμε μέσω ενός καναλιού BSC ένα μήνυμα μήκους L, τότε αφού κάθε Bit του επαναλμάνεται R φορές στην κωδικολέξη, το τελικό μήνυμα-κωδικολέξη θα έχει μήκος \ENG $L' = R \cdot L$ \GR, ρίχνοντας έτσι τον ρυθμό μετάδοσης όπως είπαμε και παραπάνω. Βέβαια, το πολύ θετικό του κώδικα αυτού είναι ότι όσο αυξάνεται το R, τόσο αυξάνεται και η πιθανότητα διόρθωσης ενός μηνύματος για δεδομένη πιθανότητα σφάλματος er του καναλιού BSC. Με άλλα λόγια, υπάρχει ένα trade-off ανάμεσα σε ρυθμό μετάδοσης και πιθανότητα σφάλματος.
  135. \vspace{2mm}
  136.  
  137. \subsection{\textit{Αποκωδικοποίηση κωδικολέξης και ανίχνευση του αρχικού μηνύματος}}
  138. Όταν στον δέκτη μας φτάσει η παραλλαγμένη κωδικολέξη λόγω της αλλοιωτικής επίδρασης του καναλιού, θα πρέπει να βρούμε έναν τρόπο να μπορούμε να συμπεράνουμε ποια κωδικολέξη έχει σταλεί και επομένως, να βρούμε και το αρχικό μήνυμα. Η διαδικασία που ακολουθούμε είναι η εξής: αρχικά, σπάμε την ληφθείσα κωδικολέξη ανά R bits (το R είναι γνωστό σε πομπό και δέκτη) και μετράμε πόσα bit είναι 0 και πόσα 1 (συνήθως επιλέγουμε R να είναι περιττό). Αν στα R bits, το bit που εμφανίζεται πιο συχνά είναι το 0 συμπεραίνουμε πως στο αρχικό μήνυμα αντί για αυτά τα R bits υπήρχε το 0, αλλιώς συμπεραίνουμε το 1.
  139. \vspace{2mm}
  140.  
  141. \subsection{Θετικά και αρνητικά}
  142. Από την στιγμή που μετασχηματίζουμε ένα μήνυμα μεγέθους \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 εν αντιθέσει με τα σφάλματα μηνύματος). Όλες αυτές οι παρατηρήσεις θα καταστούν φανερές και στην επόμενη ενότητα, όπου θα παρατεθούν γραφικές παραστάσεις από πολλαπλές προσομοιώσεις καναλιού.
  143. $ \GR
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  153. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  154. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  155. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ APPENDICES ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  156. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  157. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  158.  
  159. \newpage
  160. \appendices
  161. \section{\ENG Proof of the First Zonklar Equation}
  162. \ENG Appendix one text goes here.
  163.  
  164. % you can choose not to have a title for an appendix
  165. % if you want by leaving the argument blank
  166. \section{}
  167. Appendix two text goes here.
  168.  
  169.  
  170. % use section* for acknowledgment
  171. \section*{Acknowledgment}
  172.  
  173.  
  174. The authors would like to thank...
  175.  
  176.  
  177. % Can use something like this to put references on a page
  178. % by themselves when using endfloat and the captionsoff option.
  179. \ifCLASSOPTIONcaptionsoff
  180.   \newpage
  181. \fi
  182.  
  183.  
  184.  
  185. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  186. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  187. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  188. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ BIBLIOGRAPHY ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  189. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  190. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  191.  
  192. \newpage
  193. \begin{thebibliography}{1}
  194.  
  195.    \bibitem{IEEEhowto:kopka}
  196.    H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
  197.      0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
  198.    
  199.    \end{thebibliography}
  200.    
  201.    
  202.    \begin{IEEEbiography}{Θωμάς Μπουφίκος}
  203.    Biography text here.
  204.    \end{IEEEbiography}
  205.    
  206.     % if you will not have a photo at all:
  207.     \begin{IEEEbiographynophoto}{Δημήτριος Σκλαβενίτης}
  208.    Biography text here.
  209.    \end{IEEEbiographynophoto}
  210.    
  211.     % insert where needed to balance the two columns on the last page with
  212.     % biographies
  213.     %\newpage
  214.    
  215.     \begin{IEEEbiographynophoto}{Ράλλης Τσολακίδης}
  216.    Biography text here.
  217.    
  218. \end{IEEEbiographynophoto}
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. \end{document}
  227.  
  228.  
  229.  
RAW Paste Data Copied