i alpha index i alpha index i alpha index i alpha index i alpha index i alpha ind

000 001 -1 043 119 218 086 177 219 129 023 112 172 123 220 215 239 170

001 002 0 044 238 240 087 127 189 130 046 192 173 246 252 216 195 251

002 004 1 045 193 18 088 254 241 131 092 247 174 241 190 217 155 96

003 008 25 046 159 130 089 225 210 132 184 140 175 255 97 218 043 134

004 016 2 047 035 69 090 223 19 133 109 128 176 227 242 219 086 177

005 032 50 048 070 29 091 163 92 134 218 99 177 219 86 220 172 187

006 064 26 049 140 181 092 091 131 135 169 13 178 171 211 221 069 204

007 128 198 050 005 194 093 182 56 136 079 103 179 075 171 222 138 62

008 029 3 051 010 125 094 113 70 137 158 74 180 150 20 223 009 90

009 058 223 052 020 106 095 226 64 138 033 222 181 049 42 224 018 203

010 116 51 053 040 39 096 217 30 139 066 237 182 098 93 225 036 89

011 232 238 054 080 249 097 175 66 140 132 49 183 196 158 226 072 95

012 205 27 055 160 185 098 067 182 141 021 197 184 149 132 227 144 176

013 135 104 056 093 201 099 134 163 142 042 254 185 055 60 228 061 156

014 019 199 057 186 154 100 017 195 143 084 24 186 110 57 229 122 169

015 038 75 058 105 9 101 034 72 144 168 227 187 220 83 230 244 160

016 076 4 059 210 120 102 068 126 145 077 165 188 165 71 231 245 81

017 152 100 060 185 77 103 136 110 146 154 153 189 087 109 232 247 11

018 045 224 061 111 228 104 013 107 147 041 119 190 174 65 233 243 245

019 090 14 062 222 114 105 026 58 148 082 38 191 065 162 234 251 22

020 180 52 063 161 166 106 052 40 149 164 184 192 130 31 235 235 235

021 117 141 064 095 6 107 104 84 150 085 180 193 025 45 236 203 122

022 234 239 065 190 191 108 208 250 151 170 124 194 050 67 237 139 117

023 201 129 066 097 139 109 189 133 152 073 17 195 100 216 238 011 44

024 143 28 067 194 98 110 103 186 153 146 68 196 200 183 239 022 215

025 003 193 068 153 102 111 206 61 154 057 146 197 141 123 240 044 79

026 006 105 069 047 221 112 129 202 155 114 217 198 007 164 241 088 174

027 012 248 070 094 48 113 031 94 156 228 35 199 014 118 242 176 213

028 024 200 071 188 253 114 062 155 157 213 32 200 028 196 243 125 233

029 048 8 072 101 226 115 124 159 158 183 137 201 056 23 244 250 230

030 096 76 073 202 152 116 248 10 159 115 46 202 112 73 245 233 231

031 192 113 074 137 37 117 237 21 160 230 55 203 224 236 246 207 173

032 157 5 075 015 179 118 199 121 161 209 63 204 221 127 247 131 232

033 039 138 076 030 16 119 147 43 162 191 209 205 167 12 248 027 116

034 078 101 077 060 145 120 059 78 163 099 91 206 083 111 249 054 214

035 156 47 078 120 34 121 118 212 164 198 149 207 166 246 250 108 244

036 037 225 079 240 136 122 236 229 165 145 188 208 081 108 251 216 234

037 074 36 080 253 54 123 197 172 166 063 207 209 162 161 252 173 168

038 148 15 081 231 208 124 151 115 167 126 205 210 089 59 253 071 80

039 053 33 082 211 148 125 051 243 168 252 144 211 178 82 254 142 88

040 106 53 083 187 206 126 102 167 169 229 135 212 121 41 255 000 175

041 212 147 084 107 143 127 204 87 170 215 151 213 242 157

042 181 142 085 214 150 128 133 7 171 179 178 214 249 85

