Так выглядит избыточность.

Коды избыточности* широко применяются в компьютерных системах для увеличения надёжности хранения данных. В Яндексе их используют в очень многих проектах. Например, применение кодов избыточности вместо репликации в нашем внутреннем объектном хранилище экономит миллионы без снижения надёжности. Но несмотря на широкое распространение, понятное описание того, как работают коды избыточности, встречается очень редко. Желающие разобраться сталкиваются примерно со следующим (из Википедии):

Меня зовут Вадим, в Яндексе я занимаюсь разработкой внутреннего объектного хранилища MDS. В этой статье я простыми словами опишу теоретические основы кодов избыточности (кодов Рида Соломона и LRC). Расскажу, как это работает, без сложной математики и редких терминов. В конце приведу примеры использования кодов избыточности в Яндексе.

Ряд математических деталей я не буду рассматривать подробно, но дам ссылки для тех, кто хочет погрузиться глубже. Также замечу, что некоторые математические определения могут быть не строгими, так как статья рассчитана не на математиков, а на инженеров, желающих разобраться в сути вопроса.

* В англоязычной литературе коды избыточности часто называют erasure codes.

1. Суть кодов избыточности

Суть всех кодов избыточности предельно простая: хранить (или передавать) данные так, чтобы они не пропадали при возникновении ошибок (поломках дисков, ошибках передачи данных и т. д.).

В большинстве* кодов избыточности данные разбиваются на n блоков данных, для них считается m блоков кодов избыточности, всего получается n + m блоков. Коды избыточности строятся таким образом, чтобы можно было восстановить n блоков данных, используя только часть из n + m блоков. Далее мы рассмотрим только блочные коды избыточности, то есть такие, в которых данные разбиваются на блоки.

Чтобы восстановить все n блоков данных, нужно иметь минимум n из n + m блоков, так как нельзя получить n блоков, имея только n-1 блок (в этом случае пришлось бы 1 блок брать из воздуха). Достаточно ли n произвольных блоков из n + m блоков для восстановления всех данных? Это зависит от типа кодов избыточности, например коды Рида Соломона позволяют восстановить все данные с помощью произвольных n блоков, а коды избыточности LRC не всегда.

Хранение данных

В системах хранения данных, как правило, каждый из блоков данных и блоков кодов избыточности записывается на отдельный диск. Тогда при поломке произвольного диска исходные данные все равно можно будет восстановить и прочитать. Данные можно будет восстановить даже при одновременной поломке нескольких дисков.

Передача данных

Коды избыточности можно использовать для надёжной передачи данных в ненадёжной сети. Передаваемые данные разбивают на блоки, для них считают коды избыточности. По сети передаются и блоки данных, и блоки кодов избыточности. При возникновении ошибок в произвольных блоках (вплоть до некоторого количества блоков), данные все равно можно безошибочно передать по сети. Коды Рида Соломона, например, используют для передачи данных по оптическим линиям связи и в спутниковой связи.

* Есть также коды избыточности, в которых данные не разбиваются на блоки, например коды Хэмминга и коды CRC, широко применяемые для передачи данных в сетях Ethernet. Это коды для помехоустойчивого кодирования, они предназначены для обнаружения ошибок, а не для их исправления (код Хэмминга также позволяет частично исправлять ошибки).

2. Коды Рида Соломона

Коды Рида Соломона одни из наиболее широко распространённых кодов избыточности, изобретённые ещё в 1960-х и впервые получившие широкое применение в 1980-х для серийного выпуска компакт-дисков.

Ключевых вопросов для понимания кодов Рида Соломона два: 1) как создавать блоки кодов избыточности; 2) как восстанавливать данные с помощью блоков кодов избыточности. Найдем на них ответы.
Для упрощения далее будем считать, что n=6 и m=4. Другие схемы рассматриваются по аналогии.

Как создавать блоки кодов избыточности

Каждый блок кодов избыточности считается независимо от остальных. Для подсчёта каждого блока используются все n блоков данных. На схеме ниже X₁-X₆ блоки данных, P₁P₄ блоки кодов избыточности.

Все блоки данных должны быть одинакового размера, для выравнивания можно использовать нулевые биты. Полученные блоки кодов избыточности будут иметь тот же размер, что и блоки данных. Все блоки данных разбиваются на слова (например, по 16 бит). Допустим, мы разбили блоки данных на k слов. Тогда все блоки кодов избыточности тоже будут разбиты на k слов.

