Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1092038), страница 114
Текст из файла (страница 114)
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) дают один и тот же результат.
При наличии одного ошибочного символа три проверочных соотношения дают правильное значение, а соотношение, в котором участвует ошибочный символ, дает неверный результат. Принимая решение по мажоритарному принципу, декодер выдает правильный символ Ьь Пусть ошибочно приняты два символа. Если они входят в различные проверочные соотношения, то два проверочных соотношения дадут значение 1, а два других — значение О. В этом случае декодер выдает сигнал отказа от декодирования. Если оба искаженных символа входят в одно проверочное соотношение, то все четыре проверки дают один и тот же результат. Декодер выдает правильный символ Ьь Аналогично определяются остальные информационные символы, Проверочные соотношения для символов Ь.
и Ь, получаются из (9.19) циклической перестановкой: Ь, = Ь., Ь, Ь4 9 Ьм Ь, Ьз 9 Ь7, Ьз - ~е Схема декодера (рис. 9.28) состоит из сдвигающего регистра, сумматоров по модулю 2 и мажоритарного элемента М. Простота ее обусловлена 586 9.5. Помехоуетойчивое кодирование и декодирование Рис.
9.28. Структурная схема декодера циклического мажоритарного кода (7, 3) тем, что в данном случае каждый символ кодовой комбинации участвует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодом с разделенными проверками. Мажоритарное декодирование возможно и тогда, когда один и тот же символ участвует в нескольких проверочных соотношениях. Однако алгоритм декодирования усложняется, Идея построения итперативных кодов заключается в следующем. Информационные символы записываются в виде таблицы из 1е, столбцов и ~т строк. К каждой строке таблицы дописываются п~ — К проверочных символов в соответствии с некоторым кодом (пь lс~).
Затем к каждому из п~ столбцов полученной таблицы добавляют п, — /г, проверочных символов в соответствии с некоторым кодом (пн |сг). Таким образом строится код длиной п = п,п2 с числом информационных символов 7е = Й~lеь Можно показать, что для полученного двумерного итеративного кода кодовое расстояние е! равно 4обь где 4 и е!з — кодовые расстояния для кодов (пн /с1) и (пь lе2) соответственно. Кодовая комбинация двумерного итеративного кода обычно передается последовательно по строкам, начиная с первой. Соответственно, декодирование ведется сначала по строкам, а затем, после приема всего двумерного блока, — по столбцам. Проиллюстрируем построение кодовой комбинации двумерного итеративного кода. Пусть информационные символы записаны в виде таблицы 1 ! 1 О 1 О 1 О О 1 О О 1 ! О 1 587 9. Радиотехнические системы передачи информации В качестве кодов (пь /г,) и (п,, /г,) будем использовать коды с проверкой на четность. Тогда кодовая комбинация будет иметь вид Внешний кодер Внутренний кодер Внешний декодер Внутренний декодер Канал Вход Выход Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
