Legături de date. Detecția și corectarea erorilor.

Din diverse cauze, în timpul transmiterii de date pot apărea fenomene ce duc la coruperea biților, cu alte cuvinte, la inversarea valorii acestora. Pentru a contracara acest fenomen și pentru a menține consistența datelor transmise se pot aplica două soluții:

  • mecanisme de detecție
  • mecanisme de corecție

Ambele metode se bazează pe adăugarea de "redundanță" în cadrul frame-urilor transmise, adică introducerea unor biți adiționali ce ajută la identificarea erorilor.

Principala diferență între cele două constă în ce se întâmplă cu pachetul la receptare. Mecanismul de detecție duce la aruncarea pachetului primit și trimiterea unei cereri de retransmisie, pe când cel de corecție aplică un set de reguli pentru a corecta erorile.

Pe legături de distanță mică poate fi mult mai eficient să retrimitem un pachet decât să încercăm să-l corectăm.

Ethernet:
           ETH HEADER           PAYLOAD    FCS - frame check sequence = 32 bits
     ______________________ _____________ _____
    |-----|-----|----------|-------------|-----|
    | DST | SRC | ETH TYPE |             |     |
    |-----|-----|----------|-------------|-----|
	                                        ↳ biți redundanți

Bitul de paritate

parity bit Dacă se vrea %n cu n > 2, sunt necesari biți redundanți suplimentari.

Checksum

Checksum este o metodă de detecție ce constă în însumarea octeților mesajului ce trebuie transmis.

Pe send se trimite ~CHECKSUM (checksum negat), iar pe receive se mai calculează odată CHECKSUM pe mesajul primit.

Mesajul este corect <=> ~CHECKSUM + CHECKSUM = 0

Implementare checksum (din laborator):

uint8_t simple_csum(uint8_t *buf, size_t len)
{
	if (!buf) return 0;

	uint8_t sum = 0;

	for (int i = 0; i < len; i++) {
		sum += buf[i];
	}

	return sum % 256;
}

Ciclic Redundancy Check

Detectează orice rafală (secvență de biți consecutivi) de erori cu lungime < 32 biți și orice număr impar de erori.

Implementare a CRC32 (din laborator):

uint32_t crc32(uint8_t *buf, size_t len)
{
	uint32_t crc = ~0;
	const uint32_t POLY = 0xEDB88320;

	for (int i = 0; i < len; i++) {
		crc ^= *buf++;

		for (int bit = 0; bit < 8; bit++) {
			if (crc & 1)
				crc = (crc >> 1) ^ POLY;
			else
				crc >>= 1;
		}
	}
	
	crc = ~crc;
	return crc;
}

Cod corector de erori

    1   1   0   0   1   1   0   0   | -> Se ia bitul majoritar
   / \ / \ / \ / \ / \ / \ / \ / \  |    => orice eroare de un singur bit
   111 110 000 000 111 101 010 000  |       va fi garantat corectată
   \ / \ / \ / \ / \ / \ / \ / \ /  |
    1   1   0   0   1   1   0   0   |

Cod Hamming

Inventat de Richard Hamming în 1950, codul Hamming este o metodă de corectare a erorilor ce constă în aplicarea următorilor pași:

Pentru codificare:

  • Codificarea în sistem binar a pozițiilor biților

  • Pe pozițiile care nu au index putere a lui 2 se vor pune biții corespunzători mesajul de transmis (biți de date)

  • Pe pozițiile cu index putere a lui 2 urmează să se regăsească biții de paritate ce vor fi calculați astfel:

    • Se reține poziția pe care se află valoarea 1 în reprezentarea binară a indexului bitului de paritate
    • Se execută XOR între toți biții de date ce au în reprezentarea binară a indexului valoarea 1 pe aceeași poziție cu cea anterior reținută
    • Rezultatul final reprezintă valoarea bitului de paritate
    • Se reia procesul pentru fiecare bit de paritate

  • Odata găsiți acești biți mesajul a fost codificat și este gata să fie transmis

Pentru corecție:

  • La recepție este posibil ca pe parcursul transmisiei să se fi corupt unul sau mai mulți biți. Codul Hemming poate corecta orice eroare de maxim 2 biți.
  • Pentru a face asta se recalculează biții de paritate, iar indicele bitului corupt va fi egal cu suma indicilor biților de paritate care au ieșit diferit după recalculare.

Exemplu Hemming(7,4)

d - bit de date
r - bit de paritate

*If it's too fast you can adjust the playback speed.

Bibliografie