Ниже показан полный ручной расчёт код-слова Ри...

Question

Ниже показан полный ручной расчёт код-слова Рида–Соломона для сообщения «Gauss2026» в типовой схеме
RS (15, 9) над полем 𝔽₂⁸ (GF(256)) c примитивным многочленом
$p(x)=x^{8}+x^{4}+x^{3}+x^{2}+1\;(0x11D)$ .

1. Параметры выбранного кода

Параметр	Значение
Размер алфавита $q$	256 (по 1 байту на символ)
Длина код-слова $n$	15 символов
Длина информационной части $k$	9 символов
Кол-во проверочных символов $n-k$	6 (исправление до 3 ошибок)
Примитивный элемент	$\alpha=0x02$
Генератор	$g(x)=\prod_{i=1}^{6}(x-\alpha^{i}) = x^{6}+63x^{5}+1x^{4}+218x^{3}+32x^{2}+227x+38$

2. Преобразование сообщения

text
 G  a  u  s  s  2  0  2  6
0x47 0x61 0x75 0x73 0x73 0x32 0x30 0x32 0x36
 71   97  117  115 115  50  48  50  54   ← коэффициенты m(x)

Полином сообщения
$m(x)=71x^{8}+97x^{7}+117x^{6}+115x^{5}+115x^{4}+50x^{3}+48x^{2}+50x+54$ .

Для кодирования мы умножаем его на $x^{6}$
и делим на $g(x)$ :

c(x)=x^{6}m(x)-r(x),\qquad r(x)=m(x)x^{6}\bmod g(x)

3. Деление многочленов (метод LFSR)

Шаг	Входной байт	feedback	Сдвинутый регистр перед XOR	Регистр после XOR
1	0x47	0x47	00 00 00 00 00 00	C6 47 B8 08 F1 87
2	0x61	A7	47 B8 08 F1 87 00	BF 1F 63 A8 E1 AC
3	0x75	CA	1F 63 A8 E1 AC 00	09 A9 0E 99 9A FE
…	…	…	…	…
9	0x36	6A	DC 03 D9 E4 DD 00	8F 69 28 25 1E A0

(показаны 1-й, 2-й, 3-й и финальный 9-й шаги; промежуточные можно запросить отдельно).

После прохода всех 9 входных символов получен остаток

r(x) = 0x8F·x⁵ + 0x69·x⁴ + 0x28·x³ + 0x25·x² + 0x1E·x + 0xA0

4. Проверочные символы и итоговое код-слово

text
Проверка (6 байт) : 8F 69 28 25 1E A0
Полное код-слово   : 47 61 75 73 73 32 30 32 36 8F 69 28 25 1E A0

Первые 9 байт — оригинальное сообщение.
Последние 6 байт — вычисленные символы контроля.

Требуется показать все 9 промежуточных шагов деления?
расширь расчёт.Требуется показать все 9 промежуточных шагов деления

Answer 1

Да — вот полный развёрнутый проход всех 9 шагов деления в том же формате LFSR.

Используем тот же генератор:

g(x)=x^6+63x^5+1x^4+218x^3+32x^2+227x+38

То есть для регистра из 6 байт берём коэффициенты:

[63,\;1,\;218,\;32,\;227,\;38]

Правило на каждом шаге:

feedback = входной_байт XOR старший_байт_регистра
Регистр сдвигается влево: $[R_0,R_1,R_2,R_3,R_4,R_5]\to[R_1,R_2,R_3,R_4,R_5,00]$
В сдвинутый регистр XOR-ится вектор $feedback\cdot[63,1,218,32,227,38]$ в поле GF(256) по модулю $0x11D$ .

Начальное состояние регистра:

text
00 00 00 00 00 00

Полная таблица всех 9 шагов

