Размещено на http://www.allbest.ru/

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

ВВЕДЕНИЕ

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

Актуальность проблемы исследования

Растущая потребность в точной передаче информации

Цель исследования:

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

Объект исследования:

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

Предмет исследования:

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

Методы исследования:

· обработка и анализ научных источников

· поиск информации по выбранной теме в Интернет источниках

1. ПОМЕХИ

Помеха - это любое воздействие, которое накладывается на полезный сигнал и затрудняет его прием.

Классификация помех и их источников:

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

2. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

2.1 Классификация

В основном принцип помехоустойчивых кодов строится на прибавлении к исходной комбинации (kсимволов) контрольных (rсимволов). Закодированная комбинация будет содержать nсимволов. Коды с таким преобразованием часто называют (n,k) коды.

Где k--число символов в исходной комбинации,

r--число контрольных символов.

2.1.1 Коды с обнаружением ошибок

2.1.1.1 Код с проверкой на четность

Этот код образуется путем прибавления к передаваемому коду, состоящему из k символов, одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемом коде было четным.

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

В связи с тем, что вероятность ошибок является очень малой величиной, то можно сократить формулу

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

При передаче большого количества кодовых комбинаций Nk , число комбинаций, в которых ошибка определяется, равно:

Общее число кодовых комбинаций с обнаруживаемыми и не обнаруживаемыми ошибками находится как

Тогда коэффициент обнаружения Kобн для комбинаций с четной защитой равен

2.1.1.2 Код с постоянным весом

Такой код содержит неизменное число единиц и нулей. Число кодовых комбинаций составит

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

Для примера возьмём код с тремя единицами из семи. Для такого кода возможны три варианта смещений.

Вероятность возникновения не обнаруживаемых ошибок смещения

, где

При p<<1 , тогда

Вероятность появления всевозможных обнаруживаемых и не обнаруживаемых ошибок будет равен

Вероятность обнаруживаемых ошибок . В таком случае коэффициент обнаружения будет составлять

2.1.1.3 Корреляционный код (Код с удвоением)

Элементы такого кода заменяются двумя символами, ноль `0' преобразуется в 01, а единица `1' в 10.

Вместо комбинации 1010011 передается 10011001011010. Ошибки обнаруживаются, когда в парных элементах находятся одинаковые символы 00 или 11 (вместо 01 и 10).

2.1.1.4 Инверсный код

К изначальной комбинации добавляется такая же по длине комбинация. В линию отправляется удвоенное количество символов. Если в исходной комбинации число единиц чётное, то добавляемая комбинация равна исходной комбинации, при нечетном числе, добавляемая комбинация будет инверсной относительно исходной.

Метод инверсного кода осуществляется в два этапа. На начальном этапе суммируются единицы в первой основной группе символов. Если количество единиц четное, то контрольные символы принимаются неизменно, если нечетное, то контрольные символы меняются на противоположные. На втором этапе контрольные символы складываются с информационными символами по модулю два. Нулевая сумма говорит об отсутствии ошибок. При ненулевой сумме, принятая комбинация бракуется. Покажем суммирование для принятых комбинаций без ошибок (1,3) и с ошибками (2,4).

Обнаруживающие способности данного кода достаточно велики. Данный код обнаруживает практически любые ошибки, кроме редких ошибок смещения, которые одновременно происходят как среди информационных символов, так и среди соответствующих контрольных. Например, при k=5, n=10 и . Коэффициент обнаружения будет составлять .

2.1.1.5 Код Грея

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

7 0111 > 1111

8 1000 > 0000

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

Схема съема информации угла поворота вала в код

Код Грея записывается следующим образом

Разряды в коде Грея не имеют постоянного веса. Вес kразряда определяется следующим образом

.

При этом все нечетные единицы, считая слева направо, имеют положительный вес, а все четные единицы отрицательный.

2.1.2 Корректирующие коды

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

Рис.5.3. Представление двоичных кодов с помощью куба

Иначе, кодовое расстояние это то минимальное число элементов, в которых одна кодовая комбинация отличается от другой. Для определения кодового расстояния достаточно сравнить две кодовые комбинации по модулю 2. Так, сложив две комбинации

10110101101

11001010101

01111111000

определим, что расстояние между ними d=7.

Для кода с N=3 восемь кодовых комбинаций размещаются на вершинах трехмерного куба. Такой код имеет кодовое расстояние d=1, и для передачи используются все восемь кодовых комбинаций 000,001,..,111. Такой код является не помехоустойчивым, он не в состоянии обнаружить ошибку.

Если выберем комбинации с кодовым расстоянием d=2, например, 000,110,101,011, то такой код позволит обнаруживать однократные ошибки. Назовем эти комбинации разрешенными, предназначенными для передачи информации. Все остальные 001,010,100,111 - запрещенные.

Любая одиночная ошибка приводит к тому, что разрешенная комбинация переходит в ближайшую, запрещенную комбинацию (см. рис.5.3). Получив запрещенную комбинацию, мы обнаружим ошибку. Выберем далее вершины с кодовым расстоянием d=3

Такой код может исправить одну одиночную ошибку или обнаружить две ошибки. Таким образом, увеличивая кодовое расстояние можно увеличить помехоустойчивость кода. В общем случае кодовое расстояние определяется по формуле d=t + l + 1 где t - число исправляемых ошибок , l - число обнаруживаемых ошибок. Обычно l>t.

Большинство корректирующих кодов представляют собой линейные коды. Линейные коды - это коды, в которых контрольные символы образуются линейным комбинированием информационных символов. Также корректирующие коды являются групповыми кодами. Групповые коды (Gn) - это коды, имеющие одну основную операцию. При том, должно соблюдаться условие замкнутости (то есть, при сложении двух элементов группы получается элемент принадлежащий этой же группе ). Число разрядов в группе не должно увеличиваться. Этому условию удовлетворяет операция поразрядного сложения по модулю 2. В группе, кроме того, должен быть нулевой элемент.

Большая часть корректирующих кодов строятся на добавлении к исходной k комбинации r контрольных символов. По итогу в линию передаются n=k+r символов. Тогда корректирующие коды называются (n,k) кодами. Как определить необходимое количество контрольных символов?

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

.

помеха код начальный ошибка

Это равнозначно известной задаче о минимуме числа контрольных вопросов, на которые можно дать ответы вида “да” или “нет”, для однозначного определения одного из элементов конечного множества.

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

Эта формула называется неравенством Хэмминга, или нижней границей Хэмминга для числа контрольных символов.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

1. Вернер М. Основы кодирования. -- М.: Техносфера, 2004.

2. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.

3. Кнут Дональд, Грэхем Роналд, Паташник Орен Конкретная математика. Основание информатики -- М.: Мир; Бином. Лаборатория знаний, 2006. -- С. 703.

4. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002. - 120с.

5. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И. Халкин, Е.В. Федоров и др. - М.: Высшая школа, 2001 г. - 383с.

6. Рудаков А.Н. Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение, третья серия. -- 2000. -- Т. 4.

7. Стахов А.П. Коды золотой пропорции. -М.: Радио и Связь, 1984.

8. Цапенко М.П. Измерительные информационные системы. - М.: Энергоатом издат, 2005. - 440с.

Размещено на Allbest.ru