3.4. Поэтапное декодирование

Предположим, что для каждого полученного вектора можно определить вес минимального по весу элемента в его смежном классе. Это было бы возможно, если бы в нашем распоряжении была бы таблица, показывающая связь между синдромом и образующим смежного класса. Возможно, однако, что для определения веса потребуется память много меньше, чем для такой таблицы синдромов; и, действительно, это так для некоторых кодов, рассматриваемых в гл. 11. В этом случае декодирование можно производить следующим поэтапным образом.

Занумеруем элементы поля от 1 до произвольным образом, но так, чтобы нулевой элемент был последним. Теперь упорядочим векторы лексикографически, т. е. так, что следует за если следует за в упорядоченном расположении элементов поля и если место — первое, в котором эти два вектора отличны друг от друга. Определим вес смежного класса как вес минимального по весу элемента в данном смежном классе.

Для полученного вектора прежде всего определим вес смежного класса. Затем заменим последовательно на д., где это элемент поля в выбранном упорядочении элементов поля. Определим вес смежного класса, содержащего полученный вектор с измененной первой компонентой. Если при каком-либо из этих вычитаний вес уменьшится, то заменим на где первый элемент поля, приводящий к уменьшению веса. Если уменьшения веса не произошло, то остается в качестве первой компоненты. Затем та же самая процедура применяется последовательно ко второй, третьей и всем остальным компонентам до тех пор, пока не будет получен вектор, принадлежащий смежному классу веса 0, т. е. самому коду. Предполагается, что это и есть тот кодовый вектор, который был передан. Этот прием называется поэтапным декодированием. Ниже будет показано, что при поэтапном декодировании каждый полученный вектор декодируется в ближайший кодовый вектор и что образующие смежных классов в таблице декодирования обладают некоторыми интересными свойствами.

Вектор называется "непосредственным потомком" вектора и, если может быть получен из и путем замены одной ненулевой компоненты нулем. Вектор называется "потомком" если

существует цепь такая, что для каждого вектор непосредственный потомок вектора

Теорема 3.8. Если вектор минимального веса в своем смежном классе а — потомок то — вектор минимального веса в своем смежном классе.

Доказательство. Достаточно доказать теорему для непосредственного потомка, поскольку рассматриваемое свойство передается по наследству. Пусть где вектор веса Каждый элемент из -смежного класса, который содержит имеет вид где кодовый вектор. Так как вектор принадлежит смежному классу и так как вес вектора равен 1, то каждый вектор из отличается только одной компонентой от некоторого вектора из класса Поэтому вес смежного класса может отличаться не более чем на 1 от веса смежного класса Но вес вектора и на единицу меньше веса так что вектор и должен быть элементом минимального веса в своем смежном классе. Ч. т. д.

Теорема 3.9. Если — вектор минимального веса в своем смежном классе, предшествующий всем другим векторам минимального веса в этом смежном классе, и если потомок и, то элемент минимального веса в своем смежном классе, предшествующий всем другим элементам минимального веса в этом смежном классе.

Доказательство. Снова достаточно доказать теорему для непосредственных потомков. Предположим, что причем вектор содержит нули всюду, кроме компоненты. Тогда каждый элемент из смежного классаотличается от некоторого элемента из смежного класса точно на Следовательно, какдый элемент минимального веса из смежного класса должен иметь нуль в компоненте, так как каждый элемент минимальною веса из содержит больше нулей, чем соответствующий элемент из Поэтому каждый элемент минимального веса из смежного класса должен получаться как результат вычитания вектора из некоторого элемента минимального веса смежного класса Сравним вектор с любым другим элементом минимального веса из Элемент получается вычитанием из получается вычитанием вектора из некоторого другого элемента минимального веса смежного класса . У обоих векторов компоненты должны совпадать с компонентой вектора Следовательно, так как и предшествует то вектор предшествует

Теорема 3.10 (Слепяна — Мура). Если в каждом смежном классе в качестве образующего выбран элемент минимального веса, предшествующий всем другим элементам

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

Эта теорема непосредственно следует из теоремы 3.9.

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

Доказательство. Пусть полученный вектор, и пусть вектор минимального веса в смежном классе который предшествует всем другим элементам минимального веса в этом смежном классе. Обозначим через вектор, содержащий единицу в качестве компоненты и нули в качестве всех остальных. Пусть далее

где вес вектора где

и где элементы поля.

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

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

является Для доказательство проведено в предыдущем абзаце. Предположим, что нужное нам утверждение верно для Тогда вектор принадлежит тому же самому смежному классу, которому принадлежит вектор потому что является кодовым вектором. Поскольку потомок то по теореме 3.9 он является элементом минимального веса в своем смежном классе, предшествующим всем другим элементам минимального веса. Те же рассуждения, что и в предыдущем абзаце, показывают поэтому, что следующее изменение в процессе поэтапного декодирования состоит в вычитании из в результате чего получается вектор Это верно независимо от того, начинается ли поэтапное декодирование заново с первой компоненты или просто продолжается после последнего изменения.

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