Алгоритм определения ошибки

Основная
литература:

1. Скляр
   Б. Цифровая связь. 
   М., Санкт-П, Киев: Изд. дом «Вильямс»,
   2003.

2. Передача
   дискретных сообщений: Учебник для ВУЗов
   / В. П. Шувалов, Н. В. Захарченко, В. О.
   Шварцман и др.; Под ред. В. П. Шувалова.
   – М.: Радио и связь, 1990 — 464 с.

Дополнительная
литература:

1. Макаров
   А.А., Прибылов В.П. Помехоустойчивое
   кодирование: Монография/СибГУТИ —
   Новосибирск, 2005

2. Захарченко
   И.Б. и др. Основы передачи дискретных
   сообщений. -М.: Радио и связь, 1990.

3. Мирманов
   А.Б. Курс лекций по дисциплине «Технология
   цифровой связи» — Астана: КазАТУ, 2009.
   (электронный)

Ключевые
слова:
Циклический код, синдром ошибки, полином,
базис.

Рассматриваемые
вопросы:

1. Понятие
   циклического кода.

2. Действия
   над многочленами при формировании
   комбинаций.

3. Алгоритм
   получения разрешенной кодовой комбинации
   циклического кода из комбинации
   простого кода.

4. Формирование
   базиса (производящей матрицы) циклического
   кода.

5. Построение
   кодера циклического кода.

6. Построение
   формирователя остатка циклического
   кода.

7. Структурная
   схема кодера циклического кода.

8. Определение
   ошибочного разряда в ЦК.

9. Алгоритм
   определения ошибки.

10. Выбор
    образующего полинома.

Тезисы к лекции

Циклический
код

Широкое
распространение на практике получил
класс линейных кодов, которые называются
циклическими.
Данное название происходит от основного
свойства
этих кодов: если некоторая кодовая
комбинация принадлежит циклическому
коду, то комбинация, полученная циклической
перестановкой исходной комбинации
(циклическим сдвигом), также принадлежит
данному коду.

.

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

Синдромом
ошибки в
этих кодах является наличие остатка от
деления принятой кодовой комбинации
на производящий полином.

В
теории циклических кодов кодовые
комбинации обычно представляются в
виде полинома. Так, n-элементную кодовую
комбинацию можно описать полиномом
(n-1) степени, в виде

(7.1)

где
a_i={0,1},
причем a_i=0
соответствуют нулевым элементам
комбинации, а a_i=1
— ненулевым.

Действия
над многочленами

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

,

Поскольку
.

Следует
отметить, что действия над коэффициентами
полинома (сложение и умножение)
производятся по модулю 2.

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

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

Алгоритм
получения разрешенной кодовой комбинации
циклического кода из комбинации простого
кода

Пусть
задан полином
,
определяющий корректирующую способность
кода и число проверочных разрядовr,
а также исходная комбинация простого
k-элементного кода в виде многочлена
.

Требуется
определить разрешенную кодовую комбинацию
циклического кода (n, k).

1. Умножаем
   многочлен исходной кодовой комбинации
   на
   

1. Определяем
   проверочные разряды, дополняющие
   исходную информационную комбинацию
   до разрешенной, как остаток от деления,
   полученного в предыдущем пункте
   произведения на образующий полином

1. Окончательно
   разрешенная кодовая комбинация
   циклического кода определится так

Для
обнаружения
ошибок в
принятой кодовой комбинации достаточно
поделить ее на производящий полином.
Если принятая комбинация — разрешенная,
то остаток от деления будет нулевым.
Ненулевой
остаток
свидетельствует о том, что принятая
комбинация содержит ошибки. По виду
остатка (синдрома) можно в некоторых
случаях также сделать вывод о характере
ошибки, ее местоположении и исправить
ошибку.

Формирование
базиса (производящей матрицы) циклического
кода

Формирование
базиса циклического кода возможно как
минимум двумя путями.

Вариант
первый.

1. Составить
   единичную матрицу для простого исходного
   кода.

2. Определить
   для каждой кодовой комбинации исходного
   кода группу проверочных элементов и
   дописать их в соответствующие строки
   матрицы.

Полученная
матрица и будет базисом циклического
кода. Причем, в данном случае, разрешенные
комбинации заведомо разделимы (т.е.
информационные и проверочные элементы
однозначно определены).

Вариант
второй.

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

2. Получить
   остальные разрешенные кодовые КК
   базиса, используя циклический сдвиг
   исходной. (В базисе должно быть k –
   строк). В данном случае код будет
   неразделимым.

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

Построение
кодера циклического кода

Разрешенная
комбинация циклического кода
образуется из комбинации простого
(исходного) кода путем умножения ее наи
прибавления остаткаR(x)
от деления
на
образующий полином.

1. Умножение
   полинома на одночлен
   —
   эквивалентно добавлению к двоичной
   последовательности соответствующейG(x)
   , r — нулей справа. Для реализации операции
   добавления нулей используется r-разрядный
   регистр задержки.

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

Построение
формирователя остатка циклического
кода

Структура
устройства осуществляющего деление на
полином полностью определяется видом
этого полинома. Существуют правила
позволяющие провести построение
однозначно.

Сформулируем
правила
построения ФПГ.

1. Число
   ячеек памяти равно степени образующего
   полинома r.

