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

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

2. план

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

3. Клод Шеннон

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

4. Клод Шеннон

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

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

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

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

• I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN)
с учетом возможной неравновероятности
появления I-го сообщения в наборе из I
сообщений, где pi – вероятность того, что
именно i-е сообщение выделено в наборе
из I сообщений.

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

8. Ральф Хартли

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20. Алгоритм Лемпеля-Зива-Уэлча (1984)

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

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

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

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

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

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

• Длительность n=nx*ny
• Входной поток битов – матрица, каждая
строка которой – кодовое слово Сх=(nx; Kx),
Cy=(ny;Ky)

24. Преобразование Бэрроуза-Уиллера (1994)

Преобразование БэрроузаУиллера (1994)
• Алгоритм предварительной обработки
информации, меняющее порядок символов
во входной строке таким образом, что
повторяющиеся подстроки образуют на
выходе идущие подряд
последовательности одинаковых символов

25. Преобразование Бэрроуза – Уиллера этапы

1. Составление таблицы всех циклических
сдвигов входной строки;
2. Обратная сортировка строк таблицы в
алфавитном порядке;
3. Формирование выходной строки из
последнего столбца таблицы и номера
строки, совпадающей с исходной.

26. Кубит (1995)

• Аналог бита в квантовом компьютере –
квантовый объект, находящийся в двух
состояниях одновременно.

27. Fountain код (1998)

• Код, позволяющий передатчику
генерировать бесконечное число пакетов,
кодирующих исходное сообщение

28. Fountain code (1998)

• Формирование:
• Из диапазона 1-k, где k-число блоков в
файле выбирается случайное число d.
• Выбирается d блоков файла и
комбинируются
• Полученный блок передается вместе с
информацией о тех блоках, из которых он
создан

29. Ассимметричная система счисления (2014)

• семейство методов энтропийного кодирования ,
представленных Ярославом (Ярек) Дудой из
Ягеллонского университета , используемых в сжатии
данных с 2014 года благодаря улучшенной
производительности по сравнению с ранее
используемыми методами, В 30 раз быстрее. ANS
сочетает степень сжатия арифметического кодирования
(которое использует почти точное распределение
вероятностей) со стоимостью обработки, аналогичной
затратам на обработку кодирования Хаффмана . В
табличном варианте ANS (tANS) это достигается путем
построения конечного автомата для работы с большим
алфавитом без использования умножения