Teoria_informatsii_i_kodirovania
.pdfОсновные задачи:
•отыскание кодов, эффективно исправляющих ошибки требуемого вида;
•нахождение методов кодирования и декодирования;
•нахождение простых способов программной и аппаратной реализации кодов.
Внесение избыточности
Внесение избыточности
• Расстояние между КК равно 1
d=1
Расстояние между КК равно 2
d=2
Расстояние между КК равно 3
d=3
ОСНОВНЫЕ ХАРАКТЕРИСТИКИ КОРРЕКТИРУЮЩИХ КОДОВ
•При общем числе n символов в блоке число информационных символов равно k, а число проверочных символов: m = n - k
•число разрешенных и запрещенных кодовых комбинаций;
•избыточность кода;
•минимальное кодовое расстояние;
•число обнаруживаемых или исправляемых ошибок;
•корректирующие возможности кодов.
•Если код используется только для обнаружения ошибок кратностью r, то необходимо и достаточно, чтобы минимальное кодовое расстояние было
dmin ≥ r + 1
•условие обнаружения всех ошибок кратностью r можно записать r = dmin – 1
•Чтобы можно было исправить все ошибки кратностью s и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию dmin ≥ 2s + 1
•условие исправления всех ошибок кратностью не более s можно записать:
s<= (dmin – 1)/2
Весовой состав кодового множества
• n=2 |
00 w=0 |
n=3 000 |
w=0 |
• |
01 w=1 |
001 w=1 d=2 |
|
• |
10 |
100 |
|
• |
11 w=2 |
010 |
|
• |
|
011 |
w=2 d=2 |
• |
|
101 |
|
• |
|
110 |
|
• |
|
111 |
w=3 и т.д. |
• |
|
|
|
Избыточные коды
•Неразделимые избыточные коды:
•Код на некоторые сочетания составляет
половину полного кодового множества
|
М=2−1 . |
|
|
|
|
|
|
|
|
• |
Код на одно сочетание М= ( ). Например, |
|||
• |
(4)= 6 0011 |
|
|
|
|
2 |
|
|
|
• |
0101 |
|
|
|
• |
0110 |
|
|
= 2 |
|
|
|
|
|
• |
1001 |
|
|
|
• |
1010 |
|
|
|
• |
1100 |
|
|
|
Разделимые избыточные кода
•Если число символов «1» исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ «0», а если число символов «1» нечетное, то в дополнительном разряде формируют символ «1».
•Правило формирования проверочного символа:
Критерий правильности