2. Число
   сумматоров на единицу меньше веса
   кодирующей комбинации образующего
   полинома.

3. Место
   установки сумматоров определяется
   видом образующего полинома.

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

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

Структурная
схема кодера циклического кода

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

Работа
схемы для
кодера (n,
k)

1.
На первом этапе К₁–
замкнут К₂
– разомкнут.
Идет одновременное заполнение регистров
задержки и сдвига информационными
элементами (старший вперед!) и через k-1
тактов
старший разряд в последней
ячейке
(под номером k-1)

2.
Во время k-го
такта К₂ –
замыкается, а К₁
– размыкается с этого момента в ФПГ
формируется остаток. Одновременно из
РЗ на выход выталкивается задержание
информационные разряды.

За
k
тактов (с k
по n
включительно) в линию уйдут все k
-информационных элемента. К этому времени
в ФПГ сформируется остаток

3.
К₂
– размыкается, К₁
– замыкается, и в след за информационными
в линию уйдут элементы проверочной
группы.

4.
Одновременно идет заполнение регистров
новой комбинацией.

Определение
ошибочного разряда в ЦК

Пусть
А(х)
— многочлен соответствующий переданной
кодовой комбинации. Н(х)
— многочлен соответствующей принятой
кодовой комбинацией.

Тогда
сложение данных многочленов по модулю
два даст многочлен ошибки.

E(x)=A(x)H(x)

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

Остаток
– полученный от деления принятого
многочлена H(x)
на производящей P_r(x)
равен остатку, полученному при делении
соответствующего многочлена ошибок
E(x)
на P_r(x)

При
этом ошибке в каждом разряде будет
соответствовать свой остаток R(x)
(он же синдром), а значит, получив синдром
можно однозначно определить место
ошибочного разряда.

Алгоритм
определения ошибки

Пусть
имеем n-элементные комбинации (n = k + r)
тогда:

1.
Получаем остаток от деления Е(х)
соответствующего ошибке в старшем
разряде, на образующей поленом P_r(x)

2.
Делим полученный полином Н(х)
на P_r(x)
и получаем текущий остаток R(x).

3.
Сравниваем R₀(x)
и R(x).

—
если они равны, то ошибка произошла в
старшем разряде.

—
если «нет», то увеличиваем степень
принятого полинома на Х и снова проводим
деления

4.
Опять сравниваем полученный остаток с
R₀(x)

—
если они равны, то ошибки во втором
разряде.

—
если нет, то умножаем Н(х)х²
и повторяем эти операции до тех пор,
пока R(X) не будет равен R₀(x).

Ошибка
будет в разряде соответствующем числу
на которое повышена степень Н(х) плюс
один.

Выбор
образующего полинома

В
теории циклических кодов показано, что
образующий полином представляет собой
произведение так называемых минимальных
многочленов
m_i(x),
являющихся простыми сомножителями (то
есть делящимся без остатка лишь на себя
и на 1) бинома xⁿ+
1:

P(x)=m₁(x)*
m₃(x)…m_j(x),
(7.2)

где
j = d₀
– 2
=( 2t_u.ош+1)
– 2 = 2 t_и.ош
– 1.

Существуют
специальные таблицы минимальных
многочленов, одна из которых приведена
ниже. Кроме образующего полинома
необходимо найти и количество проверочных
разрядов r.
Оно определяется из следующего свойства
циклических кодов:
для любых значений l
и t_и.ош
существует циклический код длины n
=2^l
– 1, исправляющий
все ошибки кратности t_и.ош
и менее, и содержащий не более
проверочных элементов.

Так
как
,
то
откуда
.

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

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

Таблица
7.1 — Выбор образующего полинома

Определяя
образующий полином, нужно из столбца
для соответствующего соотношения
выписать все многочлены, начиная с
верхней строки до нижней с номером
j=2t_и.ош–1
включительно. После этого следует
перемножить выбранные минимальные
многочлены в соответствии с (7.2).

Контрольные
вопросы по теме:

1. Назовите
   основные свойства циклических кодов.

2. Запишите
   полином в двоичном виде x⁶+x⁵+x²+x+1.

3. Запишите
   полином, соответствующий двоичной
   записи 100111.

4. Получите
   остаток от деления полинома
   х⁷+x⁶+x5+x⁴+x²+x+1
   на x²+x+1.

5. Как
   получают разрешенные комбинации при
   циклическом кодировании.

6. Нарисуйте
   кодер для циклического кода, порождаемого
   полиномом x⁵+x+1.
   Поясните принцип работы кодера.

7. По
   какому признаку обнаруживают ошибку
   в принятой кодовой комбинации.

8. Каков
   алгоритм определения ошибочного разряда
   в комбинации циклического кода.

9. Нарисуйте
   структурную схему декодера, обеспечивающего
   обнаружение ошибок для кода (7,4) при
   производящем полиноме x³+x+1.
   Поясните принцип его работы.

10. Нарисуйте
    структурную схему декодера, обеспечивающего
    исправление однократной ошибки для
    кода (7,4) при производящем полиноме
    x³+x+1.
    Поясните принцип его работы.

11. Как
    выбирается образующий (производящий)
    полином.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Введение

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

Нередко у людей уходит немало времени и масса нервов на поиски какой-нибудь
лишней скобки. Однако есть способ быстрого обнаружения ошибок, который основан
на использовании комментирования. Об этом методе я и расскажу в данной статье.

