Θεωρία κωδικοποίησης

Η θεωρία κωδικοποίησης είναι η μελέτη των ιδιοτήτων των κωδίκων και της καταλληλότητάς τους για συγκεκριμένες εφαρμογές. Οι κώδικες χρησιμοποιούνται για συμπίεση δεδομένων, κρυπτογραφία, ανίχνευση και διόρθωση σφαλμάτων, μετάδοση και αποθήκευση δεδομένων. Οι κώδικες μελετώνται από διάφορους επιστημονικούς κλάδους, όπως η θεωρία της πληροφορίας, η ηλεκτρολογία, τα μαθηματικά, η γλωσσολογία και η επιστήμη των υπολογιστών, με στόχο τον σχεδιασμό αποδοτικών και αξιόπιστων μεθόδων μετάδοσης δεδομένων. Αυτό περιλαμβάνει συνήθως την εξάλειψη του πλεονασμού και τη διόρθωση ή την ανίχνευση σφαλμάτων στα μεταδιδόμενα δεδομένα.

Υπάρχουν τέσσερις τύποι κωδικοποίησης:^[1]

Συμπίεση δεδομένων (ή κωδικοποίηση πηγής)
Ελεγχος σφαλμάτων (ή κωδικοποίηση καναλιού)
Κρυπτογραφική κωδικοποίηση
Κωδικοποίηση γραμμής

Ο στόχος της συμπίεσης δεδομένων είναι να αφαιρεθεί ο ανεπιθύμητος πλεονασμός στα δεδομένα μιας πηγής, ώστε να μπορούν να μεταδοθούν αποτελεσματικότερα. Για παράδειγμα, η συμπίεση δεδομένων ZIP μπορεί να χρησιμοποιηθεί για τη μείωση του μεγέθους των αρχείων δεδομένων, ιδίως για τη μείωση της κίνησης στο Διαδίκτυο. Η συμπίεση δεδομένων και η διόρθωση σφαλμάτων μπορούν να μελετηθούν μαζί.

Η διόρθωση σφαλμάτων προσθέτει χρήσιμο πλεονασμό στα δεδομένα από μια πηγή για να κάνει τη μετάδοση πιο ανθεκτική στις διαταραχές του καναλιού μετάδοσης. Ο απλός χρήστης μπορεί να μην γνωρίζει τις πολλές εφαρμογές που χρησιμοποιούν τη διόρθωση σφαλμάτων. Ένα τυπικό μουσικό CD χρησιμοποιεί κώδικα Ριντ-Σόλομον για τη διόρθωση των γρατζουνιών και της σκόνης. Σε αυτή την εφαρμογή, το κανάλι μετάδοσης είναι το ίδιο το CD. Τα κινητά τηλέφωνα χρησιμοποιούν επίσης τεχνικές κωδικοποίησης για τη διόρθωση της εξασθένισης και του θορύβου των ραδιοφωνικών μεταδόσεων υψηλής συχνότητας. Τα μόντεμ δεδομένων, οι τηλεφωνικές μεταδόσεις και το βαθύ διαστημικό δίκτυο της NASA χρησιμοποιούν τεχνικές κωδικοποίησης καναλιού για τη μετάδοση των bits, για παράδειγμα turbo-code και κώδικες LDPC.

Ιστορία της θεωρίας κωδικοποίησης

Το 1948, ο Κλοντ Σάνον δημοσίευσε το "A Mathematical Theory of Communication" (Μαθηματική θεωρία της επικοινωνίας), ένα άρθρο σε δύο μέρη στα τεύχη Ιουλίου και Οκτωβρίου του Bell System Technical Journal. Το έργο αυτό επικεντρώνεται στο πρόβλημα του καλύτερου τρόπου κωδικοποίησης των πληροφοριών που θέλει να μεταδώσει ένας αποστολέας. Σε αυτό το θεμελιώδες έργο, χρησιμοποίησε εργαλεία από τη θεωρία πιθανοτήτων, η οποία αναπτύχθηκε από τον Νόρμπερτ Βίνερ, η εφαρμογή της οποίας στη θεωρία της επικοινωνίας βρισκόταν ακόμη στα σπάργανα εκείνη την εποχή. Ο Σάνον ανέπτυξε την εντροπία της πληροφορίας ως μέτρο της αβεβαιότητας ενός μηνύματος και ουσιαστικά εφηύρε τον τομέα της θεωρίας της πληροφορίας.