Для подсчёта i-го слова каждого блока избыточности будут использоваться i-е слова всех блоков данных. Они будут считаться по следующей формуле:

Здесь значения x слова блоков данных, p слова блоков кодов избыточности, все альфа, бета, гамма и дельта специальным образом подобранные числа, одинаковые для всех i. Сразу нужно сказать, что все эти значения не обычные числа, а элементы поля Галуа, операции +, -, *, / не привычные всем нам операции, а специальные операции, введённые над элементами поля Галуа.

Зачем нужны поля Галуа

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

1. Как сказано выше, размер слова фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
2. При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.

Эти проблемы не позволяют использовать для кодов Рида Соломона целые числа. Решение проблемы оригинальное, его можно описать следующим образом: давайте придумаем специальные числа, которые можно представить с помощью слов нужной длины (например, 16 бит), и результат выполнения всех операций над которыми (сложение, вычитание, умножение, деление) также будет представлен в памяти компьютера при помощи слов нужной длины.

Такие специальные числа давно изучает математика, их называют полями. Поле это множество элементов с определёнными для них операциями сложения, вычитания, умножения и деления.

Поля Галуа* это поля, для которых существует и единственен результат каждой операции (+, -, *, /) для любых двух элементов поля. Поля Галуа можно построить для чисел, являющихся степенью 2: 2, 4, 8, 16 и т. д. (на самом деле степенью любого простого числа p, но на практике нас интересуют только степени 2). Например, для слов размером 16 бит это поле, содержащее 65 536 элементов, для каждой пары которых можно найти результат любой операции (+, -, *, /). Значения x, p, альфа, бета, гамма, дельта из уравнений выше для расчётов будут считаться элементами поля Галуа.

Таким образом, мы имеем систему уравнений, с помощью которых можно построить блоки кодов избыточности, написав соответствующую компьютерную программу. С помощью этой же системы уравнений можно выполнить восстановление данных.

* Это не строгое определение, скорее описание.

Как восстанавливать данные

Восстановление нужно тогда, когда из n + m блоков часть блоков отсутствует. Это могут быть как блоки данных, так и блоки кодов избыточности. Отсутствие блоков данных и/или блоков кодов избыточности будет означать, что в уравнениях выше неизвестны соответствующие переменные x и/или p.

Уравнения для кодов Рида Соломона можно рассматривать как систему уравнений, в которых все значения альфа, бета, гамма, дельта константы, все x и p, соответствующие доступным блокам, известные переменные, а остальные x и p неизвестные.

Например, пусть блоки данных 1, 2, 3 и блок кодов избыточности 2 недоступны, тогда для i-й группы слов будет следующая система уравнений (неизвестные отмечены красным):

Мы имеем систему из 4 уравнений с 4 неизвестными, значит можем решить её и восстановить данные!

Из этой системы уравнений следуют ряд выводов про восстановление данных для кодов Рида Соломона (n блоков данных, m блоков кодов избыточности):

• Данные можно восстановить при потере любых m блоков или меньше. При потере m+1 и более блоков данные восстановить нельзя: нельзя решить систему из m уравнений с m + 1 неизвестными.
• Для восстановления даже одного блока данных нужно использовать любые n из оставшихся блоков, при этом можно использовать любой из кодов избыточности.

Что ещё нужно знать

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

• Система уравнений для кодов Рида Соломона должна иметь (единственное) решение при любых комбинациях неизвестных (не более m неизвестных). Исходя из этого требования подбираются значения альфа, бета, гамма и дельта.
• Систему уравнений нужно уметь автоматически строить (в зависимости от того, какие блоки недоступны) и решать.
• Нужно построить поле Галуа: для заданного размера слова уметь находить результат любой операции (+, -, *, /) для любых двух элементов.

В конце статьи есть ссылки на литературу по этим важным вопросам.

Выбор n и m

Как на практике выбрать n и m? На практике в системах хранения данных коды избыточности используют для экономии места, поэтому m выбирают всегда меньше n. Их конкретные значения зависят от ряда факторов, в том числе:

• Надёжность хранения данных. Чем больше m, тем большее количество отказов дисков можно пережить, то есть выше надёжность.
• Избыточность хранения. Чем выше соотношение m / n, тем выше будет избыточность хранения, и тем дороже будет стоить система.
• Время обработки запросов. Чем больше сумма n + m, тем дольше будет время ответа на запросы. Так как для чтения данных (во время восстановления) нужно прочитать n блоков, хранящихся на n разных дисках, то время чтения будет определяться самым медленным диском.

