в. Мажоритарное декодирование

Сейчас мы дадим первый из двух алгоритмов, который можно использовать для определения из системы проверок ортогональной относительно Будем использовать символы и для обозначения наибольшего целого числа, не превосходящего и наименьшего целого числа, не меньшего соответственно и будем говорить, что шумовой

символ контролируется некоторой проверкой тогда и только тогда, когда он входит в эту проверку с коэффициентом, отличным от нуля.

Теорема 1. Пусть отличны от нуля не болев ошибок в совокупности контролируемых системой составных проверок ортогональных относительно (т. е. имеется не более ошибок в соответствующих принятых символах). Тогда истинное значение ошибки есть значение, принимаемое большинством составных проверок (В случае когда ни одно значение из не принимается абсолютным большинством составных проверок и одно из наиболее часто встречающихся значений есть 0, полагаем

Доказательство. Положим и допустим сначала, что все другие контролируемые имеют значение 0. Тогда из (11) и (13) следует, что

Пусть теперь и выполняются условия теоремы. ненулевых шумовых символов могут изменить более чем такое же число равенств в (15), и потому не менее чем составных проверок - все еще равны нулю. Таким образом, нуль является либо наиболее часто встречающимся, либо одним из двух одинаково часто встречающихся значений в в обоих случаях правило декодирования, указанное в теореме, дает правильное значение шумового символа

Наоборот, положим Тогда из того, что следует, что отлично от нуля менее других шумовых символов, контролируемых проверками и отсюда, что более чем равенств в (15) все еще правильно, указывают значение Таким образом, правило декодирования, указанное в теореме, снова остается верным, и теорема доказана.

Если т. е. четно, то из теоремы 1 следует, что может быть правильно определено во всех

чаях, когда среди принятых символов искажено не более Аналогично, если нечетно, то снова может быть найдено во всех случаях, когда произошло не более ошибок; могут быть обнаружены дополнительно ошибок, если условиться, что произошла ошибка, когда значение, принятое большинством проверок оказывается отличным от нуля и встречается в точности раз. Эти соображения означают, что любые два кодовых слова с различными значениями символа должны находиться друг от друга на расстоянии не менее чем будем использовать всегда расстояние Хемминга, т. е. число символов, в которых кодовые слова различны.) Таким образом, мы приходим к следствию из теоремы 1.

Следствие. Если линейный код допускает образование системы проверок, ортогональных относительно то расстояние Хемминга между любыми двумя кодовыми словами с различными значениями символа не менее

Декодирование, выполняемое согласно алгоритму теоремы 1, будем называть мажоритарным декодированием для случая ортогональных проверок. Из предыдущих рассуждений должно быть ясно, что мажоритарное декодирование есть не что иное, как форма декодирования по минимальному расстоянию; в самом деле, мажоритарное декодирование приписывает символу такое значение, которое он принимает в шумовой последовательности минимального веса, удовлетворяющей системе (11). Важно отметить, что эта шумовая последовательность, вообще говоря, не совпадает с шумовой последовательностью минимального веса, удовлетворяющей системе (7), так как соответствие между не обязательно должно быть взаимно однозначным.