Ο δυαδικός κώδικας του Γκολέι αναπτύχθηκε το 1949. Είναι ένας κώδικας διόρθωσης σφαλμάτων ικανός να διορθώνει έως και τρία σφάλματα σε κάθε λέξη των 24 bit και να ανιχνεύει ένα τέταρτο.

Ο Ρίτσαρντ Χάμινγκ τιμήθηκε με το βραβείο Τιούρινγκ το 1968 για το έργο του στα εργαστήρια Bell Labs σχετικά με τις ψηφιακές μεθόδους, τα συστήματα αυτόματης κωδικοποίησης και τους κώδικες ανίχνευσης και διόρθωσης σφαλμάτων. Επινόησε τις έννοιες που είναι γνωστές ως κώδικες Χάμινγκ, παράθυρα Χάμινγκ, αριθμοί Χάμινγκ και απόσταση Χάμινγκ.

Το 1972, ο Νασίρ Αχμέντ πρότεινε τον διακριτό μετασχηματισμό συνημιτόνου (DCT), τον οποίο ανέπτυξε μαζί με τους Τ. Ναταρατζάν και Κ. R. Rao το 1973^[2] . Ο DCT είναι ο πιο ευρέως χρησιμοποιούμενος αλγόριθμος συμπίεσης με απώλειες, η βάση των φορμά πολυμέσων όπως τα JPEG, MPEG και MP3.

Κωδικοποίηση πηγής

Στόχος της κωδικοποίησης πηγής είναι η μείωση του μεγέθους των δεδομένων πηγής.

Ορισμός

Τα δεδομένα μπορούν να θεωρηθούν ως μια τυχαία μεταβλητή $X:\Omega \to {\mathcal {X}}$ , όπου $x\in {\mathcal {X}}$ εμφανίζεται με πιθανότητα $\mathbb {P} [X=x]$ .

Τα δεδομένα κωδικοποιούνται με συμβολοσειρές (λέξεις) σε ένα αλφάβητο $\Sigma$ .

Ένας κώδικας είναι μια συνάρτηση

C:{\mathcal {X}}\to \Sigma ^{*}

(ή

\Sigma ^{+}

αν η κενή συμβολοσειρά δεν είναι μέρος του αλφαβήτου).

$C(x)$ είναι η κωδικοποιημένη λέξη που σχετίζεται με $x$ .

Το μήκος της κωδικοποιημένης λέξης γράφεται ως εξής

l(C(x)).

Το αναμενόμενο μήκος ενός κωδικού είναι

l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].

Συνένωση κωδικών λέξεων $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$ .

Η κωδικοποιημένη λέξη της κενής συμβολοσειράς είναι η ίδια η κενή συμβολοσειρά:

C(\epsilon )=\epsilon

Ιδιότητες

$C:{\mathcal {X}}\to \Sigma ^{*}$ είναι μη δακτυλιοειδής αν είναι Ένα προς ένα.
$C:{\mathcal {X}}^{*}\to \Sigma ^{*}$ είναι μονοσήμαντα αποκωδικοποιήσιμη αν είναι Ένα προς ένα.
$C:{\mathcal {X}}\to \Sigma ^{*}$ είναι στιγμιαία εάν $C(x_{1})$ iδεν είναι πρόθεμα του $C(x_{2})$ (και αντιστρόφως).

Αρχή

Η εντροπία μιας πηγής είναι το μέτρο της πληροφορίας. Βασικά, οι κώδικες πηγής προσπαθούν να μειώσουν τον πλεονασμό που υπάρχει στην πηγή και να αναπαραστήσουν την πηγή με λιγότερα μπιτ που μεταφέρουν περισσότερη πληροφορία.

Η συμπίεση δεδομένων που προσπαθεί ρητά να ελαχιστοποιήσει το μέσο μήκος του μηνύματος σύμφωνα με ένα συγκεκριμένο μοντέλο πιθανότητας ονομάζεται κωδικοποίηση εντροπίας.

Διάφορες τεχνικές που χρησιμοποιούνται από συστήματα κωδικοποίησης πηγής προσπαθούν να επιτύχουν το όριο της εντροπίας της πηγής. C(x) ≥ H(x), όπου H(x) είναι η εντροπία της πηγής (bitrate) και C(x) είναι το bitrate μετά τη συμπίεση. Ειδικότερα, κανένα σύστημα κωδικοποίησης πηγής δεν μπορεί να είναι καλύτερο από την εντροπία της πηγής.