Концепция

Написать достаточно большой код без единой ошибки – весьма приятно. Но, к
сожалению, так выходит не всегда. Есть даже шутка, что ни одна программа не
была написана без единой ошибки. Я не рассматриваю здесь ошибки, которые
приводят к неверному исполнению кода. Здесь пойдёт речь об ошибках, из-за
которых становится невозможной компиляция.

Весьма распространённые ошибки – вставка лишней скобки в сложном условии,
нехватка скобки, не выставление двоеточия, запятой (при объявлении переменных)
и т.д. Часто при компиляции мы можем сразу увидеть, в какой строке допущена
подобная ошибка. Но бывают и случаи, когда найти такую ошибку не так просто. Ни
компилятор, ни зоркий глаз нам не могут помочь сходу найти ошибку. В
таких случаях, как правило, начинающие (и не очень) программисты начинают
«обходить» весь код, пытаясь визуально определить ошибку. И снова, и
снова, пока нервы не иссякнут, и не будет сказано «проще заново написать!».

Однако MQL, как и
другие языки программирования, предлагает потрясающий инструмент –
комментирование. Используя его можно «убирать», «отключать»
какие-то участки кода. Обычно комментирование используют именно для вставки
каких-то комментариев, или же отключения неиспользуемых участков кода. Комментирование
можно также успешно применять и при поиске ошибок.

Алгоритм поиска ошибок

Поиск ошибок обычно сводится к определению участка кода, где допущена
ошибка, а затем, в этом участке, визуально находится ошибка. Думаю, вряд ли кто-то
будет сомневаться в том, что исследовать «на глаз» 5-10 строчек кода
проще и быстрей, чем 100-500.

При использовании комментирования задача предельно проста. Сначала
нужно закомментировать различные участки кода (иногда чуть ли не весь код), тем
самым «отключив» его. Затем, по очереди комментирование снимается с
этих участков кода. После очередного снятия комментирования совершается
попытка компиляции. Если компиляция прошла успешно – ошибка не в этом участке
кода. Затем открывается следующий участок кода и т.д. Когда находится проблемный
участок кода, визуально ищется ошибка, затем устраняется. Опять происходит попытка
компиляции. Если всё прошло успешно, — ошибка устранена.

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

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

Пример

Приведу пример практического поиска ошибки в коде. Допустим, у нас есть некоторый код:

#property copyright ""
#property link      ""
 
extern int Level1=6;
extern int Level2=2;
 
extern double Lots=0.1;
extern int TP=7;
extern int SL=5000;
extern int Profit_stop=10;
 
