Математическая морфология.

Электронный математический и медико-биологический журнал. - Т. 13. -

Вып. 4. - 2014. - URL:

http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM

http://www.smolensk.ru/user/sgma/MMORPH/N-44-html/TITL-44.htm

http://www.smolensk.ru/user/sgma/MMORPH/N-44-html/cont.htm

УДК 681.32

ОСОБЕННОСТИ ПОСТРОЕНИЯ КОДА РИДА-СОЛОМОНА

Ó 2014 г. Пучков Ю. И.

(puchkov.doc)

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

Ключевые слова: поля Галуа, примитивный элемент, порождающий многочлен, корни многочленов, арифметика в полях Галуа.

Коды Рида-Соломона (РС) в настоящее время применяются во многих отраслях, связанных с передачей и хранением информации, в частности в устройствах памяти, в телекоммуникационных системах, в спутниковой связи[1,2]. Но, несмотря на это, они остаются трудными для понимания. Это связано с тем, что приходиться вводить много новых понятий и за их теоретическим обоснованием теряется суть построения кода РС.

Пока не затрагивая сам процесс кодирования, рассмотрим некоторые положения, которые в дальнейшем будут полезны.

Алгебраической системой, используемой при построении кодов, является поле Галуа (GF). Поле GF(q) – это конечное поле, состоящее из q элементов. Число q может быть равным простому числу p или p^m. В первом случае поле называется простым, а во втором расширением соответствующего простого поля. В поле задаются две операции: сложение и умножение, а также выполняются обычные правила ассоциативности, коммутативности, дистрибутивности. Для любого элемента a поля существует обратный элемент и единичный. Причём, для операции сложения обратный элемент это (-a), а для операции умножения - a^-1. Единичный элемент для сложения это (0), а для умножения это (1). То есть каждый элемент поля имеет свой обратный и свой единичный элементы. Эти элементы обеспечивают выполнение следующих равенств a + 0 = a, a∙1= a, a+(-a) = a - a =0, a∙ a^-1= a/ a =1.Последние два равенства используются для выполнения математических операций вычитания и деления. Например, a/b = a∙ b^-1, a –b= a+(-b).

Операции сложения и умножения выполняются по обычным правилам, но результатом операции служит остаток от деления результата соответствующей операции на число элементов q поля (выполняется приведение результата арифметической операции по модулю q). Выполнение этих операции иллюстрирует таблица 1.

Таблица 1. Таблица умножения и сложения для поля GF(5)

∙	0	1	2	3	4	+	0	1	2	3	4
0	0	0	0	0	0	0	0	1	2	3	4
1	0	1	2	3	4	1	1	2	3	4	0
2	0	2	4	1	3	2	2	3	4	0	1
3	0	3	1	4	2	3	3	4	0	1	2
4	0	4	3	2	1	4	4	0	1	2	3

Пример выполнения операций вычитания и деления.

2-4 =2 +(-4) =2+1 =3; 2/3 = 2 ∙ 3^-1 = 2∙ 2 =4

Аналогично выполняются алгебраические операции и с элементами любого простого поля. Но для расширения поля операции сложения и умножения по модулю p^m не используются. Это связано с тем, что p^m не является простым числом.

В дальнейшем станем рассматривать только поле GF(2^m). Причём элементами поля будут являться все многочлены степени m-1 или меньше. Среди этих элементов есть и обратный элемент и единичный элемент. Коэффициенты этих многочленов лежат в поле GF(2), то есть являются (0) или (1). Результат выполнения операции умножения этих многочленов приводится по модулю неприводимого многочлена степени m. Перечень неприводимых многочленов приводиться во многих книгах по теории кодирования и теории передачи информации [2]. Особенностью неприводимых многочленов является то обстоятельство, что они не могут быть разложены на множители, используя многочлены из поля GF(2). Но они могут быть разложены на множители с коэффициентами из расширения этого поля GF(2^m).

Приравняв неприводимый многочлен p(x) нулю можно найти его корни. Но корни его не могут лежать в поле GF(2), поскольку многочлен в этом поле является неприводимым. Корни уравнения p(x) = 0 лежат в поле GF(2^m). Пусть, например, m = 3. Поле GF(2³) имеет 8 элементов, а именно многочлены степени не выше3: 1, x, 1+ x, x², 1+ x², x+ x², 1+ x+ x². Получили 7 элементов поля (без учёта нулевого элемента). Выберем неприводимый многочлен этого поля p(x) =1 + x+ x³. Из условия p(x) = 0 следует, что и

x∙ p(x)=0, и x²∙ p(x)=0 и т.д. Это можно записать и так x³=1+ x, x⁴= x+ x², x⁵= x²+ x³ и т.д. Положим, что корнем уравнения 1 + x+ x³= 0 является элемент α поля (α не число, а именно элемент поля). При подстановке вместо x значения α (x= α)в исходное уравнение, получаем p(x)=0. Учитывая приведённые равенства, запишем, полагая, что элементы поля представляют собой запись двоичных чисел в виде многочленов. Эту запись назовём таблицей 2.