Κωδικοποίηση καναλιού

Κύριο άρθρο: Ανίχνευση και διόρθωση σφαλμάτων

Ο σκοπός της θεωρίας κωδικοποίησης καναλιών είναι να βρεθούν κώδικες που μεταδίδουν γρήγορα, περιέχουν πολλές έγκυρες κωδικές λέξεις και διορθώνουν ή τουλάχιστον ανιχνεύουν πολλά σφάλματα. Αν και δεν αποκλείουν η μία την άλλη, η απόδοση σε αυτούς τους τομείς είναι ένας συμβιβασμός. Έτσι, διαφορετικοί κώδικες είναι βέλτιστοι για διαφορετικές εφαρμογές. Οι αναγκαίες ιδιότητες του κώδικα εξαρτώνται κυρίως από την πιθανότητα εμφάνισης σφαλμάτων κατά τη μετάδοση. Σε ένα τυπικό CD, η βλάβη είναι κυρίως η σκόνη ή οι γρατσουνιές.

Τα CD χρησιμοποιούν κωδικοποίηση Reed-Solomon με διασταυρούμενη παρεμβολή για την κατανομή των δεδομένων στο δίσκο^[3].

Παρόλο που δεν είναι ένας πολύ καλός κώδικας, ένας απλός κώδικας επανάληψης μπορεί να χρησιμεύσει ως κατανοητό παράδειγμα. Ας υποθέσουμε ότι παίρνουμε ένα μπλοκ από μπιτ δεδομένων (που αντιπροσωπεύουν τον ήχο) και το στέλνουμε τρεις φορές. Στο τέλος του δέκτη, θα εξετάσουμε τις τρεις επαναλήψεις μπιτ προς μπιτ και θα πάρουμε μια πλειοψηφική απόφαση. Το ιδιαίτερο είναι ότι δεν στέλνουμε απλώς τα μπιτ με τη σειρά. Τα παρεμβάλλουμε μεταξύ τους. Το μπλοκ των μπιτ δεδομένων χωρίζεται πρώτα σε τέσσερα μικρότερα μπλοκ. Στη συνέχεια, περνάμε μέσα από το μπλοκ και στέλνουμε ένα bit από το πρώτο, μετά από το δεύτερο κ.ο.κ. Το κάνουμε αυτό τρεις φορές για να απλώσουμε τα δεδομένα σε ολόκληρη την επιφάνεια του δίσκου. Στο πλαίσιο του απλού κώδικα επανάληψης, αυτό μπορεί να φαίνεται αναποτελεσματικό. Ωστόσο, υπάρχουν πιο ισχυροί κώδικες που είναι πολύ αποτελεσματικοί στη διόρθωση του σφάλματος "έκρηξης" μιας γρατσουνιάς ή ενός σημείου σκόνης όταν χρησιμοποιείται αυτή η τεχνική παρεμβολής.

Άλλοι κώδικες είναι πιο κατάλληλοι για διαφορετικές εφαρμογές. Οι επικοινωνίες στο βαθύ διάστημα περιορίζονται από τον θερμικό θόρυβο του δέκτη, ο οποίος είναι περισσότερο συνεχής παρά εκρηκτικός. Παρομοίως, τα μόντεμ στενής ζώνης περιορίζονται από το θόρυβο, που υπάρχει στο τηλεφωνικό δίκτυο και επίσης μοντελοποιείται καλύτερα ως συνεχής διαταραχή. Τα κινητά τηλέφωνα υπόκεινται σε ταχεία εξασθένιση. Οι υψηλές συχνότητες που χρησιμοποιούνται μπορούν να προκαλέσουν ταχεία εξασθένιση του σήματος, ακόμη και αν ο δέκτης μετακινηθεί μερικά εκατοστά. Και πάλι, υπάρχει μια κατηγορία κωδικών καναλιού που έχουν σχεδιαστεί για την καταπολέμηση της εξασθένισης.

Γραμμικοί κώδικες

Ο όρος αλγεβρική θεωρία κωδικοποίησης αναφέρεται στο υποπεδίο της θεωρίας κωδικοποίησης στο οποίο οι ιδιότητες των κωδικών εκφράζονται με αλγεβρικούς όρους και στη συνέχεια αποτελούν αντικείμενο περαιτέρω έρευνας.

