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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ…………………………………………………………………………………………..3

ГЛАВА 1. Общие сведения о помехоустойчивом кодировании.………………………………...4

1.1. Помехоустойчивость…………………………………………………………………………....5

1.2. Основные принципы помехоустойчивого кодирования…………………………………….5

1.3. Основные параметры  помехоустойчивых кодов……………………………………………..9

ВЫВОДЫ ПО 1 ГЛАВЕ……………………………………………………………………………11

ГЛАВА 2. Коды помехоустойчивого кодирования информации……………………………….12

2.1. Краткая классификация помехоустойчивых кодов………………………………………….12

2.2. Основные помехоустойчивые коды…………………………………………………………..15

2.3. Особенности практического кодирования…………………………………………………...23

ВЫВОДЫ ПО 2 ГЛАВЕ……………………………………………………………………………28

ЗАКЛЮЧЕНИЕ……………………………………………………………………………………..29

ЛИТЕРАТУРА………………………………………………………………………………………30

 

 

ВВЕДЕНИЕ

 

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

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

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

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

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

 

Цель данной курсовой работы: изучение основных помехоустойчивых кодов.

Объект: Кодирование информации.

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

Задачи:

• изучить литературу по теме исследования;
• определить понятие помехоустойчивости;
• рассмотреть основные принципы помехоустойчивого кодирования;
• дать краткую классификацию помехоустойчивых кодов;
• рассмотреть основные помехоустойчивые коды;
• привести особенности практического кодирования.

 

ГЛАВА 1. Общие сведения о помехоустойчивом кодировании

 

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

Код принимаемого языка определяется алфавитом символов и правилами их комбинирования, т.е. правилами построения знаков различного ранга. Число символов в алфавите называется основанием кода. Знаки второго ранга называются кодовыми словами. Если все кодовые слова имеют одинаковое число символов, то код называется равномерным, в противном случае код называется неравномерным. Пример применения равномерного кода приведен в таблице 1.

 

Таблица 1.    

Номер сообщения	0	1	2	3	4	5	6	7
Кодовое слово	000	001	010	011	100	101	110	111

 

Кодовые слова в этом примере  являются записью номера сообщения  в равномерном двоичном коде (системе счисления) при числе символов в коде, равном n. Для повышения надежности связи в ряде случаев используют не все кодовые комбинации , где q – основание кода, а лишь часть из них M < N .

Символы кода можно передать различным  образом. Например, символы 1 и 0 можно  передать положительным (или отрицательным) напряжением и паузами, гармоническими колебаниями одной частоты и  паузами, колебаниями различной частоты  или фазы (см. рис.1).

 

Рис. 1. Колебания частот

 

Сигналы символов могут быть простыми и сложными.

Для передачи информации могут использоваться знаки, описываемые комбинацией символов некоторого конечного алфавита. В общем случае способ формализованного описания различных сообщений называется представлением сообщений. Кодирование символами конечного алфавита является одним из способов представления сообщений.

 

1.1. Помехоустойчивость

 

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

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

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

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

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

 

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

 

 

 Кодирование с исправлением ошибок, по существу, представляет собой метод обработки сигналов, предназначенный для увеличения надежности передачи по цифровым каналам. Хотя различные схемы кодирования очень не похожи друг на друга и основаны на различных математических теориях, всем им присущи два общих свойства. Одно из них – использование избыточности. Закодированные цифровые сообщения всегда содержат дополнительные, или избыточные, символы. Эти символы используют для того, чтобы подчеркнуть индивидуальность каждого сообщения. Их всегда выбирают так, чтобы сделать маловероятной потерю сообщением его индивидуальности из-за искажения при воздействии помех достаточно большого числа символов. Второе свойство состоит в усреднении шума. Эффект усреднения достигается за счет того, что избыточные символы зависят от нескольких информационных символов. Для понимания процесса кодирования полезно рассмотреть каждое из этих свойств отдельно.

Вначале будет рассмотрен двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя вероятность ошибки равна Р=0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем, если считать, что такой блок содержит не более трех ошибок, то мы будем неправы лишь два раза на миллион блоков. Кроме того, вероятность, что мы окажемся правы, возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Простые вычисления помогают понять, насколько верным является это утверждение. Рассмотрев, например, тот же канал, можно вычислить вероятность того, что доля ошибочных символов превышает значение p, и построить график этой функции для нескольких значений длины блока.

 

Рис. 2. Вероятность того, что доля ошибочных символов e/N в блоке длиной N превышает р при вероятности Р _e=0,01

 

Кривые на рис.2 показывают, что при обработке символов блоками, а не одного за другим можно уменьшить общую частоту ошибок. При этом потребуется, чтобы существовала схема кодирования, нечувствительная к ошибкам в некоторой доле символов блока и не приводящая при этом к потере сообщением своей индивидуальности, т. е. не приводящая к ошибочному блоку. Из графиков для различных длин блоков видно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероятность ошибки блока. Он показывает также, что при фиксированной вероятности ошибки блока доля ошибок, которые нужно исправлять, уменьшается при возрастании длины блока. Сказанное свидетельствует о резервах улучшения характеристик при усреднении шума и о том, что эти резервы возрастают при увеличении длины блока. Таким образом, длинные блоковые коды эффективнее коротких. После того как установлена целесообразность исправления ошибок в символах, возникает следующий логичный вопрос: как это сделать? Ключ лежит в избыточности. После некоторых размышлений читатель поймет, что при исправлении ошибок в сообщении, представляемом последовательностью из n двоичных символов, очень важно учесть, чтобы не все 2ⁿ возможных последовательностей представляли сообщения. В самом деле, когда каждая из возможных принятых последовательностей n символов представляет некоторое сообщение, нет никаких оснований считать, что одна последовательность является более правильной, чем любая другая. Продолжая рассуждать таким же способом, можно ясно увидеть, что для исправления всех наборов из t или менее ошибок необходимо и достаточно, чтобы каждая последовательность, представляющая сообщение, отличалась от последовательности, представляющей любое другое сообщение, не менее чем в 2t+1 местах. Например, для исправления всех одиночных или всех двойных ошибок в символах нужно, чтобы каждые две последовательности, представляющие разные сообщения, отличались не менее чем в пяти символах. Каждая принятая последовательность, содержащая два ошибочных символа и, следовательно, отличающаяся от посланной последовательности ровно в двух местах, будет всегда отличаться от всех других последовательностей, представляющих сообщения, не менее чем в трех местах. Число позиций, в которых две последовательности отличаются друг от друга, будем называть расстоянием Хемминга d между этими двумя последовательностями. Наименьшее значение d для всех пар кодовых последовательностей называется кодовым расстоянием и обозначается d_min. Поскольку d_min всегда должно быть на единицу больше удвоенного числа исправляемых ошибок, можно написать t=[(d_min-l)/2], где [ ] обозначает целую часть. Параметр t указывает, что все комбинации из t или менее ошибок в любой принятой последовательности могут быть исправлены. Имеются модели каналов, в которых значение t может быть больше указанного.