С помощью данной таблицы вы легко сможете осуществлять преобразование из полиномиальной формы в индексную и наоборот. Как пользоваться этой таблицей? Допустим, мы хотим умножить полиномы 69 и 96. Находим в первой колонке число 69. Ему соответствует alpha 47, запоминаем (записываем его на бумажке) и переходим к числу 96, alpha которого равен 217. Складываем 47 и 217 по модулю 256, получая в результате: (217 + 47) % 256 = 8. Теперь переводим результат произведения из индексной формы в полиномиальную: находим в первой колонке число 8 и в третьей колонке видим соответствующий ему полином: 3. (Если же мы выполним обратную операцию, разделив 3 на 69 – мы получим 96, что доказывает непротиворечивость операций деления и умножения, а также всей арифметики Галуа в целом). Быстро, не правда ли, хотя местами и не совсем понятно, почему таблица составлена именно так, а не иначе? Хуже всего, что достоверность результата нельзя почувствовать «вживую», поскольку все это – абстракции чистейшей воды, что серьезно осложняет отладку программы (сложно отлаживать то, чей принцип работы до конца не понимаешь).

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

Сама же функция умножения выглядит тривиально, укладываясь всего в пяток строк. В большинстве программных реализаций кодера/декодера Рида-Соломона, операция умножения даже не выносится в отдельную процедуру, а реализуется непосредственно по месту вызова.

Деление в полях Галуа

Деление в полях Галуа осуществляется практически точно так, как и умножение, с той лишь разницей, что индексы не прибавляются, а вычитаются друг из друга. В самом деле: a/b == 2ⁱ/2^j == 2^(i-j). Для перевода из полиномиальной в индексную форму и наоборот может использоваться уже приводимая выше look-up таблица. Естественно, не забывайте о том, что какими бы извращенными поля Галуа ни были, а на нуль даже в абстрактной арифметике делить нельзя и функция деления должна быть снабжена соответствующей проверкой.

Простейшие практические реализации

Хорошим примером воплощения кодера/декодера Рида-Соломона являются древние модели жестких дисков, разработанных в недрах фирмы IBM. Модель IBM 3370 имела простой и наглядный кодер/декодер Рида-Соломона типа (174,171) в поле Галуа GF(256). Другими словами, он оперировал 8-битными ячейками (2⁸ = 256), и на 171 информационный байт приходилось 3 байта суммы четности, что в результате давало кодовое слово с размером 174 байт, причем, как мы увидим далее, все три байта контрольной суммы рассчитывались совершенно независимо друг от друга, поэтому фактически кодер/декодер Рида-Соломона оперировал одним байтом, что значительно упрощало его архитектуру.

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

Ну что, слабо нам разобраться: как он работает? Что касательно переменной 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, то есть сначала шел первый байт первого блока, за ним первый байт второго блока, за ним – первый байт третьего и только потом - второй байт первого блока. Такой трюк усиливал корректирующую способность винчестера с одной одиночной ошибки, до трех последовательно искаженных байт... Однако если разрушению подвергались не соседние байты, то корректирующая способность вновь опускалась до значений в один искаженный байт на блок, но вероятность такого события была несравненно меньше.

Естественно, что данный алгоритм может быть реализован не только в самом жестком диске, но и вне его. Варьируя размер блоков и степень чередования, вы обеспечите себе лучшую или худшую защищенность при большей или меньшей избыточности информации. Действительно, пусть у нас есть N секторов на диске. Тогда, разбив их на блоки по 174 сектора в каждом и выделив 3 сектора для хранения контрольной суммы, мы сможем восстановить по меньшей мере N/174 секторов диска. Исходя из средней емкости диска в 100 Гб (что соответствует 209 715 200 секторам), мы сможем восстановить до 1 205 259 секторов даже при их полном физическом разрушении, затратив всего лишь 2% дискового пространства для хранения контрольных сумм. Согласитесь, что редкая «сыпка» винчестера проходит столь стремительно, чтобы корректирующих способностей кода Рида-Соломона оказалось недостаточно для ее воскрешения (конечно, если эту сыпку вовремя заметить и если коэффициент чередования выбран правильно: так, что сектора, принадлежащие одному дисковому блину, обслуживались бы разными корректирующими блоками, в противном случае при повреждении поверхности одного из блинов возникнет групповая ошибка, уже неисправимая данной программой).

