Коды минимальных многочленов

Ппорядок многочлена i	Минимальные многочлены при величине степени m

Образующий многочлен с общим числом элементов n=2^m-1 и с числом исправляющий искажений S строится следующим образом. Из таблицы 4.11 выписываются все значения минимальных многочленов, соответствующих выбранному m до порядка 2S-1. Если в таблице такого числа нет, то выбирается минимальный нижний предел.

Например: цель - построить код БЧХ с общим числом элементов кодовой комбинации n=15, и исправляющим двойные искажения S=2.

1. Из формулы n=2^m-1 определяется m

2^m = n+1 по определению логарифма m=log₂(n+1)=log₂(15+1)=4.

Следовательно, общий вид образующего многочлена имеет вид:

P(x)=m₁(x) m₃(x)... m_2S-1(x)=m₁(x) m₃(x).

2. Из таблицы 9 столбца m=4 выбирают многочлены для i=1 и i=3, т.е. m₁=10011, m₃=11111 откуда: m₁=x⁴+x+1, m₃=x⁴+x³+x²+x+1

3. Определяют вид образующего многочлена

P(x) = m₁(x) · m₃(x) = 10011Ä1111 = 111010001 = x⁸+x⁷+x⁶+x⁴+1

4. Определяют число проверочных и информационных элементов кодовых комбинаций кодов БЧХ: число проверочных элементов r£m·S=4·2=8; число информационных элементов k=n-r=15-8=7.

5. Строят дополнительную матрицу G_8,7 производящей матрицы G_15,7. Дополнительная матрица G_8,7 образуется делением единицы на кодовую комбинацию образующего многочлена P(x)=111010001

100000000 ë 111010001

111010001

11010001 = R₁(x)

111010001

01110011 = R₂(x)

11100110 = R₃ (x)

111010001

00011101 = R₄(x)

00111010 = R₅(x)

01110100 = R₆(x)

11101000 = R₇(x)

6. Определяют производящую матрицу G_15,7

0000001 11010001

0000010 01110011

0000100 11100110

G_15,7 = 0001000 00011101

0010000 00111010

0100000 01110100

1000000 11101000

7. Строки производящей матрицы составляют подмножество множества кодовых комбинаций кодов БЧХ, остальные кодовые комбинации кодов БЧХ определяют по матрице G_15,7 сложением по модулю 2 всех возможных строк производящей матрицы.

Общее число множества кодовых комбинаций кода БЧХ для рассмотренного случая определится как N=2^k=2⁷=128.

Например из 1-ой и 2-ой кодовых комбинаций производящей матрицы получают следующую кодовую комбинацию кодов БЧХ

0000001 11010001

Å

0000010 01110011

N₃= 0000011 10100010 и т.д.

Для примера целесообразно рассмотреть построение множества кодов БЧХ и для случая обнаружения и исправления тройных искажений в кодовых комбинациях. Ставится задача - построить множество кодовых комбинаций кодов БЧХ с общим числом элементов n=15 и количестве исправляемых искажений равных 3 (S=3).

1. Определяем степень минимальных многочленов m для построения образующего многочлена P(x)

m = log₂(n+1) = log₂16 = 4.

Следовательно образующий многочлен будет иметь вид:

P(x) = m₁(x) m₃(x)... m_2S-1(x) = m₁(x) m₃(x) m₅(x)

2. Из таблицы 9 (столбец m=4) выбирают три минимальных многочлена с i=1,3,5 m₁(x)=10011=x⁴+x+1, m₃(x)=11111=x⁴+x³+x²+x+1,

m₅(x)=111=x²⁺x+1

3. Образующий многочлен для рассматриваемого примера определится как P(x)=m₁(x) m₃(x) m₅(x)=10011 · 11111 ·111=10100110111 ®x¹⁰+x⁸+x⁵+x⁴+x²+x+1.

4. Число проверочных элементов кодовых комбинаций r определится следующим образом r£m· S=4·3=12, но так как степень образующего многочлена P(x) равна 10, то r выбирается равным 10, r=10.

5. Число информационных элементов кода БЧХ определится как k=n-r (k=15-10=5).

6. По образующему многочлену P(x) строится дополнительная матрица G_10,5 производящей матрицы G_15,5. Строки дополнительной матрицы G_10,5 определяются в результате получения остатков от деления 1 с приписанными справа нулями на образующий многочлен P(X)=10100110111, таких остатков должно образоваться 5, т.к. число кодовых комбинаций остатка равно числу проверочных элементов r (r=10).

7. По дополнительной матрице G_10,5 строится производящая матрица G_15,5. Число строк такой матрицы также равно 5 (т.е. количеству информационных элементов k=5).

8. По образующей матрице путем суммирования ее строк определяются остальные кодовые комбинации множества кодов БЧХ, состоящих из 15 элементов и исправляющих тройные искажения.

Процесс построения дополнительной и производящей матриц, как и процесс формирования множества кодов БЧХ описан в предыдущем примере.

Для обнаружения и исправления искажений в кодовых комбинациях БЧХ алгоритм функционирования синдрома приемного устройства аналогичен алгоритму обнаружения и исправления искажений в простейших циклических кодах с минимальным кодовым расстоянием d_min³2S+1.

Алгоритм обработки и исправления искажений кодовой комбинации кодов БЧХ целесообразно рассмотреть на конкретном примере.

Пример. Цель - произвести исправление двойного искажения (S=2) в принятой кодовой комбинации кода БЧХ с общим числом элементов n=15 и числом информационных элементов k=7.

