www.chms.ru - вывоз мусора в Балашихе 

Динамо-машины  Сигналы и спектры 

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 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358

Линия решений

Область 1

Область 2

Рис. 6.13 Возможности определения и исправления ошибок: а) принятый вектор Г),- б) принятый вектор Гг, в) принятый вектор Гз

В примере, приведенном на рис. 6.13, критерий принятия решения может быть следующим: выбрать и, если г попадает в область 1, и выбрать V, если г попадает в область 2. Выше показывалось, что такой код (при = 5) может исправить две ошибки. Вообще, способность кода к исправлению ошибок t определяется, как максимальное число гарантированно исправимых ошибок на кодовое слово, и записывается следующим образом [4]:

(6.44)

Здесь Ы означает наибольшее целое, не превышающее х. Часто код, который исправляет все искаженные символы, содержащие ошибку в t или меньшем числе бит, также может исправлять символы, содержащие г +1 ошибочных бит. Это можно увидеть на рис. 6.11. В этом случае f/, = 3, поэтому из уравнения (6.44) можно видеть, что исправимы все модели ошибки из г = 1 бит. Также исправима одиночная модель ошибки, содержащая t+l (т.е. 2) ошибочных бит. Вообще, линейный код (и,к), способный исправлять все символы, содержащие t ошибочных бит, может исправить всего 2 * моделей ошибок. Если блочный код с возможностью исправления символов, имеющих ошибки в t бит, применяется для исправления ошибок в двоичном симметричном канале с вероятностью перехода р, то вероятность ошибки сообщения Pf (вероятность того, что декодер совершит неправильное декодирование и и-битовый блок содержит ошибку) можно оценить сверху, используя уравнение (6.18):

л = / + 1

Jn - \ -J

ра-Р)

(6.45)



Оценка переходит в равенство, если декодер исправляет все модели ошибок, содержащие до t ошибочных бит включительно, но не модели с числом ошибочных бит, большим t. Такие декодеры называются декодерами с ограниченньш расстоянием. Вероятность ошибки в декодированном бите Рв зависит от конкретного кода и декодера. Приближенно ее можно выразить следующим образом [5]:

Рв-Т . р\1-р) ~ (6.46)

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

е = , ,-1. (6.47)

Блочный код с минимальным расстоянием rf гарантирует обнаружение всех модели ошибок, содержащих rf - 1 или меньшее число ошибочных бит. Такой код также способен обнаружить и более длинную часть модели ошибки, содержащую rf , или более ошибок. Фактически код (я, к) может обнаружить 2 - 2* моделей ошибок длины п. Объясняется это следующим образом. Всего в пространстве 2 п-кортежей существует 2 - 1 возможных ненулевых моделей ошибок. Даже правильное кодовое слово - это потенциальная модель ошибки. Поэтому всего существует 2* - 1 моделей ошибки, которые идентичны 2*-1 ненулевым кодовым словам. При появлении любая из этих 2*-1 моделей ошибки изменяет передаваемое кодовое слово U, на другое кодовое слово Uj. Таким образом, принимается кодовое слово и его синдром равен нулю. Декодер принимает Ц за переданное кодовое слово, и поэтому декодирование дает неверный результат. Следовательно, существует 2* -1 необнаружимых моделей ошибки. Если модель ошибки не совпадает с одним из 2* кодовых слов, проверка вектора г с помощью синдромов дает ненулевой синдром и ошибка успешно обнаруживается. Отсюда следует, что существует ровно 2 - 2* выявляемых моделей ошибки. При больших п, когда 2* laquo; 2 , необнаружи-мой будет только незначительная часть моделей ошибки.

6.5.3.1. Распределение весовых коэффициентов кодовых слов

Пусть Aj - количество кодовых слов с весовым коэффициентом j в линейном коде (п, к). Числа Ло. А\, ...,А называются распределением весовых коэффициентов этого кода. Если код применяется только для обнаружения ошибок в двоичном симметричном канале, то вероятность того, что декодер не сможет определить ошибку, можно рассчитать, исходя из распределения весовых коэффициентов кода [5]:

Po=Y,,p\l-pr- , (6.48)

; = 1

где р - вероятность перехода в двоичном симметричном канале. Если минимальное расстояние кода равно пши значения отЛ) до , равны нулю.



Пример 6.5. Вероятность необнаруженной ошибки в коде

Пусть код (6, 3), введенный в разделе 6.4.3, используется только для обнаружения наличия ошибок. Рассчитайте вероятность необнаруженной ошибки, если применяется двоичный симметричный канал, а вероятность перехода равна 10 .

Решение

Распределение весовых коэффициентов этого кода выглядит следующим образом: Аа=\, А] = А2 = О, Лз = 4, А5 = О, Аб = 0. Следовательно, используя уравнение (6.48), можно записать следующее:

P,i = 4p\l-pf + 3p\l-pf. Для р = 10 вероятность необнаруженной ошибки будет равна 3,9 х 10 . 6.5.3.2. Одновременное обнаружение и исправление ошибок

Возможность исправления ошибок следует из гарантированного максимума (f), где t определяется уравнением (6.44), для одновременного обнаружения класса ошибок. Код можно использовать для одновременного исправления а и обнаружения (3 ошибок, причем а lt;Р, а минимальное расстояние кода дается следующим выражением [4]:

J , gt;a + p + l. (6.49)

При появлении t или меньшего числа ошибок код способен обнаруживать и исправлять их. Если ошибок больше г, но меньше е+1, где е определяется уравнением (6.47), код может определять наличие ошибок, но исправить может только некоторые из них. Например, используя код с d,, = 7, можно выполнить обнаружение и исправление со следующими значениями аир.

Обнаружение (Р) Исправление (а)

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

6.5.4. Визуализация пространства 6-кортежей

На рис. 6.14 визуально представлено восемь кодовых слов, фигурирующих в примере из раздела 6.4.3. Кодовые слова образованы посредством линейных комбинаций из трех независимых 6-кортежей, приведенных в уравнении (6.26); сами кодовые слова образуют трехмерное подпространство. На рисунке показано, что такое подпространство полностью занято восемью кодовыми словами (большие черные круги); координаты подпространства умышленно выбраны неортогональными. На рис. 6.14 предпринята попытка изобразить все пространство, содержащее шестьдесят четыре 6-кортежей, хотя точно нарисовать или составить такую модель невозможно. Каждое кодовое слово окружают сферические слои или оболочки. Радиус внутренних непересекающихся слоев - это расстояние Хэмминга, равное 1; радиус внешнего слоя - это расстояние Хэмминга, равное 2. Большие расстоя-

372 I Глава fi Канапкнпр к-ппмппиянмй- чяптк 1



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 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358