Η αλγεβρική θεωρία κωδικοποίησης χωρίζεται ουσιαστικά σε δύο κύριους τύπους κωδίκων:

Γραμμικοί μπλοκ κώδικες
υνελικτικοί κώδικες.

Αναλύει τις ακόλουθες τρεις ιδιότητες ενός κώδικα - κυρίως :

Μήκος λέξης κώδικα
Ο συνολικός αριθμός των έγκυρων κωδικών λέξεων
Η ελάχιστη απόσταση μεταξύ δύο έγκυρων κωδικών λέξεων, χρησιμοποιώντας κυρίως την απόσταση Χάμινγκ, αλλά μερικές φορές και άλλες αποστάσεις, όπως η απόσταση Lee.

Γραμμικοί κώδικες μπλοκ

Οι γραμμικοί μπλοκ κώδικες έχουν την ιδιότητα της γραμμικότητας, δηλαδή το άθροισμα δύο οποιωνδήποτε κωδικών λέξεων είναι επίσης μια κωδική λέξη, και εφαρμόζονται στα bits της πηγής σε μπλοκ, εξ ου και η ονομασία γραμμικοί μπλοκ κώδικες. Υπάρχουν μπλοκ κώδικες που δεν είναι γραμμικοί, αλλά είναι δύσκολο να αποδειχθεί ότι ένας κώδικας είναι καλός χωρίς αυτή την ιδιότητα^[4].

Οι γραμμικοί μπλοκ κώδικες συνοψίζονται από το αλφάβητο των συμβόλων τους (π.χ. δυαδικό ή τριμερές) και τις παραμέτρους (n,m,d_min)^[5] όπου

n είναι το μήκος της κωδικής λέξης, σε σύμβολα,
m είναι ο αριθμός των συμβόλων πηγής που θα χρησιμοποιηθούν για την κωδικοποίηση ταυτόχρονα,
d_min είναι η ελάχιστη απόσταση Χάμινγκ για τον κώδικα.

Υπάρχουν πολλοί τύποι γραμμικών κωδίκων μπλοκ, όπως:

Κυκλικοί κώδικες (π.χ. κώδικες Χάμινγκ)
Κώδικες επανάληψης
Κώδικες διαίρεσης
Πολυωνυμικοί κώδικες (π.χ. κώδικες BCH)
Κώδικες Reed-Solomon
Αλγεβρικοί γεωμετρικοί κώδικες
Κώδικες Reed-Muller
Perfect codes

Οι κώδικες μπλοκ συνδέονται με το πρόβλημα της συσκευασίας σφαιρών, το οποίο απασχόλησε αρκετά τα τελευταία χρόνια. Σε δύο διαστάσεις, είναι εύκολο να το απεικονίσουμε. Πάρτε μια στοίβα από νομίσματα απλωμένη στο τραπέζι και σπρώξτε τα όλα μαζί. Το αποτέλεσμα είναι ένα εξαγωνικό μοτίβο παρόμοιο με μια κηρήθρα. Όμως οι μπλοκ κώδικες βασίζονται σε άλλες διαστάσεις που δεν είναι εύκολο να οπτικοποιηθούν. Ο ισχυρός κώδικας Γκολέ (24,12) που χρησιμοποιείται για τις επικοινωνίες στο βαθύ διάστημα αποτελείται από 24 διαστάσεις. Εάν χρησιμοποιείται ως δυαδικός κώδικας (που είναι γενικά η περίπτωση), οι διαστάσεις αναφέρονται στο μήκος της κωδικής λέξης, όπως ορίζεται παραπάνω.

Η θεωρία κωδικοποίησης χρησιμοποιεί το μοντέλο της σφαίρας Ν-διαστάσεων. Για παράδειγμα, πόσα κέρματα μπορούν να στριμωχτούν σε έναν κύκλο πάνω σε ένα τραπέζι ή, σε τρεις διαστάσεις, πόσες μπίλιες μπορούν να στριμωχτούν σε μια σφαίρα. Κατά την επιλογή ενός κώδικα υπεισέρχονται και άλλες εκτιμήσεις. Για παράδειγμα, η τοποθέτηση ενός εξαγώνου σε ένα ορθογώνιο κουτί θα αφήσει κενό χώρο στις γωνίες. Καθώς αυξάνονται οι διαστάσεις, το ποσοστό του κενού χώρου μειώνεται. Αλλά σε ορισμένες διαστάσεις, η συσκευασία χρησιμοποιεί όλο το χώρο και αυτοί οι κωδικοί είναι γνωστοί ως "τέλειοι" κωδικοί. Οι μόνοι χρήσιμοι μη τετριμμένοι τέλειοι κώδικες είναι οι κώδικες Χάμινγκ 3 αποστάσεων με ικανοποιητικές παραμέτρους (2^r – 1, 2^r – 1 – r, 3) και οι δυαδικοί [23,12,7] και τριμερείς [11,6,5] κώδικες Γκολέ^[4]^[5].

