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

Трудности, связанные с практической реализацией декодирования, заставляют искать специальные классы кодов, для которых существует простой метод декодирования. К таким кодам относятся коды с малой плотностью проверок на четность, которые впервые предложил Галлагер [24, 25]. Эти коды описываются проверочной матрицей, содержащей преимущественно нули и сравнительно небольшое число единиц. Тем самым уменьшается количество символов, входящих в проверочные соотношения. Определим код с с малой плотностью проверок на четность как код длиной разрядов с информационными разрядами и с проверочной матрицей, каждая строка которой содержит не более единиц.

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

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

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

3. Значение является минимальным для данных Из условия 1 следует, что суммарное количество

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

Это неравенство является верхней границей для количества информационных разрядов

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

Таким образом, для и является оптимальным. Поэтому при для

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

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

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

содержит в каждой строке по три единицы.

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

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

Пример. Построить проверочную матрицу кода а малой плотностью проверон на четность, для которого Согласно (3.53) имеем

Тогда проверочная матрица кода

Минимальное расстояние в этом коде равно трем.

Пусть тогда Это значение достигается в случае, когда т. е.

Оптимальное значение информационных разрядов

Для нечетного одна строка должна иметь единиц. Например, если то

Код (12, 4, 7) может быть задан с помощью следующей проверочной матрицы:

Если то Любой столбец содержит две единицы при или Отсюда для

Например, для проверочная матрица кода (15, 5, 10) имеет вид

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Все рассмотренные коды имеют и могут быть получены из кодов Хэмминга с помощью укорачивания. В табл. 27 приведены параметры некоторых кодов этого класса с