1. Основные определения теории кодирования. Кодовое слово. Длина кодовой комбинации. Системы счисления.

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

К основным характеристикам кодов относят элементы кодовых комбинаций и кодовое слово. Под кодовым словом понимают - множество упорядоченных элементов кодовой комбинации (кортеж) в цикле преобразования сообщений. Так, например, если обмен данными в каждом цикле (при передаче одного элемента естественного языка) осуществляется 8 битами, то кодовая комбинация, состоящая из конкретного множества единиц и нулей, и составляет кодовое слово. Число символов в кодовом слове называется длиной кодовой комбинации (длина кодового слова). Для отображения элементов кодовых комбинаций могут использоваться буквы, цифры, различные знаки и символы. Число различных значений m, которое может принимать каждый кодовый символ, называется основанием кода.

независимо от системы счисления с основанием m, кодовое слово k = (an-1, an-2, ... ,ao) длины n можно определить как

k = an-1 mn-1 + an-2  mn-2 + ... + a1  m1 + a0  m0 = i  mi

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

В компьютерных системах зачастую используется восьмеричная система счисления, когда для представления любого десятичного числа используют всего восемь десятичных элементов кода (0,1,2,3,4,5,6,7) и перевод из восьмеричной системы счисления в двоичную производится по правилу, каждый элемент восьмеричной цифры заменяется трехразрядным двоичным числом.

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

2. Алгоритм функционирования синдрома приемного устройства кодов Боуза-Чоудхури-Хоквингема.

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

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

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

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

001000000111010

 010000001110100

100000011101000

111000010100110

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

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

11100010101010 111010001

111010001

100111010

111010001

111010111

111010001

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

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

111000010101010



1100

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

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