Помехоустойчивое кодирование

Казанский Государственный  Технический Университет им. А.Н. Туполева

Институт радиоэлектроники и телекоммуникаций

Кафедра Радиоэлектронных и  Телекоммуникационных систем

__________________________________________________________________

 

 

 

 

Пояснительная записка к  курсовой работе по курсу 

ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ  СВЯЗИ

на тему

«Помехоустойчивое кодирование»

 

 

 

 

 

 

 

Выполнил: 
Студент группы 4404 
Супрунов Д.О.

Проверил: 
Доцент кафедры РТС 
Коробков А.А.

 

 

 

 

Казань 2009

 

Задание

 

СОДЕРЖАНИЕ

 

1. ВВЕДЕНИЕ 4

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 5

3. ПРАКТИЧЕСКАЯ ЧАСТЬ 10

4. ЗАКЛЮЧЕНИЕ 13

5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14

 

 

1. ВВЕДЕНИЕ

Теория кодирования возникла в конце 40-х годов с появлением работ Голея, Хэмминга и Шеннона. Истоками теории являются инженерные задачи, но ее развитие приводит к все  более утонченным математическим методам. Первые два автора заложили основу алгебраическим методам кодирования, Шеннон предложил и исследовал понятие случайного кодирования.

В современных информационных системах важнейшей задачей является обеспечение информационной безопасности, связанной с методами криптографии, теоретические основы которой заложил Шеннон во второй своей важнейшей работе.

В течение большей части  второй половины прошлого века математики и специалисты по аппаратным и программным средствам ЭВМ и проблемам передачи данных упорно бились над тем, чтобы выработать технологию, позволяющую кодировать информацию таким образом, чтобы  
при разрушении случайно выбранных ее блоков, эти блоки можно было восстановить. После того, как была заложена математическая основа для кодирования, разработаны эффективные алгоритмы кодирования и декодирования, технология ближе к концу прошлого века стала более  
или менее устоявшейся. Технология применяется при приеме / передаче данных в сетях и при чтении / записи данных на большинстве носителей информации, «на лету» обнаруживая и по возможности исправляя искаженные блоки данных. В связи с бурным развитием хакерской мысли эта технология является весьма актуальной в настоящее время.

 

 

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Теория помехоустойчивого кодирования  базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал  теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой  код, при котором вероятность  ошибочного декодирования будет  сколь угодно мала.

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

В настоящее время наибольшее внимание уделяется двоичным равномерным  корректирующим кодам. Они обладают хорошими корректирующими свойствами и их реализация сравнительно проста.

Помехоустойчивое  кодирование [2] - кодирование, состоящее в целенаправленном введении избыточных символов, с целью обеспечения возможности обнаружения и исправления ошибок.

Обнаружить ошибку [2] - зафиксировать факт, что в данной кодовой комбинации присутствует ошибка.

Исправить ошибку [2] - точно указать разряд в кодовой комбинации, в котором произошла ошибка и исправить её (инвертировать разряд с ошибкой).

Основой помехоустойчивого  кода является простой двоичный код. Расчёт количества разрядов необходимых  для кодирования конечного числа  сообщений в простом коде производится по формуле (1) [3, стр.22], где N-количество кодируемых сообщений, m-используемая, при кодировании, система исчисления.

	(1)
	(2)
	(3)
	(4)

При введении избыточных символов в длина кодовой комбинации увеличивается и определяется в соответствии с формулой (2) [3, стр.22], где r-количество избыточных символов, формула (3) [3, стр.22], где -минимальное кодовое расстояние по Хэммингу.

Кодовое расстояние по Хэммингу [3] - это число разрядов, в которых две кодовые  комбинации не совпадают, формула (4) [3, стр.22].

Минимальное кодовое  расстояние по Хэммингу [2] - это минимальное расстояние по Хэммингу между всеми разрешёнными кодовыми комбинациями.

Разрешёнными  кодовыми комбинациями [2] являются все комбинации простого кода с добавленными, по определённому правилу, избыточными символами.

Запрещённые кодовые  комбинации [2] - это все промежуточные комбинации, которые позволяют обнаруживать или исправлять возникающие в разрешённых кодовых комбинациях ошибки.

Возникающие в кодовых  комбинациях ошибки характеризуются  параметром q- кратностью ошибки.

Кратность ошибки [2] - количество разрядов, в которых произошла ошибка в разрешённой кодовой комбинации.

	(5)
	(6)
	(7)

Кратность обнаруживаемых ошибок [3] - количество разрядов, в которых ошибки  будут гарантированно обнаружены (5) [2].

Кратность исправляемых ошибок [3] - количество разрядов, в которых ошибки будут гарантированно исправлены (при чётном значении формула(6) [2], при нечётном – формула (7) [2]).

