В области математики и теории информации линейный код — тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.
Основы В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, физическом, канальном, транспортном уровнях модели OSI).
В системах связи возможны несколько стратегий борьбы с ошибками:
обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков — этот подход применяется в основном на канальном и транспортном уровнях; обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу; исправление ошибок () применяется на физическом уровне.
Коды обнаружения и исправления ошибок Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.
В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).
По способу работы с данными коды, исправляющие ошибки делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и сверточные, работающие с данными как с непрерывным потоком.
Блоковые коды Пусть кодируемая информация делится на фрагменты длиной бит, которые преобразуются в кодовые слова длиной бит. Тогда соответствующий блоковый код обычно обозначают . При этом число называется скоростью кода.
Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе несистематическим.
Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из информационных бит сопоставляется бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям: способность исправлять как можно большее число ошибок, как можно меньшая избыточность, простота кодирования и декодирования.
Нетрудно видеть, что приведённые требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.
Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.
Линейные пространства
Порождающая матрица Пусть векторы являются базисом линейного пространства . По определению базиса, любой вектор можно представить в виде линейной комбинации базисных векторов: , либо в матричной форме, как:
,
где
называется порождающей матрицей линейного пространства.
Это соотношение устанавливает связь между векторами коэффициентов и векторами . Перечисляя все векторы коэффициентов можно получить все векторы . Иными словами, матрица порождает линейное пространство.
Проверочная матрица Другим способом задания линейных пространств является описание через проверочную матрицу.
Пусть — линейное k-мерное подпространство n-мерного пространства над конечным полем и — ортогональное дополнение . Тогда по одной из теорем линейной алгебры, размерность равна . Поэтому в существует r базисных векторов. Пусть базис в .
Тогда любой вектор удовлетворяет следующей системе линейных уравнений:
Или в матричной форме: ,
где — проверочная матрица.
Приведённую систему линейных уравнений следует рассматривать как систему проверок для всех векторов линейного пространства, поэтому матрица называется проверочной матрицей.
Формальное определение Линейный код длины n и ранга k является линейным подпространством C размерности k векторного пространства , где — конечное поле из q элементов. Такой код с параметром q называется q-арным кодом (напр. если q = 5 — то это 5-арный код). Если q = 2 или q = 3, то код представляет собой двоичный код, или тернарный соответственно.
Линейный (блоковый) код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовем его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.
Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.
Пусть — ортогональное подпространство по отношению к , а — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:
.
Свойства и важные теоремы
Минимальное расстояние и корректирующая способность Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе .
Минимальное расстояние линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов.
Вес вектора — расстояние Хемминга между этим вектором и нулевым вектором, иными словами — число ненулевых компонент вектора.
Теорема 1:
Минимальное расстояние линейного кода равно минимальному из весов Хемминга ненулевых кодовых слов:
Доказательство:
Расстояние между двумя векторами удовлетворяет равенству , где — вес Хемминга вектора . Из того, что разность любых двух кодовых слов линейного кода также является кодовым словом линейного кода, вытекает утверждение теоремы:
Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она определяет другую, не менее важную характеристику — корректирующую способность:
, здесь угловые скобки обозначают округление «вниз».
Корректирующая способность определяет, какое максимальное число ошибок в одном кодовом слове код может гарантированно исправить.
Поясним на примере. Предположим, что есть два кодовых слова A и B, расстояние Хемминга между ними равно 3. Если было передано слово A, и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову A, чем B. Но если каналом были внесены ошибки в двух битах, декодер может посчитать, что было передано слово B.
Число обнаруживаемых ошибок — число ошибок, при котором декодер может обнаружить ошибочную ситуацию (и, например, инициировать повторную передачу сообщения). Это число равно .
Теорема 2 (без доказательства):
Если любые столбцов проверочной матрицы H линейного (n, k)-кода линейно независимы, то минимальное расстояние кода равно по меньшей мере d. Если при этом найдутся d линейно зависимых столбцов, то минимальное расстояние кода равно d в точности.
Теорема 3 (без доказательства):
Если минимальное расстояние линейного (n, k)-кода равно d, то любые столбцов проверочной матрицы H линейно независимы и найдутся d линейно зависимых столбцов.
Коды Хемминга Исторически «коды Хемминга» должны называться кодами Р. Фишера и были представлены в 1942г (Fisher R.A. The theory of confouding in factor to thr theory). Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром
, где — принятый вектор,
будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.
Код Рида — Маллера — линейный двоичный блочный код. При определённом способе построении он может быть систематическим. В общем случае код Рида — Маллера не является циклическим. Коды Рида — Маллера задаются следующими параметрами: для любых значений и , называемого порядком кода, меньшего, чем : длина кодового слова длина информационной части длина проверочной части минимальное кодовое расстояние
Код Рида — Маллера определяется при помощи порождающей матрицы, состоящей из базисных векторов которая строится по правилу: пусть — вектор, все компоненты которого равны 1; пусть — строки матрицы, столбцами которого являются все двоичные наборы длины
Код Рида — Маллера -го порядка содержит в качестве базиса векторы и все компонентные произведения или меньшего числа этих векторов.
Общий метод кодирования линейных кодов Линейный код длины n с k информационными символами является k-мерным линейным подпространством, поэтому каждое кодовое слово является линейной комбинацией базисных векторов подпространства:
.
Либо с помощью порождающей матрицы:
, где
Это соотношение есть правило кодирования, по которому информационное слово отображается в кодовое
Общий метод обнаружения ошибок в линейном коде Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова соответствует наиболее вероятное переданное слово . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.
Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора вычисляется синдром . Поскольку , где — кодовое слово, а — вектор ошибки, то . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
Линейные циклические коды Несмотря на то, что исправление ошибок в линейных кодах уже значительно проще исправления в большинстве нелинейных, для большинства кодов этот процесс все ещё достаточно сложен. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами.
Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.
Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .
В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть … могут принимать значения 0 или 1.
Порождающий полином Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному . Порождающий полином является делителем .
С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:
несистематическое кодирование осуществляется путём умножения кодируемого вектора на : ; систематическое кодирование осуществляется путём «дописывания» к кодируемому слову остатка от деления на , то есть .
Коды CRC Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.
Таким образом, вид полинома g(x) задаёт конкретный код CRC. Примеры наиболее популярных полиномов:
название кодастепеньполиномCRC-1212CRC-1616CRC-CCITT16CRC-3232
Коды БЧХ