У. Питерсон - Коды, исправляющие ошибки (1267328), страница 15
Текст из файла (страница 15)
Компоненты вектора 8 равны нулю для тех соотношений, которыеудовлетворяются, и не равны нулю для всех остальных. Теорема З.О. Два вектора чс и чг принадлежат одному и толу же смежному классу тогда и только тогда, когда их синдромы рваньи Доказательство. Во второй главе было показано, что два элемента группы ч, и чг принадлежат одному и тому же смежному классу тогда н только тогда, когда ( — ч,)+ чс = ч, — ч, есть элемент подгруппы, которой в данном случае является кодовое векторное пространство. Если кодовое пространство — это нулевое пространство матрицы Н, то вектор ч, — ч, принадлежит кодовому пространству тогда и только тогда, когда (ч, — ч,) Н = О.
Поскольку для умножения матриц справедлив дистрибутивный закон, то (ч — ч) Нт — ч Нт — ч Нт — О так что вектор ч, — чг является кодовым вектором тогда и только тогда, когда синдромы векторов ч, и чг равны. Ч. т. д. Процесс декодирования может быть значительно упрощен за счет использования таблицы декодирования. Таблица строится так, что в ней приводятся образующие смежных классов и синдромы для каждого из 2"-ь смежных классов.
После того как получен вектор, вычисляется его синдром. Затем по таблице отыскивается образующий смежного класса, являющийся предполагаемым набором ошибок; вычитание его из полученного вектора дает предположительно посланный кодовый вектор. Хотя в большинстве случаев такая процедура во много раз уменьшает требования к объему памяти при осуществлении декодирования, этот объем все-таки может быть очень большим.
Например, для двоичного (1!Х1, ЯО) -кода требуется таблица декодирования с 2'ьь входами, ч о, конечно, далеко выходит за пределы разумного. Число смеж„,х классов равно 2гь — величине, множно меньшей, но тем не менее все еще совсем нереальной. '!'еорел1а 3.7. Пусть у — линейный двоичный (и, к)-код (т. е. групповой код), используемый для передачи по двоичному симметричному каналу. Предположим, что все кодовые векторы имеют одну и ту же вероятность быть переданными.
Тогда средняя вероятность правильного декодирования совпадает с наиболыией возможной для этого кода, если в качестве таблицы декодирования используется стандартное расположение, в котором каждый образуюи!ий смежного класса имеет минимальный вес в своем классе. Доказательство. Обозначим через т;; вектор, стоящий в 1-й строке и 1-м столбце таблицы декодирования. Кодовое слово в верхней строке столбца обозначим через чм.
Обозначим через йм расстояние Хзмминга между полученным вектором т;, и кодо. вым словом тьь в которое он преобразуется при декодировании. Тогда вероятность правильного декодирования, если было передано слово чгн равна ач-ь Ргн1;!" гм, ~-ь где Р— вероятность ошибки в канале, а Я = 1 — Р (см. фиг. 1.4), Поскольку имеется 2" кодовых слов, которые предполагаются равновероятными, то при осреднении вероятности правильного декодирования используется весовой множитель 2 †": 2-ь ~.~ Рлн()~-л,.~ Каждому возможному двоичному вектору на выходе в втой сумме соответствует одно слагаемое, и каждое из этих слагаемых принимает максимальное значение, если соответствующий вектор декодируется в ближайший кодовый вектор в смысле Хзмминга, так как Р"'/Я™Несть монотонно убывающая функция от йн.
Поэтому вероятность правильного декодирования будет максимальной, если каждый полученный вектор будет преобразовываться в ближайший кодовый вектор. Предположим теперь,' что некоторый вектор ч расположен в таблице декодирования под кодовым вектором н, так что расстояние Хзмминга между ними равно ге. Допустим, что ближайший кодовый вектор н~ находится на расстоянии в.
Пусть н— ь о разующий смежного класса, содержащего вектор ч. Тогда вес веси н ~ектора н = ч — ц равен ш. Элемент ч — и, = й+(н — и ) имеет 1 н лежит в том же самом смежном классе. Поскольку пред- 1 — — 1 слагалось, что н имеет минимальный вес в своем смежном классе, то гв~ ) гз, и поэтому т лежит по крайней мере так же близко к и, как и к и,. Ч. т.
д. Число образующих смежных классов веса 1 обозначим через иь Вероятность правильного декодирования может быть записана тогда следующим образом: Р,=о4Х+а~РЯ" + азР Я" + "° ° Пример. Стандартное расположение для кода, использованного в предыдущих примерах, имеет вид 00000 10011 01010 11001 00101 10110 01111 11100 00001 10010 0101! 11000 00100 10111 01110 11101 00010 10001 01000 1!011 001!! 1О!00 01101 111 10 10000 00011 11010 01001 10101 00110 11111 01100 Во всех случаях в качестве образующего смежного класса выбран один из не использованных ранее векторов наименьшего веса, что приводит к оптимальному декодированию. (Заметим, что это не значит, что код оптимален. Мажет случиться, хотя это и неверно в данном случае, что другой выбор кодовых слов даст меньшую вероятность ошибки.) Этот код исправляет три нз пяти возможных наборов из одной ошибки.
Заметим, что векторы (О О О О 1) н (О О 1 0 О) принадлежат одному и тому же смежному классу, поскольку (О 0 1 О 1) — их разность — есть кодовый вектор. Следовательно, оба эти набора ошибок не могут быть одновременно исправлены. Это справедливо во всех случаях, когда имеется кодовое слово веса 2; минимальный вес 3 является необходимым и достаточным условием для исправления всех единичных ошибок. Рассматриваемый код удовлетворяет обеим проверкам на четность. Лля первого за кодом смежного класса в стандартном расположении синдром равея 01, для следующего смежного класса 10 и для последнего 1!.
Заметим, что в каждом смежном классе имеется вектор с нулями в качестве информационных символов и синдром в качестве проверочных символов. Для двоичного симметричного канала вероятность получения переданного кодового слова равна Я". Если Р ( Чм то это и есть наиболее вероятное из полученных слово. Кроме того, можно показать [293Ь что если передано кодовое слово, то общая вероятность того, что полученное слово является одним из кодовых слов (либо переданным, либо отличным от него), больше, чем вероятность того, что полученное слово принадлежит любому другому фиксированному смежному классу.
Стандартное расположение для сверточного кода имеет тот же вид, что и для блокового кода. Однако в этом случае декодирование будет правильным тогда, когда полученный набор лины и расположен в столбце, кодовый вектор которого совпадает с переданным вектором в первых пс компонентах. Это бъясняется тем, что только пг символов декоднруются одновременно. Таким образом, правильное декодирование происходит тогда, когда полученный набор длины и принадлежит тому же самому подмножеству (см.
гл. 1), в которое входит переданное кодовое слово. Для сверточных кодов справедлива теорема 3.5 в слегка измененном варианте. Теорема 3.8. Если стандартное расположение используется как таблица декодирования для сверточного кода, то первый блок из и символов полученного вектора ч будет правильно декодирован в соответствуюи(ий блок переданного вектора и тогда и только тогда, когда набор ошибок ч — и принадлежит правильному (первому) подмножеству. Доказательство. Доказательство аналогично доказательству теоремы 3.5 с тем изменением, что теперь правильное подмножество играет роль образующего смежного класса.
Если набор ошибок ч — и принадлежит правильному подмяожеству, то первые пс символов кодового слова и' — и, стоящего в первой строке соответствующего столбца, должны быть нулями. Таким образом, первые пс компонент кодового слова н=н+(н' — н) должны совпадать с первыми пг компонентами слова и, так что декодирование будет произведено правильно.
С другой стороны, если набор ошибок не принадлежит правильному подмножеству, то первые пс символов кодового слова н' — и необходимо не являются все нулями, и кодовое слово, которое получится в результате декодирования, будет отличаться от переданного слова первыми и, компонентами. Ч. т. д. Одно из основных различий между блоковыми и сверточнымн кодами состоит в том, что в сверточных кодах «правильный вектор», вычитаемый из полученного вектора декодером, и набор ошибок, прибавляемый каналом, могут отличаться, даже если декодирование производится правильно.
Для блоковых кодов эти два вектора должны, конечно, совпадать. Теорема 3.6 справедлива для сверточных кодов без каких-либо изменений. Тео табли ы рема 37 для сверточных кодов не верна При построении ицы декодирования для сверточного кода следовало бы стремиться к тому, чтобы полученный набор длины и был набором наименьшего веса в саптввтствующем правильном подмножестве. Однако в силу того, что наборы длины л в каждом смежном классе определяются выбором кодовых слов и образующего, ие все элементы наименьшего веса каждого смежного класса будут включены в правильное подмножество.
Вообще образующий смежного класса должен выбираться так, чтобы общая вероятность всех наборов длины и, принадлежа1цих правильному подмножеству, была бы наибольшей из возможных. Этот результат не кажется, однако, особенно глубоким и не используется при реальном декодировании. 3.5. Поэтапное декодирование для блоковых кодов Предположим, что для каждого полученного вектора можно определить вес минимального по весу элемента в его смежном классе.
Это было бы возможно, если бы в нашем распоряжении была таблица, устанавливающая связь между синдромом и образующим смежного класса. Иногда это можно сделать, используя объем памяти, много меньший, чем объем памяти, нужный для такой таблицы синдромов. В этом случае декодирование можно производить следующим образом. Занумеруем элементы поля от ! до д произвольным образом, но так, чтобы нулевой элемент был последним.
Теперь упорядочим векторы лексикографически, т. е. так, что (Ьь ., Ь„) следует за (аь...,а ), если Ь; следует за а~ в упорядоченном расположении элементов поля, и )че место — первое, в котором эти два вектора отличны друг от друга. Определим вес смежного класса как вес минимального по весу элемента в данном смежном классе. Для полученного вектора (по ам...,а ) прежде всего определим вес смежного класса. Затем а, заменим последовательна на а~ — ~ь а, — ), и т. д., где ~; — это ~-й элемент поля в выбранном упорядочении элементов поля. Определим вес смежного класса, содержащего полученный вектор с измененной первой компонентой. Если при каком-либо из этих вычитаний вес уменьшится, то заменим а1 на а1 — ~ь где ~; — первый элемент поля, приводящий к уменьшению веса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
