ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Федеральное государственное образовательное учреждение Среднего профессионального образования по Владимирской области «Гусевский. - презентация

1 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Федеральное государственное образовательное учреждение Среднего профессионального образования по Владимирской области «Гусевский стекольный колледж» подготовила: студентка 2-го курса очного отделения специальность: «Прикладная информатика» Маткина Анастасия преподаватель:Чикинеева Наталья Викторовна 2014 год

2 2 Необходимость помехоустойчивого кодирования: Если в канале есть помехи, то при приеме кодовых символов могут произойти ошибки, тогда кодовые комбинации (полученные при эффективном кодировании) будут декодированы неправильно! Задача: повышение верности передачи Один из путей ее решения – помехоустойчивое (канальное) кодирование.

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

4 4 При кодировании источника избыточность уменьшается или полностью устраняется (достигается увеличение скорости передачи информации за счёт уменьшения средней длины кодовых слов) Наиболее простой способ: например, вместо слова стол можно передавать слово ссстттоооллл При помехоустойчивом кодировании в передаваемые сообщения вводится избыточность (количество символов увеличивается!) За счет этого появляется возможность обнаруживать ошибки и даже исправлять их

5 5 2-я Теорема Шеннона (Основная теорема кодирования для каналов с помехами (шумами) Если производительность источника меньше пропускной способности канала то существует по крайней мере одна процедура кодирования/декодирования, при которой вероятность ошибочного декодирования и ненадежность могут быть сколь угодно малы. Если то такой процедуры не существует. В вышеприведённом примере ясно, что при фиксированном уровне помех для стремления вероятности ошибки к нулю количество повторений должно стремиться к бесконечности. Скорость передачи информации при этом стремится к нулю.

6 6 Классификация корректирующих кодов Коды Блочные Непрерывные Разделимые Неразделимые Свёрточные Линейные Нелинейные Код Рида-Мюллера Код Хэмминга Цепные

7 7 Линейные блочные коды Блочный равномерный код – множество кодовых слов (комбинаций) одинаковой длины n. Элементы кодовых слов выбираются из некоторого алфавита (канальных) символов объемом q. Если q =2, код называется двоичным. Далее для простоты считается, что q =2.

8 8 Поскольку все кодовые слова имеют одинаковую длину, удобно считать их векторами, принадлежащими линейному пространству размерности n. Для линейных к ó дов справедливо утверждение: линейная комбинация кодовых слов является кодовым словом …………………

9 Из них только комбинаций являются разрешёнными и составляют код, который называется -кодом (отношение называется относительной скоростью кода). Всего n-мерных векторов с двоичными компонентами (кодовых комбинаций или слов). 9 Остальные комбинации являются запрещёнными, образуются из разрешённых в канале под воздействием помех.

10 10 Для кодирования и декодирования линейных блочных кодов применяются действия, описываемые операциями над векторами в линейном пространстве над конечным полем целых чисел Сложение и умножение в конечном поле понимаются как сложение и умножение по модулю q Простейшее из таких полей, называемых полями Галуá – поле по модулю 2, обозначаемое GF(2) ЭВАРИСТ ГАЛУА Évariste Galois ( ) выдающийся французский математик, основатель современной алгебры.

11 11 Заметим, что вычитание по модулю 2 совпадает со сложением по модулю 2

12 12 Метрика (расстояние) Хэмминга, определяемая для двух двоичных кодовых векторов выражением Расстояние по Хэммингу между двумя двоичными векторами равно количеству несовпадающих элементов Скалярное произведение можно определить выражением Итак, множество всех двоичных кодовых слов длины n можно рассматривать, как n-мерное линейное пространство над конечным полем скаляров GF(2).

13 13 Линейные коды являются разделимыми, то есть k символов – информационные, остальные (n-k) проверочные. Информационные символы зависят от передаваемого сообщения и могут быть какими угодно. Проверочные символы однозначно определяются информационными (т.к. формируются из информационных символов кодером, работающим по определённому алгоритму). Отсюда следует, что каждая кодовая комбинация, будучи вектором n-мерного пространства, принадлежит его k- мерному подпространству

14 14 Обозначим информационные символы Образуем вектор длины n следующим образом : прямая сумма пространств Любой вектор одного подпространства ортогонален любому вектору из другого подпространства Далее мы придем к другому разложению пространства

15 15 Подпространство представляет собой множество всех разрешенных кодовых комбинаций – линейную оболочку совокупности вектор-строк порождающей матрицы. Это подпространство и есть код. Тогда подпространство, ортогональное к нему, также можно считать некоторым кодом (n, n-k), дуальным к данному. Порождающая матрица H дуального кода содержит n-k линейно- независимых строк длины n

16 16 Любое кодовое слово (n, k)-кода ортогонально любому кодовому слову (n, n-k)-кода, следовательно матрица размера, состоящая из нулей Для систематической матрицы проверочная матрица также систематическая (для двоичного кода минус можно опустить, так как сложение и вычитание по модулю 2 совпадают)

17 17 Матрица Н является порождающей матрицей дуального кода; в то же время она может использоваться для обнаружения ошибок в комбинациях исходного кода, прошедших через канал: если принятая кодовая комбинация Y является разрешённой, то она ортогональна к подпространству, т.е. ко всем строкам матрицы Н: Если полученный вектор ненулевой, то при передаче имела место ошибка!

18 18 Умножая слева вектор-строку, соответствующую принятой комбинации, на транспонированную матрицу, получаем вектор (называемый синдромом), который равен нулевому вектору в том и только в том случае, если комбинация является разрешённой. В противном случае комбинация является запрещённой, следовательно, при передаче произошла ошибка. По значению синдрома можно определить, какой именно разряд кодового слова содержит ошибку (а при двоичном коде – и исправить её!).

19 19 Коды Хэмминга Коды Хэмминга представляют собой (n, k)-коды, удовлетворяющие условию В частности, рассмотренный (7,4)-код принадлежит к кодам Хэмминга при m=3 Для кода Хэмминга проверочная матрица содержит в качестве столбцов все возможные - значные комбинации нулей и единиц, исключая нулевой вектор.

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

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

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

23 Спасибо за внимание!