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

Код называется равномерным или блочным, если все кодовые слова имеют одинаковую длину.

Блочный двоичный код, в котором каждое кодовое слово имеет длину n, представляет собой подмножество вершин n-мерного куба.

Пример: геометрическая модель трехзначного двоичного кода есть фигура трехзначного пространства, т. е. куб.

b=b1, b2, b3

b=000

b=001

b=010

b=011

b=100

b=101

b=110

b=111

Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b1, b2, b3. Длина ребра куба равна единице. d – это длина между соседними разрядами или кодовое расстояние.

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

Пусть разрешенными кодами являются 000 и 111 , тогда количество возможных кодов – 8, количество разрешенных кодов – 2, расстояние между разрешенными кодами = 3.

Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц в полученной комбинации. Пример:

000

111

. 111 число единиц = 3. Значит d=3.

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

1. (3,3) когда количество сообщений = 8, количество кодов = 8. В этом случае ошибочный код будет совпадать с одним из сообщений и поэтому ошибку обнаружить невозможно.

2. (2,3) количество сообщений = 4, количество кодов = 8, тогда получим 4 разрешенных кода, совпадающих с вершинами (рис. 8).

Ошибку обнаружить можно, но исправить нельзя.

3. (1,3) ошибку можно и обнаружить и исправить.

Если мы хотим построить код, который может обнаружить n ошибок, то расстояние между кодовыми словами d = k + 1.

Если мы хотим исправлять ошибку, то расстояние должно быть d=2s+1

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

d=k+s+1.

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

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

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

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

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

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

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

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

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

Имеем кодовое слово а=а1, а2,…, аm; составляем другое кодовое слово с добавлением символа – b=b1, b2…bm, bm+1

ai=bi

bm+1=………

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

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

а=а1, а2,…, аm

b= a1 a1 a1, a2 a2 a2,…am am am

ai=bi, длина кода 3m

а2 а2 а2

если 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)

3.3 Групповые коды

Рассмотрим множество двоичных кодов с заданной операцией (сложение по модулю).

Запишем таблицу истинности для операции «сложение по модулю»

a+(b+c)=(a+b)+c

a+b=b+a

a+a=0, (a-1=a)

a+0=a

На множестве кодов задана группа (В,+,0) в свою очередь множество принятых сообщений С образуют группу (С,+,0). Для рассмотренного примера множество кодов b= c=. Очевидно, что множество b является подгруппой множества С.

3.4 Классы

- классы.

Смежным классом В и С называется множество В+С, где С – фиксированный элемент, а b пробегает все значения множества В. для примера построим левый смежный класс.

Два смежных класса пересекаются либо совпадают, а множество левых классов образуют разбиение множества С.

Восемь левых смежных классов:

b c

000 +000=000 000+111=111

001+000=001 001+111=110

010+000=010 010+111=101

011+000=011 011+111=100

100+000=100 100+111=011

101+000=101 101+111=010

110+000=110 110+111=001

111+000=111 111+111=000

 Скачать реферат