рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Лекция 8. Основы помехоустойчивого кодирования. Простейшие коды. - раздел Философия, Основы теории систем связи с подвижными объектами   Помехоустойчивые Коды — Одно Из Наиболее Эффективных Средств ...

 

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

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

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

Рассмотрим сущность помехоустойчивого кодирования.

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

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

Напомним, что двоичный код - это код с основанием m = 2.

Количество разрядов п в кодовой комбинации принято называть длиной или значностью кода. Каждый разряд может принимать значения 0 или 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают .

Например, кодовая комбинация 100101100 характеризуется значностью n = 9 и весом = 4.

Степень отличия любых двух кодовых комбинаций данного кода характеризуется так называемым расстоянием, между кодами d. Оно выражается числом позиций или символов, в которых комбинации отличаются одна от другой. Кодовое расстояние есть минимальное расстояние между кодовыми комбинациями данного кода, оно определяется как вес суммы по модулю два кодовых комбинаций. Например, для определения расстояния между комбинациями 100101100 и 110110101 необходимо просуммировать их по модулю два

Полученная в результате суммирования новая кодовая комбинация характеризуется весом = 4. Следовательно, расстояние между исходными кодовыми комбинациями d = 4.

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

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

Для указания мест в кодовой комбинации, где имеются искажения

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

Вес вектора ошибки характеризует кратность ошибки. Сумма по модулю два искаженной кодовой комбинации и вектора ошибки дает исходную неискаженную комбинацию.

Помехоустойчивость кодирования обеспечивается за счет введения избыточности в кодовые комбинации. Это значит, что из n символов кодовой комбинации для передачи информации используется k< n символов. Следовательно, из общего числа No=2n возможных кодовых комбинаций для передачи информации используется только N = 2к комбинаций. В соответствии с этим все множества N0=2" возможных кодовых комбинаций делятся на две группы. В первую группу входит множество N = 2к разрешенных комбинаций. Вторая группа включает в себя множество (No - N) = 2n - 2к запрещенных комбинаций.

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

 

 

Рис. 3.1 Схема передачи информации

 

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

В общем случае каждая из N разрешенных комбинаций Аi может трансформироваться в любую из No возможных комбинаций, т. е. всего имеется N • No возможных случаев передачи, из них N случаев безошибочной передачи, N(N — 1) случаев перехода в другие разре­шенные комбинации и N(N0 — N) случаев перехода в запрещенные комбинации.

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

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

Если принятая запрещенная комбинация принадлежит подмножеству Mi, то считается, что передана комбинация Ai.

Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из комбинации Ai. Таким образом, ошибка исправляется в (No— N) случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от общего числа обнаруживаемых ошибочных комбинаций составляет

(3.1)

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

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

Пусть необходимо построить код, обнаруживающий все ошибки кратностью t и ниже.

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

(3.2)

Если же необходимо устранить ошибки, то в общем случае для устранения ошибок кратности а кодовое расстояние должно удовлетворять условию

(3.3)

Можно установить, что для исправления всех ошибок кратности не более и одновременного обнаружения всех ошибок кратности не более t (при t > ) кодовое расстояние должно удовлетворять условию

(3.4)

При этом нужно иметь в виду, что если обнаруженная кодом ошибка имеет кратность t > , то такая ошибка исправлена быть не может, т. е. в данном случае код только обнаруживает ошибку.

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

Пусть известен объем алфавита источника N. Необходимое количество информационных символов определяется из выражения

(3.5)

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

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

Полное число ошибочных комбинаций, подлежащих исправлению, равно Е2к = EN . Так как количество ошибочных комбинаций равно No -N, то код обеспечивает исправление не более No- N комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде

(3.6)

откуда получим

(3.7)

или

(3.8)

Формула (3.8) выражает условие для выбора значности кода n .

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

В этом случае зависимость (3.8) примет вид

(3.9)

При построении кода целесообразно пользоваться табл. 3.1

 

