Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 16

...............................

Проверочная матрица кода должна иметь  n столбцов и p строк.Каждый столбец должен составлять двоичную комбинацию,указывающую номер соответствующей позиции кода.

НАПРИМЕР,для кода длиной n = 9,обеспечивающего исправление однократных ошибок,количество избыточных символов p = 4.При этом в качестве проверочной матрицы может быть выбрана следующая матрица:

│0 0 0 0 0 0 0 1 1│

│0 0 0 1 1 1 1 0 0│

H = │0 1 1 0 0 1 1 0 0│

│1 0 1 0 1 0 1 0 1│

Представим в качестве примера простую двоичную комбинацию 10011 кодом Хэмминга.Так как проверочные символы должны занимать 1-ю,2-ю,4-ю и 8-ю позиции,то информационные - 3-ю,5-ю,6-ю,7-ю и 9-ю позиции.Тогда a3 = 1, a5 = 0, a6 = 0, a7 = 1, a9 = 1.Из условия обеспечения чётности сумм b1,...,b4 получим следующие значения проверочных символов: a1 = 1; a2 = 0; a4 = 1; a8 = 1.Следовательно,простому пятиэлементному коду 10011 соответствует девятиэлементный код Хэмминга

101100111.

Пусть теперь при передаче поизошло искажение пятого символа,т.е.

код принял вид 101110111.Тогда b1 = 1, b2 = 0, b3 = 1, b4 = 0.Таким образом в результате проверки получаем синдром 0101,указывающий на искажение пятого символа.Исправление ошибки сводится к инвертированию символа на пятой позиции.Так как номер искажённого символа в двоичной записи совпадает со значением синдрома,в декодере для исправления ошибки удобно использовать стандартный дешифратор.

КОД ХЭММИНГА С ИСПРАВЛЕНИЕМ ОДИНОЧНОЙ

И ОБНАРУЖЕНИЕМ ДВУКРАТНОЙ ОШИБОК.

Код Хэмминга с кодовым расстоянием d min = 4 получается путём добавления к коду Хэмминга с d min = 3 проверочного символа,представляющего собой результат суммирования по модулю два всех символов кодовой комбинации.Проверочная матрица для кода с n = 9 может иметь вид:

│0 0 0 0 0 0 0 1 1 0│

│0 0 0 1 1 1 1 0 0 0│

H = │0 1 1 0 0 1 1 0 0 0│.

│1 0 1 0 1 0 1 0 1 0│

│1 1 1 1 1 1 1 1 1 1│

Дополнительное проверочное соотношение,вводимое для увеличения минимального расстояния кода Хэмминга,имеет вид:

b5 = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10.

Операция декодирования состоит из двух этапов.На первом определяется синдром,соответствующий коду с d min = 3,на втором - проверяется последнее проверочное соотношение.

Тогда в случае одной ошибки синдром укажет номер ошибочной позиции, а проверка на чётность - на наличие ошибки (нечётной).Если синдром указывает на наличие ошибки,а проверка на чётность не фиксирует её, значит в кодовой комбинации две ошибки (исправление - невозможно).

/* Разрядность ЗУ,как правило,кратна байту.Поэтому при использовании в ЗУ корректирующих кодов приходится решать задачу получения укороченных кодов с заданным минимальным кодовым расстоянием d = 4,

H - матрицы для неукороченного кода с наименьшим значением p,удовлетворяющим 2^(p-1) - p = > k,из которой удаляются лишние столбцы.

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

Избыточность кода Хэмминга Kизб = p/n зависит от количества информационных символов и при изменении k от 4 до 1013 изменяется от

0.429 до 0.098 при d min = 3 и от 0.5 до 0.0107 при d min = 4.

Ц И К Л И Ч Е С К И Е   К О Д Ы .

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

Название кодов произошло от их свойства,заключающегося в том,что каждая кодовая комбинация может быть получена путём ЦИКЛИЧЕСКОЙ ПЕРЕСТАНОВКИ СИМВОЛОВ комбинации,принадлежащей к этому же коду.Это значит,что если,например,комбинация a0 a1 a2 ... an-1 является разрешённой комбинацией циклического кода,то комбинация an-1 a0 a1 a2