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

,

а выходом кодера является вектор из символов

.

Операцию кодирования, выполняемую в линейном двоичном блоковом коде, можно представить совокупностью из уравнений вида

(8.1.2)

где или , а представляют произведение и . Линейные уравнения (8.1.2)

можно также представить в матричной форме

где - порождающая матрица кода, равная

(8.1.4)

Заметим, что произвольное кодовое слово – это просто линейная комбинация векторов из ,

Поскольку линейный код с кодовыми словами является подпространством размерности , векторы порождающей матрицы должны быть линейно независимыми, т.е. они должны образовывать пространство размерности . Другими словами, должны образовать базис для кода. Заметим, что ансамбль базовых векторов не единственный и, следовательно, не уникальна. Мы также заметим, что, поскольку пространство имеет размерность , ранг матрицы равен .

Любую порождающую матрицу кода путём проведения операций над строками (и перестановкой столбцов) можно свести к «систематической форме»:

, (8.1.6)

где - единичная матрица, а - матрица, которая определяет избыточных или проверочных символов. Заметим, что порождающая матрица систематического кода создает линейный блоковый код, в котором первые бит любого кодового слова идентичны информационным битам, а остающиеся бит любого кодового слова являются линейными комбинациями информационных бит. Эти избыточных бита называют паритетными (проверочными) битами. Результирующий код называется в этом случае систематическим кодом .

Если код порождён матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим. Однако такая матрица эквивалентна матрице в систематической форме в том смысле, что одна может быть получена из другой элементарными операциями над строками и перемещением столбцов. Два линейных кода, порожденных двумя эквивалентными порождающими матрицами, называют эквивалентными и один может быть получен из другого перестановкой элементов. Таким образом, каждый линейный код эквивалентен линейному систематическому коду.

Пример 8.1.1. Рассмотрим код (7, 4) с порождающей матрицей

. (8.1.7)

Типичное кодовое слово можно выразить так:

где представляют четыре информационных бита, a представляют три паритетных бита, определённых так:

Линейный систематический двоичный блоковый кодер можно реализовать, используя -битовый регистр сдвига, сумматоров , связанных с соответствующими ячейками регистра сдвига и генерирующих проверочные символы, которые потом временно располагаются во втором регистре сдвига длины . Затем информационных бита, а за ними проверочных бита последовательно покидают два регистра и подаются на модулятор. Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1).

Рис. 8.1.1. Линейный регистр сдвига для получения двоичного кода (7,4)

С любым линейным кодом кодом связан дуальный код размерностью .

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

где означает вектор-столбец, состоящий из нулей, а - кодовое слово кода. Поскольку (8.1.9) справедливо для любого кодового слова кода, то следует

где - теперь матрица со всеми нулевыми элементами.

Теперь предположим, что линейный код является систематическим, и его порождающая матрица дана в систематической форме (8.1.6). Тогда, поскольку , следует, что

(8.1.11)

Отрицательный знак в (8.1.11) может быть опущен при работе с двоичными кодами, поскольку вычитание по идентично сложению по .

Пример (8.1.2). Для систематического кода (7, 4), генерируемого матрицей , определяемой (8.1.7), имеем согласно (8.1.11) матрицу в виде

(8.1.12)

Теперь уравнение распадается на три уравнения

(8.1.13)

Таким образом, видим, что произведение эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления Это значит, что (8.1.13) эквивалентно (8.1.8).

Матрицу можно использовать в декодере для проверки того, удовлетворяет ли принимаемое кодовое слово условию (8.1.13), т.е. . Таким образом, декодер сверяет принятые проверочные символы с соответствующей линейной комбинацией символов и , которые формируют проверочные символы на передаче. Поэтому принято называть проверочной матрицей, связанной с кодом.

Выскажем соображение, касающееся связи минимального расстояния кода и его проверочной матрицы . Произведение с представляют линейную комбинацию столбцов . Поскольку , векторы-столбцы линейно зависимы. Допустим, что означает кодовое слово с минимальным весом линейного кода . Оно должно удовлетворять условию . Поскольку минимальный вес равен минимальному расстоянию, следует, что столбцов линейно зависимы. Альтернативно, мы можем сказать, что не более, чем столбцов линейно независимы. Поскольку ранг матрицы не больше , имеем . Следовательно, имеет верхнюю границу. Мы называем код информационных символов (во всех кодовых комбинациях) нулями. Эти. Укороченный код состоит из кодовых слов. Минимальное расстояние этих кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного кода.

