Что такое порождающая матрица. Порождающая и проверочная матрицы

Линейный систематический блочный код может быть также определён проверочной матрицей H , обладающей следующими свойствами. Если некоторая последовательность u является кодовым словом , то , т.е. проверочная матрица H ортогональна любой кодовой последовательности данного кода .

Проверочная матрица имеет размерность (n -k )×n и следующую структуру:

, (3.4)

проверочная часть единичная

матрицы подматрица

где
– транспонированная проверочная подматрица порождающей матрицы G ( k x n ) ;
- единичная подматрица.

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

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

.

Пусть принята последовательность с =(1011001). Проверим, является ли она кодовым словом:

=(1011001)
=(1 0 1 ) ≠ 0 .

Следовательно, последовательность (1011001) не является кодовым словом данного кода.

^

3.7 Синдром и обнаружение ошибки линейным блочным кодом

Пусть x =(х 1 , х 2 , …, х n ) – кодовое слово , переданное по каналу с помехами;

y =(y 1 , y 2 , …, y n ) – принятая последовательность, которая в силу влияния помех может отличаться от переданной.

Для описания возникающих в канале ошибок используется вектор ошибок е= (e 1 , e 2 , …, e n ) , который представляет собой двоичную последовательность длиной n с единицами в тех позициях, в которых произошла ошибка.

Например, вектор ошибок е =(0 0 0 1 0 0 0 ) означает однократную ошибку в четвертом бите, е =(1 1 0 0 0 0 0 ) – двукратную ошибку в первом и втором битах.

При передаче кодового слова x по каналу с шумом принятая последовательность будет иметь вид

y = x +е , (3.5)

где x - переданное кодовое слово; e – вектор, описывающий ошибки в канале.

Например, x =(0 0 0 1 0 0 0 ), e =(0 0 0 1 0 0 0 ). Тогда y =(0 0 0 0 0 0 0 ).

Чтобы проверить наличие ошибок в принятом векторе y , декодер вычисляет следующую (n -k ) - последовательность

S =(S 1 , S 2 , … S n - k )=y 
, (3.6)

где y – принятая кодированная последовательность; – проверочная матрица данного кода.

При этом вектор y является кодовым словом тогда, когда S =(0 0 … 0 ), и не является кодовым словом данного кода , если S ≠0.

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

Некоторые сочетания ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово x под влиянием помех превратилось в другое кодовое слово этого же кода, тогда синдром S =y ×
=0 , и декодер ошибки не обнаружит .

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

Пусть x =(х 1 , х 2 , …, х 7 ) – принятая кодированная последовательность. Тогда

S =x 
=(х 1 ,х 2 ,… , х 7 )×
=((x 1 +x 3 +x 4 +x 5 ) , (x 1 +x 2 +x 3 +x 6 ) , (x 2 +x 3 +x 4 +x 7 ) ).

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

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков - этот подход применяется в основном на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков - такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• исправление ошибок (англ. 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): Логическая структура для классификации и организации сложной информации .

Так как, согласно определению, линейный (л, /с)-код длины п над GF(q) является подпространством GF k (q) векторного пространства GF n (q), то должно существовать ортогональное дополнение подпространства GF k (q) линейного кода (см. подпараграф 1.7.1).

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

Условие (2.10) позволяет проверить принадлежность произвольной л-после- довательности элементов GF(q) определенному g-ичному линейному коду.

Если вектор линейного кода имеет вес Хэмминга шо, то это значит, что в кодовом слове присутствует шо ненулевых символов (согласно определению веса Хэмминга, см. подпараграф 2.1.4). Тогда, согласно правилам умножения матриц, произведение вектора с со значением шо веса Хэмминга на матрицу Н т соответствует линейной комбинации шо столбцов матрицы Н. При этом равенство (2.10), очевидно, имеет место тогда и только тогда, когда шо столбцов матрицы Н линейно зависимы.

