Матрица контроля чётности
Каждый линейный код над GF(2) — полем, содержащим только 0 и 1, с арифметикой по модулю 2 — имеет матрицу контроля чётности H. Для кода Хэмминга (7,4) H — это матрица 3×7, столбцы которой являются двоичными представлениями чисел от 1 до 7:
``
H = [ 0 0 0 1 1 1 1 ] ← бит 2 номера позиции
[ 0 1 1 0 0 1 1 ] ← бит 1 номера позиции
[ 1 0 1 0 1 0 1 ] ← бит 0 номера позиции
``
Столбец j матрицы H — это двоичное представление j. Поэтому синдром s = Hr напрямую указывает на позицию ошибки.
Отображение H: GF(2)^7 → GF(2)^3 — это линейное отображение (умножение матрицы по модулю 2). Его ядро ker(H) = { r : Hr = 0 } — это в точности множество допустимых кодовых слов.
Подсчёт размерности: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Таким образом, есть 2^4 = 16 кодовых слов. Это подтверждает 4 информационных бита.
Код как ядро
Слово c ∈ {0,1}^7 — это допустимое кодовое слово тогда и только тогда, когда Hc = 0 (mod 2). Это определяющее уравнение линейного кода.
Пример: c = 0011001. Проверьте Hc mod 2:
``
Строка 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Строка 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Строка 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Таким образом, 0011001 — это допустимое кодовое слово.
Смежные классы кода
Кодовые слова C = ker(H) образуют подгруппу GF(2)^7. Каждое другое слово в GF(2)^7 принадлежит ровно одному смежному классу C.
Определение смежного класса: для любого слова e смежный класс C + e = { c + e : c ∈ C }.
Два слова принадлежат одному смежному классу тогда и только тогда, когда их разность — кодовое слово, т. е. они имеют один синдром: H(r₁) = H(r₂) тогда и только тогда, когда H(r₁ − r₂) = 0 тогда и только тогда, когда r₁ − r₂ ∈ C.
Отображение синдрома H индуцирует изоморфизм GF(2)^7 / C ≅ GF(2)^3. При |C| = 16 и |GF(2)^7| = 128: имеется ровно 128/16 = 8 смежных классов, по одному для каждого значения синдрома в GF(2)^3.
Стандартный массив: список по одному лидеру смежного класса на смежный класс — слово минимального веса Хэмминга в этом смежном классе. Для исправления одиночных ошибок каждый ненулевой синдром уникально соответствует одному паттерну ошибки веса 1 (единица в одной из 7 позиций). Поэтому 7 паттернов ошибок + 1 отсутствие ошибки = 8 смежных классов = 2^3.
Декодирование через лидеры смежных классов
Алгоритм декодирования: получить r → вычислить s = Hr → найти лидер смежного класса e_s (канонический паттерн ошибки для синдрома s) → выдать r − e_s = r + e_s (одно и то же в GF(2)).
Для кода (7,4) 8 лидеров смежных классов: 0000000 (синдром 000), 1000000 (синдром 001), 0100000 (синдром 010), 0010000 (синдром 011), 0001000 (синдром 100), 0000100 (синдром 101), 0000010 (синдром 110), 0000001 (синдром 111).
Почему (7,4) идеален
Код C ⊆ GF(2)^n с минимальным расстоянием 3 исправляет все одиночные ошибки. Каждое кодовое слово c имеет шар Хэмминга радиуса 1: центр c и его n ближайших соседей (паттерны ошибок веса 1). Объём шара = 1 + n.
Для n = 7: объём шара = 8. При 16 кодовых словах: 16 × 8 = 128 = 2^7. Шары идеально замощают GF(2)^7 — каждая точка покрыта, ни одна не покрыта дважды.
Это определение идеального кода: M · Vol(n, t) = 2^n. Идеальные коды, исправляющие одиночные ошибки (t=1), существуют только при специфических параметрах: (7,4), (15,11), (23,12) (двоичный код Голея), и тривиально n = 2^r − 1, k = n − r при любом r ≥ 2.
Геометрия: GF(2)^7 разлагается ровно на 8 орбит под действием кода как раздел смежные классы. Каждая орбита — смежный класс; каждый смежный класс имеет уникальный синдром. Отображение синдрома H — это биекция из смежных классов в GF(2)^3.
Аргумент подсчёта
Для идеального кода, исправляющего одиночные ошибки, с n = 2^r − 1 битами и r битами контроля чётности:
- Число кодовых слов: M = 2^k = 2^(n−r)
- Объём шара: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Всего покрыто: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Тот факт, что Vol(n,1) = 2^r при n = 2^r − 1, — это то, что делает идеальные коды возможными при этих длинах. При других длинах 1 + n не является степенью двойки, и идеальные двоичные коды, исправляющие одиночные ошибки, не могут существовать.
Порождающая матрица и двойственность
Матрица контроля чётности H определяет код через ядро. Её двойственность: порождающая матрица G, чьи строки образуют базис для ker(H).
Для кода (7,4): G — матрица 4×7. Любое кодовое слово c = mG для некоторого вектора сообщения m ∈ GF(2)^4. Строки G порождают код; строки H порождают пулевое пространство кода.
Ключевое соотношение: HG^T = 0 (mod 2). Каждая строка G находится в ker(H); каждая строка H аннулирует каждую строку G.
Двойственный код: C⊥ = ker(G^T) = image(H^T). Для кода (7,4) двойственный код — это [7,3,4] код — код с минимальным расстоянием 4.
Геометрия двойственности: C и C⊥ — ортогональные подпространства GF(2)^7. Всё пространство разлагается на код, его смежные классы и двойственную структуру, которую кодирует отображение синдрома.