Рахман П.А. - Кодирование информации

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«УФИМСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Филиал ФГБОУ ВПО УГНТУ в г. Стерлитамаке

Кафедра автоматизированных технологических и информационных систем

П.А. РАХМАН

КОДИРОВАНИЕ ИНФОРМАЦИИ С ПРИМЕНЕНИЕМ КОДОВ РИДА-СОЛОМОНА

Учебное пособие по выполнению самостоятельной и практической работы

Стерлитамак, 2012

2

УДК 519.725.2 + 512.624.2 ББК 32.811.4я73 Р27

Рецензенты зам. директора по учебной и научной работе

филиала УГАТУ в г. Стерлитамаке, доктор технических наук, профессор Галиев А.Л.;

зав. лаб. технологии и переработки ПВХ инженерно-производственного центра ОАО «Каустик»,

член-корр. РАЕН, доктор технических наук, профессор Нафикова Р.Ф.

Рахман П.А.

Р27 Кодирование информации с применением кодов Рида-Соломона: учебное пособие / П.А. Рахман. – Уфа: УГНТУ, 2012 – 167 с.

Посвящено технологии кодирования информации с применением кодов Рида-Соломона для повышения надежности хранения и передачи информации. В пособии приведены основы алгебры конечных полей и алгебраической теории кодирования, алгоритмы кодирования и декодирования кодов РС, а также вероятностный анализ искажений.

Предназначено для аспирантов и студентов технических вузов, обучающихся по направлению «220700 – Автоматизация технологических процессов и производств», изучающих дисциплины «Математические основы передачи информации» и «Диагностика и надежность автоматизированных систем».

УДК 519.725.2 + 512.624.2 ББК 32.811.4я73

© Уфимский государственный нефтяной технический университет, 2012

3

Введение

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

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

1. Кратко о конечных полях и общей алгебре.

Основная трудность в понимании технологии кодирования заключается в том, что она базируется не на привычной со школы алгебре бесконечного поля действительных чисел, а на специальной алгебре конечного поля Галуа [1, 2, 3]. Более того, сама по себе технология кодирования базируется на, так называемой, алгебраической теории кодирования [6-14]. Соответственно, чтобы разобраться в технологии, необходимо сначала познакомиться с основами общей алгебры [1, 5] и алгебраическими структурами, рассматриваемыми в ней, в том числе с конечным полем Галуа.

Алгебра. Пусть задано некоторое множество элементов G. Пусть задан набор операций { 1, , m} с некоторыми заданными арностями {n1, ,nm}, каждая

i я :1 i m из которых любым ni элементам из множества G ставит в соответствие некоторый элемент из этого же множества. Если ni 1, то операция i называется унарной

(одноместной), если ni 2, то операция i называется бинарной (двуместной), и так далее.

Тогда множество G, c заданным набором операций { 1, , m} называется алгебраической

структурой или просто алгеброй. При этом множество элементов G также называют носителем или основой алгебры, вектор арностей {n1, ,nm} называют типом, а набор

операций { 1, , m} называют сигнатурой. Носитель G не обязательно конечен, но не пуст: |G | 0. Арность любой из операций конечна, набор операций также конечен.

4

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

Ярким примером алгебраической структуры, хорошо известным еще со школьной скамьи, является поле действительных чисел <R, {+, ·}>, состоящее из бесконечного множества действительных чисел R и двух бинарных операций: сложения и умножения, ставящих любым двум элементам множества R в соответствие некоторый третий элемент из этого множества. Кроме того, обе операции обладают рядом свойств, которые мы обсудим подробнее ниже при рассмотрении понятия поля.

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

Полугруппа. Алгебраическая структура, состоящая из некоторого множества элементов G и одной бинарной операции, обозначим ее значком , ставящей в соответствие любым двум элементам a и b множества G некоторый третий элемент c этого множества, называется полугруппой, если бинарная операция обладает единственным свойством:

Свойство ассоциативности: a,b,c G:(a b) c a (b c).

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

Моноид. Алгебраическая структура, состоящая из некоторого множества элементов G и одной бинарной операции, обозначим ее значком , ставящей в соответствие любым двум элементам a и b множества G некоторый третий элемент c этого множества, называется моноидом, если бинарная операция обладает двумя свойствами:

