Программная модель помехоустойчивого кодирования

= (r₀  + r₂ + r₃ + r₄ ), ( r₀  + r₁  + r₂  + r₅ ), ( r₁  + r₂  + r₂  + r₆  ),                    (1.23)              

или

S₀=r₀+r₂+r₃+r₄,  
S₁  =  r₀  + r₁  + r₂  + r₅ ,                                                                  (1.24)                
S₂  =  r₁  + r₂  + r₂  + r₆  .                                                                   

      Основываясь на полученных соотношениях, можно легко организовать схему для вычисления синдрома. Для (7,4)-кода Хемминга она приведена на рис. 1.5.

Рис. 1.5  
 
 
 
 
 
 
 
 
 

1.2.4 Синдромное декодирование линейных блочных кодов 

      Покажем, как можно  использовать синдром принятого  вектора не только для обнаружения, но и для исправления ошибок.

    Пусть U = ( U₀ , U₁ , …, U_n-1 ),  e  = ( е₀ , е₁, …, е_n-1 ) и r  =  ( r₀ , r₁, r₂ , …, r_n-1) являются передаваемым кодовым словом, вектором-ошибкой и принятым вектором  соответственно. Тогда

      r   =  U  + e              (1.25)

и синдром

   S = r×H^T = (U + e )× H^T = U× H^T + e× H^T = 0 + e× H^T =  e× H^T ,                     (1.26)

поскольку для любого кодового слова  U × H^T  = 0.

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

                                            U*  =  r  + e .                                                        (1.27)

      На примере одиночных  ошибок при кодировании с использованием линейного блочного (7,4)-кода покажем, как вектор ошибки связан с синдромом, и как, имея синдром, локализовать и устранить ошибки, возникшие при передаче. [7]

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

e_ = ( 0000000 ),

e₀ = ( 1000000 ),

e₁ = ( 0100000 ),

e₂ = ( 0010000 ),

e₃ = ( 0001000 ),

e₄ = ( 0000100 ),

e₅ = ( 0000010 ),

e₆ = ( 0000001 ),

      Все возможные для (7,4)-кода одиночные ошибки и соответствующие им векторы  синдрома приведены в табл. 1.3.

Таблица 1.3

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

      Например,  если   синдром,   вычисленный   по принятому  вектору,   равен ( 111 ), это значит,  что произошла одиночная ошибка  в  третьем символе,  если S = ( 001 ) – то в последнем, и т.д.  [9]

      Если место ошибки определено, то устранить ее уже не представляет никакого труда.

    Полная  декодирующая схема для (7,4)-кода Хемминга, использующая синдром вектора r  не только для обнаружения, но и для исправления ошибок,  приведена на рис. 1.6.

    Рис. 1.6

    А теперь посмотрим, что произойдет, если в принятой последовательности будет  не одна, а, например, две ошибки. Пусть  ошибки возникли во второй и шестой позициях e = ( 0100010 ). Соответствующий синдром определится как

  S = ( 0100010 ) = (001).

    Однако  синдром  S = ( 001 ) соответствует также и одиночной ошибке в седьмой позиции ( e₆ ). Следовательно, наш декодер не только не исправит ошибок в позициях, в которых они произошли, но и внесет ошибку в ту позицию, где ее не было. Таким образом, видно, что (7,4)-код не обеспечивает исправления двойных ошибок, а также ошибок большей кратности.

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

      1.2.5 Вес и расстояние Хемминга. Способность кодов обнаруживать  и исправлять ошибки 

    Рассмотрим, чем определяется способность блочного кода обнаруживать и исправлять ошибки, возникшие при передаче.

    Пусть U = (U₀, U₁, U₂, ...U_n-1) - двоичная последовательность длиной  n.

    Число единиц (ненулевых компонент) в этой последовательности называется весом Хемминга  вектора  U  и обозначается   w(U).

    Например, вес Хемминга вектора U = ( 1001011 ) равен четырем, для вектора U = ( 1111111 ) величина  w(U) составит 7 и т.д.

    Таким образом, чем больше единиц в двоичной последовательности, тем больше ее вес Хемминга.

    Далее, пусть U и V  будут двоичными последовательностями длиной n.

    Число разрядов, в которых  эти последовательности различаются, называется расстоянием Хемминга   между U и V  и обозначается d( U, V).

    Например, если U = ( 1001011 ),  а V = ( 0100011 ), то d( U, V) = 3.

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

    Можно проверить и убедиться, что минимальное кодовое расстояние для рассматриваемого нами в примерах (7,4)-кода равно трем: d_min(7,4) = 3. Для этого нужно записать все кодовые слова (7,4)-кода Хемминга (всего 16 слов), вычислить расстояния между их всеми парами и взять наименьшее значение. Однако можно определить d_min блочного кода и более простым способом.