О.О.Бойко

Дніпропетровський національний університет ім.. Олеся Гончара

Реалізація алгоритмів кодування із знаходженням та виправленням однократної помилки, за допомогою мови програмування С. Код  Хеміннга.

Опис складного коду з виправленням однократної помилки. Код Хеміннга.

До складних кодів належить алгоритм Хеміннга. Алгоритмів Хеміннга існує багато, однак ми розглянемо найпростіший з них на одному з інформаційних слів «habr».

Принцип цього алгоритму полягає в тому, що ми спочатку переводимо повідомлення у бінарний вигляд, та розставляємо контрольні біти за ступенем двійки. Також ми повинні вирішитись з довжиною інформаційних біт. Довжина нашого повідомлення складатиме 16 біт. Тобто дане повідомлення буде передаватися по частинам, а саме по дві латинські букви, оскільки один символ у бінарному вигляді має довжину 8 біт. На рисунках зображених нижче показано повідомлення у бінарному вигляді та розставлені контрольні біти, на першій частині нашого повідомлення.

Повідомлення у бінарному вигляді

http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.pnghttp://habrastorage.org/storage2/917/51d/2a9/91751d2a972767500f78b7700c9e21dc.png

Повідомлення з контрольними бітами

http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png

Далі ми повинні вирішити які біти вони повинні контролювати. Це робиться за допомогою певного правила, а саме: контрольний біт під номером N, контролює кожні наступніN біт через N біт, починаючи з позиції N.Детальніше показано нижче на рисунку.

http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png

Тепер для того, щоб визначити значення контрольного біту ми повинні скласти ті контролюючі біти, які відповідають своїм контрольним бітам і отриману суму поділити навпіл. Якщо отриманий результат парний то контрольний біт дорівнюватиме 0,а якщо не парний то 1. Ось що ми отримали.

http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png

Тепер приступимо до фінальної частини алгоритму, а саме декодування та виправлення помилки.

Припустимо, що при передачі інформації виникла помилка, наприклад у 11 біті.  Для того щоб її виявити ми повинні заново закодувати наше повідомлення, однак уже з помилкою. Отриманий результат порівнюємо з кодуванням повідомлення без помилки. Тепер коли ми порівняли повідомлення яке закодоване з помилкою і без помилки, додаємо ті контрольні біти які не співпадають і отриманий результат будет номером неправильного біта.

Закодовано без помилки

http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png

Закодовано з помилкою

http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png

З нашого прикладу ми бачимо, що біти під номерами 1,2,8 не співпадають. Склавши їх номера (1+2+8=11) отримуємо, що дійсно неправильним є 11-й біт. Тепер рекурсуємо його та відкинувши контрольні біти ми отримаємо наше початкове повідомлення.

Отже розглянувши приклад з виправленням однократної помилки, ми можемо підійти до основної мети, а саме реалізації цього алгоритму, за допомогою язика програмування С. Програма написана чітко за цим алгоритмом, а отже вона слугує, як приклад для наочного пояснення роботи даного виду кодування.

Код програми:

#include<stdio.h>

#include<MATH.h>

voidKoder_Dkoder (char a[])

{

charsum[5];

charbl[21];

int i,j,l,bufer;

for(i=0;i<=4;i++)//открылицкл для контрольныхбитизмасива сам

     {

j=pow(2,i)-1;//контрольныебитырасставленные по степеням двойки в масиве а

         //printf("j=%d\n",j);

         a[j]='0';

bufer=j;

sum[i]=0;

while(bufer<=20)//цикл для масива а         {

for(l=bufer;((l<=bufer+j)&&(l<=20));l++)//цикл для одного блока контрольирующихбить одним контрольнымбитом в масиве а    {

if(a[l]=='1')

sum[i]=sum[i]+1;     }

/*printf("l=%d\n",l);*/  

bufer=bufer+2*(j+1);// переход по блокам с котролирующимибитами в масиве а          }

      }

printf("vivodnaekransumizavisimixbit\n");

for(i=0;i<=4;i++)

{//выводмасива сам на экран, тоесть результат суммыконтролирующихбитов для каждого контрольного бита

printf("sum[%d]=%d\n",i,sum[i]);}

for(i=0;i<=4;i++){

j=pow(2,i)-1;

if(sum[i]%2==0) a[j]='0';

else a[j]='1';}                // printf("Vvedenniyikodbilzakodirovan\n");

for(i=0;i<=20;i++)

printf("%c",a[i]);}

Main(){

char a[21];

charbibik[21];

int i,j,b,t,T;

printf("Vveditekoddvuxbukv s kontrolnimibitami (dvjichnayiasistemaschisleniyia))\n");

for(i=0;i<=20;i++)

scanf("%c",&a[i]);

Koder_Dkoder(a);

printf("\nVveditenomershnura ");

scanf("%d",&b);

switch (b) {

case 10: if(a[5]=='1') a[5]='0';

elseif(a[5]=='0') a[5]='1';

break;

case 15: if(a[10]=='1') a[10]='0';

elseif(a[10]=='0') a[10]='1';                   

break;

default:{}for(i=0;i<=20;i++)

{printf("%c",a[i]);}

for(i=0;i<=20;i++)

      {bibik[i]=a[i]; }

Koder_Dkoder(a);

printf("\nNomeranesootvetstvuishihbit\n");                                            

t=0;T=0;

for(i=0;i<=20;i++)

if(bibik[i]!=a[i])

{t=t+(i+1);

T=t-1;

printf(" n=%d",i+1);}printf(" \nOshibka v %d bite",t);

if(bibik[T]=='1') bibik[T]='0';

elsebibik[T]='1';

printf("\n");

printf("Rekursirovali %d -yi bit i poluchiliobratnopraveliniyizakodirovaniyikod\n",t);

for(i=0;i<=20;i++)                                     {printf("%c",bibik[i]);}

printf("\n\n\KodeHemingmodelVer 1.1++");                                 

getchar();

getchar();

}

Висновок. Розібрались для чого потрібне кодування та коди із знаходженням та виправленням помилок при передачі інформації по каналам зв’язку, чи перенесені її на диск або збереження на сайті у мережі Інтернет. Також доповнили готову статтю на сайті http://habrahabr.ru/ програмою.Отриманий продукт допоможе людям у вивченні алгоритмів Хеміннга і не тільки, адже цей алгоритм містить принципи простих кодів з задачею мінімуму.