TeiSerron.gr
Σχολή Μηχανικών => 6ο & 7ο Εξάμηνο (Μηχανικοί Δικτύων) => Τμήμα Μηχανικών Πληροφορικής, Υπολογιστών & Τηλεπικοινωνιών => Ασφάλεια & Διαχείριση Δικτύων (πρώην Δίκτυα Υπολογιστών III) => Μήνυμα ξεκίνησε από: Xaeron στις 05 Φεβρουαρίου 2010, 21:32
-
Έχει κανείς σημειώσεις με κανένα ολοκληρωμένο παράδειγμα του αλγορίθμου CRC, εκτός από τις σημειώσεις/διαφάνειες του κ. Χειλά; Η έστω λυμένη την άσκηση που έχει ο κ. Χειλας. ??? ??? Please, βοήθεια...! :(
(http://www.dnamag.gr/UserFiles/Image/Articles/provlimatismoi/foumara/help.jpg)
-
Ολοκληρωμένο παράδειγμα αλγορίθμου CRC.
/**********************************************************************
*
* Filename: crc.c
*
* Description: A table-driven implementation of CRC-CCITT checksums.
*
* Notes: Some of the constants in this file are specific to
* Arcom's Target188EB hardware.
*
* This code can be easily modified to implement any
* "non-reflective" CRC algorithm. Simply change the
* constants POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR,
* and--if an 8 or 32-bit CRC is required--the definition
* of type 'width'.
*
*
* Copyright (c) 1998 by Michael Barr. This software is placed into
* the public domain and may be used for any purpose. However, this
* notice must not be changed or removed and no warranty is either
* expressed or implied by its publication or distribution.
**********************************************************************/
#include <string.h>
#include "led.h"
/*
* The CRC parameters. Currently configured for CCITT.
* Simply modify these to switch to another CRC standard.
*/
#define POLYNOMIAL 0x1021
#define INITIAL_REMAINDER 0xFFFF
#define FINAL_XOR_VALUE 0x0000
/*
* The width of the CRC calculation and result.
* Modify the typedef for an 8 or 32-bit CRC standard.
*/
typedef unsigned short width;
#define WIDTH (8 * sizeof(width))
#define TOPBIT (1 << (WIDTH - 1))
/*
* An array containing the pre-computed intermediate result for each
* possible byte of input. This is used to speed up the computation.
*/
width crcTable[256];
/**********************************************************************
*
* Function: crcInit()
*
* Description: Initialize the CRC lookup table. This table is used
* by crcCompute() to make CRC computation faster.
*
* Notes: The mod-2 binary long division is implemented here.
*
* Returns: None defined.
*
**********************************************************************/
void
crcInit(void)
{
width remainder;
width dividend;
int bit;
/*
* Perform binary long division, a bit at a time.
*/
for (dividend = 0; dividend < 256; dividend++)
{
/*
* Initialize the remainder.
*/
remainder = dividend << (WIDTH - 8);
/*
* Shift and XOR with the polynomial.
*/
for (bit = 0; bit < 8; bit++)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = remainder << 1;
}
}
/*
* Save the result in the table.
*/
crcTable[dividend] = remainder;
}
} /* crcInit() */
/**********************************************************************
*
* Function: crcCompute()
*
* Description: Compute the CRC checksum of a binary message block.
*
* Notes: This function expects that crcInit() has been called
* first to initialize the CRC lookup table.
*
* Returns: The CRC of the data.
*
**********************************************************************/
width
crcCompute(unsigned char * message, unsigned int nBytes)
{
unsigned int offset;
unsigned char byte;
width remainder = INITIAL_REMAINDER;
/*
* Divide the message by the polynomial, a byte at time.
*/
for (offset = 0; offset < nBytes; offset++)
{
byte = (remainder >> (WIDTH - 8)) ^ message[offset];
remainder = crcTable[byte] ^ (remainder << 8);
}
/*
* The final remainder is the CRC result.
*/
return (remainder ^ FINAL_XOR_VALUE);
} /* crcCompute() */
/**********************************************************************
*
* Function: main()
*
* Description: Test the CRC functions by computing the CRC-CCITT of
* the check string "123456789". The expected result
* was provided by an independent third-party.
*
* Notes:
*
* Returns: 0 on success.
* Otherwise -1 indicates failure.
*
**********************************************************************/
main()
{
#define CCITT_CHECK 0x29B1
char * s = "123456789";
/*
* Initialize the CRC lookup table.
*/
crcInit();
/*
* Compute the CRC of the check string.
*/
if (crcCompute(s, strlen(s)) != CCITT_CHECK)
{
toggleLed(LED_RED);
return (-1);
}
else
{
toggleLed(LED_GREEN);
return (0);
}
} /* main() */
-
Ευχαριστώ αλλά δεν θέλω τον κώδικα...
-
... ολοκληρωμένο παράδειγμα του αλγορίθμου CRC ...
Τι ακριβώς θέλεις?
-
Ένα ολοκληρωμένο παράδειγμα όπως αυτό που έχει στις διαφάνειες του κ. Χειλά.
-
Τελικά εννοούσες παράδειγμα από τις σημειώσεις του Χειλά.
ΟΚ. Δεν το έχω παρακολουθήσει γιατί τώρα μπαίνω στο 6 εξάμηνο.
Πάντως θεωρώ πως αυτό το παράδειγμα είναι κατατοπιστικότατο.
Για να βρεις και σχετική θεωρία από αυτό σου προτείνω να διαβάσεις το ανάλογο κεφάλαιο του βιβλίου:
http://oreilly.com/catalog/9781565923546
-
Είναι πολύ εύκολο... Σου δίνεται:
-> ένα μήνυμα σε ακολουθία από 0 και 1, π.χ. 1100101
-> και ένας γεννήτορας
- είτε σε ακολουθία από 0 και 1 πάλι, δλδ 110011,
- είτε στη μορφή G(x)=x^5 + x^4 + x + 1
(το G(x)=x^5 + x^4 + x + 1 ισούται με το 110011, νομίζω είναι προφανές πώς προκύπτει, όπου έχουμε όρο βάζουμε 1 όπου λείπει, όπως πχ στις δυνάμεις του 2 και του 3, τότε βάζουμε 0)
Άρα με τα 2 αυτά δεδομένα κάνεις τα εξής:
1. Προσθέτεις στο τέλος του μηνύματος που θέλεις να μεταδώσεις μηδενικά (Πόσα μηδενικα? Όσο ο αριθμός των ψηφίων του γεννήτορα μείον 1)
2. Διαιρείς το μήνυμα που προκύπτει (μήνυμα προς μετάδοση ακολουθούμνενο από τα απαραίτητα 0) με τον γεννήτορα
3. Παίρνεις το υπόλοιπο της διαίρεσης και το προσθέτεις στο μήνυμα προς μετάδοση (το αρχικό μήνυμα ΧΩΡΙΣ τα μηδενικά που προσθέσαμε για τη διαίρεση)
4. Άρα το μήνυμα που αποστέλλεται τελικά είναι το αρχικό μήνυμα που μας δόθηκε ακολουθούμενο από το υπόλοιπο της διαίρεσης
5. Ο παραλήπτης παίρνει το μήνυμα αυτό και το διαιρεί με τον γεννήτορα, αν το υπόλοιπο της διαίρεσης βγει 0 τότε έχει λάβει το σωστό μήνυμα, αν βγει διάφορο του μηδενός, το μήνυμα έχει σφάλμα.
*Σημείωση1: Η διαίρεση είναι ουσιαστικά XOR (στο XOR όταν έχεις όμοια ψηφία το αποτέλεσμα είναι 0 ενώ αν είναι διαφορετικά το αποτέλεσμα είναι 1)
*Σημείωση2: Αν στη διαίρεση το πρώτο ψηφίο είναι 0 τότε ΔΕ διαιρούμε με το πολυώνυμο γεννήτορα αλλά με ακολουθία από μηδενικά.
Π.Χ.
Έστω ότι ο αποστολέας θέλει να μεταδώσει το μήνυμα 1100101 με γεννήτορα G(x) = x^3 + x + 1, ποιο είναι το μήνυμα που θα αποσταλεί τελικά?
Το πολυώνυμο του γεννήτορα ισούται με 1011 και έχει σύνολο 4 ψηφία.
Άρα εμείς στο αρχικό μας μήνυμα θα προσθέσουμε 3 μηδενικά και θα προκύψει το 1100101000
Διαιρούμε ως εξής:
1 1 0 0 1 0 1 0 0 0 | 1 0 1 1
1 0 1 1
_______
0 1 1 1 1 (το υπόλοιπο της διαίρεσης/XOR είναι το 0111 και κατεβάζουμε και τον άσσο)
1 0 1 1
_________
0 1 0 0 0
1 0 1 1
_________
0 0 1 1 1 (ΠΡΟΣΟΧΗ το υπόλοιπο είναι 0011, κατεβάζουμε και έναν άσσο και θα κάναμε XOR
0 0 0 0 το 0111 με το 1011 ΑΛΛΑ το 0111 ξεκινάει με 0 άρα θα κάνουμε ΧΟR με μηδενικά!!!)
__________
0 1 1 1 0
1 0 1 1
_________
0 1 0 1 0
1 0 1 1
_________
0 0 0 1 0 (Προσοχή και εδώ έχουμε 0 άρα διαιρούμε με μηδέν! Ουσιάστικά μας ενδιαφέρει
0 0 0 0 το 2ο ψηφίο από το υπόλοιπο, στην προκειμένη περίπτωση είναι το 0001)
__________
0 0 1 0
Άρα προκύπτει το υπόλοιπο 0010, άρα το μήνυμα που θα αποστείλουμε θα είναι το 1100101010
Ο παραλήπτης θα κάνει την διαίρεση με τον ίδιο ακριβώς τρόπο διαιρώντας το μήνυμα που στάλθηκε (και παρέλαβε), δλδ το 1100101010 με τον γεννήτορα 1011. Το υπόλοιπο της διαίρεσης θα πρέπει να βγει 0.
Αν προκύψει σφάλμα και ο παραλήπτης λάβει μήνυμα διαφορετικό από αυτό που στάλθηκε τότε η διαίρεση με τον γεννήτορα ΔΕ θα δώσει 0.
-
differentreality, σε ευχαριστώ πάρα πολύ! Ήσουν αρκετά κατανοητή!
-
no prob ;) αλλα κοίτα να σκίσεις στο μάθημα ε :p
-
παιδιά στα θέματα θεωρίας "σε περίπτωση που αλλοιωθούν κάποια bits απο την ακολουθία του μηνύματος ποιο θα ειναι το αποτέλεσμα της διαίρεσης" πως απαντάμε;
-
Έχει απαντηθεί 2 ποστ πάνω!
Αλλοίωση bit = λήψη στον παραλήπτη διαφορετικού μηνύματος από αυτό που στάλθηκε
"Αν προκύψει σφάλμα και ο παραλήπτης λάβει μήνυμα διαφορετικό από αυτό που στάλθηκε τότε η διαίρεση με τον γεννήτορα ΔΕ θα δώσει 0."
-
δηλαδη θα πουμε ότι ο χρήστης έκανε την διαίρεση με τον γεννήτορα και βρήκε διαφορετικό αποτέλεσμα απο το μηδέν που αυτό δηλώνει οτι το μήνυμα δεν παρελήφθει σωστά?
επειδή πιο πάνω είδα σε κάτι θέματα να λέει αν αλλοιωθούν τα τάδε bit ποιό θα είναι το αποτέλεσμα της διαίρεσης; και πως ο παραλήπτης θα εξακριβώσει τα σφάλματα μεταφοράς;
-
Το ίδο πράγμα λέμε...
Στην ερώτηση που έκανες αρχικά, η απάντηση είναι ότι το αποτέλεσμα στον παραλήπτη είναι διάφορο του μηδενός.
ΑΝ σε ρωτάει ποιο είναι το αποτέλεσμα, κάνεις την πράξη ακριβώς όπως φαίνεται στο πιο πάνω ποστ κ το βρίσκεις.
Το πώς εξακριβώνει ο χρήστης ότι υπάρχει σφάλμα είναι το ίδιο πράγμα με αυτό που λέμε. Ο παραλήπτης ελέγχει αυτό που έλαβε, αν πάρει 0 είναι σωστή η αποστολή/δεν υπάρχουν σφάλματα/δεν αλλοιώθηκαν bit (όπως και να το πεις η ουσία είναι η ίδια). Αν το αποτέλεσμα ΔΕΝ είναι μηδέν, ο παραλήπτης ξέρει ότι προέκυψε σφάλματα.
Τι σε μπερδεύει ακριβώς?!?
-
με κάλυψες απλά ήθελα να μου το επιβεβαιώσεις! τνχ!
Αυτόματη ένωση μηνύματος: 12 Ιουνίου 2010, 18:06
τελικά δίνει τυπολόγιο??
-
Όταν έδινα εγώ το μάθημα, έδινε (αλλά κάποιους βασικούς τύπους τους είχα μάθει απ' έξω παρ' όλα αυτά).
Τώρα από εκεί και πέρα για τώρα δεν έχω ιδέα.
-
σε ευχαριστώ
-
σε μια ασκηση λεει:
"αν αλλοιωθουν τα μπιτς 2 και 9 ποιο θα ειναι το υπολοιπο της διαιρεσης"
το 2ο και 9ο οπως μετραμε απο αριστερα προς δεξια η δεξια προς αριστερα;
-
Τι γίνεται στην περίπτωση που στηνη διαίρεση του μηνύματος με τον γενήτορα το υπόλυπο της διαίρεσης είναι μηδέν? μπαίνου τόσα μηδενικά στο τέλος όσο έιναι ο βαθμός του πολυωνύμου ή στέλνεται το μηνύμα όπως είναι???
-
Δες στην προηγούμενη σελίδα, έχω γράψει αναλυτικά παράδειγμα!
-
Η πρωτη διαιρεση μου βγαινει και εμενα το ιδιο.
Αν ομως μετα διαιρεσει ο παραληπτης το μηνυμα 11001010010 με τον γεννητορα 1011 δεν βγαινει υπολοιπο 0 αλλα 0110,ενω θα επρεπε να βγαινει 0 αφου το μηνυμα μας δεν εχει σφαλματα.
Γιατι γινεται αυτο?
Διαιρούμε ως εξής:
1 1 0 0 1 0 1 0 0 1 0 | 1 0 1 1
1 0 1 1
_______
0 1 1 1 1
1 0 1 1
_________
0 1 0 0 0
1 0 1 1
_________
0 0 1 1 1
0 0 0 0
__________
0 1 1 1 0
1 0 1 1
_________
0 1 0 1 0
1 0 1 1
_________
0 0 0 1 1
0 0 0 0
__________
0 0 1 1 0
0 0 0 0
__________
0 1 1 0
-
Σωστά, το υπόλοιπο βγαίνει 0010 αλλά ουσιαστικά προσθέτουμε ΜΟΝΟ το 010 σ' αυτό που θέλουμε να στείλουμε.
Δηλαδή πρέπει να στείλουμε 1100101010
Αντίστοιχα φυσικά για γεννήτορα 5 ψηφίων, θα έχουμε αποτέλεσμα 5 ψηφίων και θα προσθέσουμε μόνο τα 4 τελευταία.
Tnx billy!
(ας το διορθώσει κάποιος και στο αρχικό ποστ!)
-
Done
-
Ευχαριστώ πολύ differentreality για την ανάλυση σου :)
-
Το μήνυμα που αποστάλθηκε εδώ θα πρέπει να διορθωθεί:
11001010010 -> 1100101010
-
Διορθωμενο ειναι στο παραδειγμα της differentreality.
-
Ναι αλλά στο παράδειγμα που ελέγχει ο δέκτης είναι λάθος.
-
Ε αυτο λεμε στα προηγουμενα ποστ.
Ειχε λαθος στο αρχικο παραδειγμα,το οποιο διορθωθηκε.
-
differentreality μας/με βοήθησες πάρα πολύ με το post σου! :-*
-
πηρα το παραδειγμα της differentreality και συγκεκριμενα το μηνυμα που θα αποσταλει δηλαδη το 1100101010 και αλλαξα το 2ο και το 9ο bit οποτε εγινε 1000101000 εκανα τις διαιρεσεις και μου βγηκε υπολοιπο 0...δηλαδη οτι δεν υπαρχουν σφαλματα ενω ηδη υπαρχουν 2...ξερει κανεις γιατι συμβαινει αυτο;