Спосіб розбиття на підмножини залежить від того які помилки повинні виправлятися даним кодом

Зв’язок коректуючої здатності коду і кодової віддалі.

Кодова віддаль характеризує ступінь відмінності між двома довільними кодовими комбінаціями. Найменша віддаль між дозволеними кодовими комбінаціями d_min - важлива характеристика коду, яка визначає його виявляючу і коректуючу здатність. Якщо необхідно побудувати код, який виявляє всі помилки кратністю t і нижче – це значить із множини N₀ можливих вибрати N дозволених комбінацій так, щоб будь-яка з них в сумі по модулю 2 із будь-яким вектором помилок з вагою W_і не більшою t, не дала б в результаті іншої дозволеної комбінації. Для цього необхідно, щоб кодова віддаль d_min була не меншою t+1. Для виправлення виявленої помилки необхідно щоб кодова віддаль між двома дозволеними комбінаціями була не меншою ніж t+2. Це забезпечує утворення для кожної із дозволениих комбінацій множини заборонених, яка, при заданій кратності помилки, не перетинається із множинами заборонених для інших дозволених, що дає можливість однозначно виправити помилку. Очевидно, що виправлення помилок зведенням до дозволеної будь-якої комбінації із її множини заборонених базується на гіпотезі, що мала місце помилка з кратністю не більше t. Однак на практиці не виключена можливіть виникнення помилки з більшою кратністю і тоді помилкова кодова комбінація буде неправильно виправлена до найближчої дозволеної. Таким чином методи виправлення помилок мають імовірнісний характер.

Код Хемінга.

Код Хемiнга належить до найважливiших лiнiйних кодiв, якi широко використовуються на практицi i мають зручний для технiчноi реалiзацii алгоритм виявлення та виправлення однiєї помилки.

Код складаеться з k iнформацiйних двійкових розрядів та n-k контрольних. Загальна кількість розрядів у кодi n. Нумерація розрядів здійснюється справа наліво від 1 до n.

Число n повинно задoвiльняти нерiвнiсть 2^n-k не менше n+1. Для визначення основних параметрiв коду Хемiнга задається кiлькiсть iнформацiйних розрядів k, по яких обчислюється n та n-k. Кiлькiсть iнформацiйних k та контрольних n-k розрядів коду, який виявляє та коректує одну помилку приведена в таблиці.

На основi основних параметрiв коректуючого коду визначають позицii інформаційних та контрольних розрядів. Позиції контрольних розрядів вибираються по значенню степенi 2^і, де i=0,1,2,3... Тобто номери контрольних розрядів будуть рiвнi 1,2,4,16... Між контрольними розрядами справа наліво вписуються інформаційні. Потiм визначають значення контрольних розрядів по такому правилу: сума одиниць на перевiрочних позицiях для даного контрольного розряду повинна бути непарною. Якщо ця сума непарна, то контрольний розряд встановлюється рiвним нулю, якщо парна – одиницi (доповнення до непарності).

Перевiрочнi позицii вибирають таким чином. Cкладають таблицю для ряду натуральних чисел у двiйковому кодi. Кiлькiсть чисел - n. Потiм визначають перевiрочнi позицii по такому правилу: в першу перевiрку входять розряди, якi мiстять одиницю в першому розрядi справа (1,3,5,7 і т.д.), в другу - в другому (2,3,6,7…) і т.д.

7 6 5 4 3 2 1 0

12 11 10 9 8 7 6 5 4 3 2 1

1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001

Рис.1. Формування коду Хемінга.

Для виявлення і виправлення одиночноi помилки в прийнятій кодовій комбінації проводять перевiрку на непарнiсть. Для першоi перевiрки сумують розряди для позицiй, що мiстять одиницю в молодшому розрядi (1,3,5,7...). Якщо кількість одиниць парна, то перший розряд справа для двійкового значення номера помилкової позиції (синдрома) встановлюється рівним одиниці. Потім сумуючи розряди для позицій, що містять одиницю у другому двійковому розряді, і перевіряючи суму на непарність визначають значення другого розряду синдрома. Процес повторюється для позицiй, що містять одиниці у розрядах 3,4,5 i т.д. В результатi формується номер помилкової позицiї коду. Для виправлення помилки символ у цiй позицii необхiдно замiнити на протилежний. Якщо синдром рівний нулю, то прийнята комбінація не містить одиночних помилок. Наприклад, при помилці в шостому розряді визначене значення синдрому буде рівне 0110.

Формування коду Хемінга і виправлення помилкових розрядів може бути реалізоване апаратурно (рис. 2) [2].

Рис. 2. Апаратурна реалізація коду Хемінга.

Нижче приведений демонстраційний варіант програмної реалізації методу Хемінга та результати його роботи.

implicit integer*2(j),character*1(z)

dimension zmn(8),zmr(12),jm1(6),jm2(6),jm3(5),jm4(5),jmz(8)

data zmn/'1','0','1','1','0','1','1','0'/,jmz/12,11,10,9,7,6,5,3/,

*jm1/1,3,5,7,9,11/,jm2/2,3,6,7,10,11/,jm3/4,5,6,7,12/,jm4/8,9,10,11,12/

do 1 j=1,12

1 zmr(j)='0'

do 2 j=1,8

2 zmr(jmz(j))=zmn(j)

write(6,3) zmn

write(6,3) (zmr(j),j=12,1,-1)

3 format(' ',12(a1,1x))

jk=0

do 4 j=1,6

if(zmr(jm1(j)).eq.'1') jk=jk+1

4 continue

write(6,12) jk

if(jk.eq.jk/2*2) zmr(1)='1'

jk=0

do 5 j=1,6

if(zmr(jm2(j)).eq.'1') jk=jk+1

5 continue

write(6,12) jk

if(jk.eq.jk/2*2) zmr(2)='1'

jk=0

do 6 j=1,5

if(zmr(jm3(j)).eq.'1') jk=jk+1

6 continue

write(6,12) jk

if(jk.eq.jk/2*2) zmr(4)='1'

jk=0

do 7 j=1,5

if(zmr(jm4(j)).eq.'1') jk=jk+1

7 continue

write(6,12) jk

if(jk.eq.jk/2*2) zmr(8)='1'

write(6,3) (zmr(j),j=12,1,-1)

zmr(9)='0'

write(6,3) (zmr(j),j=12,1,-1)

js=0

jk=0

do 8 j=1,6

if(zmr(jm1(j)).eq.'1') jk=jk+1

8 continue

if(jk.eq.jk/2*2) js=js+1

write(6,12) jk,js

jk=0

do 9 j=1,6

if(zmr(jm2(j)).eq.'1') jk=jk+1

9 continue

if(jk.eq.jk/2*2) js=js+2

write(6,12) jk,js

jk=0

do 10 j=1,5

if(zmr(jm3(j)).eq.'1') jk=jk+1

10 continue

if(jk.eq.jk/2*2) js=js+4

write(6,12) jk,js

jk=0

do 11 j=1,5

if(zmr(jm4(j)).eq.'1') jk=jk+1

11 continue

if(jk.eq.jk/2*2) js=js+8

write(6,12) jk,js

12 format(' ',2i4)

zz='1'

if(zmr(js).eq.zz) zz='0'

zmr(js)=zz

write(6,3) (zmr(j),j=12,1,-1)

stop

end

1 0 1 1 0 1 1 0

1 0 1 1 0 0 1 1 0 0 0 0

1 0 1 1 0 0 1 1 0 0 1 1

1 0 1 0 0 0 1 1 0 0 1 1

2 1

3 1

3 1

2 9

1 1 0 0 1 1 0 0 1 1

Поиск по сайту: