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

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

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

Обозначим эту матрицу через Кь Существует д' линейных комбинаций 1 независимых столбцов. Однако поскольку в матрице б, нет нулевого столбца и имеется только один столбец из каждой совокупности д — 1 столбцов, пропорциональных одному и тому же столбцу, то в матрице К; будет (д' — 1)/(д — !) столбцов, Ранг столбцов матрицы К; равен / по определению, н поскольку ранг столбцов равен рангу строк, то анг строк матрицы К; равен также й Это значит, что среди строк матрицы К; имеется ! линейно независимых строк, а все остальные с~роки являются линейными комбинациями этих 1 строк. Пусть К',. — матрица размерности !)([(д! — 1)/(1 — 1Ц, состоящая из 1 независимых строк матрицы К;.

Тогда любые два столбца матрицы не пропорциональны, и любая линейная комбинация строк матрицы К'; и, следовательно, соответствующих строк матрицы К; является последовательностью веса в'-'. Таким образом, если новая матрица Сь полученная из матрицы 6, отбрасыванием столбцов, входящих в матрицу Кь содержит А строк и [(д" — 1)/(д — 1))— [(у' — 1)/(д — 1)! столбцов, то минимальный вес порождаемого ею кода равен у" ' — д! '. (В этом коде будут еще кодовые слова веса д"-', соответствующие линейным комбинациям строк матрицы Кь равным нулевому вектору.) На кодах с порождающей матрнцей С', все еще достигается граница, задаваемая теоремой 4,3, Вообще коды, на которых достигается граница, задаваемая теоремой 4.3, можно получать, отбрасывая совокупности из (йч — 1)/(д — !) столбцов матрицы 6„ выбранных только что описанным способом из той или иной матриц бь которые составляют матрицу бм если только для любого заданного 1 отбрасывается не более чем д — 1 совокупностей и остаются совокупности из (а! — 1)/(д — 1) столбцов этого типа.

В частности, это верно, если выполняются условия следующей ниже теоремы, а иногда, если даже эти условия и не выполняются. Теорема 4.4. Сугцествует код, для которого достигается граница, задаваемая теоремой 4,3, если: !) з)б; для всех 1 и 2) сумма значений й для которых б; Ф'О, не превосходит й. В теореме 4.4 накладываются условия на разряды в выражении для числа зэк-! — й. Вообще говоря, они могут как принимать, так и не принимать значение О. Простейшее выражение для границы получается в предположении, что б; = О.

Поскольку з приблизительно равно а/у" ', то получается неравенство которое совпадает с границей Плоткина. Эта,граница достигаетсь для значительно меньшего класса кодов, чем граница, даваемая теоремой 4.4. Верхняя граница Хэмминга для й может быть получена следующим образом. Линейный (и, й)-код содержит д" кодовых векторов и порождает д" — х смежных классов. Если код исправляет все комбин или меньше анин из 1 или меньшего числа ошибок, то всевектор!!ве р са еньше должны быть образующими смежных классов, Таким образом, число векторов веса 1 или меньше не должно превосходить числа смежных классов: 1+ С„'(у — Ц+ С'„(о — 1)'+ ...

+ С'„(у — 1)'~д" '. Теорема 4.5. Для любого блокового (и, й)-кода с минимальным весом 21+ 1 или болыие число проверочных символов и — й)1одд(!+ С„'(д — 1)+С~ (д — 1) + . „. +С',(д — 1)'(. (4,12) Эта граница может быть получена также для нелинейных кодов.