Μια άλλη ιδιότητα του κώδικα είναι ο αριθμός των γειτόνων που μπορεί να έχει μια κωδική λέξη^[6]. Ας πάρουμε πάλι το παράδειγμα των κερμάτων. Αρχικά, τοποθετούμε τα κέρματα σε ένα ορθογώνιο πλέγμα. Κάθε κέρμα θα έχει 4 κοντινούς γείτονες (και 4 στις γωνίες, που είναι πιο μακριά). Σε ένα εξάγωνο, κάθε κέρμα θα έχει 6 κοντινότερους γείτονες. Καθώς αυξάνονται οι διαστάσεις, ο αριθμός των πλησιέστερων γειτόνων αυξάνεται πολύ γρήγορα. Ως αποτέλεσμα, αυξάνεται επίσης ο αριθμός των τρόπων με τους οποίους ο θόρυβος μπορεί να προκαλέσει τον δέκτη να επιλέξει έναν γείτονα (και επομένως να κάνει σφάλμα). Αυτός είναι ένας θεμελιώδης περιορισμός των κωδίκων μπλοκ, και μάλιστα όλων των κωδίκων. Μπορεί να είναι πιο δύσκολο να προκληθεί σφάλμα σε έναν μόνο γείτονα, αλλά ο αριθμός των γειτόνων μπορεί να είναι αρκετά μεγάλος ώστε να υποφέρει η συνολική πιθανότητα σφάλματος^[6].

Οι ιδιότητες των γραμμικών μπλοκ κωδίκων χρησιμοποιούνται σε πολλές εφαρμογές. Για παράδειγµα, η ιδιότητα της µοναδικότητας του συνδρόµου-κοσέτου των γραµµικών κωδίκων µπλοκ χρησιµοποιείται στη διαµόρφωση πλέγµατος^[7], έναν από τους πιο γνωστούς κώδικες διαµόρφωσης.

Συνελικτικοί κώδικες

Η ιδέα ενός συνελικτικού κώδικα είναι να κάνει κάθε σύμβολο κωδικής λέξης το σταθμισμένο άθροισμα των διαφόρων συμβόλων μηνύματος εισόδου. Αυτό είναι παρόμοιο με τη συνέλιξη που χρησιμοποιείται στα συστήματα LTI για την εύρεση της εξόδου ενός συστήματος, όταν γνωρίζουμε την είσοδο και την κρουστική απόκριση.

Έτσι, γενικά βρίσκουμε την έξοδο του συνελικτικού κωδικοποιητή του συστήματος, η οποία είναι η συνέλιξη του μπιτ εισόδου σε σχέση με τις καταστάσεις του συνελικτικού κωδικοποιητή, τους καταχωρητές.

Βασικά, οι συνελικτικοί κώδικες δεν προσφέρουν περισσότερη προστασία έναντι του θορύβου από έναν ισοδύναμο κώδικα μπλοκ. Σε πολλές περιπτώσεις, είναι γενικά απλούστεροι στην υλοποίησή τους από έναν κώδικα μπλοκ της ίδιας ισχύος. Ο κωδικοποιητής είναι συνήθως ένα απλό κύκλωμα με μνήμη καταστάσεων και λογική ανατροφοδότησης, συνήθως πύλες XOR. Ο αποκωδικοποιητής μπορεί να υλοποιηθεί σε λογισμικό ή υλικολογισμικό.

Ο αλγόριθμος Βιτέρμπι είναι ο βέλτιστος αλγόριθμος που χρησιμοποιείται για την αποκωδικοποίηση συνελικτικών κωδίκων. Υπάρχουν απλουστεύσεις για τη μείωση του υπολογιστικού φόρτου. Βασίζονται στην αναζήτηση των πιο πιθανών διαδρομών. Αν και δεν είναι βέλτιστοι, δίνουν γενικά καλά αποτελέσματα σε περιβάλλοντα χαμηλού θορύβου.

