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

Блоковый код состоит из набора векторов фиксированной длины, называемых кодовыми словами. Длина кодового слова – это число элементов в векторах, и оно обозначается . Элементы кодового слова выбираются из алфавита с  элементами. Если алфавит содержит два элемента 0 и 1, код называется двоичным, а элементы любого кодового слова называют битами (двоичными символами). Если элементы кодового слова выбираются из алфавита, имеющего  элементов , код называют не двоичным. Интересно отметить, что если   является степенью 2, т.е. , где  - положительное целое число, каждый -й элемент имеет эквивалентное двоичное представление, состоящее из  битов и, таким образом, недвоичные коды длины  можно отобразить в двоичный код с блоковой длиной .

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

Кроме параметра скорости кода , важным параметром кодового слова является его вес, который равен числу ненулевых элементов, слова. В общем, каждое кодовое слово имеет свой собственный вес. Набор всех весов кода образует распределение весов кода. Когда все  кодовых слов имеет одинаковый вес, код называется кодом с фиксированным весом или кодом с постоянным весом. Функции кодирования и декодирования включают арифметические операции суммирования и умножения, выполненные над кодовыми словами. Эти арифметические операции выполняются в соответствии с соотношениями, правилами для алгебраического поля, которое имеет своими элементами символы, содержащиеся в алфавите кода. Для примера, символы в двоичном алфавите равны 0 и 1; следовательно, поле имеет два элемента. В общем, поле  состоит из набора элементов, над которыми выполняются две арифметические операции, именно, операции сложения и умножения, которые удовлетворяют следующим свойствам (аксиомам):

Сложение

1. Набор  замкнут относительно сложения, т.е. если , тогда .

2. Сложение ассоциативно, т.е. если  и  - элементы , тогда .

3. Сложение коммутативно, т.е. .

4. Набор содержит элемент, называемый нулевым, который удовлетворяет условию .

5. Каждый элемент множества имеет свой собственный отрицательный элемент. Следовательно если  - элемент, то его отрицательный элемент обозначается . Вычитание двух элементов, такие как  определено как .

Умножение

1. Набор  замкнут относительно умножения, т.е. если , то тогда .

2. Умножение ассоциативно, т.е. если  и  - элементы , тогда .

3. Умножение коммутативно, т.е. .

4. Умножение дистрибутивно со сложением, т.е..

5. Набор содержит элемент, называемый единичным, который удовлетворяет уcловию  для любого элемента .

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

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

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

Подобным образом, поле  содержит набор, состоящий из элементов . Таблицы сложения и умножения для :

В общем, ограниченное поле  можно построить, только если  - простое число или степень простого числа. Если  - простое число, умножение и сложение базируются на арифметике по модулю , как сказано выше. Если , где  - простое число, а  - какое-либо целое, возможно расширить поле  до поля . Последнее называется расширенным полем . Умножение и сложение элементов в расширенном поле базируется на арифметике по модулю .

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

Предположим, что  и  - какие либо два кодовых слова в  кодовом блоке. Мера разницы между кодовыми словами - число соответствующих элементов или позиций, в которых они различаются. Эта мера называется расстоянием Хемминга между двумя кодовыми словами и обозначается . Ясно, что  при   удовлетворяет условию. Наименьшее значение из набора для кодовых слов называется минимальным расстоянием кода и обозначается . Поскольку хеммингово расстояние является мерой различия между парами кодовых слов, оно, разумеется, имеет отношение к коэффициенту корреляции между соответствующими парами сигналов, генерируемыми кодовыми словами. Эта связь обсуждается в разделе 8.1.4.

Помимо классификации кодов на двоичные и недвоичные можно также их классифицировать на линейные и нелинейные. Возьмем  и  - два кодовых слова в блоковом коде  и ,  - какие-либо два скалярных элемента из определённого алфавита. Тогда код называют линейным, если и только если  тоже является кодовым словом. Это определение подразумевает, что линейный код должен содержать кодовое слово из одних нулей. Как следствие, код с постоянным весом нелинейный.

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

.                            (8.1.1)

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

Если пользоваться терминами, предназначенными для двоичных блоковых кодов, векторное пространство  состоит из  двоичных векторов с  элементами. Линейный  код является ансамблем  векторов с  элементами, называемыми кодовыми словами, которые формируют подпространство  в поле из двух элементов. Поскольку имеется  кодовых слов в , базис для  имеет  кодовых слов. Это значит, что для конструирования  линейных комбинаций требуется  линейно независимых кодовых слов, которые формируют весь код. Нуль-пространство для  образует другой линейный код, который состоит из  кодовых слов блока длиной  с  информационными битами. Его размерность равна . В разделе (8.1.1) мы рассмотрим эти соотношения с большими подробностями.