Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1151848), страница 114
Текст из файла (страница 114)
(9.15) Из соотношения (9.15) следует, что многочлен а(х)х Ю с(х) делится нар(х) и, следовательно, является искомым. Многочлен а(х)х имеет следующую структуру: первые л — Iг членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х). Многочлен с(х) имеет степень меньше л — Ф.
Таким образом, в найденном много- члене Ь(х) коэффициенты при х в степени л — Ф и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемых многочленом с(х), совпадают с проверочными символами. В соответствии с формулой (9.15) процесс кодирования заключается в умножении многочлена а(х) на х " и нахождении остатка от деления а(х)х'~ нар(х) с последующим его сложением по модулю 2 с многочленом а(х)х" ". Операции умножения и деления многочленов легко осуществляются линейными цепями на основе сдвигающих регистров 1133).
В качестве примера на рис. 9.24, а представлена схема умножения многочлена Ь(х) степени л = б на многочленг(х) = х' Ю х Ю 1 по модулю х" Ю 1. Нетрудно убедиться, что после семи тактов в регистре записывается многочлен Ь(х)Дх) шос1(х' Ю 1). При делении многочлена Ь(х) степени и = б на многочленДх) = х Ю х Ю! г (рис. 9.24, б) после семи тактов в регистре оказывается записанным остаток от деления. 6 Рнс. 9.24.
Схемы умножения (а) н деления (д) многочленов (частный случай) 581 9. Радиотехнические системог передачи информации Вход о 2 Рис. 9.25. Структурная схема кодера циклического кода с порождающим многочленом р(х) = х Ю х 9 1 На основе приведенных схем умножения и деления многочленов строятся кодирующие устройства для циклических кодов. На рис.
9.25 в качестве примера приведена схема кодера для кода (7, 4) с порождающим многочленомр(х) = х 9х 9 1. В исходном состоянии ключи К1 и Кг нахо- г дятся в положении 1. Информационные символы поступают одновременно на вход канала и на выход ячейки х сдвигающего регистра (это соответствует умножению многочлена а1х) на х ). В течение четырех тактов происходит деление многочлена а(х)х' на многочлен р(х) = х' 9 хг 9 1.
В результате в регистре записывается остаток, представляющий собой проверочные символы, Ключи К, и К, перебрасываются в положение 2, и в течение трех последующих тактов содержащиеся в регистре символы поступают в канал. Циклический код может быть задан проверочным многочленом Ь(х): кодовая комбинация В принадлежит данному циклическому коду, если Ь(х)Ь(х) = О щоб (х" 9 1). Проверочный многочлен связан с порождающим соотношением Ь(х) = (х" 9 1)/р(х). Задание кода проверочным многочленом эквивалентно заданию кода системой проверочных уравнений 19.13). Характерной особенностью циклического кода является то, что все проверочные уравнения можно получить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение.
Например, для кода 17, 4) с порождающим многочленом р(х) = =х' 9 х' 9 1 проверочный многочлен имеет вид Ь(х) =х' 9 х' 9 х 9 1. Проверочные уравнения получаются из условия Ь(х)Ь(х) = О щос1 (х' 9 1) . Осуществив умножение и приравняв коэффициенты при х, х и х нулю, получим следующие уравнения, разрешенные относительно проверочных символов: 582 9.5. Памвхоустойчивов кодирование и декодирование Ьг = Ьв 9 Ь4 9 Ьз Ь| = Ьз 9 Ьз 9 Ьг (9 16) Ь =Ь,9Ь 9Ь. В качестве примера на ег иг рис. 9.26 показана схема кодера циклического кода (7,4), задаваемого проверочным многочле- з 9 г Рис. 9.26.
Структурная схема колера цик- номЬ(х)=х 9х 9х 91,или, лического кода, задаваемого проверочным что то же самое, пРовеРочными миогочлеиомЬ(х)=х" 9хз Юхг 91 соотношениями (9.16). В исходном состоянии ключ находится в положении 1. В течение четырех тактов импульсы поступают в регистр, после чего ключ переводится в положение 2. При этом обратная связь замыкается. Начиная с пятого такта, формируются проверочные символы в соответствии с соотношениями (9.16). После седьмого такта все проверочные символы оказываются сформированными, ключ вновь переключается в положение 1.
Кодер готов к приему очередного сообщения. Символы кодовой комбинации поступают в канал, начиная с пятоГо такта. Корректирующая способность кода зависит от порождающего много- члена р(х). Поэтому его выбор очень важен при построении циклическою кода. Необходимо помнить, что степень порождающего многочлена должна быть равна числу проверочных символов.
Кроме того, многочлен р(х) должен делить двучлен х" 9 1. Обнаружение ошибок при использовании таких кодов заключается в делении многочлена Ь'(х) = Ь(х) + е(х), соответствующего принятой комбинации В = В9е, на р(х). Если остаток в(х) оказывается равным нулю, то считается, что ошибки нет, в противном случае фиксируется ошибка. Пусть необходимо построить код, обнаруживающий все одиночные ошибки. В этом случае многочлен ошибок имеет вид в(х) = х', где г = О, 1, ..., п — 1. Решение задачи заключается в нахождении такого многочлена р(х), чтобы многочлен е(х) не делился на р(х). Наиболее простым, удовлетворяющим этому требованию, является многочлен р(х) = х 9 1, Аналогично можно построить код, обнаруживающий ошибки большей кратности. Многочлен в(х) = (Ь(х) 9 е(х)) щось(р(х)) = в(х) той(р(х)) зависит только от многочлеиа ошибок в(х) и играет ту же роль, что и вектор- синдром.
Поэтому в принципе ошибки можно исправлять на основе таблицы соответствий между в(х) и в(х), хранящейся в памяти декодера„как при линейных нециклических кодах. Однако свойство цикличности позволяет существенно упростить процедуру декодирования. 583 9.
Радиотехнические системы передачи информауии Один из алгоритмов исправления ошибок основан на следукицих свойствах синдрома циклического кода. Пусть имеется циклический код с кодовым расстоянием г/, исправляющий все ошибки до кратности 1 = ((с/ — 1)/2] включительно, где ((г/ — 1)/2] — целая часть числа (г/ — 1)/2.
Тогда можно показать (133], что: — если исправляемый вектор ошибок искажает только проверочные символы, то вес синдрома будет меньше или равен / а сам синдром будет совпадать с вектором ошибок; — если вектор ошибки искажает хотя бы один информационный символ, то вес синдрома будет больше!; — если е(х) — остаток от деления многочлена Ь(х) на р(х), то остатком от деления многочлена Ь(х)х' на р(х) является многочлен е(х)х'шоб(р(х)], другими словами, синдром некоторого циклического сдвига многочлена Ь(х) является соответствующим циклическим сдвигом синдрома исходного многочлена, взятого по модулю р(х).
В качестве примера на рис. 9.27 представлена схема декодера для кода (7, 4) с порождающим многочленом р(х) = х' 9 х' Ю 1. Код имеет кодовое расстояние г/= 3, что позволяет ему исправлять все однократные ошибки. Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий для запоминания кодовой комбинации и ее циклического сдвига, и на устройство деления на многочлен р(х) для вычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферный регистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вес синдрома больше единицы, то декодер начинает проводить циклические сдвиги комбинации в буферном регистре при отсутствии новой комбинации на входе и одновременно вычислять их синдромы е(х)х'гпог((р(х)) в устройстве деления.
Если Рис. 927. Структурная схема декодера циклического кода с порож- дающим многочленомр(х) =х Юх Ю 1 584 9,5. Помехоуетойчивое кодирование и декодирование на некотором 1-м шаге вес синдрома окажется меньше двух, то ключ пере ходит в положение 2, обратные связи в регистре деления разрываются, При последующих тактах ошибки исправляются путем подачи содержимого ре гистра деления на вход сумматора по модулю 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме исправленная комбинация в буферном регистре возвращается в исходное положение (информационные символы будут занимать старшие разряды). Существуют и другие, более универсальные, алгоритмы декодирования.
К циклическим кодам относятся коды Хэмминга, которые являются примерами немногих известных совершенных кодов. Они имеют кодовое расстояние Н = 3 и исправляют все одиночные ошибки. Длина кода выбирается из условия 2"~ — 1 = п, которое имеет простой смысл: число различных ненулевых синдромов равно числу символов в кодовой последовательности. Так, существуют коды Хэмминга (2" — 1, 2" — г — 1), в частности коды (7, 4), (15, 1!), (31, 26), (63, 57) и т. д, Заметим, что ранее использованный многочлен р(х) = х' Оь х2 9 1 является порождающим для кода Хэмминга (7, 4).
Среди циклических кодов широкое применение нашли коды Боуза— Чоудхури — Хоквингема (БЧХ). Можно показать, что для любых целых положительных чисел т и 1< п12 существует двоичный код БЧХ длины и = 2 — 1 с кодовым расстоянием Ы ~ 21+ 1, причем число проверочных символов л — lс < т1 Для кодов БЧХ умеренной длины и ФМ при передаче символов можно добиться значительного выигрыша (4 дБ и более) [133]. Он достигается при скоростях ! /3 < Ьн < 314.
Прн очень высоких и очень низких скоростях выигрыш от кодирования существенно уменьшается. Иногда целесообразно использовать коды с несколько худшей корректирующей способностью по сравнению с лучшими известными кодами, но простые в реализации. К ним относятся коды, допускающие мажоритарное декодирование. Оно основано на возможности для некоторых циклических кодов выразить каждый информационный символ с помощью Д различных линейных соотношений. Решение о значении символа принимается по мажоритарному принципу. Для исправления всех ошибок до кратности 1 включительно необходимо иметь 2! + 1 независимых соотношений. В некоторой области значений параметров мажоритарные коды имеют корректирующую способность, незначительно уступающую корректирующей способности кодов БЧХ. В то же время нх реализация сравнительно проста. Покажем принцип мажоритарного декодирования на примере кода (7, 3) с проверочной матрнцей 585 9.
Радиотехнические системы передачи информации Ь~ Ьз Ь4 Ь5 Ье Ь7 1 О 1 1 О О О Н= (9.17) 1 1 1 О 1 О О 1 1 О О О 1 О О 1 1 О О О 1 Рассматриваемый код является циклическим с порождающим много- членом р(х) = х 9 х' 9 х' 9 1. Он имеет кодовое расстояние Ы = 4. Используя матрицу (9.17), можно записать следующие соотношения для символа Ь,: Ь! Ьз 9 Ь4 Ьз 9 Ье Ь 9 Ье. (9.18) С учетом (9.18) в декодере имеется возможность четырьмя разными способами вычислить первый информационный символ: Ь,' =Ь,; Ьа =Ьз 9Ь„; Ь,а' =Ь, 9Ье; Ь, =Ь5 9Ь,, (9.19) где Ь,Ь„...Ь вЂ” принятая кодовая комбинация. При отсутствии ошибок Ь,' = Ьп = Ьл' = Ь,'~, т. е. все проверочные соотношения (9.19) дают один и тот же результат.
При наличии одного ошибочного символа три проверочных соотношения дают правильное значение, а соотношение, в котором участвует ошибочный символ, дает неверный результат. Принимая решение по мажоритарному принципу, декодер выдает правильный символ Ьь Пусть ошибочно приняты два символа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
