Мажоритарное декодирование линейных блочных кодов

Идею мажоритарного декодирования линейных блочных кодов можно продемонстрировать на очень простом примере.

Пусть m – кодируемая информационная последовательность, состоящая всего из одного символа m₀ = 0 или 1, а соответствующее ей кодовое слово помехоустойчивого (избыточного) кода имеет вид U = ( m₀ , m₀ , m₀ ), то есть ( 000 ), если m₀ = 0, или ( 111 ), если m₀ = 1 (код с трехкратным повторением).

Допустим, передано кодовое слово U = (111) и в первом символе произошла одна ошибка, то есть принята последовательность r = ( 011 ).

Вопрос: какая последовательность передавалась, U = ( 000 ) или U = (111)?

Здравый смысл подсказывает, что, скорее всего, передавалось кодовое слово U = ( 111 ), так как в противном случае ошибка должна была бы исказить два символа, чтобы кодовое слово U = ( 000 ) превратилось в последовательность вида r = ( 011 ). Может быть, и не отдавая себе отчета в правиле принятия решения (о том, что передавалось), мы приняли решение по большинству – мажоритарно.

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

Рассмотрим более сложный пример – мажоритарное декодирование для (7,4)-кода Хемминга.

Пусть передано кодовое слово (7,4)-кода – U = (U₀ ,U₁ ,U₂ ,U₃ ,U₄ ,U₅ ,U₆ ), символы которого сформированы в соответствии с системой проверочных уравнений (правилом кодирования) вида:

U₀ = m₀ ,
U₁ = m₁ ,
U₂ = m₂ ,
U₃ = m₃ , (3.28)
U₄ = m₀ + m₂ + m₃ ,
U₅ = m₀ + m₁ + m₂ ,
U₆ = m₁ + m₂ + m₃ .

На входе декодера наблюдается принятая последовательность r = (r₀ , r₁ , r₂ , r₃ , r₄ , r₅ , r₆ ), и необходимо ее декодировать, то есть определить вид передаваемой информационной последовательности m .

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

Для начала предположим, что ошибок в принятой последовательности r нет, то есть r = U .

Тогда по принятой последовательности r можно легко найти оценку переданной информационной последовательности m^*, причем не единственным способом.

Во-первых, можно сразу записать

m₀ ^*1 = r₀ ,

m₁ ^*1 = r₁ , (3.29)

m₂^*1 = r₂ ,

m₃^*1 = r₃ ,

то есть в качестве ответа или результата декодирования, взять первые четыре символа принятой последовательности.

Но это не единственный способ. Учитывая, что для элементов поля GF(2) справедливо условие m_i + m_i = 0 ( то есть 1+1 = 0 и 0+0 = 0), можно записать еще несколько систем уравнений для определения m_i*:

m₀ ^*2 = r₂ + r₃ + r₄ , m₀ ^*3 = r₁ + r₂ + r₅ ,

m₂^*2 = r₀ + r₃ + r₄ , m₂^*3 = r₀ + r₁ + r₅ ,

m₀ ^*4 = r₁ + r₄ + r₆ , m₀ ^*5 = r₃ + r₅ + r₆ ,

m₂^*4 = r₄ + r₅ + r₆ , m₂^*5 = r₁ + r₃ + r₆ ,

m₃ ^*4 = r₀ + r₅ + r₆ ; m₃ ^*5 = r₁ + r₄ + r_{5 .}

Таким образом, получилось пять независимых систем уравнений для определения одних и тех же компонент вектора m^*, причем, они будут совместными (иметь одинаковые решения) только при отсутствии ошибок в принятой последовательности r, то есть при r = U. В противном случае решения для m_i^*, даваемые различными системами, будут разными.

Однако можно заметить следующее: в выражениях для m_i^* каждый из элементов принятой последовательности r_i присутствует не более двух раз (то есть не более чем в двух уравнениях из пяти).

Если считать, что в принятой последовательности возможна только одиночная ошибка (а с ошибкой большей кратности этот код не справляется), то ошибочными будут решения не более чем двух уравнений из пяти для каждого из элементов m_i^*, остальные три уравнения дадут правильное решение. Тогда правильный ответ может быть получен по "большинству голосов", или мажоритарно.

Устройством, которое принимает решение по "большинству", является так называемый мажоритарный селектор. При этом схема мажоритарного декодера для одного из символов принятой последовательности (7,4)-кода Хемминга может выглядеть, например, следующим образом (рис.3.7):

Рис. 3.7

Здесь мажоритарный селектор выполнен в виде аналогового сумматора и компаратора напряжений (напряжение на выходе компаратора = 1, если на его входе больше единиц, и равно 0 в противном случае). Однако возможна и чисто цифровая реализация мажоритарного селектора: он просто выдаст на своем выходе 1, если на его входе больше единиц, и 0 – в противном случае.