4.14. Мажоритарные циклические коды

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

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

Параметры некоторых из известных -кодов при малых значениях длины кодовой комбинации совпадают с параметрами кодов БЧХ. С ростом длины кодовой комбинации скорость передачи -кодов становится меньше, чем скорость передачи кодов БЧХ, причем эта разница тем значительней, чем больше длина кодовой комбинации. Однако аппаратурная реализация -кодов предпочтительна по сравнению с кодами БЧХ. К их достоинствам следует отнести и то, что они способны исправлять не только ошибки кратности но и некоторые сочетания более высокой кратности.

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

Так как уравнения можно решить относительно символа

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

где индексы при суммируются по модулю

Пусть каждый столбец, исключая первый слева матрицы Но, в качестве вектор-строк которой выбраны упомянутые векторов, содержит не более X единиц. Тогда алгоритм мажоритарного декодирования, основанный на решении уравнений системы (4.21), позволяет исправлять любые или менее ошибок, где Квадратными скобками обозначена операция округления до ближайшего меньшего целого числа. Число X называют показателем связности системы контрольных соотношений. Если то говорят о системе разделенных контрольных соотношений.

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

Рассмотрим систему -связанных контрольных соотношений для данного кода. Проверочная матрица кода, построенная известным способом:

Из данной матрицы получим матрицу вектор-строки которой задают контрольные соотношения с показателем связности

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

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

где индексы суммируются по модулю

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

Дальнейшим обобщением понятия -связанных контрольных соотношений является понятие квазиразделенных соотношений. Система контрольных соотношений называется квазиразделенной, если в каждое соотношение входит одно и то же подмножество символов и любой символ входит не более чем в одну проверку. Из этого определения следует, что система из квазиразделенных контрольных соотношений позволяет вычислить сумму независимыми способами (включая тривиальное соотношение). Например, контрольные соотношения являются квазиразделенными и позволяют двумя независимыми способами вычислить сумму Учитывая тривиальное соотношение получаем три независимых соотношения:

Мажоритарное декодирование циклических кодов с квазиразделенными контрольными соотношениями существенно отличается от декодирования кодов с -связанными соотношениями. В последнем случае на выходе

мажоритарного элемента появляется переданная последовательность символов При квазиразделенных соотношениях на выходе мажоритарного элемента получаем последовательность

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

Пример. Дай циклический -код с для которого справедлива следующая система квазиразделенных соотношений:

Необходимо произвести разделение системы квазиразделенных соотношений для построения схемы декодирования.

Из системы (4.23) получаем уравнения

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

В табл. 45 [130] приведены параметры некоторых циклических кодов, допускающих мажоритарное декодирование.

В заключение необходимо отметить, что кроме некоторых кодов БЧХ, мажоритарное декодирование допускают коды Хэмминга с

(см. скан)