Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Циклические коды

Читайте также:
  1. Азотсодержащие гетероциклические соединения
  2. Брана и циклические мультивселенные
  3. Задание 4.Циклические вычислительные процессы. Решение задач, содержащих вычисление конечных сумм и произведений
  4. КОРРЕКТИРУЮЩИЕ КОДЫ. ЦИКЛИЧЕСКИЕ КОДЫ
  5. Основы термодинамики. Адиабатический процесс. Циклические процессы
  6. Укороченные циклические коды
  7. Циклические алгоритмы

Циклическими кодами называют специальную группу кодов, для построения которых могут быть использованы циклические свойства квадратных матриц, а также коды, которые описываются неприводимыми, образующими (порождающими) многочленами (полиномами). Например, для кодовой комбинации 101101 полиномиальное представление таково:

A(X) = 1×x5 + 0×x4 + 1×x3 + 1×x2 + 0×x1 + 1 = x5 + x3 + x2 + 1.

Циклические коды относятся к систематическим (m, n) кодам, в которых контрольные k и информационные n разряды расположены на строго определенных местах. Общее количество разрядов: m = n + k.

Рассмотрим алгебру циклических кодов. Допустим, необходимо перемножить три многочлена (x3+x2+1)·(x3+x+1)·(x+1). Действия производятся также как в обычной алгебре, только сложение проводится по модулю 2. Операция умножения может быть произведена или в виде многочленов или в виде двоичных кодов.

или

Результат x7+1

При делении операция вычитания заменяется операцией сложения по модулю 2. Например, необходимо разделить многочлен седьмой степени на многочлен третей степени (x7+x5+x4+x+1) / (x3+x2+1). Операция деления может быть произведена или в виде многочленов или в виде двоичных кодов.

Циклический код получают следующим образом: заданный многочлен h(х) сначала умножается на одночлен хm-n, затем делится на образующий многочлен g(х). В результате получим

или

F(x) = Q(x) · g(x) = xm-nh(x) + R(X)

Таким образом, циклический код можно построить умножением кодовой комбинации h(х), являющейся заданной, на одночлен хm-n добавлением к этому произведению остатка R(х). При декодировании, принятую кодовую комбинацию необходимо разделить на g(x). Наличие остатка указывает на ошибку.

Образующий полином g(х) является сомножителем при разложении двучлена хm+1. Сомножителями разложения двучлена являются неприводимые полиномы.

Образующий полином выбирают следующим образом. По заданной кодовой комбинации определяют число контрольных символов из соотношения k = log2(т + 1) или по эмпирической формуле

k = log2((n + 1) + log2(n + 1))

Соотношение значений m, n, k можно определить по таблице.

Таблица 1 -- Зависимость между m, n и k.

m         9...15 17...31 33...63 65...127
n 1 2 3 4 5...11 12...26 27...57 28...120
k 2 3 3 3 4 5 6 7

Из таблицы неприводимых полиномов выбирают самый короткий многочлен со степенью, равной числу контрольных символов; его и принимают за образующий полином.

Таблица 2 -- Порождающие полиномы g(x) циклических кодов

Максимальная степень Порождающие полиномы g(x)
 

 

Пример. Пусть требуется закодировать кодовую комбинацию вида 1101, что соответствует полиному h(х) = х3 + х2 + 1. По формуле определяем число контрольных символов k = 3. Из таблицы возьмем полином g(х) = х3 + х + 1, т.е. 1011.

Решение:

Умножим h(х) на хk.

h(x)·xk = (x3 + x2 + 1)·x3 = x6 + x5 + x3 ® 11010000

Разделим полученное произведение на образующий полином g(х)

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х)·хk. В результате получим закодированное сообщение:

F(x) = (x3 + x2 + 1)·(x3 + x + 1) = (x3 + x2 + 1)·x3 + 1 ® 1101001

В полученной кодовой комбинации циклического кода информационные символы h(х) = 1101, а контрольные R(х) = 001. Закодированное сообщение делится на образующий полином без остатка.

Сообщение, которое закодировано, является одной из комбинаций 4-разрядного кода, так как весь ансамбль сообщений (вся группа) содержит M = 16 сообщений. Это значит, что если все сообщения передаются в закодированном виде, то каждое из них необходимо кодировать так же, как и комбинацию h(x) = 1101. Однако выполнять дополнительные 15 расчетов (а в общем случае 2m-n-1 расчет) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.

Образующая матрица составляется на основе единичной транспонированной, к которой справа дописывается матрица контрольных разрядов.

Матрица контрольных разрядов получается из остатков от деления единицы с нулями на образующий полином g(x). Комбинации единиц с нулями представляют собой векторы ошибок: 00...01, 00... 10, 00... 1...0 и т.д. Каждому вектору ошибок будет соответствовать свой остаток (опознаватель).

                   
                   
                1-й остаток  
                2-й остаток  
                   
                3-й остаток  
                   
                4-й остаток  

 

Строки матрицы это 4 комбинации циклического кода, т.е. столько, сколько информационных разрядов, а так как в 4-разрядном двоичном коде всего M = 24 = 16 кодовых комбинаций, то остальные 11 ненулевых комбинаций находятся суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы, например

1 Å 3 Å 4 = 1101001; 2 Å 4 = 1010011.

 

Конец формы


Дата добавления: 2015-07-16; просмотров: 57 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Понятие комбинированного алгоритма| Декодирование циклических кодов

mybiblioteka.su - 2015-2024 год. (0.007 сек.)