1 Цель работы

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

2 Основные теоретические положения

2.1 Избыточное кодирование. Общие понятия и определения

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

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

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

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

Общее число кодовых комбинаций в коде длиной n при m=2 (двоичный код):

N = 2ⁿ. (31)

Из них разрешенных:

N_p = 2^k, (32)

а запрещенных:

N_з = (N – N_p) = 2ⁿ – 2^k = 2^r, (33)

где k – количество информационных разрядов в кодовой комбинации;

r = n - k – количество проверочных разрядов.

Избыточность кода R – определяет долю проверочных разрядов внутри блока (кодовой комбинации).

r

R

n

= , (34)

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

Минимальное кодовое расстояние связано с кратностью обнаруживаемых ошибок следующим соотношением:

d_min  t₀ + 1, (35)

где d_min – минимальное кодовое расстояние;

t₀ – кратность обнаруживаемых ошибок.

Таким образом, для построения кода, обладающего требуемой обнаруживающей способностью t₀, необходимо внести в него такую избыточность, которая обеспечила бы минимальное кодовое расстояние не менее t₀+1. Для определения количества проверочных символов r, которые нужно добавить к безызбыточной кодовой комбинации, существует ряд верхних и нижних оценок: границы Хэмминга, Элайеса, Варшамова-Гильберта и др.

Граница Хэмминга:

(36)

Граница Варшамова-Гильберта:

(37)

С ⁱ_n =

n!

г

i! ( n - i )!

де C_nⁱ – число сочетаний из n по i.

В литературе существуют рассчитанные значения количества проверочных символов r, для двоичного алфавита при l≤k≤60 и 2≤d_min≤21, представленные в виде таблицы [3, таблица 15].