18683

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

Доклад

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

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

Русский

2013-07-08

24.75 KB

19 чел.

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

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

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