Линейные двоичные коды для обнаружения и исправления ошибок

Определение 11. Линейным блочным двоичным кодом длины п называется любое множество двоичных последовательностей длины п, которое содержит чисто нулевую последовательность, и для каждой пары последовательностей, принадлежащих этому множеству, их поразрядная сумма по mod 2 также является элементом этого множества. (Последнее свойство можно назвать замкнутостью относительно поразрядного сложения по mod2.) Таким образом, для всех линейных кодов изучение списка хэмминговских расстояний между парами комбинаций эквивалентно изучению списка хэмминговских весов, что, очевидно, значительно проще.

Виды кодов: 1)Коды с общей проверкой на четность (могут обнаруживать лишь одну ошибку) Это класс кодов с параметрами (п,k) =(k+1, k), k= 1, 2, 2)Коды Хемминга(могут гарантированно обнаруживать ошибки кратности 1 и 2) 3)М-последовательности (хорошая исправляющая способность покупается за счет низкой кодовой скорости) 4)Полиномиальные коды (процедура обнаружения ошибок сводится к делению принятой кодовой комбинации на порождающий многочлен) Коды Боуза-Чоудхури-Хоквингема (БЧХ).

Переход к линейным кодам значительно упрощает анализ их обнаруживающей и исправляющей способности. В линейной алгебре существует понятие ортогонального пространства или нуль- пространства для заданного линейного пространства V. Это по определению такое множество V* векторов х* длины n, для которых (х*, х) = 0 при любом x V, где (,) означает скалярное произведение соответствующих векторов. Определение 13. Синдромом по коду К для любого принятого на выходе канала связи двоичного слова у длины п будем называть двоичный вектор-строку длины п-к:

s = yH^T, (7.56)

где Н - проверочная матрица кода V.

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

Пусть х = (x₀,х₁,..., ) - произвольный двоичный блок длины п. Будем называть циклическим сдвигом S_x вправо данного блока преобразование следующего вида:

Определение 14. Линейный двоичный (п, k)-код V называется циклическим кодом, если в результате циклического сдвига любой из его комбинаций полученная комбинация снова принадлежит коду, т.е. S_x V, если х V.

Дата добавления: 2015-12-07