Мажоритарное декодирование

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

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

– символ входит в каждое уравнение проверки;

– любой символ , , входит не более чем в уравнений проверок.

Если , то проверки называют раздельными. Под системой раздельных проверок для символа понимают систему уравнений, удовлетворяющих двум условиям:

– символ входит в каждое уравнение проверок;

– любой символ , , входит не более чем в одно уравнение проверки.

Кроме нетривиальных проверок в систему проверок может включаться тривиальная проверка .

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

Пример 1.

Разработать систему проверок для мажоритарного декодирования кода (7,4), исправляющего однократную ошибку. Контрольная матрица кода имеет вид:

Решение.

Кодирующее устройство реализует следующие уравнения:

Декодирующее устройство реализует систему уравнений проверок для каждого информационного символа , . Система уравнений проверок составляется путем сложения по модулю 2 строк матрицы H. Полученная система проверок имеет вид:

Можно видеть, что некоторые символы входят в систему уравнений 2 раза. Это означает, что связность проверок . Требуемое число нетривиальных проверок и тривиальной проверки выполнено.

Пример 2.

Произвести декодирование по разработанной системе проверок кодового вектора

Выходы МЭ:

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

Предположим, что при передаче произошло искажение 2-го разряда, т.е. принятый КВ имеет вид:

Выходы МЭ:

Итак, однократная ошибка исправлена.

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

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