Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности
По заданному объему кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности. В случае циклического кода эта проблема сводится к нахождению нужного многочлена g(x).
Начнем рассмотрение с простейшего циклического кода, обнаруживающего все одиночные ошибки.
Любая принятая по каналу связи кодовая комбинация h(x), возможно содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комбинации кода f(x) и вектора ошибки ξ(x):
h(x) = f(x) Å ξ(x)
При делении h(x) на образующий многочлен g(x) остаток, указывающий на наличие ошибки, обнаруживается только в том случае, если многочлен, соответствующий вектору ошибки, не делится на g(x): f(x)-неискаженная комбинация кода и, следовательно, на g(x) делится без остатка.
Вектор одиночной ошибки имеет единицу в искаженном разряде и нули во всех остальных разрядах. Ему соответствует многочлен ξ(x) = xi. Последний не должен делиться на g(x). Среди неприводимых многочленов, входящих в разложении хn+1, многочленом наименьшей степени, удовлетворяющим указанному условию, является x + 1. Остаток от деления любого многочлена на x + 1 представляет собой многочлен нулевой степени и может принимать только два значения: 0 или 1. Все кольцо в данном случае состоит из идеала, содержащего многочлены с четным числом членов, и одного класса вычетов, соответствующего единственному остатку, равному 1. Таким образом, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда как раз и обеспечивает четность числа единиц в любой разрешенной кодовой комбинации, а, следовательно, и делимость ее на xn + 1.
Полученный циклический код с проверкой на четность способен обнаруживать не только одиночные ошибки в отдельных разрядах, но и ошибки в любом нечетном числе разрядов.
Прежде чем исправить одиночную ошибку в принятой комбинации из п разрядов, необходимо определить, какой из разрядов был искажен. Это можно сделать только в том случае, если каждой одиночной ошибке в определенном разряде соответствуют свой класс вычетов и свой опознаватель. Так как в циклическом коде опознавателями ошибок являются остатки от деления многочленов ошибок на образующий многочлен кода g(x), то g(x) должно обеспечить требуемое число различных остатков при делении векторов ошибок с единицей в искаженном разряде. Как отмечалось, наибольшее число остатков дает неприводимый многочлен. При степени многочлена m = n-k он может дать 2n-k - 1 ненулевых остатков (нулевой остаток является опознавателем безошибочной передачи).
Следовательно, необходимым условием исправления любой одиночной ошибки является выполнение неравенства
2n-k- 1³ = n,
где - общее число разновидностей одиночных ошибок в кодовой комбинации из п символов; отсюда находим степень образующего многочлена кода
m = n – k ³ log2(n+1)
и общее число символов в кодовой комбинации. Наибольшие значения k и п для различных m можно найти пользуясь табл. 4.13.
Таблица 4.13.
M
N
K
Как указывалось, образующий многочлен g(x) должен быть делителем двучлена хn+1. Доказано, что любой двучлен типа х2m-1+ 1 = хn+1может быть представлен произведением всех неприводимых многочленов, степени которых являются делителями числа т (от 1 до т включительно). Следовательно, для любого т существует по крайней мере один неприводимый многочлен степени т, входящий сомножителем в разложение двучлена хn+1.
Пользуясь этим свойством, а также имеющимися в ряде книг таблицами многочленов, неприводимых при двоичных коэффициентах, выбрать образующий многочлен при известных n и m несложно. Определив образующий многочлен, необходимо убедиться в том, что он обеспечивает заданное число остатков.
Пример 35. Выберем образующий многочлен для случая n = 15 и m = 4.
Двучлен x15 + 1 можно записать в виде произведения всех неприводимых многочленов, степени которых являются делителями числа 4. Последнее делится на 1, 2, 4.
В таблице неприводимых многочленов находим один многочлен первой степени, а именно x+1, один многочлен второй степени x2 + x + 1 и три многочлена четвертой степени: х4 + x + 1, х4 + х3 + 1, х4 + х3 + х2 + х + 1. Перемножив все многочлены, убедимся в справедливости соотношения (х + 1)(х2 + х + 1)(х4 + х+ 1)(х4 + х3+ 1)(х4 + х3 + х2 + х + 1) = x15 + 1
Один из сомножителей четвертой степени может быть принят за образующий многочлен кода. Возьмем, например, многочлен х4 + х3 + 1, или в виде двоичной последовательности 11001.
Чтобы убедиться, что каждому вектору ошибки соответствует отличный от других остаток, необходимо поделить каждый из этих векторов на 11001.Векторы ошибок m младших разрядов имеют вид: 00…000, 00…0010, 00…0100, 00…1000.
Степени соответствующих им многочленов меньше степени образующего многочлена g(x). Поэтому они сами являются остатками при нулевой целой части. Остаток, соответствующий вектору ошибки в следующем старшем разряде, получаем при делении 00...10000 на 11001, т.е.
Аналогично могут быть найдены и остальные остатки. Однако их можно получить проще, деля на g(x) комбинацию в виде единицы с рядом нулей и выписывая все промежуточные остатки:
При последующем делении остатки повторяются.
Таким образом, мы убедились в том, что число различных остатков при выбранном g(x) равно п = 15, и, следовательно, код, образованный таким g(x), способен исправить любую одиночную ошибку. С тем же успехом за образующий многочлен кода мог быть принят и многочлен х4 + х + 1. При этом был бы получен код, эквивалентный выбранному.
Однако использовать для тех же целей многочлен х4 + х3 + x2 + х + 1 нельзя. При проверке числа различных остатков обнаруживается, что их у него не 15, а только 5. Действительно,
Это объясняется тем, что многочлен x4 + х3 + х2 + х + 1 входит в разложение не только двучлена x15+ 1, но и двучлена x5 + 1.
Из приведенного примера следует, что в качестве образующего следует выбирать такой неприводимый многочлен g(x) (или произведение таких многочленов), который, являясь делителем двучлена хп + 1, не входит в разложение ни одного двучлена типа хλ+ 1, степень которого λ меньше п. В этом случае говорят, что многочлен g(x) принадлежит показателю степени п.
В табл. 4.14 приведены основные характеристики некоторых кодов, способных исправлять одиночные ошибки или обнаруживать все одиночные и двойные ошибки.
Это циклические коды Хэмминга для исправления одной ошибки, в которых в отличие от групповых кодов Хэмминга все проверочные разряды размещаются в конце кодовой комбинации.
Эти коды могут быть использованы для обнаружения любых двойных ошибок. Многочлен, соответствующий вектору двойной ошибки, имеет вид ξ(х) = хi – хj, или ξ(x) = хi(хj – i+ 1) при j>i. Так как j – i<n, a g(x) не кратен х и принадлежит показателю степени п, то ξ(x) неделится на g(x), что и позволяет обнаружить двойные ошибки.
