Коды Рида-Соломона – ЧАСТЬ 1

В системах передачи и хранения информации широкое применение нахо­дят коды Рида-Соломона, представляющие важный частный случай извест­ных кодов БЧХ. Эти недвоичные линейные циклические коды были предло­жены в 1960 г. сотрудниками Массачуссетского технологического института

Ирвином Ридом (Irving Reed) и Густавом Соломоном (Gustave Solomon) в ста­тье «Polynomial Codes over Certain Finite Fields» (опубликована в Journal of the Society for Industrial and Applied Mathematics).

Популярность PC-кодов обусловлена их замечательными корректирующими свойствами и наличием достаточно простых алгоритмов декодирования. Так, код РС(«, к) с минимальным кодовым расстоянием d=n-k+1 обладает способностью исправлять до t=(n~k)/2 ошибок включительно [3,22]. Таким образом, коды PC являются (см. п.2.3.1) кодами с максимально-возможным кодовым расстоянием. Поскольку коды Рида-Соломона относятся к классу циклических, их кодирование и декодирование являются вычислительными процедурами, интерпретируемыми в виде операций над полиномами. Такие операции обеспечивают относительно простую схемотехническую реализацию (символы кодов PC представимы в виде элементов числовых множеств, обладающих свойствами конечных полей Галуа, где полиномиальные операции оказываются наименее ресурсоемкими).

Символами кода Рида-Соломона являются недвоичные числа, которые при передаче или записи заменяются соответствующими двоичными комбинация­ми, содержащими по т бит каждая. Слово кода РС(и, к) состоит из п символов, к из которых – информационные, 0<к<п<2т+2.

2.3.2.1. Некоторые сведения из теории полей Галуа. Арифметика полей Галуа, используемая при построении и декодировании кодов Рида-Соломона вза­мен правил традиционной арифметики, обеспечивает существенный выигрыш в объеме вычислений, необходимых при выполнении названных процедур!

Напомним, полем называется множество элементов, в котором определены две операции – сложение и умножение, обе ассоциативные, коммутативные, свя­занные законом дистрибутивности, причем для каждого элемента существует обратный (противоположный) элемент по сложению, и для каждого ненулевого элемента – обратный по умножению. Противоположным для данного элемента является элемент, который при сложении с ним дает нуль; элемент, обратный по умножению – тот, который при перемножении с данным дает единицу. Если поле содержит конечное число элементов, оно называется конечным полем (или полем Галуа) и обозначается G¥(q), где q – число элементов поля. Поле GF(p), где р – простое число, называется простым (напомним, что число называется простым, если оно делится только на 1 и само на себя). Проще говоря, поле состоит из мно­жества элементов {0,1,2,...,р-1}, над которым операции сложения и умножения выполняются по модулю р. Это означает, что взамен получаемого в результате вы­полнения операции результата следует взять остаток от его деления на число/?.

В качестве примера рассмотрим поле GF(3)={0, 1,2}. Операции сложения и умножение в этом поле задаются следующим образом.

Для выделенных пунктиром элементов таблицы сложения имеем: во еторой строке третьего столбца 1+2=3; 3-3=0, т.е. 1+2=0 (mod 3); в третьей строке вто­рого столбца 2+1=3; 3-3=0, т.е. 2+1=0 (mod 3). Отсюда видно, что в поле GF(3) противоположным элементом для 1 является 2, а противоположным для 2 яв­ляется 1. Для выделенного пунктиром элемента таблицы умножения в третьей строке третьего столбца: 2-2=4; 4-3=1, т.е. 2-2=1 (mod 3). Отсюда ясно, что в поле GF(3) обратным элементом для 2 является 2.

Кроме простых полей GF(p), существуют поля Галуа GF(pw), где р – про­стое число, а т~ натуральное. Такое поле получают путем расширения простого поля GF(p) за счет корней многочлена хр -х. Поскольку

Сложение в поле GF(8)

 

 

000

100

010

001

110

011

111

101

 

+

0

р°

Р1

Р2

Р3

Р4

Р5

Р6

ООО

0

0

р°

Р1

Р2

Р3

Р4

Р5

В6

100

Р°

р°

0

Р3

Р6

Р1

Р5

р4

Г р2

010

Р’

Р1

Р3

0

р4

р°

Р2

рб

Р5

001

Р2

Р2

Р6

р4

0

р5

Р1

Р3

р°

110

Р3

р3

Р1

р°

Р5

0

Р6

Р2

Р4

011

Р4

Р4

Р5

Р2

р1

Р6

0

р°

4— г р3

111

Р5

Р5

Р4

р6

р3

Р2

р°

0

Р1

101

Р6

р6

Р2

Р5

р°

Р4

Р3

Р’

0

Примечание: Р – корень примитивного неприводимого многочлена х3+х+1.

Таблица 2. /

Умножение в поле GF(8)

 

 

000

100

010

001

110

011

111

101

 

X

0

Р°

Р1

Р2

Р3

Р4

Р5

Рб

000

0

0

0

0

0

0

0

0

0

100

р°

0

Р°

р1

р2

Р3

р4

Р5

Рб

010

Р1

0

Р1

Р2

Р3

р4

р5

Р6

р°

001

р2

0

Р2

Р3

р4

Р5

р6

р°

Р1

110

р3

0

Р3

Р4

р5

Р6

р°

Р1

Р2

011

Р4

0

Р4

р5

р6

р°

Р1

Р2

Р3

111

р5

0

Р5

Р6

р°

Р1

р2

Р3

Р4

101

Р6

0

Р6

р°

Р1

Р2

Р3

р4

Р5

щ

тмечани

е- Р – корень примитивного неприводимого многочлена х3+х+1.

Многочлен х3 + х2 +1 также является примитивным, в чем легко убедиться Действительно, если а – корень многочлена х3 + х +1, то а + а +1 = 0. Кро ме того, а7=1, поскольку а, являясь корнем многочлена х + х +1, также явля ется корнем х7+1. Поскольку а3 = а2 +1, то а4 = а3 + а = а2 + а +1; ^

а5422+а + 1 + а2=а + 1иа653=а + 1 + а +1 = а +а.

Таким образом, а – примитивный корень х7+1 (по отношению к примитив­ному корню р из предыдущего примера а=Р3). Используя в качестве порождаю­щего многочлена полином х3 + х2 +1, тоже можно построить поле Галуа GF(8) Однако таблица изоморфизма поля Галуа (см. табл. 2.5), соответствия межд} двоичными векторами и элементами поля, а также таблицы истинности^ арифметических операций (см. табл. 2.6, табл. 2.7) в этом случае будут заметно отличаться.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100