Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 14 стр.

       3.4 Алгоритм распознавания однозначности декодирования.

      Этот алгоритм формируется на языке теории графов.
      Пусть алфавит кодирования задан схемой:
∑:    а1 – B1
      …
      ar – Br
      Для каждого элементарного кода Biрассмотрим нетривиальное разложе-
ния вида (1)
      Bi= β ' Bi1...Biω β ' ' , β′ β′′ отличны от элементарных кодов.
      Обозначим через B0 множество, содержащее
              а) непустое слово λ;
              б) слова β, которые встречаются в разложениях вида (1) как в фор-
      ме префиксов, так и окончаний.
      Строим граф следующим образом:
      – каждому слову из В0 сопоставим вершину;
      – пусть β′ β′′ ∈ В0. Рассмотрим все нетривиальные разложения вида (3.3).
Для каждого из них соединяем соответствующие словам β′ и β′′ вершины дугой
от β′ к β′′, которой приписано слово Bi1 ...Biω . Полученный орграф обозначим
через Г(∑).
      Теорема. Алфавитное кодирование со схемой ∑ не обладает свойством
взаимной однозначности                   когда Г(∑) содержит ориентированный цикл,
проходящий через λ.

                             3.5 Избыточное кодирование

      При передаче сообщений важную роль играют методы кодирования, кон-
тролирующего ошибки.
      Для этого используется избыточное кодирование сообщений. Основной
задачей избыточного кодирования является обнаружение и исправление оши-
бок на выходе дискретного канала. Пусть данные сообщения представляются в
виде двоичной информации. Эта двоичная информация подлежит передаче по
каналу подверженному случайным ошибкам.
      Задача кодирования состоит в таком добавлении к информационным
символам дополнительных символов, чтобы на приемнике эти искажения могли
быть найдены и исправлены. Т.е. последовательность символов данных пред-
ставляется в виде некоторой более длинной последовательности символов, из-
быточность которой достаточна для защиты данных.
      Двоичный код мощности М и длины n представляет собой множество из
М двоичных слов длины n, называемых кодовыми словами. Обычно М=2k, где k
– некоторое целое число. такой код называется двоичным (n, k) – кодом (блоч-
ный код). О блочном коде судят по длине блока и числу информационных эле-
ментов. По этим двум параметрам n и k и минимальному расстоянию кода d(C),
где С – множество кодовых слов.
                                                                                17