Снова можно найти и асимптотические формулы. Для простоты положим у = 2, и пусть 1ь — наибольшее целое 1, для которого справедливо соотношение (4.12). Тогда 1 — — '~ — '1од[1+С'„+ ... +СД Используя результаты приложения А, легко показать, что в пределе при и, стремящемся к бесконечности, отношение Цп для любого блокового (п, я)-кода не может превышать 1ь/и, где --.'= ( — '.") (4.13) В этой пределькой форме граница Хэмминга показана на фиг. 4.1.

Можно определить еще одну верхнюю границу для минимального расстояния, которая справедлива как для линейных, так и для нелинейных блоковых кодов. Это верхняя граница Элайеса. При получении этой границы используются идеи, лежашие в основе рассуждений при выводе границ Плоткина и Хэмминга; при больших значениях и зта граница оказывается более точной, чем каждая нз двух последних. Граница Злайеса может быть получена для кодов с д символами 120), но здесь мы ограничимся случаем двоичных кодов. Рассмотрим блоковый (п, й)-код.

Сфера радиуса 1 в п-мерном пространстве с центром в 1-м наборе длины и содержит К; кодовых векторов, 1= 1, 2, ..., 2*'. Число точек, попадающих в каждую 1 сферу, равно ~„С~ „и каждое из 2" кодовых слов попадаст в так-е кое же количество сфер. Таким образом, Я" )', К;=2 ~, С~. (4.14) Обозначим через К наибольшее из чисел К;; поскольку К по меньшей мере столь же велико, как среднее значение чисел Кь то т ~. с'„ (4.15) Это значит, что существует сфера радиуса !, содержащая К кодощ!х слов. Заметим, что пентром этой сферы не обязательно является кодовое слово. Следующий этап получения границы Элайеса состоит в Вычислении среднего расстояния между этими К кодовыми словами. Будет показано, что при соответствующем выборе 1 кодовые слова должны располагаться ближе друг к другу, чем это гарантируется границами Хэмминга или Плоткина. Рассмотрим К наборов длины и, которые получаются в результате вычитания центрального набора длины л из К кодовых слов.

Обозначим эти наборы через ап ам ... а!а аз! ам ... а,„ (4.16) вк! пкз ° ° нк Пусть га! — вес !ьго из этих наборов. Поскольку радиус сферы равен 1, то общий вес этих наборов длины а не превосходит К1, т. е. ~: ю,~~К1. ! ! Пусть через ол 1= 1, 2, ..., а, обозначен вес )что столбца таблицы (4.16), т. е. пусть в этом столбце содержится К вЂ” и! нулей и и! единиц, Очевидно, что ~ п!~~Кг. У ! Общее расстояние Н0а,ч между наборами !4.16) равно сумме Скк попарных расстояний между наборами длины п, входящими в эту таблицу. При этом вклад )ьго столбца в выражение для д,а!„удовлетворяет соотношениям 1!>! К(а. +а! )=Ск! — Сз — Сз =и (К вЂ” и) Суммируя по /, получаем (4.17) ! 1 ! 1 Рассмотрим теперь сумму оп + па.

Если с > п + 1, то увеличение и!, на 1 и уменьшение пь на 1 приводят к уменьшению суммы и!з, +о!, так как (пн — 1)'+ ~, + 1) — ( т, + и) = 2( ь — н+ 1) С О. Отсюда следует, что прн любом выборе чисел ои таком, что и ) о! — — К! — Ь, где Ь~)0, / ! ~ч",) и (К" ')'. Поэтому из равенства (4.17) получаем д .

К!К вЂ” Ь) — п(К' а)' !К (1 — — ') — ЬК(1 — — "). Для любого кода ! ( и!2, поэтому д., ~(!К'(! — — '). Далее из Ск попарных расстояний по меньшей мере одно не пре- 2 восходит среднего значения этих расстояний; обозначим его через д. Тогда --(2 — (1 — — ) ( — ). Этот результат справедлив при л!обом выборе !!и, таком, что правая часть неравенства !4.15) превосходит единицу. !При К = 1 все эти рассуждения не применимы, так как никаких расстояний внутри сферы в этом случае нет.) Наиболее точная граница получается, если отношение !/и выбирается немного большим, чем его минимальное значение.

Этот результат можно сформулировать следующим образом: Теорема 4.6. Для любого блокового !и, й)-кода ми!!има !зное расстояние удовлетворяет неравенству д~2! (1 — — „') ( „~, ), где ! — любое целое число, такое, что ! ,)'„С~ > 2" с-о а К вЂ” наименьшее целое число, удовлетворяющее неравенству К )~ 2" Предельную форму границы Элайеса для больших значений п можно записать следующим образом: где ! задается равенством (4.13). В этой форме граница изображена иа фиг. 4,1. Получены также другие верхние границы для й, которые в некоторых случаях точнее вышеприведенных границ. (См., например, работы (155, 156, 320!.) Однако эти результаты не улучшают аснмптотическую границу Элайеса, а при малых значениях и они являются обычно более сложными, чем границы Хзмминга или Плоткина.

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

В соответствии с теоремой 3.1 нулевое пространство матрицы, любые а' — 1 или меньшее число столбцов которой линейно независимы, является линейным кодом с минимальным расстоянием, равным самое меньшее а. Этот результат дает возможность предложить следующий способ построения кода с г проверочными символами и минимальным весом й. В качестве первого столбца проверочной матрицы выберем любой ненулевой набор длины г.Затем возьмем любой яенулевой набор длины г, не кратный первому набору, и будем рассматривать его как второи столбец проверочной матрицы. Третьим столбцом матрицы может быть любой набор длины г, не являющийся линейной комбинацией первых двух. Вообще в качестве йго столбца матрицы выбирается любой набор длины г, не являюгцийся линейной комбинацией а — 2 или меньшего числа предыдущих столбцов.

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

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