Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.1. Коды с обобщенными проверками на четность

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

где принимают значения 0 или 1, а означает сложение по модулю 2. Отметим, что если посимвольно прибавить к первому кодовому слову второе кодовое слово

то получим

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

В качестве второго примера определим кодовое слово -кода равенством

Если посимвольно прибавить к а второе кодовое слово то получим слово с, в котором

Таким образом, три проверочных символа в слове с определяются точно так же, как в а и в поэтому с также является кодовым словом.

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

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

Отсюда вытекает, что множество расстояний от фиксированного кодового слова до всех других кодовых слов совпадает с множеством всех весов этого кода. Другая формулировка этого свойства состоит в том, что расстояние между двумя кодовыми

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

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

1) сумма двух элементов группы всегда лежит в группе (замкнутость)

2) выполняется закон ассоциативности, так что

3) группа всегда содержит единичный элемент (нулевое слово);

4) каждый элемент группы обладает обратным (в случае двоичного кода каждое слово совпадает со своим обратным), для которого

Ясно, что коды с обобщенными проверками на четность, определенные в этом подразделе, характеризуются всеми четырьмя указанными свойствами. Примеры кодов, обсуждаемые в этой главе, были определены над «полем» из двух элементов с помощью арифметики по модулю 2. Можно, однако, определить недвоичные коды, используя конечное поле из элементов 2). Все утверждения, сформулированные для двоичных кодов, справедливы и для недвоичных кодов. Арифметические операции в недвоичных полях будут рассмотрены в подразд. 2.2.1. Важный тип недвоичных кодов, коды Рида — Соломона, будет описан в разд. 2.3.

<< Предыдущий параграф Следующий параграф >>
Оглавление