Спирина, М.С. Дискретная математика

бинаций А и В вес третьей кодовой комбинации, полученной при сложении исходных по модулю два. 01001101 + В нашем примере С = А © В = 10101000, так как _010ШШ 10101000 Тогда К(С) = d(A, В) = £ С ; = 3. /=1 В теории кодирования известно, что систематический код обна­ руживает ошибки, когда минимальное кодовое расстояние dmm=It, где t — кратность обнаруженных ошибок. Так, при единичных ошибках / = 1 . Для кодов, корректирующих независимые ошибки, необходимо учитывать расстояние Хемминга, которое определяет корректиру­ ющие возможности кода по отношению к независимым ошибкам. Пусть код содержит t информационных разрядов и s контрольных разрядов. После проведения s проверок обнаруженной ошибке поставим в соответствие число 1 , а отсутствию ошибки — число 0 . При этом полученный кортеж двоичных символов является кон­ трольным числом, указывающим номер позиции, где произошла ошибка. Поэтому кортежу из одних нулей соответствует безоши­ бочная передача сообщения. Итак, число (г + s + 1) соответствует всем возможным событиям, поэтому для того, чтобы код обнару­ жил все комбинации из t ошибок, необходимо и достаточно, что­ бы кодовое расстояние было (t + s + 1 ). Код Хемминга обозначают (п, к), где п — длина кодового сло­ ва; к — число информационных позиций. Итак, любое слово можно записать в виде кортежа из 0 и 1. Так как в русском языке 33 буквы, а нам необходимо закодировать все, то для кодирования понадобится 2 5 = 32 разряда. Поскольку 32 < 33, примем за один символ пары Е и Ё и И и Й. Тогда, имея в запасе пробел, сможем записать в виде кортежей 0 и 1 не только слова, но и предложения. В двоичных словах помехой является замена 0 на 1 или 1 на 0, т.е. инверсия (отрицание). Учитывая тождество 1 Ф х,- = xh видим, что математически помеха описывается сложением (в смысле опе­ рации М2) 1 с исходным сообщением. Отсюда видна важная роль суммы по модулю два. Обозначим передаваемый символ х, полу­ ченный символ — у. Тогда, рассматривая х ® у, получим: 0 © 0 = 0 —передавали 0 , получили 0 , ошибки нет; 0 © 1 = 1 —передавали 0 , получили 1 , ошибка есть; 1 Ф 0 = 1 —передавали 1 , получили 0 , ошибка есть; 1 © 1 = 0 —передавали 1 , получили 1 , ошибки нет. Таким образом, наличие ошибки в данной позиции означает получение 1 в результате суммы по модулю два исходного и полу­ 322