Построение корректирующего кода

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

Избыточностью данных I называется отношение количества контрольных бит к числу передаваемых данных:

Например, если при передаче к = 4 информационных бит к ним добавляются г = = 4 корректирующих бита, то избыточность данных согласно (5.1) составит / = 4/8 = = 0,5, т. е. 50%.

Кодовые слова принято обозначать (гг, к) — преобразование к бит информационных данных в n-битовое кодовое слово; данное обозначение характеризует корректирующий код. Так, для примера выше корректирующий код обозначается (8,4).

Расстоянием между кодовыми комбинациями d в смысле Хемминга (кодовым расстоянием) называется количество бит, на которые различаются два кодовых слова. Так, для слов 10 110 001 и 10 001 001 это расстояние равно.

Для нахождения d кодовые слова складывают по модулю 2 (см. параграф 4.2) и подсчитывают количество единиц результата. Смысл величины d следующий: для преобразования одного кодового слова, находящегося на расстоянии d от другого слова, требуется исправить ровно d битовых ошибок.

Битовое слово имеет п разрядов, следовательно, всего существует N_eo3M = 2^й возможных кодовых комбинаций. Из них разрешенными являются всего М_]юзр = 2^к, так как требуется передать только к бит данных. Если приемник получает недопустимое слово, то принимается решение о наличии ошибки.

Способность кода находить и исправлять ошибки зависит от минимального кодового расстояния (расстояния всего кода по Хеммингу), получаемое следующим образом:

• 1. Строится список всех кодовых слов.
• 2. Определяется пара слов, для которых кодовое расстояние минимально: d — d_mj_n.

Пример 5.1. Рассмотрим так называемый безызбыточный код, для которого N_eo3M = — Хразр, т. е. все возможные кодовые слова являются разрешенными. Для п = 5 кодовая последовательность 1 отличается от другой разрешенной последовательности 0 только значением одного бита. Таким образом, для рассматриваемого кода dm_in = 1.

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

Обнаружение ошибок возможно только в том случае, когда количество разрешенных комбинаций меньше количества возможных, т. е. когда выполняется неравенство Д^Гразр < N_eo3M. Кодовые n-битовые слова, которые не являются разрешенными, называются запрещенными, их количество N_3anp = N_e03M — N_]xi:ip. Ошибка может быть распознана приемником, если передаваемая разрешенная комбинация перейдет в запрещенную. В качестве разрешенных комбинаций выбирают такие, различия между которыми максимальны.

Имеют место следующие утверждения:

• 1. Обнаружение битовых ошибок возможно только такими кодами, для разрешенных кодовых комбинаций которых выполняется условие d_min ^ 2.
• 2. Исправление битовых ошибок возможно только такими кодами, для разрешенных кодовых комбинаций которых выполняется условие d_min > 3.

Пример 5.2. Рассмотрим случай, когда для п = 5 выбраны следующие разрешенные комбинации: 0, 111, 11 001, 11 110. Минимальное кодовое расстояние для этих комбинаций d_mi_n = 3, так как.

Таким образом, с помощью данного кода возможно не только обнаружение, но и исправление битовых ошибок. ?

В общем случае величина c/_min и кратность только обнаруживаемых ошибок t₀ связаны связаны соотношением.

Значение d_miri и кратность исправляемых ошибок t_u в общем случае связаны выражением.

Исправление ошибок возможно только тогда, когда передаваемая источником разрешенная комбинация принимается в виде запрещенной. Одним из способов определения, какая кодовая комбинация была передана, является сравнение запрещенной комбинации со всем множеством разрешенных. При этом принимается решение, что была передана комбинация, которая больше всего похожа на полученную (та, с которой полученная комбинация имеет наименьшее расстояние Хемминга). Например, если в условиях примера 5.2 была получена последовательность бит 100, то принимается решение, что была передана кодовая комбинация 0.

Таким образом, для построения корректирующего кода следует из N_eo3M = 2″ кодовых комбинаций выбрать путем перебора Дрозр разрешенных, имеющих заданное кодовое расстояние d_min на основе соотношений (5.2) и (5.3). При небольших значениях п такой перебор не представляет затруднений, однако с ростом п эта задача может стать трудновыполнимой даже с помощью современных ЭВМ. В этом случае применяют специальные алгоритмы построения множества разрешенных кодовых комбинаций, не требующих перебора.