Циклические коды, их возможности и чем они определяются?

Определение. Циклический код (ЦК) относится к группе линейных кодов, оперирующих не с двоичными числами, а двоичными многочленами (т.е. с двоичным числом, записанным не коэффициентами, а основаниями).

Пример ЦК 1011

Двоичные многочлены, которые не могут быть разделены без остатка, называются неприводимыми Многочленами.

Пример неприводимых многочленов:

- многочлен десятичного числа 3: Р(х) = х + 1;

- многочлен десятичного числа 7: Р() = ;

- многочлен десятичного числа 11: Р() = ; и далее чисел 13, 15,19, 25, 31, 41, 47….

Свойства операций над двоичными многочленами:

1. Суммирование и вычитание для них тождественны, т.к. суммирование двоичных чисел происходит по модулю 2 (т.е. суммирование разрядов 1 и 1 дает 0).

10101110

+__ 10101

2. Перенос за знак равенства знака не меняет.

3. Умножение двоичных многочленов аналогично умножению двоичных чисел, только суммирование производится по модулю 2.

1011

*10101

+10110

10110___

4. При умножении многочлена на одночлен n-й степени – это добавление нулей для двоичного числа.

(10101)(1000)=10101000

5. Деление многочленов аналогично делению двоичных чисел, только разность заменяется разностью по модулю 2.

Получение несистематического циклического кода:

Двоичную рабочую комбинацию умножить на образующий (неприводимый) многочлен.

Q(x) – рабочая комбинация; P(x^k) – образующий многочлен. - циклический код.

Поделим ЦК на образующий многочлен P(x^k) без остатка, получим рабочую комбинацию, если с остатком – ошибка в принятой комбинации.

Получение систематического (расположение контрольных символов в коде известно) циклического кода:

- выбираем образующий многочлен k-ой степени P(x^k);

- рабочую двоичную комбинацию Q(x) умножим на x^k;

- делим на P(x^k): , где целое число, остаток;

- прибавляем : , где - двоичная комбинация, R(x) – контрольный остаток, F(x) – циклический код.

Выбор образующего многочлена

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

2. Число ненулевых членов образующего многочлена должно быть не меньше кодового расстояния.

Если:

d = 2 (код обнаруживает одиночную ошибку), то выбирают P(x) = x + 1

d = 3, то выбирают исходя из условия n = 2^k – 1 многочлен в степени k как можно короче, но так чтобы число ненулевых членов многочлена было не меньше кодового расстояния

d = 4, то , где P₁(x) – многочлен при d = 3.

для d > 4 – выбор многочлена затруднен, используют коды БЧХ

Коды БЧХ

Их общая разрядность нечетная. Образующий многочлен определяется как наименьшее общее кратное:

P(x) = НОК[P₁(x^L)…P₁(x^L)], где S – кратность исправляемых ошибок (находится из выраж. d = 2S + 1)

L – степень обр. мн. (находится из n = 2^L -1, n – разрядность кода)

S

Эти циклические коды БЧХ исправляют разрозненное число ошибок, не справляются когда их много.

Коды Файра

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

Образующий многочлен: P(x) = P₁(x) (x ^Z +1),

где P₁(x) – неприводимый многочлен степени S: P₁(x) = P(x^S);

z = S + r – 1, z не должно делиться на (2 ^r - 1);

k = S + z – число контрольных символов,

А разрядность кода определяется n = наибольшее общее кратное от Z и 2^S-1

Cверточные коды (коды кодирования непрерывного цифрового потока)

Для исправления блоков ошибок. Сверточные коды – коды, в которых число контрольных символов k равно m – числу рабочих символов. При этом k и m чередуются в своей передаче.

Кодирование заключается в том, что надо найти характер контрольных символов и расставить их. Характер контрольных символов определяется как:

если b=3 (шаг квантования), то K=m₁+m₄… и т.д. Контрольный символ расставляется так, чтобы он находился в защищенной зоне (защитный интервал (6b + 1)t_и). Задерживается по отношению к своему, рабочему символу на 6b+1

Декодирование кода заключается в том, что поток символов раздваивается на рабочие контрольные символы. По рабочим символам определяется проверочные символы как и эти символы сравниваются с принятыми контрольными символами. Если они одинаковые, то получаем 0 Þ правильно приняли.

Декодирование ЦК

Алгоритмический или программный способ:

1. Принимается циклический кода, проверяется на наличие ошибки делением на образующий многочлен. Если делится без остатка, то ошибок нет, при наличии остатка – есть ошибка.

а) если в остатке число единиц меньше или равно кратности исправляемых ошибок, то к принятому коду прибавляется остаток (суммирования по модулю 2) – исправили ошибку.

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

2. Если остаток от деления имеет число единиц меньше кратности ошибок, то он суммируется с делимым и сумма сдвигается вправо на 1 разряд.

3. Если остаток имеет число единиц больше кратности ошибок, то делимое сдвигается еще на 1 разряд влево, процедура продолжается.

4. Если число сдвигов превышает (n-1), где n – разрядность, то такая комбинация неисправима, т.е. ошибок больше чем исправлений.

Мажоритарный или аппаратный способ:

Поэлементное сравнения каждого разряда по найденной проверочной таблице (строятся на основе проверочной матрицы линейного циклического кода).

 

49.Организация доступа к узкополостным цифровым сетям интегрального об­служивания (У-ЦСИО).

Цифровая Сеть с Интегрированным Сервисом (ISDN - Integrated Service Digital Network).

Основной целью ISDN объединение в рамках одной сети голоса, звука, изображения и цифры.

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

Существует два подхода к организации доступа:

1. Абонент – Абонент

2. Пользователь – Сеть

Структура выхода в сеть:

Обозначения: V –абонентская линия, NT-1 – терминал физического уровня передачи, NT-2 – терминал сетевого и канального уровня, ОС – оконечное оборудование, цифровое оборудование (ПК, цифр автомат), ОА – адаптер оборудования между оконечными станциями.

Технологии передачи:

1) Низкоскоростная технология: 2 В + 1 Д,

2) 30 В + 1 Д

где B – информационный канал 64 кбит/сек, Д – управленческий канал 16 кбит/сек.

Физический уровень:

квазитроичный код технология передачи сигналов: X.25

Кадр передачи – 48 бит:

F L B1 L D1 L Fa L B2 L D2 L B3 L D3 L B4 L D4 L

где F и L - синхронизация кадра (F – синхронизация с положит. импульса, L – с отрицат имп.)

B – 8 бит информации,

L – выравнивающие биты,

D – управленческая информация (4 бита),

Fa – вспомогательный бит кодировки