Без потерь информации - раздел Образование, Основы теории информации и криптографии В Данном Случае Кодирующие Устройство Должно Удовлетворять Следующим Условиям...
В данном случае кодирующие устройство должно удовлетворять следующим условиям:
1. Обеспечивать безошибочную передачу информации, то есть взаимно однозначное соответствие между и .
2. Обеспечивать кодирование наиболее экономным образом (с минимальной избыточностью).
Для выполнения 1-ого требования:
а. Необходимо, чтобы различным буквам алфавита соответствовали различные кодовые слова.
б. Необходимо, чтобы была предусмотрена возможность разделения кодовых слов при их последовательной передаче. Для обеспечения этой возможности:
§ используют специальные разделяющие символы;
§ применяют кодовые слова одинаковой длины (равномерное кодирование);
§ кодовая таблица составляется таким образом, чтобы никакое кодовое слово не являлось началом другого кодового слова.
Для выполнения 2-ого требования необходимо добиваться при кодировании минимальной средней длины кодового слова: , где – это длина -ого слова с учетом разделительной буквы (если она используется).
Теорема 2.1 (Теорема Шеннона о кодировании в дискретных каналах без шума)
При кодировании множества сигналов с энтропией при условии отсутствия шумов средняя длина кодового слова не может быть меньше, чем , где – размер алфавита кодера, 2 – основание алфавита кода.
Если вероятности сигналов не являются целочисленными отрицательными степенями (то есть все вероятности сообщений имеют вид: , где – целое положительное число), достижение указанной нижней границы невозможно, но при кодировании достаточно длинными блоками к ней можно сколь угодно приближаться.
Существует несколько способов, позволяющих получать коды с малой избыточностью; причем все они обладают следующими свойствами:
1. Более вероятным буквам источника ставятся в соответствие более короткие кодовые слова.
2. Никакое кодовое слово не является началом другого более длинного кодового слова.
3. Все буквы алфавита, используемые для передачи информации приблизительно равновероятны.
4. Символы в последовательности на выходе кодера практически независимы.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Без потерь информации
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Задачи, решаемые в рамках теории информации
Теория информации – наука, появившаяся в 1948 г. в результате публикации работы Клода Шеннона «Математическая теория связи».
Ниже представлена структурная схема типичной системы передачи и
И их вероятностные модели
Пусть рассматривается произвольный источник сообщений. Каждое сообщение – это последовательность символов (например, букв русского алфавита, точек и тире в телеграфии, 0 и 1 в компьют
Собственная информация
Очевидно, что задача количественного измерения информации возникла при решении конкретных практических задач. Например, можно стремиться уменьшить количество электрических сигналов, необходимых для
Взаимная информация
Рассмотрим два ансамбля сообщений: . – ансамбль сообщений на входе
Энтропия
Пусть ИДС описывается некоторым дискретным ансамблем: . Тогда энтропия ИДС (или энтропия случайног
Условная энтропия
Пусть имеются два статистически независимых конечных ансамбля символов . Пары символов
Избыточность
Считают, что имеется избыточность, если количество информации, содержащейся в сигнале (энтропия сигнала), меньше того количества, которое этот сигнал мог бы содержать по своей физической природе.
Сжатие без потерь информации
В системах неразрушающего сжатия декодер восстанавливает данные источника абсолютно без потерь (рис. 4).
Сжатие с потерями информации.
Далее приведена система разрушающего сжатия (рис.5):
Рис. 5. Схема сжатия с потерями
&nbs
Основные методы побуквенного кодирования
Простейшими кодами, с помощью которых можно выполнять сжатие информации, являются коды без памяти. Наилучшим из кодов, обладающих свойствами, перечисленными выше, является код Хаффмана.
Ко
Код Хаффмана
Алгоритм Хаффмана дает эффективный способ поиска оптимального вектора Крафта. Код, получаемый с использованием этого оптимального вектора, называется кодом Хаффмана[1].
Далее привед
Код Шеннона
Далее приведен алгоритм кодирования по Шеннону:
Инициализации. Все буквы из алфавита записываются по убыванию вероятностей встречаемости в сообщениях. Каждой букве ставится в
Код Шеннона-Фано
Ниже приведен алгоритм кодирования по методу Шеннона-Фано:
Инициализации. Все буквы алфавита записываются в порядке убывания вероятностей.
Цикл. Всю совокупно
Код Гильбера-Мура
Далее приведен алгоритм кодирования по методу Гильбера-Мура.
Инициализация. Сопоставим каждой букве кумулятивную вероятность
Помехоустойчивое кодирование
Помехоустойчивые коды – это коды, позволяющие обнаружить и (или) исправить ошибки в кодовых словах, которые возникают при передачи по каналам связи. Эти коды строятся таким образом, что для
Коды с обнаружением ошибок
Рассмотрим простейший метод, принадлежащий к этой группе кодов и основанный на проверке на четность.
Схема кодирования: , то
Линейные блоковые коды
Линейным блоковым (n, k) кодом называется множество последовательностей длины
Коды Хэмминга
Код Хэмминга представляет собой один из важнейших классов линейных кодов, нашедших широкое применение на практике и имеющих простой и удобный для технической реализации алгоритм обнаружения и испра
Циклические коды
В отличие от кода Хемминга в циклическом коде используют математические операции не над векторами, а над многочленами. (Напомним, что произвольному вектору
Основные аспекты криптографии
Криптография – (до 70-ых годов) область научной и практической деятельности, связанной с разработкой, применением и анализом шифросистем; (в настоящее время) область науки, техники, практиче
Основные аспекты криптоанализа
Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сформулированное в XIX веке Д. А. Керкхофсом, состоит в том, что безопасность полностью опред
Шеноновские модели криптографии
На рис. 12 представлена общая схема симметричной криптосистемы.
Рис. 12. Схема симметричной крипто
Псевдослучайные последовательности
Случайные числа и их генераторы являются неотъемлемыми элементами современных криптосистем. Ниже приводятся конкретные примеры использования случайных чисел в криптологии:
1. Сеансовые и д
Система шифрования RSA
Данная криптосистема является шифрованием с открытым ключом. Алгоритм RSA[7] опирается на тот факт, что найти большие простые числа вычислительно легко, но разложить большое число на произведение д
Система шифрования Диффи-Хеллмана
Данный алгоритм[8] также является алгоритмом секретного обмена между абонентами ключом. Он основан на трудности вычисления дискретного логарифма.
Рассмотрим простейшую схему создания общег
Разложение на множители (факторизация)
Разложение на множители числа (например, ) является одной из древнейших проблем теории чисел. Приступая к факторизации числа, следует снача
Вычисление в поле Галуа
Напомним некоторые определения из алгебраических основ:
Поле – это множество
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Шеннон К. Теория связи в секретных системах. / В кн. Лекции по теории информации и кибернетике.–М.: ИЛ, 1963. Харин Ю.С., Берник В.И., Матвеев Г.В., Агиевич С.В. Матем
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов