Умножение в полях Галуа
Открыв учебник математики за третий класс (если мне не изменяет память), мы найдем, что умножение представляет собой многократное сложение и, коль скоро сложение в полях Галуа мы выполнять уже научились, мы имеем все основания считать, что реализация функции умножения не создаст особого труда. Так? А вот и нет! Я всегда знал, что дважды два равно четырем, до конца никогда не верил в это и, впервые столкнувшись с полями Галуа понял, насколько был прав.
Примечание
Другими словами говоря, щелкая выключателем я знаю, что сейчас загорится свет. Но я не уверен в этом (потому что монтер мог перерезатьл провода, могла перегореть лампочка перегорела и т. д.). Вот так и с математикой. Та "жвачка", которой пичкают нас в школе и позже в институте — это не математика. Это набор "шаманских обрядов", который нас заставляют совершать, но который не позволяет приникнуть в самую суть — в дао математики. Может оно и к лучшему, не знаю, но во всяком случае считаю долгом сказать, что "математика" преподаваемая в средних и высших учебных заведениях имеет к математике не больше отношения, чем программирование к терзанию мыши в Word'е и установкеи операционной системы Windows.
Выяснилось, что существуют и такие математики, где дважды два не равно четырем, а операция умножения определяется не через сложение, а совсем по другому.
Действительно, если попытаться "обернуть" функцию gf_sum в цикл, мы получим то же самое сложение только в профиль. a * b будет равно а, если b
четно, и нулю, если b — нечетно. Ну, и кому такое умножение нужно? Собственно, функция "настоящего" умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации приходится к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму.
Что такое индекс? Это — показатель степени при основании два, дающий искомый полином.
Например, индекс полинома 8 равен 3 (23 = 8), а индекс полинома 2 равен 1 (21 = 2). Легко показать, что a * b = 2i + 2j = 2(i + j). В частности, 2 * 8 = 23 + 21 = 2(3 + 1) = 44 = 16. Составим следующую к примеру табличку (табл. 2.2) и немного поэкспериментируем с ней.:
Таблица 2.2. Таблица полиномов (левая колонка) и соответствующих
им степеней двойки (правая колонка)
|
i |
alpha_of[i] |
|
001 |
0 |
|
002 |
1 |
|
004 |
2 |
|
008 |
3 |
|
016 |
4 |
Естественно, поскольку от выбранной схемы сопоставления напрямую зависит и конечный результат, обе стороны (кодер и декодер Рида-Соломона) должны соблюдать определенные договоренности. Однако, различные кодеры/декодеры Рида-Соломона могут использовать различные схемы сопоставления, несовместимые друг с другом.
В частности, декодер Рида-Соломона, встроенный в привод CD-ROM привод, выполняет умножение по следующей таблице. Встретив такую таблицу в дизассемблерном листинге исследуемой вами программы, вы сможете быстро и надежно отождествить использующие ее функции (листинг 2.13). Первая слева колонка — полиномы/индексы (обычно обозначается, как i), вторая — таблица степеней примитивного полинома 2 (обычно обозначается как alpha_of), третья — индексы, соответствующие данному полиному (обычно обозначается как index_of):
Листинг 21.1313. Таблица lock-up-таблица для GF(256). Первая слева колонка — полиномы/индексы (обычно обозначается, как i), вторая — таблица степеней примитивного полинома 2 (обычно обозначается как alpha_of), третья — индексы, соответствующие данному полиному (обычно обозначается как index_of)
|
i alpha index i alpha index ii alpha index i alpha index i alpha index i alpha index |
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, что доказывает непротиворечивость операций деления и умножения, а так же всей арифметики Галуа в целиком). Быстро, не правда ли, хотя местами и не совсем понятно, почему таблица составлена именно так, а не иначе? Хуже всего, что достоверность результата нельзя почувствовать "в живую", поскольку все это — абстракции чистейшей воды, что серьезно осложняет отладку программы (сложно отлаживать то, чей принцип работы до конца не понимаешь).
Впрочем, таблицу умножения не обязательно набивать с клавиатуры вручную и ее вполне можно генерировать и "на лету" по ходу исполнения программы. Один из примеров реализации генератора выглядит так как показано в листинге 2.14.:
Листинг 21.14. Процедура генерации таблицы look-up таблицы быстрого умножения полиномов
#define m 8 // степень RS-полинома (согласно Стандарта ECMA-130 [Y66] [n2k67] – восемь)
#define n 255 // n=2**m-1 (длина кодового слова)
#define t 1 // количество ошибок, которые мы хотим скорректировать
#define k 253 // k = n-2*t (длина информационного слова)
// несократимый порождающий полином
// согласно Стандарту ECMA-130: P(x) = x8 + x4 + x3 + x2
+ 1
int p[m+1]={1, 0, 1, 1, 1, 0, 0, 0, 1 };
int alpha_to[n+1]; // таблица степеней примитивного члена
int index_of[n+1]; // индексная таблица для быстрого умножения
//----------------------------------------------------------------------------
// генерируем look- up таблицу для быстрого умножения для GF(2^m) на основе
// несократимого порождающего полинома P(с)© от p[0] до p[m].
//
// look-up таблица:
// index->polynomial из alpha_to[] содержит j=alpha^i,
// где alpha есть примитивный член, обычно равный 2
// а ^ - операция возведения в степень (не XOR!);
//
// polynomial form -> index из
index_of[j=alpha^i] = i;
//
// © Simon Rockliff
//----------------------------------------------------------------------------
generate_gf()
{
int i, mask;
mask = 1; alpha_to[m] = 0;
for (i = 0; i < m; i++)
{
alpha_to[i] = mask;
index_of[alpha_to[i]] = i;
if (p[i] != 0) alpha_to[m] ^= mask;
mask <<= 1;
} index_of[alpha_to[m]] = m; mask >>= 1;
for (i = m+1; i < n; i++)
{
if (alpha_to[i-1] >= mask)
alpha_to[i] = alpha_to[m] ^ ((alpha_to[i-1]^mask)<<1);
else
alpha_to[i] = alpha_to[i-1]<<1;
index_of[alpha_to[i]] = i;
} index_of[0] = -1;
}
Сама же функция умножения выглядит тривиально (листинг 2.15), укладываясь всего в пяток строк. В большинстве программных реализаций кодера/декодера Рида-Соломона, которые мне только доводилось видеть, операция умножения даже не выносится в отдельную процедуру, а реализуется непосредственно по месту вызова.
Листинг 21.15. Функция быстрого табличного умножения полиномов в полях Галуа
// функция возвращает результат умножения
// двух полиномов a на b в полях Галуа
int gf_mul(int a, int b)
{
int sum;
if (a == 0 || b == 0) return 0; // немного оптимизации не повредит
sum = alpha_of[a] + alpha_of[b]; // вычисляем сумму индексов полиномов
if (sum >= GF-1) sum -= GF-1; // приводим сумму к модулю GF
return index_of[sum]; // переводим результат в полиномиальную…
// …форму и возвращаем результат
}
