Студопедия

КАТЕГОРИИ:


Загрузка...

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Код з перевіркою на парність




Елементи двійкової арифметики

Полем називається множина математичних об'єктів, для яких визначені операції додавання, віднімання, множення й ділення.

Розглянемо найпростіше поле з двох елементів 0 і 1. Визначимо для нього операції додавання і множення так:


0+0=0,

0+1=1,

1+0=1,

1+1=0;

0*0=0,

0*1=0,

1*0=0,

1*1=1.


Визначені таким чином операції додавання та множення називають додаванням та множенням за модулем 2 (mod 2).

З рівності 1+1=0 випливає, що -1=1 та 1+1=1-1, а з рівності 1*1=1, що 1:1=1.

Алфавіт з двох символів 0 і 1 з означеними для них операціями додавання й множення за mod 2 називається двійковим полем GF(2). Для поля GF(2) застосовні усі методи лінійної алгебри, у тому числі матричні операції.

Операція додавання за mod 2, як правило, позначається символом ⊕, проте у подальшому у даному курсі розглядається тільки додавання за mod 2, тому використовується звичайний знак +.

Найпростіший лінійний блоковий код - це (n-1, n) - код з контролем парності. Цей код, зокрема, широко використовується у модемах.

Кодування полягає у додаванні до кожного байта 9-го контрольного біта так, щоб доповнити кількість одиниць у байті до наперед вибраного для коду парного (even) або непарного (odd) значення.

Наприклад, задана інформаційна послідовність (101), тоді кодовим словом буде (1010), де перевірний символ знаходиться додаванням за mod 2 символів інформаційної послідовності. Якщо число одиниць в інформаційній послідовності парне, то значенням суми за mod 2 буде 0, якщо непарне - то 1, отже, перевірний символ доповнює кодову послідовність так, щоб кількість одиниць в ній була парною.

Математично схему кодування з перевіркою на парність можна записати так:

Е(m1, ... , mk)=(m1, ..., mk, mk+1)

де перевірний символ

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

Схему декодування можна записати так:

Уведемо поняття двійкового симетричного каналу, для якого помилки у бітах рівноймовірні й незалежні. Схематично двійковий симетричний канал зображений на рис. 2.1, де р - ймовірність безпомилкової передачі біта повідомлення; q = 1-p - ймовірність помилкової передачі.

Рис.2.1 Двійковий симетричний канал

Для такої схеми передачі даних ймовірність того, що у n-позиційному коді виникне тільки одна помилка, становить

У загальному випадку ймовірність передачі n бітів з k помилками визначається за формулою Бернуллі

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



Покажемо це на прикладі.

Приклад Перевірка парності при k=2 реалізується таким кодом: 00→000, 01→011, 10→101, 11→110.

Позначимо через р ймовірність правильної передачі, q – ймовірність помилки у біті повідомлення.

Тоді ймовірність виникнення хоча б однієї помилки у кодовій послідовності завдовжки 3 біти P=q 3 +3pq2 +3p2 q. З них не будуть виявлені помилки у двох бітах, що не змінюють парності, ймовірність яких Pпом=3pq2

. Ймовірність помилкової передачі повідомлення з двох бітів без використання контролю парності Pпом=q 2 +2pq.

Для достатньо надійного каналу передачі, тобто при q << 1, 3pq2 << q 2 +2pq, що свідчить про доцільність використання завадостійкого кодування з виявленням поодиноких помилок.

Не зважаючи на простоту і не дуже високу ефективність, коди з перевіркою на парність широко використовуються у системах передачі і зберігання інформації. Їх цінують за невисоку надлишковість: достатньо додати до інформаційної послідовності один перевірний символ - і можна визначити, чи є у прийнятій послідовності помилка. Проте локалізувати місце виникнення помилки, й відтак її виправити неможливо. Можна лише повторити передачу помилкової комбінації.

 





Дата добавления: 2017-01-14; Просмотров: 34; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:





studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.81.42.111
Генерация страницы за: 0.011 сек.