Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
49
ГЛАВА 1 ют за позиции соответственно ?^?^?^?T и ?4?5?6?7. получим
Ci = ?2 + ?-, + ?„ + ?; mod 2, (2.15a)
C2 = ?4 + ?5 + ?h + ?7 mod 2. (2.16a)
Обратим внимание, что систему (2.14а) н-(2.16а) можно рассматривать как развернутую запись матричного уравнения
Pi ?2 ?i
1 1 ?4 ?,
?a
?7
Co ] 0 I 0
= 0 1 1 0
0 0 0 1
или
Ve = A-Vat
где Ve - вектор ошибки, указывающий на се месторасположение; А - основная матрица, столбцы которой суть двоичные записи чисел от одного до семи.
Операция сложения во всех трех уравнениях (2.14а) ¦+• (2.16а) осуществляется по модулю два. Подставляя в систему уравнении (2.14а) -a- (2.16а) C11 = C1 = с2 = 0, получим систему из трех уравнений
?,+?3 + ?5 + ?7 = 0 mod 2, (2.146)
?2 + ?3 + ?6 + ?7 = 0 mod 2, (2.156)
?4 + ?5 + ?6 + ?7 = 0 mod 2, (2.166)
Приняв в качестве неизвестных величины ?5, ?6 и ?7, получим систему из грех уравнений с тремя неизвестными:
?5 + ?7 = ?, + ?3 mod 2, (2. 14b)
?6 + ?7 = ?2 + ?, mod 2, (2.15b)
?5 + ?6 + ?7 = ?j mod 2. (2.16b)
50 Эта система эквивалент на одному матричному уравнению
Pi Р:
Рз
Рд
1 0 1 P5 10 10
0 I 1 Рб = 0 110
1 1 1 Pt 0 0 (! 1
(2.17)
или
CI1=ZV,. (2 17а)
где Г( и I', векторы-столбцы, координаты которых представлены соответственно контрольными и информационными разрядами; Cnl- гак называемые контрольная и информационная матрицы. Столбцы эт их матриц суть двоичные записи номеров соответственно контрольных и информационных разрядов.
Решение системы (2.14в) (2.16в), или. что то же самое, матричного уравнения (2.17) относительно ?s. п ?7 приводит к конкретным выражениям для функций (2.11) (2.13):
?, = ?2 + ?, + ?4 mod 2, (2.11a)
?6 = ?; + ?, + ?4 mod 2, (2.12a)
?7 = ?,+ ?2 + ?4 mod 2. (2.13a)
Заметим, что сам Р. Хэмминг в качестве контрольного берет не набор символов ?,„+j, ?m+2, ••¦, ?„,+v, а набор символов, индексы которых представляют целые степени двойки. В случае, когда число контрольных символов равно трем, эти индексы равны 2" =1.21 = 2 и 22 = 4, т.е. речь идет о наборе символов ?i?2?4, относительно которых решение системы (2.146) н- (2.166) чрезвычайно упрощает ся: ?, = ?3 + ?; + ?7 mod 2, ?2= ?, + ?ft + ?7 mod 2,
?4=?5 + ?, + ?7 mod 2.
Это и естественно, поскольку в данном случае вместо (2.17) имеем дело с матричным уравнением
Р.Я
Ps
Рб P7
где контрольная матрица С всегда равна единичной матрице.
1 0 0 P1 I 1 0
0 I 0 P2 = 1 0 1
0 0 1 Рд 0 1 1
51
ГЛАВА 1 Отметив, что при указанной рекомендации Р. Хэмминга контрольная матрица всегда (независимо от т ил) оказывается равной единице, подробное обсуждение этой рекомендации оставим на потом, продолжая рассматривать в качестве контрольных ?5?6?7, а качестве информационных- ?i?2?3?4-
Рассмотрим, к примеру, набор информационных символов ?[ ?2?3?^ = = 10 1 1. С помощью зависимостей (2.11а) ¦*¦ (2.13а) определим набор контрольных (дополнительно введенных, избыточных) символов ?5?6?7 = 010. Пусть ошибка произошла на уровне символа ?5, т.е. вместо истинного расширенного кодового набора 10 1 1 (0) 1 0 получен код 1 0 1 1 (1) 1 0. Тогда с помощью зависимостей (2.14а) + (2.16а) найдем
е(1=1 + 1 + 1+0=1 mod 2
е: = 0+1 + 1+ 0 = 0 mod 2 е2=1 + 1 + 1+0=1 mod 2
Набор значений е2е\вй =10 1 является двоичной записью числа "пять", т.е. указывает именно на пятую позицию (на символ ?5), где, собственно, и произошла ошибка.
Приведенная схема Р. Хэмминга по конструированию кода, обнаруживающего и исправляющего одиночную ошибку, универсальна, и аналогичный код может быть построен для произвольной пары значений т и X, удовлетворяющих уравнению
!"-х-I= т. (2.106)
Заметим также, что вовсе не обязательно, чтобы набор из т информационных символов представлял собой код какой-то определенной буквы, как это имело место в только что рассмотренном примере. На практике сначала можно осуществить оптимальное (или близкое к оптимальному) кодирование текста. Затем уже закодированный текст можно делить на блоки по т двоичных символов в каждом, причем из возможных значений т = 2х -х - 1 (х = 3, 4, ...) его конкретное значение следует выбирать исходя из эксплуатационной необходимости. При прочих равных условиях значение т должно быть тем меньшим, чем больше значимость информации и чем больше уровень помех. После выбора конкретного значения т каждый блок из т информационных символов следует наращивать л- = х (т) контрольными символами, предназначенными для обнаружения и исправления одиночных ошибок в рамках данного блока.
А теперь вернемся к рассмотрению вопроса о том, почему Р. Хэм-минг в качестве контрольных берет именно символы, индексы которых
равны целым степеням двойки, т.е. 1, 2, 4, 8, 16..... Во-первых, как
уже об этом говорилось выше, при таком выборе контрольная матрица всегда оказывается равной единице, т.е. фактически снимается вопрос
52 решения системы (2.146) + (2.166) относительно контрольных символов, так как ее "решение" сводится к простому переписыванию соответствующих уравнений. Но это не главное, так как систему (2.146) -г- (2.166) приходится решать только один раз и далее при каждом акте кодирования мы пользуемся лишь системой (2.1 la) + (2.13а) - решением системы (2.146) н-(2.166) относительно контрольных символов. При реализации процедур кодирования и декодирования на ЭВМ сам факт, что контрольные символы разобщены (не следуют подряд друг за другом), создает определенные неудобства при каждом акте кодирования и декодирования. Естественно поэтому желание выбрать контрольные символы таковыми, чтобы они следовали подряд друг за другом, пусть даже ценою того, чтобы один раз решить систему (2.146) (2.166). Именно так поступали мы, когда вопреки рекомендации Р. Хэмминга взять в качестве контрольных символы ?,, ?2 ¦ и ?4 взяли в качестве таковых символы ?5, ?6 и ?7. Хотя это и вынудило нас решить систему (2.14в) + (2.16в) относительно переменных ?5, ?6 и ?7, но зато при каждом акте кодирования и декодирования мы смогли оперировать "пачками" контрольных символов, а не "выковыривать" их среди информационных символов.