α ⁰ = 1 - 100

α ¹ = x = 2 - 010

α ² = x² = 4 - 001

α ³ = 1+x = 3 - 110

α ⁴ = x + x² = 6 - 011

α ⁵ = x²+ x³ =1+x + x² = 7 - 111

α ⁶ = x+ x²+ x³= 1+ x²= 5 - 101

α ⁷= x + x³ = 1 и т. д.

В данном случае элемент поля α, являющейся корнем неприводимого многочлена, обладает таким свойством, что любой элемент поля является некоторой степенью этого элемента. Такой элемент называют примитивным. В поле может быть несколько примитивных элементов. Примитивные элементы поля находят перебором. Следует отметить, что примитивный элемент является корнем примитивного многочлена, который в свою очередь является одним из неприводимых многочленов поля. В данном случае неприводимый многочлен p(x) является примитивным многочленом. Обычно в литературе, где приводится список неприводимых многочленов, приводятся сведения, какие из них являются примитивными.

Полученные соотношения можно использовать для выполнения операции умножения многочленов в поле GF(2³). Покажем, что элемент α является корнем уравнения p(x)=0. Для этого подставим вместо x элемент α и представим его в виде двоичного кода в соответствии с таблицей 2

p (α) = 1+ α + α³ =(100) +(010) + (110) = 0.

Из этого примера видно, что корнем многочлена является не число, а элемент расширения поля.

Если многочлен p (x) –примитивный многочлен с коэффициентами из поля GF(p) и α – его корень, то α², α⁴, … так же будут его корнями. Примитивный многочлен p(x) третьей степени имеет три корня и, заменяя операцию вычитания операцией сложения, в соответствии с теоремой Безу, можно записать в виде p(x)=( x-α)∙( x- α²)∙( x- α⁴). Если раскрыть скобки и для выполнения алгебраических операций воспользоваться таблицей 2, то получим p (x) = 1+ x + x ³. Задание порождающего многочлена с использованием теоремы Безу применятся в кодах РС.

Код РС представляет собой разновидность БЧХ кодов. Коды РС это q-ичные циклические коды длиной n= q-1 с порождающим многочленом g(x) =Π(x +βⁱ). Здесь Π – знак произведения, а индекс сомножителей i изменяется от 1 до максимальной степени r порождающего многочлена, β – один из примитивных элементов поля GF(q) . Минимальное расстояние кода d = r+1, а число информационных символов k = q-1- r. При построении РС кода, как и при построении БЧХ–кодов задаются длиной кода n и количеством k информационных символов, а затем уже определяется кодовое расстояние d полученного кода. В качестве примитивного элемента для построения порождающего многочлена кода РС выбирают, как правило, наибольший из примитивных элементов поля. Поскольку величины n, k, d связаны вышеприведёнными равенствами, то достаточно задаться какими либо двумя и вычислить третью.

Задавшись значением длины n кода РС, фактически задаём порядок q поля GF(q). В этом поле определяем примитивные элементы и, выбирая один из них, находим порождающий многочлен g(x) кода длиной m = n-k. По полученному порождающему многочлену образуют кодовые комбинации кода РС. Как и при построении циклических двоичных кодов, это можно сделать двумя способами. Во-первых, можно просто умножить информационный многочлен k(x) на порождающий многочлен g(x). Но наиболее часто используют второй способ построения кода. Образуют произведение k(x) ∙ x^m. В результате получают многочлен, у которого последние m -1 разрядов оказываются нулевыми. Полученный многочлен делят на g(x) и получаю m -1 разрядный остаток. Этот остаток просто приписывают вместо последних нулевых элементов многочлена k(x)∙x^m. В такой полученной комбинации кода первые k являются информационными, а оставшиеся m -1 разрядов поверочные. Получаем разделимый код. Порядок q поля GF(q) обычно выбирают из условия q = 2 ^m.

Построим порождающий многочлен для кода РС длиной 7, исправляющий ошибки в двух символах. Полагаем, что поле GF(8) и задаётся таблицей 2. Порождающий многочлен в этом случае будет иметь старшую степень 4 и его записываем в виде

g(x) = ( x- α) ∙ ( x- α²) ∙ ( x- α³) ∙ ( x- α⁴) = x⁴ + α³ x³+ x²+ α x + α³.

Возведения в степень, умножения и сложения выполнены по правилам полей Галуа (в соответствии с таблицей 2). После этого коэффициенты многочлена можно записать в виде их десятичного эквивалента соответствующего двоичного кода. Из таблицы следует, что α = 2, α³= 3 и ,как следствие, получаем порождающий многочлен в виде g(x) = x⁴ + 3 x³ + x² +2 x + 3. Многочлен g(x) имеет коэффициенты из поля GF(8). Информационный многочлен k(x) также имеет коэффициенты из этого поля. Если хотим закодировать сообщение, представленное двоичным кодом, то его необходимо разбить на группы, например, по 4 символа или по 8 символов (по байту), записать десятичный эквивалент каждой группы и затем записать многочлен k(x). Коэффициенты этого многочлена будут десятичными цифрами. При образовании кодовой комбинации кода РС алгебраические операции с коэффициентами необходимо выполнять по правилам соответствующего поля Галуа.

