13.2 ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

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

Понятие группы

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

Аксиома замкнутости. Выбранная бинарная операция может быть применена к любым двум элементам группы, ваятых в определенном порядке. Результат операции также является элементом группы.

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

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

Аксиома единичного элемента. В группе существует единственный единичный элемент. Если выбранная операция есть сложение, то

единичный элемент обозначается как 0 и определяется соотношением

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

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

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

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

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

Определение. Группа, состоящая из конечного числа элементов, называется конечной.

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

Пример. Задано множество Над элементами множества определена операция суммы. Выяснить, является множество , с введенной операцией, групиой.

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

Проверка аксиомы вамкнутости:

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

Проверка аксиомы ассоциативности;

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

Проверка аксиомы единичного элемента.

Очевидно, единичным элементом является 0, так как

т. е. выполняется соотношение для единичного элемента.

Проверка аксиомы обратного элемента.

Для каждого элемента множества существует единственный обратный элемент. Любой элемент множества является обратным по отношению к самому себе, так выполняется соотношение

Представляется возможность показать самостоятельно справедливость следующих утверждений:

1. Множество с операцией суммы по модулю 2 является группой.

2. Множество с операцией суммы по модулю 2 является группой.

Понятно линейного группового кода

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

Линейные групповые коды могут быть заданы двумя способами

перечислением векторов;

матричным представлением.

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

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

где — скаляры, знак операции суммы по модулю 2.

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

Рассмотрим матрицу

Векторы, принадлежащие этой матрице, — линейно-независимы, т. е. матрица является порождающей матрицей некоторого кода Остальные векторы получаются суммированием векторов из порождающей матрицы. Пронумеруем векторы порождающей матрицы сверху вниз в порядке возрастания номеров. Тогда все векторы кода имеют

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

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

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

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

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

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

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

Минимальное расстояние линейного группового кода может быть определено в соответствии со следующим простым алгоритмом:

1. Выписать все векторы линейного группового кода.

2. Для каждого ненулевого вектора найти его вес в смысле Хэмминга. Минимальный вес ненулевого вектора и равен

Справедливость алгоритма вытекает из принадлежности нулевого вектора линейному групповому коду. Действительно, расстояние в смысле Хэмминга между нулевым вектором и вектором с минимальным числом единиц определяет рассматриваемого кода.

В соответствии с рассмотренным алгоритмом определим кода

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

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

1. Все векторы порождающей матрицы должны быть различны и линейно-независимы.

2. Нулевой вектор не должен входить в число векторов порождающей матрицы.

3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга

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

Проверочная часть порождающей матрицы (матрица Р) строится в соответствии со следующими правилами:

1. Вес в смысле Хэмминга каждого проверочного вектора должен удовлетворять соотношению

2 Вес проверочною вектора 4, являющегося суммой по модулю 2 двух любых проверочных векторов, должен удовлетворять

соотношению

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

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

1. Если Р — требуемая мощность линейного кода то формат информационной части его порождающей матрицы равен где

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

3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга

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

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

Построим порождающую матрицу линейного кода мощностью 16 и обнаруживающей способностью

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

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

Таблица 13.3

Таблица 13.4

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

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

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

матрицы следующим образом!

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

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

Декодирование линейных групповых кодов

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

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

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

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

или

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

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

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

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

и уравнения декодирования для кода, представленного матрицей

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

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

Выявление необнаруживаемых линейными кодами ошибок

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

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

только одну единичную компоненту. Очевидно, матрица имеет вид

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

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

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

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

значение синдромов для случая искажения проверочных разрядов описывается единичной матрицей формата Иными словами, матрица имеет вид

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

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

Как следует из матрицы М, рассматриваемый линейный код обнаруживает все двухкратные ошибки, так как каждому вектору двухкратной ошибки соответствует ненулевой синдром. Матрицы ошибок большей кратности строятся аналогично (например, для получения матрицы описывающей трехкратные ошибки, необходимо найти все суммы из трех векторов однократной ошибки и синдромы). Очевидно, код не обнаруживает трехкратные ошибки, возникающие в разрядах т. е. четыре трехкратные ошибки из 20 возможных. Код не обнаруживает четырехкратные, ошибки, возникающие в разрядах т. е. четыре четырехкратные ошибки из 15 возможных. Код обнаруживает любую пятикратную и шестикратную ошибки. Следовательно, из всех возможных 63 различных ошибок рассмотренный код не обнаруживает только 8 ошибок.

Тривиальные линейные групповые коды

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

их декодирования представляет собой сумму по модулю 2 всех разрядов вектора кода и известна как свертка по модулю 2.

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

Уравнение декодирования единственное и имеет вид

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

Исправление ошибок с помощью линейных групповых кодов

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

исправляющего однократные ошибки, матрица однократных ошибок имеет вид

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

Коды с простым повторением

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

Пример. Построить коде простым повторением мощности 8, Порождающая матрица С такого кода имеет вид

Уравнения, определяющие процедуру декодирования, имеют вид

Очевидно, декодирование кода с простым повторением сводится к сравнению проверочных и информационных разрядов.

Коды с малой плотностью проверок на четность

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

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

Пример. По заданной порождающей матрице построить проверочную матрицу .

Очевидно, матрица может быть представлена в виде

Коды с малой плотностью проверок на четность обычно обозначаются как где длина кода; — число информационных разрядов; число единиц в каждой строке матрицы Н.

Условие существования такого кода с можно сформулировать следующим образом:

1. Каждая из строк матрицы Н содержит единиц.

2. Каждый из столбцов матрицы Н отличается от других и содержит по крайней мере одну единицу.

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

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

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

Построим код о малой плотностью проверок на четность при условии, что Используя условие

Следовательно, Общее число единиц в матрице D определяется выражением Очевидно, матрица Я (один из вариантов) может быть представлена в виде

Отсюда порождающая матрица имеет вид

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

матрице и представлены в виде