Кроме того, хранение данных в нескольких ДЦ накладывает дополнительные ограничения на выбор n и m: при отключении 1 ДЦ данные всё ещё должны быть доступны для чтения. Например, при хранении данных в 3 ДЦ должно выполняться условие: m >= n/2, в противном случае возможна ситуация, когда данные недоступны для чтения при отключении 1 ДЦ.

3. LRC Local Reconstruction Codes

Для восстановления данных с помощью кодов Рида Соломона приходится использовать n произвольных блоков данных. Это очень существенный минус для распредёленных систем хранения данных, ведь для восстановления данных на одном сломанном диске придётся читать данные с большинства остальных, создавая большую дополнительную нагрузку на диски и сеть.

Наиболее часто встречающиеся ошибки недоступность одного блока данных из-за поломки или перегруженности одного диска. Можно ли как-то уменьшить избыточную нагрузку для восстановления данных в таком (наиболее частом) случае? Оказывается, можно: специально для этого существуют коды избыточности LRC.

LRC (Local Reconstruction Codes) коды избыточности, придуманные в Microsoft для применения в Windows Azure Storage. Идея LRC максимально проста: разбить все блоки данных на две (или более) группы и считать часть блоков кодов избыточности для каждой группы по отдельности. Тогда часть блоков кодов избыточности будет подсчитана с помощью всех блоков данных (в LRC они называются глобальными кодами избыточности), а часть с помощью одной из двух групп блоков данных (они называются локальными кодами избыточности).

LRC обозначается тремя числам: n-r-l, где n количество блоков данных, r количество глобальных блоков кодов избыточности, l количество локальных блоков кодов избыточности. Для чтения данных при недоступности одного блока данных нужно прочитать только n/l блоков это в l раз меньше, чем в кодах Рида Соломона.

Для примера рассмотрим схему LRC 6-2-2. X₁X₆ 6 блоков данных, P₁, P₂ 2 глобальных блока избыточности, P₃, P₄ 2 локальных блока избыточности.

Блоки кодов избыточности P₁, P₂ считаются с помощью всех блоков данных. Блок кодов избыточности P₃ с помощью блоков данных X₁X₃, блок кодов избыточности P₄ с помощью блоков данных X₄X₆.

Остальное делается в LRC по аналогии с кодами Рида Соломона. Уравнения для подсчёта слов блоков кодов избыточности будут такими:

Для подбора чисел альфа, бета, гамма, дельта нужно выполнить ряд условий, гарантирующих возможность восстановления данных (то есть решения системы уравнения). Подробнее о них можно прочитать в статье.
Также на практике для подсчёта локальных кодов избыточности P₃, P₄ применяют операцию XOR.

Из системы уравнений для LRC следует ряд выводов:

• Для восстановления любого 1 блока данных достаточно прочитать n/l блоков (n/2 в нашем примере).
• Если недоступно r + l блоков, и при этом все блоки входят в одну группу, то данные восстановить нельзя. Это легко объяснить на примере. Пусть недоступны блоки X₁X₃ и P₃: это r + l блоков из одной группы, 4 в нашем случае. Тогда у нас есть система из 3 уравнений с 4 неизвестными, которую нельзя решить.
• Во всех остальных случаях недоступности r + l блоков (когда из каждой группы доступен хотя бы один блок) данные в LRC можно восстановить.

Таким образом, LRC выигрывает у кодов Рида Соломона в восстановлении данных после одиночных ошибок. В кодах Рида Соломона для восстановления даже одного блока данных нужно использовать n блоков, а в LRC для восстановления одного блока данных достаточно использовать n/l блоков (n/2 в нашем примере). С другой стороны, LRC проигрывает кодам Рида Соломона по максимальному количеству допустимых ошибок. В примерах выше коды Рида Соломона могут восстановить данные при любых 4 ошибках, а для LRC существует 2 комбинации из 4 ошибок, когда данные восстановить нельзя.

Что более важно зависит от конкретной ситуации, но зачастую экономия избыточной нагрузки, которую даёт LRC, перевешивает чуть меньшую надёжность хранения.

4. Другие коды избыточности

