Порождающей матрицей линейного -кода называется матрица размера , строки которой – его базисные векторы.
Например,
является порождающей матрицей кода из двух слов {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). Если первые столбцов порождающей матрицы образуют невырожденную подматрицу (первые позиций образуют информационную совокупность), то для приведения к систематической форме достаточно таких операций как перестановка строк и замена строк линейными комбинациями строк. Если нет – нужно будет сначала найти информационную совокупность и перенумеровать позиции так, чтобы первые позиции стали информационными.
В системах связи возможны несколько стратегий борьбы с ошибками:
Корректирующие коды - коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех , а также при её хранении.
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
С кодами, исправляющими ошибки , тесно связаны коды обнаружения ошибок . В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.
В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).
По способу работы с данными коды, исправляющие ошибки делятся на блоковые , делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и сверточные , работающие с данными как с непрерывным потоком.
Пусть кодируемая информация делится на фрагменты длиной 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): Логическая структура для классификации и организации сложной информации .
Любой циклический (n, k ) – код может быть задан в соответствии с определением 2, порождающим многочленом g(x) или проверочным многочленом .
Знание этих многочленов позволяет построить порождающую матрицу и матрицу проверок. Для циклического (n, k ) – кода существует простой способ нахождения k линейно независимых кодовых комбинаций, образующих порождающую матрицу . Этот способ состоит в следующем. Записывается порождающий многочлен g(x) . В соответствии с определением 2 комбинация, соответствующая порождающему многочлену, принадлежит циклическому (n, k ) – коду. В соответствии с определением 1 циклические сдвиги комбинации, соответствующей g(x) , также должны принадлежать этому же коду. Алгебраически сдвиг соответствует умножению кодовой комбинации на х . Так как степень g(x) равна n-k , то подобным образом мы можем получить кодовые комбинации
Легко проверить, что эти кодовые комбинации линейно независимы, хотя бы потому, что степени всех этих многочленов различны, поэтому данный набор многочленов может быть использован в качестве :
.
Путем элементарных преобразований эта матрица может быть приведена к канонической форме.
Аналогичным образом по проверочному многочлену можно построить матрицу проверок
.
Пример 6.4. Для циклического (7,4) – кода с порождающим многочленом 
(см. пример 6.3.) построить порождающую матрицу.
Следовательно, порождающая матрица для данного кода имеет вид:
Полученные результаты и рассуждения относительно алгебраической структуры циклических кодов, приведенные в разделе 6.2, позволяют подметить одно важное свойство циклических кодов, определенное их циклической структурой.
Свойство 6.1. Произведение кодовой комбинации циклического кода на произвольный многочлен дает кодовую комбинацию этого же циклического кода.
Действительно , а любое произведение такого вида равно нулю, т.е. принадлежит кодовому подпространству (раздел 6.2).
Более элементарное доказательство:
Полученная сумма есть сумма циклических сдвигов кодовых комбинаций, что по свойству замкнутости группового кода должно дать комбинацию того же циклического кода.
При описании циклических кодов следует учитывать специфику действий над многочленами, по сравнению с векторами и, в частности, тот факт, что умножение многочленов не совпадает со скалярным умножением векторов, отображающих эти многочлены. Однако в классе вычетов многочленов по модулю между этими понятиями существует весьма тесная связь. Пусть имеется вектор и соответствующий ему многочлен , а также вектор и соответствующий ему многочлен . Будем считать многочлены и ортогональными, если выполнено условие .
Коэффициент при х
в произведении 
равен
Слагаемые, содержащие , появляются вследствие слагаемых в произведении , которые содержат . Но так как , т.е. , то . Равенство для можно представить в виде скалярного произведения:
В этом произведении первый вектор соответствует а(х) . Второй вектор содержит коэффициенты b(х) , расположенные в обратном порядке и сдвинутые циклически на j +1 элемент вправо.
Таким образом, если произведение равно нулю, то вектор, соответствующий многочлену а(х) , ортогонален вектору, соответствующему многочлену b(х) , компоненты которого расположены в обратном порядке, и кроме того каждому циклическому сдвигу этого вектора. Верно также и обратное утверждение. Если вектор ортогонален вектору и каждому циклическому сдвигу этого вектора, то
Учитывая эту специфику необходимо при матричном описании кода коэффициенты матрицы проверок записывать в обратном порядке. В этом случае будет выполнено условие
Пример 6.5. Построить матрицу проверок для циклического (7,4) – кода из предыдущего примера.m , являющихся сомножителями двучленов и не являющихся сомножителями никаких двучленов меньшей степени. Корни этих многочленов имеют порядок 2 m -1, т.е они являются примитивными элементами поля GF(2 m). Это означает, что порождающий многочлен кода Хэмминга порождает поле GF(2 m).
Условимся в любом циклическом коде первые n-k
элементов кодовой комбинации, то есть коэффициенты при 
использовать в качестве проверочных элементов, а последние k
элементов, то есть коэффициенты при 
, - в качестве информационных (рис. 6.0).
a 0 a, ….., a n-1 = a 0 x 0 +a 1 x 1 + …. + a n-1 x n+1
x 0 x 1 x 2 x n-k-1 x n-k x n-2 x n-1
В системах связи возможны несколько стратегий борьбы с ошибками:
Корректирующие коды - коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех , а также при её хранении.
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
С кодами, исправляющими ошибки , тесно связаны коды обнаружения ошибок . В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.
В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).
По способу работы с данными коды, исправляющие ошибки делятся на блоковые , делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и сверточные , работающие с данными как с непрерывным потоком.
Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n ,k ) . При этом число называется скоростью кода .
Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных , такой код называется систематическим , иначе несистематическим .
Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из k информационных бит сопоставляется n бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:
Нетрудно видеть, что приведенные требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.
Практически все используемые коды являются линейными . Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую легкость кодирования и декодирования.
Это соотношение устанавливает связь между векторами коэффициентов и векторами . Перечисляя все векторы коэффициентов можно получить все векторы . Иными словами, матрица G
порождает линейное пространство .
Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей .
Пусть - ортогональное подпространство по отношению к C , а H - матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:
.
Пусть имеется двоичный блоковый (n ,k ) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга ):
.
Коды, удовлетворяющие этой границе с равенством, называются совершенными . К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.
При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенных системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.
Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.
проверочная матрица - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN check matrix … Справочник технического переводчика
В области математики и теории информации линейный код это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… … Википедия
Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Циклический код … Википедия
Циклический код линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и… … Википедия
- (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передаче информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью является малая плотность значимых… … Википедия
Код с малой плотностью проверок на чётность (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передачи информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью… … Википедия
Коды Рида Соломона (англ. Reed–Solomon codes) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… … Википедия
Линейные коды обладают следующим свойством:
Из всего множества 2 k разрешенных кодовых слов, образующих линейную группу, можно выделить подмножества из k слов, обладающих свойством линейной независимости.
Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования (с помощью линейного выражения) любых других слов, входящих в это подмножество.
В то же время любое из разрешенных кодовых слов можно получить путем суммирования определенных линейно-независимых слов.
Таким образом, построение кодовых комбинаций линейного кода связано с линейными операциями. Для выполнения таких операций удобно пользоваться хорошо разработанным аппаратом матричных вычислений.
Для образования n -разрядных кодовых слов из k- разрядных кодируемых слов (кодирования) используют матрицу, которая называется образующей(порождающей).
Образующая матрица получается путем записи в столбец k линейно-независимых слов.
Обозначим кодируемую информационную последовательность X и будем записывать ее в виде матрицы-строки ||X|| размерностью 1* k , например:
||X||=||11001||, где k=5 .
Один из способов построения образующей (порождающей) матрицы следующий: Она строится из единичной матрицы ||I|| размерностью k*k и приписанной к ней справа матрицы добавочных (избыточных) разрядов ||МДР|| размерности k*r .
где при k =4
Такая структура ОМ обеспечивает получение систематического кода.
Порядок построения матрицы МДР будет рассмотрен ниже.
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||Х|| на образующую матрицу ||ОМ||:
Умножение выполняется по правилам матричного умножения: (ТАК наТАК)
Надо только помнить, что сложение здесь ведется по модулю 2.
допустим, образующая матрица
||ОМ||= 0010 011
и вектор-строка информационной последовательности
Так как множимая матрица имеет всего одну строку, умножение упрощается. В этом случае следует поставить в соответствие строкам образующей(порождающей) матрицы ||ОМ|| разряды матрицы информационной последовательности ||X|| и сложить те строки образующей(порождающей) матрицы, которые соответствуют единичным разрядам матрицы ||Х||.
Заметим, что ||KC|| = ||X, ДР||,
где ||X||- информационная последовательность (т.к. умножается на единичную матрицу ||I|| ),
а ||ДР|| - добавочные разряды, зависящие от матрицы добавочных разрядов ||МДР|| :
|| ДР ||= || Х || * || МДР||
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Искажение можно описать с помощью следующей формулы:
|| ПКС || = ||КС || + ||ВО ||,
где ||ВО|| - вектор ошибки - матрица-строка размерностью 1* n , с 1 в тех позициях, в которых произошли искажения.
Декодирование основано на нахождении так называемого опознавателя или синдрома ошибки -матрицы-строки ||ОП|| длиной r разрядов (r - количество добавочных или избыточных разрядов в кодовом слове).
Опознаватель используется для нахождения предполагаемого вектора ошибки.
Опознаватель находят по следующей формуле:
||ОП|| = ||ПКС||* ||ТПМ||,
где ||ПКС||- принятое и, возможно, искаженное кодовое слово;
||ТПМ||,- транспонированная проверочная матрица, которая получается из матрицы добавочных разрядов ||МДР|| путем приписывания к ней снизу единичной матрицы:
Пример ||ТПМ||:
Поскольку ||ПКС|| = ||КС|| + ||BO||, последнюю формулу можно записать в виде:
||ОП|| = ||КС|| * ||ТПМ||+||ВО|| * ||ТПМ||.
Рассмотрим первое слагаемое.
||КC|| - матрица-строка, причем первые k разрядов - информационные.
Докажем теперь, что произведение кодового слова ||КС|| на ||ТПМ|| приводит к получению нулевой матрицы ||0||.
Поскольку ||КС|| - матрица-строка, возможен упрощенный порядок умножения матриц, рассмотренных выше.
Следовательно, первое слагаемое в
||ОП|| = ||КС|| * ||ТПМ|| + ||ВО|| * ||ТПМ||
всегда равно нулю и опознаватель полностью зависит от вектора ошибки ||ВО||.
Если теперь подобрать такую проверочную матрицу ТПМ , а значит и МДР , чтобы разным векторам ошибки соответствовали разные опознаватели ОП, то по этим опознавателям можно будет находить вектор ошибки ВО, а значит и исправлять эти ошибки.
Соответствие опознавателей векторам ошибки находится заранее путем перемножения векторов исправляемых ошибок на ТПМ;
Таким ооразом, способность кода исправлять ошибки целиком определяется ||МДР||. Для построения МДР для кодов, исправляющих однократные ошибки нужно в каждой строке МДР иметь не менее 2-х единиц. При этом также необходимо иметь хотя бы одно различие между двумя любыми строчками МДР .
Полученный нами код неудобен тем, что опознаватель, хотя и связан однозначно с номером искаженного разряда, как число не равен ему. Для поиска искаженного разряда нужно использовать дополнительную таблицу соответствия между опознавателем и этим номером. Коды, в которых опознаватель как число определяет позицию искаженного разряда, были найдены и получили название кодов Хэмминга .
Построение МДР для случая исправления многократных ошибок значительно усложняется. Разными авторами были найдены различные алгоритмы построения ||МДР || для этого случая, а соответствующие коды называются именами их авторов.
