Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-12-12 | 89 |
5.00
из
|
Заказать работу |
Рассмотрим теперь следующую более общую схему.
Источник |
Кодер |
Кодер II |
Код |
F |
Канал |
F-1 |
Декодер II |
Декодер I |
Получатель |
Потери информации
Избыточность
Часть рисунка вне овала соответствует изучаемой раньше схеме, т.е.кодер (Кодер I) и декодер (Декодер I) – это, например, устройства реализующие алгоритм Хаффмена или что-то подобное. Но в отличие от предыдущего случая (канала без шума) добавился еще один кодер (Кодер II) и декодер (Декодер II). Их задача – обеспечить защиту передаваемой информации от шума в канале. Под шумом можно понимать самые разные искажения сигнала при передаче по каналу. Примеры моделей этих искажений приведены в следующем разделе.
Модели каналов.
1) Двоичный симметричный канал
P |
1-P |
1-P |
P |
P > 1/2
0 0
Канал называется двоичным, потому, что по нему передаются два сигнала: 0 и 1. Симметричность заключается в том, что они подвергаются искажениям в одинаковой степени. Вероятность правильной передачи P>1/2. (Ниже вероятность ошибки для удобства будем обозначать через p=1-P. При этом всегда будет понятно, о чем идет речь. Заметим, что критичный случай именно p=1/2. Если, например, p>1/2, то на приеме можно поменять местами 0 и 1. Ниже будет показано, что случай p=1/2 соответствует нулевой пропускной способности канала. Но это понятно и без всякой математики: что бы не попало в канала – на выходе с равной вероятностью будет принят или 0 или 1.
2)
P |
1-P |
1-Q |
Q |
1 1
P> 1/2, Q> 1/2
0 0
3) Двоичный стирающий канал
P |
1-P |
1-P |
P |
0 0
Пример:
Передаем 11011, p = 4/5, ошибка в четвертом символе.
Для двоичного канала на приеме может быть получена последовательность: 11001
Для канала со стиранием в этом случае будем иметь: 110х1.
Это уже существенно другой тип искажений. В отличие от предыдущих случаев, здесь мы всегда уверены в том, что полученные 0 или 1 были именно такими и переданы, а на месте искаженных символов принимает новый символ x. В предыдущих случаях мы не знаем, какие из полученных сигналов искажены (и есть ли искажения вообще). Нахождение и исправление таких искажений приводит к сложным математическим задачам Теории кодирования. В случае же канала со стиранием такой подход тоже можно использовать, но можно свести задачу на уровень Протокола. Например, можно просто перезапрашивать искаженные символы.
4) Канал с выпадением.
P |
1-P |
1-P |
P |
0 0
Пример:
Передаем 11011, p = 4/5, ошибка в четвертом символе.
Для двоичного канала на приеме может быть получена последовательность: 11001
Для канала с выпадением в этом случае будем иметь: 1101.
Для дальнейшего рассмотрения мы ограничимся одним случаем: двоичным симметричным каналом. Технически все полученные для этого случая результаты могут быть обобщены как на случай ассиметричного канала, так и на случай канала, передающего не два символа, а q символов.
Математические же модели, используемые для защиты информации от искажений в каналах с выпадением и со стиранием существенно отличны.
8.2 Необходимые определения.
Пусть Bn - булев куб размерности n.
Опр. Кодом C называется произвольное подмножество .
ПустьM– мощность множества C. Элементы этого подмножества будем называть кодовыми словами.
Опр. Пропускная способность канала - C (p) = 1 – H (p), где - энтропия канала.
Как раз для случаяp=1/2 энтропия равна единице, что соответствует полной неопределенности (абсолютному беспорядку), а пропускная способность канала нулевая.
Опр. Скорость передачи кода .
Если число слов, подлежащих передаче в канал, равно 2 k, то
- скорость передачи.
Опр. Расстояние Хемминга - это количество различных бит в x и y.
Пусть | x | -количество единиц в (норма или весx). Тогда очевидно, что
.
Опр. Кодовое расстояние .
Опр. (n,M,d)-код – это код C,такой, что | C | = M, C = { xi }, xi Bn, d (C) = d.
Пример кода для канала с выпадением.
Построение кодов для таких каналов – сложные комбинаторные задачи. Проблема соотношения пропускной способности канала и скорости передачи кода отходит при этом на второй план. Приведем простейший пример.
Пусть дан код C, α=(α1,α2,…,αn) – кодовое слово. Положим .
Опр. Cnk – кодом называется множество слов α из Bnтаких, чтоw(α)=0 (modk).
Утв. Cnk – код является кодом с исправлением одного выпадения при k>n.
Доказательство. Пусть в слове αвыпал символ. В результате получилось слово β=(β1, β2,…, βn-1) длины n-1. Пусть правее выпавшего символа расположено N1 единиц и N0нулей.Тогда, если выпал 0, тоw(α)-w(β)= N1, а, если 1, тоw(α)-w(β)= N -N0.В обоих случаях
0≤w(α)-w(β)≤N<k.
ПустьΔβ – наименьший неотрицательный вычет числа w(β) поmodk(Это разность kp-w(β), где kp –минимальное число, кратноеk и не меньшееw(β)).
Тогда из того, что w(α)=0 (modk) получаемw(α)-w(β)=Δβ. Так как N1≤|β|<N -N0, то на основании сравнения чисел |β| и Δβ можно определить выпавший символ.
1. Если |β| ≥ Δβ, то нужно вставить в слово символ 0 так, чтобы правее него было Δβ единиц.
2. В противном случае вставляется 1 так, чтобы правее нее было n- Δβ нулей.
Утверждение доказано.
Пример.
Пусть N=6 и k=7. Если в слове α=110100 выпал первый символ, то получилось β=10100. В этом случае:|β| =2,w(β)=4, поэтому Δβ=3.Так как |β| <Δβ, то исходное слово получается, если в принятом слове отсчитать справа n-Δβ нулей и поставить перед ними 1.
Упражнение. В качестве упражнения можете проверить, что подобный код может исправлять одну ошибку типа вставки (вместо выпадения появляется лишний символ) или замещения 0 на 1. А при k≥2nон может исправлять одну любую из этих трех видов ошибок.
Если же выпадает несколько символов, то задача декодирования может сводится к задаче восстановления слова по фрагментам.
Опр. Фрагментом слова α называется любое слово β, буквы которого образуют подпоследовательность последовательности букв слова α.
Зная n иp можно прогнозировать длины фрагментов l. Критерий восстановления слова по фрагментам с использованием этих параметров даст k– необходимое количество фрагментов для восстановления. Отсюда можно построить алгоритм декодирования с перезапросами: декодер, получив фрагмент принимает решение о его перезапросе. Набрав необходимое количество фрагментов, декодер произведет декодирование.
Заметим, что проколы такого типа (Ack – Nac)используются на втором уровне моделиOSI для случая кодов с обнаружением ошибок. (В таких кодах декодер не производит исправления ошибки, а только фиксирует ее появление. В случае же этого самого появления и используется протокол с перезапросом.)
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!