Лекции по количественной оценке информации (стр. 5 из 11)

(71)

Коды, порождаемые этими матрицами, известны как

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

Порождающая матрица С может быть представлена двумя матрицами И и П (информационной и проверочной). Число столбцов матрицы П равно

, число столбцов матрицы И равно :

(72)

Теорией и практикой установлено, что в качестве матрицы И удобно брать единичную матрицу в канонической форме:

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

Вес каждой строки матрицы П должен быть не менее

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

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

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

Для кодов с

=2 производящая матрица С имеет вид

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

Для кодов с

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

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

Для кодов с

соотношения п и . следующие: (3; 1), (7;4), (15; 11), (31; 26), (63; 57) и т. д.

Плотно упакованные коды, оптимальные с точки зрения минимума избыточных символов, обнаруживающие максимально возможное количество вариантов ошибок кратностью r + 1; r + 2 и т. д. и имеющие

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

, весом . Тем же Слепяном в работе [11] были исследованы неплотно упакованные коды с малой плотностью проверок на четность. Эти коды экономны с точки зрения простоты аппаратуры и содержат минимальное число единиц в корректирующих разрядах порождающей матрицы. При построении кодов с максимально простыми шифраторами и дешифраторами последовательно выбираются векторы весом = 2, 3, ..., . Если число комбинаций, представляющих собой корректирующие разряды кода и удовлетворяющих условию , больше , то в первом случаене используют наборы с наименьшим весом, а во втором - с наибольшим.

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

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

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

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

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

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

В результате осуществления проверок образуется проверочный вектор

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

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

, число столбцов которой равно числу проверочныхразрядов кода:

.

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

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

Строится кодовая таблица. В первой строке таблицы располагаются все кодовые векторы

. В первом столбце второй строки размещается вектор , вес которого равен 1.

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

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