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

Следует отметить сходство между рис. 8.9, 6.18 и 6.19. Во всех трех случаях количество разрядов в регистре равно п-к. Рисунки в главе 6 отображают пример двоичного кодирования, где каждый разряд содержит 1 бит. В данной главе приведен пример недвоичного кодирования, так что каждый разряд регистра сдвига, изображенного на рис. 8.9, содержит 3-битовый символ. На рис. 6.18 коэффициенты, обозначенные gu gi, являются двоичными. Поэтому они принимают одно из значений О или 1, просто указывая на наличие или отсутствие связи в LFSR. На рис. 8.9 каждый коэффициент является 3-битовым, так что они могут принимать одно из 8 значений.

Недвоичные операции, осуществляемые кодером, показанным на рис. 8.9, создают кодовые слова в систематической форме, так же как и в двоичном случае. Эти операции определяются следующими шагами.

1. Переключатель 1 в течение первых к тактовых импульсов закрыт, для того чтобы подавать символы сообщения в (и - /с)-разрядный регистр сдвига.

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

3. После передачи -го символа на регистр выхода, переключатель 1 открывается, а переключатель 2 переходит в верхнее положение.

4. Остальные (и - к) тактовых импульсов очищают контрольные символы, содержащиеся в регистре, подавая их на регистр выхода.

5. Общее число тактовых импульсов равно и, и содержимое регистра выхода является полиномом кодового слова р(Х)+ Х *т(Х), где р(Х) представляет собой кодовые символы, а т(Х) - символы сообщения в полиномиальной форме.

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

010 ПО 111

а ос5

Здесь крайний правый символ является самым первым и крайний правый бит также является самым первым. Последовательность действий в течение первых = 3 сдвигов в цепи кодирования на рис. 8.9 будет иметь следующий вид.

ОЧЕРЕДЬ ВВОДА ТАКТ СОДЕРЖИМОЕ РЕГИСТРА ОБРАТНАЯ СВЯЗЬ

а а

а deg;

а deg;

Как можно видеть, после третьего такта регистр содержит 4 контрольных символа, а , а, а и а*. Затем переключатель 1 переходит в верхнее положение, и контрольные символы, содержащиеся в регистре, подаются на выход. Поэтому выходное кодовое слово, записанное в полиномиальной форме, можно представить в следующем виде:



U(X) = laquo; X ,

л = 0

U(X) = a + aX + aX + aV + aV + ax + aX* = (8.26)

= (100) + (OOl)X + (011)X +(101)X + (OIO)X + (110)X + (111)X*.

Процесс проверки содержимого регистра во время разных тактов несколько сложнее, чем в случае бинарного кодирования. Здесь сложение и умножение элементов поля должны выполняться согласно табл. 8.2 и 8.3.

Корни полиномиального генератора g(X) должны быть и корнями кодового слова, генерируемого g(X), поскольку правильное кодовое слово имеет следующий вид:

U(X) = m(X)g(X). (8.27)

Следовательно, произвольное кодовое слово, выражаемое через корень генератора g(X), должно давать нуль. Представляется интересным, действительно ли полином кодового слова в уравнении (8.26) дает нуль, когда он выражается через какой-либо из четырех корней g(X). Иными словами, это означает проверку следующего:

U(a) = U(a) = Що?) = Ща ) = 0. Независимо выполнив вычисления для разных корней, получим следующее:

U(a) = а + а + + а + а + а* + а = = а + а + а + + а + а + а = = а + а + а* + а = = аЧа = 0,

U(a) = а + а + аЧ а + а + а + а = = а + а + а + а + + а* + а = = а + а* + а + а = = а + а = О,

U(a) = а + а + а + а + а + + а = = а + а + а + а + + а + = = а + а + а + = = а + а = 0,

U(a*) = а + а- + а + а laquo; + а + а + а = = а + а* + а + а + а + + а = = + а + а + а = = аЧ а* = 0.

Эти вычисления показывают, что, как и ожидалось, кодовое слово, выражаемое через любой корень генератора g(X), должно давать нуль.

8.1.6. Декодирование Рида-Соломона

В разделе 8.1.5 тестовое сообщение кодируется в систематической форме с помощью кода Рида-Соломона (7, 3), что дает в результате полином кодового слова, описываемый уравнением (8.26). Допустим, что в ходе передачи это кодовое слово подверглось искажению: 2 символа были приняты с ошибкой. (Такое количество ошибок соответ-



ствует максимальной способности кода к коррекции ошибок.) При использовании 7-символьного кодового слова модель ошибки можно представить в полиномиальной форме следующим образом:

е(Х) = е Х . (8.28)

л = 0

Пусть двухсимвольная ошибка будет такой, что е(Х) = О + ОХ + ОХЧ аХ + аХ* + ОХ + ОХ* =

(8.29)

= (ООО) + (ООО)Х + (ООО)Х + (001)ХЧ (111)Х* + (ООО)Х + (ООО)Х*.

Другими словами, контрольный символ искажен 1-битовой ошибкой (представленной как а), а символ сообщения - 3-битовой ошибкой (представленной как а). В данном случае принятый полином поврежденного кодового слова г(Х) представляется в виде суммы полинома переданного кодового слова и полинома модели ошибки, как показано ниже.

r(X) = U(X) + e(X) (8.30)

Следуя уравнению (8.30), мы суммируем U(X) из уравнения (8.26) и е(Х) из уравнения (8.29) и имеем следующее:

г(Х) = (100) + (001)Х + (011)Х + (lOO)X + (lOl)X + (110)Х + (111)Х* =

= а + аХ + + аХ + + аХ + аХ*. (8.31)

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

8.1.6.1. Вычисление синдрома

Вернемся к разделу 6.4.7 и напомним, что синдром - это результат проверки четности, выполняемой над г, чтобы определить, принапдежит ли г набору кодовых слов. Если г является членом набора, то синдром S имеет значение, равное 0. Любое ненулевое значение S означает наличие ошибок. Точно так же, как и в двоичном случае, синдром S состоит из п-к символов, {S,} (( = 1, п - к). Таким образом, для нашего кода (7, 3) имеется по четыре символа в каждом векторе синдрома; их значения можно рассчитать из принятого полинома г(Х). Заметим, как облегчаются вычисления благодаря самой структуре кода, определяемой уравнением (8.27).

U(X) = m(X)g(X)



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