Файл: ТПИ Задания 14.doc

Задание 6 (Домашнее задание) Некоторые сведения из теории полей Галуа.

Коды Рида – Соломона строятся, используя арифметические операции в конечных полях, называемых полями Галуа ( GF(p))порядкаp. Числоpдолжно быть простым. Помимо таких полей используются полеGF(p^m), называемое расширением поляGF(p). Расширение поля используется для многочленного представления элементов поляGF(p^m). Многочленное представление это все многочлены степени меньшейm. Чтобы в результате арифметических действий над многочленами не получился многочлен степени выше, чемm-1 , результат приводят по модулю неприводимого многочлена степениm. То есть, за результат выполнения арифметических операций принимают остаток от деления результата на неприводимый многочлен. Многочлен называется неприводимым, если он не раскладывается на множители (на многочлены) степени меньшей, чемmс коэффициентами из поляGF(p).

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

Неприводимый многочлен не имеет корней в поле GF(p), но имеет корни в расширении поля. Если неприводимый многочлен имеет своим корнем примитивный элемент, то такой многочлен называется примитивным (или порождающим). Если многочленp(x) имеет корень β, то его корнями будут также β в степенях р^і (і = 1,2 и т. д. доm- 1). Если р=2, то β, β² ,β⁴ … . Таблицы всех неприводимых многочленов различных степеней приводятся в учебниках по кодированию. Примитивные многочлены среди них выделены.

Рассмотрим поле GF(2⁴). Используя примитивный многочлен четвёртой степени g(x) =X⁴ +X+ 1 составим таблицу соответствия элементов поляGF(2⁴) в виде степеней примитивного элемента, двоичным и десятичным эквивалентом элемента. Примитивный элемент α =(Х). (Из записи многочлена g(x) следует, что Х =2.) Поскольку многочлен примитивный, то g(α) =0; α * g(α) =0; α² * g(α) = 0 и т.д. Откуда следует, что α⁴= α + 1; α⁵ = α² + α; α⁶ = α³ + α² и т.д. Учитывая это, начиная с α⁴, получим следующую таблицу.

Т а б л и ц а 1. Представление элементов поля в виде степени примитивного элемента и в двоичном коде.

α⁰ = 1 0001 1

α¹= α 0010 2

α² = α² 0100 4

α³ = α³ 1000 8

α⁴ = α + 1 0011 3

α⁵ = α² + α 0110 6

α⁶= α³ + α² 1100 12

α⁷= α³+ α +1 1011 11

α⁸= α² + 1 0101 5

α⁹= α³ + α 1010 10

α¹⁰= α² + α +1 0111 7

α¹¹= α³ + α² + α 1110 14

α¹²= α³ + α² + α + 1 1111 15

α¹³= α³ + α² +1 1101 13

α¹⁴= α³ +1 1001 9

α¹⁵= 1 0001 1

Здесь учтено, что, например, α⁷= α⁴+ α² = α + 1 + α²= α² + α + 1.

В поле задаются две арифметические операции: сложение и умножение, выполняемые с приведением результата по модулю. Кроме того в поле для каждого его элемента имеется обратный элемент по сложению (-а) элемента поля (а) такой, что а +(-а)=0, и обратный элемент а^-1 по умножению такой, что а*а^-1 = 1. Существование этих элементов позволяет выполнять операции вычитания и деления. Например, а –в =а +(-в); а/в =а*(в^-1 ). В полеGF(2) имеются только два элемента «0» и «1». И обратными элементами является сам элемент, а операция вычитания заменяется операцией сложения по модулю 2.

Операция сложения выполняется как операция сложения по модулю 2 с двоичным представлением элемента. Например, 12 + 5 = 1100 + 0101 = 1001 = 9; 10 + 11 = 1010 + 1011= 0001 = 1. Операция умножения производиться с применением логарифмирования и антилогарифмирования. Операция логарифмирования заключается в том, что элементы поля GF(2⁴) заменяются степенным представлением примитивного элемента. В результате умножения показатели соответствующих степеней примитивного элемента складываются, приводятся по модулю 15. Затем в соответствии с полученной степенью примитивно элемента из таблицы находят соответствующее значение десятичного представления элемента поля. Например, 4*8 = α² + α³ = α⁵ =6; 5*10 = α⁸ * α⁹ = α¹⁷ = α² = 4.

Построение кода Рида - Соломона

Задана длина кода n= 15. Число информационных символовk= 9. Находим минимальное кодовое расстояниеdмин =n–k+ 1= 15 – 9 +1=7. Находим степень порождающего многочлена равнуюdмин – 1 =7 – 1= 6. Порождающий многочлен в соответствии с теоремой Безу записывается в видеg(х) = (х – α)∙(х- α²)∙(х – α³)∙(х – α³)∙(х – α⁴)∙(х – α⁵)∙(х – α⁶) = (х+2)∙(х+4)∙(х+8)∙(х+3)∙(х+6)∙(х+12) =х⁶ + 7х⁵ +9х⁴ +3х³ +12х² +10х + 12.

Здесь использована арифметика полей Галуа и приведённая выше таблица. Примитивный элемент α=2.

Пусть сообщение имеет вид 7,5,10,0,9,1,1,1,9, что соответствует многочлену

P(х) = 9х⁸+ х⁷+х⁶+х⁵+9х⁴+0х³+10х²+5х +7.

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

P1(х)= 9х¹⁴+ х¹³+х¹²+х¹¹+9х¹⁰+0х⁹+10х⁸+5х⁷+7х⁶.

