Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
а) теоретико-множественное описание осуществляется путем фиксации мощностиых характеристик ?', например, Б' — множество всех слов задапной длины тп;
б) статистическое описание осуществляется заданием вероятностных характеристик 5', например, ?' = 5, и заданы вероятности р1, ..рг появления букв аи
в) логическое описание — это описание множества 5' как некоторого «языка». Оно характеризует способы построения множества в', например, 5' может быть порождено некоторым автоматом.
Пусть задан алфавит ©, где
Через В обозначим слово в алфавите 59 и через 5(59) — множество всех непустых слов в алфавите 59.
Пусть задано отображение В, которое каждому слову А, Л ^ 5'(§1), ставит в соответствие слово
Слово В будем называть кодом сообщения А, а переход от слова А к его коду — кодированием.
В теории кодирования отображения Р задается некоторым алгоритмом.
Пример 1-а) Алфавитное кодирование. Рассмотрим соответствие между буквами алфавита % и некоторыми словами в алфавите 59:
59 = 16,, 6Ч>.
В = Р{Л), Вє5(|3).
Щ ~Ви Щ ~ В г,
(2)
17 с. В. Ябдопевай
йг В Г.
258
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Это соответствие называют схемой и обозначают через 2. Оно определяет алфавитное,. кодирование следующим образом: каждому слову А = а{1 ... а1п из 5" (51) = 5 (Я) ставится в соответствие слово В = В^ ... В{п, называемое кодом слова. А. Слова Ву, ..Вг называются элементарными кодами.
б) Равномерное кодирование. Пусть {А|, ..., А Л — некоторое подмножество попарно различных слов в алфавите $1, имеющих одинаковую длину т. Очевидно, что каждое слово А, которое допускает разложение вида
имеет единственное разложение. Пусть, далее, 5'(9?) — подмножество всех слов в алфавите 31, допускающих разложение вышеуказанного вида. Рассмотрим схему
А1 —
.... (2)1
АЛ — В&,
где элементарные коды В^ имеют одинаковую длину.
Схема 2 определяет равномерное кодирование следующим образом: каждому . слову А = А^ ,.. А{п из 8' (51) ставится в соответствие слово В = В^ ... В1п, называемое кодом слова А.
Выбор кодов связан с различными обстоятельствами, а именно:
с удобством передачи кодов (например, двоичный код технически легче использовать);
с. обеспечением удобства восприятия (например, машинные коды удобны для работы процессора);
с обеспечением максимальной пропускной способности канала;
с обеспечением помехоустойчивости; с достижением определенных свойств алгоритма кодирования (например, простота кодирования, возможность однозначного декодирования) и т. п.
Канал связи можно рассматривать как устройство с одним входом и одним выходом (см. рис. 2). На вход этого устройства поступает код сообщения В. На выходе получают В' — код сообщепия на выходе, где В' — слово в некотором алфавите 5)' и
в'-КЩ.
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
259
В простейшем случае (тождественный канал без помех), т. е. в случае идеальной линии связи, В' = В (или /(В)^ *= В) и значит §3' = $9. В общем случае капал связи может включать в себя преобразование кодов и 33х © (как, на-
пример, в ЭВМ).
Источник помех вносит ошибки в канал связи, вызывая искажения кодов на выходе. Для
описания источника помех используют В I -В’
два способа:__________________________________________I_________________________________________
а) логико-комбинаторное списание рис 2 обычно связано с указанием ограничений па число единичных ошибок;
б) статистическое описание осуществляется заданием вероятностных характеристик источника.
Код сообщения на выходе в случае тождественного канала представляет собой некоторое слово в алфавите 59' = 50. Однако источник помех может приводить к тому, что
В'Ф В.
Сообщение на выходе представляет собой слово в некотором алфавите <5. В случае тождественного канала, т. е. при передаче сообщений, <5 = §1.
Переход от кодов сообщений на выходе к сообщениям на выходе предполагает два преобразования.
Коррекция кода сообщения на выходе. Это преобразование возможпо только для специальных кодов сообщений. В том случае, если мы имеем дело с передачей сообщений, происходит переход от В' к В.
Декодирование. Оно представляет собой переход от кода, полученного из кода сообщения на выходе после коррекции, к сообщению на выходе. Декодирование возможно также не для всяких кодов, а только для специальных кодов сообщений. В случае передачи сообщений декодирование возможно, если существует обратное отображение F-\
В данной главе мы познакомимся с элементами теории кодирования. При отборе материала мы стремились дать представление:
а) о главных классах кодов;
б) о теоретико-вероятностных и комбинаторно-логических подходах к описанию задач;
в) о характере математических задач в этой области;
г) о методах решения задач теории кодирования.
17*
200
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
В § 1—4 изучается алфавитное кодирование. Изложение концентрируется вокруг двух задач: выяснения возможности однозначного декодирования и построения кодов с наименьшей избыточностью. В § 5 изучается один класс кодов из семейства так называемых равномерных кодов. Здесь рассматривается задача о построении помехоустойчивых кодов.