Свойство ассоциативности: a,b,c G :(a b) c a (b c).

Существование нейтрального элемента e относительно бинарной операции такого, что операция любого элемента a множества G c нейтральным элементом e снова дает элемент a: a G, e G:e a a e a.

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

Отметим также, что подмножество всех элементов множества G за исключением нейтрального элемента e, вместе с заданной бинарной операцией, образуют полугруппу. Иными словами, моноид по определению содержит в себе полугруппу.

Группа. Алгебраическая структура, состоящая из некоторого множества элементов G и одной бинарной операции, обозначим ее значком , ставящей в соответствие любым двум элементам a и b множества G некоторый третий элемент c этого множества, называется группой, если бинарная операция обладает следующими тремя свойствами:

Свойство ассоциативности: a,b,c G :(a b) c a (b c).

Существование нейтрального элемента: a G, e G:e a a e a.

Существование для каждого элемента множества G такого обратного элемента относительно бинарной операции, что операция элемента с обратным ему элементом дает нейтральный элемент e: a G, a G :a a a a e .

5

Определение 1. Если для бинарной операции дополнительно выполняется свойство коммутативности: a,b G :a b b a, то группа называется коммутативной (абелевой) по заданной бинарной операции, или более коротко: коммутативной (абелевой) группой.

Определение 2. Если под операцией понимается операция сложения, обозначаемая знаком +, то группа называется аддитивной, нейтральный элемент называется нулем (нулевым элементом), обозначается 0, а обратный элемент обозначается –a. Если под операцией понимается операция умножения, обозначаемая знаком ·, то группа называется

мультипликативной, нейтральный элемент называется единицей (единичным элементом)

и обозначается 1, а обратный элемент обозначается a-1.

Определение 3. Число элементов множества G, составляющего группу, называют порядком группы. Если порядок группы бесконечен, то такая группа называется бесконечной. Если же порядок группы конечен, то группа называется конечной.

Определение 4. Конечная группа называется циклической, если множество ее элементов представляет собой последовательность из результатов u-кратной композиции некоторого, так называемого, порождающего элемента ζ группы с самим собой при помощи бинарной операции , где 0 u q 1, причем q – наименьшее целое, при котором начинаются «повторения», иными словами u-кратная композиция дает такой же результат, что и 0-кратная композиция. При этом за результат 0-кратной композиции принимается нейтральный элемент e, который также по определению входит в группу. Иными словами циклическая группа состоит из q элементов: {e, e ζ, (e ζ) ζ, …, (…(e ζ) ζ … ζ)} и бинарной операции . Порядок циклической группы равен числу q элементов группы.

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

Кольцо. Пусть задано множество элементов G и две бинарные операции: сложения, обозначим ее + и умножения, обозначим ее ·, ставящие любым двум элементам множества G некоторый третий элемент этого множества. Пусть множество элементов G вместе с бинарной операцией сложения образует коммутативную аддитивную группу: соблюдается свойство ассоциативности и коммутативности относительно операции сложения, существует нейтральный элемент по сложению, и для каждого элемента существует обратный элемент по сложению. Также пусть множество G вместе с бинарной операцией умножения образует мультипликативную полугруппу: соблюдается свойство ассоциативности относительно операции умножения. Наконец, пусть дополнительно соблюдается свойство дистрибутивности операции умножения относительно операции сложения, причем как слева,

так и справа: a,b,c G :a (b c) a b a c и a,b,c G :(b c) a b a c a. В таком случае множество элементов G и две бинарные операции: сложения и умножения, обладающие всеми вышеперечисленными свойствами, образуют алгебраическую структуру, называемую кольцом. Таким образом, в кольце с множеством элементов G и двумя бинарными операциями по определению соблюдаются следующие шесть свойств:

Ассоциативность по сложению: a,b,c G :(a b) c a (b c).

Существование нейтрального элемента по сложению: a G, 0 G:0 a a 0 a.

Существование для каждого элемента множества G обратного элемента по сложению

a G, a G:a ( a) ( a) a 0.

Коммутативность по сложению: a,b G : a b b a.

Ассоциативность по умножению: a,b,c G :(a b) c a (b c).

Дистрибутивность операции умножения (слева и справа) относительно операции сложения: a,b,c G :a (b c) a b a c и a,b,c G :(b c) a b a c a.

