Помехоустойчивое кодирование и декодирование (1151930), страница 3
Текст из файла (страница 3)
Над данными многочленами можно проводить всеалгебраические действия с учетом того, что сложение здесь осуществляется по модулю 2.Каждый циклический код (п, k) характеризуется так называемым порождающим многочленом. Имможет быть любой многочлен р(х) степени п – k, который делит без остатка двучлен xn 1. Циклические кодыхарактеризуются тем, что многочлены b(х) кодовых комбинаций делятся без остатка на р(х).
Поэтому процесскодирования сводится к нахождению по известным многочленам а(х) и р(х) многочлена b(х), делящегося нар(х), где а(x) — многочлен степени k – 1, соответствующий информационной последовательности символов.Очевидно, что в качестве многочлена b(х) можно использовать произведение а(х)р(х). Однако при этомкод оказывается несистематическим, что затрудняет процесс декодирования. Поэтому на практике, восновном, применяется следующий метод нахождения многочлена b(х).Умножим многочлен а(х) на xn–k и полученное произведение разделим на р(х).
Пустьa(x)xn–k = m(x)p(x) c(x),(9.14)где т(х) — частное, а с(х) — остаток. Поскольку операции суммирования и вычитания по модулю 2совпадают, то выражение (9.14) перепишем в видеa(x)xn–k c(x) = m(x)p(x).(9.15)Из соотношения (9.15) следует, что многочлен a(x)xn–k c(x) делится на р(х) и, следовательно, являетсяискомым.Многочлен a(x)xn–k имеет следующую структуру: первые п – k членов низшего порядка равны нулю, акоэффициенты остальных совпадают с соответствующими коэффициентами информационного многочленаа(х). Многочлен с(х) имеет степень меньше п – k.
Таким образом, в найденном многочлене b(х) коэффициентыпри х в степени п – k и выше совпадают с информационными символами, а коэффициенты при остальныхчленах, определяемых многочленом с(х), совпадают с проверочными символами.В соответствии с формулой (9.15) процесс кодирования заключается в умножении многочлена а(х)на xn-k и нахождении остатка от деления a(x)xn–k на р(х) с последующим его сложением по модулю 2 смногочленом a(x)xn–k.Операции умножения и деления многочленов легко осуществляются линейными цепями на основесдвигающих регистров [133]. В качестве примера на рис.
9.24, а представлена схема умножения многочленаb( х )степенип=6на3многочлен f (x) = x x 1 помодулю x7 1. Нетрудноубедиться, что после семитактов в регистре записываетсямногочлен b(x) f (x) mod(x7 1). При делении многочленаb(х) степени п = 6 намногочлен f (x) = x3 x2 1(рис. 9.24, б) после семитактов в регистре оказываетсязаписаннымостатокотделения.Рис.
9.24. Схемы умножения (а) и деления (б) многочленов (частный случай)На основе приведенныхсхем умножения и делениямногочленовстроятсякодирующие устройства для циклических кодов. На рис. 9.25 в качестве примера приведена схема кодера длякода (7, 4) с порождающим многочленом p(x) = x3 x2 1. В исходном состоянии ключи К1 и К2 находятся вВ хо дположении1.Информационныесимволы поступают одновременно наК1вход канала и на выход ячейки х31T1T2m2T3m2сдвигающегорегистра(это2В ы хо дсоответствуетумножению3многочлена а(х) на х ). В течениеК21четырех тактов происходит деление2многочлена а(х)х3 на многочлен р(х) =Рис. 9.25. Структурная схема кодера циклического кода сx3 x2 1.
В результате в регистрепорождающим многочленом р(х) = x3 x2 1записываетсяостаток,представляющий собой проверочныесимволы. Ключи K1 и K2 перебрасываются в положение 2, и в течение трех последующих тактовсодержащиеся в регистре символы поступают в канал.Циклический код может быть задан проверочным многочленом h(x): кодовая комбинация Впринадлежит данному циклическому коду, если b(x)h(x) = 0 mod (xn 1).
Проверочный многочлен связан спорождающим соотношениемh(x) = (xn 1)/p(x).Задание кода проверочным многочленом эквивалентно заданию кода системой проверочных уравнений(9.13). Характерной особенностью циклического кода является то, что все проверочные уравнения можнополучить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение. Например,для кода (7,4) с порождающим многочленом p(x) = x3 x2 1 проверочный многочлен имеет видh(x) = x4 x3 x2 1.Проверочные уравнения получаются из условияb(x)h(x) = 0 mod (x7 1).Осуществив умножение и приравняв коэффициенты при х4, х5 и х6 нулю, получим следующиеуравнения, разрешенные относительно проверочных символов:b 2 = b 6 b 4 b 3;b1 = b5 b3 b2;(9.16)b 0 = b 4 b 2 b 1.В качестве примера на рис. 9.26 показана схема кодера циклического кода (7,4), задаваемогопроверочным многочленом h(x) = x4 x3 x2 1, или, что то же самое, проверочными соотношениями(9.16).
В исходном состоянии ключ находится в положении 1. В течение четырех тактов импульсы поступаютв регистр, после чего ключ переводится в положение 2. При этом обратная связь замыкается. Начиная с пятоготакта, формируются проверочные символы в соответствии с соотношениями (9.16). После седьмого такта всепроверочные символы оказываются сформированными, ключвновь переключается в положение 1. Кодер готов к приему1 T1T2T3T4В ы хо дочередного сообщения. Символы кодовой комбинации2поступают в канал, начиная с пятого такта.Корректирующая способность кода зависит отm2m2порождающего многочлена р(х). Поэтому его выбор оченьважен при построении циклического кода.
Необходимопомнить, что степень порождающего многочлена должна бытьРис.9.26.Структурнаясхемакодера равна числу проверочных символов. Кроме того, многочленциклического кода, задаваемого проверочнымр(х) должен делить двучлен xn 1.многочленом h(x) = x4 x3 x2 1Обнаружение ошибок при использовании таких кодовзаключается в делении многочлена b'(х) = b(x) + e(x), соответствующего принятой комбинации B% B e, нар(х). Если остаток s(x) оказывается равным нулю, то считается, что ошибки нет, в противном случаефиксируется ошибка.Пусть необходимо построить код, обнаруживающий все одиночные ошибки. В этом случае многочленошибок имеет вид е(х) = хi, где i = 0, 1, …, n – 1.
Решение задачи заключается в нахождении такогомногочлена р(х), чтобы многочлен е(х) не делился на р(х). Наиболее простым, удовлетворяющим этомутребованию, является многочлен р(х) = х 1.Аналогично можно построить код, обнаруживающий ошибки большей кратности.Многочлен s(x) = (b(x) e(x)) mod p(x) = e(x) mod p(x) зависит только от многочлена ошибок е(х) ииграет ту же роль, что и вектор-синдром. Поэтому в принципе ошибки можно исправлять на основе таблицысоответствий между е(х) и s(x), хранящейся в памяти декодера, как при линейных нециклических кодах.Однако свойство цикличности позволяет существенно упростить процедуру декодирования.Один из алгоритмов исправления ошибок основан на следующих свойствах синдрома циклического кода.Пусть имеется циклический код с кодовым расстоянием d, исправляющий все ошибки до кратности l = [(d – 1)/2]включительно, где [(d – 1)/2] — целая часть числа (d – 1)/2.
Тогда можно показать [133], что:— если исправляемый вектор ошибок искажает только проверочные символы, то вес синдрома будетменьше или равен l, а сам синдром будет совпадать с вектором ошибок;— если вектор ошибки искажает хотя бы один информационный символ, то вес синдрома будет большеl;— если s(x) — остаток от деления многочлена b(х) на р(х), то остатком от деления многочлена b(x)xi нар(х) является многочлен s(х)xi mod [p(x)], другими словами, синдром некоторого циклического сдвигамногочлена b(х) является соответствующим циклическим сдвигом синдрома исходного многочлена, взятогопо модулю р(х).В качестве примера на рис. 9.27 представлена схема декодера для кода (7, 4) с порождающиммногочленом p(x) = x3 x2 1.
Код имеет кодовое расстояние d = 3, что позволяет ему исправлять всеоднократные ошибки.Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий длязапоминания кодовой комбинации и ее циклического сдвига, и на устройство деления на многочлен р(х) длявычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферныйрегистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вессиндрома больше единицы, тодекодер начинает проводитьциклическиесдвигикомбинациивбуферномрегистреприотсутствииновой комбинации на входе иодновременно вычислять ихсиндромы s(x)xi mod (p(x)) вустройстве деления. Если нанекотором i-м шаге вессиндрома окажется меньшедвух, то ключ переходит вРис.
9.27. Структурная схема декодера циклического кода сположение 2, обратные связи впорождающим многочленом p(x) = x3 x2 1регистределенияразрываются.Припоследующих тактах ошибкиисправляются путем подачи содержимого регистра деления на вход сумматора по модулю 2, включенного вбуферный регистр. После семи тактов работы декодера в автономном режиме исправленная комбинация вбуферном регистре возвращается в исходное положение (информационные символы будут занимать старшиеразряды).Существуют и другие, более универсальные алгоритмы декодирования.К циклическим кодам относятся коды Хэмминга, которые являются примерами немногих известныхсовершенных кодов.
Они имеют кодовое расстояние d = 3 и исправляют все одиночные ошибки. Длина кодавыбирается из условия 2n–k – 1 = n, которое имеет простой смысл: число различных ненулевых синдромовравно числу символов в кодовой последовательности. Так, существуют коды Хэмминга (2r – 1, 2r – r – 1), вчастности коды (7, 4), (15, 11), (31, 26), (63, 57) и т. д.Заметим, что ранее использованный многочлен p(x) = x3 x2 1 является порождающим для кодаХэмминга (7, 4).Среди циклических кодов широкое применение нашли коды Боуза—Чоудхури—Хоквингема (БЧХ).Можно показать, что для любых целых положительных чисел т и l < n/2 существует двоичный код БЧХ длиныn = 2m – 1 с кодовым расстоянием d ≥ 2l + 1, причем число проверочных символовn – k ≤ ml.Для кодов БЧХ умеренной длины и ФМ при передаче символов можно добиться значительноговыигрыша (4 дБ и более) [133].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
