10.10. ДЕКОДИРОВАНИЕ КОДОВ РИДА-СОЛОМОНА

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

Предположим, что было передано кодовое слово (10.6), имел место вектор ошибок и был принят вектор Таким образом, декодер знает следующие суммы:

Если ошибок не произошло, то и для определения сообщения могут быть решены любые К из этих уравнений, так как матрица коэффициентов является матрицей Вандермонда (см. лемму 17 гл. 4). Таким образом, всего имеется различных возможностей, или голосов, для определения истинного вектора и.

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

Теорема 6. Если произошло ошибок, то любой неправильный вектор и получит самое большее голосов. Истинный вектор и получит по крайней мере голосов.

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

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

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