Коды для исправления пачек ошибок

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

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

Вполне понятно, что некоторый (n, k) – код обладает способностью обнаруживать или исправлять пачки ошибок длины l и менее тогда и только тогда, если его кодовые комбинации не содержат в своем составе пачек данной длины.

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

Во-первых, необходимо, чтобы такой код не содержал пачек длины l и менее. Определим, когда это возможно. Рассмотрим разложение группы, составленной из п – элементных векторов не смежные классы по подгруппе, образующей данный (n, k) – код. Если кодовые комбинации не содержат пачек длины l и менее, то в одном и том же смежном классе не могут существовать 2 комбинации, в которых, начиная с одного и того же разряда, размещены пачки длины l и менее, так как в противном случае их сумма, являющаяся кодовой комбинацией, должна содержать пачку длины меньшей l.

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

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

Свойство 9.1. Групповой код, обнаруживающий все пачки ошибок длины l и менее, должен содержать, по крайней мере, l проверочных символов.

В случае циклического кода эта нижняя граница для числа проверочных символов является точной. Действительно, любая кодовая комбинация циклического кода может быть представлена как произведение где g(x) – порождающий многочлен кода степени n-k. Значит каждая кодовая комбинация циклического кода содержит или пачку длины n–k +1 (комбинации ) или линейную комбинацию циклически сдвинутых пачек длины n–k +1, сумма которых всегда дает пачку большей длины, т.е. справедливо следующее свойство.

Свойство 9.2. Любой циклический (n, k) – код обнаруживает все пачки ошибок длины (n - k) и менее.

В случае исправления пачек ошибок можно аналогичными рассуждениями получить нижнюю границу для числа проверочных элементов. Действительно, пусть известно, что групповой (n, k) – код исправляет все пачки ошибок длины b. Значит общее число смежных классов в таблице декодирования должно быть не меньше, чем число возможным пачек длины b. В комбинации длины п возможно всего п пачек длины 1, п -1 пачек длины 2, 2(п -2) пачек длины 3 и т.д. Общее число пачек длины b в комбинации длины п равно . Таким образом, число смежных классов равно

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

откуда, логарифмируя по основанию 2, получаем . Итак, справедливо следующее свойство групповых кодов.

Свойство 9.3. Число проверочных элементов (n, k) – кода, исправляющего все пачки ошибок длины b и менее равно самое меньшее .

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

Коды Файра – циклические коды, порождающий многочлен которых имеет вид , где Р(х) – неприводимый многочлен степени r, входящий в разложение и не являющийся сомножителем никакого двучлена меньшей степени.

Необходимо при этом, чтобы с не делилось на е. Длина кодовой комбинации п равна наименьшему общему кратному чисел е и с, т.к. только в этом случае g(x) делит

Число проверочных элементов равно , а число информационных . В [1] показано, что коды Файра исправляют любую одиночную пачку ошибок длины b или меньше и одновременно обнаруживают любую пачку ошибок длины или меньше, если выполняются соотношения и Если применять эти коды только для обнаружения ошибок, то можно обнаружить любую комбинацию из двух пачек ошибок, длина наименьшей из которых не превосходит r, а сумма длин которых не превосходит с+ 1, а так же и любую одиночную пачку ошибок, длина которой не превосходит числа проверочных символов с+r.

Указанные свойства кодов Файра обусловлены видом порождающего многочлена. Наличие в g(x) сомножителя достаточно для обнаружения одиночной пачки ошибок длины с. Дополнительная информация, требуемая для определения положения пачки ошибок, обеспечивается сомножителем Р(х).

Пример 9.1. Код Файра порождается многочленом Определить параметры кода и его корректирующие свойства.

Здесь r =3, е =7, с =4, n-k=r+c= 7;

Итак, порождает код Файра (28,21). Данный код может исправить пачки ошибок длины b =2 и b =1, а также дополнительно обнаружить при этом пачки длины b =3 и b =4 соответственно. Если использовать этот код только для обнаружение ошибок, то модно обнаружить любую одиночную пачку ошибок длины 7 и комбинацию из двух пачек ошибок, из которых одна не превосходит 3, а сумма длин обоих равна 5 или менее.

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

и

.

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

и

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

.

Для случая обнаружения пачек ошибок

.

Из определения кодов Файра вытекает, что при с =1 они совпадают с кодами Хэмминга, имеющими d_min =4, если при этом .

Дата добавления: 2015-08-02