3.2. Методы декодирования линейных кодов

Рассмотрим далее методы декодирования линейных кодов. Пусть переданный кодовый вектор, а — соответствующий ему принятый вектор (получающийся в результате разбиения последовательности символов на выходе демодулятора на блоки длины в соответствии с разбиением на блоки передаваемой последовательности). Вектор называется вектором ошибок, а вектор синдромом, соответствующим вектору Как следует из формулы (3.1), Поэтому

Векторы называются сравнимыми по модулю С, если (12]; сравнимость векторов обозначается следующим образом: Из определения сравнимости векторов непосредственно следует, что: 1) если то и 3) если то В этом случае, как хорошо известно, множество можно разбить на непересекающиеся классы таким образом, что любые два вектора из одного класса будут сравнимы по модулю С, но любые два вектдра из разных классов не будут сравнимыми по модулю С. Эти классы называют смежными классами (см. утверждение 2.5 и раздел, посвященный нормальным делителям). Смежный класс, содержащий вектор х, будем обозначать через Заметим, Что смежный класс (0) совпадает с кодом С. В общем случае

Это соотношение показывает, что каждый смежный класс состоит из векторов. Число различных смежных классов равно Так как в силу (3.1)

то необходимым и достаточным условием того, что векторы х и у принадлежат одному смежному классу, является равенство

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

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

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

1) По принятому вектору и вычисляется синдром

2) С помощью таблицы декодирования находится вектор ошибок соответствующий данному кодовое слово и посылается на выход декодера.

Задача 3.3. Описать таблицу декодирования в случае, если часть ошибок декодируется (исправляется), а другая часть обнаруживается.

Пример 3.2. Рассмотрим двоичный линейный -код, задаваемый проверочной матрицей

Этот код получается -кода Хэмминга, описанного в примере 1.4 из разд. 1.1, удалением третьей компоненты во всех кодовых словах и изменением нумерации остальных компонент. В первой строке табл. 3.1 перечислены все кодовые векторы рассматриваемого кода. Поскольку таблица имеет большие

Таблица 3.1 (см. скан) Смежные классы кода из примера 3.2

размеры, то двоичные векторы записаны в восьмеричном представлении; например, вектору (101110) соответствует запись (56). В каждой из других строк этой таблицы перечислены векторы одного из смежных классов. Так как этот код исправляет все одиночные ошибки (см. пример 1.4), то все векторы веса 1 можно взять в качестве лидеров смежных классов. В последнем смежном классе вектор (000110) является вектором минимального веса, так что его можно выбрать в качестве лидера этого смежного класса. Таким образом, рассматриваемый код исправляет все одиночные ошибки и одну ошибку веса 2. При использовании этого кода в ДСК для исправления ошибок вероятность правильного декодирования равна

(предполагается, что все кодовые векторы посылаются с равными вероятностями).

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

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

векторов веса Если канал является ДСК или обобщением ДСК на -ичный случай, то в классе линейных кодов с одинаковыми параметрами квазисовершенные коды имеют минимальную, вероятность ошибки декодирования. Квазисовершенные так же как и совершенные коды, могут не существовать при некоторых значениях и d (например, двоичные квазисовершенные коды с параметрамии существуют, а двоичный квазисовершенный код с параметрами не существует [10]), однако квазисовршенных кодов существует гораздо большй, чем совершенных. Например, квазисовершенными являются из примера 3.2 и все двоичные БЧХ-коды, исправляющие ошибки веса 2 [11]. Кроме того, при всегда существует по крайней мере один квазисовершенный код с любым наперед заданным числом проверочных символов (утверждение 3.9).

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

Утверждение 3.4. Если в линейном двоичном существуют кодовые векторы нечетного веса, то их число равно Более того, множество всех кодовых векторов четного веса образует подкод размерности

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

Утверждение 3.5. Если хотя бы один из кодовых векторов -ичного линейного имеет ненулевую компоненту, то число кодовых векторов, компонента которых равна элементу а поля составляет

Краткое доказательство. Множество всех кодовых векторов, компонента которых равна нулю, является подпространством размерности Для доказательства утверждения следует

рассмотреть порождаемое этим Подпространством разложение рассматриваемого кода на смежные классы. Множество кодовых векторов, имеющих одну и ту же компоненту, является одним из смежных классов этого разложения.

Утверждение 3.6 [8]. Если для каждого целого в коде существует хотя бы один кодовый вектор, компонента которого не равна нулю, то сумма весов всех кодовых векторов -ичного линейного -код равна

Идея доказательства. Следует воспользоваться тем, что, согласно утверждению 3.5, число кодовых векторов, компонента которых не равна нулю, составляет

Утверждение 3.7. Пусть С представляет собой -ичный линейный Тогда:

1) если код С обнаруживает пачки ошибок длины и менее, то

2) если исправляет пачки ошибок длины и менее, то

Эти соотношения известны как нижние границы Рейджера [12].

Краткое доказательство. Пусть множество векторов из все компоненты которых с по равны нулю. Рассмотрим случай 1. Предположим, что два различных вектора из принадлежат одному и тому же смежному классу по подгруппе С. Тогда существует ненулевой вектор принадлежащий коду С, т. е. код С не обнаруживает по крайней мере одну пачку ошибок длины или менее, какой является вектор Следовательно, число смежных классов не может быть меньше, чем Отсюда следует, что Рассмотрим случай 2. Аналогично можно доказать, что никакие два различных вектора из не должны входить в один смежный класс. Следовательно, число смежных классов не может быть меньше, чем т. е.

Утверждение 3.8 [13]. Пусть С — двоичный линейный -код с минимальным расстоянием и порождающей матрицей Предположим, что среди лидеров смежных классов (в качестве которых берутся векторы минимального веса) существуют векторы веса или более-, пусть и — один из таких лидеров. Тогда минимальное расстояние двоичного линейного

задаваемого порождающей матрицей равно .

Краткое доказательство. Пусть кодовый вектор кода С. Если то вес не меньше чем так как Если то Это равенство показывает, что вектор принадлежит тому же смежному классу, что и вектор а следовательно, вес не меньше чем

Утверждение 3.9 [13]. В утверждении 3.8 положим Если код С не является квазисовершенным, то условия утверждения 3.8 выполняются, так что существует код С с Если в свою очередь код С не является квазисовершенным, то по С описанным в утверждении 3.8 способом можно построить новый код и т. д. Эта процедура всегда приводит к квазисовершенному коду.

Краткое доказательство. Заметим, что каждый вновь построенный код имеет то же число проверочных символов, что и исходный код. Граница Хэмминга в этом частном случае имеет следующий вид:

Из этого неравенства видно, что описанная выше процедура построения последовательности кодов должна закончиться через конечное число шагов.

Утверждение 3.10 [8]. Двоичные квазисовершенные коды длины исправляющие одиночные ошибки, существуют для всех заключенных в пределах где произвольное четное число, и где произвольное нечетное число.

Краткое доказательство. Квазисовершенными кодами длины при четном при нечетном являются коды, столбцами проверочных матриц размера которых являются: 1) все вектор-столбцы, первые компонент которых равны нулю, и 2) все вектор-столбцы, последние компонент которых равны нулю (нулевые векторы в число столбцов проверочной матрицы не включаются). Поскольку произвольный вектор-столбец длины может быть представлен в виде суммы вектор-столбца первого

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