18683

Принципы построения корректирующих кодов и их характеристики

Доклад

Информатика, кибернетика и программирование

Принципы построения корректирующих кодов и их характеристики. Коды делятся на: 1. Коды обнаруживающие ошибки. 2. Коды исправляющие ошибки. Все коды такого вида основаны на избыточности которую надо внести в кодовую комбинацию. Эта избыточность может быть введена ...

Русский

2013-07-08

24.75 KB

23 чел.

Принципы построения корректирующих кодов и их характеристики.

Коды делятся на:

1. Коды, обнаруживающие ошибки.

2. Коды, исправляющие ошибки.

Все коды такого вида основаны на избыточности, которую надо внести в кодовую комбинацию. Эта избыточность может быть введена за счет контрольных символов, либо за счет использования не всех комбинаций.

По Хэммингу кодовое расстояние d(x,y) между двумя векторами x,y - число несовпадающих разрядов кода. Вес кода - число единиц в комбинации.

110

010

011

100

101

111

000

001

1. Пусть все комбинации разрешены.

Найдем min кодовое расстояние между комбинациями.

dmin=1

101

100 - при d=1 нет обнаружения ошибок.

2. Оставим только комбинации с dmin=2

Разрешенные комбинации:100,111,101,001.

100

110 - комбинации нет в разрешенных, ошибка.

Если dmin=2, можно обнаружить одиночную ошибку.

3) dmin=3

Разрешенные комбинации:100,011.

100

101 - принимаем за единицу ту комбинацию, до которой расстояние меньше, исправляем на 100.

Таким образом, чтобы код мог обнаруживать ошибки кратности r, надо чтобы min кодовое расстояние было r+1.

dminr+1

Чтобы код мог исправлять ошибки кратности l:

dmin ≥ 2l+1

Если надо исправлять ошибки кратности l и обнаруживать ошибки кратности r (r>l):

dminl+r+1

Характеристики корректирующих кодов.

1. Длина кода (количество информационных символов) – m.

2. Число контрольных символовk.

3. Длина кодовой комбинацииn.

n=m+k

4. Избыточность кода - h

Если используются не все комбинации, то:

,

N – общее число комбинаций, M – число разрешенных комбинаций.

5. Вероятность искаженной комбинации - Pи

Используется биномиальный закон распределения ошибки:

, q=1-p

Вероятность искажения всех комбинаций:

P0 - вероятность искажения одиночного двоичного символа в данном канале связи (устанавливается экспериментально). P0 ≈ 10-3…10-9

6. Вероятность правильной фиксации - Pпр

Pпр=1-Pи

7. Оптимальность кода.

Оптимальным является код, который исправляет max количество ошибок при min количестве контрольных символов.


 

А также другие работы, которые могут Вас заинтересовать

56123. ЕКОНОМІКА ПІДПРИЄМСТВА 248 KB
  Мета заняття: Навчальна: економічно обґрунтоване визначення величини затрат для виробництва і збуту продукції. Методичне забезпечення: Роздатковий матеріал 2 компоненти: вправа для розпізнання термінів; економічний...
56124. Собівартість продукції, її структура. Витрати на виробництво продукції 135.5 KB
  Вивчення теми «Собівартість продукції, її структура. Витрати на виробництво продукції» в рамках усієї дисципліни сприяє формування у студентів вмінь та знань щодо структури собівартості, витрат на виробництво продукції...
56125. Содержание понятия нормирование труда 57 KB
  Нормирование труда - это установление норм затрат труда на изготовление единицы продукции или выработки количества продукции в единицу времени различают следующие основные виды норм: нормы времени; нормы выработки...
56126. Закріплення теоретичного матеріалу по знаках альтерації й вокально-інтонаційних, метро-ритмічних навичок на прикладі знайомих поспівок і пісень 55.5 KB
  Учні повинні довідатися по перших 8 тактах пісню – звучить пісня «Паровоз» Г.Ернесакса у виконанні педагога. Спів групою 1-го куплету пісні. Після цього діти повинні «зіграти» на паперових клавіатурах мелодію заспіву пісні від «ре», від « до», від «фа» з проспівуванням нотами водночас.
56127. Солоність вод світового океану 37.5 KB
  Цей блок починається словами Екзюпері: Вода в тебе ні кольору ні смаку тебе неможливо описати тобою насолоджуються не відаючи що ти таке. Згідно з цією теорією в хмарі міститься вода у вигляді льодяного пилу.
56128. Я, моя сім’я та друзі 973.5 KB
  Nice to see you, my dear students! You are so good-looking today! Your eyes are shining. I know you are eager to dive into English again. And it’s high time to start our lesson. Look at the blackboard and guess what we are going to talk about today.
56129. Сон, його фізіологічні механізми та гігієна сну 6.96 MB
  Мета: виховувати бережливе ставлення до свого здоровя та гігієнічну необхідність здорового сну пізнавальний інтерес до теми; дати поняття про основний ритм життя людини встановити фази сну і їх фізіологічне значення...
56130. Сон і його значення 48 KB
  Мета: розкрити біологічні основи сну і сновидінь причини порушення сну сформувати поняття про фази сну та його роль в житті людини. Обладнання: схема фаз сну людини таблиці медіа фрагменти.