18683

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

Доклад

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

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

Русский

2013-07-08

24.75 KB

22 чел.

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

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

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 количестве контрольных символов.


 

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

75982. Олімпійський урок 164.5 KB
  Мета: Познайомити учнів із історією олімпійських ігор, досягненнями українських спортсменів на олімпіаді в Пекіні, виховувати почуття патрітизму, прагнення до здорового способу життя...
75983. Тематичний вечір присвячений ювілею Бориса Олійника. «Іду. І поруч твердо Крокує честь – мій секундант» 133.5 KB
  Мені доля вручила перстень І сказала що вже до смерті Я розмічений і заверстаний В наростаючу круговерть. Що однині не буде спокою Ні вночі мені ані вдень І життя моє піде боком А не так як у всіх людей. Коли б земля так думалось мені Була мов куля та ще й оберталась...
75984. Опис репродукції картини М.П.Глущенка «Зима» 180.5 KB
  Мета: Ознайомити учнів з творчою діяльність М.П.Глущенка. Розвивати в учнів образне і логічне мислення. Духовно збагачувати внутрішній світ учнів. Формувати поняття пейзаж, колорит, композиційний центр і т.д. Вироблення вмінь і навичок аналізувати події, прикмети.
75985. Людина – живий організм. Організм людини. Шкіра – захисник організму 8.39 MB
  Мета: Формувати поняття про людину як живий організм та про тіло людини як єдиний організм, у якому всі органи залежать один від одного; дати знання про властивості шкіри як органа, розкрити її значення для людини; розвивати уміння спостерігати...
75986. Свято «Осіння казка» 69.5 KB
  Учитель. За народними переказами осінь перша старша дочка Сонця. Вона останньою залишила батьківський дім і стала на Землі четвертою порою року. Посилаючи осінь на землю, Сонце сказало їй: «Забирай все моє багатство. Я віддаю тобі все своє золото. Будь щедрою і люди будуть любити тебе».
75987. Літературно – музична композиція «Осінні етюди». Позакласний захід за творчістю Ліни Костенко з мультимедійним додатком 80 KB
  Осінь Зустрічайте її Входить дівчина в костюмі Осені Осінь. Слайд 1 Я Осінь - чарівна й ясна Я дивна наче казочка сама Тримаю пензлик у руках Малюю всюди тут і там Щоб догодити любі вам Щоб вміли ви красу кохати Щоб теж у руки пензлик брали Красу природи малювали.
75988. Чи може природа існувати без осені? 346 KB
  Мета: навчати розглядати певну тему з різних точок зору, виявляти їх переваги та недоліки, висувати альтернативну точку зору, сприяти розвитку мислення та вміння вести дискусію; спонукати дітей до пошуку додаткової інформації, розширювати їхній світогляд...
75989. Чарівниця господиня осінь! 43 KB
  Мета: скласти усно твір розповідь за даною темою розвивати звязне мовлення учнів увагу мислення пам’ять творчу уяву спостережливість вміння висловлювати свою думку і почуття збагачувати активний словник учнів виховувати любов і дбайливе ставлення до самого себе і до природи.