ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 28.03.2025
Просмотров: 146
Скачиваний: 1
Среди элементов поля GF(pm) можно выбрать такой элемент α, что ,возводя его последовательно в степень, получают все элементы поля (кроме нулевого). Таких элементов может быть несколько. Они определяются методом перебора. Элемент α называют примитивным.
Неприводимый многочлен не имеет корней в поле GF(p), но имеет корни в расширении поля. Если неприводимый многочлен имеет своим корнем примитивный элемент, то такой многочлен называется примитивным (или порождающим). Если многочленp(x) имеет корень β, то его корнями будут также β в степенях рі (і = 1,2 и т. д. доm- 1). Если р=2, то β, β2 ,β4 … . Таблицы всех неприводимых многочленов различных степеней приводятся в учебниках по кодированию. Примитивные многочлены среди них выделены.
Рассмотрим поле GF(24). Используя примитивный многочлен четвёртой степени g(x) =X4 +X+ 1 составим таблицу соответствия элементов поляGF(24) в виде степеней примитивного элемента, двоичным и десятичным эквивалентом элемента. Примитивный элемент α =(Х). (Из записи многочлена g(x) следует, что Х =2.) Поскольку многочлен примитивный, то g(α) =0; α * g(α) =0; α2 * g(α) = 0 и т.д. Откуда следует, что α4= α + 1; α5 = α2 + α; α6 = α3 + α2 и т.д. Учитывая это, начиная с α4, получим следующую таблицу.
Т а б л и ц а 1. Представление элементов поля в виде степени примитивного элемента и в двоичном коде.
α0 = 1 0001 1
α1= α 0010 2
α2 = α2 0100 4
α3 = α3 1000 8
α4 = α + 1 0011 3
α5 = α2 + α 0110 6
α6= α3 + α2 1100 12
α7= α3+ α +1 1011 11
α8= α2 + 1 0101 5
α9= α3 + α 1010 10
α10= α2 + α +1 0111 7
α11= α3 + α2 + α 1110 14
α12= α3 + α2 + α + 1 1111 15
α13= α3 + α2 +1 1101 13
α14= α3 +1 1001 9
α15= 1 0001 1
Здесь учтено, что, например, α7= α4+ α2 = α + 1 + α2= α2 + α + 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(24) заменяются степенным представлением примитивного элемента. В результате умножения показатели соответствующих степеней примитивного элемента складываются, приводятся по модулю 15. Затем в соответствии с полученной степенью примитивно элемента из таблицы находят соответствующее значение десятичного представления элемента поля. Например, 4*8 = α2 + α3 = α5 =6; 5*10 = α8 * α9 = α17 = α2 = 4.
Построение кода Рида - Соломона
Задана длина кода n= 15. Число информационных символовk= 9. Находим минимальное кодовое расстояниеdмин =n–k+ 1= 15 – 9 +1=7. Находим степень порождающего многочлена равнуюdмин – 1 =7 – 1= 6. Порождающий многочлен в соответствии с теоремой Безу записывается в видеg(х) = (х – α)∙(х- α2)∙(х – α3)∙(х – α3)∙(х – α4)∙(х – α5)∙(х – α6) = (х+2)∙(х+4)∙(х+8)∙(х+3)∙(х+6)∙(х+12) =х6 + 7х5 +9х4 +3х3 +12х2 +10х + 12.
Здесь использована арифметика полей Галуа и приведённая выше таблица. Примитивный элемент α=2.
Пусть сообщение имеет вид 7,5,10,0,9,1,1,1,9, что соответствует многочлену
P(х) = 9х8+ х7+х6+х5+9х4+0х3+10х2+5х +7.
Умножим этот многочлен на х6, чтобы справа оказалось 6 нулей, вместо которых затем припишем остаток от его деления наg(х) . После умножения получим
P1(х)= 9х14+ х13+х12+х11+9х10+0х9+10х8+5х7+7х6.
Слагаемое в многочленах с нулевым коэффициентом пропускают (здесь оно оставлено для наглядности и его можно было не записывать). После деления многочлена P1(х) наg(х) получаем остатокr(х) =13х5+ 6х4+ 14х3+15х2+15х +3. Прибавляя его кP1(х) получим многочленG(х) кодовой комбинации кода Рида – Соломона.
G(х)= 9х14+х13+х12+х11+9х10+10х8+5х7+7х6+13х5+6х4+14х3+15х2+15х +3.
Многочлен комбинации кода делится на образующий многочлен g(х) без остатка.
Задание
А) Закодировать кодом Рида-Соломона кодовую комбинацию 9, п1,п2 ,10,0,9,1,1,1,9. Здесь п1,п2 цифры номера М студента в журнале группы. Номер М привести на титульном листе задания.
Б)Проверить правильность кодирования делением полученной кодовой комбинации на g(х).
В) Привести запись полученной кодовой комбинации в двоичном коде (для этого необходимо соответствующие коэффициенты многочлена кодовой комбинации записать четырёхразрядным двоичным кодом.
Привести подробное выполнение пунктов А) и Б) задания.
Защита задания будет заключаться в объяснении выполнения процесса умножения и деления многочленов в арифметике поля Галуа