Обнаружение ошибок с помощью систематических кодов

Систематические коды

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

v в число исходных комбинаций не должна входить тривиальная (нулевая);

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

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

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

В классической (канонической) форме кода элементы первых k столбцов служат для информационных целей, а оставшихся – для проверочных. Соответственно, порождающую матрицу G можно представить в виде двух подматриц – информационной I_k и проверочной P., где,

Информационную подматрицу часто берут в виде квадратной единичной матрицы:

При этом проверочная подматрица P должна строиться с соблюдением следующих условий:

1. вес (количество единиц) каждой строки подматрицы должен быть не менее d_min-1

2. все строки должны быть различны

3. кодовое расстояние между любыми двумя строками подматрицы должно быть не менее d_min-2

Пусть, например, порождающая матрица (7,4)-кода имеет вид:

и на вход вторичного (помехоустойчивого) кодера поступила исходная комбинация m = [0 0 1 1]. Тогда кодовое слово образуется умножением исходной комбинации на порождающую матрицу.

U = m·G =

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

1. В порождающей матрице G выделяют информационную квадратную подматрицу I и проверочную подматрицу P.

2. Проверочную подматрицу транспонируют, получая подматрицу P^T.

3. Справа к подматрице P^T приписывают квадратную единичную матрицу размера r×r.

Получается матрица, которую используют для обнаружения ошибок путем проверки ее ортогональности полученному кодовому слову Û. Вычисляют вектор s, называемый синдромом ошибки: s = H·Û. Если синдром ошибки равен нулю, то комбинация передана безошибочно, в противном случае ошибка существует, ее можно даже исправить. Можно показать, что синдром ошибки однозначно определяется вектором ошибки. Действительно: S = H∙Û, но в свою очередь Û = UÅe, значит S = H∙(UÅe) = H∙UÅH∙e. Матрица H составляется так, чтобы выполнялось условие ортогональности H∙U = 0, следовательно S = H∙e.

Возьмем порождающую матрицу (7.4)-кода из предыдущего примера и составим проверочную матрицу. Проверочная подматрица P имеет вид:

. Транспонируем:.

Составим проверочную матрицу, приписав справа единичную матрицу 3´3:

.

Проверим полученное в предыдущем примере кодовое слово U = [0 0 1 1 0 0 1].

Синдром равен 0, следовательно, ошибки нет. Комбинацию можно декодировать. Это просто. Первые четыре разряда принятого кодового слова и представляют собой исходную комбинацию. Допустим, произошла ошибка во втором разряде и была принята ошибочная комбинация Û = [0 1 1 1 0 0 1]. Вычислим синдром

Синдром ненулевой, следовательно, обнаружена ошибка. Можно ли эту ошибку не только обнаружить, но и исправить? Обратим внимание, что всего возможно 7 различных однократных ошибок (по числу разрядов). Синдром трехзначный, значит, существует 7 ненулевых синдромов. То есть каждой ошибке можно сопоставить свой синдром. Следовательно, по виду синдрома можно локализовать, а значит, исправить ошибку. Синдром совпадает с тем столбцом проверочной матрицы, номер которого соответствует позиции ошибки (верно только для однократных ошибок).

Дата добавления: 2014-10-22