2.2.3.3.  Коды, исправляющие ошибки (корректирующие коды)

В качестве корректирующего может быть использован цикличе­ский код, если число контрольных символов в нем удовлетворяет ус­ловию (2-40). Следует отметить, что при двоичном кодировании для исправления ошибки достаточно указать место искаженной пози­ции. Коррекция ошибки производится инвертированием символа, стоящего на указанной позиции.

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

Корректирующий код Хэмминга. Рассматриваемый код предназначен для обнаружения и исправления одиночной ошибки. При построении такого кода каждый из k проверочных символов определяется как результат суммирования по модулю 2 определенного сочетания инфор­мационных символов. В результате этого сумма проверяемых инфор­мационных и контрольного символов всегда является четной. При при­еме комбинаций такого кода принятые комбинации подвергаются аналогичным проверкам, охватывающим информационные и контрольный символы.

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

волы входят в проверочные суммы в раз­личных сочетаниях, то число нечетных контрольных сумм может быть различным (от 0 до k).

В коде Хэмминга проверки на четность орга­низованы таким образом, что получается число, указывающее номер позиции, на которой произошло искажение. Для этого результаты k проверок, представляющие собой контрольные суммы по моду­лю 2 и являющиеся, таким образом, единицами или нулями, записы­ваются в виде контрольного числа Ek Ek-1 … Е2 Е1. Это число должно указывать номер искаженного символа.

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

Е1 = х1 Å  х3  Å  х5  Å  х7  Å … .                                              (2-53)

Единица во втором разряде контрольного числа свидетельствует о наличии ошибки на одной из позиций, двоичные номера которых имеют единицу во втором разряде. Такими позициями являются 2, 3, 6, 7, 10, 11 и т.д. Символы с перечисленными номерами войдут во вторую проверку:

Е2 = х2 Å  х3 Å  х6 Å  х7 Å  х10 Å  х11 Å                                    (2-54)

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

Е3 = х4 Å  х5 Å  х6 Å  х7 Å  х12 Å х13 Å  х14 Å  х15 Å ….

Для последней проверки с номером k легко получить, что

где .

В таблице 2.11 крестиками отмечены номера позиций, вклю­чаемые в последовательные проверки для k = 4,  п = 15.

Таблица 2.11

Номер

проверки

Номер позиции

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

+

+

+

+

+

+

+

+

2

+

+

+

+

+

+

th=30 valign=top style='width:22.25pt;border-top:none;border-left: none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt; padding:0cm 5.4pt 0cm 5.4pt'>

+

+

3

+

+

+

+

+

+

+

+

4

+

+

+

+

+

+

+

+

Поскольку контрольные символы должны обеспечивать четность проверочных сумм, они включаются лишь в одну проверку. Только в одну проверку входят символы, двоичные номера позиций которых являются целыми степенями двойки, т.е. 1, 2, 4, 8, 16 и т.д. На этих позициях и размещаются контрольные символы. Значения контроль­ных символов находятся как результат суммирования всех символов, входящих в данную проверку. Из выражений (2-53) – (2-55) можно опре­делить значения контрольных символов: