Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
13.3. ЦИКЛИЧЕСКИЕ КОДЫЦиклические коды являются разновидностью линейных групповых кодов и относятся к систематическим кодам. Первоначально были созданы для упрощения процедуры декодирования. Однако высокая эффективность к обнаружению ошибок таких кодов обеспечила их широкое применение на практике. Двоичный вектор циклического кода удобно рассматривать не как комбинацию нулей и единиц, а в виде полинома некоторой степени
где х — основание системы счисления, Пример. Двоичный вектор
Представление двоичных векторов в виде полиномов позволяет свести действие над векторами к действиям над многочленами. При этом: сложение многочленов сводится к сумме по модулю 2 коэффициентов при равных степенях переменной умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2; деление осуществляется по правилам деления степенных функций, при этом операция вычитания заменяется суммированием по модулю 2. Пример. Найти сумму многочленов
Найти произведение многочленов
Выполнить деление многочленов
Основным свойством циклических кодов является следующее: если вектор принадлежит циклическому коду, то любой вектор, полученный из рассматриваемого с помощью циклических сдвигов, также принадлежит циклическому коду. Идея построения циклических кодов базируется на понятии неприводимого многочлена. Многочлен называется неприводимым, если он делится только на самого себя и на единицу, и не делится ни на какой другой многочлен. Иными словами, неприводимый многочлен нельзя представить в виде произведения многочленов низших степеней. На неприводимый многочлен без остатка делится многочлен Примеры неприводимых многочленов:
Векторы циклического кода строятся в соответствий со следующими правилами. Пусть
где Таким образом, любой вектор циклического кода может быть образован умножением некоторого вектора натурального двоичного кода на одночлен степени Пример. Вектор натурального двоичного кода имеет вид
Представим вектор
Тогда
В результате деления полинома
Циклический код, как и всякий систематический код, удобно задавать в матричном виде с помощью порождающей матрицы
где Зададим порождающую матрицу Очевидно, заготовка для порождающей матрицы имеет вид
Для нахождения строк проверочных разрядов матрицы
Длина вектора циклического кода (см. скан) В результате получаем порождающую матрицу С:
Любой вектрр циклического кода получается как сумма по моду Таблица 13.5
Пример. Построить все векторы циклического кода, заданного порождающей матрицей
Код представлен в табл. 13.5. Необходимо отметить, что каждый циклический код, заданный некоторой порождающей матрицей, можно представить в нескольких вариантах, отличающихся друг от друга длиной Пример, Циклический код задан своей порождающей матрицей
Вычеркнем из шесть последних строк и шесть первых слева столбцов. Получим порождающую матрицу
Характеристики (в смысле обнаружения ошибок) полученного кода такие же, как и циклического кода, представленного порождающей матрицей Построение циклических кодов с заданными параметрами связано с выбором образующего неприводимого полинома. Образующий полином выбирается исходя из следующего условия: степень полинома должна быть равна числу проверочных разрядов циклического кода. На практике часто возникает задача построения циклического кода заданной мощности и заданной обнаруживающей и корректирующей способностей. Рекомендации для построения кода следующие: 1. Так как мощность
2. Оптимальное число проверочных разрядов 3. По справочникам находятся все неприводимые полиномы степени 4. Для одного из непроводимых многочленов (следует выбирать многочлен с максимальным числом членов) степени
где 5. Построенная порождающая матрица проверяется на выполнение следующих условий: а) вес в смысле Хэмминга любого вектора б) вес в смысле Хэмминга проверочного вектора, являющегося суммой по модулю 2 любых двух проверочных векторов
6. Если порождающая матрица циклического кода удовлетворяет всем приведенным условиям, то выписываются все векторы циклического кода и определяется Построим циклический код мощностью 16 и корректирующей с по собностью I. В соответствии с первым пунктом рекомендаций по построению циклических кодов, определяем значение Для
3» По справочникам находим все неприводимые полиномы степени
4. Выбираем в качестве образующего полином
Каждый информационный вектор из матрицы
Определяем полностью все векторы порождающей матрицы, используя формулу
Так как длина вектора циклического кода
Аналогично находим все остальные векторы порождающей мат рицы
Таблица 13.6
В результате получена порождающая матрица С? циклического кода
5. Полученная порождающая матрица удовлетворяет всем необходимым условиям. Поэтому строим циклический код полностью (табл. 13.6). Как следует из таблицы, код имеет Замечания. При использовании неприводимого полинома
Обнаружение ошибок с помощью циклических кодов производится следующим образом. Любой вектор циклического кода делится на образующий полином без остатка. Поэтому критерием наличия ошибки в векторе циклического кода является появление ненулевого остатка от деления вектора циклического кода на образующий полином. Ненулевой остаток является опознавателем ошибки в векторе циклического кода, однако его вид не указывает на место расположения ошибки в кодовом векторе. Исправление ошибок базируется на следующем алгоритме: 1. Принятый кодовый вектор разделить на образующий полином. 2. Подсчитать число единиц в полученном остатке. Если число единиц не превышает корректирующей способности кода, то принятый вектор сложить по модулю 2 с полученным остатком. Результат суммирования даст исправленный кодовый вектор. Если число единиц остатка больше корректирующей способности кода, то осуществить циклический сдвиг искаженного вектора влево на один разряд, а затем произвести деление на образующий полином. Если полученный остаток содержит единиц не больше корректирующей способности циклического кода, то произвести суммирование сдвинутого циклически вектора с остатком. Результат суммирования сдвинуть циклически на один разряд вправо. Полученный вектор уже не содержит ошибок и является вектором циклического кода. 3. Если после первого циклического сдвига и последующего деления остаток содержит единиц больше, чем корректирующая способность кода, то повторять процедуру Пусть циклический код задан своей порождающей матрицей С и образующим полиномом
Код имеет
Полученный в результате деления остаток Осуществляем деление на
Полученный остаток Осуществляем деление на
Полученный остаток снова содержит две единицы, поэтому делаем еще один циклический сдвиг влево на один разряд и получаем
Остаток Определим необнаруживаемые циклическими кодами ошибки. Представим векторы одиночных ошибок (длина вектора ошибки равна длине вектора циклического кода) в виде единичной транспонированной матрицы
Тогда матрица ошибок М имеет вид
Построение матрицы
Матрицу остатков, являющуюся частью матрицы М, разобьем на две части: первая содержит остатки от деления одночленов
поэтому матрица Из общего количества 35 трехкратных ошибок не обнаруживается всего лишь 7 ошибок, Аналогично, четырехкратных необнаруживаемых ошибок будет также Аналогичный линейный групповой код, заданный порождающей матрицей
и уравнениями
очевидно имеет матрицу ошибок
полностью аналогичную матрице одиночных ошибок циклического кода. Следовательно, в плане необнаруживаемых ошибок приведенные два кода полностью эквивалентны. Рассмотрим аппаратурную реализацию схем обнаружения ошибок циклических кодов. Так как обнаружение ошибок в них осуществляется по наличию ненулевого остатка от деления вектора циклического кода на образующий полином, то схема обнаружения ошибок представляет собой схему деления полинома на полином. Такие схемы принадлежат к особому классу схем, называемых линейными, так как аппаратурно они могут реализоваться на элементах задержки (О-триггерах) и логических элементах суммы по модулю 2.
Рис. 13.2
Рис. 13.3
Рис. 13.4
|
1 |
Оглавление
|