Контрольное задание № 3 Тема : Обнаружение и исправление ошибок в сообщениях
3.1. Постановка задачи.
В таблице заданы кодовые комбинации.
1. Определить корректирующие способности кода, представленного в графе 3.1.
2. Получена комбинация кода Хемминга, исправляющего одиночные ошибки (графа 3.2). Проверить, верно, ли передана комбинация, и при необходимость исправить ошибку.
Номер варианта |
3.1 |
3.2 |
15 |
Код |
8.4 |
00000101001 01011010101 10110011110 |
11100111 11100001 10110000 10101101
|
Выполнение работы:
3.2. Определение корректирующих способностей кода, представленного в графе 3.1.
Чтобы в принятом сообщении можно было обнаружить ошибку, это сообщение должно обладать некоторой избыточной информацией, позволяющей отличить ошибочный код от правильного. Минимальное количество символов, в которых любые две комбинации отличаются друг от друга, называется кодовым расстоянием. Минимальное количество символов, в которых все комбинации кода отличаются друг от друга, называется минимальным кодовым расстоянием – это параметр, определяющий помехоустойчивость кода и заложенную в коде избыточность. Минимальным кодовым расстоянием определяются корректирующие свойства данного кода.
Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода, достаточно просуммировать эти комбинации по модулю два и подсчитать число единиц в полученной комбинации.
Определим минимальное кодовое расстояние между 1 и 2 комбинациями:
00000101001
+
01011010101
01011111100 dmin = 7.
Определим минимальное кодовое расстояние между 1 и 3 комбинациями:
00000101001
10110011110
10110110111 dmin
= 8.
Определим минимальное кодовое расстояние между 2 и 3 комбинациями
01011010101
10110011110
11101001011 dmin = 7.
Вычислим минимальное кодовое расстояние:
dmin=min{7, 8, 7}=7.
Для определения корректирующих способностей существуют формулы (1) – (3).
dmin ≥ R + 1, (1)
dmin=
R+1
7
=R+1
R=6.
где R – кратность обнаруживаемых ошибок;
dmin ≥ 2S + 1, (2)
dmin=2S+1 7=2S+1 S=3.
где S – кратность исправляемых ошибок;
dmin ≥ R + S. (3)
dmin= R+S+1 7 =R+S+1 R=4; S=2.
Исследуемый код может обнаружить ошибки кратности 6, либо исправить ошибки кратности 3, либо обнаружить ошибки кратности 4 и две из них исправить.
3.3. Получена комбинация кода Хемминга, исправляющего одиночные или обнаруживающий двойные ошибки (код 8, 4).
Проверить, верно, ли передана комбинация, и при необходимость исправить ошибку.
Пусть надо исправить одиночную ошибку бинарного кода. Такой код состоит из nи символов, несущих информацию, и nк контрольных символов.
Всего символов в коде n= nи + nк
Для вычисления основных параметров кода задается количество символов. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочим, а какие контрольными. Номера контрольных символов удобно выбирать по закону 2i , где i=0,1,2. Номера контрольных символов: 1,2,4,8,16 и т.д. Затем определяют значения контрольных коэффициентов: сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна – значение контрольного коэффициента 0, в противном случае –1.
а8 a7 a6 a5 a4 a3 a2 a1
1 0 0 1 1 0 1 0
После получения очередного кодового слова на приемном конце необходимо вычислить значения разрядов синдрома кода (7, 4) и организовать проверку на четность полученного кодового слова (обозначим это значение через V):
(2.16)
Обозначив
синдром кода через С, а результат общей
проверки на четность
через
,
и пренебрегая
возможностью возникновения ошибок
кратности 3 и выше, запишем алгоритм
декодирования:
при С=0 и V=0
ошибок нет;при С=0 и V=1 ошибка в восьмом разряде;
при С
0
и V=0
двойная ошибка (коррекция блокируется,
необходимо послать запрос повторной
передачи);при С 0 и V=1 одиночная ошибка, осуществляется ее исправление.
Вычислим значение синдрома С и выполним общую проверку на четность (вычислим значение V) первого кодового слова Cod 1.
Cod 1=11100111.
С1= а1+а3+а5+а7 = 1+1+0+1 = 1;
С2 = а2+а3+а6+а7= 1+1+1+1 =0;
С3= а4+а5+а6+а7 = 0+0+1+1 = 0.
V = а1+а2+а3+а4+а5+а6+а7+а8 = 1+1+1+0+0+1+1+1 = 0.
С=(с3+с2+с1) = 001, V = 0. Следовательно, произошла одиночная ошибка, осуществляется ее исправление.
Номер разряда |
Вектор ошибок |
Синдром |
||||||||
а8 а7 |
а6 |
а5 |
a4 |
а3 |
а2 |
а1 |
c3 |
c2 |
c1 |
|
1 |
0 0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Cod 2 = 11100001.
С1= а1+а3+а5+а7 = 1+0+0+1 = 0;
С2 = а2+а3+а6+а7= 0+0+1+1 = 0;
С3= а4+а5+а6+а7 = 0+0+1+1 = 0.
V = а1+а2+а3+а4+а5+а6+а7+а8 = 1+0+0+0+0+1+1+1 = 0.
С=(с3+с2+с1) = 0, V = 0. Ошибок нет.
Cod 3=10110000.
С1= а1+а3+а5+а7 = 0+0+1+0 = 1;
С2 = а2+а3+а6+а7=0+0+1+0 = 1;
С3= а4+а5+а6+а7 =1+0+1+0 = 0.
V = а1+а2+а3+а4+а5+а6+а7+а8 = 0+0+0+0+1+1+0+1 = 1.
С=(с3+с2+с1) = 011, V = 1. Допущена двойная ошибка (коррекция блокируется, необходимо послать запрос повторной передачи).
Cod 4 = 10101101.
С1= а1+а3+а5+а7 =1+1+0+0 = 0;
С2 = а2+а3+а6+а7=0+1+1+0 = 0;
С3= а4+а5+а6+а7 =1+0+1+0 = 0.
V = а1+а2+а3+а4+а5+а6+а7+а8 =1+0+1+1+0+1+0+1 = 1.
С=(с3+с2+с1) = 0, V = 1. Произошла ошибка в восьмом разряде. На передающем конце было отправлено кодовое слово:
Cod 4 |
|
10101101 |
Вектор ошибки а8 |
10000000 |
|
Верная комбинация |
|
00101101 |
Вывод:
При передаче первого кодового слова Cod 1=1110011 произошла одиночная ошибка, осуществилось ее исправление.
При передаче второго кодового слова Cod 2 = 11100001 ошибок не было.
При передаче третьего кодового слова Cod 3=10110000 произошла двойная ошибка в связи, с чем необходимо послать запрос на повторную передачу этого кодового слова.
При передаче четвертого кодового слова Cod 4 = 10101101 произошла ошибка в восьмом разряде.
Код Хемминга представляет собой один из важнейших классов линейных кодов, нашедших широкое применение на практике и имеющих простой и удобный алгоритм обнаружения и исправления ошибки.