int start()
  {


   int pos_sell=0;
 for (int i_op_sell=OrdersTotal()-1; i_op_sell>=0; i_op_sell--) 
 { 
  if (!OrderSelect(i_op_sell,SELECT_BY_POS,MODE_TRADES)) break; 
  if (Symbol()==OrderSymbol()&&(OrderType()==OP_SELLSTOP||OrderType()==OP_SELL)&&(OrderComment()=="sar_ao"))
  {
   pos_sell=1;  break;   
  } 
 }
    
   int pos_buy=0;
 for (int i_op_buy=OrdersTotal()-1; i_op_buy>=0; i_op_buy--) 
 { 
  if (!OrderSelect(i_op_buy,SELECT_BY_POS,MODE_TRADES)) break; 
  if (Symbol()==OrderSymbol()&&(OrderType()==OP_BUYSTOP||OrderType()==OP_BUY)&&(OrderComment()=="sar_ao"))
  {
   pos_buy=1;  break;   
  } 
 }
     


 


  double stop_open; 
  for (int ia=OrdersTotal()-1; ia>=0; ia--) 
  { 
   if (!OrderSelect(ia,SELECT_BY_POS,MODE_TRADES)) break; 
   if ((OrderType()==OP_BUY)&&(Symbol()==OrderSymbol())&&(OrderComment()=="sar_ao"))
   { 
    stop_open=OrderOpenPrice(); 
    if (NormalizeDouble(Bid,Digits)-stop_open<=Profit_stop*Point) continue; 
    OrderModify(OrderTicket(),OrderOpenPrice(),OrderOpenPrice()+1*Point,OrderTakeProfit(),OrderExpiration(),CLR_NONE);  
   } 
 if ((OrderType()==OP_SELL)&&(Symbol()==OrderSymbol())&&(OrderComment()=="sar_ao"))
   { 
    stop_open=OrderOpenPrice(); 
    if (stop_open-NormalizeDouble(Ask,Digits)<=Profit_stop*Point) continue; 
    OrderModify(OrderTicket(),OrderOpenPrice(),OrderOpenPrice()-1*Point,OrderTakeProfit(),OrderExpiration(),CLR_NONE);       
   } 
  }   


   int i;   
   bool trend_UP=true,trend_DOWN=true;   

if(!pos_buy)
 {  
  for(i=Level1; i>=0; i--)
   {
   
    if(Open[i]<iSAR(NULL,0,0.02,0.1,i))
    {
     trend_UP=false; break;
    }
    
   }
 
   for(i=Level2*2; i>=0; i--)
   {    
   
    if(i>Level2)
    {
     if(iAO(NULL, 0, i+1)<=iAO(NULL, 0, i))    
     { 
      trend_UP=false; break;
     }
    }
    
    if(i<Level2)
    {
     if(iAO(NULL, 0, i+1)>=iAO(NULL, 0, i))   
     {  
      trend_UP=false; break;
     }
    }          
   
   } 
 }
 else
 {
  trend_UP=false; 
 }

if(!pos_sell)
 { 
   for(i=Level1; i>=0; i--)
  {
   {
    if(Open[i]>iSAR(NULL,0,0.02,0.1,i))
    {
     trend_DOWN=false; break;
    }
    
   }
 
   for(i=Level2*2; i>=0; i--)
   { 
          
    if(i>Level2)
    {
     if(iAO(NULL, 0, i+1)>=iAO(NULL, 0, i))   
     {  
      trend_DOWN=false; break;
     }   
    }
    
    if(i<Level2)
    {
     if(iAO(NULL, 0, i+1)<=iAO(NULL, 0, i))    
     { 
      trend_DOWN=false; break;
     } 
    } 
       
   }
   
 }
  else
 {
  trend_DOWN=false; 
 }  
 
 
  if(Open[0]>iSAR(NULL,0,0.02,0.2,0))
  {
    ObjectDelete("sell"); 
  }
  
  if(Open[0]<iSAR(NULL,0,0.02,0.2,0))
  {
    ObjectDelete("buy"); 
  } 
   
double MA_1;
MA_1=iStochastic(NULL,0,5,3,3,MODE_SMA,0,MODE_SIGNAL,0);  
   if(trend_UP && MA_1<50 && Open[1]<Close[1] && !pos_buy && ObjectFind("buy") != 0)
   {   
     OrderSend(Symbol(),OP_BUY, Lots,Ask,2,Ask-SL*Point,Ask+TP*Point,"sar_ao",0,0,Blue); 
      
     ObjectCreate("buy", OBJ_ARROW, 0, Time[0], Bid);
     ObjectSet("buy", OBJPROP_STYLE, STYLE_DOT);
     ObjectSet("buy", OBJPROP_ARROWCODE, SYMBOL_ARROWUP);
     ObjectSet("buy", OBJPROP_COLOR, LightSeaGreen);
   }
   
   if(trend_DOWN && MA_1>50 && Open[1]>Close[1] && !pos_sell && ObjectFind("sell") != 0) 
   {   
      OrderSend(Symbol(),OP_SELL, Lots,Bid,2,Bid+SL*Point,Bid-TP*Point,"sar_ao",0,0,Red);   
      
      ObjectCreate("sell", OBJ_ARROW, 0, Time[0], Bid);
      ObjectSet("sell", OBJPROP_STYLE, STYLE_DOT);
      ObjectSet("sell", OBJPROP_ARROWCODE, SYMBOL_ARROWDOWN);
      ObjectSet("sell", OBJPROP_COLOR, Red);  
   }
   
 


   return(0);
  }

При попытке его компиляции мы видим сообщение об ошибке:

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

#property copyright ""
#property link      ""
 
extern int Level1=6;
extern int Level2=2;
 
extern double Lots=0.1;
extern int TP=7;
extern int SL=5000;
extern int Profit_stop=10;
 
int start()
  {
  
 

 
 


 

 
  
double MA_1;
MA_1=iStochastic(NULL,0,5,3,3,MODE_SMA,0,MODE_SIGNAL,0); 
 

  
  


   return(0);
  }

Легко можно убедиться, что такой код компилируется без проблем. Значит, участок кода, где допущена ошибка «скрыт». По очереди открываем участки кода /* … */, пытаемся откомпилировать.

Компиляция будет происходить благополучно, пока мы не дойдём до участка кода:

 
 
if(!pos_sell)
 { 
   for(i=Level1; i>=0; i--)
  {
   {
    if(Open[i]>iSAR(NULL,0,0.02,0.1,i))
    {
     trend_DOWN=false; break;
    }
    
   }
 
   for(i=Level2*2; i>=0; i--)
   { 
          
    if(i>Level2)
    {
     if(iAO(NULL, 0, i+1)>=iAO(NULL, 0, i))   
     {  
      trend_DOWN=false; break;
     }   
    }
    
    if(i<Level2)
    {
     if(iAO(NULL, 0, i+1)<=iAO(NULL, 0, i))    
     { 
      trend_DOWN=false; break;
     } 
    } 
       
   }
   
 }
  else
 {
  trend_DOWN=false; 
 }

Следовательно, ошибка именно в этой логической конструкции. При детальном «осмотре» данного участка кода, можно увидеть, что поставлена лишняя фигурная скобка в данной конструкции:

   for(i=Level1; i>=0; i--)
  {
   {
    if(Open[i]>iSAR(NULL,0,0.02,0.1,i))
    {
     trend_DOWN=false; break;
    }
    
   }

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

Убрав оставшиеся комментарии, мы убедимся в том, что других ошибок в коде нет. Значит, цель достигнута — ошибка в коде была найдена достаточно оперативно.

Заключение

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

5.1. Понятие о корректирующих кодах

5.2. Циклические коды

5.3. Выбор образующего полинома циклического кода

От СПДС обычно требуется не только передавать сообщения с заданной скоростью передачи информации, но и обеспечивать при этом требуемую достоверность.

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

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

В общей структурной схеме СПДС задачу защиты от ошибок выполняет кодер и декодер канала, который иногда называют УЗО.

5.1. Понятие о корректирующих кодах

Пусть имеется источник сообщений с объемом алфавита К.

Поставим в соответствие каждому сообщению n — элементную двоичную последовательность. Всего последовательностей из n — элементов может быть .

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

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

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

Появление ошибки в кодовой комбинации будет обнаружено, если передаваемая разрешенная комбинация перейдет в одну из запрещенных.

Расстояние Хемминга – характеризует степень различия кодовых комбинаций и определяется числом несовпадающих в них разрядов.

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d₀.

Минимальное расстояние d₀ — называется кодовым расстоянием

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

У простого кода d₀=1 – он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В общем случае справедливы следующие соотношения

– для обнаруживающей способности

– для исправляющей способности

Линейные коды

Двоичный блочный код является линейным если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Линейные коды также называют групповыми.

Введем понятия группы.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

1. Замкнутость g_ig _j= g_k G в результате операции с двумя элементами группы получается третий, так же принадлежащий этой группе.
2. Ассоциативность (сочетательность) (g_ig_j) g_k = g_i (g_j g_k)
3. Наличие нейтрального элемента g_j e = g_j
4. Наличие обратного элемента. g_i (g_i)^-1= e

Если выполняется условие g_i g_j = g_j g_i, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

Поэтому используя свойство замкнутости относительно операции 2, множество всех элементов можно задать не перечислением всех элементов, а производящей матрицей.

Все остальные элементы, кроме 0, могут быть получены путем сложения по модулю 2 строк производящей матрицы в различных сочетаниях.

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

5.2. Циклические коды

Широкое распространение на практике получил класс линейных кодов, которые называются циклическими. Данное название происходит от основного свойства этих кодов:

если некоторая кодовая комбинация принадлежит циклическому коду, то комбинация полученная циклической перестановкой исходной комбинации (циклическим сдвигом), также принадлежит данному коду.

.

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

Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином.

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

Представление кодовой комбинации в виде многочлена

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов).

В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементную кодовую комбинацию можно описать полиномом (n-1) степени, в виде

.

где ={0,1}, причем = 0 соответствуют нулевым элементам комбинации, а = 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций

Действия над многочленами

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

,

поскольку .

Следует отметить, что действия над коэффициентами полинома (сложение и умножение) производятся по модулю 2.

Рассмотрим операцию деления на следующем примере:

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

Отметим, что запись кодовой комбинации в виде многочлена, не всегда определяет длину кодовой комбинации. Например, при n = 5, многочлену соответствует кодовая комбинация 00011.

Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

Пусть задан полином , определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена .

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

• Умножаем многочлен исходной кодовой комбинации на

• Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на образующий полином

• Окончательно разрешенная кодовая комбинация циклического кода определится так

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Формирование базиса (производящей матрицы) циклического кода

Формирование базиса циклического кода возможно как минимум двумя путями.

Вариант первый.

1. Составить единичную матрицу для простого исходного кода.
2. Определить для каждой кодовой комбинации исходного кода группу проверочных элементов и дописать их в соответствующие строки матрицы.

Полученная матрица и будет базисом циклического кода. Причем, в данном случае, разрешенные комбинации заведомо разделимы (т.е. информационные и проверочные элементы однозначно определены).

Вариант второй.

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

• Получить остальные разрешенные кодовые КК базиса, используя циклический сдвиг исходной. (В базисе должно быть k – строк)

В данном случае код будет неразделимым.

Получив базис ЦК, можно получить все разрешенные комбинации, проводя сложение по модулю 2 кодовых комбинаций базиса в различных сочетаниях и плюс НУЛЕВАЯ.

Циклические коды достаточно просты в реализации, обладают высокой корректирующей способностью (способностью исправлять и обнаруживать ошибки) и поэтому рекомендованы МСЭ-Т для применения в аппаратуре ПД. Согласно рекомендации V.41 в системах ПД с ОС рекомендуется применять код с производящим полиномом

Построение кодера циклического кода

Рассмотрим код (9,5) образованный полиномом

.

Разрешенная комбинация циклического кода образуется из комбинации простого (исходного) кода путем умножения ее на и прибавления остатка R(x) от деления на образующий полином.

• Умножение полинома на одночлен

эквивалентно добавлению к двоичной последовательности соответствующей G(x) , r — нулей справа.

Пусть

тогда

Для реализации операции добавления нулей используется r-разрядный регистр задержки.

• Рассмотрим более подробно операцию деления:

Как видим из примера, процедура деления одного двоичного числа на другое сводится к последовательному сложению по mod2 делителя [10011] с соответствующими членами делимого [10101], затем с двоичным числом, полученным в результате первого сложения, далее с результатом второго сложения и т.д., пока число членов результирующего двоичного числа не станет меньше числа членов делителя.

Это двоичное число и будет остатком .

Построение формирователя остатка циклического кода

Структура устройства осуществляющего деление на полином полностью определяется видом этого полинома. Существуют правила позволяющие провести построение однозначно.

Сформулируем правила построения ФПГ.

1. Число ячеек памяти равно степени образующего полинома r.
2. Число сумматоров на единицу меньше веса кодирующей комбинации образующего полинома.
3. Место установки сумматоров определяется видом образующего полинома.

Сумматоры ставят после каждой ячейки памяти, (начиная с нулевой) для которой существует НЕнулевой член полинома. Не ставят после ячейки для которой в полиноме нет соответствующего члена и после ячейки старшего разряда.

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

Структурная схема кодера циклического кода (9,5)

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

Рассмотрим работу этой схемы

1. На первом этапе К₁– замкнут К₂ – разомкнут. Идет одновременное заполнение регистров задержки и сдвига информ. элементами (старший вперед!) и через 4 такта старший разряд в ячейке №4

2. Во время пятого такта К₂ – замыкается а К₁ – размыкается с этого момента в ФПГ формируется остаток. Одновременно из РЗ на выход выталкивается задержание информационные разряды.

За 5 тактов (с 5 по 9 включительно) в линию уйдут все 5-информационных элемента. К этому времени в ФПГ сформируется остаток

3. К₂ – размыкается, К₁ – замыкается и в след за информационными в линию уйдут элементы проверочной группы.

4. Одновременно идет заполнение регистров новой комбинацией.

Второй вариант построения кодера ЦК

Рассмотренный выше кодер очень наглядно отражает процесс деления двоичных чисел. Однако можно построить кодер содержащий меньшее число элементов т.е. более экономичный.

Устройство деления на производящий полином можно реализовать в следующем виде:

За пять тактов в ячейках будет сформирован такой же остаток от деления, что и в рассмотренном выше Формирователе проверочной группы. (ФПГ).

За эти же 5 тактов информационные разряды, выданные сразу на модулятор.

Далее в след за информационными уходят проверочные из ячеек устройств деления.

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

Окончательно структурная схема экономичного кодера выглядит так.

— На первом такте Кл.1 и Кл.3 замкнуты, информационные элементы проходят на выход кодера и одновременно формируются проверочные элементы.

— После того, как в линию уйдет пятый информационный элемент, в устройстве деления сформируются проверочные;

— на шестом такте ключи 1 и 3 размыкаются (разрываются обратная связь), а ключ 2 замыкается и в линию уходят проверочные разряды.

Ячейки при этом заполняются нулями и схема возвращается в исходное состояние.

Определение ошибочного разряда в ЦК

Пусть А(х)-многочлен соответствующий переданной кодовой комбинации.

Н(х)- многочлен соответствующей принятой кодовой комбинацией.

Тогда сложение данных многочленов по модулю два даст многочлен ошибки.

E(x)=A(x) H(x)

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

Остаток – полученный от деления принятого многочлена H(x) на производящей P_r(x) равен остатку полученному при делении соответствующего многочлена ошибок E(x) на P_r(x)

При этом ошибке в каждом разряде будет соответствовать свой остаток R(x) (он же синдром), а значит, получив синдром можно однозначно определить место ошибочного разряда.

Алгоритм определения ошибки

Пусть имеем n-элементные комбинации (n = k + r) тогда:

1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде [1000000000], на образующей поленом P_r(x)

2. Делим полученный полином Н(х) на P_r(x) и получаем текущий остаток R(x).

3. Сравниваем R₀(x) и R(x).

— Если они равны, то ошибка произошла в старшем разряде.

— Если «нет», то увеличиваем степень принятого полинома на Х и снова проводим деления

в) Опять сравниваем полученный остаток с R₀(x)

— Если они равны, то ошибки во втором разряде.

— Если нет, то умножаем Н(х)х² и повторяем эти операции до тех пор, пока R(X) не будет равен R₀(x).

Ошибка будет в разряде соответствующем числу на которое повышена степень Н(х) плюс один.

Например: то номер ошибочного разряда 3+1=4

Пример декодирования комбинации ЦК

Положим, получена комбинация H(х)=111011010

Проанализируем её в соответствии с вышеприведенным алгоритмом.

Реализуя алгоритм определения ошибок, определим остаток от деления вектора соответствующего ошибке в старшем разряде Х⁸ на производяший полином P(x)=X⁴+X+1

X⁸ X²+X+1

X⁸+X⁵+X⁴ x⁴+x+1

X⁵+X⁴

X⁵+X²+X

X⁴+X²+X

X⁴+X+1

X²+1=R₀(X)=0101

Разделим принятую комбинацию на образующий полином

Полученный на 9-м такте остаток, как видим, не равен R₀(X). Значит необходимо умножить принятую комбинацию на Х и повторить деление. Однако результаты деления с 5 по 9 такты включительно будут такими же, значит необходимо продолжить деление после девятого такта до тех пор, пока в остатке не будет R₀(Х). В нашем случае это произойдет на 10 такте, при повышении степени на 1. Значит ошибки во втором разряде.

Декодер циклического кода с исправлением ошибки

Если ошибка в первом разряде, то остаток R₀(X)=10101 появления после девятого такта в ячейках ФПГ.

Если во втором по старшинству то после 10^го;
в третьем по старшинству то после 11^го;
в четвертом по старшинству то после 12^го
в пятом по старшинству то после 13^го
в шестом по старшинству то после 14^го
в седьмом по старшинству то после 15^го
в восьмом по старшинству то после 16^го
в девятом по старшинству то после 17^го.

На 10 такте старший разряд покидает регистр задержки и проходит через сумматор по модулю 2.

Если и этому моменту остаток в ФПГ=R₀(X), то логическая 1 с выхода дешифратора поступит на второй вход сумматора и старший разряд инвертируется.

В нашем случае инвертируется второй разряд на 11 такте.

5.3. Выбор образующего полинома

Рассмотрим вопрос выбора образующего полинома, который определяет корректирующие свойства циклического кода. В теории циклических кодов показано, что образующий полином представляет собой произведение так называемых минимальных многочленов m_i(x), являющихся простыми сомножителями (то есть делящимся без остатка лишь на себя и на 1) бинома xⁿ+ 1:

P(x)=m₁(x)* m₃(x)…m_j(x), (*)

где j = d₀ – 2 =( 2t_u.ош+1) – 2 = 2 t_и.ош – 1.

Существуют специальные таблицы минимальных многочленов, одна из которых приведена ниже. Кроме образующего полинома необходимо найти и количество проверочных разрядов r. Оно определяется из следующего свойства циклических кодов:

для любых значений l и t_и.ош существует циклический код длины n =2^l – 1, исправляющий все ошибки кратности t_и.ош и менее, и содержащий не более проверочных элементов.

Так как , то откуда . (**)

Очевидно, что для уменьшения времени передачи кодовых комбинаций, r следует выбирать как можно меньше. Пусть, например, длина кодовых комбинаций n = 7, кратность исправляемых ошибок t_и.ош =1. Из (**) получим r = 1 ^. log₂ ( 7+1 )=3.

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

Таблица минимальных многочленов

Определяя образующий полином, нужно из столбца для соответствующего соотношения выписать все многочлены, начиная с верхней строки до нижней с номером j=2t_и.ош–1 включительно. После этого следует перемножить выбранные минимальные многочлены в соответствии с (*). В частности, если r=3, t_и.ош=1, j=2*1-1=1, образующий полином будет представлять собой единственный минимальный многочлен P(x)= m₁(x) = x³+x+1 (первая строка, второй столбец таблицы ). Соответственно образующее число равно 1011.

Контрольные вопросы по теме:

1. Что такое разрешенные и запрещенные кодовые комбинации.
2. Что называется расстоянием Хемминга.
3. Дайте понятие кодового расстояния и как его определить.
4. Как связано кодовое расстояние с исправляющей и обнаруживающей способностью кода.
5. Какой код называется линейным.
6. Какое множество называется группой.
7. Назовите основные свойства циклических кодов.
8. Запишите полином в двоичном виде.
9. Запишите полином, соответствующий двоичной записи 100111.
10. Получите остаток от деления полинома на .
11. Как получают разрешенные комбинации при циклическом кодировании.
12. Нарисуйте кодер для циклического кода, порождаемого полиномом . Поясните принцип работы кодера.
13. По какому признаку обнаруживают ошибку в принятой кодовой комбинации.
14. Каков алгоритм определения ошибочного разряда в комбинации циклического кода.
15. Нарисуйте структурную схему декодера, обеспечивающего обнаружение ошибок для кода (7,4) при производящем полиноме . Поясните принцип его работы.
16. Нарисуйте структурную схему декодера, обеспечивающего исправление однократной ошибки для кода (7,4) при производящем полиноме . Поясните принцип его работы.
17. Как выбирается образующий (производящий) полином?

Каналы передачи данных ненадежны (шумы, наводки и т.д.), да и само оборудование обработки информации работает со сбоями. По этой причине важную роль приобретают механизмы детектирования ошибок. Ведь если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным. Можно, конечно, передать код дважды и сравнить, но это уже двойная избыточность.

Простейшим способом обнаружения ошибок является контроль по четности. Обычно контролируется передача блока данных ( М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).

При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой – минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое расстояние Хэмминга.

Пусть А и Б — две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.

Можно показать, что для детектирования ошибок в n битах схема кодирования требует применения кодовых слов с расстоянием Хэмминга не менее N + 1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с расстоянием Хэмминга между кодами не менее 2N + 1. Таким образом, конструируя код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями большее, чем оно может возникнуть из-за ошибок.

Широко распространены коды с одиночным битом четности. В этих кодах к каждым М бит добавляется 1 бит, значение которого определяется четностью (или нечетностью) суммы этих М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем четности будут 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится.

Предположим, что частота ошибок ( BER – Bit Error Rate) равна р = 10^-4. В этом случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p)⁸ = 7,9 х 10^-4. Добавление бита четности позволяет детектировать любую ошибку в одном из переданных битах. Здесь вероятность ошибки в одном из 9 битов равна 9p(1 – p)⁸. Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p)⁹ – 9p(1 – p)⁸ = 3,6 x 10^-7. Таким образом, добавление бита четности уменьшает вероятность необнаруженной ошибки почти в 1000 раз. Использование одного бита четности типично для асинхронного метода передачи. В синхронных каналах чаще используется вычисление и передача битов четности как
для строк, так и для столбцов передаваемого массива данных. Такая схема позволяет не только регистрировать, но и исправлять ошибки в одном из битов переданного блока.

