Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 71
Текст из файла (страница 71)
Они не всегда удобны для практического использования, поскольку исправление только однократных ошибок обычно оказывается недостаточным для обеспечения высокой верности передачи, а высокая исправляющая способность М-последовательностей покупается за счет их весьма низкой кодовой скорости А. Поэтому необходимо иметь класс кодов с промежуточными значениями Я.
Это может быть достигнуто при переходе к определенным подклассам циклических кодов. Полиномиальные коды. Циклические коды. Коды Боуза-ЧоудхуриХоквингема (БЧХ). Кодовые слова двоичного линейного кода могут быть представлены в виде полиномов х(Р) = х, +х,Р+х,Р'+...+х„,Р" ' степени и — 1 от некоторой формальной переменной Р, причем двоичные коэффициенты х, задают символы кодового слова.
Полиномиальный код определяется как множество полиномов (кодовых слов) степени п-1, получаемых умножением информационного полинома Ь(Р) степени й — 1 на порождающий полином кода 8(Р) степени и — й; х(Р) = Ь(Р)8(Р) (7.68) Уравнение (7.68) задает процедуру. кодирования полиномиального кода: сообщение дискретного источника кодируется примитивным кодом длины символы примитивного кода становятся коэффициентами информационного полинома Ь(Р) =Ь.+Ь,Р+...+Ь,,Р' '; последний умножается на порождающий полином кода 8(Р) = е. +81Р+...+8„,Р" ', и после приведения подобных членов определяются и коэффициентов полинома х(Р), являющихся символами кодового слова.
Из уравнения (7.68) видно, что любой из полиномов х(Р), соответствующих кодовым словам полиномиального кода, должен делиться без остатка на порождающий полином 8(Р). Остаток от деления полинома у(Р), соответствующего принятой из канала комбинации, на порождающий полином кода 8(Р) называется синдромным полиномом в(Р). Если синдромный полином равен нулю (т.е. деление произошло без остатка), то принятая комбинация является кодовым словом.
В противном случае принятая комбинация не является кодовым словом. Таким образом, для полиномиальных кодов процедура обнаружения ошибок (вычисление синдрома) состоит в делении принятой комбинации на порождающий многочлен. На практике находят применение циклические коды, являющиеся частным случаем полиномиальных кодов. Пусть х=(х„х„..., х„,) — произвольный двоичный блок длины п.
Будем называть циклическим сдвигом Я, вправо данного блока преобразование следующего вида: 283 Бх — (Х„„о Хо, хо ..., Х„-з) . Определение 14, Линейный двоичный (п, Ф)-код 1' называется циклическим кодом, если в результате циклического сдвига любой из его комбинаций полученная комбинация снова принадлежит коду, т.е. Б, н)', если х н1'. Теорема 7.9.
4~и любого двоичного циклического (п, 1с)-кода существует такой многочлен е(Р) степени т=п — к с двоичными коэффициентами, который делит без остатка многочлен В" +1, и при этом любое кодовое слово может быть представлено как многочлен х(Р) степени п — 1 следующего вида: х(Р) = й(Р)1у(Р), где Ь(Р) — произвольный многочлен с двоичными коэффициентами степени не выше lс — 1 12Ц.
Многочлен я(Р), о котором идет речь в данной теореме, называется порождающим многочленом циклического кода. Многочлен й(В) = 1.0" + 1)/8(.0) называется проверочным многочленом. Можно доказать, что многочлен Л(Р) является порождающим многочленом для дуального кода. Циклические коды значительно упрощают описание линейного кода, поскольку для них вместо задания /с х (п — 1с) элементов двоичной матрицы Р в представлении (7.48) требуется задать (п — Й+ 1) двоичных козффициентов многочлена 8(Р). Кроме того, они упрощают процедуру кодирования и декодирования для обнаружения ошибок. Действительно, для осуществления кодирования достаточно выполнить перемножение полиномов, что реализуется с помощью линейного регистра, содержащего 1с ячеек памяти и имеющего обратные связи, соответствующие многочлену Ь(Р) 1211.
Для обнаружения ошибок, достаточно разделить многочлен, соответствующий принятому слову у(Р), на порождающий многочлен е(Р) и проверить, будет ли остаток от деления равен нулю. Эта процедура также осуществляется на линейных сдвиговых регистрах с обратными связями. Однако более важное преимущество циклических кодов состоит в том, что они могут быть сконструированы как коды с некоторым гарантированным значением минимального кодового расстояния. Для этого необходимо определенным образом выбрать порождающий.многочлен кода я(Р), Циклические коды, которые имеют порождающий многочлен, заданный своими определенными корнями, называются кодами Боуза-Чоудхури-Хоквингема (кратко БЧХ-кодами). Однако корни этого многочлена ищутся не среди вещественных или комплексных чисел, а как злементы так называемых конечных полей Галуа.
Для того чтобы пояснить методы построения таких кодов и в дальнейшем рассматривать конструктивные методы исправления ошибок при помощи данных кодов, нам необходимо вкратце рассмотреть основы теории конечных полей. Полем э'(не обязательно конечным) называется множество элементов, для которого выполняются следующие свойства: 1. Для любой пары элементов поля а е э; Ь е э'определены операции а + Ь и а х Ь, называемые, соответственно, сложением и умножением, отображающие пару (а, Ь) в какой-либо элемент поля ж 2. Поле содержит нулевой элемент О и единичный 1, такие что а + О = а, ах1 = а для любого аеК 3.
Для любого и е .всушествует противоположный (аддитивно обратный) элемент — а такой, что ( — а) + а = О, и для любого а е м, а ~ О, существует мультипликативно обратный элемент а 1 такой, что аа 1 = 1. 284 4. Для операций с элементами поля У'выполняются законы: а) ассоциативный а + (Ь + с) = (а + Ь) + с; а(Ьс) = (аЬ)с; б) коммутативный а + Ь = Ь + а; аЬ = Ьа; в) дистрибутивный а(Ь + с) = аЬ + ас.
Поле называется кояечиым (или полем Галуа, в память об открывшем его французском ученом), если оно состоит из конечного числа элементов. Число элементов поля я называется его порядком, а само поле обозначается как ОР(я). Из определения поля видно, что фактически для любых пар элементов определена также и операция вычитания: а — Ь = а+ ( — Ь), а для пар а, Ь ~ 0 — и операция деления а/Ь = аЬ '. Доказывается, что в поле существует единственный элемент 0 и единственный элемент 1. В алгебре доказывается важная теорема о том, что порядок поля я всегда является степенью простого числа р, т.е. д = р", где и — натуральное число.
Если л = 1, то поле ОР(д) = ОР(р) называется лросррьрм. Для каждого допустимого значения я правила сложения и умножения, удовлетворяющие заданным требованиям, можно определить только одним способом. Все элементы простого поля могут быть заданы как множество чисел (О, 1, ..., р — 1), а операции над ними — как действия по модулю р (шод р), т.е. как числа, равные остатку от деления на р. В качестве примера в табл. 7.3 даны правила умножения и сложения для поля ОР(5).
Таблица умножения позволяет находить обратные элементы; так, 4 ' = 4, поскольку 4.4=1. Таблица сложения позволит определить обратный элемент — а на пересечении а и О. При вычитании или делении необходимо, используя таблицы, найти обратный элемент для вычитаемого или делителя, а затем выполнить сложение или' умножение обычным образом. Например, 3-4=3 + ( — 4)=3 + 1=4; 3(4 = 3 4 ' = 3 4 = 2.
Таблица 7.3 Возведение в степень также возможно с учетом формулы а = а а,.ра.. Например, 2 =1, 2'=2, 2 =2 2=4, 2'=2 2=4 2=3, 2 =2 2=3 2=1 Определим операции в расширенном поле ОР(р"), которые не задаются уже как операции по пнх1 р". Поле ОР(ц) при ц = р" и л ~ 1 называется расширением поля ОР(р), а поля такого вида— расширенными волями. Все элементы расширенного поля ОР(р") можно представить как всевозможные последовательности длины л с элементами из поля ОР(р).Например, поле ОР(2з) состоит из элементов: 000, 001, 010, 011, 100, 101, 110, 111.
Определение. Многочлен р(В) с коэффициентами из поля ОР(я) называется неприводимым над этим полем, если он не может быть представлен как произведение двух и более многочленов с коэффициентами из этого поля, когда степени этих многочленов больше нуля. При проверке этого условия действия над коэффициентами многочленов должны производиться в поле ОР(д). Пример. Многочлен хз + 1 приводим над ОР(2), так как ха + 1 = (х+ 1)(х+ 1); много- член хз + х+ 1 не приводим над ОР(2), так как его нельзя представить как произведение каких-либо из следующих многочленов степени меньше 3, но больше нуля над полем. ОР(2): х, х + 1, х~, х~ + 1, х + х, х + х + 1.
Разработаны регулярные методы генерирования неприводимых многочленов. В литературе (см., например, 12Ц) имеются таблицы некоторых неприводимых многочленов различных степеней. (В действительности имеется много неприводимых многочленов любой степени.) Теперь мы можем описать операции над элементами конечного поля ОР(р") как операции ' над последовательностями длины и над полем ОР(р). Прежде всего отметим, что любую такую последовательность Ь=(Ьр, Ь,,, Ь„,), Ь,е ОР(р), г'= О, 1, ..., л — 1, можно 285 представить полиномом степени п — 1 с коэффициентами над полем ОР(р) как н-1 7ь'(Р) = ~~~ Ь1Р1 . Тогда сумму двух элементов поля я + Ь можно получить как сумму соответст- 1=О вующих им многочленов, а произведение аЬ вЂ” как произведение соответствую1цих многочленов по модулю неприводимого полинома у(Р) степени л.
Пример: а= 010, Ь = 111, 7,'(х) = Р, 7ь(Р) = Рз+ Р+ 1, у(Р) = Рз+ Р+ 1, аЬ-/'(Р)Ьь(Р) = Рз + Рз + Р(щей Рз + Р + 1) = (Рз + Рз + Р) х 1 + Рз + 1(щод Рз + Р + 1) =, = Рз + 1 — 101 Поскольку существует несколько неприводимых многочленов степени л, то, казалось бы, могут существовать различные операции умножения для поля ОР(р"), однако в алгебре (2Ц доказывается важная теорема о том, что все конечные поля ОР(д), простые или расширенные, являются изоморфными. Это означает, что они фактически тождественны с точностью до переобозначения элементов. Поэтому не имеет значения, какой именно неприводнмый многочлен у(Р) степени л с коэффициентами из ОР(р) был выбран для задания поля ОР(р"). Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
