A1 = 000; A8 = 111.
Пусть теперь необходимо построить КОД,ОБЕСПЕЧИВАЮЩИЙ УСТРАНЕНИЕ
ОДНОКРАТНЫХ ОШИБОК.Выбираем в качестве первой разрешённой комбинации A1 = 000.При наличии одиночных ошибок комбинация A1 может перейти в A2 = 001,A3 = 010 или A5 = 100.Комбинации A2,A3 и A5 должны быть запрешёнными.Тогда в случае приёма одной из них выносится решение,что передана комбинация A1.
Пусть в качестве второй разрешённой комбинации выбирается комбинация,отстоящая от первой на расстоянии d = 2,например,A4 = 011.Ей соответствует подмножество запрещённых комбинаций A3 = 010,A2 = 001
и A8 = 111.Однако получилось пересечение подмножеств для A4 и A1.
При приёме A2 или A3 нельзя однозначно установить,передана комбинация A1 или A4.
Если же в качестве второй разрешённой комбинации выбрать комбинацию,отстоящую от A1 на d = 3,т.е.комбинацию A8 = 111,которой соответствует подмножество запрещённых комбинаций A4 = 011,A6 = 101 и
A7 = 110,то в этом случае подмножества запрещённых комбинаций не пересекаются.Следовательно,при d = 3 обеспечивается устранение всех одиночных ошибок.
В ОБЩЕМ СЛУЧАЕ ДЛЯ УСТРАНЕНИЯ ОШИБОК кратности S кодовое расстояние должно удовлетворять условию
d min = > t + S + 1
Аналогично рассуждая,можно установить,что для ИСПРАВЛЕНИЯ всех ошибок кратности не более S и одновременно ОБНАРУЖЕНИЯ всех ошибок кратности не более t и при t = > S кодовое расстояние должно удовлетворять условию
d min = > t + S + 1 .
ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА КОРРЕКТИРУЮЩИХ СИМВОЛОВ .
При построении реальных кодов перед разработчиками стоит задача опредпления числа добавочных,корректирующих символов p = n - k,исходя из числа информационнных разрядов k,либо из общей длины кода n.
Для обнаружения и исправления одиночой ошибки соотношение между числом информационнх разрядов k и числом корректирующих разрядов p
должно удовлетворять следующим условиям
2^p = > n + 1
2^k = > 2^n/( n + 1 ).
При этом подразумевается,что общая длина кодовой комбинации
n = k + p .
Для ПРАКТИЧЕСКИХ РАСЧЁТОВ при определении p для кодов с минимальным кодовым расстоянием d = 3 удобно пользоваться выражениями,где цифра в индексе - число исправляемых ошибок,в скобках - обнаруживаемых:
p1(2) = [log 2 (n + 1)], если известна длина полной кодовой последовательности n,и
p1(2) = [log 2 {(k + 1) + [log 2 (k + 1)]}], если задано число информационных символов k (квадратные скобки означают округление).
Для кодов,ОБНАРУЖИВАЮЩИХ ВСЕ ТРЁХКРАТНЫЕ ОШИБКИ (d min = 4),
p1(3) = >1 + log 2(n + 1), или
p1(3) = >1 + log 2[(k + 1) + log 2(k + 1)],
Для кодов длиной в n символов,исправляющих одну или две ошибки
( d min = 5),
2 1
p2 = >log 2 ( C n + C n + 1 ) .
Для практических расчётов можно поьзоваться выражением
p2 = [ log 2 (n^2 + n + 1) / 2 ].
Для кодов,ИСПРАВЛЯЮЩИХ ТРИ ОШИБКИ (d min = 7),
p3 = [ log 2 (n^3 + n^2 + n + 1) / 6 ].
Для кодов,ИСПРАВЛЯЮЩИХ S ОШИБОК (d min = 2S + 1),
s s-1 2s-1 2s-2
log 2 (Cn + Cn + ... + 1) < p2 < log 2 (Cn-1 + Cn-1 + ... + 1)
Выражение слева известно как нижняя граница Хэмминга,а выражение справа - как верхняя граница Варшамова - Гильберта.
Для приближённых расчётов можно пользоваться выражением:
ps = [(log 2 n^s + n^s-1 + ... + 1) / S!].
К О Д Ы С О Б Н А Р У Ж Е Н И Е М О Ш И Б О К .
К О Д С Ч Ё Т Н Ы М Ч И С Л О М Е Д И Н И Ц .
Код содержит лишь один избыточный символ.Выбирается избыточный символ таким образом,чтобы общее количество единиц в кодовой комбинации было чётным.Проверка кодовой комбинации производится путём суммирования по модулю два всех его символов.
Избыточность кода равна Kизб = p/n = 1/n.
Код позволяет обнаруживать все ошибки нечётной кратности.
К О Д С У Д В О Е Н И Е М Э Л Е М Е Н Т О В .
Этот код характеризуется введением дополнительных символов для каждого символа информационной части комбинации,причём единица дополняется нулём и преобразуется в 10,а нуль дополняется единицей и преобразуется в 01.Например,комбинация 101 будет представлена в виде
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.