Контроль по четности достаточно эффективен для выявления одиночных и множественных ошибок в условиях, когда они являются независимыми. При возникновении ошибок в кластерах бит метод контроля четности неэффективен, и тогда предпочтительнее метод вычисления циклических сумм ( CRC — Cyclic Redundancy Check). В этом методе передаваемый кадр делится на специально подобранный образующий полином. Дополнение остатка от деления и является контрольной суммой.

В Ethernet вычисление CRC производится аппаратно. На
рис.
4.1 показан пример реализации аппаратного расчета CRC для образующего полинома R(x) = 1 + x² + x³ + x⁵ + x⁷. В этой схеме входной код приходит слева.

Эффективность CRC для обнаружения ошибок на многие порядки выше простого контроля четности. В настоящее время стандартизовано несколько типов образующих полиномов. Для оценочных целей можно считать, что вероятность невыявления ошибки в случае использования CRC, если ошибка на самом деле имеет место, равна (1/2)^r, где r — степень образующего полинома.

4.1. Алгоритмы коррекции ошибок

Исправлять ошибки труднее, чем их детектировать или предотвращать. Процедура коррекции ошибок предполагает два совмещеных процесса: обнаружение ошибки и определение места (идентификации сообщения и позиции в сообщении). После решения этих двух задач исправление тривиально — надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется метод детектирования ошибок и повторной пересылки фрагмента, содержащего дефект. Для спутниковых каналов с типичными для них большими задержками системы коррекции ошибок становятся привлекательными. Здесь используют коды Хэмминга или коды свертки.

Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7), используемыми при передаче 7-битных ASCII-кодов. Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7 + 4 = 11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью. Например, пусть возможны следующие правильные коды (все они, кроме первого и последнего, отстоят друг от друга на расстояние Хэмминга 4):

