Обнаружение ошибок Хэмминга

Question

У меня есть этот код, как указано ниже, для проверки ошибок с использованием кодов помех. Я просмотрел алгоритм в Википедии, а также понял его работу, как описано в потоке How does the Hamming code work?

Но приведенный ниже код использует некоторую сумму бит четности, чтобы определить, какой бит является ошибкой.

Может кто-нибудь объяснить, как именно сумма может быть использована для обнаружения ошибки?

Код:

#include<stdio.h> 
#include<math.h> 
void main() 
{ 
    int i,a[4],c[3],r[7],clk[3],n,sum=0; 
    printf("Enter data bits\n"); 

    for(i=3;i>=0;i--) 
     scanf("%d",&a[i]); 
    printf("\n"); 

    c[0]=(a[0]+a[1]+a[2])%2; 
    c[1]=(a[1]+a[2]+a[3])%2; 
    c[2]=(a[1]+a[0]+a[3])%2; 

    printf("data bits after hamming code is\n"); 

    for(i=3;i>=0;i--) 
     printf("%d",a[i]); 
    for(i=2;i>=0;i--) 
     printf("%d",c[i]); 
    printf("Enter recieved code\n"); 
    for(i=0;i<7;i++) 
     scanf("%d",&r[i]); 

    clk[0]=(r[3]+r[1]+r[2]+r[6])%2; 
    clk[1]=(r[0]+r[2]+r[1]+r[5])%2; 
    clk[2]=(r[0]+r[2]+r[3]+r[4])%2; 

    sum=4*clk[2]+2*clk[1]+1*clk[0]; 

    if(sum==0) 
     printf("\n u have recived coorrect code\n"); 
    if(sum==1) 
    { printf("Error in check bit 2\n"); 
     printf("The correct code is"); 
     r[6]=(r[6]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
    if(sum==2) 
    { 
     printf("Error in check bit 1\n"); 
     printf("The correct code is"); 
     r[5]=(r[5]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
    if(sum==3) 
    { 
     printf("\nError in data bit 1"); 
     printf("The correct code is"); 
     r[1]=(r[1]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
    if(sum==4) 
    { 
     printf("\n Error in chect bit 0"); 
     printf("The correct code is"); 
     r[4]=(r[4]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
    if(sum==5) 
    { 
     printf("\n Error in data bits 3"); 
     printf("The correct code is"); 
     r[3]=(r[3]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
    if(sum==6) 
    { 
     printf("Error in data bits 0"); 
     printf("The correct code"); 
     r[0]=(r[0]+1)%2; 
     for(i=0;i<7;i++); 
     printf("%d",r[i]); 
    } 
    if(sum==7) 
    { 
     printf("Error in data bits 2"); 
     printf("The correct code is"); 
     r[2]=(r[2]+1)%2; 
     for(i=0;i<7;i++) 
     printf("%d",r[i]); 
    } 
} 

Answer 1

Биты суммируются таким образом, что каждая возможная одноразрядная ошибка производит уникальную сигнатуру в sum. Например, все биты с нечетным номером суммируются в бит 0, поэтому, если ошибка в бите с нечетным номером, сигнатура будет нечетной. (Ну, схема нумерации в примерной программе смешает бит вверх, но так я ее и реализую, как показывает статья в Википедии.)

Существует более одного кода Хэмминга, поэтому обязательно прочитайте статью в Википедии на странице Hamming (7,4) code.

Answer 2

Вот альтернативный способ мышления о коде Хэмминга в частности и линейных кодах в целом. Один из способов кодирования кода Хэмминга - передать исходные данные, а затем добавить к нему контрольную сумму. Эта контрольная сумма является линейной функцией исходных данных (вычисляется с помощью арифметики mod 2).

Когда вы получаете данные, вы можете рассчитать контрольную сумму и добавить ее, mod 2, в полученную контрольную сумму. Если результат равен нулю, две контрольные суммы были идентичны, и вы могли бы также принять данные.

Если результат не равен нулю, у вас есть некоторая линейная функция передаваемых данных и шаблон ошибок, которые его испортили. Когда вы добавили две контрольные суммы, вы добавили линейную функцию исходных данных и линейную функцию (исходные данные с шаблоном ошибок, добавленным в него mod 2). Поскольку это дополнение к моду 2, когда вы добавили две контрольные суммы, два вклада от исходных данных отменили друг друга, и вы получили что-то, что зависит только от шаблона ошибки, а вовсе не от данных, закодированных. Этот результат называется синдромом (или, по крайней мере, эквивалентен синдрому).

Поэтому одним из способов узнать, что такое шаблон ошибки, является вычисление синдромов для каждого возможного шаблона ошибки (или, по крайней мере, шаблонов ошибок, о которых вы заботитесь) и хранения их синдромов в таблице. Для кода Хэмминга вы, как правило, рассматриваете все однобитовые шаблоны ошибок. Это синхронное декодирование.

Итак, когда вы получаете данные, вы вычисляете синдром (сумма ожидаемых и полученных контрольных сумм). Если он равен нулю, все хорошо. Если это не так, вы просматриваете его в таблице синдрома и, если он есть, вы добавляете полученный шаблон ошибки к полученным данным для исправления ошибки. Если его там нет, вы обнаружили что-то другое, кроме однобитовой ошибки, возможно, двухбитовой ошибки.

Одна из причин детального рассмотрения этой проблемы заключается в том, чтобы показать, что вы можете использовать ту же идею (при условии, что вы можете создавать достаточно большие таблицы), чтобы исправить более сложные шаблоны ошибок или исправить различные варианты ошибок, если вы знаете, что некоторые одиночные битовые ошибки очень маловероятны (поэтому не помещайте их в таблицу), но вероятны некоторые двойные битовые ошибки (поэтому помещаем их в таблицу, если для них есть место).

Для более мощных кодов ошибок количество исправляемых ошибок становится неуправляемым, и вам нужно использовать более умные идеи, которые используют структуру кода.

Answer 3

См понять, поставив ошибки в коде

1. Предположим, что мы изменить r[3] бит в полученном код Хемминга так изменить в r[3] приводит к изменению в 2 inidividual Syndrom бит, который clk[0] и clk[2] то соответствующий полученная сумма составляет 5 (1*1+0*2+1*4).
2. Как мудрый u может поместить другую ошибку в любое другое место бит, так что u получит другую сумму, следовательно, вы можете различать суммы и биты ошибок.
3. Если вы хотите узнать больше на этом электронном письме Sambhav goel - мое имя, а goelsambhav9@gmail.com - мой идентификатор.