Рассмотрим систематический линейный код , задаваемый порождающей матрицей , и построим матрицу вида

где надстрочный символ означает транспонирование матрицы . Роль подобной матрицы становится наиболее очевидной, если учесть, что для любого кодового вектора

Из (6.6) следует, умножение любого кодового вектора на транспонированную матрицу дает нуль, в связи с этим матрицу (6.5) называют проверочной матрицей . Кроме того, говорят, что линейный код является нуль–пространством проверочной матрицы, либо что код ортогонален проверочной матрице.

На основании соотношений (6.4) и (6.6) имеем

откуда не составляет труда получить, что проверочные символы кодового слова определены, как

Таким образом, линейный код может быть задан как порождающей (6.3) и проверочной (6.5) матрицами, так и соотношениями (6.7), устанавливающими связь между проверочными и информационными символами кодовых слов.

Теорема 6.4.1. Линейный код имеет минимальное расстояние, равное , тогда и только тогда, когда проверочная матрица содержит множество из линейно зависимых столбцов, а любое множество из столбцов матрицы линейно независимо.

Доказательство: Рассмотрим линейный код, задаваемый проверочной матрицей размерности в виде

где – –компонентный вектор-столбец проверочной матрицы. Тогда, на основании теоремы 6.3.1, найдется хотя бы один кодовый вектор, имеющий ненулевых компонент, для которого

где – позиции ненулевых компонент вектора . Таким образом, среди столбцов матрицы всегда найдутся таких, которые при ненулевых скалярах дают нулевую сумму, а значит, являются линейно зависимыми.

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

где – номера столбцов проверочной матрицы, вошедшие в упомянутое множество. Построим вектор , в котором , а остальные позиций заполнены нулями. Очевидно, что

следовательно, , т.е. является кодовым вектором. Последнее означает, что кодовое расстояние не более , поскольку , что противоречит условию теоремы. Таким образом, любое множество из столбцов матрицы линейно независимо.

Рассматривая структуру матриц и можно вынести следующее заключение. Обе матрицы состоят из множества линейно независимых векторов, поскольку наличие в их структуре единичной матрицы делает невозможным существование линейной комбинации строк с нулевой суммой. Следовательно, каждая из матриц может рассматриваться как базис некоторого линейного пространства. Более того, каждое из этих пространств является подпространством векторного пространства, состоящего из всех векторов длины . Учитывая сказанное выше, можно их «поменять ролями» и использовать в качестве порождающей, а – проверочной матрицы некоторого другого кода. Коды, связанные с таким преобразованием, называются дуальными друг другу. Таким образом, если исходным являлся кодом, то дуальным ему будет код.

Кроме того, из заданного кода можно получить новый, обладающий теми же параметрами, если в каждом кодовом слове поменять местами символы, стоящие на одинаковых позициях. Получаемый по такому алгоритму код называется эквивалентным. Порождающие матрицы и эквивалентных кодов связаны друг с другом элементарным преобразованием. Так обмен символами на одинаковых позициях кодовых слов (или, что то же самое, перестановка координат кода) эквивалентна перестановке столбцов матрицы . Следовательно, два кода эквивалентны тогда и только тогда, когда их порождающие матрицы получаются одна из другой посредством перестановки столбцов, либо в результате элементарных операций над строками.

Любой код с кодовым расстоянием , удовлетворяющим соотношению (6.8), называется кодом с максимальным расстоянием .

Замечание. Граница Синглтона (6.8) бесполезна для двоичных кодов, поскольку значительно уступает в точности границам Плоткина и Хэмминга. Однако, она играет значительную роль в случае –ичных кодов.

Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с g(х) = 1+х+х*3

Циклические коды

Циклические коды - это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей кодов Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Одним из классов циклических кодов, способность исправлять многократные ошибки, являются коды БЧХ. Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров. Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова:

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) степени r = n-k, являющийся сомножителем двучлена x n +1, и их корней. Кроме того, вводятся понятия полинома исходного сообщения. Для этих полиномов, представляющих собой, по существу, альтернативную запись чисел в двоичной системе счисления, определяются операции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все эти операции выполняются по модулю 2.

