Системы связи и теория информации

Обобщенные модели передачи и хранения информации

Типы кодирования

Обобщенная модель системы передачи информации

Исторические вехи в теории и технике кодирования

1837: Электрический телеграф и код Морзе (S. Morse).

1875: Буквопечатающий телеграф и код Бодо (E. Baudot).

1924, 1928: Работы Найквиста (H. Nyquist) и Хартли (R. Hartley) по исследованию каналов связи и скорости передачи информации.

1947-48: Фундаментальные работы К. Шеннона (C. Shannon) и В.А. Котельникова, ознаменовавшие создание теории информации.

1949-50: Первые помехоустойчивые коды: Голей, (M. Golay), Хэмминг (R. Hamming).

1952: Алгоритм Хаффмена (D. Huffman) кодирования источника.

1959-60: Коды БЧХ (R. Bose, D. Ray-Chaudhuri, A. Hochquenghem) и Рида- Соломона (I. Reed, G. Solomon).

1967: Алгоритм Витерби (A. Viterbi) декодирования сверточных кодов.

1976-78: Криптография с открытым ключом (W. Diffie, M. Hellman, R. Rivest, A. Shamir, A. Adleman and others).

1977-78: Словарные алгоритмы компрессии данных (A. Lempel, J. Ziv).

1979-1982: Модуляция на основе решетчатых кодов (G. Ungerboek).

1993: Турбо-коды (C. Berrou, A. Glavieux, P. Titimajshima).

Источники сообщений, количество информации, энтропия

1.2.1 Идея определения количества информации

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

Математическая модель источника информации. Дискретные и непрерывные источники

Дискретным называется источник, множество X возможных сообщений которого конечно или счетно X={x₁, x₂, …}. Подобный источник полностью описывается набором вероятностей сообщений: p(x_i), i=1,2, … . Условие нормировки:

Рассматривая непрерывные источники, мы ограничимся только теми, несчетный ансамбль которых может быть ассоциирован с непрерывной случайной переменной, т.е. описан в терминах плотности вероятности W(x).

Условие нормировки:

Количество информации в сообщении

Аксиомы количества информации (требования к универсальной информационной мере):

1. Количество информации в сообщении x зависит только от его вероятности:

2.Неотрицательностьколичества информации:

причем I(x)=0толькодля достоверного события (p(x)=1).

3. Аддитивность количества информации для независимых сообщений:

.

Единственной функцией, удовлетворяющей этим трем аксиомам оказывается логарифм вероятности сообщения:

.

Единица измерения количества информации зависит от выбора основания логарифма. Традиционное основание два дает единицу измерения количества информации, называемую битом (binary digit).

Энтропия дискретного источника

Энтропия дискретного источника есть среднее количество информации в его сообщениях:

Свойства энтропии:

1.Энтропия неотрицательна:

где равенство нулю имеет место только для полностью детерминированного (неслучайного) источника.

2.Энтропия ограничена сверху соотношением

с равенством только для ансамбля M равновероятностных сообщений.

3. Энтропия ансамбля пар сообщений, генерируемых двумя независимыми источниками аддитивна:

Энтропия двоичного источника (p – вероятность одного из двух сообщений):

Кодирование источника

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

При кодировании источника M сообщений ансамбля источника отображаются на M кодовых слов или кодовых векторов,элементы которых принадлежат некоторому алфавиту. Код – это попросту множество всех кодовых слов. Если длины всех слов одинаковы, код называется равномерным или фиксированной длины (пример – ASCII код). Коды, в которых допускаются разные длины слов, называются неравномерными (переменной длины).

Цель кодирования источника – наиболее экономное представление сообщений, т.е. отображение их словами по возможности меньшей длины.