1. Основные понятия
Цель: Обнаружение и исправление ошибок при передаче данных.
Причина ошибок: Помехи в каналах связи.
Типы кодов:
| Тип кода | Возможности | Пример использования |
|---|---|---|
| Обнаруживающие | Только обнаружение ошибок | Контрольная сумма |
| Исправляющие | Обнаружение + исправление | Код Хэмминга |
2. Расстояние Хэмминга
Определение: Количество позиций, в которых соответствующие биты двух кодовых слов различаются.
Формула:
$$ d = \sum_{i=1}^{n} (a_i \oplus b_i) $$
Где \( a_i, b_i \) — биты слов, \( \oplus \) — XOR.
Пример:
10101 и 10011 → Различия в 3-м и 4-м битах → \( d = 2 \)
Правила:
| \( d_{\text{min}} \) | Возможности кода |
|---|---|
| 1 | Нет защиты |
| 2 | Обнаружение 1 ошибки |
| 3 | Обнаружение 2 или исправление 1 |
3. Кодирование с повторением
Принцип: Каждый бит дублируется \( n \) раз.
Пример (трёхкратное повторение):
- Исходный бит:
1→ Закодированный:111 - Принято:
101→ Исправление: большинство битов =1
Схема:
graph LR
A[Бит 0] --> B[000]
A --> C[111]
B -->|Ошибка| D[001]
C -->|Ошибка| E[101]
D --> F{Расшифровка: 0?}
E --> G{Расшифровка: 1?}
Плюсы и минусы:
| Плюсы | Минусы |
|---|---|
| Простота реализации | Высокая избыточность |
4. Код Хэмминга
Принцип: Добавление контрольных битов в позиции степеней 2 (1,2,4…).
Этапы для (7,4)-кода:
- Расстановка битов:
- Позиции 1,2,4 — контрольные
- Позиции 3,5,6,7 — данные
- Вычисление контрольных битов:
- \( r_1 \) = бит3 ⊕ бит5 ⊕ бит7
- \( r_2 \) = бит3 ⊕ бит6 ⊕ бит7
- \( r_4 \) = бит5 ⊕ бит6 ⊕ бит7
- Обнаружение ошибки:
- Синдром \( s_1 = r_1 \oplus \text{бит3} \oplus \text{бит5} \oplus \text{бит7} \)
- Синдром \( s_2 = r_2 \oplus \text{бит3} \oplus \text{бит6} \oplus \text{бит7} \)
- Синдром \( s_4 = r_4 \oplus \text{бит5} \oplus \text{бит6} \oplus \text{бит7} \)
- Позиция ошибки: \( s_4 s_2 s_1 \) (двоичное число)
Пример:
- Данные:
1101→ Закодировано:1 0 1 0 1 0 1 - Принято с ошибкой:
1 0 1 0 1 1 1 - Синдром: \( s_1=0 \), \( s_2=1 \), \( s_4=1 \) → Позиция 6
- Исправление: инвертировать 6-й бит