CRC - Laptörténet

HG2ECZ, 2006. október 9., 14:02-n

2006-10-09T14:02:58Z

HG2ECZ: /* Keresőtáblás algoritmus gyorsítás */

2006-08-05T23:09:39Z

Keresőtáblás algoritmus gyorsítás

HG2ECZ: /* CRC-32 */

2006-08-05T23:00:30Z

CRC-32

HG2ECZ, 2006. augusztus 5., 22:53-n

2006-08-05T22:53:16Z

Új lap

A CRC a Cyclic Redundancy Code rövidítése.

== CRC-12 ==

Polinomja: CRC-12 = x12 + x11 + x3 + x2 + x1 + 1.

== CRC-16 ==

Polinomja: CRC-16 = x16 + x15 + x2 + 1.

== CRC-CCITT ==

Polinomja: CRC-CCITT = x16 + x12 + x5 + 1.

Rádióamatőr alkalmazása:
* AX.25 esetén használatos hibadetektáló ellenörző kód.

=== Hardver implementáció ===

[[Kép:CRC-CCITT-shiftreg.png]]

A fenti ábrán 1 bites tárolók (latch-ek) vannak egymás után kötve, így az adatbit minden egyes órajel hatására eggyel balra lép. A bit a bal oldalon érkezik, és 1 bites XOR áramkörön keresztül kerül az X0 tároló bemenetére. A jel a megfelelő tároló bemenet előtt szintén XOR kapuba van csatlakoztatva.

Amikor beérkezett az utolsó bit is, a tárolók kimeneteit kell kiolvasni, és megvan a CRC. Természetesen az új számítás előtt a kezdőértékre vissza kell állítani a tárolókat (reset).

=== Algoritmikus implementáció ===

<HIGHLIGHTSYNTAX language="c">/* Alábbi példa egy CRC-CCITT kiszámítására alkalmas algoritmust ismertet */
const unsigned short crc_poly=0x0810; // binaris erteke: 0000 1000 0001 0000
unsigned short crc;

void init_crc() {
crc=0xffff
}

/* 1 byte hozzáadása a CRC polinomhoz */
void calc_crc(unsigned char x) {
int k, i;
for (k=0; k<8; k++) {
i = (x >> 7) & 1; // MSB
if (crc & 0x8000) crc = (crc ^ crc_poly) << 1 + (i ^ 1);
else crc = (crc ^ crc_poly) << 1 + i;
crc =^ 0xffff;
x << 1;
}
}
</HIGHLIGHTSYNTAX>

Mint látszik, elég nehézkes számítás a CRC. A gyorsítás érdekében vagy hardveres gyorsítást alkalmaznak (visszacsatolt shift regiszter) vagy keresőtáblás megoldást.

=== Keresőtáblás algoritmus gyorsítás ===

<HIGHLIGHTSYNTAX language="c">/* A keresőtábla 256 db 16 bites értéket tartalmaz. Alább egy teljes csomag keresőtáblás CRC számító algoritmusa látható */
unsigned short crc_ccitt(u16 crc, u8 const *buffer, size_t len) {
while (len--) crc = (crc >> 8) ^ crc_ccitt_table[(crc ^ *buffer++) & 0xff];
return crc;
}
</HIGHLIGHTSYNTAX>

A keresőtáblázatot a Linux kernelforrás ( http://www.kernel.org ) linux-2.6.xx/lib/crc-ccitt.c állományából lehet kimásolni.

← Régebbi változat		A lap 2006. október 9., 14:02-kori változata
65. sor:		65. sor:

	A keresőtáblázatot a Linux kernelforrás ( http://www.kernel.org ) linux-2.6.xx/lib/crc-ccitt.c állományából lehet kimásolni.		A keresőtáblázatot a Linux kernelforrás ( http://www.kernel.org ) linux-2.6.xx/lib/crc-ccitt.c állományából lehet kimásolni.
		+
		+
		+	[[Kategória:Rádióamatőr adatátvitel]]

← Régebbi változat		A lap 2006. augusztus 5., 23:09-kori változata
54. sor:		54. sor:

	=== Keresőtáblás algoritmus gyorsítás ===		=== Keresőtáblás algoritmus gyorsítás ===
		+
		+	Alább bemutatásra kerülő megoldás körülbelül 10-szer gyorsabb, mint a fennt bemutatott bitről bitre számoló megoldás. Ezért szoftveres megoldás esetén szinte kivétel nélkül ezzel a keresőtáblás megoldással találkozunk.

	<HIGHLIGHTSYNTAX language="c">/* A keresőtábla 256 db 16 bites értéket tartalmaz. Alább egy teljes csomag keresőtáblás CRC számító algoritmusa látható */		<HIGHLIGHTSYNTAX language="c">/* A keresőtábla 256 db 16 bites értéket tartalmaz. Alább egy teljes csomag keresőtáblás CRC számító algoritmusa látható */

← Régebbi változat		A lap 2006. augusztus 5., 23:00-kori változata
8. sor:		8. sor:

	Polinomja: CRC-16 = x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1.		Polinomja: CRC-16 = x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1.
		+
		+	== CRC-32 ==
		+
		+	Polinomja: x<sup>32</sup> + x<sup>26</sup> + x<sup>23</sup> + x<sup>22</sup> + x<sup>16</sup> + x<sup>12</sup> + x<sup>11</sup> + x<sup>10</sup> + x<sup>8</sup> + x<sup>7</sup> + x<sup>5</sup> + x<sup>4</sup> + x<sup>2</sup> + x<sup>1</sup> + 1

	== CRC-CCITT ==		== CRC-CCITT ==