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

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

Пусть 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₂^*2 = r₀ + r₃ + r₄ , m₂^*3 = r₀ + r₁ + r₅ ,

m₃ ^*2 = r₀ + r₂ + r₄ ; m₃ ^*3 = r₁ + r₂ + r₆ ;

(3.30)

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₆ ,

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 – в противном случае.

Дата добавления: 2014-01-07