4.6. Способы определения количества вариантов не обнаруживаемых циклическими кодами ошибок

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

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

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

В данном случае сами одночлены представляют собой остатки от деления, так как степень образующего полинома равная больше степени которую может иметь одночлен ошибок, расположенный в первых строках матрицы. Из совокупности всех таких остатков можн» образовать транспонированную единичную матрицу порядка Остальные к строк приписанной матрицы остатков образуют вторую подматрицу остатков от деления х степени к) на полином Как известно, из этих остатков составлена дополнительная матрица производящей матрицы циклического -кода. Составленная таким образом матрица из трех подматриц отображает все варианты одиночных ошибок и остатки от деления кодовых комбинаций, содержащих указанные одиночные ошибки. В общем случае эта матрица имеет следующую структуру [59]:

где верхний индекс указывает на кратность ошибок, нижний — на число столбцов и строк матрицы (4.9).

В качестве примера рассмотрим построенную указанным способом матрицу для циклического -кода с образующим полиномом

Для наглядности матрица (4.10) в соответствии с матрицей (4.9) разделена пунктирными линиями на подматрицы. Под столбцами матрицы ошибок написаны цифры, указывающие номера позиций кодовой комбинации; столбцы матриц остатков обозначены соответственно ей Цифры справа указывают номера строк матрицы (4.10).

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

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

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

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

где — символ суммирования по модулю два.

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

Если произвести сложение по модулю два элементов других строк, например 1, 2 и 6, получим нулевой остаток. Действительно,

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

Рассматривая матрицу остатков, нетрудно заметить, что нулевые суммы получатся при сложении одной строки остатка весом с двумя соответствующими строками остатков, имеющих вес Таких вариантов три: (1, 2, 6), (1, 3, 4), (2, 3, 7), где в скобках указаны номера суммируемых строк.

Нулевые строки получаются при суммировании элементов двух строк из нижней подматрицы с одной строкой верхней подматрицы: (2, 4, 5), (3, 5, 6), (1, 5, 7). Наконец, один нулевой остаток получается при суммировании трех строк из нижней подматрицы (4, 6, 7). Таким образом, из общего количества 35 тройных ошибок -кодом не обнаруживается вариантов.

Аналогичным образом можно найти количество вариантов нёобнаруживаемых четырехкратных ошибок, если производить суммирование элементов четырех строк. Нулевые остатки получаются при суммировании следующих строк: (1, 2, 3, 5), (1, 2, 4, 7), (1, 3, 6, 7), (1, 4, 5, 6), (2, 3, 4, 6), (2, 5, 6, 7), (3, 4, 5, 7); всего семь вариантов. Наконец, -кодом не обнаруживается единственная семикратная ошибка (1, 2, 3, 4, 5, 6, 7), соответствующая искажению всех элементов кодовой комбинации. Таким образом, мы нашли все возможные варианты необнаруживаемых ошибок циклическим -кодом, общее число которых равно

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

произвести всего сложений строк матрицы (4.10) в различных сочетаниях от до

При нахождении нет необходимости в выражении (4.10) приписывать транспонированную единичную матрицу В примере она приводится только для обоснования метода и пояснения характера ошибок в -элементной кодовой комбинации.

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

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

Необнаруживаемые ошибки определяем согласно следующему правилу.

Первый шаг. Выпишем в табл. 32 номера строк матрицы (4.11), при сложении которых получаются

нулевые суммы. В первом столбце таблицы показаны номера этих нулевых сумм, в трех последних — номера строк матрицы, при сложении которых получается нулевая сумма.

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

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

Слева в скобках указаны номера суммируемых строк табл. 32, справа — соответствующие им номера строк исходной матрицы остатков (4.11). Здесь первая строка представлена четное число раз, поэтому она должна быть вычеркнута.

Легко проверить, что при сложении четырех строк (2, 3, 5, 9) матрицы (4.11) действительно получается нулевая сумма, что и следовало ожидать, так как при сложении каждой строки дважды получается нулевой полином ошибок.

В результате суммирования любых строк табл. 32 получим нулевые суммы четырех или шести строк исходной матрицы (4.11), что свидетельствует о

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

обнаружении четырехкратных и шестикратных ошибок. Нулевые суммы запишем соответственно в табл. 33, 35.

Произведем аналогичное сложение трех любых строк табл. 32, результаты сложения с нулевыми суммами запишем соответственно в табл. 34, 36, 38.

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

Наконец, выполним сложение четырех строк табл. 32, результат сложения с нулевыми суммами запишем в табл. 37.

Как видно из таблиц 32—38, укороченный циклический (10,6)-код имеет всего варианта необнаруживаемых ошибок. Таким образом, найдены все варианты необнаруживаемых ошибок циклическим -кодом. Все остальные возможные варианты ошибок в количестве этим кодом обнаруживаются.

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

(см. скан)

ты необнаруживаемых ошибок были найдены при испытании двух, трех и четырех строк табл. 32.

В [59] приведены сведения о корректирующих способностях некоторых циклических кодов.