10

Реферат

По курсу “Теория информации и кодирования”

Тема:

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

Содержание

Введение

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

2. Обнаруживающие коды

Список литературы

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Кодовое расстояние - d определяется как количество единиц в результате суммирования по модулю два двух кодовых комбинаций. Минимальное кодовое расстояние d₀ - минимальное из кодовых расстояний всех возможных кодовых комбинаций.

Для обнаружения r ошибок минимальное кодовое расстояние равно:

d₀ r+1. (1)

Для обнаружения r ошибок и исправления s ошибок минимальное кодовое расстояние равно:

d₀ r+s+1. (2)

Только для исправления ошибок минимальное кодовое расстояние равно:

d₀ 2s+1. (3)

2. Обнаруживающие коды

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

В символьном коде ASCII к семи битам кода добавляется восьмой бит проверки на четность - k₁.

S₁ S₂ S₃ S₄ S₅ S₆ S₇ K₁

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

Внесение избыточности за счет увеличения длины кодовой комбинации приводит к снижению скорости передачи информации.

Если скорость идеально использует канал, то

. (4)

Если кодовая комбинация длиной n содержит k информационных и m контрольных разрядов (n = k + m), то

.

Для кода ASCII n = 8 и k = 7

,

т. е. введения одного избыточного разряда приводит к уменьшению пропускной способности канала связи на 12,5%.

Чаще всего шумы (молнии, разрыв и т.д.) порождают длинные пакеты ошибок и вероятность четного и нечетного числа ошибок одинакова, а значит и однобитовая проверка не эффективна.

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

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

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

1 0 1 1 0 1 1 1

0 1 0 0 0 1 0 0

1 0 1 0 0 1 0 1

1 1 0 0 1 0 1 0

0 0 0 1 0 1 0 0

1 0 0 0 1 0 0

После обнаружения ошибок иногда можно повторить передачу сообщений, иногда после обнаружения ошибки предпринимается вторая и даже третья попытка передачи сообщения. Такая ситуация актуальна в дуплексных каналах, где применения кодов, обнаруживающих ошибки (Feedback or Backward Error Control), достаточно , так как сигнализация об ошибке вызывает повторную передачу от источника. Это основные методы, используемые в информационных сетях.

Проверка на четность широко используется на ЭВМ, как на аппаратном, так и на программном уровне.

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

Пример 1. Символы алфавита источника кодируются семиразрядным двоичным кодом с весом кодовых векторов (количеством единиц в кодовой комбинации) w = 3. Определить необходимую мощность кода и его избыточность.

Решение: Мощность семиразрядного кода равна N = 2⁷ = 128.

Так как для кодирования используются только кодовые вектора с весом три , то количество таких векторов в семиразрядном коде равно

Избыточность кода равна R = 1 - log₂K/ log₂N = 0,265.

Список литературы

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

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

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

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

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

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

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

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