Кодовые слова представляются в виде многочленов:

Основные параметры циклических кодов

Длина кода - n; Длина информационной последовательности - k; Длина проверочной последовательности - r=n-k; Кодовое расстояние кода - d 0 ; Скорость кода - R=k/n; Избыточность кода - R?; Вероятность обнаружения ошибки (искажения) - Р ОО; Вероятность не обнаружения ошибки (искажения) - Р НО.- коэффициенты из поля GF(q).

Основные понятия и определения

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга. Кодовое расстояние кода - это наименьшее расстояние Хэмминга между различными парами кодовых слов. Основные зависимости между кратностью обнаруживаемых ошибок t 0 , исправляемых ошибок t u , исправлением стираний t c и кодовым расстоянием d 0 кода:

Стиранием называется "потеря" значения передаваемого символа в некоторой позиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим. Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q m -1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена x n +1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x). Многочлен ошибок степени не более (n-1) определяется из выражения

где - многочлены, отображающие соответственно принятое (с ошибкой) и переданное кодовые слова. Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам. Синдромный многочлен, используемый при декодировании циклического кода, определяется как остаток от деления принятого кодового слова на порождающий многочлен, т.е.

Следовательно, синдромный многочлен зависит непосредственно от многочлена ошибок е(х). Это положение используется при построении таблицы синдромов, применяемой в процессе декодирования. Эта таблица содержит список многочленов ошибок и список соответствующих синдромов, определяемых из выражения (см. таблицу 4).

В процессе декодирования по принятому кодовому слову вычисляется синдром, затем в таблице находится соответствующий многочлен е(х), суммирование которого с принятым кодовым словом дает исправленное кодовое слово, т.е.

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по модулю 2, а затем по модулю x n +1, если степень результата превышает степень (n-1). Примеры.

Допустим, что длина кода n=7, то результат приводим по модулю x 7 +1.

При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления. Поэтому рекомендуется более простой способ деления, используя не многочлены, а только его коэффициенты (вариант 2 в примере).

Циклический код может быть задан порождающей g(x) и проверочной h(x) матрицами. Для построения достаточно знать порождающий и проверочный многочлены. Для не систематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т. е. путем их умножения на х.

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

Существуют специальные таблицы по выбору порождающего многочлена в зависимости от предъявляемых требований к корректирующим возможностям кода. Однако у каждого циклического кода имеются свои особенности формирования порождающего многочлена. Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения порождающего многочлена.

В системах связи возможны несколько стратегий борьбы с ошибками:

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков - этот подход применяется в основном на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков - такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• исправление ошибок (англ. forward error correction ) применяется на физическом уровне.

Коды обнаружения и исправления ошибок

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

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

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

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

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

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n ,k ) . При этом число называется скоростью кода .

Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных , такой код называется систематическим , иначе несистематическим .

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из k информационных бит сопоставляется n бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

• способность исправлять как можно большее число ошибок,
• как можно меньшая избыточность,
• простота кодирования и декодирования.

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

Практически все используемые коды являются линейными . Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую легкость кодирования и декодирования.

Линейные пространства

Порождающая матрица

Это соотношение устанавливает связь между векторами коэффициентов и векторами . Перечисляя все векторы коэффициентов можно получить все векторы . Иными словами, матрица G порождает линейное пространство .

Проверочная матрица

Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей .

Пусть - ортогональное подпространство по отношению к C , а H - матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

Свойства и важные теоремы

Минимальное расстояние и корректирующая способность

Коды Рида-Соломона

Преимущества и недостатки линейных кодов

Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок , их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока. Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.

Оценка эффективности

Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Граница Хемминга и совершенные коды

Пусть имеется двоичный блоковый (n ,k ) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга ):

Коды, удовлетворяющие этой границе с равенством, называются совершенными . К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.

Энергетический выигрыш

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

Wikimedia Foundation Википедия

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Циклический код … Википедия

Циклический код линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и… … Википедия

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

