Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1. ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

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


1.1. Структура линейных блоковых кодов

 

Напомним, что булево пространство Bn , B = {0,1}, представляет собой множество двоичных векторов длины n. Операция Å сложения по модулю 2 является групповой операцией, и множество Bn представляет собой линейное пространство с операцией Å  и умножением на скаляр из множества {0,1}.

Линейным двоичным или групповым кодом называется подпространство линейного пространства Bn.

Таким образом, линейный код есть непустое множество двоичных слов длины n, называемых кодовыми словами, такое, что сумма двух кодовых слов является кодовым словом. В любом линейном коде нулевое слово 0 = 0...0 выполняет роль нуля. Более того, в линейном двоичном коде каждое слово противоположно самому себе, так как c Å c = 0...0 для любого cÎBn. Мы далее в основном будем рассматривать линейные двоичные коды. Поэтому слово «двоичный» будем опускать, и операцию Å сложения по модулю 2 будем называть просто операцией сложения и обозначать +.

Пример. Рассмотрим множество V = {000, 011, 100, 111}. Непосредственной проверкой можно убедиться, что сумма любых двух слов множества является элементом множества, т. е. V - линейный код.

Пусть VÍBn - линейный код. Так как V - конечное множество, то в подпространстве V существует конечный a1, ..., ak базис из k векторов. Любой вектор можно представить как линейную комбинацию a1a1 + ... + akak, где все коэффициенты a1, ..., ak принимают значения из множества {0,1}. Число k называется размерностью линейного кода. Линейный код VÍBn размерности k называется (n,k) - кодом.

Напомним, что в линейном (n,k) - коде число k есть размер блока информационных символов, который затем, при кодировании, преобразуется в блок из n символов, где n>k. Добавленные n-k символов называют проверочными символами. Заметим, что не всегда можно сказать, какие символы являются информационными, а какие - проверочными.

Например, в линейном (5,3)-коде V = {00000, 10011, 11001, 11100, 01010, 01111, 00101, 10110} базисом является множество {10011, 11001, 11100}. Вектор 01010 представляется в виде линейной комбинации 01010 = 1×10011 + 1×11001 + 1×11100. Непосредственной проверкой можно убедиться, что кодовое расстояние равно 3.

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

Теорема 1.1. Кодовое расстояние линейного кода равно минимальному весу ненулевого кодового слова.

Доказательство. Пусть расстояние кода совпадает с расстоянием между кодовыми словами x и y. Так как V линейный код, то x + y =   z тоже принадлежит коду V; т. о. dV = w(z). Так как нулевое слово принадлежит коду V, то код не содержит ненулевых слов веса меньше dV.

Теорема 1.2. Мощность линейного (n,k) - кода равна 2k.

Доказательство. Каждое кодовое слово есть линейная комбинация базисных кодовых слов. Число различных линейных комбинаций равно, т. е. |V| ≤ 2k. Две линейные комбинации с различными коэффициентами не совпадают, так как базисные векторы линейно независимы. Поэтому |V| = 2k.