Главная страница  История развития электросвязи 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [ 72 ] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215

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

Номер элемента, в котором произошла ошибка

Вид синдрома

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

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

0000111 1000000. 1000111

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

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

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

+... + а,х+ао,

где а, = {0,1}, причем а, = О соответствуют нулевым элементам комбинации, а а, = 1 - ненулевым. Например, комбинациям 1101 и 1010 соответствуют многочлены Д (х) = + +1 и 2 (х) = х + х.

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

Д (x)-(-/\2(x) = (x-(-x+l) + (x-(-x)= x + x+l,

поскольку X® + X® = х (1 ©1) = О.

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

x + x + xx + l х + х+1

х + х + х х + х+1

х + х + х

х + х + х

х + х+1

х + х+1



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

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

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

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

= G(x)-b. (12.10)

Р(х) Р(х)

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

Q(x)x = G(x)P(x)+R(x). (12.11)

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

G(x)P(x) = Q(x)x + R(x). (12.12)

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

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

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



х + х +1

х + х + х

x + x+l

х + х + х

х + х + х

х + х

х + х +1

R(x)=1

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

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

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

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

Po:=i-(i-Poj.

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

Ро:= t Oo.(i-Poj .

1) G(x)x=(x + x)x = x + x*; 2)



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [ 72 ] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215

© 2000 - 2018 ULTRASONEX-AMFODENT.RU.
Копирование материалов разрешено исключительно при условии цититирования.