Разработка динамических сайтов
SEO услуги
Управление контекстной рекламой

Вход на хостинг

Имя пользователя:*

Пароль пользователя:*

IT-новости

20.04.2016 iPhone 2017 года поместят в водонепроницаемый корпус из стекла

Линейка iPhone в новом году серьезно поменяется. В этом уверен аналитический исследователь Мин Чи Ку......

подробнее

30.07.2015 Ищем уникальный контент для сайта

Ищем уникальный контент для сайта Без уникального контента Ваш сайт обречен на то, что его страницы......

подробнее

11.05.2015 Распространённые ошибки разработчиков сайтов

Не секрет, что в сети Интернет насчитывается миллионы сайтов, и каждый день появляются тысячси новых......

подробнее

    s1  =         GF_mult_by_alpha[ s1 ^ input[i] ];

    sm1 = GF_mult_by_alpha_inverse[sm1 ^ input[i] ];

};

 

Листинг 7. Ключевой фрагмент декодера Рида-Соломона, вырванный из IBM 3370

 

err_i = GF_log_base_alpha[ GF_divide[s1][s0] ];    // вычисляем синдром ошибки

input[err_i] ^= s0;                         // исправляем сбойный байт

Ну что, слабо нам разобраться: как он работает? Что касательно переменной s0 - с ней все предельно ясно: она хранит контрольную сумму, рассчитанную по тривиальному алгоритму. Как вы, наверное, помните, сложение в полях Галуа осуществляется логической операцией XOR, и потому: s0 += input[i].

Назначение переменной s1 выяснить сложнее, и чтобы понять суть разворачивающегося вокруг нее метаболизма, мы должны знать содержимое таблицы GF_mult_by_alpha. Несмотря на то, что по соображениям экономии бумажного пространства она здесь не приводится, ее имя говорит само за себя: содержимое s1 суммируется с очередным байтом контролируемого потока данных и умножается на так называемый примитивный член, обозначаемый как alpha, и равный двум. Другими словами: s1 = 2 . (s1 + input[i]).

Допустим, один из байтов потока данных впоследствии будет искажен (обозначим его позицию как err_i), тогда индекс искаженного байта можно определить тривиальным делением s1 на s0. Почему? Так ведь выражение s1 = 2 . (s1 + input[i]) по своей сути есть не что иное, как завуалированное умножение информационного слова на порожденный полином, динамически генерируемый на основе своего примитивного члена alpha. А контрольная сумма информационного слова, хранящаяся в переменной s0, фактически представляет собой то же самое информационное слово, только представленное в более «компактной» форме. И, как уже говорилось в предыдущей статье: если ошибка произошла в позиции x, то остаток от деления кодового слова на порожденный полином будет равен k = 2x. Остается лишь по известному k вычислить x, что в данном случае осуществляется путем обращения к таблице GF_log_base_alpha, хранящей пары соответствий между k и 2x. Коль скоро позиция сбойного байта найдена, его можно исправить путем XOR с рассчитанной контрольной суммой s0 (input[err_i] ^= s0). Конечно, сказанное справедливо только для одиночных ошибок, а искажения двух и более байт на блок данный алгоритм исправить не в силах. Собственно, для этого и присутствует третий байт контрольной суммы - sm1, защищающий декодер от «политнекорректных» попыток исправления ошибок, когда их больше одной. Если выражение s1/s0 == sm1 . s0 становится ложным, контроллер винчестера может засвидетельствовать факт наличия множественных ошибок, констатируя невозможность их исправления.

Однако, как хорошо известно, дефекты магнитной поверхности имеют тенденцию образовывать не одиночные, а групповые ошибки. И, чтобы хоть как-то компенсировать слабость корректирующего алгоритма, парни из IBM прибегли к чередованию байт. Винчестер IBM 3370 имел чередование 3:1, то есть сначала шел первый байт первого блока, за ним первый байт второго блока, за ним – первый байт третьего и только потом - второй байт первого блока. Такой трюк усиливал корректирующую способность винчестера с одной одиночной ошибки, до трех последовательно искаженных байт... Однако если разрушению подвергались не соседние байты, то корректирующая способность вновь опускалась до значений в один искаженный байт на блок, но вероятность такого события была несравненно меньше.


Предыдущая страницаОглавлениеСледующая страница
 
[001] [002] [003] [004] [005] [006] [007] [008] [009] [010] [011] [012] [013] [014] [015] [016] [017] [018] [019] [020]
[021] [022] [023] [024] [025] [026] [027] [028] [029] [030] [031] [032] [033] [034] [035] [036] [037] [038] [039] [040]
[041] [042] [043] [044] [045] [046] [047] [048] [049] [050] [051] [052] [053] [054] [055] [056] [057] [058] [059] [060]
[061] [062] [063] [064] [065] [066] [067] [068] [069] [070] [071] [072] [073] [074] [075] [076] [077] [078] [079] [080]
[081] [082] [083] [084] [085] [086] [087] [088] [089] [090] [091] [092] [093] [094] [095] [096] [097] [098] [099] [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]

+7 (831) 413-63-27
ООО Дельта-Технология ©2007 - 2016 год
Нижний Новгород, ул. Дальняя, 17А.
Rambler's Top100