Обнаружение ошибок с использованием синдрома

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

Блочный код определяется, как набор возможных кодов, который получается из последовательности бит, составляющих сообщение. Например, если мы имеем К бит, то имеется 2^К возможных сообщений и такое же число кодов, которые могут быть получены из этих сообщений. Набор этих кодов представляет собой блочный код. Линейные коды получаются в результате перемножения сообщения М на порождающую матрицу G[IA]. Каждой порождающей матрице ставится в соответствие матрица проверки четности (n-k)*n. Эта матрица позволяет исправлять ошибки в полученных сообщениях путем вычисления синдрома. Матрица проверки четности находится из матрицы идентичности i и транспонированной матрицы А. G[IA] ==> H[A^TI].

I

A

AT

Если , то H[A^TI] =

Синдром полученного сообщения равен

S = [полученное сообщение]^. [матрица проверки четности].

Если синдром содержит нули, ошибок нет, в противном случае сообщение доставлено с ошибкой. Если сообщение М соответствует М=2^k, а k =3 высота матрицы, то можно записать восемь кодов:

Сообщения	Кодовые вектора	Вычисленные как
M1 = 000	V1 = 000000	M1.G
M2 = 001	V2 = 001101	M2.G
M3 = 010	V3 = 010011	M3. G
M4 = 100	V4 = 100110	M4. G
M5 = 011	V5 = 011110	M5.G
M6 = 101	V6 = 101011	M6 .G
M7 = 110	V7 = 110101	M7 .G
M8 = 111	V8 = 111000	M8 .G

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

Таблица 2.8.3. Стандартный массив для кодов (6,3)

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

Синдром равен произведению левой колонки (CL "coset leader") стандартного массива на транспонированную матрицу контроля четности H^T.

Синдром = CL . HT	Левая колонка стандартного массива

Чтобы преобразовать полученный код в правильный, нужно умножить полученный код на транспонированную матрицу проверки четности, с тем чтобы получить синдром. Полученное значение левой колонки стандартного массива добавляется (XOR!) к полученному коду, чтобы получить его истинное значение. Например, если мы получили 001100, умножаем этот код на H^T:

этот результат указывает на место ошибки, истинное значение кода получается в результате операции XOR:

под горизонтальной чертой записано истинное значение кода.

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

Когда вероятность искажения велика, например, в каналах коммуникаций с геостационарными спутниками, используются методы коррекции ошибок. Одним из таких методов является FEC (Forward Error Correction, иногда называемое канальным кодированием [1]). Технология FEC последнее время достаточно широко используется в беспроводных, локальных сетях (WLAN). Существуют две основные разновидности FEC: блочное кодирование и кодирование по методу свертки.

Блочное кодирование работает с блоками (пакетами) бит или символов фиксированного размера. Метод свертки работает с потоками бит или символов произвольной протяженности. Коды свертки при желании могут быть преобразованы в блочные коды.

Существует большое число блочных кодов, одним из наиболее важных является алгоритм Рида-Соломона, который используется при работе с CD, DVD и жесткими дисками ЭВМ. Блочные коды и коды свертки могут использоваться и совместно.