У. Питерсон - Коды, исправляющие ошибки (1267328), страница 16

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

Текст из файла (страница 16)

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

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

Вектор ч назынается потомком и, если существует цепь но — — н, нь нг, . н„=ч, такая, что для каждого 1 вектор и; — непосредственный потомок вектора пс ь Теорема 3.9. Если ч — вектор минимального веса в своем смежном классе и и — потомок ч, то и — вектор минимального веса в своем смежном классе. Доказательство. Достаточно доказать теорему для непосредственного потомка, поскольку рассматриваемое свойство передается по наследству. Пусть ч — е = н, где е — вектор веса 1. Каждый элемент из (и)-смежного класса, который содержит и, имеет вид э+и = э+ч — е, где з — кодовый вектор.

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

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

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

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

У обоих векторов и и н~ их й-е компоненты должны совпадать с А-й компонентой вектора е. Следовательно, так как и предшествует нь то вектор и предшествует чь Ч. т. д. Теорема 3.11 (Слепян — Мур). Если в каждом смежном классе в качестве образующего выбран элемент минимального веса, предшествующий всем другим элементам минимального веса, то каждый потомок образующего смежного класса является образуюи(им смежного класса. Эта теорема непосредственно следует из теоремы 3.10. Теорема 3.12 (Прейндж).

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

Доказательство, Пусть ч — полученный вектор, а д — вектор минимального веса в смежном классе (ч), который предшествует всем другим элементам минимального веса в этом смежном классе. Обозначим через е, вектор, ря компонента которого равна единице, а все остальные компоненты нулевые. Пусть, далее, д=~|е,,+ ... +) е,, где ш — вес вектора д, й ~ ... ~1 и )» ..., 1„,— элементы поля. Начиная доказательство, заметим, что первой компонентой вектора ч, изменяемой в процессе поэтапного декодирования, будет 1ки компонента, и из нее должен быть вычтен элемент 1» В самом деле, если не изменялась никакая из предшествующих компонент и никакой из предшествующих элементов поля не вычитался из 1гй компоненты, то из 1~й компоненты будет вычитаться элемент )» так как при этом элемент д'=д — 1,е,„имеющий вес ге — 1, будет находиться в смежном классе, содержащем измененный вектор, и, следовательно, этот смежный класс будет иметь вес, меньший чем ш.

Предположим, что или была изменена одна из предыдущих компонент, или что существует элемент поля, предшествующий 1» который был вычтен из 1гй компоненты. Допустим, что первое изменение равно 1'е,'. Тогда получившийся смежный класс должен иметь вес, не больший чем ге — 1, и, следовательно, вес образующего смежного класса д' не превышает ш — 1. Поэтому вектор у'+~'е, является элементом минимального веса в смежном классе (ч), предшествующем у, что противоречит сделанному предположению. Следовательно, первой компонентой вектора ч, изменяемой в процессе поэтапного декодирования, является 1мя компонента, и из нее вычитается элемент 1» Пусть ч; — вектор, полученный после 1 изменений вектора ч в процессе поэтапного декодирования.

Теперь индукцией по 1 будет показано, что 1-м изменением вектора ч, которое равно ч; ь ЯвлЯетсЯ ~,есь ДлЯ 1 = 1 доказательство пРоведено в пРеыдущем абзаце. Предположим, что нужное нам утверждение верно для 1(1. Тогда вектор н,=)~е, +)~,,е, + ... +!„е,. принадлежит тому же самому смежному классу, к которому относится вектор чь потому что 3~ — и — — д — т является кодовым вектором.

