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

Нетрудно убедиться, что произведение UH любого кодового слова U, генерируемого с помощью матриц G и Н, дает следующее:

где биты четности pi, pi, .. ,pn-L определены в уравнении (6.29). Таким образом, поскольку проверочная матрица Н создана так, чтобы удовлетворять условиям ортогональности, она позволяет проверять принятые векторы на предмет их принадлежности заданному набору кодовых слов. U будет кодовым словом, генерируемым матрицей G, тогда и только тогда, когда UH= 0.

6.4.7. Контроль с помощью синдромов

Пусть г = Г1, Г2,г - принятый вектор (один из 2 п-кортежей), полученный после передачи U = laquo;i, laquo;2. и (один из 2* laquo;-кортежей). Тогда г можно представить в следующем виде:

г = и + е. (6.34)

Здесь е =е сг, е - вектор ошибки или модель ошибки, внесенная каналом. Всего в пространстве из 2 п-кортежей существует 2 - 1 возможных ненулевых моделях ошибки. Синдром сигнала г определяется следующим образом:

S = гН. (6.35)

Синдром - это результат проверки четности, выполняемой над сигналом г для определения его принадлежности заданному набору кодовых слов. При положительном результате проверки синдром S равен 0. Если г содержит ошибки, которые можно исправить, то синдром (как и симптом болезни) имеет определенное ненулевое значение, что позволяет отметить конкретную модель ошибки. Декодер, в зависимости от того, производит ли он прямое исправление ошибок или использует запрос ARQ, участвует в локализации и исправлении ошибки (прямое исправление ошибок) или посылает запрос на повторную передачу (ARQ). Используя уравнения (6.34) и (6.35), мы можем представить синдром г в следующем виде:

= (6.36)

Но для всех элементов набора кодовых слов UH = 0. Поэтому

S = еН. (6.37)

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

Интересно также отметить два необходимых свойства проверочной матрицы.

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

G /1 n...jn.-:i,ji.n fr. , ,п .пг... 361



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

Пример 6.3. Контроль с помощью синдромов

Пусть передано кодовое слово 11=101110 из примера в разделе 6.4 3 и принят вектор г=001 1 10, т.е. крайний левый бит принят с ошибкой. Нужно найти вектор синдрома S = гН и показать, что он равен еН. Решение

S = гН =

[о О 1 1 1 о]

= [l, 1 + 1, l + l]=[l о l] (синдром искаженного вектора кода)

Далее проверим, что синдром искаженного вектора кода равен синдрому модели ошибки, которая вызвала эту ошибку

S = еН = [1 О О О О 0] Н = [1 О 0] (синдром модели ошибки) 6.4.8. Исправление ошибок

Итак, мы обнаружили отдельную ошибку и показали, что контроль с помощью синдромов, выполняемый как на искаженном кодовом слове, так и на соответствующей модели ошибки, дает один и тот же синдром. Этот момент является ключевым, поскольку мы имеем возможность не только определить ошибку, но и (поскольку существует взаимно однозначное соответствие между исправимой моделью ошибки и синдромом) исправить подобные модели ошибки. Давайте так расположим 2 п-кортежей, которые представляют собой возможные принимаемые векторы, в так называемой нормальной матрице, чтобы первый ряд содержал все кодовые слова, начиная с кодового слова с одними нулями, а первый столбец - все исправимые модели ошибки. Напомним, что основным свойством линейного кода является то, что в набор кодовых слов включен вектор, состоящий из одних нулей. Каждая строка сформированной матрицы, именуемая классом смежности, состоит из модели ошибки в первом столбце, называемой образующим элементом класса смежности, за которой следуют кодовые слова, подвергающиеся воздействию этой модели ошибки. Нормальная матрица для кода (и, к) имеет следующий вид:



U2+e2

и+ез

и,+ез

Ut +ез

U.+e

U,+e

2 -

(6.38)

Отаетим, что кодовое слово Uj (кодовое слово со всеми нулями) ифает две роли. Оно является кодовым словом, а также может рассматриваться как модель ошибки ei - комбинация, означающая отсутствие ошибки, так что г= U. Матрица содержит все 2 п-кортежей, имеющихся в пространстве V . Каждый п-кортеж упомянут только один раз, причем ни один не пропущен и не продублирован. Каждый класс смежности содержит 2* laquo;-кортежей. Следовательно, всего классов смежности будет (2 /2*) = 2

Алгоритм декодирования предусматривает замену искаженного вектора (любого п-кортежа, за исключением указанного в первой строке) правильным кодовым словом, указанным вверху столбца, содержащего искаженный вектор. Предположим, что кодовое слово и, (( = 1,2) передано по каналу с помехами, в результате чего принят (искаженный) вектор и, + е,. Если созданная каналом модель ошибки е, является образующим элементом класса смежности с индексом j = \,.. ,2 , принятый вектор будет правильно декодирован в переданное кодовое слою U, Если модель ошибки не является образующим элементом класса, то декодирование даст ошибочный результат.

6.4.8.1. Синдром класса смежности

Если является образующим элементом класса смежности или моделью ошибки j-го класса смежности, то вектор U, + является п-кортежем в этом классе смежности. Синдром этого л-кортежа можно записать в следующем виде:

S = (U, + е)Н = и,Н + е,Н.

Поскольку и, - это вектор кода и = О, то, как и в уравнении (6.37), мы можем записать следующее:

8 = (и, + е)Н=еН. (6.39)

Вообще, название класс смежности (или сомножество) - это сокращение от множество чисел, имеющих совместные свойства . Что же все-таки общего между членами каждой данной строки (класса смежности)? Из уравнения (6.39) видно, что каждый член класса смежности имеет один и тот же синдром. Синдром каждого класса смежности отличается от синдромов других классов смежности; именно этот синдром используется для определения модели ошибки.

6.4.8.2. Декодирование с исправлением ошибок

Процедура декодирования с исправлением ошибок состоит из следующих этапов.

1. С помощью уравнения S = гН вычисляется синдром г.

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

д л п/1 lt; 1А1Л1 1 ) А riJLILII-IA LJnLI 363



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