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

      Если  же  вероятность  ошибки  в  канале  будет  в  сто  раз меньше  Р_ош = 10 ^-5, то  вероятность ее неисправления   составит уже Р(N) » 2×10 ^-9,  или в   5000 раз меньше!

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

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

    Другими словами, помехоустойчивое кодирование существенно улучшает свойства хороших каналов, в плохих же каналах оно большого эффекта не дает. [17] 
 
 
 
 
 
 
 
 
 
 

    1.3 Циклические коды

    Линейный (n,k)-код называется циклическим, если в результате циклического сдвига кодового слова получается другое кодовое слово данного кода.  Другими словами, если  U = ( U₀, U₁, ...U_{n- 1} ) является кодовым словом, то и V = ( U_{n- 1}, U₀, U₁, ...U_{n- 2} ), полученное циклическим сдвигом U, является кодовым словом данного кода.[4]

    Циклические коды привлекательны по двум причинам.

    Во-первых, операции кодирования и вычисления синдрома для них выполняются очень просто с использованием сдвиговых регистров.

    Во-вторых, этим кодам присуща алгебраическая структура, и можно найти более  простые и эффективные способы  их декодирования.

    Основные  свойства циклических кодов:

    g(x)=1 + g₁ × x + g₂ × x² +...+ g_n-k-1 × x^n-k-1 + x^n-k,                             (1.60)  

  вида 
называемый порождающим полиномом кода.

                              U(x)= m(x) × g(x).                                                        (1.61)    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.3.1 Кодирование с использованием циклических кодов 

    Предположим, надо закодировать некоторую информационную последовательность

                                m = ( m₀, m₁, m₂... m_{k- 1} ).                                           (1.62)  

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

                 m(x)= m₀ + m₁ × x + m₂ × x² +...+m_{k- 1} × x^k-1.                                 (1.63)  

    Умножив  m(x) на x^n-k:

     x^n-k × m(x)= m₀ × x^n-k + m₁ × x^n-k+1 +...+m_{k- 1} × x^n-1 ,                                  (1.64)  

получим полином степени n-1 или меньшей.

    Воспользовавшись  теоремой о делении полиномов, можно  записать

               x^n-k × m(x) = q(x) × g(x) + r(x) ,                                                     (1.65)  

где  q(x) и r(x) — частное и остаток от деления полинома x^n-k × m(x) на порождающий полином g(x).

    Поскольку  степень  g(x)   равна (n-k), то степень r(x) должна  быть  (n-k-1)  или меньше, а сам полином r(x) будет иметь вид

                 r(x)= r₀ + r₁ × x + r₂ × x² +...+ r_{n- k- 1} × x^n-k-1 .                              (1.66)  

    С учетом правил арифметики в GF(2) данное выражение можно переписать следующим образом:

                   r(x) + x^n-k × m(x) = q(x)× g(x) ,                                                  (1.67)  

откуда  видно, что полином r(x)+x^n-k × m(x) является кратным g(x) и имеет степень n-1 или меньшую. Следовательно, полином r(x)+x^n-k × m(x) - это кодовый полином, соответствующий кодируемой информационной  последовательности m(x).

    Раскрыв последнее выражение, получим

r(x)+m(x)× x^n-k =r₀ +r₁ x +r₂ x²  ..+r_{n- k-1} x^n-k-1 + m₀ x^n-k + m₁ × x^n-k+1 + ..+ m_k-1 x^n-1,

что соответствует кодовому слову

    Таким образом, кодовое слово состоит  из неизменной информационной части  m, перед которой расположено (n-k) проверочных символов. Проверочные символы являются коэффициентами полинома r(x), то есть остатка от деления m(x) × x^n-k на порождающий полином g(x).

    Чтобы полученный результат был понятнее, напомним, что умножению некоторого двоичного полинома на x^n-k соответствует сдвиг двоичной последовательности m  =  (m₀, m₁ ... m_k-1)  на  n-k  разрядов вправо.

      Рассмотрим пример. С использованием кода, задаваемого порождающим полиномом g(x) = 1 + x + x³, закодируем произвольную последовательность, например m = (0111).

    Последовательности  m =(0111) соответствует полином m (x)=x+ x² + x³.

    Умножим m(x) на x^n-k :

    m(x) × x^n-k =m(x) × x³ =(x + x² + x³) × x³ = x⁴ + x⁵ + x⁶ .                         (1.68)  

    Разделим  m(x) × x^n-k на порождающий полином g(x) :

      
X⁵ + 0  + X³ 
 X⁵ + 0 + X³ +X² 
      X²=r(x).                                                      (1.69)  

    Таким образом, кодовый полином, соответствующий  информационной последовательности m = (0111), будет иметь следующий вид:

    U(x) =   0*X⁰ + 0*X¹ + 1*X² +  0*X³ + 1*X⁴ + 1*X⁵ + 1*X⁶,                (1.70)  

а соответствующее кодовое слово  U = (0010111).

    Итак, циклический (n,k)-код k-разрядной информационной последовательности m = (m₀, m₁ ... m_k-1) получают следующим образом:

    -  информационную последовательность  m умножают на x^n-k, то есть сдвигают вправо на n-k разрядов;

    -  полином полученной последовательности делят на порождающий полином кода g(x);