Каналы передачи данных ненадежны (шумы, наводки и т.д.), да и само оборудование обработки информации работает со сбоями. По этой причине важную роль приобретают механизмы детектирования ошибок. Ведь если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным. Можно, конечно, передать код дважды и сравнить, но это уже двойная избыточность обнаружения ошибок является контроль по четности. Обычно контролируется передача блока данных ( М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).
При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой – минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое расстояние Хэмминга.
Пусть А и Б — две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.
Можно показать, что для детектирования ошибок в n битах схема кодирования требует применения кодовых слов с расстоянием Хэмминга не менее N + 1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с расстоянием Хэмминга между кодами не менее 2N + 1. Таким образом, конструируя код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями большее, чем оно может возникнуть из-за ошибок.
Широко рас коды с одиночным битом четности. В этих кодах к каждым М бит добавляется 1 бит, значение которого определяется четностью (или нечетностью) суммы этих М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем четности будут 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится.
Предположим, что частота ошибок ( BER – Bit Error Rate) равна р = 10-4. В этом случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p)8 = 7,9 х 10-4. Добавление бита четности позволяет детектировать любую ошибку в одном из переданных битах. Здесь вероятность ошибки в одном из 9 битов равна 9p(1 – p)8. Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p)9 – 9p(1 – p)8 = 3,6 x 10-7. Таким образом, добавление бита четности уменьшает вероятность необнаруженной ошибки почти в 1000 раз. Использование одного бита четности типично для асинхронного метода передачи. В синхронных каналах чаще используется вычисление и передача битов четности как для строк, так и для столбцов передаваемого массива данных. Такая схема позволяет не только регистрировать, но и исправлять ошибки в одном из битов переданного блока.
Контроль по четности достаточно эффективен для выявления одиночных и множественных ошибок в условиях, когда они являются независимыми. При возникновении ошибок в кластерах бит метод контроля четности неэффективен, и тогда предпочтительнее метод вычисления циклических сумм ( CRC — Cyclic Redundancy Check). В этом методе передаваемый кадр делится на специально подобранный образующий полином. Дополнение остатка от деления и является контрольной суммой.
В Ethernet вычисление CRC производится аппаратно. На рис. 4.1 показан пример реализации аппаратного расчета CRC для образующего полинома R(x) = 1 + x2 + x3 + x5 + x7. В этой схеме входной код приходит слева.
Вот, нашел на одном из сайтов: #include <iostream>
#include <conio.h>
#include <cstdlib>
#include <ctime>
using namespace std;
int main (){
srand(time(0));
int n, one, two, co=0, ol, k=0, var, sum1=0, sum2=0;
bool kto=true;
cout << "Privet davaii sigraem v kosti.\nPobedit tot u kogo suma 3 broskov budet bolshe\n\n";
while (k<3)
{
cout << "\n1 - Brositj kubik\n2 - Vijti\nViberi variant: ";
cin >> var;
if (var==1)
{
for (int j=0; j<=1; j++)
{
one=1+(rand()%6);
two=1+(rand()%6);
cout << "\n";
if (kto) cout << "\tTvoi kubiki\n";
if (!kto) cout << "\tMoi kubiki\n";
cout << "\n";
for (int i=1; i<=5; i++)
{
if (i==1) n=1;
else if (i==2 && one==1) n=2;
else if (i==2 && one==3 || i==2 && one==2) n=3;
else if (i==2 && one==4 || i==2 && one==5 || i==2 && one==6) n=4;
else if (i==3 && one==3 || i==3 && one==1 || i==3 && one==5) n=5;
else if (i==3 && one==2 || i==3 && one==4) n=2;
else if (i==3 && one==6) n=4;
else if (i==4 && one==1) n=2;
else if (i==4 && one==3 || i==4 && one==2) n=6;
else if (i==4 && one==4 || i==4 && one==5 || i==4 && one==6) n=4;
else if (i==5) n=7;
switch (n){
case 1:
cout << (char)201 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)187;
break;
case 2:
cout << (char)186 << " " << (char)186;
break;
case 3:
cout << (char)186 << " o " << (char)186;
break;
case 4:
cout << (char)186 << " o o " << (char)186;
break;
case 5:
cout << (char)186 << " o " << (char)186;
break;
case 6:
cout << (char)186 << " o " << (char)186;
break;
case 7:
cout << (char)200 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)205 << (char)188;
break;
}
if (co%2==0) {
cout << "\t";
i--;
ol=one;
one=two;}
else {
cout << endl;
one=ol; }
co++;
}
if (kto){
sum1=sum1+one+two;
kto=false;
continue;
}
if(!kto){
sum2=sum2+one+two;
kto=true;
}
}
}
else if (var==2) return 0;
else {
cout << "\n!!! Viberi variant 1 ili 2 !!!\n";
continue;}
k++;
}
cout << "\nTvoj rezultat = " << sum1 << endl << "Moj rezultat = " << sum2 << endl;
if (sum1>sum2)
cout << "\n\tTi pobedil ;)";
else cout << "\n\tTi proigral :(";
getch ();
}