- (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передаче информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью является малая плотность значимых… … Википедия

Код с малой плотностью проверок на чётность (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передачи информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью… … Википедия

структура - (framework): Логическая структура для классификации и организации сложной информации .

Порождающей матрицей линейного -кода называется матрица размера , строки которой – его базисные векторы.

Например,

является порождающей матрицей кода из двух слов {000, 011}.

является порождающей для кода В из примера 6.3.

Мы знаем, что кодовые слова – линейные комбинации базисных векторов, т.е. строк матрицы . Это означает, что слова могут быть получены умножением вектора на матрицу. Итак, сообщение записывается в виде вектора и соответствующее сообщению кодовое слово вычисляется по формуле

Тем самым вектор из бит превращается в последовательность из двоичных символов, передаваемых по каналу или записываемых в память запоминающего устройства.

Обратимся к задаче декодирования.

Предположим, что для некоторого двоичного вектора все кодовые слова -кода , удовлетворяют тождеству

в котором обозначает скалярное произведение векторов и .

Про такой вектор мы скажем, что он ортогонален. Найдя такой вектор, мы могли бы проверять с помощью тождества (6.2), является ли принятая из канала последовательность кодовым словом.

Заметим, что (6.2) справедливо для всех кодовых слов, если оно справедливо для базисных векторов, т.е. если

где верхний индекс Т обозначает транспонирование.

Чем больше таких «проверок» мы найдем, тем, по-видимому, больше ошибок сумеем обнаружить и исправить.

Упражнение 6.4 . Докажите, что проверки образуют линейное пространство.

Это пространство назовем пространством, ортогональным линейному коду или проверочным пространством .

Упражнение 6.5 . Найдите размерность линейного пространства проверок.

Чтобы выполнить последнее упражнение, нужно заметить, что в матрице имеется ровно линейно независимых столбцов. Не больше (почему?) и не меньше (почему?). Зафиксируем список номеров этих столбцов и назовем этот набор чисел информационной совокупностью . Чуть позже смысл этого названия станет яснее. Выберем произвольно значения вектора на позициях, не входящих в информационную совокупность. Какими должны быть значения на позициях информационной совокупности, чтобы выполнилось (6.3)? Чтобы ответить на этот вопрос, придется решить систему линейных уравнений, причем система имеет единственное решение.

Следствием этих рассуждений является теорема

Теорема. Размерность проверочного пространства линейного -кода равна .

Базис проверочного пространства запишем в виде матрицы

называемой проверочной матрицей кода.

Проверочная и порождающая матрицы связаны соотношением

Из этого соотношения мы видим, что для любого кодового слова имеет место

Это тождество можно использовать как критерий принадлежности произвольной последовательности коду, т.е. для обнаружения ошибок.

Зная, можно найти . Для того, чтобы понять, как это сделать, заметим, что один тот же код можно задать разными порождающими матрицами, выбирая по-разному базис пространства. Больше того, заменив в любую строку на любую линейную комбинацию этой строки с другими строками, мы получаем новую порождающую матрицу того же кода.

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

Понятно, что для каждого кода найдется эквивалентный, для которого первые позиций образуют информационную совокупность, т.е. первые столбцов образуют невырожденную матрицу размера . Заменяя строки линейными комбинациями строк (метод Гаусса) полученную матрицу можно привести к виду

где – единичная матрица порядка , а – некоторая матрица размера .

Матрица вида (6.6) называется порождающей матрицей, приведенной к систематическому виду , а соответствующий код называется систематическим . Кодирование для систематического кода немного проще, чем для кода общего вида:

, (6.7)

т.е. в кодовом слове первые позиций – просто копия информационной последовательности , а остальные (проверочных) позиций получаются умножением информационного вектора на матрицу размера , что иногда существенно меньше, чем . Соответственно, и информация о систематическом коде занимает существенно меньше памяти, чем информация о линейном коде общего вида.

Для систематического кода с порождающей матрицей в форме (6.6) проверочная матрица может быть вычислена по формуле

Упражнение 6.6 . Проверьте (6.7). Подсказка: для этого нужно подставить (6.8) и (6.6) в (6.4).

Как найти проверочную матрицу для несистематического кода?

Очень просто. Нужно привести матрицу к систематическому виду и воспользоваться (6.7). Если первые столбцов порождающей матрицы образуют невырожденную подматрицу (первые позиций образуют информационную совокупность), то для приведения к систематической форме достаточно таких операций как перестановка строк и замена строк линейными комбинациями строк. Если нет – нужно будет сначала найти информационную совокупность и перенумеровать позиции так, чтобы первые позиции стали информационными.