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

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

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

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

     Следует отметить тот факт, что хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние  помех в канале связи. Одним из средств решения подобных несоответствий в системах передачи цифровой информации, является применение помехоустойчивых кодов, лежащих в основе устройств кодирования/декодирования.

     Помехоустойчивое  кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Как правило, корректирующий код может исправлять меньше ошибок, чем обнаруживать. Число ошибок, которые корректирующий код может исправить в определенном интервале последовательности двоичных символов, например, в одной кодовой комбинации, называется исправляющей способностью кода. 
 
 
 
 
 

     2. Алфавитное кодирование

 

    Чтобы сделать кодирование объектом математической теории, на модель канала связи накладываются дополнительные ограничения. Основным объектом, который систематически изучается, является алфавитное кодирование – простейший вид автоматного кодирования, при котором память не используется. 

    2.1. Основные определения. 

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

    Пусть  B = {b₁,b₂,…,b_m} – алфавит. Конечную последовательность символов β = b_i1 b_i2… b_in будем называть словом, а число n - длиной слова (длину слова β будем обозначать через |β|). Через B* обозначается множество всех слов в алфавите B. Слова из B* будем называть также сообщениями. Языком сообщений назовем произвольное подмножество L ⊆ B*.

    Пусть L – язык. Под двоичным кодированием языка L понимается инъективное  отображение f : L→{0,1}⁺ , где {0,1}⁺ - множество всех непустых двоичных последовательностей. Далее под кодированием будет пониматься двоичное кодирование.

    Отображение f ставит в соответствие слову β ∈ L слово α ∈{0,1}+ , α будем называть

кодом сообщения  β.

    Требование  инъективности отображения f означает, что различные сообщения должны

кодироваться  разными двоичными последовательностями. При выполнении этого

требования обеспечивается однозначность декодирования сообщений. Такое кодирование называется взаимно-однозначным.

    В теории кодирования рассматриваются  не любые инъективные отображения  f, а те из них, которые могут быть реализованы алгоритмами.

    Наиболее  изученными являются вопросы экономного кодирования для случая, когда

L=B*, свойства информации описываются вероятностями появления букв в сообщениях

из B*, а в качестве способа кодирования применяется побуквенное, или алфавитное,

кодирование.

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

   v_i ∈ {0,1} 

    Коды  v_i называются элементарными, а их набор V = (v₁, v₂,… v_m) - кодом.

    При построении схемы кодирования используется дополнительная информация о вероятностях появления букв – вероятностное распределение P = (p₁,p₂,…p_m).

    При построении схем алфавитного кодирования  возникают две основные задачи:

1. Проблема распознавания взаимной однозначности алфавитного кодирования;
2. Задача построения схемы кодирования, обеспечивающего наибольшее сжатие.

 

    2.2. Проблема распознавания взаимной однозначности алфавитного кодирования 

    Пример  2.1. Рассмотрим схему

    f ₁ задает взаимно-однозначное кодирование. Достаточно заметить, что перед каждым вхождением символа 1 стоит символ 0, поэтому каждое вхождение 1 вместе с предшествующим нулем кодирует букву b₂. Символ 0, за которым не следует 1, кодирует

букву b₁. Например, последовательность β = 001010001 имеет единственную

расшифровку α = b₁b₂b₂b₁b₁b₂.

    Пример  2.2. Рассмотрим схему

      

    Кодирование, задаваемое схемой f₂, не является взаимно-однозначным. Последовательность β= 001 допускает две расшифровки α₁ = b₁ b₂ и α₂ = b₃.

    Для непосредственной проверки взаимной однозначности  необходимо в общем случае

проверить бесконечное  множество пар слов.

    Определение 2.1. Пусть слово α имеет вид α₁α₂. Тогда α₁ называется префиксом слова α, а α₂ - суффиксом α. Если 0<| α₁ | <| a |, то α₁ называется собственным префиксом α, если 0 <| α₂ | <| a |, то α₂ – собственный суффикс α.

    Определение 2.2. Схема алфавитного кодирования f обладает свойством префикса,

если  для любых i и j (1 ≤ i, j ≤ m, i ≠ j) элементарный код v_i не является префиксом

элементарного кода v_j.

    Определение 2.3. Алфавитное кодирование, схема которого обладает свойством префикса, называется префиксным.

    Теорема 2.1. Если схема обладает свойством префикса, то алфавитное кодирование является взаимно-однозначным.

    Таким образом, свойство префикса является достаточным условием взаимной однозначности.

    Теорема 2.2. Если алфавитное кодирование со схемой f обладает свойством взаимной

однозначности, то длины элементарных кодов l_i = | v_i | (i =1,…, m) удовлетворяют неравенству Мак-Миллана:

      

    Неравенство Мак-Миллана является необходимым  условием взаимной однозначности

кода со схемой f, но не достаточным.

    Рассмотрим  схему , f₂ приведенную ранее:

     

Для нее l₁ = 1, l₂ = 2, и l₃ = 3, и неравенство Мак-Миллана выполняется: 2^-1 + 2^-2 + 2^-3 = 7 /8 <1. Однако задаваемое схемой f₁ кодирование не является взаимно-однозначным.

    Теорема 2.3. Если набор натуральных чисел l₁,l₂,…l_m удовлетворяет неравенству

Мак-Миллана, то существует префиксное кодирование, удовлетворяющее равенствам:

| v₁ |= l₁ ,| v₂ |= l₂,…,| v_m |= lm.

    Следствие. Если существует взаимно-однозначное алфавитное кодирование с заданными длинами элементарных кодов, то существует также префиксное кодирование с теми же длинами элементарных кодов.

    Неравенство Мак-Миллана в силу справедливости теоремы 2.3 можно рассматривать и

как достаточное  условие взаимной однозначности, в том смысле, что если неравенство для некоторой схемы кодирования выполняется, можно заменить эту схему схемой со свойством префикса с теми же длинами элементарных кодов.

    Пусть задан код V = (v₁,v₂,…v_m). Элементарные коды определяют бинарное кодовое дерево. Из каждой вершины дерева выходит не более двух ребер в вершины следующего яруса, левое из которых помечается символом 0, а правое – символом 1. Элементарным

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

    Дерево  называется насыщенным, если из каждой вершины, не являющейся листом, в

следующий ярус выходит ровно два ребра.

     На  рис. 2.1 изображено дерево для схемы префиксного кодирования f₃.

      

     

     Рис.2.1. Кодовое дерево для схемы кодирования f₃. 

    Проблема  распознавания взаимной однозначности алфавитного кодирования решена

Ал. А. Марковым (1963 г.). Алгоритм распознавания состоит  в следующем.

    Для кода V = (v₁,v₂,…v_m) пусть S₁ - множество слов, обладающих следующим свойством. Слово β является собственным префиксом некоторого элементарного кода v_i и одновременно собственным суффиксом некоторого v_j. Положим S = S₁ ∪ { λ} ( λ - пустое слово).