Таким образом, условием существования во множестве кодовых слов некоторого линейного кода кодового слова с весом Хэмминга шо является наличие в матрице Н линейно зависимых столбцов в количестве шо. Из этого следует также, что линейный код имеет минимальный вес (см. подпараграф 2.1.4) не менее некоторого значения шо тогда и только тогда, когда любые шо - 1 столбцов матрицы Н линейно независимы. Следовательно, согласно неравенству (2.6), для того чтобы найти линейный код с минимальным весом шо, исправляющий t ошибок, достаточно найти матрицу Н, у которой не менее чем шо - 1 = 2-t любых столбцов были линейно независимы.

Рассмотрим подробнее матрицу Н. Как было сказано выше, строками матрицы Н являются базисные векторы ортогонального дополнения линейного кода. Если множество л-последовательностей образует подпространство размерности к, то ортогональное дополнение этого подпространства будет иметь размерность п-к (см. подпараграфы 1.7.1 и 1.7.2). Подпространство размерности п - к образуют любые п-к базисных векторов. Поэтому матрица Н должна содержать п-к линейно независимых строк.

Так как матрицы G и Н принадлежат одному пространству л-последовательностей, то число столбцов матрицы Н равно числу столбцов матрицы G. Таким образом, матрица Н имеет размер (л - к) х л. Все столбцы матрицы Н, как уже было сказано, образуют линейно независимые группы по 2t столбцов.

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

Результатом произведения матриц G размера к* ли Н т размера л х (п-к) является матрица размера к х (л - к), состоящая из нулевых элементов.

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

Согласно соотношению (2.4), порождающая матрица систематического линейного кода состоит из единичной матрицы порядка к и матрицы проверочных символов размера к х (л - к), которая, в свою очередь, является расширением единичной матрицы. Как показано в приложении 1, умножение двух матриц можно выполнить, разделив перемножаемые матрицы на матрицы меньшего размера (блоки) с последующим умножением отдельных блоков перемножаемых матриц. Тогда для матриц G и Н можно записать:

Число столбцов в блоках А и В матрицы Н 7 должно соответствовать числу строк в блоках Ек и Р матрицы G (по правилам умножения матриц). Результирующая матрица должна иметь размер /с * (л - к). Очевидно, что если положить А = -Р и В = Ел_/с, то матрица Н будет удовлетворять уравнению (2.11).

Таким образом, матрица Н т является расширением матрицы -Р и помимо матрицы - Р матрица Н содержит единичную матрицу порядка п - к. Матрица Н т является результатом транспонирования матрицы Н.

Результатом повторного транспонирования матрицы является исходная матрица. Поэтому матрица Н может быть получена путем транспонирования матрицы Н т. Так как для любого элемента а поля GF[ 2) справедливо а = - а, то для двоичного линейного кода справедливо Р--Р.

Матрица Н двоичного линейного кода будет иметь следующий вид:

Матрица Р, входящая в состав матрицы G и содержащая проверочные символы, может быть получена путем транспонирования матрицы Р т, входящей в состав матрицы Н.

Таким образом, построение линейного кода сводится к поиску матрицы Н. По заданной матрице Н легко найти матрицу G.

Пример 2.1.4. Рассмотрим построение двоичного линейного кода - кода над GF(2), исправляющего одну ошибку кодового слова с информационной последовательностью размера к = 3 бита.

Согласно соотношению (2.9), для кода с максимальным расстоянием r = 2-t = = 2. Тогда л = /с + г = 3 + 2 = 5. Однако, как будет показано в следующем подпараграфе, линейный двоичный (5,3)-код не способен исправлять одиночную ошибку кодового слова. При этом минимальное число избыточных символов для данного случая г = 3, а рассматриваемый код - двоичный линейный (6,3)-код.

Таким образом, в данном случае матрица Н содержит проверочную матрицу размера /сх(л-/с) = 3*3и единичную матрицу порядка п-к= 3.