Таблица 3.1 Справочные данные

n
1.33 3.2 6.33 9.2 28.4 61.2

 

Нужно при этом иметь в виду, что код должен также удовлетворять условию

(3.10)

Если необходимо обеспечить устранение всех ошибок кратности от 1 до l, то нужно учесть, что

  • число возможных однократных ошибок ;
  • число возможных двукратных ошибок;
  • ............................................................................;
  • число возможных l кратных ошибок.

Общее число ошибок

При этом зависимость (3.8) примет вид

(3.11)

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

(3.12)

где - вероятность необнаруживаемой ошибки.

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

(3.13)

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

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

(3.14)

где рк- вероятность искажений кодовой комбинации; р00 - ве­роятность появления обнаруживаемых искажений комбинаций. Тогда

(3.15)

Для оценки избыточности корректирующего кода пользуются понятием коэффициента избыточности

(3.16)

где p = n-k- количество избыточных позиций кодовой комбинации, используемых для обеспечения корректирующих способностей кода.

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

(3.17)

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

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

Избыточность кода равна

(3.17)

где n - значность кода; р - число проверочных символов.

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

Код с удвоением элементов характеризуется введением допол­нительных символов для каждого символа информационной части комбинации, причем единица дополняется нулем и преобразуется в 10, а нуль дополняется единицей и преобразуется в 01. Тогда исходная, например, комбинация 10101 будет представлена в виде 1001100110. Показателем искажения кода будет появление в «парных» элементах сочетаний вида 00 или 11.

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

Избыточность кода не зависит от числа элементов кодовой комбинации

r = 0.5

Естественно, что помехоустойчивость этого кода выше, чем кода с четным числом единиц.

В основу построения инверсного кода положен метод повторения исходной кодовой комбинации. Причем в тех случаях, когда исходная комбинация содержит четное число единиц, вторая комбинация в точности воспроизводит исходную, если же исходная комбинация содержит нечетное число единиц, то повторение происходит в инвертированном виде. Например, комбинации 01010 и 01110 инверсным кодом представляются соответственно как 0101001010 и 0111010001.

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

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

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

 

– Конец работы –

Эта тема принадлежит разделу:

Основы теории систем связи с подвижными объектами

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... Технологический институт ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО ОБРАЗОВАНИЯ... ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция 1. Общие понятия и определения
  На рисунке 1.1 изображена структурная схема простейшей системы связи. Источни­ком сообщений и получателем может быть человек, автомат, вычислительная машина и т.п.  

Лекция 2. Формирование и представление сигналов.
  Нанесение информации на носители достигается определенным изменением па­раметров некоторых физических процессов, состояний, соединений, комбинаций эле­ментов. Чаще всего материализа

Лекция 3. Спектры импульсных сигналов
  Рассмотрим спектры одиночных импульсов различной формы. Их определение производится подстановкой аналитического описания импульса в формулу для интеграла Фурье.  

Лекция 4. Основы оптимальной обработки сигналов
  Если на входе приемника действует сигнал x(t), равный сумме полезного сигнала

Тестовый контроль
Вопросы Варианты ответов 1. Как классифицируются каналы связи?   2. Если динамический диапазон канала увеличилс

Лекция 6. Различение сигналов
  При различении сигналов имеет место миогоальтернативная ситуация, когда полезный сигнал X может иметь много значений и приемное устройство должно определить, какое именно зна

Лекция 7. Восстановление сигналов
  Восстановление сигналов сводится к оценке некоторого числа неизвестных параметров полезного сигнала. Ограничимся рассмотрением случая оценки одного из параметров сигнала, например а

Тестовый контроль
  Вопросы Варианты ответов 1. Какое пороговое значение отношения правдоподобия используется в критерии мак

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

Тестовый контроль
  Вопросы Варианты ответов 1. Имеются две кодовые комбинации 11100011 и 10110010. Каково кодовое расстояни

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги