Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
/1 і о 1 0 0 0\ н /о I 10 100) І001 1010 г \0 о 0 1 10 1/
Эта матрица получена способом, указанным в дополнении 9 к § 11. В том, что коды с проверочными матрицами H и Hi действительно эквивалентны, читатель может убедиться самостоятельно. '
,93 Пусть принято некоторое слово а0 oc1 а2 ос3 ос4 а5 осв, содержащее, быть может, ошибочные символы. Для каждого символа а,- будем в отдельности решать, верен он или нет, используя те соотношения, которыми этот символ связан с остальными. Начнем с символа ос0 и выпишем некоторые содержащие его проверки. Первой строке матрицы Hi отвечает проверочное соотношение а0+а1+а3=0, сумме первой, второй и третьей строк — соотношение сс0 + ос.,+ +Ct5=O, а сумме первой, второй и четвертой строк — соотношение а0+а2+ос6=0. Итак, имеем:
oc0 = g^oc31
ос0=ос4+а5, (1)
а0=ос2+ав.
Если ошибки при передаче отсутствовали, то в принятом слове будет выполняться каждое из соотношений (I)5 а правые их части дадут верное значение для ос0. Соотношения (1) для символа а0 выбраны с таким расчетом, что всякий другой символ входит в правую часть ровно одной проверки. Поэтому если лишь один из них ошибочен, то только в одном из соотношений (1) будет нарушено равенство. Учитывая это, можно предложить следующее правило для определения верного значения символа а0: если среди значений ocj+осз, а4+а5, а2+ае, а0 большинство составляют нули, то полагаем, что нуль и есть верное значение для oc0, если же большинство из них — единицы, то верным значением для а0 считаем единицу. Такое голосование гарантирует верное решение, если принятое слово содержит не более одной ошибки. Возможно и равенство голосов (например, в случае двойной ошибки), и в этом случае приходится довольствоваться ее обнаружением.
Аналогичные проверки могут быть составлены и для других символов. Например, для Oc1 имеем соотношения:
ai=oc2+oc4,
cc1 = cc^ocei
«i=a0+a3,
также обладающие тем свойством, что каждый символ входит в правую часть не более одного раза. Эти проверки получаются из системы (1) циклическим сдвигом на одну позицию. Последующие циклические сдвиги дают системы подобных проверок для остальных символов.
Анализируя указанным способом каждый символ принятого слова, мы правильно восстановим посланное кодовое слово, если произошло не более одной ошибки, и обна-
,94 ружим любую двойную ошибку. Тем самым полностью используются корректирующие способности данного кода — ведь его кодовое расстояние равно 4.
Разобранный нами метод исправления и обнаружения ошибок называют мажоритарным декодированием (т. е. декодированием по принципу большинства). Применим он тогда, когда — как в нашем примере — для каждого символа aj существует система проверок
k
cV = Sa^ft, (2)
k
aZ = SisAl
и
обладающая тем свойством, что в правую часть каждой проверки входят символы, отличные от ау, и всякий такой символ входит не более чем в одну проверку. Такая система проверок называется ортогональной (или разделенной). Если число проверок, входящих в каждую ортогональную систему, не меньше S, то путем голосования могут быть исправлены любые t ошибок, где ^<(s+1)/2. В самом деле, ошибка в одном символе влияет в силу ортогональности не более чем на одну проверку, следовательно, среди значений символа Gty, которые даются всеми соотношениями (2), неправильными могут оказаться не более t, т. е. не более половины значений. Тогда, сравнивая значения правых частей проверок, а также значение самого символа а,., мы по большинству голосов определяем верное значение этого символа. Если же (при нечетном s) t= (s+1)/2, то имеет место равенство голосов, ошибка при этом хотя и обнаруживается, но не исправляется.
Случай, когда число s проверок в каждой ортогональной системе на единицу меньше кодового расстояния d, т. е. когда s=d—1, является в известном смысле идеальным. В этом случае голосование позволяет, как и в рассмотренном примере, полностью реализовать корректирующие свойства кода. Код, для каждого символа которого существует система из (d—1) ортогональных проверок, называется полностью ортогонализуемым.
Чем хорош метод голосования? Прежде всего тем, что его техническая реализация предельно проста (особенно в случае двоичных циклических кодов). Наряду с обычными сумматорами и ячейками памяти схема декодирования дол-
,95 ясна содержать мажоритарный элемент (логическую схему, осуществляющую выбор значения а,- по большинству голосов).
Вот как устроена принципиальная схема мажоритарного декодирования для (7,3)-кода, упомянутого выше (рис. 24, а).
В этой схеме M — мажоритарный элемент, осуществляющий голосование, К — переключатель, находящийся в
положении 0 во время приема сообщения и в положении / при его декодировании. Рис. 24, а соответствует моменту, когда сообщение полностью поступило в запоминающий регистр и ключ К переводится в положение 1. Начинается декодирование. На первом его шаге (первый такт) на вход мажоритарного элемента подаются значения а0, Ct1+^, а2+ + ав, а4+а5. Ha выходе его появляется символ а'3, являющийся итогом голосования. В следующем такте происходит сдвиг сообщения в регистре, а символ c?.j поступает в последнюю ячейку памяти. Этому моменту соответствует рис. 24, б.
