Основы теории передачи информации

  35790931     

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


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

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

), если  m0 = 0, или ( 111 ), если  m0

= 1 (код с трехкратным повторением).

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

).

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

U = (111)?

Здравый смысл подсказывает, что, скорее всего, передавалось кодовое слово U

= ( 111 ), так как в противном случае ошибка должна была бы исказить два символа, чтобы кодовое слово U = ( 000

) превратилось  в последовательность вида r = ( 011

).  Может быть, и не отдавая себе отчета в правиле принятия решения (о том, что передавалось), мы приняли решение по большинству – мажоритарно.

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

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

Пусть передано кодовое слово (7,4)-кода – U = (U0 ,U1 ,U2 ,U3 ,U4 ,U5 ,U6 ), символы которого сформированы в соответствии с системой проверочных уравнений (правилом кодирования) вида: 

U0  =  m0 ,



U1  =  m1 ,

U2  =  m2 ,

U3  =  m3 ,                                                                 (1.28)

U4  =  m0  + m2  + m3 ,

U5  =  m0  + m1  + m2 ,

U6  =  m1  + m2  + m3 .                                                     

На входе декодера наблюдается принятая последовательность r = (r0 , r1 ,  r2 ,  r3 ,  r4 ,  r5 , r6  ), и  необходимо ее декодировать, то есть определить вид передаваемой информационной последовательности m .


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

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

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

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

                                                  m0 *1  = r0 ,

                                              m1 *1  = r1  ,                                                                               (1.29)

                                                 m2*1  = r2  ,

                             m3*1  = r3 ,                                                                                                                               

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


Содержание раздела