Слагаемое в многочленах с нулевым коэффициентом пропускают (здесь оно оставлено для наглядности и его можно было не записывать). После деления многочлена P1(х) наg(х) получаем остатокr(х) =13х⁵+ 6х⁴+ 14х³+15х²+15х +3. Прибавляя его кP1(х) получим многочленG(х) кодовой комбинации кода Рида – Соломона.

G(х)= 9х¹⁴+х¹³+х¹²+х¹¹+9х¹⁰+10х⁸+5х⁷+7х⁶+13х⁵+6х⁴+14х³+15х²+15х +3.

Многочлен комбинации кода делится на образующий многочлен g(х) без остатка.

Задание

А) Закодировать кодом Рида-Соломона кодовую комбинацию 9, п1,п2 ,10,0,9,1,1,1,9. Здесь п1,п2 цифры номера М студента в журнале группы. Номер М привести на титульном листе задания.

Б)Проверить правильность кодирования делением полученной кодовой комбинации на g(х).

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

Привести подробное выполнение пунктов А) и Б) задания.

Защита задания будет заключаться в объяснении выполнения процесса умножения и деления многочленов в арифметике поля Галуа.

Задание 6. Коды, обнаруживающие ошибки

Введение. Число m возможных ошибок в кодовой комбинации длиной n равно числу сочетаний из n по m, обозначаемое как (n, m),

n ∙ (n – 1) ∙ …….∙( n – (n – 1))

(n, m) = -------------------------------------- .

m!

Рассматриваются следующие коды: код на одно сочетание; код с числом единиц кратным 3; код с проверкой на чётность; корреляционный код.

В коде на одно сочетание, называемого иногда как код с постоянным весом, в n разрядах содержится m «1».

В коде с числом единиц кратным трём к разрядам неизбыточного кода добавляются справа два разряда такие, чтобы в полученном коде число единиц было кратно трём.

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

В корреляционном коде к каждому разряду неизбыточного кода добавляется разряд с инверсным значением.

Задание.Закодировать 5 сообщений указанными ниже кодами. Указать, корректирующую способность кода. Для кодов п2,п3,п4 число разрядов неизбыточного кода равно п1+п2 +3.

1 Код на одно сочетание n = п2 + 5, m =п1+2.

2.Код с числом единиц кратным 3.

3. Код с проверкой на чётность.

4.Корреляционный код.

Контрольные вопросы

1. Какие ошибки позволяет корректировать заданный преподавателем код?

2. При передаче сообщения указанным преподавателем кода необходимо ли разделять буквы.

3. Чему равно минимальное кодовое расстояние указанного кода?

4. Какова избыточность указанного кода?

5. К неизбыточному коду добавим ещё один разряд с проверкой на нечётность. Сравнить его корректирующую способность с кодом с проверкой на чётность.

6. Является ли код Грэя корректирующим кодом?

7. Какова корректирующая способность кода с повторением комбинации?

8. Какова корректирующая способность кода с инверсным повторением комбинации?

9. Какова корректирующая способность кода с двухкратным повторением кодовой комбинации?

10. Сравнить помехоустойчивость корреляционного кода и кода с простым повторением разряда кода.

Задание 8

Групповые коды с dмин = 3,4

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

В этом задании рассматриваются коды G_7,4 иG_8,4 , соответственно сdмин = 3 иdмин = 4. В обеих кодах число информационных разрядов -4, а остальные разряды проверочные. Разряд кода обозначим буквой «а» с номером разряда. Для кодаG_7,4 один из вариантов образования проверочных разрядов выбирается из условий

а1 + а3 + а5 + а7 = Р1

а2 +а3 + а6 + а7 = Р2

а4 + а5 + а6 + а7 = Р3 .

Из условий Р1 = 0, Р2 = 0, Р3 = 0 получаем:

а1 = а3 + а5 + а7

а2 = а3 + а6 + а7

а4 = а5 + а6 + а7.

Таким образом, проверочными разрядами кода являются а1, а2, а4. А остальные разряды кода – информационные. Код записывается в виде порождающей матрицы, в которой на местах информационных разрядов записывается единичная транспонированная матрице в канонической форме, а о проверочные разряды определяются из соответствующих проверочных уравнений. Вид матрицы

а1 а2 а3 а4 а5 а6 а7

0 0 0 1 А1

0 1 0 0 А4

1 0 0 0 А8.

Здесь А1, А2, а4. А8 – номера кодовых комбинаций. Остальные получают их суммированием, например, А6 = А2 + А4. КодG_8,4 получают приписыванием к матрице кодаG_7,4 разряда а8, определяемого из проверочного уравнения Р4 = а1 + а2 + а3 + а4 + а5 + а6 + а7 +а8. Из условия Р4 = 0 находят а8.

Для кода G_7,4 на приёмной стороне находят трёхзначное число Р1Р2Р3, называемое опознавателем. Его десятичный эквивалент указывает номер искажённого разряда и для исправления ошибки значение разряда должно быть инвертировано. Так производится исправление одиночной ошибки. В кодеG_8,4 также возможно исправление одиночной ошибки, если нет двойной. Различные варианты одиночной и двойной ошибки определяют по значению опознавателя Р1Р2Р3Р4. Значение Р4 равно «1» только при наличии в кодовой комбинации одиночной ошибки.

Задание

1. Записать образующие матрицы кодов G_7,4 G_8,4, заполнив проверочные разряды.

2. В коде G_7,4 выбрать кодовую комбинацию с номером М. Если М > 15, то взять М – 15. Вычислить для неё опознаватель. Исказить один разряд кода и вновь вычислить опознаватель. Исправить ошибку.

3. Исказить в выбранной комбинации два разряда. Вычислить опознаватель. Обратить внимание как она будет декодирована.

4. Выполнить пункты 2 и3 для кода G_8,4 .