Для примера построим кодовую комбинацию множества кодов БЧХ на основании производящей матрицы G_15,7. рассмотренной несколько выше. Сложением по модулю 2 трех строк производящей матрицы G_15,7 образуется следующая кодовая комбинация кода БЧХ

Å 010000001110100

100000011101000

Предположим, что при передаче кодовой комбинации кодов БЧХ N_i(1,0) = 11100001010 01 10 произошло двойное искажение в двух соседних элементах (3 и 4 элементы младших разрядов). Принятая кодовая комбинация будет иметь вид N_i(1,0) =11100001010 10 10.

Для исправления искажений в принятой кодовой комбинации необходимо принятую комбинацию разделить на образующий многочлен P(x)=P(1,0)=111010001. Образующий многочлен взят из приведенного примера, где и описано его построение.

11100010101010 ë 111010001

111010001

111010001

111010001

1100 остаток p = S = 2,

т.е. вес остатка равен числу исправляемых искажений. Напоминаем, что для нахождения искаженных элементов кодовых комбинаций кодов БЧХ и их исправлений необходимо выполнение условия, чтобы вес остатка (количество единиц в остатке) был меньше или равен числу исправляемых искажений, т.е. p£S. После чего принятая комбинация суммируется с полученным остатком по модулю 2. Полученная сумма и даст исправленную кодовую комбинацию. Если p>S, то производится циклический сдвиг принятой комбинации на один разряд влево, и вновь образованная кодовая комбинация делится на образующий многочлен. Эта операция повторяется до тех пор, пока не будет выполняться условие p£S. Затем производится последовательно сдвиг последней кодовой комбинации вправо на столько разрядов, на сколько была сдвинута влево искаженная кодовая комбинация. В результате циклического сдвига образуется исправленная кодовая комбинация.

Итак, в рассмотренном примере вес остатка равен числу исправляемых искажений (p=S=2), что удовлетворяет условию p£S. Производя суммирование по модулю 2 принятой искаженной кодовой комбинации с полученным остатком, производится исправление искажений

Å

1100

111000010100110 исправленная комбинация.

Для получения полной картины исправления искажений необходимо рассмотреть несколько вариантов.

Допустим, что искажены не соседние разряды кодовой комбинации кодов БЧХ, а первый и шестой, т.е. принятая кодовая комбинация будет иметь вид 111000010 0 0011 1.

111000010000111 ë111010001

111010001

111010001

111010001

100001 остаток p=2.

Условие p £ S выполняется, производится суммирование остатка с принятой кодовой комбинацией

Å 100001

111000010 1 0011 0 исправленная комбинация.

При искажении пятого и тринадцатого элементов принятой комбинации алгоритм исправления определится как принятая искаженная комбинация 11 0 0000101 1 0110

110000010110110 ë111010001

111010001

111010001

111010001

111010001

101010 остаток p=3 >S

Производится сдвиг принятой кодовой комбинации (искаженной) 110000010110110 на один разряд влево, получаем 100000101101101. Производим деление вновь образованной кодовой комбинации на образующий многочлен.

100000101101101 ë111010001

111010001

111010001

111010001

111010001

1010100 остаток p=3>S.

Повторяем операцию сдвига еще раз 000001011011011

000001011011011 ë111010001

111010001

111010001

10101000 остаток p=3>S.

Т.к. p>S кодовая комбинация 000001011011011 сдвигается еще на один разряд влево, получают 000010110110110.

000010110110110 ë111010001

111010001

111010001

111010001

10000001 остаток p=2=S.

Условие p£S выполняется, т.к. S=2.

Производится сложение по модулю 2 сдвинутой на 3 разряда влево принятой искаженной кодовой комбинации 000010110110110 с последним остатком 10000001.

Å 10000001

Производим трехкратный сдвиг вправо результата суммирования 000010100110111. В результате такого сдвига получают исправленную кодовую комбинацию, переданную с передающего комплекта системы передачи данных, функционирующей в кодовом множестве БЧХ.

000010100110111 ® 100001010011011 ® 110000101001101 ® ®111000010100110 (исправленная кодовая комбинация)

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

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

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

Однако, прежде чем перейти к вопросам защиты информации от несанкционированного доступа, необходимо рассмотреть методы формирования исходных кодовых комбинаций, применяемых в современных вычислительных системах. Примером такого исходного кодирования является преобразование семантического алфавита в операционных оболочках Windows, определяемые как кодирование по стандарту CP-1251 или Windows-кодирование. Эта система кодирования не содержит символы псевдографики и получила в настоящее время наибольшее распространение как в локальных, так распределенных и глобальных системах типа Internet. При применении указанной системы кодирования семантического алфавита, каждый символ алфавита кодируется 8-битовой двоичной комбинацией. Однако, применение системы 8-битового кодирования имеет существенный недостаток, т.к. не обеспечивает кодирование символов алфавитов азиатских стран.

В настоящее время для обмена информацией на языках всех стран мира создается универсальная система кодирования UNICODE. В ее основе заложено 16-битовое кодирование. Т.е. каждый символ естественного алфавита, на каком бы языке стран мира он не отображался, представляет собой 16-разрядную кодовую комбинацию. В этом случае общее число кодовых комбинаций составит N=2ⁿ=2¹⁶=65536. Такое количество кодовых комбинаций позволяет кодировать даже полные наборы иероглифов всех восточных и арабских языков, а также все математические и химические символы. Такие системы кодирования не требует включения в набор сервисных программ-программ перекодирования естественных символов с одного стандарта на другой.