Помимо кодов Рида Соломона и LRC, есть много других кодов избыточности. Разные коды избыточности используют разную математику. Вот некоторые другие коды избыточности:

• Код избыточности с помощью оператора XOR. Операция XOR выполняется над n блоками данных, и получается 1 блок кодов избыточности, то есть схема n+1 (n блоков данных, 1 код избыточности). Используется в RAID 5, где блоки данных и кодов избыточности циклически записываются на все диски массива.
• Алгоритм even-odd, основанный на операции XOR. Позволяет построить 2 блока кодов избыточности, то есть схема n+2.
• Алгоритм STAR, основанный на операции XOR. Позволяет построить 3 блока кодов избыточности, то есть схема n+3.
• Pyramide codes ещё одни коды избыточности от Microsoft.

5. Использование в Яндексе

Ряд инфраструктурных проектов Яндекса применяет коды избыточности для надёжного хранения данных. Вот несколько примеров:

• Внутреннее объектное хранилище MDS, о котором я писал в начале статьи.
• YT MapReduce-система Яндекса.
• YDB (Yandex DataBase) распределённая база данных newSQL.

В MDS используются коды избыточности LRC, схема 8-2-2. Данные с кодами избыточности пишутся на 12 разных дисков в разных серверах в 3 разных ДЦ: по 4 сервера в каждом ДЦ. Подробнее об этом читайте в статье.

В YT используются как коды Рида Соломона (схема 6-3), которые были реализованы первыми, так и коды избыточности LRC (схема 12-2-2), причём LRC предпочтительный способ хранения.

В YDB используются коды избыточности, основанные на even-odd (схема 4-2). Про коды избыточности в YDB уже рассказывали на Highload.

Применение разных схем кодов избыточности обусловлено разными требованиями, предъявляемыми к системам. Например, в MDS данные, хранимые с помощью LRC, размещаются сразу в 3 ДЦ. Нам важно, чтобы данные оставались доступными для чтения при выходе из строя 1 любого ДЦ, поэтому блоки должны быть распределены по ДЦ так, чтобы при недоступности любого ДЦ количество недоступных блоков было не больше допустимого. В схеме 8-2-2 можно разместить по 4 блока в каждом ДЦ, тогда при отключении любого ДЦ будет недоступно 4 блока, и данные можно будет читать. Какую бы схему мы ни выбрали при размещении в 3 ДЦ, в любом случае должно быть (r + l) / n >= 0,5, то есть избыточность хранения будет минимум 50%.

В YT ситуация другая: каждый кластер YT целиком располагается в 1 ДЦ (разные кластеры в разных ДЦ), поэтому там нет такого ограничения. Схема 12-2-2 даёт избыточность 33%, то есть хранить данные выходит дешевле, при этом они также могут переживать до 4 одновременных отключений дисков, как и схема в MDS.

Есть ещё много особенностей применения кодов избыточности в системах хранения и обработки данных: нюансы восстановления данных, влияние восстановления на время выполнения запросов, особенности записи данных и т. д. Я собираюсь отдельно рассказать об этих и других особенностях применения кодов избыточности на практике, если тема будет интересна.

6. Ссылки

1. Серия статей про коды Рида Соломона и поля Галуа: http://personeltest.ru/aways/habr.com/ru/company/yadro/blog/336286/
   http://personeltest.ru/aways/habr.com/ru/company/yadro/blog/341506/
   В них доступным языком глубже рассматривается математика.
2. Статья от Microsoft про LRC: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   В разделе 2 кратко объясняется теория, далее рассматривается опыт применения LRC на практике.
3. Схема even-odd: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. Схема STAR: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. Pyramid codes: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. Коды избыточности в MDS: http://personeltest.ru/aways/habr.com/ru/company/yandex/blog/311806
7. Коды избыточности в YT: http://personeltest.ru/aways/habr.com/ru/company/yandex/blog/311104/
8. Коды избыточности в YDB: https://www.youtube.com/watch?v=dCpfGJ35kK8

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

И так, я отвлёкся. В детстве-юношестве для помехоустойчивого кодирования можно было бы применить контроль чётности по матричному методу, но сейчас это не серьёзно. Полистав интернет я решил остановиться на кодировании по методу Рида-Соломона. Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент. В этой статье о самих кодах Рида-Соломона я не буду сильно распространяться это за меня на Хабре сделали много раз и много кто. Здесь я хочу описать реализацию алгоритма умножения в GF[256]. Тем не менее, чтобы не заставлять читателя прыгать по ссылкам, кратенько опишу зачем вообще приходится иметь дело
с полями Гаула.

