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

3. Полагается, что модели ошибки вызываются искажениями в канале.

4. Полученный исправленный вектор, или кодовое слово, определяется как и = г + е. Можно сказать, что в результате вычитания определенных ошибок мы восстановили верное кодовое слово. {Замечание: в арифметических операциях по модулю 2 операция вычитания равносильна операции сложения.)

6.4.8.3. Локализация модели ошибки

Возврашаясь к примеру из раздела 6.4.3, мы составляем матрицу из 2* = шестидесяти четырех 6-кортежей, как это показано на рис. 6.11. Правильные кодовые слова - это восемь векторов в первой строке, а исправимые модели ошибки - это семь ненулевых образующих элементов классов смежности в первом столбце. Заметим, что все однобитовые модели ошибки являются исправимыми. Отметим также, что после того, как исчерпываются все однобитовые модели ошибки, еше остаются некоторые возможности для исправления ошибок, поскольку учтены еще не все шестьдесят четыре 6-кортежа. Имеется один образующий элемент класса смежности, с которым ничего не сопоставлено; а значит, остается возможность исправления еще одной модели ошибки. Эту модель ошибки (один из п-кортежей в оставшемся образующем элементе класса смежности) можно выбрать произвольным образом. На рис. 6.11 эта последняя исправимая модель ошибки выбрана равной комбинации с двумя ошибочными битами 010001. Декодирование будет правильным тогда и только тогда, когда модель ошибки, введенная каналом, будет одним из образующих элементов классов смежности.

000000

110100

011010

101110

101001

011101

110011

000111

000001

1I010I

011011

101111

totooo

оиюо

uooto

000110

000010

110110

011000

101100

101011

011111

110001

000101

000100

110000

011110

101010

101101

011001

110111

000011

001000

111100

010010

100110

100001

010101

111011

001111

010000

100100

001010

111110

111001

001101

100011

010111

100000

010100

111010

001110

001001

111101

010011

100111

010001

100101

001011

111111

111000

001100

100010

010110

Рис 6. п. Пример нормальной матрицы для кода (6, 3)

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

1 О О

S = e

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



Таблица 6.2. Таблица соответствия синдромов

Модель ошибки

Синдром

000000

000001

000010

000100

001000

010000

100000

010001

6.4.8.4. Пример исправления ошибки

Как говорилось в разделе 6.4.8.2, мы принимаем вектор г и рассчитываем его синдром с помощью выражения S = гН. Затем, используя таблицу соответствия синдромов (табл. 6.2), составленную в предыдущем разделе, находим соответствующую модель ошибки, которая является оценкой ошибки (далее будем обозначать ее через ё). Затем декодер прибавляет ё к г и оценивает переданное кодовое слово U .

й = г + ё = (и + е)+ё = и + (е + ё) (6.40)

Если правильно вычислили ошибку: ё = е, тогда оценка U совпадает с переданным кодовым словом и. С другой стороны, если оценка ошибки неверна, декодер неверно определит переданное кодовое слово и мы получим необнаружимую ошибку декодирования.

Пример 6.4. Исправление ошибок

Пусть передано кодовое слово U = 101110 из примера в разделе 6.4.3 и принят вектор г = 001110. Нужно показать, как декодер, используя таблицу соответствия синдромов (табл 6 2), может исправить ошибку.

Решение

Рассчитывается синдром г.

S= [001 1 10] Н=[10 0]

С помощью табл. 6.2 оценивается модель ошибки, соответствующая приведенному выше синдрому.

ё=1 0 0 0 0 0

Исправленный вектор равен следующему:

и = г+ё=

=00111 0+1 00000=.

= 10 1110

Поскольку оцененная модель ошибки в этом поимере совпадает с действительной моделью ошибки, процедура исправления ошибки дает U = U.

Можно видеть, что процесс декодирования искаженного кодового слова путем предварительного обнаружения и последующего исправления ошибки можно сравнить с аналогичной

б 4 Линрйныр блочный копы л, 365



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

6.4.9. Реализация декодера

Если код короткий, например рассмотренный ранее код (6, 3), декодер может быть реализован в виде довольно простой схемы. Рассмотрим шаги, которые должны быть предприняты декодером: (1) вычислить синдром, (2) локализовать модель ошибки и (3) осуществить сложение по модулю 2 модели ошибки и принятого вектора (что приводит к устранению ошибки). В примере 6.4, имея искаженный вектор, мы покажем, как с помощью последовательности этих шагов можно получить исправленное кодовое слово. Сейчас мы рассмотрим схему, показанную на рис. 6.12, где реализованы логические элементы исключающего ИЛИ и И, которые позволяют получить тот же результат для любой модели с одним ошибочным битом в коде (6, 3). Из табл. 6.2 и уравнения (6.39) можно записать все разряды синдрома через разряды принятых кодовых слов:

S = гН,

2 3 4 5 б

52 = Г2+Г4 + rs, S 3 = Гз + Г5 + Гб.

Мы используем эти выражения для синдромов при связывании схемы на рис. 6.12. Логический элемент исключающее ИЛИ - это и есть реализация той самой операции сложения (или вычитания) по модулю 2, поэтому он обозначен тем же символом + . Маленький кружок в конце каждой линии, входящей в элемент И, означает операцию логического дополнения сигнала.

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

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



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