Реферат: Основные положения дискретной математики

Если мы хотим построить код одновременно обнаруживающий и исправляющий ошибку, то минимальное кодовое расстояние должно быть

d=k+s+1.

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

10110 – переданная кодовая комбинация

10010 – 1-я принятая комбинация

10100 – 2-я принятая комбинация

00110 – 3-я принятая комбинация

10110 – накопленная комбинация

Как видим на всех трех комбинациях, были ошибки, но накопленная комбинация ошибок не содержит.

Еще одним методом обнаружения ошибок является проверка на четность или нечетность, суть которого состоит в том, что к исходным кодам добавляются нули либо единицы таким образом, чтобы их сумма всегда была четной или нечетной. Сбой любого одного символа всегда нарушит условие четности (нечетности) и ошибка будет обнаружена. В этом случае комбинации друг от друга должны отличаться в двух символах. Запрещенными являются все нечетные комбинации при проверке на четность и наоборот).

3.1 Коды с обнаружением ошибок

Имеем кодовое слово а=а₁ , а₂ ,…, а_m ; составляем другое кодовое слово с добавлением символа – b=b₁ , b₂ …b_m , b_{m +1}

a_i =b_i

b_{m +1} =………..

получим на входе нечетный код, он является всегда ошибочным. Ошибку обнаружить можно но исправить нельзя. Данный код соответствует разработанному примеру (2,3)

3.2 Корректирующие коды

а=а₁ , а₂ ,…, а_m

b= a₁ a₁ a₁ , a₂ a₂ a₂ ,…a_m a_m a_m

a_i =b_i , длина кода 3_m

а₂ а₂ а₂

если 0 0 0, то ошибки нет

если 1 1 1, то ошибки нет

если 0 1 1, то ошибка есть

Такие корректирующие коды надежность, причем их надежность возрастает с увеличением дублирующих, но не экономичны.

Аксиомы расстояния:

d(a,b)0

d(a,b)=0, если a=b

d(a,b)= d(b,a)

d(a,b)+d(b,c)d(a,c)