EssayAI
Блог
Блог
Математика и алгоритмы

Проверочная матрица линейного кода: синдром и пример

8 ноября 2026Время чтения: 8 минут
#линейный код#проверочная матрица#синдром ошибки#код Хэмминга#теория кодирования
Проверочная матрица линейного кода: синдром и пример

Проверочная матрица линейного кода - это набор уравнений, которым должно удовлетворять каждое кодовое слово. Умножив на неё принятое слово, получают синдром: он показывает, какие проверки нарушены. На примере двоичного кода Хэмминга разберём вычисление и увидим, когда синдром помогает найти ошибочный бит. В интерактиве можно менять его позицию и сравнивать результат со столбцами матрицы.

Что проверяет матрица

Линейный код длины nn и размерности kk над полем F2={0,1}\mathbb F_2=\{0,1\} - подпространство множества двоичных векторов длины nn. Его элементы называют кодовыми словами. Сложение здесь выполняется по модулю 2: 1+1=01+1=0, а вычитание совпадает со сложением. Близкая запись чисел объясняется в статье о двоичной системе счисления.

Проверочная матрица HH размера (n−k)×n(n-k)\times n полного строкового ранга задаёт код как множество решений

HcT=0.Hc^{T}=0.

Здесь cc - строка из nn битов, cTc^T - столбец. Каждая строка HH задаёт одну проверку чётности: единицы в ней выбирают позиции, сумма которых должна быть чётной. Так, строка (1,0,1)(1,0,1) требует c1+c3=0c_1+c_3=0 по модулю 2. Необязательно хранить все допустимые слова списком: достаточно проверить уравнения. В более общем определении допускаются и избыточные строки; тогда их число может превышать n−kn-k, но ранг остаётся n−kn-k.

В слове 1011010 меняется третий бит, и синдром становится 011. После обратного изменения бита исходное слово и нулевой синдром возвращаются.

Пример матрицы кода Хэмминга

Возьмём код длины семь с матрицей

H=(000111101100111010101).H=\begin{pmatrix} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{pmatrix}.

Её семь столбцов - все ненулевые трёхбитовые векторы от 001001 до 111111 в указанном порядке. Три строки независимы: столбцы 1, 2 и 4 образуют единичную матрицу с переставленными столбцами. Поэтому ранг равен трём, размерность кода 7−3=47-3=4, а число кодовых слов равно 24=162^4=16. Число независимых проверок показывает, сколько степеней свободы они убирают, но позиции информационных и проверочных битов зависят от выбранного представления.

Проверим c=1011010c=1011010. Три суммы по выбранным строками позициям равны соответственно 1+0+1+0=21+0+1+0=2, 0+1+1+0=20+1+1+0=2 и 1+1+0+0=21+1+0+0=2. Остаток каждой от деления на два равен нулю, следовательно, HcT=000Hc^T=000. Это конкретное слово допустимо. Обычное правило умножения матриц по строкам и столбцам сохраняется, меняется только арифметика поля.

Как получить допустимое слово

Проверочную матрицу можно использовать и для построения слова, решив её уравнения относительно выбранных проверочных позиций. Для нашей матрицы удобно оставить информационными позиции 3, 5, 6 и 7: они могут принимать любые значения. Тогда проверки имеют вид

x4+x5+x6+x7=0,x2+x3+x6+x7=0,x1+x3+x5+x7=0.x_4+x_5+x_6+x_7=0,\quad x_2+x_3+x_6+x_7=0,\quad x_1+x_3+x_5+x_7=0.

В двоичном поле перенос через знак равенства не меняет знак. Поэтому x4=x5+x6+x7x_4=x_5+x_6+x_7, x2=x3+x6+x7x_2=x_3+x_6+x_7, а x1=x3+x5+x7x_1=x_3+x_5+x_7. Все суммы вновь берутся по модулю 2. Например, для информационных битов x3x5x6x7=1010x_3x_5x_6x_7=1010 получаем x4=1x_4=1, x2=0x_2=0 и x1=1x_1=1. Записывая все семь позиций в исходном порядке, получаем уже знакомое слово 10110101011010.

