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