Коды Хэмминга, исправляющие ошибки. Декодирование, синдром ошибки.

 

17.3.4. Коды Хемминга, исправляющие одиночные ошибки.

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

(17.13)

С учетом этого уравнение (17.12) может быть записано в виде:

(17.14)

Из этого следует, что при наличии одиночной ошибки в кодовом слове из n символов, например, в j-й позиции, последовательность ошибок состоит из всех нулей за исключением единицы в j-й позиции, и тогда

(17.15)

Поэтому при появлении одиночной ошибки в j-й позиции принимаемого кодового слова формируется синдром, равный в j-й вектор- строке проверочной матрицы. Если необходимо обнаружить все одиночные ошибки, то все вектор- строки, образующие проверочную матрицу, должны быть различными. При этом вектор, содержащий все нули, должен быть исключен, поскольку нулевой синдром означает отсутствие ошибок. Поскольку имеется 2 ^{n- k} различных последовательностей длиной (n - k ), то проверочная матрица содержит 2 ^{n- k} - 1 строк. Таким образом, n и k связаны между собой соотношением:

n = 2 ^{n- k} – 1, (17.16) где (n – k ) – количество проверочных символов.

Пример 17.3. Код Хемминга (7, 4). Рассмотри код с (n – k )= 3 проверочными символами. Имеется 2³ – 1 = 7 последовательностей длиной 3 (исключая последовательность из всех нулей). Эти семь последовательностей являются строками проверочной матрицы. Из этого следует, что n = 7 и k = 4. Для систематического (7, 4) кода первые четыре строки проверочной матрицы представляют последовательности, содержащие более одной двоичной единицы. Порядок следования строк произвольный и никак не влияет на характеристики кода. Одна из возможных проверочных матриц кода, исправляющего одиночные ошибки, имеет вид:

(17.17)

Этой проверочной матрице соответствует порождающая матрица кода:

(17.18)

Информационной последовательности соответствует кодовое слово: . Если ошибка передана в пятой позиции, то принимаемая последовательность и синдром имеют следующий вид:

,

Так как синдром совпадает с пятой строкой проверочной матрицы, то ошибка произошла в пятой позиции.

 

.

Сдвиг	Вход	Ключ	Коммутатор	R1	R2	R3	Выход
		С	А
		С	А
		С	А
		С	А
	-		В
	-		В
	-		В

 

а) б)

Рис. 17.3 Кодирование циклическим кодом (7.4)

а) структурная схема кодера; б) таблица содержимого регистра сдвига кодера.

Теперь предположим, что ошибки имеют место во второй и пятой позициях, так что вектор ошибки . Принятая последовательность и ей соответствует синдром: ошибочно указывающий на то, что ошибка произошла в седьмой (шестой? ) позиции. Причина этого ошибочного решения заключается в том, сто код, формируемый согласно (17.17) имеет расстояние 3 и не способен исправлять двойные ошибки, для исправления которых необходимо иметь расстояние 5. Однако при этом он обнаруживает наличие ошибок.

На рис. 17.3 приведена структурная схема кодера, иллюстрирующая процедуру кодирования.

 

3.1.3. Синдромное декодирование кода Хемминга, исправляющего одиночные ошибки

 

Коды Хемминга бывают двоичными и недвоичными. Двоичные коды включают класс кодов со свойствами:

(n, k) = (2^m -1, 2^m-1 - m), (3.23)

где m –целое положительное число; при m =3 имеем код (7, 4).

Проверочная матрица таких кодов проста, содержит (n-k) строк и n линейно независимых столбцов-векторов с (n- k) = m элементами. Она легко приводится к систематической форме (3.17) и соответствующей порождающей матрице из уравнения (3.16).

Однако, при m > 1 можно найти 3 столбца из , которые при сложении дают нуль. Следовательно, для ( n, k) кода Хемминга d_min =3.

Для иллюстрации синдромного декодирования кода Хемминга, исправляющего одиночные ошибки, рассмотрим проверочную матрицу:

(3.24)

где - вектор- строка из (n- k) символов.

В этом случае уравнение синдрома (3.22) имеет вид:

. (3.25)

При наличии одиночной ошибки в кодовом слове из n символов, например, в j -й позиции, последовательность ошибок состоит из нулей за исключением единицы в j -й позиции, и тогда

(3.26)

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

Если необходимо обнаружить все одиночные ошибки, то все вектор-строки проверочной матрицы должны быть различными. При этом вектор, содержащий все нули, должен быть исключен, поскольку нулевой синдром означает отсутствие ошибок. Так как имеется 2 ^n-k различных последовательностей длиной ( n-k ), то проверочная матрица содержит 2 ^{n - k}- 1 строк.

Таким образом, n и k в (3.25) связаны между собой соотношением:

 

n = 2 ^{n - k} – 1, (3.27)

где ( n – k ) – количество проверочных символов

 

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. Больной бронхоэктатическое болезнью с выраженным обструктивным компонентом погиб от прогрессирующего нефротического синдрома. На секции обнаружен амилоидоз почек.
2. Вопрос 57. Стилистические ошибки. Проблемы их классификации и устранения.
3. Глава Х. ОБОЛОЧКИ ГОЛОВНОГО И СПИННОГО МОЗГА, ЦЕРЕБРОСПИНАЛЬНАЯ ЖИДКОСТЬ, МЕНИНГЕАЛЬНЫИ СИНДРОМ
4. Дети с синдромом дефицита внимания (гиперактивные).
5. ИНТЕРПРЕТАЦИЯ ОСНОВНЫХ РЕНТГЕНОЛОГИЧЕСКИХ СИНДРОМОВ ВО ФТИЗИАТРИИ С ЭЛЕМЕНТАМИ ДИФФЕРЕНЦИАЛЬНОЙ ДИАГНОСТИКИ
6. Коды ICOM гарантируют стыковку диаграмм
7. Неврологические синдромы с нарушениями различных функций
8. НЕВРОТИЧЕСКИЙ ДЫХАТЕЛЬНЫЙ СИНДРОМ -ГИПЕРВЕНТИЛЯЦИОННАЯ ТЕТАНИЯ
9. ОКАЗАНИЕ ПЕРВОЙ ДОВРАЧЕБНОЙ ПОМОЩИ ПРИ СИНДРОМЕ ДЛИТЕЛЬНОГО СДАВЛЕНИЯ НА МЕСТЕ ПРОИСШЕСТВИЯ
10. Основные симптомы и синдромы при заболеваниях печени
11. Острый коронарный синдром без подъемов сегмента ST