----
Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом
((:gruppe:galois:vspom4 ПОЛЕ ГАЛУА GF(16) (версия для программистов)))
!!⊗!! Страница --- в переработке. Начало работ --- 06.04.2016, окончание --- ??.??.????
----
==Математика отказоустойчивых дисковых массивов==
~~TOC~~
Одним из способов повышения производительности при обмене данными с жестким диском является объединение нескольких дисков в единый массив и распараллеливание операций чтения и записи.
**RAID**[[Redundant Array of Independent Disks (первоначальный вариант расшифровки аббревиатуры --- Redundant Array of Inexpensive Disks) --- избыточный массив независимых (жестких) дисков]] --- технология хранения, обеспечивающая сохранность и/или возможность восстановления данных с помощью различных алгоритмических и технологических методов организации контроля процесса записи на диск. В настоящем разделе RAID-технология будет разбираться на примере задачи восстановления **двух** дисков (RAID-6).
При использовании этой технологии данные для обмена с жестким диском собираются в большие массивы --- **страйпы**[[stripe (//англ.//) --- полоса.]], которые сегментируются (разбиваются) на блоки одинаковой длины. Количество таких блоков должно совпадать с количеством дисковых массивов, и операция записи на жесткий диск (или считывания с него) производится одновременно (параллельно) для всех блоков. Для упрощения терминологии, в настоящем разделе будем говорить о дисках, имея в виду составляющие страйп блоки.
===Идея==
Рассмотрим страйп, состоящий из пяти четырехразрядных дисков:
$$ (D_0,D_1,D_2,D_3,D_4) \quad npu \quad D_j=(d_{j1},d_{j2},d_{j3},d_{j4}) , \quad \{d_{j\ell}\} \subset \{0,1\} \ . $$
Каждый из этих дисков будем считать элементом ((:gruppe:galois:vspom4 поля Галуа)) $ \mathbf{GF}(2^4) $,
c операцией умножения, заданной по двойному модулю $ 2, f(x) $ при полиноме
$$ f(x)=x^4+x+1 $$
являющемся ((:gruppe:galois#полиномы_над_gf_p неприводимым)).
Проверочные диски (синдромы) будем формировать по правилу[[Обозначения $ P_{} $ и $ Q_{} $ --- традиционные.]]:
$$ P=D_0+D_1+D_2+D_3+D_4 \pmod{2} $$
(контрольная сумма) и
$$ Q=D_0\mathfrak A^{4}+ D_1\mathfrak A^{3}+D_2\mathfrak A^{2}+D_3\mathfrak A+D_4 \quad (\operatorname{modd} \ 2,f(x)) \ . $$
Здесь $ \mathfrak A \in \mathbf{GF}(16) $ --- произвольный ((:gruppe:galois:vspom2 примитивный элемент)) поля; в данном примере можно взять $ \mathfrak A= x $, что в дальнейшем и делается.
В отличие от синдрома $ P_{} $ вычисление синдрома $ Q_{} $ требует операции умножения в поле $ \mathbf{GF}(16) $, т.е. нахождение
коэффициентов остатка от деления полинома
$$ (d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})x^4 +(d_{11}x^3+d_{12}x^2+d_{13}x+d_{14})x^3+ $$
$$+(d_{21}x^3+d_{22}x^2+d_{23}x+d_{24})x^2+ (d_{31}x^3+d_{32}x^2+d_{33}x+d_{34})x+ $$
$$+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44}) $$
на полином $ f_{}(x) $ с приведением коэффициентом по модулю $ 2_{} $. Эффективная организация этого умножения --- отдельная задача, которую обсудим позже. Можно, например, действовать по такой схеме:
$$
\equiv_{_{2,f(x)}} (d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})(x+1) +
$$
$$
+ \left( (d_{11}x^2+d_{12}x+d_{13})x^4+d_{14}x^3 \right)+
$$
$$
+\left( (d_{21}x+d_{22})x^4+d_{23}x^3+d_{24}x^2 \right) +
$$
$$
+d_{31}x^4+ (d_{32}x^2+d_{33}x+d_{34})x+
$$
$$
+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44}) \equiv
$$
$$
\equiv_{_{2,f(x)}} (d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})(x+1) +
$$
$$
+(d_{11}x^2+d_{12}x+d_{13})(x+1)+d_{14}x^3 +
$$
$$
+(d_{21}x+d_{22})(x+1)+d_{23}x^3+d_{24}x^2 +
$$
$$
+d_{31}(x+1)+ (d_{32}x^2+d_{33}x+d_{34})x+
$$
$$
+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44}) \, ,
$$
т.е. каждую возникающую при умножении степень $ x^4 $ заменять на $ x+1 $ (поскольку это и есть остаток от деления $ x^4 $ на полином $ f_{}(x) $ по модулю $ 2_{} $). В результате получим полином
$$
\equiv_{_{2,f(x)}} (d_{01}+d_{02}+d_{11}+d_{14}+d_{23}+d_{32}+d_{41})x^3+\dots+ (d_{01}+d_{04}+d_{13}+d_{22}+d_{31}+d_{44}) \, ,
$$
коэффициенты которого и составляют вектор[[Мы намеренно не заостряем внимания каким именно вектором --- столбцом или строкой --- являются рассматриваемые векторы. В теории кодирования больше тяготеют к формализму строк. Мы будем использовать обе возможности.]] синдрома $ Q_{} $:
$$ \begin{array}{rl}
Q= & (d_{01}+d_{02}+d_{11}+d_{14}+d_{23}+d_{32}+d_{41},\\
& d_{02}+d_{03}+d_{11}+d_{12}+d_{21}+d_{24}+d_{33}+d_{42}, \\
& d_{01}+d_{03}+d_{04}+d_{12}+d_{13}+d_{21}+d_{22} +d_{31}+d_{34} + d_{43}, \\
& d_{01}+d_{04}+d_{13}+d_{22}+d_{31}+d_{44} ) \, .
\end{array}
$$
Таким образом, для одного пятидискового страйпа мы создали две контрольные суммы, а если перевести на язык битов, то для $ 20 $ битов информационных составили $ 8_{} $ битов служебных. Если записать соотношения, связывающие служебные биты с информационными,
то получим систему линейных уравнений, которую можно записать в матричном виде:
$$ (D_0,D_1,D_2,D_3,D_4,P,Q) \mathbf H^{\top}= \mathbb O_{1\times 8} $$
при записи содержимого дисков в строку и при матрице $ \mathbf H $ имеющей порядок $ 8\times 28 $
$$ \mathbf H = $$
$$
=\left(
\begin{array}{cccc|cccc|cccc|cccc|cccc|cccc|cccc}
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
\hline
1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{array}\right) \, .
$$
Структура этой матрицы будет понятной, если мы перепишем ее в блочном виде --- так, как она уже ``разрезана'':
$$ \mathbf H
=\left(
\begin{array}{lllllcc}
E & E & E & E & E & E & \mathbb O \\
\mathbf H_{21} & \mathbf H_{22} & \mathbf H_{23} & \mathbf H_{24} & E & \mathbb O & E
\end{array}\right) \ ;
$$
здесь $ E_{} $ --- единичная, а $ \mathbb O $ --- нулевая матрицы порядка $ 4 \times 4 $. Матрицы $ \{ \mathbf H_{2j} \}_{j=1}^4 $ кажутся сформированными хаотично. Тем не менее, закономерность в их ряду имеется. Обозначим
$$
\mathbf F= \mathbf H_{24}=
\left(
\begin{array}{cccc}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{array} \right) \, .
$$
Тогда
$$
\mathbf H_{23}= \mathbf F^2,\ \mathbf H_{22}= \mathbf F^3,\ \mathbf H_{21}= \mathbf F^4 \, .
$$
Эта закономерность является проявлением общего правила, которое подробнее описано
☞
((:gruppe:galois:vspom4#места_потерь_известны ЗДЕСЬ)).
На практике, в символьном виде синдромы не хранят, а вычисляют каждый раз для конкретных дисков. Теперь посмотрим как эти синдромы можно использовать для восстановления содержания поврежденных дисков.
Этот момент принципиален: поврежденные информационные биты могут располагаться на разных дисках, но если все такие повреждения можно локализовать в одном или двух дисках, то восстановление возможно. Если же три поврежденных бита разбросаны по трём дискам, то их восстановление невозможно.
!!П!! **Пример.** Пусть при записи страйпа
$$ \big(\underbrace{1010}_{D_0},\ \underbrace{0111}_{D_1},\ \underbrace{0101}_{D_2},\ \underbrace{1010}_{D_3},\ \underbrace{0011}_{D_4}\big) $$
происходит потеря (порча) двух дисков $ D_1 $ и $ D_3 $. Для их восстановления снова используем значения синдромов --- исходного страйпа и записанного; только в последнем не учитываем испорченные диски --- формально обнуляем все их разряды:
$$ \tilde D_0=D_0,\ \tilde D_1= (0000),\ \tilde D_2=D_2,\ \tilde D_3= (0000),\ \tilde D_4=D_4 \ . $$
Результаты вычисления синдромов: до записи ---
$$
P=(0001), Q=(0011) \, ,
$$
а после записи ---
$$
\tilde P=(1100),\ \tilde Q=(1001) \ .
$$
Для восстановления значений утерянных дисков $ D_1 $ и $ D_3 $ получаем систему сравнений:
$$
\left\{
\begin{array}{rrl}
D_1 & +D_3 & \equiv P + \tilde P \\
x^{3} D_1 & +x D_3 & \equiv Q + \tilde Q
\end{array}
\right. \quad (\operatorname{modd} \ 2,f(x)) \ .
$$
Из первого сравнения выражаем $ D_3 $ через $ D_1 $ и подставляем во второе:
$$ D_3 \equiv D_1 + P + \tilde P, $$
$$
\Rightarrow \quad D_1= \left( Q + \tilde Q+ x(P + \tilde P) \right)(x^{3}+x)^{-1} \
$$
$$
\Rightarrow \ D_1=
\left( (Q + \tilde Q)x^{-1}+ P + \tilde P \right)(x^{2}+1)^{-1} \quad (\operatorname{modd} \ 2,f(x)) \ .
$$
Вычисления отрицательных степеней элементов поля проводим с использованием стандартых упрощений и таблицы из
☞
((:gruppe:galois:vspom4 ПУНКТА)):
$$ x^{-1} \equiv x^3+1 \, , $$
$$x^2+1 \equiv x^8 \ \Rightarrow \ (x^2+1)^{-1}\equiv x^{-8} \equiv x^7 \equiv x^3 +x+1 \, . $$
Окончательно:
$$
\begin{array}{ll}
D_1&= (x^3+1)(x^3+x+1)(Q + \tilde Q)+(x^3+x+1)(P + \tilde P) \quad (\operatorname{modd} \ 2,f(x)) \equiv (0111),\\
D_3&=(0111)+(0001)+(1100) \pmod{2} =(1010) \ .
\end{array}
$$
----
В общем случае --- когда происходит потеря двух дисков $ D_{j} $ и $ D_{k} $ при
$ 0 \le j< k \le 4 $ --- аналогичные рассуждения приводят к формулам
$$ D_k \equiv D_j + P + \tilde P_{jk}, \quad D_j= \left( (Q + \tilde Q_{jk})x^{-(4-k)}+ P + \tilde P_{jk} \right)(x^{(k-j)}+1)^{-1} \quad (\operatorname{modd} \ 2,f(x)) \ . $$
Для универсального использования этих "восстанавливающих диски" формул желательно иметь заранее вычисленными выражения
$$ (x^{-1})^t \quad u \quad (x^t+1)^{-1} \quad npu \quad t \in \{0,1,2,3,4\} \ . $$
На всякий случай подчеркну, что этот алгоритм будет работать и для произвольного количества $ N_{} $ четырехразрядных дисков в страйпе --- если только $ N\le 15=2^{4}-1 $, т.е. $ N_{} $ не превосходит количества ненулевых элементов поля Галуа $ \mathbf{GF}(16) $. А вот в каком месте алгоритм может засбоить если это условие нарушить --- догадайтесь сами.
Отличие идеологии RAID-6 от практики применения ((:codes:cyclic:bch#коды_рида-соломона КОДОВ РИДА-СОЛОМОНА)) состоит в том, что в последней места испорченных дисков (блоков) считаются __неизвестными__; так что коды Рида-Соломона предназначены для решения более сложной задачи.
Выбор элементов поля, на которые домножаются разряды страйпа в виде убывающих степеней примитивного элемента поля $ \mathfrak A^{4},\mathfrak A^{3},\mathfrak A^{2},\mathfrak A,\mathfrak A^{0} $ как раз идет больше из традиции кодов Рида-Соломона. В следующем примере мы выберем другой набор и покажем, что это не повлияет на корректность работы алгоритма восстановления.
!!П!! **Пример.** Страйп --- тот же, что и в разобранном выше примере, так же как и синдром $ P_{} $. Будем считать синдром $ Q_{}(x) $ по правилу:
$$ Q(x)\equiv D_0(x)+ D_1(x)x+D_2(x)x^{2}+D_3(x)x^{3}+D_4(x)x^{4} \equiv x^3+1 \quad (\operatorname{modd} \ 2,f(x)) \ . $$
После потери $ D_1(x) $ и $ D_3(x) $ его значение: $ \tilde Q(x) \equiv x^3 \quad (\operatorname{modd} \ 2,f(x)) $. Формула восстановления:
$$
D_1(x)= \left( (Q(x) + \tilde Q(x))x^{-3}+ P(x) + \tilde P(x) \right)(x^{-2}+1)^{-1} \equiv
x^2+x+1 \quad (\operatorname{modd} \ 2,f(x)) .
$$
♦
Последний пример в переводе на язык матриц (линейных уравнений над $ \mathbf{GF}(2) $) см. в конце
☞
((:gruppe:galois:vspom4#места_потерь_известны ПУНКТА)) (только в том пункте нумерацию дисков увеличил на $ 1_{} $).
((:codes:raid:questions .))
===Общий вид решения==
Пусть в нашем распоряжении имеется программная реализация ((:gruppe:galois:vspom4 поля Галуа)) $ \mathbf{GF}(2^n) $ и наша задача состоит в восстановлении __одного или двух__ потерянных дисков данных из $ N_{} $ записываемых на жесткий диск:
$$ D_0,D_1,\dots,D_{N-1} \ . $$
Считаем, что количество дисков $ N \le 2^n-1 $ и каждый диск представляет собой $ n_{} $-битный блок $ (A_0,A_1,\dots,A_{n-1}) $. Этот вектор (или же, в альтернативном представлении, полином $ A_0x^{n-1}+A_1x^{n-2}+\dots+A_{n-1} $) мы будем считать элементом поля, которое порождается некоторым неприводимым полиномом $ f_{}(x) $ степени $ n_{} $ (т.е. операция умножения элементов поля определяется как умножение полиномов по двойному модулю $ 2,f(x) $). Обозначим $ \mathfrak{A} $ --- произвольный ((:gruppe:galois:vspom2 примитивный элемент поля)) $ \mathbf{GF}(2^n) $. Забегая вперед, отметим существенность условия
примитивности
элемента для целей настоящего раздела: нам нужно, чтобы степени
$$ \mathfrak{A}^0, \mathfrak{A}^1, \mathfrak{A}^2,\dots, \mathfrak{A}^{2^n-2} $$
были все __различными__ и, следовательно, порождали все поле $ \mathbf{GF}(2^n) $ --- за исключением нулевого его элемента[[На всякий случай, напомню: нулевой элемент поля $ \mathfrak o $ интерпретируется либо как нулевой $ n_{} $-битный блок $ (0,\dots,0) $, либо как тождественно нулевой полином $ 0\cdot x^{n-1}+0\cdot x^{n-2}+\dots+0\cdot x + 0 $.]] $ \mathfrak o $.
Будем вычислять синдромы по правилам
$$
\begin{array}{rcrrrr}
P&=&D_0+&D_1+&\dots+& D_{N-1}, \\
Q&=&\mathfrak{A}^0 \cdot D_0+&\mathfrak{A}^1 \cdot D_1+&\dots+& \mathfrak{A}^{N-1} \cdot D_{N-1}.
\end{array}
$$
Здесь, как и ранее, суммирование понимается поразрядное, умножение --- по двойному модулю $ 2,f(x) $. Таким образом, к уже имеющимся "информационным" дискам $ D_0,D_1,\dots,D_{N-1} $ нужно добавить еще два --- "служебных, проверочных"[[В слэнге RAID-технологов принята терминология "data disks - redundancy disks". Терминологию //"информационный-проверочный"// я перетащил из теории кодирования.]] диска $ P_{} $ и $ Q_{} $, тем самым создается //избыточность// информации, заявленная в названии технологии RAID. Эта избыточность используется для восстановления дисков, испорченных в процессе записи.
Заметим, что, в отличие от **//Coder sapiens//**[[(//лат.//) --- программист разумный; редкий подвид Homo sapiens ;-)]], запоминающее устройство не способно учуять различия между информационными и служебными дисками, и может --- с (примерно) одинаковой вероятностью --- запортить любой из них.
Иными словами, испортиться могут не только какие-то из $ D_0,D_1,\dots,D_{N-1} $, но и $ P_{} $ или $ Q_{} $ (и даже оба служебных диска вместе). Рассмотрим сначала более вероятный случай --- порчи двух информационных дисков $ D_j $ и $ D_k $ при $ 0\le j < k \le N-1 $.
Снова вычисляем значения синдромов --- для набора дисков
$$ D_0,\dots,D_{j-1},\tilde D_j=\mathfrak o,D_{j+1},\dots,D_{k-1},\tilde D_k=\mathfrak o,D_{k+1},\dots,D_{N-1} \ , $$
в котором значения запорченных дисков обнуляются:
$$ P_{jk}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} D_{\ell},\quad
Q_{jk}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ . $$
Тем самым количество служебных дисков увеличивается до четырех. Складывая по модулю $ 2_{} $ значения соответствующих синдромов, получаем систему уравнений[[Cтрого говоря, это --- система __сравнений__ по двойному модулю $ 2,f(x) $.]]
$$
\left\{
\begin{array}{rrr}
D_j+&D_k=&P+P_{jk}, \\
\mathfrak{A}^j D_j+&\mathfrak{A}^k D_k =&Q+Q_{jk}. \\
\end{array}
\right.
$$
Мы хотим, чтобы эта система была разрешимой и разрешимой единственным образом в поле $ \mathbf{GF}(2^n) $ относительно неизвестных $ D_j $ и $ D_k $.
Более того, мы хотим, чтобы такими же --- однозначно разрешимыми --- были __все__ системы __при любом выборе__ индексов $ j_{} $ и $ k_{} $ ($ 0\le j < k \le N-1 $).
Это требование оказывается выполненным. В самом деле, домножим первое уравнение на $ \mathfrak{A}^j $ и прибавим ко второму (опять же, по модулю $ 2_{} $):
$$ (\mathfrak{A}^j+\mathfrak{A}^k) D_k=\mathfrak{A}^j (P+P_{jk})+Q+Q_{jk} \ . $$
Утверждается, что $ \mathfrak{A}^j+\mathfrak{A}^k \ne \mathfrak o $. Действительно, в поле ((:gruppe:galois#структура_конечного_поля характеристики)) $ 2_{} $ имеем $ \mathfrak{A}^k =-\mathfrak{A}^k $ (элемент поля $ \mathbf{GF}(2^n) $ противоположен сам себе). Таким образом, $ \mathfrak{A}^j+\mathfrak{A}^k =\mathfrak{A}^j-\mathfrak{A}^k $, и вот в этот момент происходит использование свойства примитивности элемента $ \mathfrak{A} $: $ \mathfrak{A}^j \ne \mathfrak{A}^k $.
Поскольку любой ненулевой элемент поля имеет обратный относительно умножения, то получаем однозначное разрешение последнего уравнения:
$$ D_k=(\mathfrak{A}^j+\mathfrak{A}^k)^{-1} \left( \mathfrak{A}^j (P+P_{jk})+Q+Q_{jk} \right) \ . $$
Поскольку обращение элементов поля является нетривиальной задачей, то, имея в виду универсальность использования последней формулы --- ее планируется использовать при любых наборах индексов $ \{j,k\}, 0\le j < k \le N-1 $, --- имеет смысл хранить заранее вычисленными выражения для $ (\mathfrak{A}^j+\mathfrak{A}^k)^{-1} $ при всех этих значениях индексов. Легко увидеть, что количество таких элементов равно $ C_{N-1}^2=(N-1)(N-2)/2 $. Имеет смысл уменьшить это число, за счет небольшого упрощения последней формулы:
$$ D_k=(\mathfrak e+\mathfrak{A}^{k-j})^{-1} \left( P+P_{jk}+\mathfrak{A}^{-j}(Q+Q_{jk}) \right) \ ; $$
здесь $ \mathfrak e $ --- единичный элемент поля[[Его всегда можно считать либо $ n- $битным блоком $ (0,0,\dots,0,1) $ или тождественно равным $ 1_{} $ полиномом $ 0\cdot x^{n-1}+0\cdot x^{n-2}+\dots+ 0\cdot x+1 $.]].
Количество обращений элементов снизилось до $ 2N-1 $. Можно еще уменьшить количество обращений, если воспользоваться цикличностью последовательности $ \{\mathfrak{A}^{\ell}\} $: $ \mathfrak{A}^{2^n-1}=\mathfrak e $ и, следовательно, $ \mathfrak{A}^{-j} = \mathfrak{A}^{2^n-1-j} $.
После нахождения значения диска $ D_k $, величина второго испорченного диска определяется из линейного соотношения
$$ D_j=D_k+(P+P_{jk}) \ . $$
Теперь посмотрим, что произойдет, если запорчен только один информационный диск, скажем $ D_j $, а также один синдром, например $ Q $. В этом случае $ D_j $ определяется из соотношений для оставшегося синдрома $ P_{} $ и его значения $ P_{j} $ , пересчитанного в предположении $ D_j=\mathfrak o $ :
$$ D_j=P+ P_j \qquad \mbox{ при } \qquad P_j=\sum_{\ell=0 \atop \ell \ne j }^{N-1} D_{\ell} \ . $$
В случае, когда испорченными являются блоки $ D_j $ и $ P_{} $, восстанавливающая формула:
$$ D_j=\mathfrak{A}^{-j} \left(Q+ Q_j \right) \qquad \mbox{ при } \qquad Q_j= \sum_{\ell=0 \atop \ell \ne j}^{N-1} \mathfrak A^{\ell} D_{\ell} \ .
$$
----
Из двух синдромов $ P_{} $ и $ Q $ вычисление именно последнего наиболее затратно. Любая экономия приветствуется. Одна из них лежит на виду --- это ((:polynomial#схема_хорнера схема Хорнера)) вычисления значения полинома:
$$ Q= D_0+\mathfrak{A} \left( D_1+\mathfrak{A} \left( D_2+\mathfrak{A} \left( D_3+\dots+ \mathfrak{A} \left( D_{N-2} +\mathfrak{A} D_{N-1} \right) \dots \right) \right) \right) \ . $$
Она позволяет сократить количество умножений на $ N-1 $.
===Модификации==
===Три синдрома: полет нормальный==
Рассматриваем снова диски данных
$$ D_0,D_1,\dots,D_{N-1} $$
как элементы ((:gruppe:galois:vspom4 поля Галуа)) $ \mathbf{GF}(2^n) $ и ставим задачу состоит в восстановлении от __одного__ до __трех__ потерянных из их числа.
Для решения задачи кажется естественным обобщить правило вычисления синдромов:
$$
\begin{array}{lcrrrr}
P_0&=&D_0+&D_1+&\dots+ &D_{N-1} , \\
P_1&=&D_0+&\mathfrak{A}^1 \cdot D_1+&\dots+& \mathfrak{A}^{N-1} \cdot D_{N-1}, \\
P_2&=&D_0+&\mathfrak{B}^1 \cdot D_1+&\dots+& \mathfrak{B}^{N-1} \cdot D_{N-1}
\end{array}
$$
при $ \mathfrak{B} $ --- примитивном элементе поля, отличном от $ \mathfrak{A} $. Выполнения какого свойства мы хотим от этих соотношений? ---
Если они предназначены для восстановления потерянных дисков в любом количестве от $ 1_{} $ до $ 3_{} $ (включая, возможно, и синдромы), то необходимое условие заключается в возможности разрешимости любой подсистемы из этих линейных уравнений относительно такого же количества дисков.
Это требование можно переписать в виде условия на миноры матрицы этой системы
$$
M
=\left[
\begin{array}{lllll}
\mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\
\mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \dots & \mathfrak A^{N-1} \\
\mathfrak e & \mathfrak B^1 & \mathfrak B^2 & \dots & \mathfrak B^{N-1}
\end{array}
\right]_{3\times N} \ .
$$
И от этой матрицы нам нужно, чтобы все ее ((:algebra2#определитель миноры)) (любого порядка) были ненулевыми. Ввиду рассуждений предыдущего пункта, понятно, что элементы поля $ \mathfrak A $ и
$ \mathfrak B_{} $ должны быть примитивными и различными: $ \mathfrak A\ne \mathfrak B $. Также понятно, что матрица $ M_{} $ --- это ((:algebra2#вандермонда матрица Вандермонда)). Смотрим в ((:gruppe:galois:vspom4#возведение_в_степень таблицу логарифмов)) с целью найти примитивный элемент поля $ \mathfrak B $, отличный от уже выбранного элемента $ \mathfrak A $. Например, в соответствии с теоремой $ 3 $, приведенной
☞
((:gruppe:galois:vspom2 ЗДЕСЬ)), можно взять $ \mathfrak B = \mathfrak A^2 $. Таким образом,
$$
M=
\left[
\begin{array}{llllll}
\mathfrak e & \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\
\mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \mathfrak A^3 & \dots & \mathfrak A^{N-1} \\
\mathfrak e & \mathfrak A^2 & \mathfrak A^4 & \mathfrak A^6 & \dots & \mathfrak A^{2(N-1)}
\end{array}
\right]
\, .
$$
Все ее элементы отличны от нуля. Ее миноры второго порядка --- одного из следующих видов
$$
\left|
\begin{array}{cc}
\mathfrak e & \mathfrak e \\
\mathfrak A^{k} & \mathfrak A^{\ell}
\end{array}
\right|=\mathfrak A^{\ell}-\mathfrak A^k,
\
\left|
\begin{array}{cc}
\mathfrak e & \mathfrak e \\
\mathfrak A^{2k} & \mathfrak A^{2\ell}
\end{array}
\right|=\mathfrak A^{2\ell}-\mathfrak A^{2k},
\
\left|
\begin{array}{cc}
\mathfrak A^{k} & \mathfrak A^{\ell} \\
\mathfrak A^{2k} & \mathfrak A^{2\ell}
\end{array}
\right|=\mathfrak A^k\mathfrak A^{\ell} (\mathfrak A^{\ell}-\mathfrak A^k) \quad npu \quad 0\le k < \ell \le N-1 ;
$$
и все они отличны от нуля. Эти условия гарантируют нам возможность восстановления содержимого любых двух информационных дисков даже в случае, когда дополнительно отказывает любой из служебных. В самом деле, если потеряны диски $ D_j $ и $ D_k $, а, в дополнение к ним, еще и $ P_0 $,
то мы пересчитываем значения синдромов $ P_{1} $ и $ P_{2} $, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):
$$ P_1^{(jk)}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ , \
P_2^{(jk)}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{2\ell} D_{\ell} \ . $$
Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений
$$
\left\{
\begin{array}{rrr}
\mathfrak{A}^j D_j+&\mathfrak{A}^k D_k=&P_1+P_1^{(jk)}, \\
\mathfrak{A}^{2j} D_j+&\mathfrak{A}^{2k} D_k =&P_2+P_2^{(jk)},
\end{array}
\right.
$$
которая является линейной относительно утерянных дисков $ D_{j} $ и $ D_{k} $. Разрешаем систему (либо по формулам Крамера, либо по методу Гаусса), получаем
$$
\begin{array}{ccl}
D_j &=& (\mathfrak e+\mathfrak A^{k-j})^{-1}\left[ \mathfrak A^{k-2j} \left( P_1+P_1^{(jk)} \right)+ \mathfrak A^{-2j} \left(P_2+P_2^{(jk)} \right)\right], \\
D_k &=& (\mathfrak e+\mathfrak A^{k-j})^{-1}\left[ \mathfrak A^{-k} \left( P_1+P_1^{(jk)} \right)+ \mathfrak A^{-k-j} \left(P_2+P_2^{(jk)} \right)\right].
\end{array}
$$
Рассмотрим теперь случай порчи трех информационных дисков $ D_i,D_j,D_k $, $ 0\le i< j < k \le N-1 $.
Им соответствует минор третьего порядка матрицы $ M_{} $
$$
\Delta_{ijk}=
\left|
\begin{array}{lll}
\mathfrak e & \mathfrak e & \mathfrak e \\
\mathfrak A^{i} & \mathfrak A^{j} & \mathfrak A^{k} \\
\mathfrak A^{2i} & \mathfrak A^{2j} & \mathfrak A^{2k}
\end{array}
\right| =
\Delta_{ijk}=(\mathfrak A^{k}-\mathfrak A^{j})(\mathfrak A^{j}-\mathfrak A^{i})(\mathfrak A^{k}-\mathfrak A^{i}) \, .
$$
(определитель ((:algebra2:dets#вандермонда Вандермонда)) ). Он отличен от нуля по условию примитивности элемента $ \mathfrak A_{} $.
Пересчитываем значения синдромов $ P_0, P_{1} $ и $ P_{2} $, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):
$$ P_0^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} D_{\ell},\ P_1^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ , \
P_2^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} \mathfrak A^{2\ell} D_{\ell} \ . $$
Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений
$$
\left\{
\begin{array}{rrrr}
D_i + & D_j + & D_k=& P_0+ P_0^{(ijk)}, \\
\mathfrak{A}^i D_i+&\mathfrak{A}^j D_j+&\mathfrak{A}^k D_k=&P_1+P_1^{(ijk)}, \\
\mathfrak{A}^{2i} D_i+&\mathfrak{A}^{2j} D_j+&\mathfrak{A}^{2k} D_k =&P_2+P_2^{(ijk)},
\end{array}
\right.
$$
которая однозначно разрешима относительно потерянных дисков.
===Четыре синдрома: «Хьюстон, у нас проблемы!»==
Дальнейшее развитие идеологии формирования синдромов кажется очевидным. С привлечением матричного формализма можно записать $ 4_{} $ вычислительные формулы в виде
$$
\underbrace{\left[
\begin{array}{lllll}
\mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\
\mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \dots & \mathfrak A^{N-1} \\
\mathfrak e & \mathfrak A^2 & \mathfrak A^4 & \dots & \mathfrak A^{2(N-1)} \\
\mathfrak e & \mathfrak A^3 & \mathfrak A^6 & \dots & \mathfrak A^{3(N-1)}
\end{array}
\right]}_{M} \left(\begin{array}{c} D_0 \\ D_1 \\ D_2 \\ \vdots \\ D_{N-1} \end{array}\right)=
\left(\begin{array}{c} P_0 \\ P_1 \\ P_2 \\ P_{3} \end{array}\right) \, .
$$
Первая проблема:
не для всяких полей $ \mathbf{GF}(2^n) $ элемент $ \mathfrak A^3 $ будет примитивным. Для $ n\in \{4,6,8,10,\dots \} $ точно не будет.
$$ (x^3)^5 \equiv 1 \quad (\operatorname{modd} \ 2,x^4+x+1), $$
$$ (x^3)^{17} \equiv 1 \quad (\operatorname{modd} \ 2,x^8+x^4+x^3+x+1), $$
$$ (x^3)^{85} \equiv 1 \quad (\operatorname{modd} \ 2,x^8+x^4+x^3+x^2+1) \ . $$
Здесь полиномы $ x^8+x^4+x^3+x^2+1 $ и $ x^8+x^4+x^3+x+1 $ --- неприводимые, и каждый из них порождает поле $ \mathbf{GF}(2^8) $.
На чем это может сказаться?
!!П!! **Пример.** Поле
$$ \mathbf{GF}(2^4) , \ f(x)=x^4+x+1, \ \mathfrak A=x \, .$$
Информационные диски $ D_0,D_1,D_2,D_3,D_4,D_5 $. Матрица $ M_{} $ имеет вид
$$
\left[
\begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \\
1 & x & x^2 & x^3 & x+1 & x^2+x \\
1 & x^2 & x+1 & x^3 + x^2 & x^2+1 & x^2 +x +1 \\
1 & x^3 & x^3+x^2 & x^3 + x & x^3 +x^2 +x +1 & 1
\end{array}
\right] \, .
$$
Теперь предположим, что теряются диски $ D_0,D_5 $ и $ P_1, P_2 $. Действуя по аналогии с предыдущим пунктом, пересчитаем значения этих двух синдромов, считая $ D_0=(0000),D_5=(0000) $, составим систему уравнений
$$
\left\{
\begin{array}{rr}
D_0+D_5=&P_0+P_0^{(1234)}, \\
D_0+D_5 =&P_2+P_2^{(1234)}
\end{array}
\right.
$$
относительно потерянных дисков $ D_0,D_5 $. Если она совместна, т.е. $ P_0+P_0^{(1234)} = P_2+P_2^{(1234)} $, то она не может быть однозначно разрешена.
♦
Как обойти эту проблему? Можно было бы заменить последнюю строку матрицы $ M_{} $ на строку степеней другого примитивного элемента $ \mathfrak B_{} $, отличного от $ \mathfrak A_{} $ и $ \mathfrak A^2 $. Однако такая замена приведет к другой проблеме, о которой будет рассказано ниже.
Можно пойти другим путем: отказаться от требования примитивности, и убедиться только, что все участвующие в матрице $ M_{} $ степени
$$ \mathfrak e, \mathfrak A^3, \mathfrak A^6, \dots , \mathfrak A^{3(N-1)} $$
являются различными. Так, если мы действуем в поле $ \mathbf{GF}(2^8) $, порожденным полиномом $ x^8+x^4+x^3+x+1 $, то вполне спокойно можем применять матрицу $ M_{} $ для $ \mathfrak A=x $, если только в наших исправительных работах участвуют не более $ N=17 $ дисков.
А если взять порождающим полиномом поля $ f(x)=x^8+x^4+x^3+x^2+1 $, то количество дисков можно увеличить вплоть до $ N=85 $.
Иными словами, примитивность элемента $ \mathfrak A $ --- хорошее свойство, но особенно сильно держаться за него не стоит. Если можно гарантировать различность элементов $ \mathfrak e, \mathfrak A, \mathfrak A^2, \dots , \mathfrak A^{(N-1)} $ --- то для целей этого вполне достаточно. В терминологии полей Галуа --- ((:gruppe:galois:vspom2 показатель)) элемента $ \mathfrak A $ должен быть больше $ N-1 $. Для поля $ \mathbf{GF}(2^n) $ этот показатель находится среди делителей числа $ 2^n-1 $ (так что достаточно проверить на равенство $ 1_{} $ нескольких вполне определенных степеней элемента, а не всех подряд идущих...)
Такое решение проблемы позволяет сохранить структуру матрицы $ M_{} $ как матрицы Вандермонда. Это обстоятельство гарантирует выполнение условия: любой минор порядка $ 4_{} $ этой матрицы
$$
\left|
\begin{array}{llll}
\mathfrak e & \mathfrak e & \mathfrak e & \mathfrak e \\
\mathfrak A^{j_1} & \mathfrak A^{j_2} & \mathfrak A^{j_3} & \mathfrak A^{j_4} \\
\mathfrak A^{2j_1} & \mathfrak A^{2j_2} & \mathfrak A^{2j_3} & \mathfrak A^{2j_4} \\
\mathfrak A^{3j_1} & \mathfrak A^{3j_2} & \mathfrak A^{3j_3} & \mathfrak A^{3j_4}
\end{array}
\right|=
$$
$$
=(\mathfrak A^{j_2}-\mathfrak A^{j_1})(\mathfrak A^{j_3}-\mathfrak A^{j_1})(\mathfrak A^{j_4}-\mathfrak A^{j_1})
(\mathfrak A^{j_3}-\mathfrak A^{j_2})(\mathfrak A^{j_4}-\mathfrak A^{j_2})(\mathfrak A^{j_4}-\mathfrak A^{j_3})
$$
отличен от нуля; здесь $ 0\le j_1
вторая проблема