Все столбцы матрицы Н должны образовывать линейно независимые группы по два столбца и линейно зависимую группу из трех столбцов. Такому условию отвечают, например, последовательности 101, 110 и 011 над GF(2). Указанные последовательности образуют столбцы матрицы Р т, входящей в состав матрицы Н. Остальные элементы матрицы Н соответствуют единичной матрице порядка 3:

Дописав к единичной матрице порядка 3 матрицу Р, полученную транспонированием матрицы Р т, получим матрицу G:

Рассмотрим теперь процесс формирования и структуру кодового слова двоичного линейного (6, 3)-кода с порождающей матрицей вида (2.12):

Три первых символа кодового слова (ci - Сз) содержат информационные символы (/ 1 - г"з), сформированные в результате умножения матрицы информационной последовательности i на единичную матрицу порядка 3, входящую в состав матрицы G. Оставшиеся символы кодового слова (С4 - Сб) содержат проверочные символы (t^ - tz), полученные в результате умножения матрицы информационной последовательности на матрицу проверочных символов Р, также входящую в состав матрицы G.

Нетрудно проверить, что в случае (6, 3)-кода из примера 2.1.4 минимальное число ненулевых символов среди всех кодовых слов равно трем (кодовые слова 001101, 010011,100110 и 111000). Таким образом, d* = 3 и, согласно соотношению (2.5), код должен исправлять одну ошибку кодового слова. Как будет показано в следующем подпараграфе, это действительно так.

Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с 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-кратных ошибок.

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

1.2.2. Проверочная матрица линейного кода

Поскольку линейный код V является подпространством, то для него существует ортогональное дополнение (или нулевое подпространство ). Ортогональное дополнение V " (n , k ) - кода V состоит из всех векторов длины n , ортогональных к каждому вектору v Î V . Векторы и называются ортогональными , если их скалярное произведение равно 0. Для двоичных векторов скалярное произведение равно сумме произведений соответствующих компонент. Например, скалярное произведение (00101, 10110) векторов 00101 и 10110 есть вектор 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как линейный код. Множество V " - называется кодом, дуальным или двойственным к V.

Ортогональное дополнение V " (n , k ) - кода V имеет размерность (n - k) ; соответственно любой его базис состоит из (n -k) векторов. Порождающая матрица Н ортогонального дополнения называется проверочной матрицей кода V .

Т. к проверочная матрица состоит из базисных векторов ортогонального дополнения, то двоичный вектор с является кодовым словом, если и только если сН T = 0. Таким образом, проверка на наличие ошибок при передаче кодового слова сводится к умножению двух матриц вместо перебора всех кодовых слов. Умножение матриц, размерность которых составляет несколько тысяч, при современной вычислительной технике выполняется очень быстро.

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

из предыдущего раздела порождает следующую систему уравнений:

Основная матрица системы совпадает с матрицей G . Неизвестные x 1 , x 2 и x 3 , для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x 4 и x 5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:

и

Из первой системы получаем x 1 = 1, x 2 = 0, x 3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x 1 = 1, x 2 = 1, x 3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

.

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

Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема 1.3. Каждое не нулевое кодовое слово имеет вес не менее w , тогда и только тогда, когда любая совокупность из w столбцов матрицы Н

Доказательство. Для любого кодового слова с выполняется равенство сН T = 0. Пусть кодовое слово с имеет вес u . Исключим из рассмотрения нулевые компоненты вектора. Полученное равенство будет соотношением линейной зависимости u столбцов из Н . Следовательно, Н содержит множество из u линейно зависимых столбцов. Таким образом, в коде существует слово веса u , если и только если в матрице Н существует совокупность из u линейно зависимых столбцов. Таким образом, все не нулевые слова кода имеют вес не меньше w w -1 столбцов матрицы Н является линейно независимой.

Как следствие теорем 1.1 и 1.3 имеет место следующее утверждение:

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

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