00000000

11110000

00001111

11111111

При получении кода 00000111 нетрудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее расстояние Хэмминга.

Рассмотрим пример передачи кода буквы s = 0x073 = 1110011 с использованием кода Хэмминга (11,7). Таблица 4.2.

Символами * помечены четыре позиции, где должны размещаться контрольные биты. Эти позиции определяются целой степенью 2 (1, 2, 4, 8 и т.д.). Контрольная сумма формируется путем выполнения операции XoR (исключающее ИЛИ) над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3. Вычислим контрольную сумму:

11=	1011
10=	1010
09=	1001
05=	0101
03=	0011
	1110

Таким образом, приемник получит код

Просуммируем снова коды позиций ненулевых битов и получим нуль;

11=	1011
10=	1010
09=	1001
08=	1000
05=	0101
04=	0100
03=	0011
02=	0010
	0000

Ну а теперь рассмотрим два случая ошибок в одном из битов посылки, например в бите 7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых битов еще раз:

Таблица
4.3.

11= 1011 10= 1010 09= 1001 08= 1000 07= 0111 05= 0101 04= 0100 03= 0011 02= 0010 0111

11= 1011 10= 1010 09= 1001 08= 1000 04= 0100 03= 0011 02= 0010 0001

В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме. Понятно, что если ошибка произойдет при передаче более чем одного бита, код Хэмминга при данной избыточности окажется бесполезен.

