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

06.04.2019

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

Например,

является порождающей матрицей кода из двух слов {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). Если первые столбцов порождающей матрицы образуют невырожденную подматрицу (первые позиций образуют информационную совокупность), то для приведения к систематической форме достаточно таких операций как перестановка строк и замена строк линейными комбинациями строк. Если нет – нужно будет сначала найти информационную совокупность и перенумеровать позиции так, чтобы первые позиции стали информационными.

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

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

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

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

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

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

Линейный блочный (л, /с)-код полностью определяется матрицей G размером к х п с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом.

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

Например, для простейшего (4, 3)-кода с проверкой на четность порождающая матрица будет иметь вид:

Пусть т - (т 1; т 2 , ..., т к) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.

Тогда соответствующим ему кодовым словом U будет

С учетом структуры матрицы G символы кодового слова и будут такими:

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

Например, если входная последовательность кодера т = = (10 1), то с применением порождающей матрицы код будет построен так:

8 Командир послал трех разведчиков по первой дороге, трех - по второй, двух - по третьей, по четвертой пошел сам. Составить порождающую матрицу такого кода.

Ответ: по сюжету задачи сообщение, полученное командиром лично, не может быть искаженным. Поэтому ограничимся исследованием информации, передаваемой бойцами. В группе, отправившейся по одной из дорог, каждый боец должен доложить командиру либо об обнаружении объекта (обозначим такой доклад «1»), либо об отсутствии объекта («0»). При отсутствии искажений доклады каждого бойца из одной и той же группы должны совпадать. Следовательно:

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

Определенный таким образом код называется линейным блочным систематическим (п, /cj-кодом с обобщенными проверками на четность.

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

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

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

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

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

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

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

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

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

Пусть кодируемая информация делится на фрагменты длиной 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) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… … Википедия

Любой циклический (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

Пусть x1, x2, ..., xk означают слово из k информационных битов на входе кодера, кодируемое в кодовое слово C размерности n битов:

вход кодера: X =[x 1, x 2, ...,xk ]

выход кодера: C =[c 1, c 2, ..., cn ]

Пусть задана специальная порождающая матрица G n , k ,

задающая блочный код (n ,k ).

Строки матрицы G n , k должны быть линейно независимы.

Тогда разрешенная кодовая комбинация C , соответствующая кодируемому слову X :

C =x 1 g 1 + x 2 g 2 + ... + x k g k .

Систематическая (каноническая) форма порождающей матрицы G размером k xn :

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

Проверочная матрица H n , k имеет r xn элементов, причем справедливо:

C xH T = 0.

Это выражение используется для проверки полученной кодовой комбинации. Если равенство нулю не выполняется, то получаем матрицу-строку ||c 1 , c 2 , ..., c r ||, называемую синдромом ошибки.

Код Хэмминга. Корректирующая и обнаруживающая способности. Правила выбора соотношения между длиной кодового слова и числом информационных битов. Формирование порождающей и проверочной матриц кода Хэмминга. Толкование синдрома ошибки

Рассмотрим код Хэмминга с кодовым расстоянием d =3, позволяющий исправлять одиночные ошибки (d =2q max +1).

Число разрешенных кодовых комбинаций для кода с d =3, для кода Хэмминга строго равно 2 n /(n +1). Первые k разрядов кодовых комбинаций кода используются в качестве информационных и их число равно

k = log 2 (2 n /(n +1)] = n – log 2 (n +1).

Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, которые и определяют соответствующие коды Хэмминга: (3,1)-код, (7,4)-код, (15,11)-код и т.д. (всегда n =2 w ‑1).

Проверочная матрица H кода Хэмминга (r =n-k строк и n столбцов): для двоичного (n,k)-кода n=2 w -1 столбцов состоят из всех возможных двоичных векторов с r=n-k элементами, исключая вектор со всеми нулевыми элементами .

Легко проверить, что G xH T = 0 (нулевая матрица размером k xr элементов).

Пример. Проверим работу кода при передаче сообщения X =1011. Передаваемая кодовая комбинация будет сформирована в виде линейной комбинации (сложения по модулю 2) строк № 1, 3, 4 матрицы G 7,4:

Предположим, что на передаваемое кодовое слово C воздействовала ошибка 0000100, что привело к получению на приемной стороне слова C "=10111 10.

Тогда при перемножении C" на проверочную матрицу H T получаемматрицу-строку синдрома ошибки, которая соответствует тому столбцу проверочной матрицыH с номером бита, содержащего ошибку.

Сравнивая полученный синдром со строками H T , получаем, что ошибочен бит № 5 слева.

Декодер Хэмминга может работать в двух взаимоисключающих режимах:

Режим исправления (коррекции) ошибок (т.к. d min =3, то он позволяет исправлять одиночные ошибки);

Режим обнаружения ошибок (т.к. d min =3, то он обнаруживает ошибки кратности q £2). Если синдром не равен 0, то декодер выдает сигнал ошибки.

Если в принятом кодовом слове имеются 2 ошибки, а декодер работает в режиме коррекции, то он не сможет по синдрому определить, произошла ли одна ошибка или две, и выполнит неправильную коррекцию кодового слова.

Расширенный код Хэмминга. Режимы работы декодера, корректирующая и обнаруживающая способности. Формирование кодового слова. Формирование проверочной матрицы расширенного кода Хэмминга. Толкование синдрома ошибки

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

Длины кодов увеличиваются с 2 w -1 до 2 w , что удобно с точки зрения передачи и хранения информации;

Минимальное расстояние d min расширенных кодов Хэмминга равно 4, что дает возможность обнаруживать (!) 3-кратные ошибки.

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

Рассмотрим расширение (7,4,3)-кода Хэмминга.

Каждый кодовый вектор C a получается из кодового вектораc путем добавления дополнительного разряда проверки на четностьC a = (c 1 , ..., c 7, c 8), где .

Проверочная матрица H (8,4)-кода получается из проверочной матрицы (7,4)-кода в два приема:

К матрице (7,4)-кода дописывается нулевой столбец;

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

Получаем:

При синдромном декодировании

s " = C "ÄH T ,

причем все компоненты s" должны быть равны 0.

При одиночной ошибке s"(4) = 1. По значению синдрома (младшие 3 бита) находим и исправляем (инвертируем) ошибочный бит.

При двойной ошибке компонента s"(4)= 0, а синдром отличен от нуля. В отличие от стандартного кода Хемминга такая ситуация ужеобнаруживается , но не исправляется (передается запрос на повторную передачу слова и т.п.).

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

Для исправления однократных и обнаружения двукратных ошибок;

Для обнаружения трехкратных ошибок.