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