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

    Определение. Линейный блочный систематический (n,k)-код полностью определяется матрицей G размером k * n с двоичными матричными элементами. При этом  каждое кодовое слово является линейной комбинацией строк матрицы  G, а каждая линейная комбинация строк   G - кодовым словом.

    Пусть m = (m₀ , m₁ ,. . . , m_{k -1}) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.

    Тогда соответствующим ему кодовым  словом   U   будет

                                               U = m× G .                                                  (1.11)          

    С учетом структуры матрицы  G  символы кодового слова U будут такими:

    для  i = 0, 1, 2,. . . , k- 1

                                          U_i = m_i ;                                                           (1.12)

    для  i = k, k+1,. . . , n

          U_i = m₀× P_0j + m₁× P_1j + m₂× P_2j +…+ m_{k- 1}× P_{k- 1, j} .                          (1.13)

    Иными словами,  k  крайних левых символов кодового слова совпадает с символами  кодируемой   информационной последовательности,  а остальные   (n - к) символов являются  линейными комбинациями символов информационной последовательности.

    Определенный  таким образом код называется линейным блочным систематическим (n,k)-кодом с обобщенными проверками на четность, а задающая  его  матрица  G   называется порождающей матрицей кода. [14]

    В качестве примера рассмотрим  известный (7,4)-код Хемминга, являющийся классической иллюстрацией простейших кодов с исправлением ошибок. 

    Пусть  m = (m₀, m₁, m₂, m₃)  будет тем сообщением, или информационной последовательностью,  которую нужно закодировать.

    Порождающая матрица G  для (7. 4)-кода Хемминга имеет вид 

    Тогда символы соответствующего кодового слова определяются следующим образом : 

=    (m₀ , m₁ , m₂ , m₃ , m₀ + m₂ + m₃ , m₀ + m₁ + m₂ , m₁ + m₂ + m₃ ),             (1.15)

или

U₀=m₀,  
U₁=m₁,  
U₂   =   m₂ ,  

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

      Например, пусть  m =  ( 1 0 1 1 ) ,  тогда соответствующее кодовое слово будет иметь вид    U =  ( 1 0 1 1 1 0 0 ).  Или другой пример: пусть  m  = ( 1 0 0 0 ),  тогда    U  =  ( 1 0 0 0 1 1 0 ). 

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

    На  основании порождающей матрицы  G_(7,4) (1.15) или приведенной системы проверочных уравнений (1.16) легко реализовать схему кодирования для рассматриваемого (7,4)-кода Хемминга  (рис. 1.4).

    Кодер работает точно так же, как и при простой проверке на четность,  но теперь выполняет не одну общую, а несколько частичных проверок, формируя, соответственно,  несколько проверочных символов.[14] 

    Рис. 1.4  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1.2.3 Синдром и обнаружение ошибок 

      Пусть  U = ( U₀ , U₁ ,… U_n  ) является кодовым словом, переданным по каналу с помехами, а r  = ( r₀ , r₁ , ... r_n  )  - принятой последовательностью, возможно, отличающейся от переданного кодового слова U.  Отличие r  от   U  состоит в том, что некоторые символы r_i  принятой последовательности  могут отличаться от соответствующих символов U_i  переданного кодового  слова.  Например,  U  =  ( 0 0 0 1 0 0 0 ) ,  а   r  = ( 0 0 0 0 0 0 0  ) , то есть произошла ошибка в четвертом символе кодового слова,  1 перешла в 0 .  Или другой пример:  передано кодовое слово   U  =  ( 0 0 1 1 1 1 ),  а принятая  последовательность  имеет вид   r = ( 1 0 1 1 1 1 1  ), то есть ошибка возникла в первом бите кодового слова, при этом  0 перешел в единицу. [5]

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

      Так, вектор ошибки  e  =  ( 0 0 0 1 0 0 0 ) означает однократную ошибку в четвертой позиции (четвертом бите),  вектор ошибки e  =  ( 1 1 0 0 0 0 0 ) - двойную ошибку в первом и втором битах и т.д.

      Тогда при передаче кодового слова U по каналу с ошибками принятая последовательность  r  будет иметь вид

                                                r   =  U  + e ,                    (1.21)

например:     U  =  ( 0 0 0 1 0 0 0 ),

       e  =  ( 0 0 0 1 0 0 0 ),                (1.22)

r  =  ( 0 0 0 0 0 0 0  ) .                                     

      Приняв вектор r , декодер сначала должен определить,  имеются ли в принятой последовательности ошибки. Если ошибки есть, то он должен выполнить действия по их исправлению.

      Чтобы проверить, является ли принятый вектор  кодовым словом, декодер вычисляет (n-k)-последовательность, определяемую следующим образом :

                 S = ( S₀ , S₁ , … , S_n-k-1 ) = r ×  H^T.                                       (1.23)

      При этом  r  является кодовым  словом  тогда,  и  только  тогда, когда S = (00..0), и  не является кодовым словом данного кода, если S ¹ 0. Следовательно, S используется для обнаружения ошибок, ненулевое значение  S служит признаком наличия ошибок в принятой последовательности. Поэтому вектор  S  называется синдромом принятого вектора   r.

      Некоторые сочетания  ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово U под влиянием помех превратилось в другое действительное кодовое слово  V  этого же кода,  то синдром S = V * H^T = 0 . В этом случае декодер ошибки не обнаружит и, естественно, не попытается ее исправить.

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

      Для рассматриваемого в качестве примера линейного блочного систематического (7,4)-кода Хемминга синдром определяется следующим образом:

      пусть принят вектор  r   =  ( r₀ , r₁ , r₂ , r₃ , r₄ , r₅ , r₆ ),  тогда