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

Алфавит – это конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.).

И R – некоторое множество конечных слов в алфавите А. Однозначное отображение множества R в некоторое множество слов в алфавите В называется кодированием множества R.

Образ С множества R при отображении называется кодом множества R. Слова из С называются кодовыми словами; при этом, если слово w из R отображается в слово v из С, то v называется кодом слова w. Слова из R называются сообщениями, алфавит А – алфавитом сообщений, алфавит В – кодирующим алфавитом. Если кодирующий алфавит В состоит из двух букв (в этом случае будем полагать, что ), то кодирование и соответствующий код С называется двоичным (с ними мы и будем работать).

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

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

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

b=b₁ , b₂ , b₃

b=000

b=001

b=010

b=011

b=100

b=101

b=110

b=111

Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b₁ , b₂ , b₃ . Длина ребра куба равна единице. 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.