Поскольку 3~ — потомок 3, то по теореме 3.10 он является элементом минимального веса в своем смежном классе, предшествующим всем другим элементам минимального веса в этом смежном классе. Те же рассуждения, что и в предыдущем абзаце, показывают поэтому, что следующее изменение в процессе поэтапного декодиРованиЯ состоит в вычитании (,е, из гь в РезУльтате чего получается вектор тн.ь Это верно независимо от того, начинается ли поэтапное декодирование заново с первой компоненты или просто продолжается после последнего изменения.

Таким образом, в процессе поэтапного декодирования будет произведено и последовательных изменений вектора (,е , ... 1 ю ..., 1 е, в результате чего получится вектор ч — 3, который яв- %Р ляется искомым кодовым вектором. Ч. т. д. 3.6. Модулярное представление линейных блоковых кодов Пусть б — порождавшая матрица линейного (л,й)-кода. Поскольку эта матрица имеет й строк и чисто нулевой столбец может быть исключен из рассмотрения как бесполезный, существует всего д" — 1 различных типов возможных столбцов.

Если не обращать внимания на порядок расположения столбцов, то код можно задать указанием числа столбцов каждого типа. Этот способ задания и называется модулярным представлением кода. Пусть М вЂ” специальная матрица размерности ЙХ(д" — 1), содержащая в качестве столбцов все возможные векторы из й элементов поля, исключая нулевой вектор. Тогда 1-й столбец матрицы М можно рассматривать как столбец типа !', а код может быть задан вектором, образованным д» вЂ” 1 положительными целыми числами: й( = (пи пм .. '' пах — 1) в котором л; — число столбцов типа й Заметим, что матрица 1~= Мгб (3.16) Размерности (д" — !))(л в качестве строк содержит все возмож. ные ненулевые линейные комбинации строк матрицы 6. Таким образом, строками матрицы К являются все ненулевые кодовые векторы.

Важным частным случаем является матрица, которая содержит весь код, задаваемый матрицей М, если ее рассматривать как порождающую матрицу кода (3.17) Очевидно, что эта матрица симметрична и содержит по одному столбцу каждого возможного типа. Теперь рассмотрим случай двоичного кода. Теорема 3.!3 (Макдональд), Веса каждого из 2" — 1 ненулевых кодовых слов двоичного группового кода могут быть найдены как компоненты вектора, получающегося в результате матричного умножения (как матриц с действительными алементами) вектора й! модулярного представления на матрицу С: (3.18) % = !Ч!С илн чтт = СНт. (Веса кодовых слов упорядочены так же, как кодовые слова в матрице в равенстве (3.16).) Доказательство. Соотношение (3.18) легко доказать, если заметить, что йя компонента вектора Ъ7т получается в результате умножения (-й строки матрицы С на вектор г!.

Поскольку элементами матрицы С являются единицы и нули, то получается сумма некоторого подмножества компонент вектора Х, тех компонент, которые соответствуют столбцам, содержащим единицу в 1-м кодовом слове. Ч. т. д. Матрица С, рассматриваемая как матрица действительных чисел, является невырожденной. Матрицу, обратную к матрице С, можно получить, заменяя в матрице С каждый О на — 1 и деля каждый элемент на 2"-'. Для того чтобы доказать это, сначала покажем, что любые два различных столбца матрицы С содержат единицы в 2ч-' строках. Строки матрицы С с присоединенным к янм вектором из одних нулей образуют группу, поскольку онн составляют пространство строк матрицы М.

Рассмотрим совокупность строк, содержащих нули в (-м и 1-м столбцах. Легко проверить, что они образуют подгруппу. Далее, существуют четыре смежных класса, содержащих одно и то же число элементов, а именно: сама подгруппа; совокупность всех строк, содержащих О в (-м столбце и 1 в 1-м столбце; совокупность всех строк, содержащих 1 в 1-м столбце и О в 1-м столбце, и, наконец, совокупность всех строк, содержащих единицы в обоих столбцах. Таким образом, одна четвертая часть всех строк, или всего 2х-Я строк, содержит единицы в (-м и 1-м столбцах. Аналогичными рассуждениями можно доказать, что каждый столбец содержит 2"-' единиц.

Характеристики

Список файлов книги