АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Коди стійкі до перешкод

Читайте также:
  1. Геліостійкість рослин
  2. Д) вихід автопоїзда із повороту, рух причепа із уводом при наявності поперечного нахилу дороги, наїзд його коліс на перешкоду і боковий удар та боковий вітер.
  3. Жаро- і посухостійкість мезофітів
  4. Класифікація ґрунтів за ступенем і якістю засолення в зв'язку із солестійкістю рослин
  5. Маркування перешкод
  6. Несуча можливість дернини. Стійкість дернини.
  7. Обмеження перешкод на ЗПС точного заходу на посадку I,II,III категорії
  8. ОГОРОДЖЕННЯ МІСЦЬ ПЕРЕШКОД ДЛЯ РУХУ ПОЇЗДІВ І МІСЦЬ ПРОВЕДЕННЯ РОБІТНА СТАНЦІЯХ
  9. Особливості водного режиму та посухостійкість деревних рослин
  10. По-перше, це дасть змогу перешкоджати намаганням проімперських сил розколоти український народ за етнічною, мовною та ідеологічною ознаками.
  11. Поверхні обмеження перешкод

У процесі зберігання даних і передачі інформації з мереж зв'язку неминуче виникають помилки. Контроль цілісності даних і виправлення помилок - важливі завдання на багатьох рівнях роботи з інформацією (зокрема, фізичному, канальному, транспортному рівнях мережевої моделі).

У системах зв'язку можливі кілька стратегій боротьби з помилками:

· Виявлення помилок у блоках даних і автоматичний запит повторної передачі пошкоджених блоків - цей підхід застосовується, в основному, на канальному і транспортному рівнях;

· Виявлення помилок у блоках даних і відкидання пошкоджених блоків - такий підхід іноді застосовується в системах потокового мультимедіа, де не повинно бути затримки передачі і немає часу на повторну передачу;

· Виправлення помилок (англ. forward error correction) застосовується на фізичному рівні.

Перешкодостійкі коди – один з найбільш ефективних засобів забезпечення високої вірогідності передачі дискретної інформації. Історія розвитку перешкодостійкого кодування почалась 1984 р. публікацією знаменитої статті Клода Шенонна, у якій він сформулював теорему для випадку передачі дискретної інформації з каналу із перешкодами, яка стверджує, що ймовірність помилкового декодування прийнятих сигналів може бути як завгодно малою шляхом вибору відповідного способу кодування сигналів..

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

Означення 4.2. Блоковим кодом називається код, у якому при кодуванні до вхідної інформації надається надлишкова. Блоковий код позначається (n,k), де n – кількість розрядів у закодованій комбінації (прийнято називати довжиною або значністю коду), k – кількість інформаційних розрядів вхідної інформації. Якщо вихідні k біт код залишає незмінними, і додає n - k перевірочних, такий код називається систематичним, інакше несистематичним.

Означення 4.4. Приблоковомукодуванні вхідна інформація збільшується на певну величину, яку називають надмірністю коду. Надмірність коду (n,k) обчислюється за формулою:

R над = (n−k)/ п,

Означення 4.3. Кількість одиниць у кодовій комбінації називають вагою (w).

Приклад 4.1. Кодова комбінація 1001001 характеризується значністю n =7 і вагою w =3. ▲

Відстань за Хеммінгом характеризує ступінь відмінності будь-яких двох кодових комбінацій і позначається d. Вона виражається числом позицій або символів, у яких комбінації відрізняються одна від іншої, і визначається як вага по символьної суми за модулем двох цих комбінаціях.

Приклад 4.2. Визначення відстані за Хеммінгом між комбінаціями 10010010 та 11011000. Ці комбінації відрізняються в другій, п’ятій та сьомій позиції. Щоб пересвдчитись застосуємо побітове альтернативне “або”:

Отже, вага отриманої комбінації w =3, тому відстань між вихідними комбінаціями d =3. ▲

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

.

Означення 4.5. Кодом Хеммінга називається (n, k) – систематичний код, який містить надлишкові біти на позиціях 1, 2, 4, 8.. , де <n< .

Синдром коду Хемінга обчислюється наступним чином:

.

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

Таким чином, при кодуванні обираються таким чином, щоби синдром був рівний нулю.

Приклад 4.4. Закодувати двійковим кодом Хеммінга комбінацію A = 10111 двійкового простого коду та показати на прикладі виправлення будь-якої однократної помилки. Визначити надмірність коду Хеммінга.

Виконуємо кодування заданої комбінації А. При k = 5 кількість надишкових елементів r = n-k = 4 становить. Перевірні елементи знаходяться на позиціях 1, 2, 4 та 8.

Записавши кодовий вектор коду Хеммінга у вигляді u 1 u 21 u 4011 u 81, визначаємо значення u 1, u 2, u 4, u 8:

П’ятий біт ми не враховуємо, тому що він рівний “0”. Кожне з чисел 1, 2, 3, 4, 6, 7, 8 та 9 розписуємо у двійковій системі:

1 = 0001, 2 = 0010, 3 = 0011, 4 = 0100, 6 = 0110, 7 =0111, 8 = 1000, 9 = 1001. При застосуванні кон’юнкції над невідомими бітами, для прикладу, результатом буде 0 0 0. Запишемо бітове представлення вертикальними стовбцями:

Звідcи:

u 1 = 1; u 2 = 1; u 4 = 1; u 8 =1.

Отже комбінація коду Хеммінга матиме вигляд 111001111.

Декодування коду Хемінга. Синдром коду Хемінга має наступну особливість: Якщо помилка була в одному біті, то значення синдрому вказує позицію помилки. Якщо помилка була допущена в двох бітах, то синдром просто вказує на наявність помилок без можливості їх виправленя

Нехай передане кодове слово 1101001, а прийняте слово – 1101101.
Синдром, відповідний прийнятому слову, буде дорівнювати:

.

Обчислений синдром вказує на помилку в п'ятій позиції.

Продемонструємо декодування цього коду з виправленням однократної помилки, припустимо, що при передачі сталося спотворення і замість 111001111 була прийнята кодова комбінація 111001011.

Для виявлення та виправлення помилки зробимо ті самі перевірки на парність, що й при кодуванні, але з урахуванням перевірних елементів, тобто знайдемо синдром помилки:

S 1 = u 1 Å u 3 Å u 5Å u 7 Å u 9 = 1 Å 1 Å 0 Å 0 Å 1 = 1;

S 2 = u 2 Å u 3 Å u 6Å u 7 = 1 Å 1 Å 1 Å 0 = 1;

S 3 = u 4 Å u 5 Å u 6Å u 7 = 0 Å 0 Å 1 Å 0 = 1;

S 4 = u 8 Å u 9 = 1 Å 1 = 0.

Маємо синдром 0111. Отже, спотворено елемент за номером 01112 = 710, тобто елемент и 7.Виправляємо його: замість помилкового елемента и 7 = 0 записуємо значення и 7 = 1 і дістаємо правильну кодову комбінацію 111001111.

Надмірність коду Хеммінга R над = r / п = 4/9. ▲

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)