Элементы теории кодирования

 

   3. 2. Самокорректирующиеся коды

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

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

     Очевидно, что если исходное слово передавать без предварительного 
кодирования, то установить на выходе истинное сообщение практически 
невозможно. Поэтому возникает задача построения по исходному, любо 
му слову а₁ а₂...а_т его самокорректирующегося кода b₁ b₂…b_l (l > т), по      
зволяющего по полученному на выходе канала кода b₁ ^҆ b₂^҆…b_l^҆ однозначно      
восстановить передаваемый код b₁ b₂…b_l ,а значит, и исходное сообще-      
ние а₁ а₂...а_т .Напомним, что при передаче кода b₁ b₂…b_l по каналу связи      
код, возможно, исказился и, следовательно, на выходе канала будет сло-      
во b₁ ^҆ b₂^҆…b_l^҆ , вообще говоря, отличающееся от b₁ b₂…b_l не более чем в р      
позициях. 

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

3. 3. Коды Хемминга

     Перейдем к построению самокорректирующихся кодов для случая р = 1, которые называются кодами Хемминга. Будем считать, что в канале связи при передаче сообщения может произойти не более одной ошибки. Это означает, что если исходное сообщение а₁ а₂...а_т кодируется набором b₁ b₂…b_l ( l = m+k), то на выходе возможны следующие варианты кодов:b₁b₂…b_l; ̅b₁b₂…b_l ,b₁b̅₂…b_l, b₁b₂…̅b_l .   

     Таким образом, число вариантов равно l + 1. Поясним, что ошибка может не произойти, либо она произойдет в одном из l разрядов, и символ b_l заменится на противоположный b̅_i. Число дополнительных разрядов для построения кодов Хемминга нужно выбрать так, чтобы их хватило для кодирования перечисленных (l + 1) случаев. Следовательно, необходимо, чтобы

   2^k ≥ l + 1 или 2^m ≤     2 ^l

.

 
Поэтому, зная m, l выбираем как наименьшее целое число, удовлетворяющее условию:

2^m ≤     2 ^l                    

     

     Число l называется длиной кода Хемминга. Число т — число информационных символов.

Замечание. Учитывая, что l = m + k, можно выбирать не l, а число k, которое называется числом контрольных символов и является наименьшим целым числом, удовлетворяющим условию: 2^k ≥ k + тп + 1.

  Например, если т = 4, то l = 7, k = 3;

если  т = 9, то l = 13, k = 4.

     Таким образом, при построении кодов Хемминга, первое, что нужно 
сделать: это по числу т определить числа k и l.

3. 4. Алгоритм построения кода Хемминга

       Пусть для сообщения а = а₁а₂...а_m длины m необходимо построить код Хемминга. Возьмем m = 9; исходное сообщение

а = 101110111 =а₁а₂а₃а₄а₅а₆а₇а₈а₉.

Тогда l = 13, k = 4; код Хемминга β= b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁ b₁₂b₁₃.

1. Представим каждое число i из множества L = {1, 2, ..., l} в виде k -разрядного двоичного числа τ = V_k-1V_k-2….V₁V₀ . Результаты запишем в виде таблицы

 

2.  Разберем  множество L на k подмножеств следующим образом:

L₀ = {i ϵ L₀ : V₀ = 1};   L₀ = {1,3, 5, 7,9,11,13}, 
L₁ = {i ϵ L_x : V₁ = 1};    L₁ = {2, 3, 6, 7,10,11}, 
L₂ = {i ϵ L₂:V₂ = 1}    L₂ = {4,5,6,7,12,13},

L₃ = (i ϵ L₃ : V₃ = 1};          L₃ = {8,9,10,11,12,13}.

3. Первые элементы (их ровно k) этих множеств есть степени числа 2;

они определяют номера контрольных разрядов кода Хемминга. Остальные элементы множества  L определяют номера информационных разрядов. Следовательно, в коде Хемминга разряды b₁b₂b₄b₈ – контрольные, остальные разряды b₃b₅b₆b₇b₉b₁₀b₁₁b₁₂b₁₃ – информационные.

4. Формирование значений информационных символов.

       Информационные символы кода  Хемминга формируются естественным  образом из символов исходного  сообщения а₁а₂...а_т. А именно: b₃ = a₁; b₅ = a₂; b₆ = a₃; b₇ = a₄; b₉ = a₅; b₁₀ = a₆; b₁₁ = a₇; b₁₂ = a₈; b₁₃ = a₉.

        Так как исходное сообщение  α = 101110111, то b₃ = 1; b₅ = 0; b₆ = 1;b₇ = 1; b₉ = 1; b₁₀ = 0; b₁₁ = b₁₂ = b₁₃ = 1.

5. Формирование значений контрольных символов.

      После определения информационных символов контрольные символы определяются следующим образом:

b₁ = ⊕∑ b_j;  j ϵ L₀; j ≠ 1,

b₂ = ⊕∑ b_j;  j ϵ L₁;  j ≠ 2,

b₄ = ⊕∑ b_j;  j ϵ L₂; j ≠ 4,

b₈ = ⊕ ∑ b_j; j ϵ L₃;  j ≠ 8,

        Здесь ⊕∑ - сумма по модулю два, b_j – разряды, имеющие номера из соответствующих множеств L_l.

        В примере будем иметь:

b₁ =  b₃ ⊕ b₅  ⊕ b₇ ⊕ b₉ ⊕ b₁₁ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1

b₂ =  b₃ ⊕  b₆  ⊕  b₇ ⊕ b₁₀ ⊕ b₁₁ = 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1

b₄ =  b₅ ⊕  b₆  ⊕  b₇ ⊕ b₁₂ ⊕ b₁₃ = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1

b₈ =  b₉ ⊕  b₁₀  ⊕  b₁₁ ⊕ b₁₂ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0

6. Окончательно, для сообщения α = 101110111 код Хемминга β будет следующим: β = b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃ = 1010011010111.

        Таким образом, можно построить  код Хемминга для сообщения  с любым набором длины т.