Основы теории кодирования

Overview

Лекция посвящена основам теории кодирования, моделям передачи данных, ошибкам в каналах связи и способам их обнаружения и исправления с помощью различных кодов контроля.

Введение в теорию кодирования

• Передача данных может сопровождаться ошибками из-за помех, сбоев оборудования или атмосферных условий.
• Используются коды контроля ошибок для обнаружения и коррекции ошибок при передаче данных.
• Пример: передачи данных с Марса на Землю требуют эффективных и надёжных методов кодирования.

Структура и процесс кодирования

• Передача сообщения включает кодирование, передачу по каналу и декодирование на приёмнике.
• Коды и криптография используются для защиты и коррекции данных.
• Введение понятий "кодовый вектор", "вектор ошибки", "суммирование по модулю".

Коды ISBN и контрольные разряды

• ISBN-код состоит из 10 или 13 цифр, где последний разряд — контрольная цифра.
• Контрольная цифра вычисляется с помощью взвешенной суммы цифр и сравнивается по модулю 11 (для 10-значных кодов) или модулю 10 (для 13-значных).
• Контрольные коды позволяют обнаружить ошибку при вводе или передаче номера.

Двумерные коды и матрицы

• Коды для коррекции ошибок могут быть представлены в виде матриц (например, 5x6).
• Использование паритетных битов по строкам и столбцам позволяет обнаруживать и исправлять одиночные ошибки.

Параметры и свойства кодов

• Минимальное расстояние Хэмминга между кодовыми словами определяет возможности обнаружения и исправления ошибок.
• Основные параметры кода: длина слова n, число информационных битов k, минимальное расстояние d.
• Коды могут быть линейными или нелинейными; важна бинарность (используются 0 и 1).

Бинарные линейные коды

• Бинарный линейный код — код, где сумма любых двух кодовых слов также принадлежит коду.
• Проверка линейности: если x, y ∈ C, то x + y ∈ C (по модулю 2).
• Коды классифицируются по типу (n, k, d), где n — длина кода, k — число информационных битов, d — минимальное расстояние.

Key Terms & Definitions

• Код — способ представления данных с избыточностью для контроля ошибок.
• Контрольная цифра — дополнительная цифра для проверки корректности кода.
• Вектор ошибки — позиционно указывает места ошибок в переданном сообщении.
• Паритетный бит — бит, добавляемый для контроля чётности.
• Минимальное расстояние Хэмминга — минимальное число позиций, в которых различаются любые два кодовых слова.
• Линейный код — код, замкнутый относительно сложения по модулю 2.

Action Items / Next Steps

• Повторить основные формулы вычисления контрольных цифр (ISBN-10, ISBN-13).
• Ознакомиться с примерами построения и коррекции ошибок с помощью двумерных кодов.
• Подготовиться к практике по вычислению расстояния Хэмминга и определению параметров кода.