4.4. Выбор образующего полинома

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

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

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

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

Доказано [93], что любой двучлен Типа (4,5) может быть представлен произведением всех без исключения непроводимых многочленов, степени которых являются делителями числа (от 1 до включительно). Следовательно, для любого существует, по крайней мере, один неприводимый многочлен степени входящий сомножителем в разложение двучлена

Боуз и Чоудхури показали [20, 60], что для любых целых положительных чисел существует циклический код значности

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

При этом число проверочных символов не превышает величины т. е.

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

Соотношения (4.6) — (4.8) могут быть использованы для выбора образующего полиномд.

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

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

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

Следовательно, необходимым условием исправления любой одиночной ошибки является выполнение неравенства [117]

которое совпадает с (3.17).

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

По табл. 15 находим количество проверочных разрядов

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

Из соотношения (4.6) определяем К числам, на которые делится без остатка, относятся единица и три. Следовательно, сомножителями двучлена должны быть неприводимые полиномы первой и третьей степени. Выписав из

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

Обнаруживающая способность циклического кода определяется не только степенью образующего полинома, но и числом его членов [36]. Чем больше остатков может быть образовано при делении многочлена сообщения на образующий полином, тем выше корректирующая способность кода. Наибольшее число остатков, равное (исключая нулевой), может обеспечить только неприводимый многочлен степени [118].

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

Рассмотрим на примере этот вопрос более подробно.

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

Пусть общее число элементов в кодовой комбинации равно 15. Число проверочных разрядов определяем из соотношения По выражению Следовательно, Число информационных элементов Для имеем Так как делится без остатка на 1, 2 и 4, то сомножителями полинома должны быть все неприводимые полиномы 1-й, 2-й и 4-й степеней. Пользуясь таблицей неприводимых полиномов (приложение 2), получаем

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

Делением единицы с приписанными справа нулями на полиномы

получим соответственные подматрицы:

Для исправления одиночных ошибок дополнительные матрицы должны выбираться таким образом, чтобы вес каждой строки производящей матрицы был не меньше трех единиц (т. е. кодового расстояния) [36].

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

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

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

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

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

Из трех возможных парных произведений полиномов четвертой степени получим три полинома восьмой степени:

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

с приписанными справа нулями на 111010001, 100010111 и 110111011 находим соответственные дополнительные матрицы:

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

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

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

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

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

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

Обратный ему полином

Выполнив операцию умножения и расположив члены по убывающим степеням, получим

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

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

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

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

Табличные и расчетные методы нахождения образующих полиномов циклических кодов далеко не всегда позволяют однозначно выбирать наилучший полином для определенного типа канала и определенного характера распределения ошибок. Поэтому широкое распространение получили машинные методы отбора наилучших кодов и их образующих полиномов. Так, с помощью вычислительной машины произведен отбор образующих полиномов циклических кодов, более всего подходящих для обнаружения ошибок в телефонных каналах. Указанный отбор произведен на основании статистических данных распределения ошибок при передаче сигналов методом относительной фазовой модуляции со скоростью 1200 бод. Вероятность ошибки (по импульсам) при этом составляла Результаты отбора приведены в табл. 31 [86]. Здесь также приведено ожидаемое время (средний период) между двумя необнаруженными ошибками в часах.

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

(см. скан)

Продолжение табл. 31 (см. скан)