В общем случае код имеет N = M + C бит и предполагается, что не более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М = 4, а N = 7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Теперь попытаемся вычислить значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:

С1 = М1 + М2 + М4
С2 = М1 + М3 + М4
С3 = М2 + М3 + М4

Для определения того, доставлено ли сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):

С11 = С1 + М4 + М2 + М1
С12 = С2 + М4 + М3 + М1
С13 = С3 + М4 + М3 + М2

Результат вычисления интерпретируется следующим образом:

Описанная схема легко переносится на любое число n и М.

Число возможных кодовых комбинаций М помехоустойчивого кода делится на n классов, где N — число разрешенных кодов. Разделение на классы осуществляется так, чтобы в каждый класс вошел один разрешенный код и ближайшие к нему (по расстоянию Хэмминга ) запрещенные коды. В процессе приема данных определяется, к какому классу принадлежит пришедший код. Если код принят с ошибкой, он заменяется ближайшим разрешенным кодом. При этом предполагается, что кратность ошибки не более q_m.

В теории кодирования существуют следующие оценки максимального числа N n -разрядных кодов с расстоянием D.

В случае кода Хэмминга первые k разрядов используются в качестве информационных, причем

K = n – log(n + 1), откуда следует (логарифм по основанию 2), что k может принимать значения 0, 1, 4, 11, 26, 57 и т.д., это и определяет соответствующие коды Хэмминга (3,1); (7,4); (15,11); (31,26); (63,57) и т.д.

Обобщением кодов Хэмминга являются циклические коды BCH (Bose-Chadhuri-hocquenghem). Эти коды имеют широкий выбор длин и возможностей исправления ошибок.

Одной из старейших схем коррекции ошибок является двух-и трехмерная позиционная схема (
рис.
4.2). Для каждого байта вычисляется бит четности (бит <Ч>, направление Х). Для каждого столбца также вычисляется бит четности (направление Y. Производится вычисление битов четности для комбинаций битов с координатами (X,Y) (направление Z, слои с 1 до N ). Если при транспортировке будет искажен один бит, он может быть найден и исправлен по неверным битам четности X и Y. Если же произошло две ошибки в одной из плоскостей, битов четности данной плоскости недостаточно. Здесь поможет плоскость битов четности N+1.
Таким образом, на 512 передаваемых байтов данных пересылается около 200 бит четности.