А как быть, если «навернется» весь жесткий диск целиком? Наиболее разумный выход – создать массив из нескольких дисков, хранящих полезную информацию вперемешку с корректирующими кодами. Главный минус такого подхода – его неэффективность на массивах, состоящих из небольшого количества жестких дисков. Разумный минимум: четыре информационных диска и один контрольный, тогда потеря любого из информационных дисков компенсируется оставшимся в живых контрольным. Ну а потерянный контрольный диск элементарным образом заменяется на новый, с последующим пересчетом всех контрольных кодов. Правда, одновременный выход двух дисков из строя – это кранты. Массив из пятнадцати дисков, двенадцать из которых – информационные, а оставшиеся три – контрольные, намного более отказоустойчив и допускает одновременный крах двух любых дисков, а при благоприятном стечении обстоятельств – и трех. Собственно, во всем этом ничего нового нет, и соответствующие RAID-контроллеры можно купить буквально в любом магазине. Однако… мне трудно представить себе, сколько будет стоит RAID-контроллер уровня 15 и удастся ли его вообще заставить работать (по личному опыту могу сказать, что RAID-контроллеры даже начальных уровней – вещь крайне глючная, капризная и требовательная как к железу, так и к операционному окружению). Наконец, практически все RAID-контроллеры требуют наличия абсолютно идентичных, ну или близких по своим характеристикам и/или интерфейсам дисков. А коли таковых нет?

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

Как это можно реально использовать на практике? Первое, что приходит на ум, использовать часть емкости жестких дисков под хранение избыточной информации, помогающей восстановить их в случае аварии. Если несколько компьютеров объединить в сеть (что уже давным-давно сделано и без нас), то при относительно небольших накладных расходах мы сможем восстановить любой из жестких дисков членов сети даже при полном его разрушении лишь

за счет одной избыточной информации, распределенной между остальными компьютерами. Более надежного хранилища для ваших данных нельзя и придумать! Подобная схема была реализована автором этой статьи в локальных сетях нескольких фирм и доказала свою высокую живучесть, гибкость и функциональность. Необходимость в постоянном резервировании содержимого жестких дисков автоматически отпала, что в условиях одноранговой сети с отсутствующим выделенным сервером более чем актуально! А ведь такие локальные сети – не редкость (нет, я не утверждаю, что такие сети хороши, просто я констатирую факт, что они существуют в природе и в обозримом будущем вымирать не собираются).

Единственный минус программного RAID - его невысокая производительность. В частности, поставив программный RAID на сервер, обрабатывающий тысячи запросов ежесекундно и интенсивно модифицирующий большое количество файлов, вы не выиграете ничего, но… ведь само понятие «производительность» очень относительно и при достаточно быстром процессоре кодирование/декодирование информации вполне реально осуществлять и на лету безо всяких потерь в пропускной способности!

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

Заключение

Вот мы и разобрались с нашим первым полноценным кодером/декодером Рида-Соломона, выполненным на базе арифметики Галуа. Мы также обсудили основные моменты организации дисковых массивов и даже соблазнились написанием соответствующего драйвера для реализации программного RAID. Все, что нам требуется – это научиться обрабатывать корректирующие коды большой разрядности, корректирующая способность которых не ограничивается одними лишь одиночными ошибками, а позволяет исправлять любое наперед выбранное количество искаженных байт.

Вот об этом мы и поговорим в следующей статье этого цикла, где будет дан законченный алгоритм работы современных кодеров/декодеров Рида-Соломона и полезные советы по их самостоятельной реализации.

На самом деле, полями Галуа называют любые конечные поля, но в данном контексте мы будем говорить лишь о тех полях, количество членов которых равно 2n.

Другими словами говоря, щелкая выключателем, я знаю, что сейчас загорится свет. Но я не уверен в этом (монтер перерезал провода, лампочка перегорела и т. д.). Вот так и с математикой. Та жвачка, которой пичкают нас в школе и позже в институте, – это не математика. Это набор шаманских обрядов, который нас заставляют совершать, но который не позволяет проникнуть в самую суть – в дао математики. Может, оно и к лучшему, не знаю, но во всяком случае считаю долгом сказать, что «математика» преподаваемая в средних и высших учебных заведениях, имеет к математике не больше отношения, чем программирование к терзанию мыши в Word и установке системы Windows