Οι συνελικτικοί κώδικες χρησιμοποιούνται σε μόντεμ φωνητικής ζώνης (V.32, V.17, V.34) και κινητά τηλέφωνα GSM, καθώς και σε δορυφορικές και στρατιωτικές συσκευές επικοινωνίας.

Κρυπτογραφική κωδικοποίηση

Η κρυπτογραφία ή κρυπτογραφική κωδικοποίηση είναι η πρακτική και η μελέτη των τεχνικών ασφαλούς επικοινωνίας με την παρουσία τρίτων (που ονομάζονται αντίπαλοι)^[8]. Γενικότερα, περιλαμβάνει την κατασκευή και την ανάλυση πρωτοκόλλων που εμποδίζουν τους αντιπάλους^[9]- διάφορες πτυχές της ασφάλειας των πληροφοριών, όπως η εμπιστευτικότητα των δεδομένων, η ακεραιότητα των δεδομένων, η αυθεντικοποίηση και η μη άρνηση^[10], βρίσκονται στο επίκεντρο της σύγχρονης κρυπτογραφίας. Η σύγχρονη κρυπτογραφία βρίσκεται στη διασταύρωση των κλάδων των μαθηματικών, της επιστήμης των υπολογιστών και της ηλεκτρολογίας. Οι εφαρμογές της κρυπτογραφίας περιλαμβάνουν τραπεζικές κάρτες, κωδικούς πρόσβασης σε υπολογιστές και το ηλεκτρονικό εμπόριο.

Πριν από τη σύγχρονη εποχή, η κρυπτογραφία ήταν στην πραγματικότητα συνώνυμο της κρυπτογράφησης, δηλαδή της μετατροπής των πληροφοριών από μια αναγνώσιμη κατάσταση σε μια σε μια μη ανιχνεύσιμη κατάσταση. Ο συγγραφέας ενός κρυπτογραφημένου μηνύματος μοιραζόταν μόνο την τεχνική αποκωδικοποίησης που χρειαζόταν για την ανάκτηση της αρχικής πληροφορίας με τους προβλεπόμενους παραλήπτες, εμποδίζοντας έτσι ανεπιθύμητους ανθρώπους να κάνουν το ίδιο. Μετά τον Πρώτο Παγκόσμιο Πόλεμο και την έλευση του υπολογιστή, οι μέθοδοι που χρησιμοποιούνται για την επίτευξη της κρυπτογραφίας έγιναν όλο και πιο πολύπλοκες και η εφαρμογή της πιο διαδεδομένη.

Η σύγχρονη κρυπτογραφία βασίζεται σε μεγάλο βαθμό στη μαθηματική θεωρία και στην πρακτική των υπολογιστών- οι κρυπτογραφικοί αλγόριθμοι σχεδιάζονται με βάση υποθέσεις υπολογιστικής σκληρότητας, γεγονός που καθιστά δύσκολη την παραβίασή τους στην πράξη από οποιονδήποτε αντίπαλο. Είναι θεωρητικά δυνατό να σπάσει ένα τέτοιο σύστημα, αλλά είναι αδύνατο να γίνει με τα γνωστά πρακτικά μέσα. Οι θεωρητικές εξελίξεις, όπως η βελτίωση των αλγορίθμων παραγοντοποίησης ακεραίων αριθμών, και η επιτάχυνση της τεχνολογίας των υπολογιστών σημαίνουν ότι οι λύσεις αυτές πρέπει να προσαρμόζονται συνεχώς. Υπάρχουν θεωρητικά πληροφοριακά ασφαλή συστήματα που σαφώς δεν μπορούν να παραβιαστούν, ακόμη και με απεριόριστη υπολογιστική ισχύ (π.χ. ο απομονωτής μιας χρήσης), αλλά τα συστήματα αυτά είναι πιο δύσκολο να εφαρμοστούν από τους καλύτερους θεωρητικά παραβιάσιμους αλλά υπολογιστικά ασφαλείς μηχανισμούς.

Γραμμικός κώδικας

Ο γραμμικός κώδικας (που ονομάζεται επίσης ψηφιακή διαμόρφωση βασικής ζώνης ή ψηφιακή μέθοδος μετάδοσης βασικής ζώνης) είναι ένας κώδικας που επιλέγεται για χρήση σε ένα σύστημα επικοινωνίας για μετάδοση βασικής ζώνης. Η κωδικοποίηση γραμμής χρησιμοποιείται συχνά για τη μεταφορά ψηφιακών δεδομένων.