Определение 1. Если операция умножения в кольце обладает дополнительным свойством коммутативности: a,b G : a b b a, то кольцо называется коммутативным по умножению, или более коротко: коммутативным кольцом.

6

Определение 2. Если во множестве элементов кольца существует нейтральный элемент по умножению, называемый единицей и обозначаемый 1, такой, что умножение любого элемента a множества G на нейтральный элемент по умножению снова дает элемент a, иными словами: a G, 1 G:1 a a 1 a, то кольцо называют кольцом с единицей.

В качестве примера можно привести коммутативное кольцо с единицей, состоящее из множества целых чисел Z и двух заданных бинарных операций: сложения + и умножения ·.

Поле. Пусть задано множество элементов G и две бинарные операции: сложения, обозначим ее + и умножения, обозначим ее ·, ставящие любым двум элементам множества G некоторый третий элемент этого множества. Пусть множество элементов G и две бинарные операции сложения и умножения образуют коммутативное кольцо с единицей (выполняются шесть свойств кольца, а также два дополнительных свойства коммутативности по умножению и существования нейтрального элемента по умножению). Пусть дополнительно соблюдается еще одно свойство: для каждого ненулевого элемента (не являющегося нейтральным элементом по сложению, то есть нулем) существует обратный элемент по умножению, иными словами a G:a 0; a 1 G:a a 1 a 1 a 1. Тогда множество G и две бинарные операции сложения и умножения образуют алгебраическую структуру, называемую полем. Таким образом, в поле с множеством элементов G и двумя бинарными операциями по определению соблюдаются следующие девять свойств:

Ассоциативность по сложению: a,b,c G :(a b) c a (b c).

Существование нейтрального элемента по сложению: a G, 0 G:0 a a 0 a.

Существование обратного элемента по сложению для каждого элемента множества G:

a G, a G :a ( a) ( a) a 0.

Коммутативность по сложению: a,b G : a b b a.

Ассоциативность по умножению: a,b,c G :(a b) c a (b c).

Дистрибутивность операции умножения (слева и справа) относительно операции

сложения: a,b,c G :a (b c) a b a c и a,b,c G :(b c) a b a c a.

Коммутативность по умножению: a,b G : a b b a.

Существование нейтрального элемента по умножению: a G, 1 G :1 a a 1 a.

Существование обратного элемента по умножению для каждого ненулевого элемента множества G: a G:a 0, a 1 G:a a 1 a 1 a 1.

Число элементов множества G, составляющего поле, называют порядком поля. Порядок поля с бесконечным числом элементов бесконечен, и такое поле называется бесконечным. Если же число элементов конечно, то поле называется конечным.

Ярким примером поля является бесконечное поле действительных чисел, состоящее из множества действительных чисел R и двух бинарных операций сложения + и умножения ·.

Поле Галуа. Если число элементов поля конечно, то мы имеем конечное поле, которое также называют полем Галуа по имени их первого исследователя, Эвариста Галуа. Поле Галуа обозначается GF(q). Аббревиатура GF – это сокращение от словосочетания Galois Field, а q – число элементов поля по определению является порядком поля.

Определение 1. Поле Галуа GF(q) по определению содержит единичный элемент 1 (нейтральный элемент по умножению). Тогда, наименьшее целое число 0 такое, что

1 1 1 1 0, называют характеристикой поля. Отметим также, что при помощи

слагаемых

единичного элемента поля можно породить циклическую аддитивную группу порядка . Определение 2. Пусть задан ненулевой элемент a поля Галуа GF(q). Наименьшее

целое число 0 такое, что a a a a 1, называют порядком элемента a. Отметим

множителей

также, что при помощи элемента a, порядок которого равен , можно породить циклическую мультипликативную группу порядка .

7

Особо отметим, что поля Галуа существуют не для любого q. Согласно общей алгебре, поле Галуа можно построить только для числа q, являющегося либо простым числом p, либо некоторой степенью простого числа, то есть pm, где m – целое число ≥ 2.

Определение 3. Поле порядка q, являющегося простым числом p, называют простым полем Галуа и обозначают GF(p), а поле порядка q = pm, называют расширенным полем Галуа и обозначают GF(pm), и оно является расширением простого поля GF(p).

