У. Питерсон - Коды, исправляющие ошибки (1267328), страница 32
Текст из файла (страница 32)
Они охватывают некоторое количество неограниченных классов и все возможные значения т, кратные 4, до 200, за исключением 188. Остается не опровергнутым предположение о существовании матрицы Адамара для любого и, кратного 4. 5.7. Произведения кодов Для того чтобы получить более мощные коды, можно использовать комбинации двух или более кодов. Например, при помощи единственной проверки на четность для компонент каждого векгора можно обнаружить все одиночные ошибки. Рассмотрим теперь чнформационпые символы, образующие прямоугольную таблицу, как это показано на фиг. 5,2, с одной проверкой на четность по всем символам для каждой строки и каждого столбца.
Этот код, полученный из простейшего кода с проверкой на четность, мож.т исправлять все одиночные ошибки, ибо, если произошла одна эшибка, строка и столбец, в которых она произошла„будут ука~аны неверными результатами проверок на четность. В самом деле. Фвг. б.а. Структура произведения кодов. а — общий вид; б — двоиеиий код-ироизведеиие. минимальный вес этого кода, являющегося линейным, равен 4, так как он ранен весу кодового слова, имеющего ненулевые компоненты на пересечении двух строк и двух столбцов. Этот код используется на практике для обнаружения ошибок на магнитной ленте в вычислительных машинах. Важным обобщением этого кода нвляется код, получаемый в том случае, когда в качестве строк таблицы берутся векторы из одного кода, а в качестве столбцов — векторы из другого кода.
Произведения кодов можно также строить на основе трехмерных таблиц и таблиц более высоких размерностей. При этом получаются линейные коды и порождающая матрица произведения двух кодов комбинаторно эквивалентна тензорному произведению порождающих матриц двух первоначальных кодов.
Следует отметить, что некоторые символы, например символы, расположенные на фиг. 5.2 в нижнем правом углу, получаются как проверки проверочных символов. Они могут быть простроены на основе проверок по строкам и тогда будут удовлетворять проверке по столбцам, и наоборот. Если они построены при помощи пРоверок по строкам на основе соответствующих проверочных правил для кода, используемого в строках таблицы, то каждый провеРочный столбец является в действительности линейной комбинацией столбцов, содержащих информационные символы. Добавление к каждому из этих столбцов проверочных символов превращает любой столбец в кодовый вектор, и, следовательно, проверочные ~~абды, будучи линейными комбинациями кодовых векторов для кода, используемого в столбцах таблицы, также являются кодовыми векторами из этого кода.
мягно сделать несколько замечаний относительно возможности этих кодов исправлять ошибки. Теорема 5.3 (Злайес). Минимальный вес произведения двух кодов равен произведению минимальных весов этих кодов, Доказательство. Если минимальный вес для одного кода равен гэ1 и иг для другого, то вектор, принадлежащий произведению кодов, должен иметь по крайней мере в, ненулевых элементов в каждой строке, которая содержит ненулевые элементы, и по крайней мере гсг ненулевых элементов в каждом столбце, который содержит ненулевые элементы и, следовательно, должен иметь ш,шг ненулевых элементов, если он вообще содержит ненулевые элементы. Кроме того, по крайней мере одна такая комбинация элементов существует, если в первом коде найдется вектор веса гсь а во втором коде в вектор веса гсь Ч. т. д.
В дальнейшем изложении индексы 1 и 2 относятся к кодам, расположенным соответственно в строках и столбцах таблицы. Если таблица произведения кодов заполняется полученными символами по строкам, то в любой столбец может попасть самое большее Ьэ символов из пакета длины, не превосходящей п~Ьь Таким образом, если способность к исправлению пакетов ошибок для кода, расположенного в столбцах, характеризуется величиной Ьь то соответствующая величина Ь, характеризующая произведение кодов, равна по меньшей мере Ьгпь Аналогичные рассуждения для случая, когда таблица заполняется по столбцам, позволяют сделать окончательный вывод, что Ь'= тах(Ьэпо Ь~пг).
(5.4) В действительности этот результат можно слегка улучшить (задача 5.11). Поскольку произведения кодов могут исправлять как случайные ошибки, так и пакеты ошибок, то естественно возникает вопрос, какова способность кода исправлять пакеты ошибок, если код исправляет все комбинации ошибок веса 1 = ((й|йг — 1)/2] или меньше. Частичный ответ содержится в следующей теореме: Теорема 5.4 (Батон и Уэлдон). Произведение (пи й1)-кода, для которого способность исправлять пакеты ошибок равна 1, = =[(й~ — 1)/2], и (пв кг)-кода, для которого аналогичная величина равна 1, = ((йэ — 1)/2], может исправлять все комбинации ошибок веса 1=((й1йг — 1)/2] или меньше и все пакеты длины, не превосходящей Ь = гпах (пА, пг(1].
Доказательство. Утверждение о способности кода исправлять случайные ошибки является следствием теоремы 5.3; остается поэтому только показать, что никакой смежный класс не содержит комбинации ошибок веса 1 или меньше и пакета длины Ь нли меньше. Как и прежде, предположим, что таблица кода заполняется по строкам. Тогда в каждом столбце содержится самое болыпее (г ошибок в пакете длины п,1г или меньше. Если такой пакет ошибок и случайная комбинация ошибок веса, не превосходящего 1, принадлежат одному и тому же смежному классу, то их сумма является кодовым словом.
Каждый столбец такого кодового слова имеет либо нулевой вес, либо по меньшей мере вес Аь Каждый его ненулевой столбец должен содержать по меньшей мере с(з — 1э случайных ошибок и самое болыпее 1з ошибок из пакета. Таким образом, случайные ошибки должны быть распределены самое большее среди столбцов. Следовательно, вся таблица содержит самое большее ) (з + ( ( 2( < с( ненулевых элементов. Но, поскольку минимальный вес кода равен б, эта таблица не может быть кодовым словом и Ь ) п,1,. Меняя роли строк и столбцов в этом рассуждении, можно также показать, что 6 ) пело Ч. т.
д. Теорема 5.5. Если при передаче по двоичному симметричному каналу вероятность ошибки для первого кода равна ~~(Р), а вероятность ошибки для второго кода равна ~е(Р), то для произведения этих кодов возможно декодирование с вероятностью ошибки, не большей, чем ~т(~1(Р)). Доказательство. Предположим, что первый код используется в качестве строк и что после получения всей информации декодирование производится только по строкам. Тогда вероятность ошибки в некоторой строке равна ~,(Р) и, следовательно, вероятность ошибки в любом заданном символе не превосходит этой величины.
Кроме того, строки независимы между собой, и так как каждый столбец содержит только один символ из каждой строки, то элементы каждого столбца независимы между собой. Если теперь декодировать столбцы, используя код по столбцам, то получаемая вероятность ошибки не превысит ~т(Ц~(Р)). Могут, конечно, существовать и лучшие способы декодирования. Ч. т. д. Элайес очень интересно использовал эти идеи для того, чтобы найти для двоичного симметричного канала последовательность кодов, вероятности ошибок для которых стремятся к нулю, когда длина кодов неограниченно возрастает, а скорости передачи при этом стремятся к пределу, который болыпе нуля.
Это один из немногих известных примеров кодовой системы, обладающей обоими этими свойствами, ~ Рассматриваемой системе используется код Хэмминга, исправл Этот Равлнющий одиночные ошибки и обнаруживающий две ошибки. от код содержит и = 2 символов„из которых т+ 1 символов проверочные и 2 — л2 — 1 символов информационные. (См. равд. 5.!.) Код исправляет одиночные ошибки. Все комбинации из четного числа ошибок либо обнаруживаются, либо являются кодовыми векторами, но в обоих случаях в полученный вектор не вносятся никакие изменения. Однако если число ошибок нечетко и равно самое мекьшее трем, то ошибки будут исправляться н один символ, вероятнее всего правильный, будет заменен; таким образом, вводится еще одна ошибка.
Вероятность заданной комбинации из 1 ошибок равна Р%л — '; имеется всего С'„таких комбинаций, я, следовательно, вероятность того, что произойдет 1 ошибок, равна Р (1) = С2Р~(~" ~. Среднее число ошибок в блоке тогда равно л л-2 лр, ~ ~~е 1Р(2)+ ~ (1+ 1) РЯ( по чечнлн 2 ~ 2 по нечечннн Е й 3 ~~2С'„Р'~-'+ ~Х~, (1+ 1) СлР'Я"-' = г=з (2+!) С~ л 2С2Р2 дл 2+ ~ч 2+ Се 2ре ныл е 2-2 (н'и*'12" '-Нуп2:*22 'О' '~- г-2 л — 2 еп Р~Я' '.~- 2 и',РО" ' '1— 2 1 =2Се,Р'=п(п — 1)Р', я, следовательно, вероятность того, что после исправлении ошибок в некотором символе останется ошибка, будет Р1 ~ (и — 1) Р2 < лр2.
(5.5) Рассмотрим теперь произведение г таких кодов, в котором длина первого кода равна и = 2'", а длина каждого следующего кода в 2 раза больше по сравнению с предыдущим, так что код, используемый как Рй сомножитель, имеет длину, равную 2 .г'-'. Пусть Р2 = Р— вероятности ошибки в канале, а Р; — вероятность ошибки после 1 итераций (произведений ( кодов). Тогда в соответствии с (5.5) р ~ 2пе+2 — 1р2 (5.6) а последовательное пРименение неравенства (Ь.б) совместно с тождеством (4.64) дает Р, < (2 / (2 ~~)~ (2т+з)а з (2т+ -1) м Ро =(2 ~~РО)~.
(57) Это выражение стремится к нулю, когда г стремится к бесконечности, если только 2 Р,( '/м т. е. если среднее число ошибок в строке в первой итерации меньше, чем '/м Наконец, долю символов, которые будут информационными символами после г итераций, можно оценить следующим образом. Число проверочных символов кода, используемого в /-й итерации, равно 1оазп+ 1 = т+ й так что доля информационных символов равна т+1 2т ы — ! и на каждом шаге добавляются проверочные символы, сокрашая долю всех информационных символов на это отношение.
Следовательно, результирующая скорость передачи равна ( т(1)( т+2) ( т+г ) Это выражение может быть ограничено снизу на основе неравенства (1 — а) (1 — Ь) > 1 — (а+ Ь) при а > 0 и Ь > О, которое совместно с неравенством (4.53) дает ~т+1 т+2 т+г Х т+2 Из изложенного выше следует, что если вероятность ошибки в канале достаточно мала для того, чтобы среднее число ошибок в каждой стРоке пеРвой итеРации было меньше '/х, то веРоЯтность ошибки может быть сделана произвольно малой, если использовать достаточное число итераций, причем скорость передачи, или доля символов, несущих информацию, для любого числа итераций остается больше некоторой постоянной величины.
Скорость передачи для этого кода оказывается меньше скорости передачи, которую можно достигнуть в соответствии с основной теоремой Шеннона для каналов с шумом. действительно, эффективность рассматриваемо~о кода определяется с некотором смысле эффективностью первой итерации. Вероятность ошибки (н эффективность) первой итерации ограничена для коротких кодов границей сферической упаковки, так что для того, чтобы увеличить эффективность сверх некоторого предела, надо увеличить длину первой итерации. (Используемое здесь понятие эффективности может быть сделано точным; см. работу Питерсона [231].) Возможно, однако, что причиной всего этого является плохой выбор не кода, а метода декодирования.
Другое важное замечание состоит в том, что минимальный вес произведения г кодов равен 4; так как на каждом шаге используется код с минимальным весом 4. Отношение минимального веса к длине кода 2 2м-вг-'« '«"-1>lм и 2 ° 2м Ы ... 2~~~ (5.9) 5.8. Теоретико-графовые коды Линейным нгориентированным графом называется совокупность из т вершин и и соединяющих их ребер. На фиг. 5.3 показан граф с т = 10 и и = 15. Занумеруем все ребра графа произвольным образом числами от 1 до и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
