Звоните! 
 (926)274-88-54 
 Бесплатная доставка. 
 Бесплатная сборка. 
Ассортимент тканей

График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
Читальный зал -->  Программные средства foundation 

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 359

Код с минимальным расстоянием 3

Код с минимальным расстоянием 4

Информационные биты

Проверочные биты

Информационные биты

Проверочные биты

0000

0000

0000

0001

0001

0111

0010

0010

1100

0100

0100

0101

0101

1010

0111

0111

0001

1000

1000

1110

1001

1001

1001

1010

1010

0101

1011

ООН)

1100

1101

1101

0100

1110

1110

1000

1111

1111

1111

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

Доказательство указывает также, как можно построить декодер, исправляющий ошибки (error-correcting decoder) в принимаемых словах кода Хэмминга. Прежде всего проверяются условия четности во всех контрольных группах; если все условия четности выполнены, то принятое слово считается правильным. Если в одной группе или в большем числе групп условие четности нарушено, то счита-

Табл. 2.14. Кодовые слова кодов Хэмминга с четырьмя информационными битами с минимальными расстояниями, равными 3 и 4



-----------------------. пт

ется, что произошла одиночная ошибка. Совокупность фупп с нечетным числом единиц [называемая синдромом (syndrome)] должна иметь один общий столбец в проверочной матрице; предполагается, что значение соответствующего разряда неверно и оно заменяется на противоположное. Предположим, например, что используется код, указанный на рис. 2. ] 3(b) и принято слово 0101011. Число единиц в группах В и С нечетно, что соответствует б-му разряду в проверочной матрице (синдром равен 110, то есть 6). Беря обратное значение бита в 6-м разряде, мы найдем правильное слово: 0001011.

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

Коды Хэмминга с минимальным расстоянием, равным 3 и 4, широко применяются для обнаружения и исправления ошибок в запоминающих системах компьютеров, в частности, в больших универсальных вычислительных машинах, где на запоминающие устройства приходится основная масса системных отказов. Эти коды особенно привлекательны, когда длина запоминаемых слов очень велика, поскольку требуемое число проверочных битов растет медленно с увеличением длины слова, как показано в табл. 2.15.

Табл. 2.15. Число разрядов в кодовых словах кодов Хэмминга с минимальными расстояниями, равными 3 и 4

Код с минимальным Код с минимальным

Информацион- расстоянием 3 расстоянием 4

ные биты Проверочные Общее число Проверочные Общее число биты битов биты битов

<4

<7

<8

<]5

< 16

<26

<3!

<32

<57

<63

<64

< 120

<127

< !28

2.15.4. Циклические коды

Помимо кодов Хэмминга придумано много других кодов, обнаруживающих и исправляющих ошибки. Самыми важными являются циклические коды [cyclic-redundancy-check (CRC) codes], которые, как это ни странно, включают в себя



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

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

2.15.5. Двумерные коды

Другой способ получения кода с большим минимальным расстоянием заключается в построении двумерного кода {two-dimensional code), иллюстрацией чего служит рис. 2.14(a). Из информационных битов образуется двумерная решетка и проверочные биты добавляются как к строкам, так и к столбцам. Для строк используется код С с минимальным расстоянием d, а для столбцов - возможно другой код Ci с минимальным расстоянием d Другими словами, проверочные символы строки вь[бираются так, чтобы каждая строка была кодовым словом кода С а проверочные символы столбца-так, чтобы каждый столбец был кодовым словом кода Cj. (Проверочные биты в углу решетки можно выбрать согласно одному из этих кодов.) Минимальное расстояние в двумерном коде равно произведению d и d-, в связи с этим двумерный код иногда называют кодом-произведением (product code).

В двумерном коде, показанном нарис. 2.14(b), для строк и столбцов используются коды с одним контрольным символом проверки на четность, так что минимальное расстояние в двумерном коде равно 22 = 4. Мы можем легко убедиться в этом, проверив, что любая комбинация из одной, двух или трех ошибок в битах приведет к нарушению условия четности в строке или в столбце или в том и другом. Чтобы ошибка была необнаруживаемой, необходимо изменить, по меньшей мере, четыре бита, расположенные по углам прямоугольника, как показано на рис. 2.14(c).

Процедура обнаружения и исправления ошибок этим кодом носит совершенно естественный характер. Предположим, что мы считьшаем информацию по строке за раз. Прочтя каждую строку, мы проверяем ее принадлежность строковому коду. Если в строке обнаруживается ошибка, то только по виду этой строки мы еще не можем сказать, какой бит неверен. Однако в случае, когда испорчена только одна строка, ее можно восстановить, складывая строки поразрядно по правилу ИСКЛЮЧАЮЩЕЕ ИЛИ, опустив при этом поврежденную строку, но принимая во внимание строку контрольных битов по столбцам.



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 359



ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку.



Звоните! Ежедневно!
 (926)274-88-54 
Продажа и изготовление мебели.


Копирование контента сайта запрещено.
Авторские права защищаются адвокатской коллегией г. Москвы
.