Важно не приклеивать вычисленные биты к концу без перестановки остальных: в этой матрице проверочные позиции находятся в начале и середине слова. В другой систематической записи они могут стоять в конце, и формулы будут выглядеть иначе. Сам код при согласованной перестановке координат имеет те же параметры и расстояние, но значения синдрома для заданного номера позиции следует читать по новой матрице.

Как найти синдром принятого слова

Пусть передано c=1011010c=1011010, но третий бит изменился. Получатель видит r=1001010r=1001010 и вычисляет

s=HrT=(011).s=Hr^T=\begin{pmatrix}0\\1\\1\end{pmatrix}.

По строкам это 1+0+1+0=21+0+1+0=2, 0+0+1+0=10+0+1+0=1 и 1+0+0+0=11+0+0+0=1; остатки дают 011011. Вектор ошибки e=0010000e=0010000 содержит единицу только на третьей позиции. Поскольку r=c+er=c+e, линейность даёт

HrT=H(c+e)T=HcT+HeT=HeT.Hr^T=H(c+e)^T=Hc^T+He^T=He^T.

Для одиночной ошибки произведение HeTHe^T выбирает соответствующий столбец HH. Столбец 011011 стоит третьим, поэтому при условии не более одной ошибки меняем третий бит обратно и получаем 10110101011010.

Три строки проверочной матрицы: третий столбец равен синдрому 011 при ошибке в третьей позиции
Три строки проверочной матрицы: третий столбец равен синдрому 011 при ошибке в третьей позиции

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

Что синдром может и чего не может показать

Ненулевой синдром доказывает, что принятое слово не принадлежит коду. Нулевой означает лишь, что оно удовлетворяет всем проверкам; он не гарантирует отсутствия ошибок при передаче. Если вектор ошибки сам является ненулевым кодовым словом, то HeT=0He^T=0, и получатель не заметит подмену только по синдрому.

Для двух ошибок синдром равен сумме двух столбцов. В нашем примере ошибки в позициях 1 и 2 дают 001+010=011001+010=011 - тот же синдром, что и одиночная ошибка в позиции 3. Если безусловно исправить третий бит, результат окажется другим кодовым словом. Поэтому правило «синдром равен номеру ошибки» действует здесь только в выбранном порядке столбцов и при предположении об одной ошибке. В общем случае декодер выбирает предполагаемый вектор ошибки по модели канала или использует другие сведения.

Синдром как результат нескольких проверок

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

В учебном примере у каждой позиции свой ненулевой столбец, поэтому семь одиночных ошибок дают семь разных синдромов. Восьмой синдром, 000000, соответствует отсутствию ошибки в рассматриваемом наборе вариантов. Это не перечисление всех возможных векторов ошибки: всего их 272^7, поэтому многие дают одинаковый результат проверки. Такой подход к декодированию описан в учебных материалах MIT.

Как построить H по порождающей матрице

Порождающая матрица GG описывает код с другой стороны: из информационной строки uu получают c=uGc=uG. Для систематической двоичной матрицы

G=(IkP)G=\begin{pmatrix}I_k & P\end{pmatrix}

можно взять

H=(PTIn−k).H=\begin{pmatrix}P^T & I_{n-k}\end{pmatrix}.

Действительно, GHT=P+P=0GH^T=P+P=0 по модулю 2, а единичный блок обеспечивает полный ранг HH. В поле иной характеристики вместо первого блока пишут −PT-P^T. Для несистематической GG найдите базис решений системы Gx=0Gx=0 над нужным полем и запишите эти векторы строками HH. Убедитесь, что строк ровно n−kn-k и они независимы: одного условия GHT=0GH^T=0 недостаточно, если проверок слишком мало.

