Файл: Методы кодирования данных (Процесс формирования цифровых сигналов).pdf

1.2. Первая теорема Шеннона

Очевидно, что при передаче посланий по линиям связи могут образовываться помехи, ведущие к нежелательной модификации передаваемых символов. К примеру, при передаче речевого сообщения в ветреную погоду собеседнику, находящемуся от вас на существенной дистанции, передаваемое сообщение будет в значительной степени искажено естественной помехой - ветром. В целом, трансфер данных при существующих помехах является значительной теоретической и практической задачей. Ее значимость существенно растет из-за многопланового внедрения компьютерных линий связи, в которых помехи представляют собой неизбежную проблему.[1]

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

Помехи в процессе передачи данных характерны не только для сугубо технических систем. Они являются вполне обыденным эффектом в повседневной жизни. Как пример можно привести разговор по телефону с неудовлетворительным качеством линии связи. Как правило, человеческий организм довольно-таки эффективно справляется с любой из перечисленных выше задач, однако далеко не всегда сознательно отдает себе в этом отчет относительно внутренних механизмом осуществления. Таким образом, мозг человека действует неалгоритмически, а больше из неких ассоциативных нейронных связей. Очевидно, что натуральный язык характеризуется значительной избыточностью. Избыточность в европейских языках может составлять до 70 процентов. Таким образом, натуральный язык позволяет обеспечить существенную помехоустойчивость передачи данных, набранных из символов алфавитов такого типа языков. Устойчивость русского языка к помехам можно проиллюстрировать фразой "в словох всо глосноо зомононо боквой о", в которой 26 процентов знаков модифицированы «помехой», но сообщение все равно можно распознать. В такой ситуации избыточность является положительным качеством языка.

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

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

«При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак кодируемого алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.» [5]

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

«При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.»

Такие тезисы рассматриваются как теоремы, а, значит, необходимо их доказывать. В рамках данной работы не будем приводить доказательства, так как в данном случае более важно то, что тезисы Шеннона предоставляют нам базу для практического обеспечения возможности кодирования с оптимальными параметрами.

Тем не менее важно сознавать, что из самой теоремы вовсе не следует конкретный способ реализации такого типа кодирования. Получается, что следует привлечь дополнительные изыскания для конкретной реализации алгоритма. Рациональное кодирование с оптимальными принципиально возможно на практике, однако средства реализации могут выбираться различные.

Самым важным в практическом смысле моментом является то, что информацию кодируют бинарно с помощью символов 1 и 0 при М=2. [1]

Шенноном была изучена определнная ситуация, когда при кодировании послания во внутреннем алфавите уже изначально закладывается различная вероятность возникновения символов знаков, а также равная вероятность возникновения символов в выходном алфавите. В такой ситуации справедливо равенство:

К_min (А, В)= I ^(A) / log₂ M= I ^(A) , где I ^(A) - средняя информация на символ внутреннего алфавита.

Гипотетически ограничимся случаем, когда M = 2, т.е. для создания кодов в канале связи применяется только два типа сигналов. Такой тип кодирования именуется двоичным. Символы двоичного алфавита обычно обозначают 0 и 1. Привлекательность двоичных кодов состоит также в том, что всякий элементарный сигнал (0 или 1) хранит в себе один бит данных (log₂M = 1); тогда из (1), теоремы Шеннона получим:

I₁^(A)≤ K⁽²⁾

В таком случае первая теорема Шеннона обеспечивается новым объяснением:

«Если на канале связи нет помех, то средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на символ внутреннего алфавита.»

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

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

Таблица 1. Варианты сочетаний

В том случае, если применяется неравномерный тип кодирования или сигналы разной длительности (ситуации (2), (3) и (4)) для отделения кода одного символа от другого между ними требуется транслировать специфический сигнал – временной разделитель (признак конца символа) или использовать такие модификации кодов, которые являются уникальными, то есть несовпадающими с фрагментами других кодов. При равномерном кодировании одинаковыми по времени сигналами (ситуация (1)) в трансляции разделителя нет необходимости, поскольку отделение одного кода от другого выполняется по суммарной длительности, которая для всех кодов является одинаковой.

Длина двоичного простейшего сигнала показывает количество времени, которое потребуется для трансляции одного бита данных.

Характерно, что для трансляции данных, в среднем приходящихся на символ внутреннего алфавита, необходимо затратить определенное время. Проблему рационализации допустимо также сформулировать иначе: реализовать такой комплекс программно-аппаратных средств кодирования, чтобы суммарная длина кодов при трансляции определенного послания была бы минимальной.

Если есть в наличи источник данных, характеризующийся энтропией Н(х)), а также линия связи с пропускной способностью С, то если С > H(X), то есть возможность зашифровать большое послание таким способом, что она будет транслировано без временных задержек. Если же, наоборот, С < H(X), то трансляция данных без временных задержек нереальна.

Первая теорема Шеннона обеспечивает реализацию системы рационального шифрования дискретных посланий, в которых среднее число двоичных знаков на один знак послания асимптотически стремится к энтропии источника данных при отсутствии помех. [13]

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

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

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

1.3 Вторая теорема Шеннона

Отношение характерной пропускной способности линии связи к скорости передачи знаков алфавита без помех транслируемого послания должно быть больше или равно энтропии трансляции одного знака.[5]

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

Доказательство теоремы основывается на таких умозаключениях: изначально поток X={x_i} записывается знаками из В таким образом, что получается наибольшая пропускная способность, так как линия связи без помех. После этого в поток из В длины n добавляется r знаков, по линии передачи данных передается вновь созданная последовательность из n + r знаков. Количество возможных комбинаций длины n + r превосходит количество комбинаций длины n. Общность всех комбинаций длины n + r может быть разбито на n подмножеств, любому из них сопоставлена одна из комбинаций длины n. При возникновении помех на линии связи последовательность из n + r выводит ее из такого подмножества с минимальной вероятностью. [12]

Данная теорема дает возможность выявлять на стороне-приемнике, какому из общностей принадлежит поврежденная помехами транслируемая комбинация n + r, и тем самым появляется возможность восстановить истинную последовательность длины n.

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

1.4 Помехоустойчивые коды

1.4.1 Классификация помехоустойчивых кодов

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

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

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

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