Xaeron
Μηχανικών Πληροφορικής ΤΕ
Πληροφορικής & Επικοινωνιών
Μηνύματα: 3205
Θετικοί ψήφοι: +40
 Αποσυνδεδεμένος
If you smell...what Xaeron...is cooking...
|
|
05 Φεβρουαρίου 2010, 21:32
|
0
|
|
|
|
|
Τελευταία τροποποίηση: 05 Φεβρουαρίου 2010, 21:54 από Xaeron
|
Καταγράφηκε
|
|
|
|
|
|
lafs
Μηχανικών Πληροφορικής ΤΕ
Μηνύματα: 839
Θετικοί ψήφοι: 0
Αποσυνδεδεμένος
|
Ολοκληρωμένο παράδειγμα αλγορίθμου 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() */
|
|
|
|
|
Καταγράφηκε
|
Efstathios Chatzikyriakidis (efxa)
Informatics & Communications Engineer (BSc)
WEB: efxa.org - EMAIL: contact@efxa.org
|
|
|
Xaeron
Μηχανικών Πληροφορικής ΤΕ
Πληροφορικής & Επικοινωνιών
Μηνύματα: 3205
Θετικοί ψήφοι: +40
Αποσυνδεδεμένος
If you smell...what Xaeron...is cooking...
|
Ευχαριστώ αλλά δεν θέλω τον κώδικα...
|
|
|
|
|
Καταγράφηκε
|
|
|
|
lafs
Μηχανικών Πληροφορικής ΤΕ
Μηνύματα: 839
Θετικοί ψήφοι: 0
Αποσυνδεδεμένος
|
... ολοκληρωμένο παράδειγμα του αλγορίθμου CRC ...
Τι ακριβώς θέλεις? |
|
|
|
|
Καταγράφηκε
|
Efstathios Chatzikyriakidis (efxa)
Informatics & Communications Engineer (BSc)
WEB: efxa.org - EMAIL: contact@efxa.org
|
|
|
Xaeron
Μηχανικών Πληροφορικής ΤΕ
Πληροφορικής & Επικοινωνιών
Μηνύματα: 3205
Θετικοί ψήφοι: +40
Αποσυνδεδεμένος
If you smell...what Xaeron...is cooking...
|
Ένα ολοκληρωμένο παράδειγμα όπως αυτό που έχει στις διαφάνειες του κ. Χειλά.
|
|
|
|
|
Καταγράφηκε
|
|
|
|
lafs
Μηχανικών Πληροφορικής ΤΕ
Μηνύματα: 839
Θετικοί ψήφοι: 0
Αποσυνδεδεμένος
|
Τελικά εννοούσες παράδειγμα από τις σημειώσεις του Χειλά. ΟΚ. Δεν το έχω παρακολουθήσει γιατί τώρα μπαίνω στο 6 εξάμηνο. Πάντως θεωρώ πως αυτό το παράδειγμα είναι κατατοπιστικότατο. Για να βρεις και σχετική θεωρία από αυτό σου προτείνω να διαβάσεις το ανάλογο κεφάλαιο του βιβλίου: http://oreilly.com/catalog/9781565923546 |
|
|
|
|
Καταγράφηκε
|
Efstathios Chatzikyriakidis (efxa)
Informatics & Communications Engineer (BSc)
WEB: efxa.org - EMAIL: contact@efxa.org
|
|
|
differentreality
Μηχανικών Πληροφορικής ΤΕ
Μηνύματα: 602
Θετικοί ψήφοι: +20
Αποσυνδεδεμένος
|
Είναι πολύ εύκολο... Σου δίνεται:
-> ένα μήνυμα σε ακολουθία από 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.
|
|
|
|
Τελευταία τροποποίηση: 28 Ιανουαρίου 2011, 22:47 από Sermac
|
Καταγράφηκε
|
|
|
|
Xaeron
Μηχανικών Πληροφορικής ΤΕ
Πληροφορικής & Επικοινωνιών
Μηνύματα: 3205
Θετικοί ψήφοι: +40
Αποσυνδεδεμένος
If you smell...what Xaeron...is cooking...
|
differentreality, σε ευχαριστώ πάρα πολύ! Ήσουν αρκετά κατανοητή!
|
|
|
|
|
Καταγράφηκε
|
|
|
|
differentreality
Μηχανικών Πληροφορικής ΤΕ
Μηνύματα: 602
Θετικοί ψήφοι: +20
Αποσυνδεδεμένος
|
no prob  αλλα κοίτα να σκίσεις στο μάθημα ε :p |
|
|
|
|
Καταγράφηκε
|
|
|
|
|
Mini
|
παιδιά στα θέματα θεωρίας "σε περίπτωση που αλλοιωθούν κάποια bits απο την ακολουθία του μηνύματος ποιο θα ειναι το αποτέλεσμα της διαίρεσης" πως απαντάμε;
|
|
|
|
|
Καταγράφηκε
|
|
|
|
|
Shoutbox!
Καλώς ορίσατε, Επισκέπτης. Παρακαλούμε συνδεθείτε ή εγγραφείτε.
Χάσατε το email ενεργοποίησης;
19 Απριλίου 2024, 00:03