Шаг	Вход	feedback	Сдвиг регистра	$feedback \cdot [63,1,218,32,227,38]$	Регистр после XOR
1	`47`	`47`	`00 00 00 00 00 00`	`C6 47 B8 08 F1 87`	`C6 47 B8 08 F1 87`
2	`61`	`A7`	`47 B8 08 F1 87 00`	`F8 A7 6B 59 66 AC`	`BF 1F 63 A8 E1 AC`
3	`75`	`CA`	`1F 63 A8 E1 AC 00`	`16 CA A6 78 36 FE`	`09 A9 0E 99 9A FE`
4	`73`	`7A`	`A9 0E 99 9A FE 00`	`84 7A D0 FB 55 FA`	`2D 74 49 61 AB FA`
5	`73`	`5E`	`74 49 61 AB FA 00`	`CB 5E DD 0F CF D6`	`BF 17 BC A4 35 D6`
6	`32`	`8D`	`17 BC A4 35 D6 00`	`D0 8D 1E 70 C7 79`	`C7 31 BA 45 11 79`
7	`30`	`F7`	`31 BA 45 11 79 00`	`54 F7 CE 8B 92 83`	`65 4D 8B 9A EB 83`
8	`32`	`57`	`4D 8B 9A EB 83 00`	`11 57 99 32 67 DD`	`5C DC 03 D9 E4 DD`
9	`36`	`6A`	`DC 03 D9 E4 DD 00`	`53 6A F1 C1 C3 A0`	`8F 69 28 25 1E A0`

Те же шаги, но в виде явных XOR

Шаг 1

text
feedback = 47 XOR 00 = 47
shift    = 00 00 00 00 00 00
mult     = C6 47 B8 08 F1 87
result   = 00 00 00 00 00 00
         XOR C6 47 B8 08 F1 87
         =   C6 47 B8 08 F1 87

Шаг 2

text
feedback = 61 XOR C6 = A7
shift    = 47 B8 08 F1 87 00
mult     = F8 A7 6B 59 66 AC
result   = 47 B8 08 F1 87 00
         XOR F8 A7 6B 59 66 AC
         =   BF 1F 63 A8 E1 AC

Шаг 3

text
feedback = 75 XOR BF = CA
shift    = 1F 63 A8 E1 AC 00
mult     = 16 CA A6 78 36 FE
result   = 1F 63 A8 E1 AC 00
         XOR 16 CA A6 78 36 FE
         =   09 A9 0E 99 9A FE

Шаг 4

text
feedback = 73 XOR 09 = 7A
shift    = A9 0E 99 9A FE 00
mult     = 84 7A D0 FB 55 FA
result   = A9 0E 99 9A FE 00
         XOR 84 7A D0 FB 55 FA
         =   2D 74 49 61 AB FA

Шаг 5

text
feedback = 73 XOR 2D = 5E
shift    = 74 49 61 AB FA 00
mult     = CB 5E DD 0F CF D6
result   = 74 49 61 AB FA 00
         XOR CB 5E DD 0F CF D6
         =   BF 17 BC A4 35 D6

Шаг 6

text
feedback = 32 XOR BF = 8D
shift    = 17 BC A4 35 D6 00
mult     = D0 8D 1E 70 C7 79
result   = 17 BC A4 35 D6 00
         XOR D0 8D 1E 70 C7 79
         =   C7 31 BA 45 11 79

Шаг 7

text
feedback = 30 XOR C7 = F7
shift    = 31 BA 45 11 79 00
mult     = 54 F7 CE 8B 92 83
result   = 31 BA 45 11 79 00
         XOR 54 F7 CE 8B 92 83
         =   65 4D 8B 9A EB 83

Шаг 8

text
feedback = 32 XOR 65 = 57
shift    = 4D 8B 9A EB 83 00
mult     = 11 57 99 32 67 DD
result   = 4D 8B 9A EB 83 00
         XOR 11 57 99 32 67 DD
         =   5C DC 03 D9 E4 DD

Шаг 9

text
feedback = 36 XOR 5C = 6A
shift    = DC 03 D9 E4 DD 00
mult     = 53 6A F1 C1 C3 A0
result   = DC 03 D9 E4 DD 00
         XOR 53 6A F1 C1 C3 A0
         =   8F 69 28 25 1E A0

Остаток и код-слово

Итак, окончательный остаток:

text
8F 69 28 25 1E A0

то есть

r(x)=8F\,x^5+69\,x^4+28\,x^3+25\,x^2+1E\,x+A0

И полное систематическое код-слово RS(15,9):

text
47 61 75 73 73 32 30 32 36 8F 69 28 25 1E A0

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

c(\alpha^1),c(\alpha^2),\dots,c(\alpha^6).