Материал: Телекоммуникационные системы и сети - КНИГА

Алгоритм формирования проверочных элементов а₅, а₆, а₇ может быть задан матрицей, называемой проверочной. Эта матрица содержит r строк и n столбцов. Применительно к сформированному нами коду (7,4) она имеет вид:

Единицы, расположенные на местах, соответствующих информационным элементам матрицы Н_(7,4), указывают на то, какие информационные элементы должны участвовать в формировании проверочного элемента. Единица на месте, соответствующем проверочному элементу, указывает, какой проверочный элемент получается при суммировании по модулю два информационных элементов. Так, из первой строки следует равенство

Процедура обнаружения ошибок основана на использовании проверок (12.4)-(12.6). Очевидно, что проверочные элементы, сформированные из принятых информационных, при отсутствии ошибок должны совпадать с принятыми проверочными.

Пример 12.3. Переданная кодовая комбинация имеет вид 1000111 (первая строка матрицы (12.3)). В результате действия помех на приемном конце имеем . Произведем проверки (12.4)-(12.6):

, (12.7)

(12.8)

(12.9)

В то же время , т.е. , что говорит о наличии ошибок в принятой кодовой комбинации. При отсутствии в принятой кодовой комбинации ошибок , ,

Комбинация b₃b₂b₁ называется синдромом (проверочным вектором). Равенство нулю всех элементов синдрома указывает на отсутствие ошибок или на то, что кодовая комбинация принята с ошибками, которые превратили ее в другую разрешенную. Последнее событие имеет существенно меньшую вероятность, чем первое.

Вид ненулевого синдрома определяется характером ошибок в кодовой комбинации. В нашем случае вид синдрома зависит от местоположения одиночной ошибки. В табл. 12.2 отражено соответствие между местоположением одиночной ошибки для кода, заданного матрицей (12.3), и видом синдрома.

Таблица 12.2. Местоположение ошибки и вид синдрома

Номер элемента, в котором произошла ошибка	1	2	3	4	5	6	7
Вид синдрома	111	101	110	011	001	010	100

Таким образом, зная вид синдрома, можно определить место, где произошла ошибка, и исправить принятый элемент на противоположный.

Пример 12.4. Передавалась кодовая комбинация 1000111. Принята кодовая комбинация 0000111. Синдром имеет вид 111. В соответствии с табл. 12.2 исказился первый элемент (а₁). Изменим первый элемент на противоположный:

Полученная в результате исправления ошибки кодовая комбинация совпадает с переданной.

Рассмотренный код (7,4) гарантированно обнаруживает двухкратные ошибки, а исправляет только однократные ошибки.

Циклические коды. В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, п-элементная кодовая комбинация записывается в виде

A(x) = a_n_-1xⁿ^-1 + a_n_-2xⁿ^-2 + … + a₁x + a₀,

где a_i = {0,1}, причем а_i = 0 соответствуют нулевым элементам комбинации, а а_i = 1 - ненулевым. Например, комбинациям 1101 и 1010 соответствуют многочлены A₁(х) = х³ + х² +1 и А₂(х) = х³ + х.

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

A₁(х) + A₂(х) = (х³ + х² +1) + (х³ + х) = х² + х +1,

поскольку х³ + х³ = х³(11) = 0.

Рассмотрим операцию деления на следующем примере:

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

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

Найдем алгоритмы построения циклического кода, удовлетворяющего перечисленным выше условиям. Задан полином Р(х) = a_r_-1x^r + a_r_-2x^r^-1 + ... + 1, определяющий корректирующую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический.

Обозначим многочлен, соответствующий комбинации простого кода, Q(x). Возьмем произведение Q(х)x^r разделим его на Р(х). В результате получим многочлен G(x) и остаток R(x)/P(x):

(12.10)

Умножим левую и правую части на Р(х), тогда (12.10) перепишется в виде

Q(x)x^r = G(x)P(x) + R(x) (12.11)

Перепишем равенство (12.11) в виде

G(x)P(x) = Q(x)x^r + R(x) (12.12)

Левая часть (12.12) делится без остатка на Р(х), значит, без остатка делится и правая часть. Из (12.12) вытекают два способа формирования комбинаций циклического кода: путем умножения многочлена G(x) на Р(х) и путем деления Q(х)x^r на Р(х) и приписывания к Q(x)x^r остатка от деления R(х).

Пример 12.5. Задан полином G(x) = x³ + x, соответствующий комбинации простого кода. Сформировать комбинацию циклического кода (7,4) с производящим полиномом Р(х) = х³+ х²+ 1. Можно получить комбинацию циклического кода в виде G(x)P(x) = = (х³ + х)(х³ + х² +1) = х⁶ + х⁵ + х⁴ + х. Однако в полученной комбинации нельзя отделить информационные элементы от проверочных, и код получается неразделимым.

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

3) (х⁶ + х⁴+1) - комбинация циклического кода, полученная методом деления на производящий полином. Она может быть переписана в виде 1010001. Первые четыре элемента - информационные, последние три - проверочные, т.е. полученный код - разделимый.

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки и исправить ее.

Циклические коды достаточно просты в реализации, обладают высокой корректирующей способностью (способностью исправлять и обнаруживать ошибки) и поэтому рекомендованы МСЭ-Т для применения в аппаратуре ПД. Согласно рекомендации V.41 в системах ПД с ОС рекомендуется применять код с производящим полиномом Р(х) = х¹⁶ + х¹² + х⁵+1.

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

где P_ОШ - вероятность неправильного приема единичного элемента; k - число элементов в комбинации простого кода. При применении систематических корректирующих кодов к исходной кодовой комбинации добавляются проверочные элементы, позволяющие исправлять или обнаруживать ошибки. Так, если код используется в режиме исправления ошибок и кратность исправляемых ошибок t_и.ош, то вероятность неправильного приема кодовой комбинации

В результате применения корректирующего кода в режиме ис-правления ошибок вероятность ошибки уменьшается в К_и раз: . Однако это достигается за счет увеличения затрат на реализацию системы и снижения скорости передачи информации. Если в системе с простым кодом скорость равна С_п, то в системе с корректирующим кодом скорость - коэффициент, характеризующий потери скорости вследствие введенной в код избыточности. Чем больше избыточность (меньше ). тем меньше скорость передачи информации, т.е. тем меньше в единицу времени передается полезной информации.

Качество реальных каналов во времени меняется, и если заданы требования на верность передачи, то необходимо ввести такую избы-точность, которая обеспечивала бы заданную верность даже при са-мом плохом качестве канала. Напрашивается мысль о целесообраз-ности изменения избыточности, вводимой в кодовую комбинацию, по мере изменения характеристик канала связи. Системы, в которых меняется избыточность с изменением качества канала, относятся к чис-лу адаптивных. Одним из типов адаптивных систем являются систе-мы с обратной связью. В этих системах между приемником и пере-датчиком помимо основного (прямого) канала имеется вспомогательный (обратный).

Источник: https://tut-files.ru/previewfile/161622

Смотрите также:







Изложение содержания дела, по которому приняты судебные постановления
_-___-~1
_1-тема-СтрМетал
_10_Эмиль Золя для эл версии