Η γραμμική κωδικοποίηση συνίσταται στην αναπαράσταση του ψηφιακού σήματος που πρόκειται να μεταφερθεί με ένα διακριτό σήμα σε πλάτος και χρόνο, βέλτιστα προσαρμοσμένο στις ειδικές ιδιότητες του φυσικού καναλιού (και του εξοπλισμού λήψης). Η κυματομορφή τάσης ή ρεύματος που χρησιμοποιείται για την αναπαράσταση των 1s και 0s των ψηφιακών δεδομένων σε μια ζεύξη μετάδοσης ονομάζεται κωδικοποίηση γραμμής. Οι συνήθεις τύποι κωδικοποίησης γραμμής είναι ο μονοπολικός, ο πολικός, ο διπολικός και ο Μάντσεστερ.

Νευρωνική κωδικοποίηση

Η νευρωνική κωδικοποίηση είναι ένας τομέας της νευροεπιστήμης που ασχολείται με τον τρόπο με τον οποίο οι αισθητηριακές και άλλες πληροφορίες αναπαρίστανται στον εγκέφαλο από δίκτυα νευρώνων. Ο κύριος στόχος της μελέτης της νευρωνικής κωδικοποίησης είναι να χαρακτηριστεί η σχέση μεταξύ του ερεθίσματος και των ατομικών ή συνολικών νευρωνικών αποκρίσεων, καθώς και η σχέση μεταξύ της ηλεκτρικής δραστηριότητας των νευρώνων του συνόλου^[11]. Θεωρείται ότι οι νευρώνες μπορούν να κωδικοποιήσουν τόσο ψηφιακή όσο και αναλογική πληροφορία^[12], ότι ακολουθούν τις αρχές της θεωρίας της πληροφορίας και συμπιέζουν την πληροφορία^[13] και ότι ανιχνεύουν και διορθώνουν^[14] σφάλματα στα σήματα που αποστέλλονται μέσω του εγκεφάλου και του ευρύτερου νευρικού συστήματος.

Δημοσιεύσεις

Mac Lane, Saunders; Birkhoff, Garrett (1999), Algebra (2nd έκδοση), AMS Chelsea, ISBN 978-0-8218-1646-2
Michel, Anthony N.; Herget, Charles J. (1993), Applied Algebra and Functional Analysis, New York: Dover Publications, ISBN 978-0-486-67598-5
Burris, Stanley N.; Sankappanavar, H. P. (1981), A Course in Universal Algebra, Berlin, New York: Springer-Verlag, ISBN 978-3-540-90578-3, http://www.thoralf.uwaterloo.ca/htdocs/ualg.html

Θεωρία κατηγοριών