Согласно общей алгебре для заданного числа q, равного простому числу p или некоторой его степени pm, существует одно и только одно поле Галуа GF(q).

Простое поле Галуа. Ярким примером простого поля Галуа является поле GF(2) = <{0, 1}, {+, ·}>, состоящее всего из двух элементов: 0, являющегося нейтральным элементом по сложению, и 1, являющегося нейтральным элементом по умножению, а также двух операций, сложения и умножения, со следующими «таблицами сложения и умножения»:

Заметим, что обратным элементом по сложению для 0 является сам элемент 0, а для элемента 1 – сам элемент 1. Обратным элементом по умножению для единственного ненулевого элемента 1 – сам элемент 1. Порядок поля равен 2, поскольку поле содержит всего два элемента, кроме того, характеристика поля также равна 2, поскольку 1 1 0, т.е. две единицы в сумме уже дают нулевой элемент.

Отметим, что простое поле GF(2) является наименьшим возможным простым полем. Приведем еще один пример простого поля GF(3) = <{0, 1, 2}, {+, ·}>, с нейтральным элементом по сложению: 0, с нейтральным элементом по умножению: 1, и со следующими

«таблицами сложения и умножения»:

Заметим, что обратным элементом по сложению для 0 является сам элемент 0, для 1 – элемент 2, для 2 – элемент 1. Обратным элементом по умножению элемента 1 является сам элемент 1, а для элемента 2 – сам элемент 2. Порядок поля равен 3, поскольку поле содержит всего три элемента, кроме того, характеристика поля также равна 3, поскольку 1 1 1 (1 1) 1 2 1 0, т.е. три единицы в сумме уже дают нулевой элемент.

Наконец, приведем пример простого поля GF(5) = <{0, 1, 2, 3, 4}, {+, ·}>, с нейтральным элементом по сложению: 0, с нейтральным элементом по умножению: 1, и со следующими «таблицами сложения и умножения»:

Заметим, что обратным элементом по сложению для 0 является сам элемент 0, для 1 – элемент 4, для 2 – элемент 3, для 3 – элемент 2, для 4 – элемент 1. Обратным элементом по умножению для 1 является сам элемент 1, для 2 – элемент 3, для 3 – элемент 2, для 4 – сам элемент 4. Порядок поля равен 5, поскольку оно состоит из пяти элементов. Кроме того, характеристика поля равна 5, поскольку сумма из 5 единичных элементов уже дают нулевой элемент: 1 1 1 1 1 (((1 1) (1 1)) 1) ((2 2) 1) (4 1) 0.

«предыдущих» итераций. В качестве «начальных» условий для алгоритма принимаются: r(0) p и r(1) a. В расширенном алгоритме Евклида на каждой итерации частное q(s)

результаты предпоследней итерации: НОД(a, p) r(n 1) , g g(n 1) и h h(n 1) .

Отметим, что поскольку в нашем случае цель – поиск обратного элемента по умножению в простом поле GF(p), то вычисление числа h нам фактически не требуется, для получения обратного элемента по умножению достаточно вычислить число g .

Рассмотрим пример вычисления обратного элемента по умножению в простом поле GF(p) при помощи вышеописанного алгоритма.

Пример. Вычислим в простом поле GF(97) обратный элемент по умножению для элемента a 10. Сначала применим расширенный алгоритм Евклида для чисел a 10 и

алгоритма на этом завершается, а в качестве результатов принимаются результаты вычислений на предпоследней итерации: НОД(a, p) r(4) 1 и g g(4) 29.

Поскольку в результате работы расширенного алгоритма Евклида мы получили отрицательное число g 29, то в качестве итогового результата, являющегося обратным

образом, мы убедились в том, что элемент b 68 является обратным элементом по умножению для элемента a 10 в простом поле GF(97).

Примечание. Следует отметить, что вышерассмотренный алгоритм также может применяться для поиска обратного элемента по умножению в коммутативном кольце с единицей, состоящем из множества целых неотрицательных чисел, являющихся остатками по модулю некоторого целого числа n > 1, не являющегося простым числом. Однако, в кольце по определению не для всякого ненулевого элемента существует обратный элемент по умножению, и для таких элементов наибольший общий делитель НОД(a,n) 1.