Материал: Лабораторная работа 4

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

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

5. Циклический код с порождающим многочленом степени не обнаруживает часть ошибок -й кратности.

6. Циклический код с порождающим многочленом степени не обнаруживает часть ошибок более -й кратности.

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

При обнаружении ошибок стандартные многочлены имеют вид: , при длине кодовой комбинации ,

или , при длине кодовой комбинации ;

, при длине кодовой комбинации .

Разработан ряд методик по выбору порождающего многочлена . В литературе коды называют по фамилиям ученых, предложивших ту или иную методику. Так получили свое название коды Боуза-Чоудхури-Хоквингема (БЧХ), коды Рида-Соломона, коды Файра и др.

Укороченные циклические коды

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

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

Вероятности ошибочного декодирования циклических кодов

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

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

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

Вероятность того, что будет одна ошибка в заданном символе, равна .

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

.

Вероятность того, что слово на выходе канала будет отличаться от передан­ного слова в любых разрядах, равна

,

где — число сочетаний из по .

Предположим, что некоторый линейный код (5,3) содержит одно нулевое слово (как всякий линейный код), два слова, вес которых равен 2, четыре слова — весом 3, одно слово — весом 4 (всего слов).

Вероятность необнаруживаемой этим кодом ошибки равна вероятности по­явления в ДСК векторов ошибок, совпадающих с кодовыми словами, т.е.:

В режиме исправления ошибок декодер вычисляет остаток от деления принятой последовательности на . Этот остаток называют синдромом. Принятый полином представляет собой сумму по модулю 2 переданного слова и вектора ошибок :

.

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

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

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

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

Если кодом могут быть исправлены только все векторы ошибок веса и меньше, то любой вектор ошибки веса от до п будет приводить к ошибоч­ному декодированию.

Вероятность ошибочного декодирования будет равна вероятности появления векторов ошибок веса и больше в заданном канале. Для ДСК эта вероятность будет равна

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

4.2. Описание лабораторной установки

Лабораторная работа выполняется на ПЭВМ. Программа содержит несколько страниц:

• «Установки» — содержит различные установки и панель формирования индивидуального задания;

• «Читайте» — содержит разделы: цель работы, задание, содержание отчета и контрольные вопросы. Раздел «Задание» содержит лабораторное задание и ме­ тодику выполнения каждого пункта;

• «Схема» — содержит схему, иллюстрирующую процесс кодирования и декодирования. На этой странице имеется возможность вводить различные ко­довые комбинации, векторы ошибок и наблюдать процесс кодирования и декоди­рования. Также эта страница содержит таблицу соответствия векторов ошибоки соответствующих им синдромов;

• «Таблица» — содержит таблицу разрешенных кодовых комбинаций ис­пользуемого кода, таблицу расстояний Хэмминга для всех пар кодовых комбина­ций и таблицу весов кодовых комбинаций.

Имеется возможность изменять порождающий полином, используемый ДЛЯ кодирования. Обратите внимание, что только полиномы 1011 и 1101 обеспечива­ют коду (7,4) требуемые помехоустойчивые свойства ( = 3).

Выполнять работу рекомендуется при полиноме 1011 (установлен по умол­чанию). Это связано с тем, что тестовые вопросы для защиты этой лабораторной работы составлены для полинома 1011;

• «Формулы» — содержит некоторые формулы, используемые в лабораторной работе;

• «Статистика» — демонстрирует использование различных способов поме­ хоустойчивого кодирования для обнаружения и исправления ошибок.

Функциональная схема лабораторного макета приведена на рис. 8.2. Информационное слово длиной четыре разряда (т = 4) задается нажатие кнопок на панели «Источник».

Кодер формирует кодовую комбинацию разделимого циклического кода (7,4), путем добавления к четырем информационным трех проверочных разрядов. Проверочные разряды образуются в результате умножения на х³ и деления полу­пившейся комбинации на порождающий полином 1011 (g(х) = х³+х+1). Остаток от деления будет представлять проверочные разряды, которые приписываются справа от информационных.

Рис. 4.2. Функциональная схема лабораторной установки

Кодер выдает кодовое слово F(х) длиной n = 7. соответствующее информа­ционному слову P(х) длиной т = 4, поданному на вход кодера.

Семиразрядная кодовая комбинация (вектор F(х)) с выхода кодера подается на вход канала. В канале передаваемая кодовая комбинация складывается с семираз­рядным вектором ошибки Е(х). Сложение производится поразрядно по модулю 2. Например, если комбинация на входе канала равна 1011000, а вектор ошибки ра­вен 0010001, то комбинация на выходе канала будет равна 1001001. Таким обра­зом, единица в j-м разряде в векторе ошибки приводит к ошибке (инверсии) j-го разряда в кодовой комбинации на выходе канала.

Вектор ошибки задается на панели «Источник ошибок». Там же имеются кнопки для циклического сдвига вектора ошибки и для его инверсии.

С выхода канала принятая кодовая комбинация подается на входы декодеров.