Коды обнаружения и исправления ошибок
Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию (контрольное число), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.
В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).
По способу работы с данными коды, исправляющие ошибки делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные, работающие с данными как с непрерывным потоком.
Построение кода Хэмминга
Код Хэмминга,
являющийся групповым (n,k) кодом, с
минимальным расстоянием d=3 позволяет
обнаруживать и исправлять однократные
ошибки. Для построения кода Хэмминга
используется
матрица H. 
, где Ak- транспонированная
подматрица, En-k - единичная
подматрица порядка n-k.
Если Х - исходная
последовательность, то произведение
Х·Н=0. Пусть E- вектор ошибок.
Тогда (Х+Е)·Н = Х·Н+Е·Н = 0+Е·Н=E·H -
синдром или корректор, который позволяет
обнаружить и исправить ошибки. Контрольные
символы e1 ,e2 ,...,er образуются
из информационных символов, путем
линейной комбинации 
, где аj={0,1} - коэффициенты,
взятые из подматрицы A матрицы H.
Рассмотрим Построение
кода Хэмминга для k=4 символам. Число
контрольных символов r=n-k можно
определить по неравенству Хэмминга 
для
однократной ошибки. Но так, как нам
известно, только исходное число
символов k, то проще вычислить по
эмпирической формуле
, (5.2)
где [.] - означает
округление до большего ближайшего
целого значения. Вычислим для k=4 
.
Получим код
(n,k)=(7,4); n=7; k=4; r=n-k=3; d=3. Построим
матрицу H.
Контрольные
символы ej определим по формуле 
.
Например, 
. Для
простоты оставляем только слагаемые с
единичными коэффициентами. В результате
получим систему линейных уравнений, с
помощью которых вычисляются контрольные
разряды. Каждый контрольный разряд
является как бы дополнением для
определенных информационных разрядов
для проверки на четность.
При декодировании вычисляем корректор K=k4k2k1
Если корректор равен
нулю, следовательно, ошибок нет. Если
корректор не равен нулю, то местоположение
вектор-столбца матрицы H, совпадающего
с вычисленным корректором, указывает
место ошибки. При передаче может
возникнуть двойная и более ошибка.
Корректор также не будет равен нулю. В
этом случае произойдет исправление случайного
символа и нами будет принят неверный
код. Для исключения такого автоматического
исправления вводится еще один
символ 
для
проверки всей комбинации на четность.
Кодовое расстояние d=4. Тогда
матрица H будет иметь вид
Пример 5.4. Дана 1101 - исходная комбинация (k=4). Закодировать ее в коде Хэмминга.
По формуле (5.2) находим число контрольных символов r=3. Берем регистр из 7 ячеек памяти. Размещаем исходную комбинацию в ячейках 3,5,6,7.
1 2 3 4 5 6 7
* * 1 * 1 0 1
Находим контрольные символы
е4 = 5 + 6 + 7 = 1 + 0 + 1 = 0
е2 = 3 + 6 + 7 = 1 + 0 + 1 = 0
е1 = 3 + 5 + 7 = 1 + 1 + 1 = 1
Закодированная комбинация будет иметь вид
1 2 3 4 5 6 7
1 0 1 0 1 0 1
Допустим, что при передаче возникла ошибка, и мы приняли неверную комбинацию
1 2 3 4 5 6 7
1 0 1 0 1 1 1
Проверяем ее
к 4 = 4 + 5 + 6 + 7 = 0 + 1 + 1 + 1 = 1
к2 = 2 + 3 + 6 + 7 = 0 + 1 + 1 + 1 = 1
к1 = 1 + 3 + 5 + 7 = 1 + 1 + 1 + 1 + 0
K= 
-
в шестом разряде ошибка.
Если бы нам понадобилось построить код и для проверки двойных ошибок, необходимо было бы ввести еще один дополнительный нулевой разряд.
Получим следующий код
0 1 2 3 4 5 6 7
0 1 0 1 0 1 0 1
При передаче и возникновении ошибки код будет иметь вид
0 1 2 3 4 5 6 7
0 1 0 1 0 1 1 1
Проверка в этом случае показала бы, что корректор K=110, а проверка всей комбинации на четность E0 = 0+1+0+1+0+1+1+1=1. Это указывает на одиночную ошибку. Допускается автоматическое исправление ошибки.
Существует следующий алгоритм декодирования кода Хэмминга с d=4
|
Корректор - K |
Значение E0 |
Вывод |
|
K=0 |
E0=0 |
Ошибок нет |
|
K#0 |
E0#0 |
Произошла одиночная ошибка |
|
K#0 |
E0=0 |
Произошла двойная ошибка. Исправление запрещено. |
|
K=0 |
E0#0 |
Произошла тройная или более нечетная ошибка |
Код (7,4) является минимально возможным кодом с достаточно большой избыточностью. Эффективность кода (k/n) растет с увеличением длины кода
|
Длина кода - n |
7 |
15 |
31 |
63 |
|
Число информационных разрядов - k |
4 |
11 |
26 |
57 |
|
Число контрольных разрядов - r |
3 |
4 |
5 |
6 |
|
Эффективность кода k/n |
0,57 |
0,73 |
0,84 |
0,9 |
-
Алгоритмы и их свойства. Способы записи алгоритма. Различные подходы к разработке алгоритмов. Формализация понятия «алгоритм». Понятие сложности алгоритма. Полиномиальные и экспоненциальные алгоритмы, понятие трудной задачи.
Алгоритм - это точное описание упорядоченной последовательности действий, приводящей за конечное число шагов к необходимому результату.
Свойства алгоритмов:
-
понятность
-
однозначность
-
дискретность (пошаговость)
-
массовость (универсальность)
-
результативность
-
конечность
-
безошибочность
Способы представления алгоритма:
-
словесный;(инструкции, рецепты)
-
табличный;(бухгалтерские ведомости)
-
графический;(блок схема)
-
программа на алгоритмическом языке.( изложение алгоритма специально для ЭВМ)