Та же логика применяется к другим семействам, например к кодам Рида - Маллера. Строковые преобразования HH над полем сохраняют её ядро, если обратимы; потому проверочная матрица одного кода не единственна.

Как по столбцам определить расстояние

Расстояние Хэмминга между словами - число различающихся позиций. Для линейного кода минимальное расстояние dd равно минимальному числу ненулевых позиций ненулевого кодового слова. Условие HxT=0Hx^T=0 говорит, что сумма столбцов с номерами ненулевых координат xx равна нулю. Поэтому dd - наименьшее число линейно зависимых столбцов HH.

В нашей матрице нет нулевого столбца и одинаковых столбцов, значит зависимость из одного или двух столбцов невозможна. Но 001+010+011=000001+010+011=000, поэтому d=3d=3. Такой код гарантированно обнаруживает до двух ошибок или исправляет одну; одновременно обещать исправление одной и обнаружение любой второй ошибки стандартным декодером нельзя. Общий принцип - исправление до ⌊(d−1)/2⌋\lfloor(d-1)/2\rfloor ошибок. Подробнее устройство этого семейства разобрано в статье о коде Хэмминга.

Где встречаются проверочные матрицы

Проверки чётности используют при передаче и хранении цифровых данных, когда избыточность помогает выявить и исправить искажения. Для длинных кодов важна не только исправляющая способность, но и стоимость вычислений. У LDPC-кодов матрица проверок разрежена: в ней относительно мало единиц, что позволяет строить эффективные итеративные алгоритмы. Однако разреженность сама по себе не гарантирует исправления любой конкретной ошибки: результат зависит от кода и декодера.

Частые ошибки

  • Считать в обычной арифметике до конца. Суммы нужно уменьшить по модулю 2: например, 22 превращается в 00.
  • Путать HH и GG. Одна матрица задаёт проверки, другая порождает слова; их размеры и роли различны.
  • Принимать нулевой синдром за доказательство безошибочной передачи. Ошибка может перевести одно кодовое слово в другое.
  • Исправлять любую ненулевую комбинацию как одиночную ошибку. При нескольких ошибках синдром может совпасть с одиночным.

FAQ

Всегда ли у синдрома есть единственная позиция ошибки?

Нет. Для одиночных ошибок это верно, когда все столбцы HH ненулевые и различны. При нескольких ошибках совпадения синдромов возможны даже тогда.

Сколько строк должно быть у H?

У полной по рангу матрицы без избыточных проверок для кода [n,k][n,k] ровно n−kn-k строк. Можно добавить зависимые проверки, сохранив тот же код.

Можно ли восстановить код по H?

Да. Его слова - все решения HxT=0Hx^T=0 над заданным полем. Базис этого ядра можно записать строками порождающей матрицы.

Коротко

Проверочная матрица задаёт линейный код через систему проверок, а синдром HrTHr^T показывает их результат для принятого слова. В выбранном коде Хэмминга синдром одиночной ошибки совпадает со столбцом её позиции; вывод об исправлении зависит от предположения о числе ошибок.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Код Хэмминга: исправление ошибок на примере

Код Хэмминга: исправление ошибок на примере

Код Хэмминга для исправления ошибок: как расставить проверочные биты, вычислить синдром и восстановить данные на примере кода (7, 4), а также каковы его ограничения.

8 ноября 20269 минут
Код Рида-Маллера: параметры, построение и декодирование

Код Рида-Маллера: параметры, построение и декодирование

Код Рида-Маллера простыми словами: как считать длину, размерность и кодовое расстояние RM(r, m), рекурсивное построение u, u+v и мажоритарное декодирование с примерами и калькулятором.

19 июня 20267 минут
Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.

8 ноября 20268 минут
Абсолютная пропускная способность СМО: формула

Абсолютная пропускная способность СМО: формула

Как найти абсолютную пропускную способность СМО через интенсивность потока и вероятность отказа: формула, пример расчёта и отличие от относительной способности.

8 ноября 20268 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

8 ноября 20268 минут
Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

8 ноября 20268 минут