...............................
Проверочная матрица кода должна иметь 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
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.