Теория кодирования

     Пусть Ar — слово в алфавите А и Br =G(Ar) — слово в алфавите В. Код называется обратимым, если для любого слова Br =G(Ar) в алфавите В существует единственное преобразование G-1(Br)= Ar . То есть, по слову Br в алфавите В, всегда однозначно восстанавливается слово Ar в алфавите А, из которого было образовано слово Br.

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

     Примером  необратимого кодирования является перевод текста с одного естественного языка на другой. (Обратный перевод побуквенно обычно не соответствует исходному тексту.)

     Чтобы код был обратимым, необходимо:

     1) чтобы разным символам входного  алфавита А были сопоставлены  разные кодовые комбинации;

     2) чтобы никакая кодовая комбинация  не составляла начальной части  какой-нибудь другой кодовой комбинации.

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

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

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

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

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

     Помехи  в передачи информации - свойство отнюдь не только технических систем. Это - вполне обычное дело в быту. Пример был выше; другие примеры - разговор по телефону, в трубке которого "трещит", вождение автомобиля в тумане и т.д. Чаще всего человек вполне прилично справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 70%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение "в словох всо глосноо зомононо боквой о". Здесь 26% символов "поражены", однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.

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

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

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

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

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

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

     Таким образом, оптимальное кодирование  принципиально возможно.

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

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

     К_min (А, В)= I ^(A) / log₂ M= I ^(A) , 

     здесь I ^(A) - средняя информация на знак первичного алфавита.

     Ограничим себя ситуацией, когда M = 2, т.е. для представления  кодов в линии связи используется лишь два типа сигналов – наиболее просто реализуемый вариант. Подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1. Удобство двоичных кодов и в том, что каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log₂M = 1); тогда из (1), теоремы Шеннона:  

     I₁^(A)≤ K⁽²⁾ 

     и первая теорема Шеннона получает следующую интерпретацию:

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

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

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

 

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

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

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

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

     Первая  теорема Шеннона (переформулировка). [13]

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

     Какие же могут быть особенности вторичного алфавита при кодировании:

     Элементарные  коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (≠).

     Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)

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

 

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

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

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

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

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