Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 72
Текст из файла (страница 72)
Элемент ае ОР(в) называется примитивным, если все его степени а', 1= О, 1, ..., д — 2 различны и дают все элементы конечного поля ОР(в), кроме нулевого. Доказывается [2Ц, что в любом конечном поле всегда существует примитивный элемент. (В действительности в каждом поле имеется несколько примитивных элементов.) Использование понятия примитивного элемента значительно упрощает описание таблицы умножения элементов поля.
Действительно„если а=а', Ь=а~, то аЬ=аЫ = а1+1. Легко определяются и обратные элементы, поскольку если а = а'„то а ' = ае ' ' (Однако таблица сложения не упрощается при использовании примитивного элемента.) Пусть имеется некоторый многочлен ЯР) степени и с коэффициентами из конечного поля ОР(р). Согласно основной теореме алгебры этот многочлен может иметь в поле ОР(р) не более чем л корней, но он может не иметь и одного корня. Определение. Неприводимый многочлен степени л над полем ОР(р) называется примитивным многочленом, если хотя бы один из его корней является примитивным элементом поля ОР(р~).
Можно доказать 12Ц, что у примитивного многочлена все корни являются примитивными элементами, причем если а — один из корней этого многочлена, то а, а~, а~, ..., а" ' образуют совокупность всех корней этого многочлена. (В действительности последнее свойство справедливо для любого неприводимого многочлена.) Существует и другое (зквиралентное) определение примитивного многочлена — это такой неприводимый многочлен степени п, что он делит многочлен Р~ ' — 1 и не делит многбчлены вида Р" -1, осли и' < р" — 1. В литературе приводятся таблицы примитивных элементов 12Ц.
Число примитивных многочленов Ф(п) степени и определяется по формуле Л1(п) =.У(2" — 1)/и, где к(1) — функция Эйлера, которая определяется как количество чисел ряда О, 1, ..., 1 — 1, взаимно простых с 1. Если 2" — 1 — простое число„то Ю(2" — 1) = 2" — 2. Рассмотрим частный случай блоковых циклических кодов, позволяющих гарантировать определенную величину минимального кодового расстояния и реализовать конструктивный алгоритм исправления ошибок гарантированной кратности.
Определение. Двоичный циклический код длины 21 — 1, где 1 — неотрицательное целое число, называемое кодом Боуза-Чоудхури-Хоквиигема (нли сокращенно БЧХ-кодом) в узком смысле, если слово х принадлежит коду тогда, и только тогда, когда а, а~,..., а~1, где а — примитивный элемент поля ОР(2'), являются корнями многочлена ЯР). Это определение эквивалентно следующему матричному уравнению: хН =О, (7.68а) 286 „0 „ аи-г и-1 (а) а ...
(а) (а) (а ) а ... (а ) (а ) где Н= Все действия в (7.б8а) выполняются в поле бх(21). Рассмотрим определитель Р, составленный из любого набора 21 столбцов матрицы Н: (а)б (а)Л ... (а)г" ( г)я ( г)л ( г)л~ ( гг)Л ( гг)Л ( гг)~ч Вынося из каждого 1-го столбца множитель ая, получаем 1 1 ...
1 ал ал агч П = а1Х'Л'-'1ч) (7.69) (ал) (ал) ... (ал') 7.3.5. КОНСТРУКТИВНЫЕ АЛГОРИТМЫ ИСПРАВЛЕНИЯ ОШИБОК ЛИНЕЙНЫМИ КОДАМИ Подытоживая сказанное ранее, можно сделать вывод, что переход к линейным кодам и к их частным случаям — циклическим и БЧХ-кодам практически полностью решает проблему кодирования-декодирования с обнаружением ошибок и построения кодов с большим минимальным расстоянием. Однако проблема исправления ошибок по-прежнему остается открытой. Действительно, даже при наиболее экономном способе синдромного декодирования необходимо произвести запоминание таблицы, содержащей 2" " различных синдромов и поиск по этой таблице. (Сложность декодирования экспоненциально зависит от 7с или от л — lс.) Переход к циклическим кодам лишь несколько упрощает вычисление самого синдрома, но не исключает необходимость запоминания 2" ~ векторов. В современной теории кодирования разработан ряд конструктивных методов декодирования, которые позволяют перейти от экспоненцианьной сложности декодирования к полиномиальной.
Это прежде всего: 1. Алгебраические методы декодирования для БЧХ- и родственных им кодов. 2. Мажоритарные методы декодирования. 287 Поскольку в правой части (7.б9) стоит определитель Ван-дер-Монда, то он всеща будет отличен от нуля, и, следовательно, не существует линейно зависимых комбинаций из 21 или меньшего числа столбцов матрицы Н. Поэтому аналогично выводу границы ВаршамоваГильберта получим, что код, определяемый уравнением (7.б8а)„будет иметь минимальное кодовое расстояние д = 21+ 1. Можно доказать [2Ц, что степень порождающего многочлены 8()9) такого циклического кода не превосходит В и поэтому такой код содержит не более чем д проверочных символов.
Этот факт может быть сформулирован в виде следующей теоремы. Теорема 7,10. Всегда можно построить двоичный БЧХкод с длиной блока и = 21 — 1 (1 — любое натуральное число), который имеет й > и — 11 информационных символов (г с 2' ' — натуральное число) и гарантированно исправляет ошибки кратности не меньше, чем 1. Этот код в отличие от неконструктивного метода, который мы использовали при выводе границы Варшамова-Гильберта, весьма просто определяется своим порождающим многочленом 8(О).
Имеются достаточно подробные таблицы, которые дают для всевозможных наборов (п,к) виды порождающих многочленов и соответствующие им значения минимальных кодовых расстояний д. Мажоритарная процедура декодирования допускает итеративное обобщение, когда на первой итерации с использованием проверочных соотношений вычисляются апостериорные вероятности символов кодового блока в предположении, что априорные вероятности всех символов имеют равномерное распределение. Затем на второй итерации вычисляются новые апостериорные вероятности в предположении, что априорными вероятностями в этом случае оказываются апосгериорные вероятности, полученные на 1-й итерации, и т.д.
При определенных условиях итеративная процедура сходится к действительно передававшемуся кодовому слову, т.е. происходит исправление ошибок. Рассмотрим более подробно первый подход. Пусть передается произвольное кодовое слово х = (хо,..., х„!) и принято слово у = х Э е, ще е = !ео,е„... е„!), е, в ОР(2) - это образец ошибок, а Ю означает поэлементное суммирование в !7Р(2). Найдем синдром в для принятого слова у по известной матрице Н: з= уН". (7.70) Поскольку у=х+е, а хнг =О, то из (7.70) находим в=он (7.71) В действительности можно показать, что в матрице Н можно ограничиться лишь нечетными степенями оо, т.е. рассматривать в (7.71) матрицу Н следующего вида: о о-3 л-! О' "* - Оьа О"' н= и-!) ц-! ( ц-!)" ~ ~ о!-!)" ' Тогда, если з =(л!, ..., лн !), то из (7,71) получим лу — — 1,~со!), !'=1, 3, ..., 21 — 1, (7.72) где г",(р) — многочлен, соответствующий образцу ошибки е.
Предположим', что вес вектора ошибки равен а и его ненулевыми компонентами являются е„, еь, е,, т.е. вектор у содержит ошибки в координатах !!, 1о, ..., ! . Определим локаиюры о!аибок как величины в поле бР(2") 1~ ку — — а!, 1=1, 2, ..., о! . и многочлен локаторов оиоибок а(е)=п(1 — х>е)=~~1 аф. (7 74) ,/ ! / о Из (7.72) и (7.73) получим, что, г!=~х . / ! (7.73) (7.75) 288 При втором подходе выбираются специальные подклассы линейных кодов, имеющих так называемые "разделенные проверки".
Каждый из символов блока такого кода входит только в одну из проверок для любого символа блока. Например, для кода (7, 3), дуального к коду хэмминга, первый символ х1 блока связан проверочными соотношениями х1 = х2 6 хб = х5 Е х7 = х3 оТо х4. После приема кодового блока можно вычислить все эти проверки, включая и тривиальную х = х1, и принять решение о том, равен х1 нулю или единице в зависимости от того, оказывается ли больше среди данных проверок нулей или единиц.
Такой метод декодирования называется мажоршпарным. Он обобщается и на другие циклические коды, хотя возможен далеко не для всех из них. Покажем, как можно найти коэффициенты многочлена локаторов ошибки ~тн ..., <т по известным координатам синдрома е,, ..., х,, 1 Положим х = — в выражении (7.74), что дает равенство х 1 1 1 1+ о,— + е2 — 2+...+ о„— „= О.
(7.76) хз х1 х1 Умножим (7.76) на х'~ х'+~+о х'~ '+о х'~ з+...+о„х' =О / 1/ 2/ "вт и просуммируем по всем 1= 1, 2,, в . Тогда получим А, „+о,А, „, +озА, „з+...+о А, =О, А, =е,, 1=1, ..., 21 — 1. (7.77) Система уравнений (7.77) является линейной, и поэтому если ее решение существует, то оно может быть легко найдено, Доказывается 1211, что если число действительно произошедших ошибок не превосходит 1, то система (7.77) имеет решение.
После нахождения неизвестных он ..., о„можно по (7.74) вычислить многочлен локаторов ошибок. Затем находятся корни этого многочлена е,, е,., а и, наконец, локаторы ошибок х =а,'. Очевидно, что нахождение локаторов ошибок позволяет найти положения самих ошибок еч на кодовом блоке, т.е. произвести исправление ошибок. Как видно, при использовании алгебраических методов декодирования процедура исправления ошибок имеет полиномиальную сложность в зависимости от числа ошибок гз, чем она существенно отличается от экспоненциально сложной процедуры декодирования методом перебора всех образцов ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