Построим код РС с n = 15 и k =9. Этот код способен исправлять до трёх ошибок: (15 – 9)/2 =3. Степень порождающего многочлена определяется как n - k = 15-9 = 6. Находим порождающий многочлен кода

g(x) = ( x- α) ∙ ( x- α²) ∙ ( x- α³) ∙ ( x- α⁴) ∙ ( x- α⁵) ∙ ( x- α⁶) =

= x⁶+7 x⁵+9 x⁴+3 x³+ 12 x²+10 x +12. Положим, сообщение имеет вид: 7,5,10,0,9,1,1,1,9. Запишем это сообщение в виде информационного многочлена k(x)=9 x⁸+ x⁷+ x⁶ + x⁵+ 9 x⁴+ 10 x²+5 x +7. После его умножения на x⁶ получим 9 x¹⁴+ x¹³ + x¹² + x¹¹ +9 x¹⁰ + 10x⁸+ 5x⁷+ 7x⁶. Разделив этот многочлен на g(x), получим остаток 13x⁵+6x⁴+14x³+15x²+15x+3. Приписываем этот остаток к предыдущему многочлену и получаем закодированное сообщение А(x) = 9 x¹⁴+ x¹³ + x¹² + x¹¹ +9 x¹⁰ + 10x⁸+ 5x⁷+ 7x⁶+13 x⁵+6 x⁴+14 x³+15 x²+15 x +3. Это сообщение передаётся в линию связи, начиная с младшего разряда, и в случае безошибочной передачи на приёмной стороне получаем закодированное сообщение 3,15,15,14,6,13,7,5,10,0,9,1,1,2,9. При построении этого кода использовалось поле GF(16) и составленная для этого поля таблица типа таблицы 2.

Поскольку коды РС имеют большую длину (n= 2^m-1), то порождающую матрицу кода не строят. Но даже если её и построить, то получение из неё других комбинаций кода в виде суммы комбинаций строк матрицы необходимо осуществлять по правилам арифметики полей Галуа. Поэтому поступают иначе. Строят кодирующее устройство и, подавая на его вход информационный многочлен, получают на его выходе комбинацию кода. Код РС обычно применяют как внешний код в каскадном кодировании, и поступающая на вход кодирующего устройства кода РС информационная последовательность может быть самой разнообразной, заранее непредвиденной. Например, для широко используемого кода РС (255,223) информационная последовательность имеет длину в 223 символа. Следует заметить, что энергетический выигрыш кода РС увеличивается с увеличением m и имеет вид кривой с насыщением [2]. Одновременно растёт сложность реализации декодирующего устройства. Поэтому на практике ограничиваются величиной m = 8 т.е. применяют код (255,223).

На вход кодирующего устройства поступает двоичная последовательность и на выходе кодирующего устройства также образуется двоичная последовательность. Для кода (255,223) входная последовательность делиться на байты, десятичный эквивалент которых становиться коэффициентом информационной последовательности. При передаче в линию связи каждый коэффициент кодовой последовательности кода РС снова превращается в байт двоичного кода. Так для указанного кода одна двоичная последовательность в линии связи будет иметь длину 255∙8=2040 символов. Разрядность проверочных символов кода 255-223=32. Следовательно, код может исправлять до 16 ошибок. Под ошибками понимается, как и обычно, ошибки в двоичной выходной последовательности кода. Очевидно, что если произошла хотя бы одиночная ошибка в байте, то при приёме измениться соответствующий символ кода РС.

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

1) вычисляют синдром ошибки (остаток от деления принятой кодовой последовательности на порождающий многочлен);

2) строят полином ошибки;

3) находят корни полинома ошибок;

4) определяют характер ошибки; исправляют ошибку.

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

Литература

1. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ.-М.: Радио и связь, 1987.- 392 с.

2. Камнев В.Е.,Черкасов В.Ф.,Чечин Г.В. Спутниковые сети связи: Учебн. Пособие/В.Е. Камнев, В.Ф. Черкасов, Г.В. Чечин. – М.: «Альпина Поблишер», 2004. – 536 с.

3. Т.Касами, Н. Токура, Е. Ивадари, Я. Инагаки. Теория кодирования. Пер. с япон.:М.: Мир, 1978, 575с.

FEATURES OF CONSTRUCTION OF THE REED-SOLOMON CODE

Puchkov Yu. I.

The encoding and decoding of reed-Solomon codes are difficult to understand engineers familiar with the construction of binary error correcting codes. This is explained by the introduction of a large number of new concepts and unfamiliar arithmetic. In this regard, in this article the review of the code is limited only by questions of its construction, which is stated with engineering positions. Decoding more difficult than coding and it will be described later.

Key words: Galois fields, primitive element, a generating polynomial, roots of polynomials, arithmetic in Galois fields.

Филиал ФГБОУВПО "Национальный исследовательский университет "МЭИ" в г. Смоленске

Поступила в редакцию 8.12.2014.