Избыточное кодирование Рида-Соломона это о матрицах. Мы используем матрицы при кодировании и при декодировании. В этих процессах присутствуют как операции умножения матриц, так и операции нахождения обратных матриц деления. Деление здесь требуется не приблизительное-целочисленное, а самое настоящее, точное. А точное деление для компьютера нерешаемая задача: один разделить на три это ноль целых и бесконечное количество троек после запятой, но память при этом 640 килобайт хватит каждому.

Гаул жил в начале 19 века, жил очень мало (21 год, вообще про его личность история интересная, но сейчас не об этом). Его работы очень сильно пригодились при цифровом кодировании. Конечное поле Гаула это набор чисел от нуля до n. Суть и интересность этих полей в том, что для элементов этого набора можно определить операции сложения-умножения-вычитания-деления такие, что результат операции будет находиться в самом этом поле. Например, возьмём набор (поле):

$$display$$[0,1,2,3,4,5,6,7]$$display$$

2+2=4 в этом поле также, как и в поле привычных нам, действительных чисел. А вот 5+6 равно не 11, как мы привыкли, а 5+6=3, и это замечательно! 3 входит в это поле (вообще сложение и вычитание для конкретно этого поля это просто побитовый XOR). Для умножения и деления тоже выполняется правило: результат от умножения или деления любых двух чисел из поля (набора Далее буду говорить только поле) будет находиться в этом поле.

Вообще, количество элементов поля это число не произвольное. Оно называется характеристикой поля и может быть либо простым числом, либо степенью простого числа (её называют порядком поля, основание этой степени называют основанием поля). К счастью, количество чисел, которое можно зашифровать с помощью одного байта равно 256, а это два (простое число) в степени 8, и мы можем принять множество всех возможных значений байта за конечное поле Гаула. По умному оно называется GF[256], GF значит Galois Field.

Так вот. Если использовать арифметику в поле Гаула над байтами, то при делении матриц, состоящих из байтов никогда не получится чисел, которые нельзя записать в один байт, а значит то, как реализовывать в железе (я использую stm32 в основном) алгоритмы кодирования-декодирования становится немного понятнее.

Немного об арифметике. Сложение и вычитание, как упоминалось ранее, это одна и та же операция в полях Гаула (это точно верно для полей с основанием 2), и реализуется она как побитовый XOR.

$$display$$A+B = A xor B$$display$$

$$display$$A-B = A xor B$$display$$

Просто до ужаса. Но когда заходит речь об умножении и делении начитнается что-то, что для человека с натянутыми отношениями с математикой (да, это про меня) не так ясно, как день на луне.

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

Пример:

$$display$$5=101_2=1*x^2+0*x^1+1*x^0=x^2+1$$display$$

Далее полиномы перемножаются по правилам перемножения полиномов, то есть каждый член в первой скобке умножается на каждый член во второй, но не просто так, а с учётом того, что коэффициент не может быть больше одного.

$$display$$x^2+x^2=0$$display$$

$$display$$x^2+x^2+x^2=x^2$$display$$

$$display$$x^2+x^2+x^2+x^2=0$$display$$

То есть коэффициенты складываются по модулю 2. Пример умножения в GF[8]:

$$display$$6*3 = 110_2*11_2= (1*x^2+1*x^1+0*x^0)*(1*x^1+1*x^0)=$$display$$

$$display$$ =(x^2+x)(x+1)=x^2*x+x^2*1+x*x+x*1=$$display$$

$$display$$=x^3+x^2+x^2+x$$display$$

Далее складываем (в кавычках потому, что по модулю 2) подобные члены, и получаем $inline$x^3+x$inline$, что мы переводим в обычное число $inline$1010_2=10$inline$.

Так как это умножение мы подразумевали в GF[8], то число 10 в результате должно вызвать недоумение: Как же так? 10 нету в наборе [0,1,2,3,4,5,6,7]. И да. Тут кроется ещё ложка дёгтя. Если получается такая ситуация (результат перемножения не в поле), то далее мы проводим операцию деления по правилам полиномов. Причём делим мы не на что попало, а на определённый, так называемый порождающий полином. Откуда он берётся? Почему делится только сам на себя? И прочие вопросы я оставлю без ответа (не потому, что жадный, а потому что не хочу вводить в заблуждение, сам плохо понимаю). Скажу лишь, что для конкретного поля Гаула есть один или несколько таких подходящих порождающих полиномов. Для GF[8] их всего два: 11 и 13, то есть 1011 и 1101 или $inline$x^3+x+1$inline$ и $inline$x^3+x^2+1$inline$

