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

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

29 тема из списка

план

• Что изучает теория информации?
• Клод Шеннон и его труды
• Ральф Хартли
• Кодирование Хаффмана
• Коды Рида-Маллера (1954)
• Коды Рида-Соломона (1960)
• Коды Слепиана-Вольфа (1973)
• Трелис-модуляция (1976)
• Создание zip- формата deflate(1989)
• Турбо-коды (1993)

Клод Шеннон

• Родился 30 апреля 1916 в Петоски, штат Мичиган
• Умер 24 февраля 2001 г. в Медфорд Массачусетс

Клод Шеннон

• «Математическая теория связи» (1948)– начало теории информации. Основные положения:
• бит (англ. Binary digiT) – наименьшая единица информации
• понятие энтропии – меры неопределенности появления какого-либо символа первичного алфавита в сообщении

Теоремы Шеннона

• Теорема Шеннона-Хартли – определение пропускной способности канала C с белым гауссовым шумом как функции средней мощности принятого сигнала S , средней мощности шума N , и ширины полосы пропускания W

Теорема Шеннона-Хартли

• I = — ( p 1 log 2  p 1  + p 2  log 2  p 2  + . . . + p N  log 2  p N ) с учетом возможной неравновероятности появления I- го сообщения в наборе из I сообщений, где p i – вероятность того, что именно i- е сообщение выделено в наборе из I сообщений.

Формула Шеннона

Ральф Хартли

• Американский ученый-электронщик (30. XI.1888 – 1.V.1970) процесс получения информации = выбор одного сообщения из N равновероятных сообщений, количество информации – формула Хартли
• I=log 2 N, Где N- множество равновероятных сообщений. (1928 г)

Дэвид Хаффман

• Автор алгоритма «жадного кодирования» (1952) - алгоритма, заключающегося в принятии локально  оптимальных решений  на каждом этапе, допуская, что конечное решение также окажется оптимальным.

АЛГОРИТМ Хаффмана

• Последовательное суммирование единиц с наименьшим информационным весом и объединение значений в дерево (дерево Хаффмана)

Дерево Хаффмана

Дерево Хаффмана

• Бинарное дерево, у которого:
• Листья помечены символами, для которых разрабатывается кодировка
• Узлы помечены суммой вероятностей появления всех символов, соответствующих листьям поддерева, корнем которого является соответствующий узел

Алгоритм построения

• Шаг 1. Символы входного алфавита образуют  список  свободных узлов. Каждый  лист  имеет  вес , который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемый текст.
• Шаг 2. Выбираются два свободных узла дерева с наименьшими весами.
• Шаг 3. Создается их родитель с весом, равным их суммарному весу.
• Шаг 4. Родитель добавляется в  список  свободных узлов, а двое его детей удаляются из этого списка.
• Шаг 5. Одной  дуге , выходящей из родителя, ставится в соответствие  бит  1, другой –  бит  0.
• Шаг 6. Повторяем шаги, начиная со второго, до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться  корнем дерева .

Коды Рида-Маллера

• Общая идея матричных кодов – умножение двоичной строки на фиксированную матрицу А – производящую матрицу кода.
• К-число информационных символов, n – длина блока.

Коды Рида-Соломона

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

Коды Рида-Соломона

Код Слепиана-Вольфа

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

Трелис-модуляция (1976)

• Совместные кодирование и модуляция, улучшающая спектральную эффективность сигнала по сравнению с раздельными методами.

Трелис-модуляция

• Повышает помехоустойчивость за счет добавления трелис-бита
• Декодер Витерби используется для анализа поступающих последовательностей битов.
• Способ обеспечивает передачу данных на скоростях до 9600 бит/с и более по стандартному каналу с полосой пропускания 300-3400 Гц.

Создание .zip формата сжатия DEFLATE (1989)

• Алгоритм сжатия без потерь, использующий комбинацию алгоритмов LZ77 и Хаффмана.
• Характерной чертой алгоритма DEFLATE является прямая зависимость между степенью сжатия и затратами времени на сжатие.

Турбо-коды (1993)

• Параллельные блоковые каскадные коды, способные исправлять ошибки
• Двумерный блочный код изображается в виде прямоугольника и основан на двух систематических кодах – горизонтальном (С х =( n x )) и вертикальном (C y =(n y )
• Общая информационная емкость кода – k=k x *K y

Турбо-коды (1993)

• Длительность n=n x *n y
• Входной поток битов – матрица, каждая строка которой – кодовое слово С х =( n x; K x ), C y =(n y ;K y )