Ошибки кратностью превышающей  значение могут быть обнаружены, если кодовая комбинация с ошибкой не переходит в другую разрешенную кодовую комбинацию. Исправление ошибок кратностью превышающей значение не возможно, т. к. алгоритм поиска разрядов с ошибкой связан с фиксированными математическими операциями, приводящими к ограниченному количеству результатов.

Из формулы (5) [2] видно, что  кратность обнаруживаемых ошибок и  минимальное кодовое расстояние по Хэммингу зависят линейно и  прямо пропорционально. В формулах (6) [2] и (7) [2] зависимость кратности  исправляемых ошибок от минимального кодового расстояния по Хэммингу так  же прямо пропорциональна, однако, вероятно присутствуют некоторые «провалы»  роста исправляющей способности.

Для получения наглядной  количественной оценки надежности системы  связи, необходимо получить вероятность  ошибочного декодирования и  вероятность необнаруженной ошибки. Зная вероятность ошибки при передаче одного символа по каналу связи p можно вычислить вероятность правильного прихода импульса (8) [2].

	(8)
	(9)
	(10)

Кратность ошибки для вычисления вероятности ошибочного декодирования  больше кратности исправляемых ошибок т.к. исправленные ошибки не могут вызвать  ошибочного декодирования (9) [2]. Подставляя (8), (9), (10) в (11) найдём вероятность ошибочного декодирования.

Вероятность ошибочного декодирования [3] – вероятность, с которой кодовая комбинация будет декодирована ошибочно (11) [2].

Как уже говорилось выше, ошибки могут быть не обнаружены, если кодовая комбинация с ошибкой  переходит в другую разрешенную  кодовую комбинацию, поэтому для  расчёта вероятности необнаруженной ошибки кратность ошибок берётся  равной минимальному кодовому расстоянию по Хэммингу (12) [2].

Вероятность необнаруженной ошибки [3] – вероятность, с которой ошибочная кодовая комбинация будет декодирована как разрешённая (13) [2].

Время передачи по каналу одной  кодовой комбинации зависит от скорости передачи системы связи  и от минимальной длины кодовой комбинации (2) [2], формула (14) [2].

	(11)
	(12)
	(13)
	(14)

 

 

3. ПРАКТИЧЕСКАЯ ЧАСТЬ

Для решения поставленной задачи минимальное кодовое расстояние d будем находить методом подбора: d=[1;∞]  так, чтобы выполнялось условие:

_{до тех  пор, пока:}

_{Следующим действием вычисляем  кратность обнаруживаемых ошибок по формуле (5) и кратность исправляемых ошибок по формулам (6), (7):}

	(5)
	(6)
	(7)

_{Все вышеперечисленные  вычисления необходимо провести для различных  вероятностей ошибки при передаче символа  по каналу, указанной  в задании: p=0.1, 0.2, 0.3}

_{Ниже  представлен график зависимости минимального кодового расстояния d от вероятности ошибки при передаче символа по каналу:}

Рис.1. График зависимости минимального кодового расстояния от вероятности ошибки при передаче символа по каналу

_{Для вычисления пропускной способности канала воспользуемся формулой:}

(15)

_{Также вычисления проводим для  p=0.1, 0.2, 0.3.}

_{По полученным данным строим график зависимости пропускной способности канала от вероятности ошибки при передаче символа  по каналу:}

Рис.2. График зависимости пропускной способности канала от вероятности ошибки при передаче символа по каналу

 

 

 

 

 

 

4. ЗАКЛЮЧЕНИЕ

В ходе выполнения данного  курсового проекта мы исследовали  методы помехоустойчивого кодирования.

Основной задачей в  проделанной работе являлось обеспечение  вероятности необнаруженной ошибки, а также вычисление минимального кодового расстояния для различных  вероятностей ошибки при передаче символа  по каналу, нахождение кратности обнаруживаемых и исправляемых ошибок, а также  пропускной способности канала.

 После выполнения задания  нами были сделаны следующие  выводы: с увеличением вероятности ошибки при передаче символа по каналу минимальное кодовое расстояние увеличивается.

 

5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Зюко А.Г. и др. Теория передачи сигналов. - М.: Радио и связь, 1986.
2. Седов. С.С. Конспект Лекций Теория Электрических Связей
3. Седов С.С., Козлов С.В. Теория электрической связи, Методическое пособие по курсовой работе, Казань, 2003.
4. Седов С.С., Надеев А.Ф. Методические указания к лабораторной работе по курсу «Теория электрической связи» «Исследование принципов помехоустойчивого кодирования»
5. http://ru.wikipedia.org/wiki/Помехоустойчивое_кодирование