И так, чтобы умножить 6 на 3 в поле GF[8] недостаточно лишь перемножить два многочлена. После перемножения надо результат $inline$x^3+x$inline$ поделить на один из возможных порождающих многочленов. Здесь мы выберем $inline$x^3+x+1$inline$. Правила деления многочленов столбиком здесь похожи на те, которые мы должны помнить из школьной программы, но во-первых должны, а во вторых они всё же отличаются. Поясню на нашем примере. Берём старшую степень делимого, в нашем случае это $inline$x^3$inline$ и делим на старшую степень делителя (здесь это также $inline$x^3$inline$). Записываем результат 1. Далее получившийся результат умножаем на весь делитель (получается $inline$x^3+x+1$inline$). Это мы записываем под делимым, и проводим вычитание (а в поле GF[8] вычитание и сложение есть одно и то же) то есть $inline$(x^3+x) +(x^3+x+1)$inline$. Сложение проводим по модулю 2, этому нас обязывает работа в поле, и получаем 1. Далее этот результат мы опять бы делили на порождающий многочлен таким же образом, если бы степень получившегося результата (после вычитания) была бы больше или равной степени делителя (порождающего многочлена). А так как степень меньше, то мы за результат деления принимаем остаток от деления, то есть результат вычитания(сложения здесь это одно и тоже), то есть 1.

Всё. 6 * 3 = 1 для GF[8] c порождающим полиномом 11.

Казалось бы всё непросто. С такими сложностями нужно много-много кода и суперкомпьютеры и вообще проще хранить таблицу умножения как массив 256х256 (ну или 8х8, смотря какое поле мы используем), Но всё не так плохо. У полей Гаула есть ещё одно замечательное свойство, и связано оно с операцией возведения в степень. Так как возведение в степень это просто последовательное умножение, то результат возведения в степень так же является элементом поля Гаула. Также для любого поля верно утверждение, что в нём есть минимум один элемент, степени которого содержат в себе всё поле (кроме 0). То есть, если взять для GF[8] число 2, то
$inline$2^0=1$inline$$inline$2^7=1$inline$
$inline$2^1=2$inline$$inline$2^8=2$inline$
$inline$2^2=4$inline$$inline$2^9=4$inline$
$inline$2^3=3$inline$$inline$2^{10}=3$inline$
$inline$2^4=6$inline$$inline$2^{11}=6$inline$
$inline$2^5=7$inline$$inline$2^{12}=7$inline$
$inline$2^6=5$inline$$inline$2^{13}=5$inline$

Если присмотреться, то можно обратить внимание, что любое число от 1 до 7 можно однозначно представить как 2 в какой либо степени. Так же свойство операции возведения в степень в этом поле таково, что $inline$2^7=2^0$inline$ ещё $inline$2^8=2^1$inline$, $inline$2^9=2^2$inline$ и так далее. Это значит, что 2 в любой степени может быть представлено в виде двойки в степени от нуля до 6 с помощью операции получения остатка от деления на 7 в случае положительной степени и простой формулы $inline$2^{-x}=2^{(7-(x\: mod\:7))}$inline$, если показатель отрицательное число

Собственно, если вспомнить свойство умножения степеней, то умножение чисел многократно упрощается. И чтобы умножить 6 на 3 мы теперь смотрим, в какой степени двойка равна 6 и в какой степени двойка равна 3, складываем степени и смотрим результат два в какой-то степени, которую можно представть как 2 в степени от 0 до 6 пример:

$$display$$6*3=2^4*2^3=2^{(4+3)} = 2^7 = 2^0 = 1 $$display$$

С делением тоже всё становится предельно понятно:

$$display$$3/6=2^3/2^4=2^{(3-4)} = 2^{-1} = 2^{(7-(1\: mod\:7))} = 2^6 = 5 $$display$$

