3.13. Код Макдональда

Чтобы понять принцип построения кодов Макдональда, вначале рассмотрим так называемое представление систематических -кодов, записанных с помощью производящей матрицы Поскольку данная матрица имеет строк (см. § 3.3) и чисто нулевой столбец может быть исключен из рассмотрения как бесполезный, существует всего различных типов возможных столбцов. Поэтому код можно задать указанием числа столбцов каждого типа. Этот способ задания называется модулярным представлением кода. Пусть специальная матрица размерности -содержащая в качестве столбцов все возможные векторы, кроме нулевого. Тогда столбец матрицы можно рассматривать как столбец типа а код может быть задан вектором, образованным положительными целыми числами [93]: где число столбцов типа

Например, если количество информационных символов то специальная матрица содержит 23—1 различных типов столбцов:

Если производящая матрица кода имеет вид

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

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

Если умножить транспонированную специальную матрицу размерности на производящую матрицу кода размерности полученная матрица

размерности в качестве строк содержит все возможные ненулевые комбинации строк матрицы Таким образом, строками матрицы К являются все ненулевые кодовые векторы.

Пример. Код (5.3) задан следующей производящей матрицей:

Найти все кодовые комбинации этого кода. Матрица для имеет вид

Модулярное представление кода , так как пропущены третий и седьмой столбцы специальной матрицы

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

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

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

Различные случаи, для которых Макдональду удалось доказать максимальность минимального кодового расстояния, приведены в табл. 25 [93].

Таблица 25 (см. скан)

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

Это говорит о том, что из специальной матрицы

необходимо вычеркнуть первые 16 столбцов.

Полученная производящая матрица кода Макдональда имеет вид

Умножив транспонированную матрицу на матрицу получим все кодовые векторы (см. с. 132).

Подсчитав количество единиц в каждой строке, находим, что данный код имеет 15 слов веса 8, 15 слов веса 7 и одно слово веса 15, т. е. действительно минимальное кодовое расстояние равно 7.

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

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

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