15. Понятия минимального Хеммингово расстояния.

Для определения степени различия между кодовыми словами вводится специальная метрика - кодовое или хэммингово расстояние. Расстояние между двумя кодовыми словами определяется числом разрядов с различным содержанием.

Пример: 10011101

 01011101

11000000 Кодовое расстояние d = 1+1= 2.

Минимальное хэммингово расстояние задает такое мн-во разрешенных слов, для любой пары в котором простое кодовое расстояние не меньше заданной величины.

Хэмминг установил границу существования оптимальных корректирующих кодов. Пусть имеется возможность кодировать словами длиною n- разрядов. При этом все мн-во разных двоичных слов (включая запрещенные) составляет величину 2ⁿ . Требуется узнать какое количество слов из этого множества М использовать в качестве разрешенных, Если надо исправлять все ошибки вплоть до S - кратных.

Число возможных ошибок в n - разрядном кодовом слове:

=

Пример: Для множества трехразрядных слов

{000 , 001 , 011 , 100 , 101 , 110 , 111 } d_min = 2.

Это разрешенные слова для кода, обнаруживающего однократные ошибки. Если дешифратор принимает кодовое слово с нечетным числом единиц, то это значит, что произошла однократная ошибка.

16. Понятие вектора ошибок. Виды. Вероятность. Различают аддитивные(fсп(t)=fсигнал(t)+fпомехи(t)) и мультипликативные(fсп(t)=k*fсигнал(t)*fпомехи(t) 0<k<1) помехи под действием которых возникают ошибки. Для моделирования ошибок исп. псевдослово такой же длины , как исходное слово, это слово содержит единицы в тех разрядах, в которых произошло искажение. Такое псевдослово – вектор ошибки.

Классификация ошибок:

- по кратности: 1-,2-,…r-кратные

- по влиянию искажений одних разрядов на др:

1) некоррелированные – ошибки, при которых искажение содержимого одних разрядов не приводит к искажению содержимого других разрядов.

2) коррелир. - ошибки, при которых искажение содержимого одних разрядов приводит к искажению содержимого группы др разрядов.

Вероятность r-кратной ошибки в n-разрядном слове:

-кол-во таких ошибок

Вероятность такого события – вероятность сложного события и определяется произведение следующих множителей: вероятности, что искажение произойдет в этом разряде p, т.к. таких разрядов r и события независимые, то - p^r , вероятности, что в остальных (n-r) разрядах искажения не будет определяется как (1-p)^(n-r) , умноженных на количество возможных r-кратных ошибок. Т.о.

P=

17 Формула для определения числа избыточ разряд.

Поскольку все ошибки исправить невозМ, то разработчик строит код в расчете на те ошибки, которые исправлять надо.

Пример: 10111011 - помехоустойчивое кодовое слово 00101000 - вектор ошибки

10010011 - запрещенное слово

Множеству подлежащих исправлению векторов ошибок должно соответствовать мн-во запрещенных слов, порожденных из данного разрешенного слова этими ошибками. Таким образом в каждом подмножестве столько запрещенных слов, сколько разных ошибок мы хотим исправить. Если требуется исправлять все ошибки кратности не более S , то количество запрещенных слов в каждом подмножестве, вместе с соответствующим разрешенным словом, равно ( ). Отношение числа всех n- разрядных слов к числу слов в каждом подмножестве определяет предельное количество непересекающихся подмножеств, а значит - максимальное число разрешенных слов т.е. Если , то

Таким образом определяется граница Хэмминга для существования оптимальных корректирующих кодов.

Пример: Пусть для построения кода, корректирующего все однократные ошибки, используются однобайтовые слова. Требуется определить максимальное число разрешенных слов, выбираемых из всего множества однобайтовых слов.

Число однократных ошибок , т.е. .

Максимальное число разрешенных слов , т.е.