Информации теория

Теория информации (ТИ) возникла в 1948 году, когда были опубликованы основополагающие работы американского инфенера и математика Клода Шеннона «Математическая теория связи» и «Связь при наличии шума» [1]. Основной теоретико-вероятностной задачей ТИ является проблема кодирования для передачи данных по каналу связи с шумом. Не нарушая общности, данную задачу в дискретном случае можно описать приводимой ниже блок-схемой, содержащей двоичные источник и канал:

,  ,

,  ,  ,

,  .

• Источник генерирует предназначенную для адресата двоичную (из 0 и 1) последовательность длины , которая называется сообщением источника и может быть случайной (с точки зрения адресата) последовательностью с известным, или неизвестным, распределением вероятностей . Значения , для которых вероятности , называются информационными словами. Число информационных слов обозначим через . В частности, может принимать равновероятные значения, т.е. и для любого .
• Для передачи по дискретному каналу связи сообщение поступает на вход кодера, который отображает (кодирует) его с помощью функции кодирования , , , в сигнал на входе канала . Число называется временем работы канала для передачи сообщения , а число – двоичной скоростью передачи по каналу связи. Для сообщения с равновероятными значениями скорость определяет число двоичных информационных символов, передаваемых за единицу времени работы канала. Частным случаем кодера является линейный код, задаваемый порождающей -матрицей . При этом функция кодирования задается как операция произведения в двоичном поле матрицы на столбец (информационное слово) , т.е. .
• Дискретный канал связи с шумом описывется условным распределением, т.е. набором условных вероятностей , , где – условная вероятность получения на выходе канала двоичной последовательности (выходного сигнала) , если входной сигнал . Примером является стационарный дискретный канал связи без памяти (ДКБП), в котором изменения символов в разные моменты времени передачи происходят независимо, т.е. , с одним и тем же условным распределением, задаваемым переходной матрицей канала , . В частном случае двоичного симметричного канала без памяти (ДСК) вероятность ошибки (искажения) при передаче одного символа задается переходной вероятностью , , т.е. . При этом вероятность правильной передачи двоичного символа .
• Выходной сигнал канала связи поступает на вход декодера, который с помощью декодирующей функции , , , преобразует его в сообщение адресата . Как пример декодирующей функции укажем декодирование по максимуму правдоподобия (МП-декодиование), когда при заданной функции кодирования результат декодирования совпадает с одним из тех информационных слов , где достигается .
• Пара кодирование-декодирование называется методом передачи сообщения источника по каналу . В качестве критерия метода передачи рассматривается вероятность несовпадения сообщения источника с сообщением адресата, т.е. число , называемое вероятностью ошибки. Отметим важное свойство оптимальности МП-декодирования: если сообщение принимает равновероятные значения, то для любой функции кодирования вероятность ошибки минимизируется при соответствующем МП-декодировании. Проблема кодирования для передачи информации по каналу связи формулируется следующим образом. Для заданных распределения вероятностей , канала связи и числа требуется построить метод передачи с вероятностью ошибки .

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

Данные результаты описываются с помощью введенной в теорию вероятностей К. Шенноном числовой характеристики совместного распределения пары случайных величин, называемой информацией. Пусть – фиксированное целое число, а  обозначает -ичный алфавит, составленный из целых чисел от 0 до . Пусть , , , – распределение вероятностей на , а матрица , где , , , является матрицей условных (переходных) вероятностей, т.е.

,  , .

Через  обозначим пару случайных величин с совместным распределением

, , ,

для которого распределение вероятностей и матрица условных вероятностей являются соответствующими маргинальным и условным распределениями вероятностей. Число

,

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

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

Теорема Шеннона [1, 2, 3]. Для ДКБП справедливы следующие утверждения:

1. Обратная теорема. Если , то , т.е. при и не существует метода передачи с вероятностью ошибки, стремящейся к нулю.
2. Прямая теорема. Если , то , т.е. при и существует метод передачи с вероятностью ошибки, стремящейся к нулю.

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

Список литературы

[1] К. Шеннон, «Сборник работ по теории информации и кибернетике», М.: ИЛ, 1963.

[2] Р.Г. Галлагер, «Теория информации и надежная связь», М.: Сов. радио, 1974.

[3] T.M. Cover, J.A. Thomas, «Elements of information theory», New York: Wiley, 1991.

А.Г. Дьячков,    А.Н. Воронина