Advertisement
makispaiktis

Full report

Jan 25th, 2022
1,248
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 στην χειρότερη περίπτωση (Hamming(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{Diagramme5}
  423. \end{figure}
  424. \vspace{4mm}
  425. \end{justify}
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433. \section{LDPC Codes}
  434. Οι κώδικες αυτοί λαμβάνουν χώρα στα λεγόμενα BEC κανάλια (Binary Erasure Channel) και είναι γραμμικοί κώδικες με αραιό Tanner graph. Μία συνηθισμένη μορφή τους περιλαμβάνει n κόμβους μεταβλητών και (n-k) κόμβους συναρτήσεων με σταθερό βαθμό για καθέναν τους, έστω l και m αντίστοιχα. Έτσι, θα πρέπει να ικανοποιείται η σχέση \ENG $l \cdot n = m \cdot (n-k)$ \GR, ώστε οι ακμές από όποια μεριά του γράφου κι αν υπολογιστούν να είναι ίσες. Για την αύξηση του rate, ωστόσο, συνήθως επιλέγουμε να μην δίνουμε σταθερό βαθμό σε κάθε είδος κόμβου, αλλά επιτρέπουμε μία κατανομή βαθμών. Επιδιώκουμε μέσω αυτής της κατανομής το rate που ισούται με \ENG $r = \frac{n-k}{n}$ \GR να γίνει όσο το δυνατόν μεγαλύτερο. Για αυτό είναι αναγκαίος ο ορισμός μίας σειράς μεταβλητών, που θα μας βοηθήσουν στο πρόβλημα.
  435.  
  436.  
  437. \subsection{Δημιουργία πίνακα Η}
  438. Αρχικά, έστω πως έχουμε έναν μέγιστο αριθμό βαθμού κορυφών, \ENG $r_{max}$ \GR για τις μεταβλητές και \ENG $l_{max}$ \GR για τις συναρτήσεις. Δεδομένων κάποιων συνθηκών, επιδιώκουμε να μεγιστοποιήσουμε τον ρυθμό μετάδοσης:
  439. $r = r(λ,ρ) = 1 - \frac{\sum _{i=1} \frac{ρ_i}{i} }{\sum _{i=1} \frac{λ_i}{i}}$.
  440. \newpage
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448. \phantom{s}
  449. \vspace{122.5mm}
  450. Ακολουθώντας συγκεκριμένους περιορισμούς και λαμβάνοντας υπόψιν την πιθανότητα σφάλματος er στο BEC δίαυλο, καταλήγουμε στην εύρεση των λιστών λ και ρ, τις οποίες μπορούμε να αντιμετωπίσουμε και ως πολυώνυμα. Συγκεκριμένα για δεδομένα  \ENG $r_{max}$ \GR και \ENG $l_{max}$ \GR, εφαρμόζουμε την υπορουτίνα intlinprog του Matlab, για να υπολογίσουμε τις βέλτιστες λύσεις για τα $ρ_i$ και $λ_i$. Οι επιστρεφόμενες λίστες εκφράζουν για την θέση i της λίστας, το ποσοστό των κόμβων που έχουν βαθμό i-1 (συνδέονται με  i-1 άλλους κόμβους δηλαδή). Προφανώς, θα έχουν μηδέν στην 1η θέση, πράγμα αναμενόμενο και βάσει της παραπάνω εξήγησης, αφού δεν γίνεται κάποιος κόμβος να έχει βαθμό 0 και να μην έχει καθόλου συνδέσεις-ακμές. Οι λίστες αυτές εκφράζονται και ως κανονικοποιημένα πολυώνυμα:
  451.  
  452. \begin{equation*}
  453.    \begin{split}
  454.        λ(x) &= \sum _{i=1} λ_i \cdot x^{i-1} =^{λ_1=0} \\
  455.             &= λ_2x + λ_3x^2 + \cdots + λ_{l_{max}}x^{l_{max} - 1} \\ \\
  456.        ρ(x) &= \sum _{i=1} ρ_i \cdot x^{i-1} =^{ρ_1=0} \\
  457.             &= ρ_2x + ρ_3x^2 + \cdots + ρ_{r_{max}}x^{r_{max} - 1} \\
  458.    \end{split}
  459. \end{equation*}
  460. \newpage
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468. Βρίσκοντας τα λ(x) και ρ(x), ακολοθούμε μία διαδικασία έυρεσης των πολυωνύμων Λ(x) και R(x), τα οποία έχουν την μορφή:
  469.  
  470. \begin{equation*}
  471.    \begin{split}
  472.        Λ(x) &= \sum _{i=1} Λ_i \cdot x^{i-1} = \\
  473.             &= λ_1x + Λ_2x^2 + \cdots + Λ_{l_{max}}x^{l_{max}} \\ \\
  474.        Ρ(x) &= \sum _{i=1} Ρ_i \cdot x^{i-1} = \\
  475.             &= Ρ_1x + Ρ_2x^2 + \cdots + Ρ_{r_{max}}x^{r_{max}} \\
  476.    \end{split}
  477. \end{equation*}
  478. \vspace{4mm}
  479.  
  480. Τώρα οι συντελεστές $Λ_i$ και \ENG $R_i$ \GR συμβολίζουν το πλήθος των κόμβων με βαθμό i για τους κόμβους συναρτήσεων και μεταβλητών αντίστοιχα. Είναι εμφανές ότι Λ(1) = n και R(1) = n-k, ώστε ο ρυθμός μετάδοσης βάσει του γράφου να είναι: \ENG $r = 1 - \frac{R(1)}{Λ(1)}$ \GR. Γνωρίζοντας πλέον πόσες ακμές έχει κάθε κόμβος, μπορούμε να δημιουργήσουμε τον parity check matrix. Ξέρουμε σίγουρα πως ο αριθμός ακμών E είναι ο ίδιος είτε κάνουμε την πρόσθεση από την πλευρά των variable nodes είτε την εκτελέσουμε για τους check nodes. Αυτός το Ε είναι ο αριθμός των sockets. Κατασκευάζουμε έναν πίνακα Ε x Ε και, μιας και ξέρουμε πόσα sockets έχει κάθε κόμβος (μέσα από την κατανομή των Λ(x) και R(x)), σταδιακά τον αποσυνθέτουμε για να δημιουργήσουμε έναν πίνακα (n-k) x n, ο οποίος είναι ο parity check matrix. Η αποσύνθεση έχει στάνταρ αλγοριθμικά βήματα, ωστόσο η επιτυχία της εξαρτάται από την τύχη. Για να δημιουργήσουμε τον πίνακα Ε x E των sockets, κάνουμε combinations των κόμβων μεταξύ τους. Αν προκύψει ανακύκλωση είναι σαν να μην υπάρχει αυτή η διπλή σύνδεση και ο Η που θα προκύψει δεν θα είναι σωστός. Κάνουμε, λοιπόν, όσες επαναλήψεις απαιτούνται ώστε τα 2 τυχαία παραγόμενα permutations που αφορούν τα sockets να μην έχουν καμία ανακύκλωση. Έτσι, ο αριθμός των 1 στο πίνακα Η θα είναι ίσος με Ε, όσες και οι επιθυμητές ακμές. Στην ουσία, έτσι, δικαιολογείται και το όνομα του κώδικα (Low Density Parity Check). Από τον πίνακα Ε x Ε (των sockets), προκύπτει ο Η που περιέχει E μονάδες (Ε μονάδες σημαίνει Ε ακμές), γεγονός που σημαίνει ότι σε χώρο \ENG $Ε^2$ \GR στοιχείων συναντάμε μόλις Ε άσσους, δηλαδή η πυκνότητα της μονάδας είναι \ENG $\frac{1}{E}$ \GR.
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489. \subsection{Αλγόριθμος}
  490. Έχοντας παράξει μετά από τυχαίο αριθμό προσπαθειών (αποτυχίες οφείλονται στα τυχαία permutations που προκαλούν ανακυκλώσεις) τον Η, εφαρμόζουμε κανόνες σαν αυτούς της παραπάνω ενότητας σαν λογική, αλλά με διαφορετικές μαθηματικές πράξεις. Και πάλι προσομοιώνουμε τα ζεύγη πιθανοτήτων που ταξιδεύουν μέσω τον ακμών στον γράφο σαν ένα κανονικοποιημένο μήνυμα. Στον κώδικα Matlab που δημιουργήσαμε, έχουμε συμβολίσει τα μηνύματα αυτά ως εξής:
  491.  
  492. \begin{itemize}
  493.    \item 0: το bit 0 \\
  494.    \item 1: το bit 1 \\
  495.    \item Inf: το erasure
  496. \end{itemize}
  497. \vspace{4mm}
  498.  
  499. Μία τέτοια αντιστοίχιση μοιάζει προφανής, αλλά προκύπτει μέσω των παρακάτω πινάκων:
  500. \begin{table}[h]
  501.    \centering
  502.    \begin{tabular}{|c|c|c|c|}
  503.    
  504.         \hline
  505.         $y_j$ & $μ_j(0)$ & $μ_j(1)$ & Message \\
  506.         \hline
  507.         0 & 1-er & 0 & "Zero" \\
  508.         \hline
  509.         ? & er & er & "Erasure" \\
  510.         \hline
  511.         1 & 0 & 1-er & "One" \\
  512.         \hline
  513.        
  514.    \end{tabular}
  515.    \caption*{Probability messages}
  516.    \label{Table1}
  517. \end{table}
  518. \vspace{4mm}
  519.  
  520. \begin{table}[h]
  521.    \centering
  522.    \begin{tabular}{|c|c|c|c|}
  523.    
  524.         \hline
  525.         $y_j$ & $μ_j(0)$ & $μ_j(1)$ & Message \\
  526.         \hline
  527.         0 & 1 & 0 & "Zero" \\
  528.         \hline
  529.         ? = Inf & 1 & 1 & "Erasure" \\
  530.         \hline
  531.         1 & 0 & 1 & "One" \\
  532.         \hline
  533.        
  534.    \end{tabular}
  535.    \caption*{Normalized (for simplification)}
  536.    \label{Table2}
  537. \end{table}
  538. \vspace{4mm}
  539.  
  540.  
  541.  
  542.  
  543. \subsection{Αποστολή και λήψη}
  544. Η κωδικολέξη που θα αποστείλουμε στον BEC δίαυλο θα έχει μήκος όσο και οι στήλες του Η, δηλαδή n. Εξάλλου αυτός είναι και ο αριθμός των variable nodes, καθένας από τους οποίους αντιστοιχεί για κάθε bit πληροφορίας στην λήψη.
  545. Αν k είναι ο αριθμός των κόμβων συναρτήσεων, τότε ο μέγιστος ρυθμός μετάδοσης βάσει του Shannon και της θεωρίας πληροφορίας είναι: \ENG $r = 1 - \frac{k}{n}$ \GR. Εμείς με τον αλγόριθμο που κατασκευάσαμε για να διορθώνουμε τα λάθη φτάνουμε συνήθως αρκετά κοντά σε αυτό το νούμερο (συνήθως στο 85-90 \% του θεωρητικού ανώτερου ορίου), οπότε τέτοια ποσοστά είναι ικανοποιητικά. Η μοναδική κωδικολέξη που μπορούμε να στείλουμε είναι η μηδενική (λίστα με n μηδενικά), μιας και τώρα δεν γνωρίζουμε τον G, για να παράξουμε μία τυχαία κωδικολέξη. Αξίζει μάλιστα να σημειώσουμε ότι σε όλες τις περιπτώσεις, όλα τα λάθη διορθώνονται. Για παράδειγμα στην συνάρτηση test.m στέλνουμε 202 μηδενικά με er = 0.2, οπότε αναμένουμε κοντά στα 40 λάθη στην ληφθείσα κωδικολέξη. Μέσα από 3-4 επαναλήψεις του επαναληπτικού αλγορίθμου, συμπεραίνουμε εν τέλει την σωστή κωδικολέξη σε κάθε περίπτωση. Τρέξαμε μάλιστα και προσομοίωση με er=0.8, στην οποία έγιναν πάρα πολλά λάθη, αλλά διορθώθηκαν εν τέλει μετά από σειρά επαναλήψεων. Πάντως, εδώ να σημειώσουμε 3 πράγματα:
  546.  
  547. \begin{enumerate}
  548.    \item Η ταχύτητα σύγκλισης του αλγορίθμου έχει να κάνει με τον αριθμό των ληφθέντων λαθών.
  549.    \item Ορισμένες φορές ένας ανασταλτικός παράγοντας στο να τρέξει γρήγορα μία προσομοίωση είναι η δημιουργία του Η. Ειδικά για μεγάλα n, επειδή τυχαίνει πολύ συχνά να έχουμε ανακυκλώσεις στον Η, ο χρόνος εκτέλεσης του προγράμματος αυξάνεται. Η τύχη, δηλαδή, καθορίζει το πόσο γρήγορα θα παραχθεί ο Η, βάσει του δεδομένουν αριθμού των sockets.
  550.    \item Υπάρχουν ορισμένοι συνδυασμοί \ENG $n, \,\, l_{max}, \,\, r_{max}$ \GR, οι οποίοι προφανώς αποτυγχάνουν, μιας και χρησιμοποιήθηκε η προσεγγιστική διαδικασία εύρεσης των πολυωνύμων λ(x), ρ(x), Λ(x) και R(x). Είναι δηλαδή, ορισμένες φορές που δεν μπορούν να βρεθούν οι βέλτιστες τιμών μέσω της intlinprog, γιατί κάποιοι περιορισμοί καταστρατηγούνται.
  551. \end{enumerate}
  552. \vspace{4mm}
  553.  
  554.  
  555.  
  556.  
  557.  
  558. \subsection{Προσομοιώσεις}
  559.  
  560. \subsubsection{Προσομοίωση 1η}
  561. Η 1η προσομοίωση είναι απλώς μία επιβεβαίωση της λειτουργίας του κώδικά μας και δεν εξάγει κάποιο διάγραμμα. Στην test.m, θέτουμε όπως είπαμε και πιο πάνω, n = 202, er = 0.2, \ENG $l_{max} = 4$ και \GR\ENG $r_{max} = 6$ \GR και υπολογίζουμε μία σειρά μεταβλητών, όπως:
  562.  
  563. \begin{itemize}
  564.    \item τον αριθμό των variable nodes (προφανώς ίσος με n=202),
  565.    \item τον αριθμό των check nodes, που είναι μικρότερος του n, ώστε και το rate να είναι θετικό,
  566.    \item τον αριθμό των ακμών του γράφου (υπολογίζεται με 2 τρόπους και μας δίνει το ίδιο αποτέλεσμα)
  567.    \item τον αριθμό των προσπαθειών που έγιναν μέχρι να παραχθεί ο Η (συχνά μεγάλος για μεγάλα n, λόγω της χρήσης της randperm - Matlab),
  568.    \item το rate του γράφου (0.29703),
  569.    \item και τέλος, τα αρχικά και τα τελικά λάθη της κωδικολέξης (τα πρώτα κοντά στο 40 και τα τελευταία πάντα 0).
  570. \end{itemize}
  571. \vspace{2mm}
  572. Εκτυπώνουμε, επίσης, και τα bitstream για επιβεβαίωση της καλής λειτουργίας του προγράμματος.
  573. \vspace{4mm}
  574.  
  575.  
  576.  
  577. \subsubsection{Προσομοίωση 2η}
  578. Στην προσομοίωση αυτή (test with stats and plots), τρέχουμε πολλά simulations με er=0.2 και \ENG $l_{max}=4$ \GR, \ENG $r_{max}=6$ \GR. Κάθε φορά αλλάζουμε το n και του δίνουμε τιμές από 101 ως και 301 με βήμα 5. Σε ορισμένες περιπτώσεις είναι πιθανόν αυτοί οι συνδυασμοί των βαθμών ελευθερίας να μην μπορούν να μας δώσουν λύσεις για τις λίστες-πολυώνυμα, οπότε αποκλείονται και από τα διαγράμματα. Τα συμπεράσματα που βγαίνουν για αυτά τα n, μέσα από πολλά "τρεξίματα" αυτού του αρχείου είναι:
  579.  
  580. \begin{enumerate}
  581.    \item ο αριθμός των check nodes, variable nodes και των συνολικών ακμών-sockets αυξάνεται γραμμικά με την αύξηση του n, δηλαδή του αριθμού των variable nodes,
  582.    \item ο ρυθμός μετάδοσης \ENG $r = 1 - \frac{check\,\,nodes}{variable\,\,nodes}$ \GR παραμένει σταθερός με κάποια ανεβοκατεβάσματα, τα οποία ,σε περιπτώσεις που ο κώδικας τρέξει για όλα αυτά το n σε αυτό το διάστημα, φαίνεται να σχηματίζουν μία κοίλη μορφή σαν αυτή της \ENG $f(x) = \sqrt{x}$ \GR,
  583.    \item ο αριθμός των προσπαθειών για την δημιουργία πίνακα Η για κάθε n είναι καθαρά τυχαίος (3ο διάγραμμα) και είναι και ο λόγος που ίσως δεν τρέξει με την 1η φορά η προσομοίωση και
  584.    \item ο αριθμός των λαθών στην κωδικολέξη φαίνεται να ακολουθεί την γραμμική ιδανική-αναμενόμενη μορφή (\ENG $[E_{cod}] = er \cdot n$ \GR), όπου n είναι το μήκος κωδικολέξης. Τα τελικά λάθη είναι πάντα 0 (μία ευθεία γραμμή που ταυτίζεται με τον οριζόντιο άξονα).
  585. \end{enumerate}
  586. \vspace{4mm}
  587.  
  588. Στην 2η παρατήρηση, είπαμε πως το rate ανεβοκατεβαίνει σε ένα στενό range τιμών (εδώ από 0.294 ως 0.302), αλλά σε κάποιες προσομοιώσεις φαίνεται να είναι μία κοίλη συνάρτηση του n, όπως η \ENG $\sqrt{x}$ \GR. Αυτό επιβεβαιώνεται με το \hyperref[Diagramme10]{figure 10}, το οποίο προέκυψε ύστερα από κάποια τρεξίματα της συνάρτησης.
  589. \newpage
  590.  
  591.  
  592.  
  593.  
  594.  
  595.  
  596.  
  597. \begin{justify}
  598. \begin{figure}[H]
  599.    \centering
  600.    \includegraphics[scale=0.32]{LDPC/var_ch_edg.eps}
  601.    \caption{Graph characteristics depending on n}
  602.    \label{Diagramme6}
  603. \end{figure}
  604. \vspace{4mm}
  605. \end{justify}
  606.  
  607. \begin{justify}
  608. \begin{figure}[H]
  609.    \centering
  610.    \includegraphics[scale=0.32]{LDPC/rate.eps}
  611.    \caption{Rate (based on graph) depending on n}
  612.    \label{Diagramme7}
  613. \end{figure}
  614. \vspace{4mm}
  615. \end{justify}
  616. \newpage
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624. % ΑΥΤΑ ΕΔΩ ΕΙΝΑΙ ΓΙΑ ΝΑ ΜΠΟΡΕΣΟΥΝ ΝΑ ΜΠΟΥΝΕ ΣΩΣΤΑ ΣΑΝ ΘΕΣΕΙΣ ΚΑΙ ΤΑ 2 ΔΙΑΓΡΑΜΜΑΤΑ
  625. \phantom{s}
  626. \newpage
  627. \phantom{s}
  628. % ΓΡΑΦΟΥΜΕ ΜΕΤΑ ΑΠΟ ΑΥΤΑ ΠΟΥ ΜΟΥ ΔΕΣΜΕΥΣΑΝΕ ΤΙΣ ΑΠΑΡΑΙΤΗΤΕΣ ΘΕΣΕΙΣ ΣΤΟ ΧΑΡΤΙ
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636. \vspace{8mm}
  637. \begin{justify}
  638. \begin{figure}[H]
  639.    \centering
  640.    \includegraphics[scale=0.15]{LDPC/tries.eps}
  641.    \caption{Tries until graph without circles depending on n}
  642.    \label{Diagramme8}
  643. \end{figure}
  644. \vspace{4mm}
  645. \end{justify}
  646.  
  647.  
  648. \begin{justify}
  649. \begin{figure}[H]
  650.    \centering
  651.    \includegraphics[scale=0.32]{LDPC/errors.eps}
  652.    \caption{Codeword errors depending on n}
  653.    \label{Diagramme9}
  654. \end{figure}
  655. \vspace{4mm}
  656. \end{justify}
  657. \newpage
  658.  
  659.  
  660.  
  661.  
  662.  
  663.  
  664.  
  665. \phantom{s}
  666. \vspace{9mm}
  667. \begin{justify}
  668. \begin{figure}[H]
  669.    \centering
  670.    \includegraphics[scale=0.12]{LDPC/rate_correct.jpg}
  671.    \caption{Rate depending on n}
  672.    \label{Diagramme10}
  673. \end{figure}
  674. \vspace{4mm}
  675. \end{justify}
  676. \newpage
  677.  
  678.  
  679.  
  680.  
  681.  
  682.  
  683.  
  684. \subsubsection{Προσομοίωση 3η}
  685. Στην τελευταία αυτή προσομοίωση, θέσαμε er=0.2 και n=101 και επιδιώξαμε να τρέξουμε τον κώδικα LDPC αλλάζοντας τα ζευγάρια τιμών των λιστών \ENG $l_{max}$ \GR και \ENG $r_{max}$ \GR (προηγουμένως ήταν 4 και 6 αντίστοιχα). Στις περισσότερες περιπτώσεις, ο κώδικας δουλεύει (κάποιες φορές επειδή δεν φτιάχνει σε πολλούς συνδυασμούς το Η σταματάει) και εξάξει ένα 3D διάγραμμα. Σε αυτό ουσιαστικά για κάθε δυάδα-συνδυασμό των \ENG $l_{max}$ \GR, \ENG $r_{max}$ \GR, αποτυπώνουμε 3 rates. Το θεωρητικό upper bound του Shannon και της θεωρίας πληροφορίας (*), το rate που βασίζεται στον τύπο \ENG $r = 1 - \frac{check \,\, nodes}{variable \,\, nodes}$ (ο) και τέλος,\GR τον ρυθμό που εμείς επιτυγχάνουμε με την διόρθωση των σφαλμάτων (+). Αυτός ο τελευταίος ρυθμός καθορίζεται από τις μεταβλητές l και r του κώδικα (με δείκτη optimum) και οι οποίες βρίσκονται είτε με την κλασική μέθοδο της βελτιστοποίσης είτε με την μέθοδο που περιλαμβάνει το $r_{avg}$. Προφανώς, επιλέγουμε από τις 2 λύσεις εκείνη που μας δίνει τον υψηλότερο ρυθμό για κάθε συνδυασμό και την απεικονίζουμε με το '+'. Ο ρυθμός, λοιπόν, αυτός στις περισσότερες περιπτώσεις είναι πολύ κοντά στον ιδανικό του Shannon (ποσοστά 85-90 \%). Θα παρατεθούν 2 διαγράμματα, όπου ο Shannon rate θα είναι πάνω από τους άλλους 2 και ο δικός μας θα βρίσκεται πιο κάτω. Στο \hyperref[Diagramme11]{figure 11}, "κοιτάμε" από πάνω για να δούμε ότι όλοι όντως αντιστοιχούν στα ίδια \ENG $l_{max}$ \GR και \ENG $r_{max}$ \GR.
  686. \vspace{6mm}
  687.  
  688. \begin{justify}
  689. \begin{figure}[H]
  690.    \centering
  691.    \includegraphics[scale=0.32]{LDPC/3d2.eps}
  692.    \caption{3D plot of rates (looking above)}
  693.    \label{Diagramme11}
  694. \end{figure}
  695. \vspace{4mm}
  696. \end{justify}
  697. \newpage
  698.  
  699.  
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708.  
  709.  
  710.  
  711.  
  712. \begin{justify}
  713. \begin{figure}[H]
  714.    \centering
  715.    \includegraphics[scale=0.35]{LDPC/3d1.eps}
  716.    \caption{3D plot of rates}
  717.    \label{Diagramme10}
  718. \end{figure}
  719. \vspace{4mm}
  720. \end{justify}
  721.  
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  736. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  737. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  738. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ APPENDICES ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  739. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  740. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  741. \newpage
  742. \phantom{s}
  743. \newpage
  744. \appendices
  745. \section{\ENG Proof of the First Zonklar Equation}
  746. \ENG Appendix one text goes here.
  747.  
  748. % you can choose not to have a title for an appendix
  749. % if you want by leaving the argument blank
  750. \section{}
  751. Appendix two text goes here.
  752.  
  753.  
  754. % use section* for acknowledgment
  755. \section*{Acknowledgment}
  756.  
  757.  
  758. The authors would like to thank...
  759.  
  760.  
  761. % Can use something like this to put references on a page
  762. % by themselves when using endfloat and the captionsoff option.
  763. \ifCLASSOPTIONcaptionsoff
  764.   \newpage
  765. \fi
  766.  
  767.  
  768.  
  769. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  770. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  771. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  772. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~ BIBLIOGRAPHY ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  773. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  774. % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  775.  
  776. \newpage
  777. \begin{thebibliography}{1}
  778.  
  779.    \bibitem{IEEEhowto:kopka}
  780.    H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
  781.      0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
  782.    
  783.    \end{thebibliography}
  784.    
  785.    
  786.    \begin{IEEEbiography}{Θωμάς Μπουφίκος}
  787.    Biography text here.
  788.    \end{IEEEbiography}
  789.    
  790.     % if you will not have a photo at all:
  791.     \begin{IEEEbiographynophoto}{Δημήτριος Σκλαβενίτης}
  792.    Biography text here.
  793.    \end{IEEEbiographynophoto}
  794.    
  795.     % insert where needed to balance the two columns on the last page with
  796.     % biographies
  797.     %\newpage
  798.    
  799.     \begin{IEEEbiographynophoto}{Ράλλης Τσολακίδης}
  800.    Biography text here.
  801.    
  802. \end{IEEEbiographynophoto}
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809.  
  810. \end{document}
  811.  
  812.  
  813.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement