Корректирующие коды

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

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

Блочные коды характеризуются тем, что каждая кодовая комбинация состоит из двух частей (блоков), первая состоит из информационных символов, вторая – из контрольных. Особенностью непрерывных кодов является то, кодовая комбинация не разделяется на блоки, а контрольные символы размещаются по определенному правилу между информационными.

Для корректирующих кодов справедливо неравенство

N = K^m M,

где М– количество сообщений;N– количество кодовых комбинаций;К– основание кода;

m– длина кодовой комбинации:m = n + k;n– число информационных разрядов,k– число контрольных разрядов, обеспечивающих локализацию и исправление искаженных элементов кодовой комбинации.

Число контрольных разрядов, необходимых для обнаружения и исправления однократных ошибок, определим путем следующих рассуждений. При передаче любого из Мсообщений может быть искажен любой изmэлементов кодовой комбинации или сообщение будет передано верно. Следовательно, возможныm + 1исходов. Используяkконтрольных разрядов необходимо различить все эти исходы. С помощьюkразрядов можно закодировать 2kисходов. Значит, должно выполняться условие

Например, если М = 10, то в соответствии с равенствомM = Kⁿполучаем n  3,3 = 4. Чтобы иметь возможность обнаруживать ошибочные кодовые комбинации и исправлять их следует добавитьkконтрольных разрядов в соответствии с выражением:

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

При этом избыточность кода составит

.

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

,

где α– кратность обнаруживаемых ошибок,

β– кратность исправляемых ошибок,

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

Рассмотрим эту формулу на примере равномерного трехразрядного кода.

При α = 0,β = 0 d = 1. Этот результат соответствует равномерному оптимальному коду. Его кодовые комбинации:000, 001, 010, 100, 110, 101, 011, 111.

При этом избыточность кода равна .

При α = 1,β = 0 d = 2. Этот результат соответствует равномерному коду, обнаруживающему однократную ошибку. Его кодовые комбинации:001, 010, 101, 110.

При этом избыточность кода равна .

При α = 1,β = 1 d = 3. Этот результат соответствует равномерному оптимальному коду. Его кодовые комбинации:000, 111.

При этом избыточность кода равна .

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

В зависимости от требуемой разрядности кода записывается единичная матрица (nn)

С помощью этой матрицы можно записать все комбинации n-разрядного оптимального кода.

Чтобы образовать на основании этой матрицы код, корректирующий однократную ошибку, необходимо расширить ее до mразрядов, т. е.(nn) → (nm). Для этого справа приписывается матрица контрольных разрядов, содержащаяkстолбцов(m = n + k).

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

К матрице Апредъявляются следующие требования:

1. Поскольку будет синтезироваться избыточный равномерный систематический код, позволяющий обнаружить и скорректировать однократную ошибку, то расстояние между кодовыми комбинациями должно быть: d3. Поскольку единичная матрица расширилась наkразрядов, то каждая строка дополнительно приписываемой части матрицы должна иметь не менее чем(d - 1)единиц, поскольку уже одну единицу содержит каждая строка единичной матрицы.

2. Различие между строками в приписываемой матрице должно быть не менее чем в (d - 2)разрядах, т.к. различие в единичной матрице в двух строках уже есть.

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

Проверочная матрица строится следующим образом: к единичной матрице размером kkслева приписывается матрица изnстолбцов иkстрок(nk).При этом строка приписываемой матрицы является столбцом дополнительной матрицы из матрицыA.

К матрице Ппредъявляется следующее требование.

Сумма единиц по модулю 2любой строки проверочной матрицы должна быть четным числом (или во всех строках нечетная), т.к. сумма по модулю2равна нулю при четности. Это является условием обнаружения и локализации ошибки в любой кодовой комбинации. Локализация ошибки основана на индивидуальной кодовой комбинации (опознавателях), и эта кодовая комбинация представляется в видеf₀ f₁ f₂ … f_k-1(количество контрольных разрядов)

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

Согласно условию задачи количество отображенных чисел (сообщений) М = 10. Для представления этих чиселn = 4, k = 3. Составим производящую матрицу.

Выполняется условие: не менее (d-1)единиц. На основании этой матрицы можно построить16кодовых комбинаций с разрядностью. Составим10кодовых комбинаций, которые будут необходимы для индикации требующихся цифр. Пусть это будут следующие комбинации:

Первые четыре кодовые комбинации – это строки матрицы А. Последние 6 кодовых комбинаций являются суммами строк по модулю 2, соответственно: ,,,,,.

Строим проверочную матрицу

Проверочная матрица показывает, что k₀контролирует1,2,3разряды,k₁ – 0,2,3разряды,k₂ – 0,1,3разряды.

На основании проверочной матрицы можно составить уравнения кодов-опознавателей местоположения ошибки:

(*)

Последовательность f₀ f₁ f₂– является кодом ошибочной или безошибочной комбинации

Если кодовая комбинация не содержит ошибок, то согласно (*) все позиции будут содержать нули, следовательно, получится код f₀ f₁ f₂ = 0 0 0.

Рассмотрим подчеркнутую кодовую комбинацию 1 0 1 0 1 0 1и начнем последовательно вводить ошибки.

Вводим ошибку в разряд a₀ и получаем код опознавателя ошибки в этом разряде:

,f₀ f₁ f₂ = 0 1 1.

Затем вводим ошибку в разряд а₁и получаем код опознавателя ошибки в этом разряде; затем в вводим ошибкуа₂и получаем код опознавателя ошибки в этом разряде и т.д.

Например, ошибка в разряде а₃:

,f₀ f₁ f₂ = 1 1 1

В итоге получаем таблицу кодов опознавателей ошибок:

Проверим получившийся результат. Пусть передали комбинацию 1000011, а получили1001011. Определяем код опознавателя:

,f₀ f₁ f₂ = 1 1 1следовательно, ошибка в разрядеа_3.

Недостатком такого способа является то, что коды опознавателей ошибок не соответствуют десятичным числам.