Mac Lane, Saunders (1998), Categories for the Working Mathematician (2nd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-98403-2
Taylor, Paul (1999), Practical foundations of mathematics, Cambridge University Press, ISBN 978-0-521-63107-5

Παραπομπές

↑ James Irvine· David Harle (2002). «2.4.4 Types of Coding». Data Communications and Networks. σελ. 18. ISBN 9780471808725. There are four types of coding
↑ Nasir Ahmed. «How I Came Up With the Discrete Cosine Transform». Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.
↑ Todd Campbell. "Answer Geek: Error Correction Rule CDs".
↑ ^4,0 ^4,1 Terras, Audrey (1999). Fourier Analysis on Finite Groups and Applications. Cambridge University Press. σελ. 195. ISBN 978-0-521-45718-7.
↑ ^5,0 ^5,1 Blahut, Richard E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. ISBN 978-0-521-55374-2.
↑ ^6,0 ^6,1 Christian Schlegel· Lance Pérez (2004). Trellis and turbo coding. Wiley-IEEE. σελ. 73. ISBN 978-0-471-22755-7.
↑ Forney, G.D. Jr. (March 1992). «Trellis shaping». IEEE Transactions on Information Theory 38 (2 Pt 2): 281–300. doi:10.1109/18.119687.
↑ Rivest, Ronald L. (1990). «Cryptology». Στο: J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. Elsevier.
↑ Bellare, Mihir· Rogaway, Phillip (21 Σεπτεμβρίου 2005). «Introduction». Introduction to Modern Cryptography. σελ. 10.
↑ Menezes, A. J.· van Oorschot, P. C.· Vanstone, S. A. (1997). Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0.
↑ «Multiple neural spike train data analysis: state-of-the-art and future challenges». Nature Neuroscience 7 (5): 456–461. May 2004. doi:10.1038/nn1228. PMID 15114358. http://www.stat.columbia.edu/~liam//teaching/neurostat-fall13/papers/brown-et-al/brown-kass-mitra.pdf.
↑ Thorpe, S.J. (1990). «Spike arrival times: A highly efficient coding scheme for neural networks» (PDF). Στο: Eckmiller, R.· Hartmann, G.· Hauske, G. Parallel processing in neural systems and computers (PDF). North-Holland. σελίδες 91–94. ISBN 978-0-444-88390-2. Ανακτήθηκε στις 30 Ιουνίου 2013.
↑ Gedeon, T.; Parker, A.E.; Dimitrov, A.G. (Spring 2002). «Information Distortion and Neural Coding». Canadian Applied Mathematics Quarterly 10 (1): 10. Αρχειοθετήθηκε από το πρωτότυπο στις 2016-11-17. https://web.archive.org/web/20161117220131/http://www.math.ualberta.ca/ami/CAMQ/table_of_content/vol_10/10_1c.htm. Ανακτήθηκε στις 2023-07-06.
↑ Stiber, M. (July 2005). «Spike timing precision and neural error correction: local behavior». Neural Computation 17 (7): 1577–1601. doi:10.1162/0899766053723069. PMID 15901408.

[1] James Irvine· David Harle (2002). «2.4.4 Types of Coding». Data Communications and Networks. σελ. 18. ISBN 9780471808725. There are four types of coding

[Ahmed-2] Nasir Ahmed. «How I Came Up With the Discrete Cosine Transform». Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.

[3] Todd Campbell. "Answer Geek: Error Correction Rule CDs".

[terras-4] 4,0 ^4,1 Terras, Audrey (1999). Fourier Analysis on Finite Groups and Applications. Cambridge University Press. σελ. 195. ISBN 978-0-521-45718-7.

[blahut-5] 5,0 ^5,1 Blahut, Richard E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. ISBN 978-0-521-55374-2.

[schlegel-6] 6,0 ^6,1 Christian Schlegel· Lance Pérez (2004). Trellis and turbo coding. Wiley-IEEE. σελ. 73. ISBN 978-0-471-22755-7.

[7] Forney, G.D. Jr. (March 1992). «Trellis shaping». IEEE Transactions on Information Theory 38 (2 Pt 2): 281–300. doi:10.1109/18.119687.

[rivest90-8] Rivest, Ronald L. (1990). «Cryptology». Στο: J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. Elsevier.

[modern-crypto-9] Bellare, Mihir· Rogaway, Phillip (21 Σεπτεμβρίου 2005). «Introduction». Introduction to Modern Cryptography. σελ. 10.

[hac-10] Menezes, A. J.· van Oorschot, P. C.· Vanstone, S. A. (1997). Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0.

[Brown-11] «Multiple neural spike train data analysis: state-of-the-art and future challenges». Nature Neuroscience 7 (5): 456–461. May 2004. doi:10.1038/nn1228. PMID 15114358. http://www.stat.columbia.edu/~liam//teaching/neurostat-fall13/papers/brown-et-al/brown-kass-mitra.pdf.

[12] Thorpe, S.J. (1990). «Spike arrival times: A highly efficient coding scheme for neural networks» (PDF). Στο: Eckmiller, R.· Hartmann, G.· Hauske, G. Parallel processing in neural systems and computers (PDF). North-Holland. σελίδες 91–94. ISBN 978-0-444-88390-2. Ανακτήθηκε στις 30 Ιουνίου 2013.

[13] Gedeon, T.; Parker, A.E.; Dimitrov, A.G. (Spring 2002). «Information Distortion and Neural Coding». Canadian Applied Mathematics Quarterly 10 (1): 10. Αρχειοθετήθηκε από το πρωτότυπο στις 2016-11-17. https://web.archive.org/web/20161117220131/http://www.math.ualberta.ca/ami/CAMQ/table_of_content/vol_10/10_1c.htm. Ανακτήθηκε στις 2023-07-06.

[14] Stiber, M. (July 2005). «Spike timing precision and neural error correction: local behavior». Neural Computation 17 (7): 1577–1601. doi:10.1162/0899766053723069. PMID 15901408.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]