И вроде бы вот оно! счастье программиста реализация арифметики в поле Гаула пара строчек кода, не нужно заморачиваться с полиномами Да и быстродействие такого кода будет высоким, но тут я столкнулся с ещё одной проблемой: Таблицу степеней двойки в поле GF[8] с порождающим полиномом 11 найти легко. Даже на этом ресурсе есть. А вот таблицу степеней для GF[256] я с нахрапа не нагуглил, так что решил её составить самостоятельно, C# мне в помощь. Пришлось реализовать алгоритм умножения по правилам полиномов.

Привожу рабочую функцию перемножения для GF[2^n] c произвольным полиномом. Ограничение я испольую 32-битную арифметику, так что n должно быть меньше 16. Также здесь добавлена функция поиска номера старшего бита числа

private uint GetLeadBitNum(UInt32 Val) {    int BitNum = 31;    uint CmpVal = 1u << BitNum;    while (Val < CmpVal) {        CmpVal >>= 1;        BitNum--;    }    return (uint)BitNum;}private uint Galois_b2_ext_mult(uint m1, uint m2, uint Poly) {    if (0 == m1 || 0 == m2) { return 0; }    uint m1_tmp = m1;    uint m2_tmp;    uint m1_bit_num = 0;        //Перемножение двух полиномов, при использовании арифметики по модулю 2 достаточно простое занятие.    //перебираем единички и нолики (для каждого бита первого числа перебираем все биты второго (или наоборот)), складываем номера позиций битов,    //но не всегда, а только когда оба перебираемых бита - единицы, и инвертируем бит результата под номером, равном сумме позиций для данного шага перебора    //(инверсия - это прибавление единицы по модулю 2)    uint PolyMultRez = 0;    while (m1_tmp != 0) {        uint bit_m1 = (m1_tmp & 1u) == 0u ? 0u : 1u;        m1_tmp = m1_tmp >> 1;        m2_tmp = m2;        uint m2_bit_num;        m2_bit_num = 0;        while (m2_tmp != 0) {            uint bit_m2 = (m2_tmp & 1u) == 0u ? 0u : 1u;            m2_tmp = m2_tmp >> 1;            if ((bit_m1 != 0) && (bit_m2 != 0)) {                int BitNum = (int)(m2_bit_num + m1_bit_num);                PolyMultRez ^= 1u << BitNum;            }            m2_bit_num = m2_bit_num + 1;        }        m1_bit_num = m1_bit_num + 1;    }    //Тут есть результат умножения полиномов PolyMultRez. Осталось найти остаток от деления на выбранный порождающий полином.    //Деление полиномов происходит так: Берём старшую степень делимого, и вычитаем старшую степень делителя.     //Получаем число - степень частного    //Теперь перемножаем, а по сути, просто прибавляем к каждой степени делителя степень получившегося частного    //и повторяем всё по кругу, пока степень делимого не окажется меньше степени делителя    uint TmpDivisor_lead_bit_n;    uint TmpQuotient;    uint TmpDivisor = Poly;    uint TmpDividend = PolyMultRez;    uint TmpDividend_LeadBitNum;    uint TmpMult_bitNum;    uint TmpMult_rez;    TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);    TmpDivisor_lead_bit_n = GetLeadBitNum(TmpDivisor);    while (TmpDividend_LeadBitNum >= TmpDivisor_lead_bit_n) {        TmpQuotient = (TmpDividend_LeadBitNum - TmpDivisor_lead_bit_n);        TmpMult_bitNum = 0;        TmpMult_rez = 0;        while (TmpDivisor != 0) {            uint bit_TmpMult = (TmpDivisor & 1u) == 0u ? 0u : 1u;            TmpDivisor >>= 1;            TmpMult_rez ^= bit_TmpMult << (int)(TmpQuotient + TmpMult_bitNum);            TmpMult_bitNum = TmpMult_bitNum + 1;        }        TmpDividend = TmpDividend ^ TmpMult_rez;        TmpDivisor = Poly;        TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);    }                //Результат умножения числел есть остаток от деления произведения многочленов на порождающий полином.    return TmpDividend;}

Теперь, с помощью приведённой выше функции можно составить таблицу степеней двойки для нужного мне GF[256] и написать модуль арифметики Гаула для stm32 с использованием двух таблиц по 256 одна для прямого, вторая для обратного преобразования числа в его степень. К самой реализации кодирования Рида-Соломона я ещё даже не приступал, но, когда будет готово, думаю поделюсь здесь же. Надеюсь, получится короче.